信息論-第五章

2024/8/131第五章：信道編碼定理§5.1離散信道編碼問題§5.2~3離散信道編碼定理2024/8/132§5.1離散信道編碼問題最簡單的檢錯和糾錯單個的字無法檢錯：捫→？詞匯能夠檢錯：我捫的→我捫的詞匯能夠糾錯：我捫的→我們的，我等的，我輩的，我班的，…原因分析：“捫→？”可以有幾萬個答案，但“我捫的→？”的答案卻很少。結(jié)論：課文以及詞匯的概率分布的稀疏性可以用來檢錯和糾錯。2024/8/133§5.1離散信道編碼問題設(shè)信道是一個D元字母輸入/D元字母輸出的DMC信道，字母表為{0,1,…,D-1}。其信道轉(zhuǎn)移概率矩陣為D×D矩陣如下。這是一個對稱信道。信道傳輸錯誤的概率定義為P(輸出不等于k|輸入為k)=p，k∈{0,1,…,D-1}。此處p<(1-p)。2024/8/134§5.1離散信道編碼問題設(shè)信源消息序列經(jīng)過D元信源編碼（等長編碼或不等長編碼）后變成了如下的隨機變量序列…X-2X-1X0X1X2…，其中每個隨機變量Xl的事件全體都是D元字母表{0,1,…,D-1}。將此隨機變量序列切割成L維隨機向量準備輸入信道：(X1X2…XL),(XL+1XL+2…X2L),…。2024/8/135§5.1離散信道編碼問題如果直接將(X1X2…XL)輸入信道，信道的輸出為(X1’X2’…XL’)，則①當信道傳輸錯誤時無法檢測到（即接收方無法確知是否正確接收）。②正確接收的概率為P((X1’X2’…XL’)=(X1X2…XL))=P(X1’=X1)P(X2’=X2)…P(XL’=XL)=(1-p)L。2024/8/136§5.1離散信道編碼問題將(X1X2…XL)進行變換：C(X1X2…XL)=(U1U2…UN)，其中(U1U2…UN)為N維隨機向量，N≥L，且變換是單射（即(X1X2…XL)的不同事件映射到(U1U2…UN)的不同事件）。將(U1U2…UN)輸入信道；信道的輸出為(Y1Y2…YN)；再根據(jù)(Y1Y2…YN)的值猜測出輸入信道的值(U1’U2’…UN’)，并根據(jù)變換式(U1’U2’…UN’)=C(X1’X2’…XL’)將(U1’U2’…UN’)反變換為(X1’X2’…XL’)。如果(X1’X2’…XL’)=(X1X2…XL)，則正確接收。2024/8/137§5.1離散信道編碼問題（1）(X1X2…XL)的事件共有DL個，因此(U1U2…UN)的事件共有DL個，占N維向量值的份額為DL/DN=1/DN-L。因此當信道傳輸錯誤時，有可能使輸出值(Y1Y2…YN)不在這1/DN-L份額之內(nèi)。這就是說，信道傳輸錯誤有可能被檢測到。（2）如果精心地設(shè)計變換C(X1X2…XL)=(U1U2…UN)和猜測規(guī)則(Y1Y2…YN)→(U1’U2’…UN’)，則正確接收的概率遠遠大于(1-p)L。2024/8/138§5.1離散信道編碼問題（3）變換(X1X2…XL)→(U1U2…UN)=C(X1X2…XL)稱為信道編碼，又稱為(N,L)碼。一個事件的變換值稱為該事件的碼字。L稱為信息長，N稱為碼長。（4）過程(Y1Y2…YN)→(U1’U2’…UN’)→(X1’X2’…XL’)稱為糾錯譯碼。當(X1’X2’…XL’)=(X1X2…XL)時稱為正確譯碼（實際上就是正確接收）。2024/8/139§5.1離散信道編碼問題（5）N比L大得越多，1/DN-L份額越小，碼字的分布越稀疏，信道傳輸錯誤不在這1/DN-L份額之內(nèi)的可能性越大，即信道傳輸錯誤越容易被檢測到。但N比L大得越多，信道傳輸?shù)睦速M越大。（6）稱R=L/N為編碼速率，也稱為信息率。（似乎與信源編碼相互倒置？）（7）注解：“(X1X2…XL)不進行編碼”實際上也是一種編碼，稱為恒等編碼。此時N=L，事件x=(x1x2…xL)的碼字就是x自身。2024/8/1310§5.1離散信道編碼問題關(guān)于譯碼準則譯碼準則就是猜測規(guī)則。當信道的輸出值為y時，將其譯為哪個碼字u最合理？最大后驗概率準則簡記b(u|y)=P((U1U2…UN)=u|(Y1Y2…YN)=y)。稱b(u|y)為后驗概率。最大后驗概率準則：2024/8/1311§5.1離散信道編碼問題后驗概率的計算：記q(u)=P((U1U2…UN)=u)，稱q(u)為先驗概率；pN(y|u)=P((Y1Y2…YN)=y|(U1U2…UN)=u)，我們知道p(y|u)是信道響應(yīng)特性，而且pN(y|u)=P(Y1=y1|U1=u1)P(Y2=y2|U2=u2)…P(YN=yN|UN=uN)=(p/(D-1))d(1-p)N-d，其中d是(y1y2…yN)與(u1u2…uN)對應(yīng)位置值不相同的位數(shù)；（以后將稱d為Hamming距離）2024/8/1312§5.1離散信道編碼問題記w(y)=P((Y1Y2…YN)=y)。我們知道2024/8/1313§5.1離散信道編碼問題最大似然概率準則(看成轉(zhuǎn)移概率矩陣中的第y列向量中的最大分量)2024/8/1314最小距離準則（最小錯誤準則）y與u的Hamming距離定義為(y1y2…yN)與(u1u2…uN)對應(yīng)位置值不相同的位數(shù)，記為d(y,u)。2024/8/1315§5.1離散信道編碼問題命題最大似然概率準則等價于最小距離準則。證明pN(y|u)=P(Y1=y1|U1=u1)P(Y2=y2|U2=u2)…P(YN=yN|UN=uN)=(p/(D-1))d(1-p)N-d，其中d是y與u的Hamming距離。注意到p/(D-1)<(1-p)。所以pN(y|u)達到最大，當且僅當y與u的Hamming距離達到最小。得證。2024/8/1316§5.1離散信道編碼問題命題如果每個碼字是等概出現(xiàn)的，則最大后驗概率準則等價于最大似然概率準則。證明2024/8/1317§5.1離散信道編碼問題對兩種譯碼準則的評述最大后驗概率準則具有很好的直觀合理性。收到y(tǒng)的條件下，最可能發(fā)送的是哪個碼字，就認為發(fā)送的是哪個碼字”。最大似然概率準則（最小距離準則）所具有的直觀合理性弱一些。發(fā)送哪個碼字的條件下，最可能收到y(tǒng)，就認為發(fā)送的是哪個碼字。最大似然概率準則（最小距離準則）的實現(xiàn)比最大后驗概率準則的實現(xiàn)更簡單：前者只需要看哪個碼字與y的Hamming距離最??；后者需要知道各碼字的概率分布，然后用貝葉斯公式計算并比較后驗概率。兩種準則都可以用在沒有編碼（直接發(fā)送）情況下的糾錯譯碼。2024/8/1318§5.1離散信道編碼問題例5.1.1BSC信道的轉(zhuǎn)移概率矩陣為取L=1。如果直接將X1輸入信道，信道的輸出為X1’，則①當信道傳輸錯誤時無法檢測到。②正確接收的概率為P(X1’=X1)=1-p。今取L=1，N=4，二元(4,1)碼如下：0→0000，1→1111。2024/8/1319§5.1離散信道編碼問題譯碼規(guī)則如下：當(Y1Y2Y3Y4)中1的個數(shù)為3或4時，(Y1Y2Y3Y4)→(1111)→1；當(Y1Y2Y3Y4)中1的個數(shù)為0或1時，(Y1Y2Y3Y4)→(0000)→0；當(Y1Y2Y3Y4)中1的個數(shù)為2時，(0011)、(1100)、(1001)→(0000)→0，(0101)、(1010)、(0110)→(1111)→1。譯碼規(guī)則顯然是最小距離準則。

2024/8/1320§5.1離散信道編碼問題何時檢測到信道傳輸錯誤？當(Y1Y2Y3Y4)不是一個碼字時，檢測到信道傳輸錯誤。換句話說，(Y1Y2Y3Y4)與原發(fā)碼字(U1U2U3U4)的Hamming距離≥1且≤3時，檢測到信道傳輸錯誤。因此，信道傳輸有錯誤但能檢測出錯誤的概率為2024/8/1321§5.1離散信道編碼問題何時正確譯碼（正確接收）？當(Y1Y2Y3Y4)與原發(fā)碼字(U1U2U3U4)的Hamming距離≤1時，正確譯碼；當(Y1Y2Y3Y4)與原發(fā)碼字(U1U2U3U4)的Hamming距離=2時，一半能正確譯碼，另一半不能正確譯碼；當(Y1Y2Y3Y4)與原發(fā)碼字(U1U2U3U4)的Hamming距離≥3時，不能正確譯碼。正確譯碼（正確接收）的概率為2024/8/1322§5.1離散信道編碼問題2024/8/1323§5.2~3離散信道編碼定理首先需要說明，上述離散信道編碼的編碼速率（信息率R）本來是設(shè)備所確定的。當信源每秒產(chǎn)生ns個字母，信道編碼所使用的設(shè)備每秒產(chǎn)生nc個字母，則設(shè)備所確定的編碼速率就是R

=ns/nc。其次，實際編碼速率（實際信息率L/N）必須不小于設(shè)備所確定的編碼速率：L/N≥R。于是對離散信道編碼有了以下兩條相互矛盾的要求：（1）實際編碼速率L/N盡可能小以便使正確譯碼（正確接收）的概率盡可能接近1。（2）實際編碼速率不小于設(shè)備所確定的編碼速率L/N≥R。2024/8/1324§5.2~3離散信道編碼定理設(shè)信源序列經(jīng)過信源編碼后變成了如下的序列…X-2X-1X0X1X2…。設(shè)各隨機變量獨立同分布。記H(X)為X0的熵，C為信道容量。如果設(shè)備所確定的編碼速率R<C/H(X)，則能夠同時滿足以下兩條要求：（1）L/N使正確譯碼（正確接收）的概率盡可能接近1。（2）L/N≥R。如果設(shè)備所確定的編碼速率R>C/H(X)，則不能夠同時滿足這兩條要求。（如果設(shè)備