1、北工大信息論第六章 有噪信道編碼14 第六章 有噪信道編碼需要把握的內容： 譯碼規章與錯誤概率的關系 平均差錯率與信道編碼的關系 漢明距離 有噪信道編碼定理 線性分組碼 第一節一.譯碼規章信源 (信源編碼，信道編碼) 譯碼規章與錯誤譯碼概率 信道 譯碼 (信源譯碼，信道譯碼) 信宿 0 p 1/ 4p 3/ 4 p 3/ 4 0 1 p 1/ 4 1 定義信道譯碼函數f是從輸出符號集合b到輸入符號集合a的映射 f (b j ) a j * a, j 1,2,., s譯碼函數又稱譯碼規章 留意:譯碼規章是人為定的,對于同一個信道可有多個 不同的譯碼規章 例如：對于二元信道就可制定若干不同譯碼規章

2、，如圖所示。 a1 a2 0.8 0.2 0.10.9 b1 b2 ( f 1 b1 ) a1 f1: ( 1 b2 ) a1 f ( f 3 b1 ) a1 f3: ( 3 b2 ) a 2 f ( f 2 b1 ) a 2 f2: ( 2 b2 ) a 2 f ( f 4 b1 ) a 2 f4: ( 4 b2 ) a1 f 二.錯誤譯碼概率“好”的譯碼規章的標準是：錯誤譯碼概率小 譯碼正確-假如接收到bj,按 f (b j ) a j * a而輸入的剛好是aj*p( x bj的譯碼正確概率為： 譯成aj* , a* j | y b j ) p f (b j ) | b j p(e | b

3、 j ) p x f (b j ) | y b j 1 p f (b j ) | b j bj的譯碼錯誤概率為： 譯碼錯誤概率的統計平均稱為平均譯碼錯誤概率或平 均差錯率，記為pes j 1 pe p(b j ) p(e | b j ) p(b j )1 p f (b j ) | b j j 1 s pe與譯碼規章f有關使pe小的譯碼規章f是好的譯碼規章 簡化pe式為下面的形式：pe p(b j )1 p f (b j ) | b j j 1 s 1 p(b j ) p f (b j ) | b j j 1 s 1 p(b j f (b j ) 1 p(b j a* j)j 1 j 1 s s

4、 pe p (aib j ) p (ai )p(b j | ai )y x a* y x a* 當輸入等概:上式可化為： p f (b j ) p a* j 1/ r1 pe p(b j | ai ) r y x a* 例6-1: 參見下圖，假設p(a1)=0.4,分別求出4種譯碼規 則所對應的平均差錯率。a1 a20.8 0.2 0.1 0.9 b1 b2 ( f 1 b1 ) a1 f1: ( 1 b2 ) a1 f ( f 3 b1 ) a1 f3: ( 3 b2 ) a 2 f ( f 2 b1 ) a 2 f2: ( 2 b2 ) a 2 f ( f 4 b1 ) a 2 f4: (

5、 4 b2 ) a1 f 解：信道輸入概率矩陣和轉移矩陣分別為： px 0.4 0.6 0.8 0.2 py | x 0.1 0.9 轉移矩陣各行元素乘以對應的輸入概率，得聯合概率矩陣 0.32 pxy 0.06 0.08 0.54 譯碼規章f1對應的平均差錯率為 pe ( f1 ) 1 p f1 (b j ), b j j 1 s 1 p (a1b1 ) p ( a1b2 ) 1 (0.32 0.08) 0.6 其它譯碼規章對應的平均差錯率分別為pe(f2)=0.4 pe(f3)=0.14 pe(f4)=0.86 四種規章相比， f3最好，f4最差 其次節 兩種典型的譯碼規章 一.最佳譯碼規

6、章平均差錯率pe與譯碼規章有關，使pe達到最小 的譯碼規章最佳譯碼規章。 pe p(b j ) p(e | b j ) p(b j )1 p f (b j ) | b j j 1 j 1 s s 可以看出：要減小pe ,必需減小各個接收符號的譯碼 錯誤概率 p(e | bj ) ,或者增大各個接收符號的譯碼正確概 率 p f (bj ) | bj 。 確定最佳譯碼規章的方法：* f ( b ) a j j a,b j b f: , ai a * p(a j | b j ) p(ai | b j ) 該最佳譯碼規章稱為最大后驗概率譯碼規章最大后驗概率條件可等價為最大聯合概率條件,為什么呢?p(a

7、 * j | b j ) p ( ai | b j )* p(b j ) p(a* | b ) p ( b ) p ( a | b ) p ( a j j j i j j b j ) p ( ai b j ) 則最佳譯碼規章又可表示為：* f (b j ) a j a,b j b f: , ai a * p(a j b j ) p(ai b j ) 最佳譯碼規章又稱為最大聯合概率譯碼規章 例6-2 參見下圖，假設p(a1)=0.4,求最佳譯碼規章。a10.8 a2 0.2 0.1 0.9 b1 a1 0.32 a2 0.06 b2 0.08 0.54 b1 b2 解：例6-1已經求出聯合概率矩

8、陣，重寫為 pxy 則最大聯合概率譯碼規章為： f (b1 ) a1 f : f (b2 ) a 2 對應的平均差錯概率： pe 1 p f (b j )b j 1 (0.32 0.54) 0.14j 1 s 二、極大似然譯碼規章按最大轉移概率條件確定的譯碼規章* f ( b ) a j j a,b j b f: , ai a * p(b j | a j ) p(b j | ai ) 例6-3:已知信道轉移矩陣，試確定譯碼規章。 0.5 py | x 0.2 0.3 0.3 0.2 0.3 0.5 0.3 0.4 解：按轉移概率最大原則確定極大似然譯碼規章如下： f (b1 ) a1 f :

9、f (b2 ) a1 , (a2 , f (b ) a 3 2 a3 ) 當信道輸入等概率時，極大似然譯碼規章是最佳的。 提問:為什么?緣由是：極大似然譯碼規章是按最大轉移概率條件確定 的，即 p(b j | a ) p(b j | ai )* j 假如輸入等概，則 p( a ) p( a i )* j 所以 p(a ) p(b j | a ) p(ai ) p(b j | ai )* j * j * j p(a b j ) p(ai b j ) 第三節 信道編碼的編碼原則 二元信源和二元對稱信道的模型如下圖所示dms u u1,u2 x a1,a2 a1=0 a2=1 dmc1-pp=0.0

10、1 y b1,b2 b1=0 b2=1 u u1 0 u 2 1 p 0.5 0 . 5 u p=0.01 1-p 由圖可知：信源的熵為：h(u)=logm=1比特/符號 信道容量為：c=log2-h(0.99,0.01)=0.92比特/符號信源與信道之間不加信道編碼，則由于信道輸入等概分布，則 極大似然譯碼規章就是最佳譯碼規章，依據信道轉移矩陣b2 b1 a1 py | x a 0 . 99 0 . 01 2 0.01 0.99 f (b1 ) a1 確定極大似然譯碼規章為：f : f (b2 ) a 2 平均差錯率為： 1 s 1 pe 1 pb j | f (b j ) p(b j |

11、ai ) r j 1 r y , x a* (0.01 0.01) / 2 0.01 提問：傳輸系統的pe要求掌握在10-6以下，而利用譯 碼規章的pe太高，如何降低平均差錯率呢？ -信道編碼一.簡潔重復編碼對信源符號進行“重復2次”編碼:u x3 py 信道編碼f u1 , u 2 1 , 2 ,., 8 3 |x 3 y3 信道譯碼f 1 , 2 ,., 8 x3 1 , 8 f u1 0 1 000 000 1 001 2 001 2 010 3 3 010 011 4 011 1 000 4 f 5 100 8 111 100 5 101 6 6 101 7 110 110 7 f 1

12、11 u2 1 8 111 8 “重復2次”編碼規章為 0 000 f: 1 111 求出3次擴展信道的轉移矩陣 p y 3|x 3 1 1 3 p 8 3 p 8 2 2 2 2 p p p p p p p p p p 2 p p 2 p 3 , p 1 p 2 2 2 2 2 2 p p p p p p p p p p p p p3 f ( 3) 1 f ( 7) 8 f ( 5) 1 f ( 8) 8 2 3 4 5 6 7 按極大似然譯碼規章得譯碼函數f ( 1) 1 f ( 4) 8 f ( 2) 1 f ( 6) 8 即： 1 000 2 001 f 1 000 3 010 5 100 4 6 7 8 011 101 f 8 111 110 111 譯碼差錯率為： 結論：信道編碼降低平均錯誤率 3 2 1 8 1 pe 1 p i | f ( i ) 1 (2