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

看板CSSE (電腦科學及軟體工程)作者mgtsai (鐵軌不是我偷的)時間18年前 (2006/05/25 10:36)推噓-1(1推 2噓 3→)

留言6則, 3人參與討論串19/20 (看更多)

※ 引述《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