信息論與編碼理論基礎(chǔ)第五章

1、信息論與編碼理論基礎(chǔ)第五章第1頁(yè)，共27頁(yè)，2022年，5月20日，1點(diǎn)14分，星期一2022/9/115.1 離散信道編碼問(wèn)題最簡(jiǎn)單的檢錯(cuò)和糾錯(cuò)單個(gè)的字無(wú)法檢錯(cuò)：捫？詞匯能夠檢錯(cuò)：我捫的我捫的詞匯能夠糾錯(cuò)：我捫的我們的，我等的，我輩的，我班的，原因分析：“捫？”可以有幾萬(wàn)個(gè)答案，但“我捫的？”的答案卻很少。結(jié)論：課文以及詞匯的概率分布的稀疏性可以用來(lái)檢錯(cuò)和糾錯(cuò)。第2頁(yè)，共27頁(yè)，2022年，5月20日，1點(diǎn)14分，星期一2022/9/125.1 離散信道編碼問(wèn)題設(shè)信道是一個(gè)D元字母輸入/ D元字母輸出的DMC信道，字母表為0, 1, , D-1。其信道轉(zhuǎn)移概率矩陣為DD矩陣如下。這是一個(gè)對(duì)稱

2、信道。信道傳輸錯(cuò)誤的概率定義為P(輸出不等于k|輸入為k)= p，k0, 1, , D-1。此處p(1-p)。第3頁(yè)，共27頁(yè)，2022年，5月20日，1點(diǎn)14分，星期一2022/9/135.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)備輸入信道：(X1X2XL), (XL+1XL+2X2L), 。如果直接將(X1X2XL)輸入信道，信道的輸出為(X1X2XL)，則當(dāng)信道傳輸錯(cuò)誤時(shí)無(wú)法檢測(cè)到（即接收方無(wú)法確知是

3、否正確接收）。正確接收的概率為P(X1X2XL)=(X1X2XL)=P(X1=X1)P(X2=X2)P(XL=XL)=(1-p)L。 第4頁(yè)，共27頁(yè)，2022年，5月20日，1點(diǎn)14分，星期一2022/9/145.1 離散信道編碼問(wèn)題將(X1X2XL)進(jìn)行變換：C(X1X2XL)=(U1U2UN)，其中 (U1U2UN)為N維隨機(jī)向量，NL，且變換是單射（即(X1X2XL)的不同事件映射到(U1U2UN)的不同事件）。將(U1U2UN)輸入信道；信道的輸出為(Y1Y2YN)；再根據(jù)(Y1Y2YN)的值猜測(cè)出輸入信道的值(U1U2UN)，并根據(jù)變換式(U1U2UN)=C(X1X2XL)將(U1

4、U2UN)反變換為(X1X2XL)。如果(X1X2XL)=(X1X2XL)，則正確接收。第5頁(yè)，共27頁(yè)，2022年，5月20日，1點(diǎn)14分，星期一2022/9/155.1 離散信道編碼問(wèn)題（1）(X1X2XL)的事件共有DL個(gè)，因此(U1U2UN)的事件共有DL個(gè)，占N維向量值的份額為DL/DN=1/DN-L。因此當(dāng)信道傳輸錯(cuò)誤時(shí)，有可能使輸出值(Y1Y2YN)不在這1/DN-L份額之內(nèi)。這就是說(shuō)，信道傳輸錯(cuò)誤有可能被檢測(cè)到。（2）如果精心地設(shè)計(jì)變換C(X1X2XL)=(U1U2UN)和猜測(cè)規(guī)則(Y1Y2YN)(U1U2UN)，則正確接收的概率遠(yuǎn)遠(yuǎn)大于(1-p)L。 （3）變換(X1X2XL

5、)(U1U2UN)=C(X1X2XL)稱為信道編碼，又稱為(N, L)碼。一個(gè)事件的變換值稱為該事件的碼字。L稱為信息長(zhǎng)，N稱為碼長(zhǎng)。第6頁(yè)，共27頁(yè)，2022年，5月20日，1點(diǎn)14分，星期一2022/9/165.1 離散信道編碼問(wèn)題（4）過(guò)程(Y1Y2YN)(U1U2UN)(X1X2XL)稱為糾錯(cuò)譯碼。當(dāng)(X1X2XL)=(X1X2XL)時(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為編碼速率，也稱為

6、信息率。（似乎與信源編碼相互倒置？）（7）注解：“(X1X2XL)不進(jìn)行編碼”實(shí)際上也是一種編碼，稱為恒等編碼。 此時(shí)N=L，事件x=(x1x2xL)的碼字就是x自身。第7頁(yè)，共27頁(yè)，2022年，5月20日，1點(diǎn)14分，星期一2022/9/175.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(U1U2UN)=u|(Y1Y2YN)=y)。稱b(u|y)為后驗(yàn)概率。最大后驗(yàn)概率準(zhǔn)則：第8頁(yè)，共27頁(yè)，2022年，5月20日，1點(diǎn)14分，星期一2022/9/185.1 離散信道編碼問(wèn)題后驗(yàn)概率的計(jì)算：記q

7、(u)=P(U1U2UN)=u)，稱q(u)為先驗(yàn)概率；pN(y|u)=P( (Y1Y2YN)=y|(U1U2UN)=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是(y1y2yN)與(u1u2uN)對(duì)應(yīng)位置值不相同的位數(shù)；（以后將稱d為Hamming距離）第9頁(yè)，共27頁(yè)，2022年，5月20日，1點(diǎn)14分，星期一2022/9/195.1 離散信道編碼問(wèn)題記w(y)=P(Y1Y2YN)=y)。我們知道第10頁(yè)，共27頁(yè)，2022年，5月20日，1點(diǎn)1

8、4分，星期一2022/9/1105.1 離散信道編碼問(wèn)題最大似然概率準(zhǔn)則最小距離準(zhǔn)則（最小錯(cuò)誤準(zhǔn)則）y與u的Hamming距離定義為(y1y2yN)與(u1u2uN)對(duì)應(yīng)位置值不相同的位數(shù)，記為d(y, u)。第11頁(yè)，共27頁(yè)，2022年，5月20日，1點(diǎn)14分，星期一2022/9/1115.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)

9、且僅當(dāng)y與u的Hamming距離達(dá)到最小。得證。第12頁(yè)，共27頁(yè)，2022年，5月20日，1點(diǎn)14分，星期一2022/9/1125.1 離散信道編碼問(wèn)題命題 如果每個(gè)碼字是等概出現(xiàn)的，則最大后驗(yàn)概率準(zhǔn)則等價(jià)于最大似然概率準(zhǔn)則。證明第13頁(yè)，共27頁(yè)，2022年，5月20日，1點(diǎn)14分，星期一2022/9/1135.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)則（最

10、小距離準(zhǔn)則）的實(shí)現(xiàn)比最大后驗(yàn)概率準(zhǔn)則的實(shí)現(xiàn)更簡(jiǎn)單：前者只需要看哪個(gè)碼字與y的Hamming距離最??；后者需要知道各碼字的概率分布，然后用貝葉斯公式計(jì)算并比較后驗(yàn)概率。兩種準(zhǔn)則都可以用在沒(méi)有編碼（直接發(fā)送）情況下的糾錯(cuò)譯碼。第14頁(yè)，共27頁(yè)，2022年，5月20日，1點(diǎn)14分，星期一2022/9/1145.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)碼如下：00000，11111。 第15頁(yè)，共27頁(yè)，2022年，5月

11、20日，1點(diǎn)14分，星期一2022/9/1155.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)則。 第16頁(yè)，共27頁(yè)，2022年，5月20日，1點(diǎn)14分，星期一2022/9/1165.1 離散信道編碼問(wèn)題何時(shí)檢測(cè)到信道傳輸錯(cuò)誤？當(dāng)(Y1Y2Y3Y4)不是一個(gè)碼字時(shí)，檢

12、測(cè)到信道傳輸錯(cuò)誤。換句話說(shuō)，(Y1Y2Y3Y4)與原發(fā)碼字(U1U2U3U4) 的Hamming距離1且3時(shí)，檢測(cè)到信道傳輸錯(cuò)誤。因此，信道傳輸有錯(cuò)誤但能檢測(cè)出錯(cuò)誤的概率為第17頁(yè)，共27頁(yè)，2022年，5月20日，1點(diǎn)14分，星期一2022/9/1175.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í)，不能正確

13、譯碼。正確譯碼（正確接收）的概率為第18頁(yè)，共27頁(yè)，2022年，5月20日，1點(diǎn)14分，星期一2022/9/1185.1 離散信道編碼問(wèn)題第19頁(yè)，共27頁(yè)，2022年，5月20日，1點(diǎn)14分，星期一2022/9/1195.23 離散信道編碼定理首先需要說(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 盡可能小以

14、便使正確譯碼（正確接收）的概率盡可能接近1。（2）實(shí)際編碼速率不小于設(shè)備所確定的編碼速率L/N R。第20頁(yè)，共27頁(yè)，2022年，5月20日，1點(diǎn)14分，星期一2022/9/1205.23 離散信道編碼定理設(shè)信源序列經(jīng)過(guò)信源編碼后變成了如下的序列X-2X-1X0X1X2。設(shè)各隨機(jī)變量獨(dú)立同分布。記H(X)為X0的熵，C為信道容量。如果設(shè)備所確定的編碼速率RC/H(X)，則不能夠同時(shí)滿足這兩條要求。（如果設(shè)備所確定的編碼速率R=C/H(X)，則情況如何？很復(fù)雜，屬于邊界情況，沒(méi)有簡(jiǎn)單整齊的結(jié)論。 ）第21頁(yè)，共27頁(yè)，2022年，5月20日，1點(diǎn)14分，星期一2022/9/1215.23 離散

15、信道編碼定理定理(p152) （Shannon信道編碼定理）如果設(shè)備所確定的編碼速率RC/H(X)，則對(duì)任何正整數(shù)L（L=1，2，），存在D元(N, L)碼和對(duì)應(yīng)的譯碼方法，使第22頁(yè)，共27頁(yè)，2022年，5月20日，1點(diǎn)14分，星期一2022/9/122習(xí)題課5.l 設(shè)有一DMC，其轉(zhuǎn)移概率矩陣如下。若Q(x1)l/2，Q(x2)Q(x3)1/4，試求最佳譯碼判決以及誤碼率。第23頁(yè)，共27頁(yè)，2022年，5月20日，1點(diǎn)14分，星期一2022/9/123習(xí)題課5.l的解答 最佳譯碼判決指的是最大后驗(yàn)概率譯碼。記(Q(x1), Q(x2), Q(x3)信道的輸入隨機(jī)變量X的概率向量，又稱為

16、先驗(yàn)概率向量， (W(y1), W(y2), W(y3)為信道的輸出隨機(jī)變量Y的分布概率向量。則(Q(x1), Q(x2), Q(x3)=(1/2,1/4, 1/4)，第24頁(yè)，共27頁(yè)，2022年，5月20日，1點(diǎn)14分，星期一2022/9/124習(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)

17、=(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|Y=y3)=P(X, Y)=(x1, y3)/W(y3)=2/7P(X=x2|Y=y3)=P(X, Y)=(x2, y3)/W(y3)=2/7P(X=x3|Y=y3)=P(X, Y)=(x3, y3)/W(y3)=3/7第25頁(yè)，共27頁(yè)，2022年，5月20日，1點(diǎn)14分，星期一2022/9/125習(xí)題課收到“Y=y1”時(shí)，譯作“X=x1”，誤碼率（譯碼錯(cuò)誤的概率）為1/3；收到“Y=y2”時(shí)，譯作“X=x1”，誤碼率（譯碼錯(cuò)誤的概率）為1/2；收到“Y=y3”時(shí)，譯作“X=x3”，誤碼率（譯碼錯(cuò)誤的概