我決定要把兩個一直放在心中想看..可是又一直沒看的topic看過
第一個也是比較簡單的一個..就是Shannon的information theory
我看的版本是University of Illinois Press出的
前面是Weaver先解釋一下什麼是communication..以及一些基本的概念
後面則是當初Shannon在Bell Lab的論文
自己雖然常把entropy coding放在嘴上
但對於其理論細節和定義的不了解..一直感到不太舒服
看完整本後的感想跟看完Von Neumann的Game Theory很像
很精采也能對一些現象給出數學的描述..對於1948年那個時代建立通訊系統概念有重大的貢獻
但對於實際應用幫助似乎有限
(為了弄懂這兩本書的證明也都花了不少時間)
裡面的理論幾乎都建立在ergodic process上
但實際上我遇到的問題要嘛就連stationary process都不是..不用說是ergodic
要嘛就是finite data set
所以這裡的理論只能拿來參考用
但說實在的..光是了解Shannon的巧思就值回票價了
最一開始Weaver就強調..這裡的communication指的是工程技術面的
也就是給定symbol組合去找出最好的編碼和傳送方式
這裡定義的資訊量單指symbol的傳送量
對於傳送內容(symbol代表的意義)是不管的 (ex. 全世界網頁的資訊量大爆炸..但有意義的倒不多)
Shannon的論文本身部份..我覺得主要分為三個部份
第一是定義discrete signal的資訊量
第二是在有noise底下..discrete signal的資訊量
第三則是考慮continuous signal的資訊量
關於discrete signal的資訊量..在給定有限個symbol以及其機率後
Shannon只用了三個簡單的假設就可以證明出
該資訊量或稱為entropy必定表示為常見的entropy H = -sum Pi logPi
另外對於資訊傳送的channel..也定義出其capacity (這裡只考慮無失真狀況)
一個channel的定義來自於有幾種symbol以及每個symbol傳送需要的時間ti
capacity即為在長時間的平均下..能傳送的資訊量的上限 (這裡開始有了ergodic process的假設)
假設N(T)為時間T內能傳送的可能symbol sequence個數
則 N(T) = N(T-t1) + N(T-t2) + .. + N(T-tn)
[每一項對應的是若最後一個symbol為i..再之前的symbol sequence數]
該證明用了有趣的finite difference的結果..也就是用matrix的eigenvalue找出N(T)在T很大時的趨近式
而Capcity C = lim log(N(T))/T 就可以得出 C = 最大的eigenvalue
(我另外用別的方法也得到了一樣的證明結果..以及該極限下的條件)
有了 source entropy H和channel capacity C後..就能計算出最大的資訊傳送速率為 C/H
我覺得這裡應該就是此論文最經典的地方
從這些結果可以推論出許多有趣的結果
例如 H(x,y) <= H(x) + (y) 用數學描述了一次考慮多一點symbol會比分開的好 (entropy小)
反過來看就是..如果想一次只考慮一個symbol..那他們最好是independent
又如 -sum Pi logQi >= -sum Pi logPi 代表了編碼的最佳方式就是用-logPi..別的都只會更糟
第二部份考慮了channel會有失真的結果
該失真依然用機率來表示..Py(x)代表收到y而原始訊號為x之機率
則該transmission rate R = H(x) - Hy(x)
Hy(x)稱為equivocation..也就是資訊少掉的部份
而channel capacity C則為transmission rate的最大值
(p.s. 給定Py(x)下..尋找P(x)可以讓R最大化)
這裡有一些有趣的關係式
H(x,y) = H(x) + Hx(y) = H(y) + Hy(x)
=> R = H(x) - Hy(x) = H(y) - Hx(y)
這裡的最終定理是..給定information source (z) entropy H..以及channel capacity C
若H <= C..則可以找到編碼方法(z->x)..使得transmisson error趨近於零
反之若H>C..則頂多只能做到equivocation >= H - C
白話一點的講 (或許不那麼準確)..就是如果你有一個source (z) entropy H
則有辦法找到一個編碼方法將z編碼成x..其傳送錯誤率趨於零
x之entropy即為H(x)..H(x)會約等於H + Hy(x) [Hy(x)在這裡即為redundancy]
所以最後收到的資訊量為 H + Hy(x) - Hy(x) = H !
(用redundancy去補足因為失真少掉的資訊..這也是錯誤更正碼的本意)
這裡我自己試著用Hamming code當例子
Hamming code編碼後一個block有 2^m-1 bits (x)
若每一個transmitted block在接送後都有2^m種可能 (在2^m-1不同位置錯一個bit + 沒有錯)
於是這channel最大的equivocation即為不同可能之機率都相同的時候 (機率都一樣時entropy最大)
若y為接收後的結果..則 Hx(y) = 2^m/2^m * log 1/2^m = m
而 C = max (H(y) - Hx(y)) = max(H(y)) - m = 2^m - 1 - m
這結果和Hamming code的data bits為2^m-m-1一模一樣!!
所以可以說Hamming code在更正1-bit這件事上達到了Shannon limit
第三部份講的是continuous signal的資訊量
這裡牽涉的數學更難..而且能得到的結論其實也較少
大致上的概念為..完全複製continous signal所需的資訊量為無限大 (因為資訊量是定義在discrete signal上)
所以講到continous signal之資訊量必定跟隨著能容許的誤差範圍 (和一般量化的問題類似)
首先是定義continous signal的信號源為ensemble
即某函數之參數帶有機率分布..ex. sin(t+theta), theta在0~2pi間平均分布
接著由sampling theorem我們知道對於一個頻寬為W的continous信號
可用取樣頻率為2W之discrete-time信號來完全代表
若該信號的時間長度為T..則只要取樣n=2WT個點就可以代表該信號
所以一個頻寬為W長度為T的ensemble可以用2WT個random variable來代表
這裡的random variable的值為continous而非先前的discrete value
所以機率也變成了機率密度函數
entropy的定義和先前的類似..只是將summation換成integral..機率換成機率密度函數
continuous entropy麻煩的地方就在於常要用Calculus of Variation (變分法)來計算
經過計算可以推得一些有趣的性質
例如若機率密度只分布在有限範圍內..則entropy最大值發生在flat probability function (和discrete很像)
若限制variance為某固定值..則entropy最大值發生在Gaussian distribution
(這個性質感覺幾乎是continuous entropy的核心)
然而continuous entropy有些地方和discrete entropy很不同
首先它可能是負的..再來是它的值和所採用的座標變數有關
考慮兩組座標變數 x=(x1,..,xn) and y=(y1,..,yn)
則相對應的體積內的機率應該是一樣的..所以P(y)*dy = P(x)*dx
於是得到 P(y) = P(x) * J(x/y), J(x/y)為determinant of Jacobian matrix
所以 H(y) = -S P(y) logP(y) dy = - S P(x)*J(x/y)*log(P(x)J(x/y))*dx*J(y/x)
= - S P(x)*(logP(x)+logJ(x/y))*dx = H(x) - S P(x)*logJ(x/y)*dx
H(y)和H(x)差了後面由Jacobian造成的差別
不過幸好對於continous entropy來說..有意義的rate和capacity都是定義在entropy的difference上
所以剛好把Jacobian或是可能為負的效應扺消..所以rate和capacity都還是正的而且與座標無關
解決一些數學性質後..終於進入正題
首先定義ensemble的entropy per freedom
H' = - lim n->inf. {1/n* SS..S P(x1,..,xn) logP(x1,..xn)dx1..dxn}
因為n=2WT..所以另一個較好懂的定義為
entropy per second = - lim T->inf. {1/T* SS..S P(x1,..,xn) logP(x1,..xn)dx1..dxn}
= n*H'/T = 2WH'
於是對於Gaussian noise..其H = W log(2*pi*e*N) (bit/sec) where N is variance
若把continous entropy想成切為很細的discrete entropy..會發現結果是一致
也就是continous entropy也是可用於產生discrete entropy的
不過當然只是理論上可以..實際上切成無限細是不可能
但continous entropy代表了實際能傳送的資訊量的上限
或許因為Gaussian noise太好用的關係
Shannon定義了entropy power N1 = 1/(2*pi*e)*exp(H/W)
若該source為Gaussian的話..則N1便為其average power (variance)
但因為同average power的source中..Gaussian的entropy最大
所以任何source之average power都會比entropy power大
在有失真的channel下..transmission rate一樣被定義為
R = H(x) - Hy(x) = SS P(x,y)log(P(x,y)/P(x)/P(y)) dxdy
則channel capacity = lim T->inf. {R/T} (bit/sec)
(給定Py(x)後..找出能最大化R之P(x))
接下來是一個很重要的特例..也就是失真為independent gaussian noise
假設transmission signal x has average power P, noise has power N
則received signal y will have average power P+N
C = max (H(y) - H(n)) = max H(y) - H(n) [y's power is given so y is gaussian to maximize R]
= Wlog(2*pi*e*(P+N)) - Wlog(2*pi*e*N)
= W log(P+N)/N (bit/s)
這個式子幾乎成為了通訊系統的golden rule!
對於general noise (N is average power, N1 is entropy power)
C可以得到以下的不等式
Wlog(P+N1)/N1 <= C <= Wlog(P+N)/N
本書最後的一個推論..是通訊系統很常遇到的問題
也就是如何在失真一樣的情況下..用最小的資訊量傳送信號
這裡的問題定義為..給定信號x以及其P(x)..將信號x轉換為y的行為用P(x,y)來表示
給定量測失真之函式rho(x,y)下..總失真可定義為 v = SS P(x,y)rho(x,y)dxdy
於是在給定總失真之限制下..找出最佳的P(x,y)來最小化rate R= SS P(x,y)log(P(x,y)/P(x)/P(y)) dxdy
在將Lagrange multipier引進對P(x,y)的first variation中
最後會得到 Py(x) = B(x)*exp(-lambda*rho(x,y))
這結果看起來不是很有用
但若假設失真只會x和y的差有關..即rho(x,y)=rho(x-y)
則可進一步得到B(x)為常數..即 Py(x) = A*exp(-lambda*rho(x-y))
所以若失真是用square error即(x-y)^2來計算的話..則Py(x)為Gaussion為最佳解!!
於是若source為Gaussian且average power = P..則R = WlogP/N
對於general source來說..可得到以下之不等式
WlogP1/N <= R <= WlogP/N
以上是屬於non-constructive deduction
這也讓無數的工程師想破頭要找出方法去滿足以上的Shannon limit!
唯一可惜的是Shannon在這裡對於quantization的問題並沒有討論到
似乎是在之後才再發表的
不過以上已經將information theory的大門打開了
在60幾年後的現在..我才進入了這扇門
留言列表
