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

1、2021/1/23,1,2021/1/23,2,2021/1/23,3,信道編碼,在傳輸過程中噪聲和干擾在所難免，為了降低差錯率，提高傳送的可靠性，在信道編碼器中可以引入冗余度，在信道解碼端就可以利用此冗余度來盡可能地重建輸入序列。 可靠性：增加冗余,2021/1/23,4,實際信道由于信道噪聲的干擾，傳輸錯誤不可避免。為了降低平均差錯率，可先對消息進行編碼信道編碼，再送入信道傳送。 信道編碼的基本思路是根據(jù)一定的規(guī)律在待發(fā)送的信息碼中加入一些多余的碼元，以保證受損或出錯的信息仍能在接收端恢復 。信道編碼的任務就是構造出以最小冗余度代價換取最大抗干擾性能的“好碼”。,2021/1/23,5,一

2、般來說，引入監(jiān)督碼元越多，碼的檢錯、糾錯能力越強，但信道的傳輸效率下降也越多。 人們研究的目標是尋找一種編碼方法使所加的監(jiān)督碼元最少，而檢錯、糾錯能力又高且又便于實現(xiàn)。,通信過程,信源,信道編碼器,Um,信道,Ym,信道譯碼器,信宿,干擾,Xm,Xm,糾錯編碼器 調制器,糾錯譯碼器 解調器,信源消息序列經(jīng)過信源編碼后變成了信息隨機變量序列Xm ；其中每個隨機變量Xm的事件全體都是D元字母表中的元素。,2021/1/23,7,將信息隨機變量序列Xm分成長度為k0的段（每段稱為一個信息段）; 然后依次輸入到有L位移位寄存器的編碼器中， 編碼器根據(jù)當前的輸入和編碼器的狀態(tài)計算出n0個編碼數(shù)字（稱為碼

3、段）送入信道，其中L稱為編碼約束長度。,編碼速率：信息段與碼段段長之比。 糾錯編碼： k0長信息段空間到n0長二元碼段空間的映射。 映射的任何一種指定方案就是一種編碼方案。,2021/1/23,8,(n0, k0)卷積碼 (Convolutional codes)：各分組相關，約束長度L為(m+1) k0 n0長碼段 (N, L)分組碼 (Block codes)：分組之間獨立，約束長度L為k0,N=n0長碼段,2021/1/23,9,(N, L)分組碼的糾錯譯碼,譯碼器根據(jù)收到的N 長碼段y=(Y1Y2YN)和編碼規(guī)則，對發(fā)送的M=2L個可能的信息段xm=(X1X2XL)中的哪一個作出判決，

4、這樣的一個通信過程yxm=(X1X2XL)稱為糾錯譯碼。 譯碼是編碼的反變換，也是一種映射，若與碼段y=(Y1Y2YN)對應的信息段是xm，經(jīng)過通信過程判為xm，則： 若xm=xm，則正確譯碼; 若xmxm，發(fā)生譯碼錯誤。 譯碼錯誤概率（誤組率）： 接收y的譯碼錯誤概率：,2021/1/23,10,接下來來分析這個錯誤概率與哪些因素有關。 在第四章里，我們已經(jīng)知道錯誤概率與信道統(tǒng)計特性有關。但通信過程一般并不是在信道輸出端就結束了，還要經(jīng)過譯碼過程（或判決過程）才到達消息的終端（收信者）。因此譯碼過程和譯碼規(guī)則對系統(tǒng)的錯誤概率影響很大。,譯碼規(guī)則對錯誤概率的影響,2021/1/23,11,譯碼

5、規(guī)則對錯誤概率的影響,因此譯碼規(guī)則對系統(tǒng)的錯誤概率影響很大。,譯碼規(guī)則1：,譯碼規(guī)則2：,現(xiàn)在我們來定義譯碼規(guī)則，制定譯碼規(guī)則就是設計一個函數(shù)它對于每一個輸出符號確定一個唯一的輸入符號與其對應。,2021/1/23,12,譯碼規(guī)則,例：有一個離散信道，其轉移概率矩陣P為 根據(jù)該轉移概率矩陣可以設計一個譯碼規(guī)則A如上;,也可以設計一個譯碼規(guī)則B如下：,2021/1/23,13,由于s個輸出符號中的每一個都可以翻譯成r個輸入符號中的任何一個，所以共有rs種譯碼規(guī)則可供選擇。 譯碼規(guī)則的選擇應該根據(jù)什么準則？ 一個很自然的準則當然就是要使錯誤概率為最小。,譯碼規(guī)則,制定譯碼規(guī)則就是設計一個函數(shù)它對于

6、每一個輸出符號確定一個唯一的輸入符號與其對應。,若信道有r個輸入符號，s個輸出符號，則共有多少種譯碼規(guī)則？,2021/1/23,14,最佳譯碼規(guī)則使Pe(y)達到最小 最佳譯碼規(guī)則的確定： 對接收矢量y和所有可能的發(fā)送消息m，計算P(m|y)； 若對所有的m，有 ，將y判為m。 P(m|y)被稱為后驗概率，這種譯碼準則被稱為最大后驗概率準則。,兩種典型的譯碼規(guī)則,2021/1/23,15,例： （5.1） 設有一DMC，其轉移概率矩陣如下。 若Q(x1)l/2，Q(x2)Q(x3)1/4，試求最佳譯碼判決。,兩種典型的譯碼規(guī)則,2021/1/23,16,解答 最佳譯碼判決指的是最大后驗概率譯碼

7、。記(Q(x1), Q(x2), Q(x3)信道的輸入隨機變量X的概率向量，又稱為先驗概率向量， (W(y1), W(y2), W(y3)為信道的輸出隨機變量Y的分布概率向量。則 (Q(x1), Q(x2), Q(x3)=(1/2,1/4, 1/4)，,兩種典型的譯碼規(guī)則,2021/1/23,17,兩種典型的譯碼規(guī)則,2021/1/23,18,收到“Y=y1”時，譯作 “X=x1”， 誤碼率（譯碼錯誤的概率）為 1/3； 收到“Y=y2”時，譯作 “X=x1”，誤碼率（譯碼錯誤的概率）為 1/2； 收到“Y=y3”時，譯作 “X=x3”，誤碼率（譯碼錯誤的概率）為 4/7。,兩種典型的譯碼規(guī)則

8、,2021/1/23,19,兩種典型的譯碼規(guī)則 計算后驗概率是困難的，針對具體信道（轉移概率已知），采用最大似然準則 離散序列,若所有可能消息序列的先驗概率相等,最大似然準則,對特定的接收序列y，選擇m使得m轉移成y的概率不小于其它任意消息轉移為y的概率,2021/1/23,20,例 已知信道轉移矩陣如下，試確定譯碼規(guī)則。 解 只知轉移概率，無法找出最佳譯碼規(guī)則，只能采用最大似然準則。 將轉移概率矩陣各列最大的值標出，重寫轉移矩陣如下：,2021/1/23,21,按轉移概率最大原則確定最大似然準則如下： 盡管一般情況下并不知道這樣譯碼 的差錯率。但可以證明，當信道輸入等概時，最大似然準則也是最

9、佳的。,兩種典型的譯碼規(guī)則,2021/1/23,22,命題 如果每個碼字是等概出現(xiàn)的，則最大后驗概率準則等價于最大似然概率準則。 證明,兩種典型的譯碼規(guī)則,2021/1/23,23,譯碼錯誤概率,譯碼規(guī)則也可以看做是由信道輸出空間YN到消息空間UL的映射，將YN按譯碼規(guī)則劃分為M=2L個不相交的判決區(qū)間Y1,Y2,YM,其中 Yk=y:lnQ(k)+lnP(y|xk) lnQ(m)+lnP(y|xm), 對所有的mk,最有可能是由xk轉移過來概率的所有輸出序列y的集合,P(xk|y) P(xm|y),2021/1/23,24,若消息m的先驗概率為Q(m)，則平均譯碼錯誤概率為,譯碼錯誤概率,當

10、發(fā)送消息為m，而接收y落入YmC，即Ym的補集中時，就會產(chǎn)生譯碼錯誤，給定m時的譯碼錯誤概率為,2021/1/23,25,定義 兩個等長符號序列 和 之間的漢明距離，是 與 之間對應位置上不同符號的個數(shù)，記為 ， 例如 小意味著 與 的相似程度高，否則 與 的相似程度低。,漢明距離,2021/1/23,26,最小漢明距離譯碼準則（最小錯誤準則） 記y與u的Hamming距離為d(y, u)，則,最小漢明距離譯碼,2021/1/23,27,最小漢明距離譯碼,設信道 D元對稱DMC信道，字母表為0, 1, , D-1。其信道轉移概率矩陣為DD矩陣如下。 信道傳輸錯誤的概率定義為 P(輸出不等于k|

11、輸入為k)= p，k0, 1, , D-1。 此處p(1-p)。,2021/1/23,28,后驗概率的計算：記q(u)=P(U1U2UN)=(u1u2uN)，稱q(u)為先驗概率；我們知道 pN(y|u)=P( (Y1Y2YN)=y|(U1U2UN)=u) =P(Y1=y1|U1=u1)P(Y2=y2|U2=u2)P(YN=yN|UN=uN) 若記d是(y1y2yN)與(u1u2uN)對應位置值不相同的位數(shù)，即d為(y1y2yN)與(u1u2uN) 之間的Hamming距離，則 pN(y|u)=(p/(D-1)d(1-p)N-d，,最小漢明距離譯碼,2021/1/23,29,命題 對于對稱DM

12、C信道，最大似然概率準則等價于最小漢明距離譯碼準則。 證明：若pN(y|u)達到最大，即對于任意的wu，有 pN(y|u)pN(y|w)， 令記d是y與u的Hamming距離， d是y與w的Hamming距離，則 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， pN(y|w)=(p/(D-1)d(1-p)N-d,最小漢明距離譯碼,對pN(y|u)pN(y|w)兩邊取對數(shù)，則有,2021/1/23,30,dln(p/(D-1)+(N-d)ln(1-p) d ln(p/(D-1)+(N-d)ln(1-p)

13、,最大后驗概率譯碼,最大似然譯碼,所有消息等概,q元對稱信道,最小漢明距離譯碼,最小漢明距離譯碼,d(ln (p/(D-1) -ln(1-p)d (ln(p/(D-1)-ln(1-p) d(ln (p/(D-1)/(1-p)d (ln(p/(D-1)/(1-p),注意到p/(D-1)(1-p)，所以dd。 得證。,2021/1/23,31,例5.1.1(p143) BSC信道的轉移概率矩陣為 取L=1。如果直接將X1輸入信道，信道的輸出為X1，則 當信道傳輸錯誤時無法檢測到。 正確接收的概率為P(X1=X1)=1-p。 今取L=1，N=4，二元(4, 1)碼如下： 00000， 11111。,

14、最小漢明距離譯碼,2021/1/23,32,譯碼規(guī)則如下： 當(Y1Y2Y3Y4)與(1111)的漢明距離不大于1時，將其譯為1，放入集合A 即1111;1110;1101;1011;0111屬于集合A ，譯為1； 當(Y1Y2Y3Y4)與(0000)的漢明距離不大于1時，將其譯為0，放入集合B 即0000;0001;0010;0100;1000屬于集合B ，譯為0； 若采用完備譯碼，即任何情況都必須做出判決，則當(Y1Y2Y3Y4)與(1111)及(0000)的漢明距離都等于2時，做如下處理， (0011)、(1100)、(1001)放入集合B ，譯為0， (0101)、(1010)、(01

15、10)放入集合A ，譯為1。 譯碼規(guī)則顯然是最小距離準則。,最小漢明距離譯碼,2021/1/23,33,A=1111;1110;1101;1011;0111; 0101;1010;0110 B= 0000;0001;0010;0100;1000; 0011;1100;1001 信道傳輸錯誤概率為 ？ 當集合A(或B)中的元素譯為0（或1）時，信道傳輸錯誤。 因此，信道傳輸出現(xiàn)錯誤的概率為,最小漢明距離譯碼,2021/1/23,34,若收到(0011)、(1100)、(1001)、(0101)、(1010)、(0110)這六個元素之一時，將其判為0和1按照最小漢明距離譯碼是等價的，可以單獨作一個

16、集合C,它表明接收的向量有錯誤但無法判決，此時 集合A=(1111;1110;1101;1011;0111)1； 集合B=(0000;0001;0010;0100;1000)0； 信道傳輸出現(xiàn)錯誤的概率為： 發(fā)現(xiàn)錯誤無法判決的概率為：,最小漢明距離譯碼,2021/1/23,35,Fano不等式和信道編碼逆定理,信道編碼逆定理：表明當每個符號所含的信息量超過信道容量時，錯誤將是不可避免的。,2021/1/23,36,研究Pb，HL(U) ， I (UL;VL)之間的關系,先考慮L=1 ，這時，當收到V后關于U的平均不確定性或含糊度H(U|V)若不為0，就一定有錯誤存在。,信道編碼,信 道,信道譯

17、碼,2021/1/23,37,設空間U和V各有M個元素a1，a2，aM。,平均誤碼率,接收矢量y判為vj時的錯誤概率,vj判為uj時正確譯碼,2021/1/23,38,定理5.2.1 (Fano不等式) U 和V 空間中的事件滿足下不等式,其中,用V估計U產(chǎn)生的信息損失,誤差的不確定性,估計錯誤時消除的不確定性,2021/1/23,39,證明：引入譯碼錯誤隨機變量 E，E1 表示譯碼錯誤，E=0 表示譯碼正確。,H(UE|V) = H(E|V) + H(U|EV),H(E) + Pb H(U|E=1, V) + (1-Pb) H(U|E=0, V), H(E) + Pb log (|U|-1)

18、 + 0,另一方面：H(UE|V) = H(U|V) + H(E|UV)= H(U|V),所以 H(U|V) H(E) + Pb log (|U|-1)， 也就是 H(U|V) H(Pb) + Pb log (|U|-1),2021/1/23,40,L1時,定理5.2.2 令ULVL是信息序列u=(u1,u2,uL)和譯碼判決序列v=(v1,v2,vL)的聯(lián)合集，Pb為誤比特率，表示為,其中Pek是第k位出錯的概率，則有,2021/1/23,41,證明：,首先,2021/1/23,42,信道編碼逆定理,設離散平穩(wěn)信源的字母表有M個字母，每s秒產(chǎn)生一個字母，且熵為 令離散無記憶信道的容量為C，每

19、c秒送一個信道符號，若長為L的信息序列被變成NLs/ c的碼字，則誤碼率滿足 當 誤碼率為非零值。,2021/1/23,43,L1時,由信息處理定理,2021/1/23,44,信道編碼,信 道,信道譯碼,這個定理說明，對于信源在Ls秒產(chǎn)生的信息序列，當以長為NLs/c的分組碼表示，經(jīng)過信道傳送和譯碼器處理時，若信源每個符號所含的熵H (U)大于信道容量s/c C，則不管采用何種編譯碼方法都不能使得平均錯誤概率為0。,2021/1/23,45,聯(lián)合典型序列和信道編碼定理,2021/1/23,46,3.2 離散無記憶（簡單）信源的等長編碼,當L足夠大時，在信源序列中必有一些消息序列其自信息量的均值

20、與信源熵之差小于，而對另外一些信源序列其差 ，因此，可以把信源序列分成兩個互補的子集。,2021/1/23,47,3.2 離散無記憶（簡單）信源的等長編碼,定義3.2.1(p57) 定義 TU(L, )=(u1u2uL)|H(U1)-ILH(U1)+， 稱TU(L, )為-典型序列集。 稱TU(L, )的補集為非-典型序列集。,P(U1U2UL) )=(u1u2uL)| (u1u2uL) TU(L, )1-。 系3.2.1(特定典型序列出現(xiàn)的概率) 2-L(H(U)+)P(U1U2UL)=(u1u2uL)2-L(H(U)-)。 系3.2.2(典型序列的數(shù)量) (1-)2L(H(U)-)|TU(

21、L, )|2L(H(U)+)。,2021/1/23,48,定義5.3.1 x和y是聯(lián)合典型序列,(1) x是典型序列，即對任意小的正數(shù)e，存在N使,(2) xy是典型序列，即對任意小的正數(shù)e，存在N使,(2) y是典型序列，即對任意小的正數(shù)e ，存在N使,2021/1/23,49,聯(lián)合典型序列,TX(N,e)表示XN中典型序列的集合，排在前邊 TY(N,e)表示YN中的典型序列集合，排在前邊 TXY(N,e) 表示XN YN 中的典型序列集 ，分布在陣列的左上角,|XN|個可能的x序列作為行號，以|YN|個可能的y序列作為列號,2021/1/23,50,聯(lián)合典型序列,引理1,上圖中每列最多的點數(shù),上圖中每行最多的點數(shù),給定y和y構成聯(lián)合典型序列的所有x序列的集合，稱為在條件y下，x的典型序列集。,2021/1/23,51,聯(lián)合典型序列,2021/1/23,52,聯(lián)合典型序列,引理2,證明：,2021/1/23,53,聯(lián)合典型序列,左上角中聯(lián)合典型序列點的密度,引理3,陣列中的左上角的總的格子數(shù),2021/1/23,54,信道編碼定理,DMC P(y|x),令編碼速率為R，則各碼字的標號集為1,2NR。 編碼函數(shù),譯碼函數(shù),2021/1/23,55,信道編碼定理