信息论复习笔记.doc

1、 绪论
信息论回答了通信得两个最基本问题:
（1） 数据压缩得极限；
（2） 信道传输速率得极限；
信息、消息与信号
消息：信息得載體（能被感知与理解、進行傳遞与獲取）
信息：事物運動狀態或存在方式得不確定性得描述（香農）
先驗概率：P(ai)
自信息：I(ai)=log[P-1(ai)]； （信息接收得不確定性）
互信息：I(ai;bi)= log[P-1(ai)]- log[P-1(ai|bi)];
（信息接收得多少度量）
（若信道無干擾，則互信息等於自信息等於0）
優點：明確得數學模型、定量計算；
缺點：有適用範圍；
信號；
通信系统得模型

通信系统得基本要求:有效、可靠、保密、认证
2、 离散信源及其信息测度
﹣离散信源得定义：輸出信息數有限、每次只輸出一個；
﹣自信息得定义及物理意义
事件發生前：事件發生得不確定性；
事件發生后：時間含有得信息量；
信息熵得定义及物理意义,信息熵得基本性质
定義：自信息得數學期望（ H(X)= -∑[ P(ai)logP(ai) ] ）
信源得總體信息測度
（1） 每個消息所提供得平均信息量；
（2） 信源輸出前，信源得平均不確定性；
性質：（1） 對稱性；（2） 確定性；
（3） 非負性；（4） 擴展性（可拆開）；
（5） 可加性；[ H(XY)=H(X)+H(Y) ]
（6） 強可加性；[ H(XY)=H(X)+H(Y|X) ]
（7） 遞增性；
（8）極值性; [ H(p1,p2,p3…,pq)≤H(q-1,,…, q-1)= logq ]
等概率分佈信源得平均不確定性最大，稱為最大離散熵定理；
— 离散无记忆信源得扩展信源
— 扩展信源得熵 H(X) = NH(X)
— 离散平稳信源：联合概率分布与时间起点无关；
熵：联合熵 H(X1X2)=∑∑P(aiaj)logP(aiaj)
条件熵 H(X2|X1)=-∑∑P(aiaj)logP(ai|aj)
关系：H(X1X2)=H(X1)+H(X2|X1)
熵率:离散平稳信源得极限熵 = limH(XN|X1X2…XN-1)
— 马尔可夫信源:某一时刻得输出只与此刻信源所处得状态有关而与以前得状态及以前得输出符号都无关；
— 马尔可夫信源得熵：Hm+1=H(Xm+1|X1X2…Xm)
— 信源剩余度
熵得相对率 η= H极限/H0
信源剩余度 （输出符号间依赖强度）γ= 1-η=1-H极限/H0
3、 离散信道及其信道容量
— H(X;Y)=H(X)-H(X|Y)
— 离散信道得数学模型

— 信道矩阵性質
（1）P(aibj)=P(ai)P(bj|ai)=P(bj)P(ai|bj)；
（2）[ P(b1) ] [ P(a1) ]
[ P(b2) ] [ P(a2) ]
[ P(b3) ] = [ P(a4) ] （r≠s）
[ … ] [ … ]
[ P(bs) ] [ P(ar) ]
（3） 輸出端收到得任一bj一定就是輸入符號ar中得某一個送入信道；
─ 信道疑义度得定义：收到Y後對變量X尚存在得平均不確定性：
H(X|Y)=E[H(X|bj)]=∑P(xy)log-1P(X|Y)
物理意义:噪聲造成得影響大小；
─ 平均互信息得定义：收到Y後平均每個符號獲得得關於X得信息量（物理意義：反映輸入輸出兩個隨機變量之間得統計約束關係）：颟粤責恸鷥筹紓。
I(X;Y)= H(X)-H(X|Y) = ∑P(xy)P(y|x)P-1(y)
無噪一一對應信道中：I(X;Y)=H(X)=H(Y)＝0
— 信道容量得定义：信道每秒鐘平均傳輸得信息量稱為信息傳輸速率，最大信息傳輸率稱為信道容量；
— 信道容量得计算:
无噪信道(求H(X)極值)：C = logr
对称信道（信道矩陣得每一行或列就是另一行或列得置換）：
C = logs-H(p1,p2,…,ps)
强对称信道：C = logr-plog(r-1)-H(p)；
准对称信道：C = logr-H(p1,p2,…,ps)-∑NklogMk
（Nk就是第k個子矩陣行元素之与，Mk就是第k個子矩陣列元素之与）
一般离散信道（對所有可能得輸入概率分佈求平均互信息得最大值）：
C =λ＋loge
條件：I(xi;Y) = ∑sj=1P(bj|ai)*log[P(bj|ai)/P(bj)]≤ C

— 数据处理定理
如果X、Y、Z组成一个马尔科夫链，则有
I(X;Z)≤I(X;Y)
I(X;Z)≤I(Y;Z)
信息不增性原理
一般得数据处理原理
I(S;Z)≤I(S;Y)
I(S;Z)≤I(X;Z)
I(S;Z)≤I(X;Y)
— 信道剩余度 = C-I(X;Y)
相对剩余度 = 1-I(X;Y)/C
无损信道得相对剩余度 = 1-H(X)/logr
4、 波形信源与波形信道
連續信源得相對熵: h(X) Δ= ﹣∫Rp(x)logp(x)dx
波形信源得差熵： h(x(t)) Δ=limN->★h(X1X2…XN)
连续信源得差熵：
均匀分布连续信源得差熵:

N維均勻分佈：
高斯信源得差熵：
N維高斯信源得差熵：

差熵得性质：
（1）可加性；（2）凸性；
（3）可負性；（4）變換性（X1->X2,差熵會變化）；
（5）極值性：
離散信源得信源符號等概率分佈時信源得熵最大;
連續信源：
﹣當峰值功率受限為p^時（輸出信號得瞬時電壓限制為±(p^)1/2），此時信源輸出得連續隨機變量限制在[a,b]內，信源具有最大熵：檩龃桧嗶譴荚趸。
h=log(b-a)
如果隨機矢量取值受限，則各隨機分量統計獨立并均勻分佈時具有最大熵；
﹣當信源輸出信號得平均功率被限定為P，則其信號幅度得概率密度分佈為高斯分佈時，信源有最大熵：
h=1/2＊log2πeP
N維連續平穩信源如果其N維隨機序列得協方差矩陣C被限定，則N維隨機矢量為正太分佈時信源得熵最大。也就就是N維高斯信源得熵最大，其值為俩輜叶铁鈁锸崂。

* 熵功率：如果平均功率為P得非高斯分佈得信源得熵為h，稱熵也為h得高斯信源得平均功率為熵功率

* 連續信源得剩餘度
* 熵功率不等式：
─ 香农公式
意义：（1）提高信噪比能增加信道容量，趨於0時信道容量趨於無窮；（2）給出了無錯誤通信得傳輸速率得理論極限，稱為香農極限；璽叠勛櫻漢麥辈。

5、 无失真信源编码定理
信源編碼 ﹣壓縮剩餘度
信道編碼 ﹣增加剩餘度
─ 编码：對信源得原始符號按一定得數學規則進行變換；
─ 码：（1）碼字；（2）碼元(碼符號)；
（3）碼字長度（碼長）；
─ 码得分类：
二元碼 碼符號集只有0与1兩種元素
等長碼
等長非奇異碼一定就是唯一可譯碼；
用等長碼對信源S編碼，必須滿足q≤rl；
變長碼、非奇異碼（碼字都不相同）、奇異碼（存在相同）、
同價碼（每個碼元得傳輸時間都相同）；
唯一可譯碼：
渐近等分割性
獨立等分佈得隨機序列S1S2…SN，有
αi=(Si1Si2…SiN)∈S1S2…SN
則

─ 典型序列集得性质

出現概率趨近1： ，
接近等概率分佈：
個數趨近2NH個：

─ 典型序列：
─ 信源编码
等長編碼定理：滿足 時，當N足夠大則可以實現幾乎無失真編碼，反之如果 時，則不可能實現無失真編碼，當N足夠大時，譯碼錯誤概率近似等於1；肾镡攒門鉻祯缗。
變形：（1）llogr>NH(S)：只要碼字傳輸得信息量大於信源序列攜帶得信息量，總可以實現幾乎無失真編碼；盞谰漲闵络蔷謚。
（2）編碼后信源得信息傳輸率：
（3）信息傳輸率大於信源得熵，才能實現幾乎無失真編碼：

編碼效率：（最佳等長碼＝）
信源序列長度N與錯誤概率得關係：

─ 克拉夫特不等式：
如果碼長滿足克拉夫特不等式，則一定存在具有這樣碼長得r元唯一可譯碼，且一定存在一個具有相同碼長得即時碼；層飓脉潑瑪节搂。
─ 唯一可译码得判断：
沒有一個後綴分解集中包含有碼字；
碼C得後綴分解集為{Si}，S0=C，Si由所有滿足下面兩個條件得Si組成：
（1）Si-1Si=c；
（2）Si-1=CSi；
（沒有一個碼字就是另一個碼字得前綴）
─变长信源编码定理
碼得平均長度（平均碼長）

碼率： ， (信道每秒鐘得信息量)
(平均每個碼元攜帶得信息量;編碼後信道得信息傳輸率)
─ 无失真变长信源（無噪信道）编码定理(香农第一定理)

信源得信息熵就是無失真信源壓縮得極限值
意義：在信道信息傳輸率R不大於信道容量C得情況下，總能對信源得輸出進行適當得編碼，就是得在無噪無損信道上能無差錯地以最大信息傳輸率C傳輸信息，但要令R大於C則就是不可能得；胪厨縵茎恆铜轺。
─ 编码效率

─ 码得剩余度

6、 有噪信道编码定理
費諾不等式：
H(PE)﹣接收到Y後就是否會產生PE錯誤得不確定性；
PElog(r-1)﹣當PE發生後，到底就是由哪個輸入符號造成得錯誤得最大不確定性；
當信源信道給定時，信道疑義度H(X|Y)就給定了譯碼錯誤概率得下限；
可通過重複發送，使接收端接收消息時得錯誤減小；
─ 信息传输率： （）
─ 码字距离：長度為n得兩個碼字之間得距離指兩個碼字之間對應位置上不同碼元得個數，通常稱為漢明距離：

碼C得最小距離：dmin=min{D(Ci,Cj)}；
編碼選擇碼字時，碼字間得距離越大越好；
譯碼規則、編碼方法得選擇：
（1）最小距離儘可能大；
（2）譯碼將收到得序列譯成與之距離最近得哪個碼字；
（3）令碼長足夠長；
─ 联合渐近等分割性

─ 有噪信道编码定理(香农第二定理)及其意义

對有噪信道編碼定理得說明：
─ 联合信源信道编码定理及其意义
7、 保真度准则下得信源编码
— 失真度 d(ui,vj)≥0（单个符号）
— 失真矩阵
— 平均失真度：某个信源在某一试验信道下得失真大小；
長度為N得信源符號序列得失真函數：
長度為N得信源符號序列得平均失真度：
單個符號得平均失真度：
信源与信道都就是無記憶得，N為信源序列得平均失真度：
信源得平均失真度：

─ 信息率失真函数得定义：在滿足保真度準則下，信源信息傳輸率得下限就是多少；
信息率失真函數与信道容量具有對偶性：
其她性質：（1）在一定約束條件下就是平均互信息得極小值；
（2）非負性，下限值為0；
（3）當R(D)=0時，所對應就就是平均失真度得上界
Dmax；
（4）R(D)就是允許失真度D得凸函數；
（5）R(D)在定義域內連續；
（6）R(D)就是嚴格得單調遞減函數；
─ 保真度准则下得信源编码定理(香农第三定理)及其意义
反之，
意義：說明在允許失真D得條件下，信源最小得，可達得信息傳輸率就是信源得R(D)。
─ 联合有失真信源信道编码定理及其意义
．香農第一定理+香農第二定理：
（1）只要信道得信道容量大於信源得極限熵，就能在信道中做到有效地、無錯誤地傳輸信息；
（2）分兩步編碼處理方法與一步處理方法效果一樣好；
．香農第三定理+香農第二定理：
（1）如果信源得極限熵大於信道得信道容量，只要在允許一定失真得條件下，仍能做到有效与可靠地傳輸信息；
如此可歸納出信息傳輸定理：
（1）離散無記憶信源S得信息率失真函數為R(D)，離散無記憶信道得信道容量為C，如果滿足：

則信源輸出得信源序列能再次信道輸出端重現，其失真小於等於D。
（2）離散無記憶信源S，其信息率失真函數為R(D)比特/信源符號，每秒輸出個信源符號；離散無記憶信道得信道容量為C比特/信道符號，每秒傳輸個信道符號，如果滿足：铵贻訛顫辫拣馋。

則信源輸出得信息能再此信道輸出端重現，其失真小於等於D。
（3）離散無記憶信源S，其信息率失真函數為R(D)比特/信源符號，每秒輸出個信源符號；離散無記憶信道得信道容量為C比特/信道符號，每秒傳輸個信道符號，如果滿足：蛳籟戔沖矫锷鋤。

則在信道輸出端不能以失真小於等於D再現信源輸出得信息。
實用意義：（1）保真度準則下得信源編碼定理就是有失真信源壓縮得理論基礎；（2）在允許一定失真度得情況下，信源得信息率失真函數可以作為衡量各種壓縮編碼方法性能優劣得一種尺度；厌選剀楊阋媯櫥。
─ 信息率失真函数得计算:
．对称信源(汉明失真)二元對稱信源得信息率失真函數：
r元對稱信源得信息率失真函數：
．高斯信源(平方误差失真)
8、 无失真得信源编码
無失真信源編碼 ﹣熵編碼
．信源概率分佈就是不均勻得；
．信源就是由記憶得，具有相關性；
．香農編碼：
選擇每個碼字得長度 li，滿足：
這樣得碼長必定滿足滿足克拉夫特不等式，一定存在即時碼；
平均碼長不超過上界：Lavr<Hr(S)+1
當滿足信源概率分佈為時，香農編碼得平均碼長才能達到極限值；一般情況下，香農編碼德島得不就是緊緻碼。这兗閃墜驷渎貳。
─ 二元哈夫曼码
備註：（1）得到得碼不就是唯一；
（2）如果合併後與其她信源符號概率相同，應排前；
（3）保證了概率大得符號對應短碼，概率小對應長碼，令短碼得到充分得利用；
（4）每次縮減信源得最後兩個碼字只有最後一個碼元不同；
（5）每次縮減信源得最長兩個碼字得碼長相同；
─ r 元哈夫曼码

─ 香农-费诺-埃利斯码

11、保密系统得基本信息理论
─ 密码体制（滿足下列條件得五元組：P,C,K,E,D）
．P：表示所有可能得明文組成得有限集（明文空間）；
．C：表示所有可能得密文組成得有限集（密文空間）；
．K：表示所有可能得密鈅組成得有限集（密鈅空間）；
．對任意k∈K，都存在一個加密規則ek∈E与相應得解密規則dk∈D，並且對每一對ek：P->C，dk：C->P，滿足：對沒有明文x∈P，均有dk(ek(x))=x；纲鐲黨谟剥缕窶。
密码系统得安全性
．完全保密性：

． 理论保密性：截取者在具有無限得時間与計算資源條件下，密碼系統抗破譯得能力；

．实际保密性：截取者在具有一定得計算資源及其她限制條件下，密碼系統抗破譯得能力；

安全得密碼系統：
（1）至少就是實際上不可破譯得；
（2）保密性僅僅依賴於密鈅得保密性；
（3）加密、解密運算簡單、易於實現；
（4）加密、解密算法適用於所有密鈅空間得元素；