信息論與編碼理論基礎(chǔ)第五章第一頁(yè)，共二十七頁(yè)，2022年，8月28日2023/3/131§5.1離散信道編碼問(wèn)題最簡(jiǎn)單的檢錯(cuò)和糾錯(cuò)單個(gè)的字無(wú)法檢錯(cuò)：捫→？詞匯能夠檢錯(cuò)：我捫的→我捫的詞匯能夠糾錯(cuò)：我捫的→我們的，我等的，我輩的，我班的，…原因分析：“捫→？”可以有幾萬(wàn)個(gè)答案，但“我捫的→？”的答案卻很少。結(jié)論：課文以及詞匯的概率分布的稀疏性可以用來(lái)檢錯(cuò)和糾錯(cuò)。第二頁(yè)，共二十七頁(yè)，2022年，8月28日2023/3/132§5.1離散信道編碼問(wèn)題設(shè)信道是一個(gè)D元字母輸入/D元字母輸出的DMC信道，字母表為{0,1,…,D-1}。其信道轉(zhuǎn)移概率矩陣為D×D矩陣如下。這是一個(gè)對(duì)稱信道。信道傳輸錯(cuò)誤的概率定義為P(輸出不等于k|輸入為k)=p，k∈{0,1,…,D-1}。此處p<(1-p)。第三頁(yè)，共二十七頁(yè)，2022年，8月28日2023/3/133§5.1離散信道編碼問(wèn)題設(shè)信源消息序列經(jīng)過(guò)D元信源編碼（等長(zhǎng)編碼或不等長(zhǎng)編碼）后變成了如下的隨機(jī)變量序列…X-2X-1X0X1X2…，其中每個(gè)隨機(jī)變量Xl的事件全體都是D元字母表{0,1,…,D-1}。將此隨機(jī)變量序列切割成L維隨機(jī)向量準(zhǔn)備輸入信道：(X1X2…XL),(XL+1XL+2…X2L),…。如果直接將(X1X2…XL)輸入信道，信道的輸出為(X1’X2’…XL’)，則①當(dāng)信道傳輸錯(cuò)誤時(shí)無(wú)法檢測(cè)到（即接收方無(wú)法確知是否正確接收）。②正確接收的概率為P((X1’X2’…XL’)=(X1X2…XL))=P(X1’=X1)P(X2’=X2)…P(XL’=XL)=(1-p)L。

第四頁(yè)，共二十七頁(yè)，2022年，8月28日2023/3/134§5.1離散信道編碼問(wèn)題將(X1X2…XL)進(jìn)行變換：C(X1X2…XL)=(U1U2…UN)，其中(U1U2…UN)為N維隨機(jī)向量，N≥L，且變換是單射（即(X1X2…XL)的不同事件映射到(U1U2…UN)的不同事件）。將(U1U2…UN)輸入信道；信道的輸出為(Y1Y2…YN)；再根據(jù)(Y1Y2…YN)的值猜測(cè)出輸入信道的值(U1’U2’…UN’)，并根據(jù)變換式(U1’U2’…UN’)=C(X1’X2’…XL’)將(U1’U2’…UN’)反變換為(X1’X2’…XL’)。如果(X1’X2’…XL’)=(X1X2…XL)，則正確接收。第五頁(yè)，共二十七頁(yè)，2022年，8月28日2023/3/135§5.1離散信道編碼問(wèn)題（1）(X1X2…XL)的事件共有DL個(gè)，因此(U1U2…UN)的事件共有DL個(gè)，占N維向量值的份額為DL/DN=1/DN-L。因此當(dāng)信道傳輸錯(cuò)誤時(shí)，有可能使輸出值(Y1Y2…YN)不在這1/DN-L份額之內(nèi)。這就是說(shuō)，信道傳輸錯(cuò)誤有可能被檢測(cè)到。（2）如果精心地設(shè)計(jì)變換C(X1X2…XL)=(U1U2…UN)和猜測(cè)規(guī)則(Y1Y2…YN)→(U1’U2’…UN’)，則正確接收的概率遠(yuǎn)遠(yuǎn)大于(1-p)L。（3）變換(X1X2…XL)→(U1U2…UN)=C(X1X2…XL)稱為信道編碼，又稱為(N,L)碼。一個(gè)事件的變換值稱為該事件的碼字。L稱為信息長(zhǎng)，N稱為碼長(zhǎng)。第六頁(yè)，共二十七頁(yè)，2022年，8月28日2023/3/136§5.1離散信道編碼問(wèn)題（4）過(guò)程(Y1Y2…YN)→(U1’U2’…UN’)→(X1’X2’…XL’)稱為糾錯(cuò)譯碼。當(dāng)(X1’X2’…XL’)=(X1X2…XL)時(shí)稱為正確譯碼（實(shí)際上就是正確接收）。（5）N比L大得越多，1/DN-L份額越小，碼字的分布越稀疏，信道傳輸錯(cuò)誤不在這1/DN-L份額之內(nèi)的可能性越大，即信道傳輸錯(cuò)誤越容易被檢測(cè)到。但N比L大得越多，信道傳輸?shù)睦速M(fèi)越大。（6）稱R=L/N為編碼速率，也稱為信息率。（似乎與信源編碼相互倒置？）（7）注解：“(X1X2…XL)不進(jìn)行編碼”實(shí)際上也是一種編碼，稱為恒等編碼。此時(shí)N=L，事件x=(x1x2…xL)的碼字就是x自身。第七頁(yè)，共二十七頁(yè)，2022年，8月28日2023/3/137§5.1離散信道編碼問(wèn)題關(guān)于譯碼準(zhǔn)則譯碼準(zhǔn)則就是猜測(cè)規(guī)則。當(dāng)信道的輸出值為y時(shí)，將其譯為哪個(gè)碼字u最合理？最大后驗(yàn)概率準(zhǔn)則簡(jiǎn)記b(u|y)=P((U1U2…UN)=u|(Y1Y2…YN)=y)。稱b(u|y)為后驗(yàn)概率。最大后驗(yàn)概率準(zhǔn)則：第八頁(yè)，共二十七頁(yè)，2022年，8月28日2023/3/138§5.1離散信道編碼問(wèn)題后驗(yàn)概率的計(jì)算：記q(u)=P((U1U2…UN)=u)，稱q(u)為先驗(yàn)概率；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)對(duì)應(yīng)位置值不相同的位數(shù)；（以后將稱d為Hamming距離）第九頁(yè)，共二十七頁(yè)，2022年，8月28日2023/3/139§5.1離散信道編碼問(wèn)題記w(y)=P((Y1Y2…YN)=y)。我們知道第十頁(yè)，共二十七頁(yè)，2022年，8月28日2023/3/1310§5.1離散信道編碼問(wèn)題最大似然概率準(zhǔn)則最小距離準(zhǔn)則（最小錯(cuò)誤準(zhǔn)則）y與u的Hamming距離定義為(y1y2…yN)與(u1u2…uN)對(duì)應(yīng)位置值不相同的位數(shù)，記為d(y,u)。第十一頁(yè)，共二十七頁(yè)，2022年，8月28日2023/3/1311§5.1離散信道編碼問(wèn)題命題最大似然概率準(zhǔn)則等價(jià)于最小距離準(zhǔn)則。證明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)達(dá)到最大，當(dāng)且僅當(dāng)y與u的Hamming距離達(dá)到最小。得證。第十二頁(yè)，共二十七頁(yè)，2022年，8月28日2023/3/1312§5.1離散信道編碼問(wèn)題命題如果每個(gè)碼字是等概出現(xiàn)的，則最大后驗(yàn)概率準(zhǔn)則等價(jià)于最大似然概率準(zhǔn)則。證明第十三頁(yè)，共二十七頁(yè)，2022年，8月28日2023/3/1313§5.1離散信道編碼問(wèn)題對(duì)兩種譯碼準(zhǔn)則的評(píng)述最大后驗(yàn)概率準(zhǔn)則具有很好的直觀合理性。收到y(tǒng)的條件下，最可能發(fā)送的是哪個(gè)碼字，就認(rèn)為發(fā)送的是哪個(gè)碼字”。最大似然概率準(zhǔn)則（最小距離準(zhǔn)則）所具有的直觀合理性弱一些。發(fā)送哪個(gè)碼字的條件下，最可能收到y(tǒng)，就認(rèn)為發(fā)送的是哪個(gè)碼字。最大似然概率準(zhǔn)則（最小距離準(zhǔn)則）的實(shí)現(xiàn)比最大后驗(yàn)概率準(zhǔn)則的實(shí)現(xiàn)更簡(jiǎn)單：前者只需要看哪個(gè)碼字與y的Hamming距離最?。缓笳咝枰栏鞔a字的概率分布，然后用貝葉斯公式計(jì)算并比較后驗(yàn)概率。兩種準(zhǔn)則都可以用在沒(méi)有編碼（直接發(fā)送）情況下的糾錯(cuò)譯碼。第十四頁(yè)，共二十七頁(yè)，2022年，8月28日2023/3/1314§5.1離散信道編碼問(wèn)題例(p143)BSC信道的轉(zhuǎn)移概率矩陣為取L=1。如果直接將X1輸入信道，信道的輸出為X1’，則①當(dāng)信道傳輸錯(cuò)誤時(shí)無(wú)法檢測(cè)到。②正確接收的概率為P(X1’=X1)=1-p。今取L=1，N=4，二元(4,1)碼如下：0→0000，1→1111。第十五頁(yè)，共二十七頁(yè)，2022年，8月28日2023/3/1315§5.1離散信道編碼問(wèn)題譯碼規(guī)則如下：當(dāng)(Y1Y2Y3Y4)中1的個(gè)數(shù)為3或4時(shí)，(Y1Y2Y3Y4)→(1111)→1；當(dāng)(Y1Y2Y3Y4)中1的個(gè)數(shù)為0或1時(shí)，(Y1Y2Y3Y4)→(0000)→0；當(dāng)(Y1Y2Y3Y4)中1的個(gè)數(shù)為2時(shí)，(0011)、(1100)、(1001)→(0000)→0，(0101)、(1010)、(0110)→(1111)→1。譯碼規(guī)則顯然是最小距離準(zhǔn)則。

第十六頁(yè)，共二十七頁(yè)，2022年，8月28日2023/3/1316§5.1離散信道編碼問(wèn)題何時(shí)檢測(cè)到信道傳輸錯(cuò)誤？當(dāng)(Y1Y2Y3Y4)不是一個(gè)碼字時(shí)，檢測(cè)到信道傳輸錯(cuò)誤。換句話說(shuō)，(Y1Y2Y3Y4)與原發(fā)碼字(U1U2U3U4)的Hamming距離≥1且≤3時(shí)，檢測(cè)到信道傳輸錯(cuò)誤。因此，信道傳輸有錯(cuò)誤但能檢測(cè)出錯(cuò)誤的概率為第十七頁(yè)，共二十七頁(yè)，2022年，8月28日2023/3/1317§5.1離散信道編碼問(wèn)題何時(shí)正確譯碼（正確接收）？當(dāng)(Y1Y2Y3Y4)與原發(fā)碼字(U1U2U3U4)的Hamming距離≤1時(shí)，正確譯碼；當(dāng)(Y1Y2Y3Y4)與原發(fā)碼字(U1U2U3U4)的Hamming距離=2時(shí)，一半能正確譯碼，另一半不能正確譯碼；當(dāng)(Y1Y2Y3Y4)與原發(fā)碼字(U1U2U3U4)的Hamming距離≥3時(shí)，不能正確譯碼。正確譯碼（正確接收）的概率為第十八頁(yè)，共二十七頁(yè)，2022年，8月28日2023/3/1318§5.1離散信道編碼問(wèn)題第十九頁(yè)，共二十七頁(yè)，2022年，8月28日2023/3/1319§5.2~3離散信道編碼定理首先需要說(shuō)明，上述離散信道編碼的編碼速率（信息率R

）本來(lái)是設(shè)備所確定的。當(dāng)信源每秒產(chǎn)生ns個(gè)字母，信道編碼所使用的設(shè)備每秒產(chǎn)生nc個(gè)字母，則設(shè)備所確定的編碼速率就是R=ns/nc。其次，實(shí)際編碼速率（實(shí)際信息率L/N

）必須不小于設(shè)備所確定的編碼速率：L/N≥R。于是對(duì)離散信道編碼有了以下兩條相互矛盾的要求：（1）實(shí)際編碼速率L/N盡可能小以便使正確譯碼（正確接收）的概率盡可能接近1。（2）實(shí)際編碼速率不小于設(shè)備所確定的編碼速率L/N≥R。第二十頁(yè)，共二十七頁(yè)，2022年，8月28日2023/3/1320§5.2~3離散信道編碼定理設(shè)信源序列經(jīng)過(guò)信源編碼后變成了如下的序列…X-2X-1X0X1X2…。設(shè)各隨機(jī)變量獨(dú)立同分布。記H(X)為X0的熵，C為信道容量。如果設(shè)備所確定的編碼速率R<C/H(X)，則能夠同時(shí)滿足以下兩條要求：（1）L/N使正確譯碼（正確接收）的概率盡可能接近1。（2）L/N≥R。如果設(shè)備所確定的編碼速率R>C/H(X)，則不能夠同時(shí)滿足這兩條要求。（如果設(shè)備所確定的編碼速率R=C/H(X)，則情況如何？很復(fù)雜，屬于邊界情況，沒(méi)有簡(jiǎn)單整齊的結(jié)論。）第二十一頁(yè)，共二十七頁(yè)，2022年，8月28日2023/3/1321§5.2~3離散信道編碼定理定理(p152)（Shannon信道編碼定理）如果設(shè)備所確定的編碼速率R<C/H(X)，則對(duì)任何正整數(shù)L（L=1，2，…），存在D元(N,L)碼和對(duì)應(yīng)的譯碼方法，使第二十二頁(yè)，共二十七頁(yè)，2022年，8月28日2023/3/1322習(xí)題課5.l設(shè)有一DMC，其轉(zhuǎn)移概率矩陣如下。若Q(x1)＝l/2，Q(x2)＝Q(x3)＝1/4，試求最佳譯碼判決以及誤碼率。第二十三頁(yè)，共二十七頁(yè)，2022年，8月28日2023/3/1323習(xí)題課[5.l的解答]最佳譯碼判決指的是最大后驗(yàn)概率譯碼。記(Q(x1),Q(x2),Q(x3))信道的輸入隨機(jī)變量X的概率向量，又稱為先驗(yàn)概率向量，(W(y1),W(y2),W(y3))為信道的輸出隨機(jī)變量Y的分布概率向量。則(Q(x1),Q(x2),Q(x3))=(1/2,1/4,1/4)，第二十四頁(yè)，共二十七頁(yè)，2022年，8月28日2023/3/1324習(xí)題課P((X,Y)=(x1,y1))=1/4P((X,Y)=(x2,y1))=1/24P((X,Y)=(x3,y1))=1/12P((X,Y)=(x1,y2))=1/6P((X,Y)=(x2,y2))=1/8P((X,Y)=(x3,y2))=1/24P((X,Y)=(x1,y3))=1/12P((X,Y)=(x2,y3))=1/12P((X,Y)=(x3,y3))=1/8P((X=x1|Y=y1)=P((X,Y)=(x1,y1))/W(y1)=2/3P((X=x2|Y=y1)=P((X,Y)=(x2,y1))/W(y1)=1/9P((X=x3|Y=y1)=P((X,Y)=(x3,y1))/W(y1)=2/9P((X=x1|Y=y2)=P((X,Y)=(x1,y2))/W(y2)=1/2P((X=x2|Y=y2)=P((X,Y)=(x2,y2))/W(y2)=3/8P((X=x3|Y=y2)=P((X,Y)=(x3,y2))/W(y2)=1/8P((X=x1|