Re: [問題] 以bit為單位的無失真compressor...

[mgtsai (鐵軌不是我偷的)]

※ 引述《CWP (ccc)》之銘言：
: <後文恕刪>
: 我想Shannon的問題不是他太早死了,
: 而是這東西本來就不是他所原創的.
: 這個式子老早就出現在早一個世紀的物理學家Boltzmann的墓碑上了. :p

簡單地說，消息理論其實是承襲自熱力學 (統計力學)
而 entropy 一字更是直接沿用自統計力學

以消息理論第一定律，直接套用上 Stirling formula 計算狀態量
其實，馬上就可以發現消息理論第一定律與熱力學之間的直接關聯
（這一點，也可以說明為何消息理論的 entropy 要定義為 -p log p
  一般人剛開始學消息理論時，對於 entropy 為何如此定義很難理解其緣由）

消息理論比較重要的突破其實是在第二定律與第三定律

第二定律給出一個帶雜訊的通道，它的資訊承載量的上限為何 (Shannon limit)
這一點，在通訊領域有極為廣泛應用
在 1940 年代第二定律出爐後，這幾十年間
通訊上所使用的 encoding/decoding algorithm，雖然有時會有突破性的進展
（例如魏立芳 -- 一位 NTUEE 的學長，他發明的 Trellis code
  比傳統演算法好至少 3dB 以上，這個突破性的發展
  使 Trellis code 廣泛應用於 14400bps up modem
  此一事蹟也讓他創下只發表六篇 paper 就拿到 IEEE fellow 的記錄
  這裡頭還有一段學術界抄襲論文的小插曲，不過暫時先打住）
但都離 Shannon limit 有一大段距離 (至少都差了 3dB 以上).......

直到 1993 年，幾位法國人發明了 Turbo code
這世界才有第一個真正如此接近 Shannon limit 的 encoding/decoding algorithm
(只相差約 0.7dB 而已)，更好玩的是這幾位法國人原本並不是搞 coding 出身的
由於 Turbo code 有專利，直到 1997 年
發明了 LDPC code，也很接近 Shannon limit

到今日為止，全世界就只有 Turbo code 與 LDPC code 能趨近於 Shannon limit
而且出爐到現在，也才十多年而已
而消息理論第二定律則是已經超過五十年的歷史

第三定律則是給定在一定的失真率下，一個類比資訊最少可以使用多少位元儲存
這一點，廣泛應用於壓縮演算法之中，尤其是影像壓縮與聲音壓縮

其實，消息理論第二定律與第三定律，算是與原本的統計力學分道揚鑣

: 和Newton或Einstein不一樣的是,
: 這個工作如果不是他的話,相信很快也會有別人做出來.
: 因為該有的物理理論都有了,而資訊科學也在那時蓬勃發展,
: 就像Einstein的狹義相對論一樣,其實Lorentz teansformation早就出來了,
: 他不過是站在一個承先啟後的位置,看出其中的物理意義,
: 就算他沒做出來,也很快地會被別人做出來的.

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.139.221.119
推 reader:大推 高手就是不一樣 能夠提供深入淺出的說明 :)
→ lovewa:LDPC Code是在61年提出，後來在96年被重新拿出來討論～
→ lovewa:但是Wei真的很厲害～那時候上課的時候老師還一直提到他這個
→ lovewa:學長，很快就拿到Fellow了....
噓 losfer:Shannon entropy is not from Stirling formula,not at all
噓 losfer:He used axiomatic and funcational analysis approaches.