第六章信道編碼2024/3/231第1頁，課件共107頁，創作于2023年2月一、信道編碼－線路碼與糾錯碼信道編碼是以信息在信道上的正確傳輸為目標的編碼，它可分為兩個層次上的問題：一是如何正確接收載有信息的信號，二是如何避免少量差錯信號對信息內容的影響；前者是《通信原理》的問題，后者是《信息論》的問題。比如在數字基帶信號中的編碼，主要目的是為了消除直流分量、改造信號頻譜、便于時鐘頻率的提取、實現數字信號的透明傳輸等。還有的是為了壓縮占用帶寬、抑制碼間干擾，如部分響應系統。這個層次上的編碼，如曼徹斯特碼、AMI碼、HDB3碼、nBmB碼、部分響應系統中的相關編碼等，一般稱之為線路編碼（linecode）。第2頁，課件共107頁，創作于2023年2月從信息論角度來看的信道編碼是指第二層次的編碼，即差錯控制編碼，包括各種形式的糾錯、檢錯碼，統稱為糾錯編碼。糾錯編碼的理論體系屬于信息理論，但糾錯編碼的實現離不開有形載體的信號理論，因此信息的編碼與信號的編碼有天然聯系。糾錯碼在有形化信號階段的差錯概率是符號(symbol)差錯概率（誤碼元率），而在承載信息方面的差錯概率是比特差錯概率(誤比特率)。本書討論的信道編碼主要指糾錯編碼，而衡量糾錯編碼性能的指標主要是誤比特率的改善程度。第3頁，課件共107頁，創作于2023年2月舉例說明：A、B兩消息，可用一位二進制數表示，A=1、B=0出錯時無法判定。

增加一個監督位，取11→A、00→B,若收到01或10時，

可知發生了錯誤，但不能糾正錯誤。

再增加一個監督位，取111→A、000→B,若一位錯：B→001A→110，這樣糾碼：001→000→B,110→111→A若兩位錯011,110則只能發現不能糾錯

因此，這種（3，1）碼，能糾正一個錯，發現兩個錯。

可以看出：本來只需要2位二進制數就可以表示A、B兩個符號，用2或3位表示時，碼長變長，帶來信息冗余。所以，糾錯能力是靠冗余換取的。二、檢錯和糾錯（差錯控制）的基本原理：第4頁，課件共107頁，創作于2023年2月第一、二節有擾離散信道的編碼定理一、差錯控制（1）前向糾錯法FEC

所發碼具有糾錯能力，收端接收后自動糾錯，無需反向信道。實時性好，但譯碼設備復雜，傳輸效率↓

。信源FEC編碼信道FEC譯碼信宿（2）反饋重發ARQ(AutomaticRepeatRequest能檢錯的碼應答信號發端收端第5頁，課件共107頁，創作于2023年2月方法和設備簡單，無需糾檢錯編譯系統。但需要雙向信道，傳輸效率↓、實時性差

。（3）混合糾錯法HEC

能糾錯（能力有限）的碼應答信號發端收端性能介于前面二者之間第6頁，課件共107頁，創作于2023年2月（1）根據各碼組信息碼和監督碼的關系分：

線性碼，非線性碼根據監督碼元是否僅與本組信息元有關

分組碼，卷積碼（2）根據糾錯碼組中信息元是否隱蔽分：

系統碼，非系統碼（3）根據碼的用途分：

檢錯碼，糾錯碼（4）根據碼元的取值：

二進制碼，多進制碼（5）根據構造編碼的數學方法：

代數碼，幾何碼，算術碼（6）二、糾錯碼的分類第7頁，課件共107頁，創作于2023年2月對于給定的有擾信道，若信道容量為C，只要發送端以低于C的信息速率Rb發送信息，則一定存在一種編碼方法，使得譯碼錯誤概率P隨著碼長n的增加，按指數下降至任意小的值，表示為

P

e-nE(Rb)E(Rb)為誤差指數，Rb<C時，E(Rb)>0。兩個結論：1.碼長n和信息速率Rb一定時，隨CE(Rb)P↓隨指數下降。其中C=Blog2(1+S/N)（bit/s）2.在C和Rb一定時(Rb<C)，隨nP隨指數下降(P0)。三、有擾信道編碼定理（Shannon第二定理第8頁，課件共107頁，創作于2023年2月一、分組碼

將信息碼首先分成若干組，分別代表不同的含義，然后為每個碼組附加若干位監督碼元，這種編碼方式稱之為分組碼在分組碼中，監督碼僅監督本碼組中的信息碼元。與分組碼相對應，存在非分組碼，如卷積碼。在非分組碼中，監督碼元除了與本組信息元有關，還與其它組的信息碼元有關。由于卷積碼充分利用了各碼組間的相關性，其性能要優于分組碼。第三節線性分組編碼

分組碼一般用符合（n,k）表示，其中k表示每組碼二進制信息碼元的數目，n是碼組的總位數或碼組長度，則n-k=r為每組碼中的監督碼元的數目，因此分組碼的結構通常可表示為：第9頁，課件共107頁，創作于2023年2月二、碼組重量和距離為了分析各種碼的檢錯糾錯能力，引入碼組重量和距離的概念。碼組中包含1的個數稱為碼組的權，也稱碼組的漢明重量，用W表示。碼長n=k+rk個信息位r個監督位兩個不同的碼組，其對應碼位碼元不同的個數，稱為漢明距離，用d表示。例：C1＝{11001100}和C2={10010111}重量分別為W1＝4，W2＝5；它們的距離為d(c1,c2)=5。第10頁，課件共107頁，創作于2023年2月

在某種編碼中，各碼組間距離的最小值稱為最小碼距，用d0表示。最小碼距的大小直接關系著這種編碼的檢錯和糾錯能力，它是衡量各種碼抗干擾能力大小的標準。碼組的最小距離越大，抗干擾能力越強，這個結論具有普遍性。最小距離與檢錯和糾錯能力之間滿足如下關系：設碼組能檢錯個數為e，則有設碼組能糾錯個數為t，則有若碼組能檢錯個數為e，又能糾錯t個，則有

對任何糾錯編碼都適用。第11頁，課件共107頁，創作于2023年2月三、編碼效率對于分組碼（n,k），編碼效率定義為信息位在碼字中所占的比重，按下式計算：在信道中傳送n個單位的時間內，傳輸信息位占k個單位的時間。因此，編碼效率可看成是信道傳送信息碼元的利用率。

編碼效率是衡量碼性能的一個重要參量。但不難看出，編碼效率與抗干擾能力這兩個參數是相互矛盾的。編碼的主要任務就是如何找到一種方法，在滿足一定編碼效率的前提下，使抗干擾能力盡可能大。第12頁，課件共107頁，創作于2023年2月四、線性分組碼1、基本概念線性分組碼的性質：含有全零碼字。任意兩個許用碼字之和仍是一個許用碼字。（封閉性）最小碼距d0等于非零碼字的最小重量即d0=wmin

（由此性質可以方便的確定出線性分組碼的最小碼距，進而明確其糾錯能力。）可用線性方程組表述碼的規律性建立在代數學群論基礎上，各許用碼的集合構成代數學中的群，又稱為群碼。在群中只有一種運算，就是模2和。第13頁，課件共107頁，創作于2023年2月如：碼長為5的偶監督碼2、最簡單的線性分組碼—奇偶檢驗碼序碼字序碼字號信息碼元監督元號信息碼元監督元a4a3a2a1a0a4a3a2a1a0000000810001100011910010200101101010030011011101114010011211000501010131101160110014111017011111511110

第14頁，課件共107頁，創作于2023年2月

偶監督碼編碼器a4a3a2a1+信息組a0a1a2a3a4碼字第15頁，課件共107頁，創作于2023年2月偶監督碼的檢錯電路b3b0b1b2b4+接收碼組BS檢錯信號這里S稱為校正子，上式也稱伴隨式。第16頁，課件共107頁，創作于2023年2月例：一數據序列：{11100

10111

01101

10001

10101}試對其進行（6，5）偶校驗編碼，寫出碼序列并分析其抗干擾能力解：（6，5）,將數據序列每5碼元分組，并作：的運算可得出編碼數據序列：{111001∣101110∣011011∣100010∣101011}只能檢測出奇數個錯誤，不能發現偶數個錯誤，也不能糾錯。用以下方法改進。∣∣∣

∣第17頁，課件共107頁，創作于2023年2月水平垂直奇偶校驗碼：

又稱行列監督碼或二維奇偶監督碼。特點：對水平方向和垂直方向的碼元同時實施奇偶監督。110010100000100001101001111000011100111000001010101010111000111100行列監督碼第18頁，課件共107頁，創作于2023年2月把接收碼R與發送碼C的差稱為錯誤圖樣,用E表示：E=C-R（模M）如：八進制M=8，C=(0254752

),R=(0154754)則：E=(010006）

3、錯誤圖樣E=C⊕R→C=R⊕E,只要設法估計出差錯圖樣，就可以由接收碼估計出發送碼。這就是譯碼的概念。M=2,二進制碼，則為異或運算，可以寫為E=C⊕R。E中的某一位值為1，表示接收碼在該位出了錯。第19頁，課件共107頁，創作于2023年2月4、矢量空間和碼空間

長度為n的碼字看作一個n維矢量，又叫碼字矢量，所以可以從矢量空間的角度來分析和研究分組編碼。①矢量空間的定義：第20頁，課件共107頁，創作于2023年2月②矢量（碼字）的運算法則③線性相關和線性無關第21頁，課件共107頁，創作于2023年2月④矢量空間的基底⑤n維矢量空間是由n個基底張成的一維空間是一條直線。一個基底（不是唯一的）。如x=5是其一個基底。由x=5向兩邊延伸就張成了一條直線。第22頁，課件共107頁，創作于2023年2月二維空間是一個平面。兩個基底（不是唯一的）。如（0,1)和(1,0)是其兩個基底。這兩個基底的所有線性組合構成了平面，或者說張成了二維空間三維空間有三個基底如（1,0,0),(0,1,0),(0,0,1)這三個基底的所有線性組合張成了三維空間自然基底：矢量中的元素包含一個1，其它為0的那組基底。如三維空間的基底（1,0,0),(0,1,0),(0,0,1)。在線性無關的前提下，任意縮放或旋轉后仍為基底，如(0,0,2),(0,2,0),(0,0,2)第23頁，課件共107頁，創作于2023年2月⑥子空間第24頁，課件共107頁，創作于2023年2月總結:重數---構成矢量的元素的個數

維數---張成矢量空間的基底的個數⑦矢量空間的正交第25頁，課件共107頁，創作于2023年2月⑧分組碼的碼集（n,k)碼信息長度為k,信息序列的個數為2k。碼字長度為n，n維n重的矢量空間Vn中矢量的總數為2n。其中的2k個為碼字，其余2n-2k個是禁用碼組。若接收到了禁用碼組說明在傳輸過程中出了差錯。一般地，碼集不一定是Vn的子空間。但對于線性分組碼而言，碼集則一定是它的一個子空間（線性分組碼包含了所有的線性組合，構成一個子空間）。第26頁，課件共107頁，創作于2023年2月⑨分組編碼的數學概念從2n組合中，選擇2k個作為碼字構成碼集。或說，從n維n重的矢量空間Vn中選擇一個k維n重的子空間作為碼空間。確定k維k重的信息空間到k維n重的子空間的映射方法，就是編碼。不同的k維n重的子空間構成不同的碼。即使是同一個k維n重的子空間，映射的方法不同，也是不同的碼。第27頁，課件共107頁，創作于2023年2月5、線性分組碼的生成矩陣和校驗矩陣

①生成矩陣第28頁，課件共107頁，創作于2023年2月用矩陣運算來表示上述組合運算，將k個基底排列成矩陣G:

碼空間中的碼字是由信息組和矩陣G相乘得到的，把G叫做線性分組碼的生成矩陣

第29頁，課件共107頁，創作于2023年2月②系統形式的生成矩陣線性空間的底不是唯一的→碼空間的生成矩陣G也不是唯一的。通過線性組合運算可以將G變換成如下形式：k*k單位矩陣P:k*(n-k)的矩陣形式第30頁，課件共107頁，創作于2023年2月

碼字的前k位就是信息組的各信息位，而其余的n-k位就是冗余位（或監督位）。這種碼叫系統碼，相應的生成矩陣叫系統形式的生成矩陣。

將非系統形式的生成矩陣，通過線性組合運算變換成系統形式的生成矩陣，該過程叫做系統化。

顯然，系統化只是改變映射關系，碼空間不變。第31頁，課件共107頁，創作于2023年2月③校驗矩陣（監督矩陣）對偶空間和對偶碼K個n重的基底張成k維n重的碼空間C即(n,k)碼，一定存在n-k個正交矢量作為基底，構成其生成矩陣H，張成C的對偶空間D,即(n,n-k)碼，稱后者為前者的對偶碼（互為對偶碼）。對偶碼(n,n-k)的生成矩陣H是(n,k)碼的校驗矩陣，這是因為，第32頁，課件共107頁，創作于2023年2月釋：碼空間C與D正交，C中的任一碼子正交與D中的任一碼字，而H是D的生成矩陣（D中n-k個基底）④如何求檢驗矩陣H?第33頁，課件共107頁，創作于2023年2月（1）計算碼集C,列出信息組與碼字的映射關系（2）系統化處理后，計算碼集，列出映射關系（3）計算系統碼的校驗矩陣H。若收碼為100110，檢驗是否是碼字。（4）據系統碼的生成矩陣，畫出編碼電原理圖例6-2：(6,3)碼的生成矩陣為：解：（1）求出每一個碼字第34頁，課件共107頁，創作于2023年2月

信息組碼字0000→0000001001→0111012010→1100013011→1011004100→

111010

5101→1001116110→

0010117111→010110第35頁，課件共107頁，創作于2023年2月（2）正交化處理

信息組碼字0000→0000001001→0010112010→0101103011→0111014100→

100111

5101→1011006110→

1100017111→111010第36頁，課件共107頁，創作于2023年2月（3）校驗矩陣（4）編碼的電原理圖（據輸入與輸出的關系）第37頁，課件共107頁，創作于2023年2月第38頁，課件共107頁，創作于2023年2月6、伴隨式和標準陣列譯碼第39頁，課件共107頁，創作于2023年2月第40頁，課件共107頁，創作于2023年2月選擇哪一個？

第41頁，課件共107頁，創作于2023年2月作業講評1、3.33.6一定要畫出信道模型，判斷對稱性。2、3.8Ps/N0=45.5或Ps/（N0/2）=45.5皆可3、3.10dB數換算成倍數4、4.1計算平均失真=ε。不是2ε5、5.1唯一可譯碼：C1C2?C3C6。C4?6、5.55.85.10。霍夫曼編碼讀碼一定要仔細。

5.10:a4

101,a51000,a61001第42頁，課件共107頁，創作于2023年2月測驗：

某(n,k)線性二元碼的碼集為C={C1=000000,C2=000111,C3=011001,C4=011110,C5=101011,C6=101100,C7=110010,C8=110101}求n,k為何值？構造此碼的生成矩陣G.對G進行系統化，重新編碼。第43頁，課件共107頁，創作于2023年2月2k=8,-->k=3.n=6G=[00111;011001;101011]Gs=[100011;010101;001111]第44頁，課件共107頁，創作于2023年2月復習矢量空間的基底、生成重數---構成矢量的元素的個數維數---張成矢量空間的基底的個數矢量空間的正交、對偶空間分組編碼的數學概念第45頁，課件共107頁，創作于2023年2月生成矩陣：第46頁，課件共107頁，創作于2023年2月校驗矩陣例6-2！！！！第47頁，課件共107頁，創作于2023年2月伴隨式和標準陣列譯碼編、譯碼過程：選擇重量最輕的那組差錯圖樣進行譯碼

理解最小距離譯碼Goon第48頁，課件共107頁，創作于2023年2月最佳譯碼（最大后驗概率譯碼）：在已知r的條件下找出可能性最大的發碼c作為譯碼估值，即令：這是一種通過經驗與歸納由收碼推測發碼的方法，是我們認為的最優譯碼算法。但在實際譯碼時，后驗概率的定量確定是很困難的。最大似然譯碼：在已知r的條件下使先驗概率最大的譯碼算法，即令：，p(r|c)為似然函數當發送碼的概率都相等以及接受碼的概率也都相等時，二者等效。根據貝葉斯公式可以建立先驗概率和后驗概率之間的關系：第49頁，課件共107頁，創作于2023年2月設每個碼字長為n，若接收碼字R與碼字C的距離為d(R,C)，則條件概率p(R│C)可表示為：最大化p(R│C)等價于最小化d(R,C)，所以使差錯概率最小的譯碼是使接收向量R與輸出碼字C’距離最小的譯碼。對于BSC信道，最大似然譯碼就是最小距離譯碼。（5）構造標準陣列譯碼表上述概率譯碼不能進行實時譯碼：

每收到一個碼字R,就要計算一次伴隨式S，然后求解方程組，得到2k個差錯圖樣，選擇重量輕者進行譯碼。第50頁，課件共107頁，創作于2023年2月為此，首先構造標準陣列譯碼表，事先將所有不同取值的伴隨式S所對應的差錯圖樣全部解出來，選擇最輕者與所有可能的發送碼字相加，得到所有可能的接收碼字。并將它們排列成表格，接收端只需要根據接收到的碼字查表即可譯碼。標準陣列的構造方法是：⑴選擇所有碼字構成陣列的第0行，通常將全零碼字c1作為第0行第1列元素。⑵選擇差錯圖案ei作為第0列，通常以無差錯圖案e1=(0…0)作為第0列第l行元素。⑶陣列中的i行j列元素為ei＋cj；i=l,2,…2r，j=l,2,…2k⑷對越小的i，ei選擇為越容易出現的差錯圖案

以（6,3）碼為例介紹：第51頁，課件共107頁，創作于2023年2月（6，3）碼：陪集首c1000000c2001110c3010011c4011101c5100101c6101011c7110110c8111000se1000000e1+c1000000e1+c2001110e1+c3e1+c4e1+c5e1+c6e1+c7e1+c8000e2000001e2+c1000001001e3000010e3+c1010e4000100e4+c1100e5001000e5+c1ei+cj010101110e6010000e6+c1011e7100000e7+c1101e8100010e8+c1100010101100110001111111000111001001010100011010111第52頁，課件共107頁，創作于2023年2月伴隨式S有23=8種組合，而差錯圖樣中代表無差錯的有一種，代表一個差錯的圖案有=6種，代表兩個差錯的圖案=15種。要把8個伴隨式對應到8個最輕的差錯圖樣，無疑應先選無差錯的圖案和6種一個差錯的圖樣。對于兩個差錯的圖樣，我們只能挑選其中的1個，至于挑選方法可有若干種，不是唯一的。先將ei=(000000)、(000001)、…(100000)解得對應的S；剩下的伴隨式（111）所對應的差錯圖案有2k=8個，其中(100010)、(001001)、(010100)并列重量最輕，任選其中一個比如(100010)。陪集首：在最小距離準則下最可能產生錯誤的集合標準陣列譯碼：根據最大似然譯碼思想，把2n個n重接收矢量劃分成2k個互不相交的子集D1D2…，在這2k個子集中使每個子集僅含有一個碼字，使得某個子集Di與某一ci一一對應。譯碼時，凡是落在Di這個子集中的接收矢量都被譯成ci.第53頁，課件共107頁，創作于2023年2月舉例：當收到碼組R=[111011]時，判斷是否碼字？解：查表：e=[010000]c=r⊕e=[101011]

7、完備碼

任何一個二元（n，k）線性分組碼都有2n-k個伴隨式，假如該碼的糾錯能力是t，則對于任何一個重量小于等于t的差錯圖案，都應有一個伴隨式與之對應，即伴隨式的數目滿足條件：上式稱作漢明限，任何一個糾t碼都應滿足上述條件。第54頁，課件共107頁，創作于2023年2月如果某二元（n，k）線性分組碼伴隨式數目恰好和不大于t個差錯的圖案數目相等，相當于在標準陣列中能將所有重量不大于t的差錯圖案選作陪集首而沒有一個陪集首的重量大于t，這時的校驗位得到最充分的利用。（1）完備碼：滿足方程的二元(n，k)線性分組碼（2）完備碼特性：圍繞2k個碼字、漢明距離為t的所有球都是不相交的，每一個接收碼字都落在這些球中之一，因此接收碼離發送碼的距離至多為t，這時所有重量≤t的差錯圖案都能用最佳（最小距離）譯碼器得到糾正，而所有重量≥t＋1的差錯圖案都不能糾正。（3）幾種完備碼：漢明碼：t=1（d=3）的二進制完備碼由上述方程得：m＝3，→（7，4）m＝4，→（15，11）m＝5，→（31，26）m＝6，→（63，57）m＝7，→（127，120）m＝8，→（255，247）第55頁，課件共107頁，創作于2023年2月漢明碼的構造:漢明碼的校驗矩陣H具有特殊的性質(二進制時):（n，k）碼的H：r×nr個碼元所能組成的列矢量總數是2r－l，（全零矢量除外）恰好和校驗矩陣的列數n=2m－1相等。只要排列所有列，通過列置換將矩陣H轉換成系統形式，就可以進一步得到相應的生成矩陣G。例：（7，4）漢明碼.相應的伴隨式計算方程：第56頁，課件共107頁，創作于2023年2月另一種完備碼：（高萊）戈雷碼，t=3的（23，12）二進制完備碼采用伴隨式計算的一種糾錯譯碼電路實現形式如圖:滿足方程：第57頁，課件共107頁，創作于2023年2月總復習（一）1、按發出符號之間的關系來分，信源可以分為（）和（）2、連續信源的熵是（），不再具有熵的物理含義。3、對于有記憶離散序列信源，需引入（）描述信源發出的符號序列內各個符號之間的統計關聯特性3、連續信源X,平均功率被限定為P時，符合（）分布才具有最大熵，最大熵是（）。4、數據處理過程中信息具有（）。5、信源冗余度產生的原因包括（）和（）。6、單符號連續信道的信道容量取決于（）。7、香農信息極限的含義是（）。8、對于無失真信源編碼，平均碼長越小，說明壓縮效率（）。第58頁，課件共107頁，創作于2023年2月9、對于限失真信源編碼，保證D的前提下，盡量減少（）。10、立即碼指的是（）。11、算術編碼是（）分組碼。12、游程編碼是（）失真信源編碼。13、線性分組碼的（）就是該碼空間的對偶空間的生成矩陣。14、若（n，k）線性分組碼為MDC碼，那么它的最小碼距為（）。15、完備碼的特點是（）。16、卷積碼的自由距離決定了其（）。第59頁，課件共107頁，創作于2023年2月（）1、信息是指各個事物運動的狀態及狀態變化的方式。（）2、信息就是信息，既不是物質也不是能量。（）3、馬爾可夫信源是離散無記憶信源。（）4、不可約的馬爾可夫鏈一定是遍歷的。（）5、單符號連續信源的絕對熵為無窮大。（）6、序列信源的極限熵是這樣定義的：H(X)=H(XL|X1,X2,…,XL-1)。（）7、平均互信息量I(X;Y)是接收端所獲取的關于發送端信源X的信息量。（）8、信源X,經過處理后，輸出為Y，H(Y)小于H(X),說明信息不增。（）9、如果一個消息包含的符號比表達這個消息所需要的符號多，那么該消息存在冗余度。（）10、有噪無損離散信道的輸入為X,輸出為Y，那么其信道容量Ｃ＝ｍａｘＨ（Ｙ）。第60頁，課件共107頁，創作于2023年2月（）11、非高斯噪聲信道的信道容量比高斯噪聲信道的信道容量小。（）12、信息率失真函數具有單調遞減性。（）13、異前綴碼不能及時可譯。（）14、用碼樹構造的一定是及時碼。（）15、香農編碼壓縮了符號相關造成的冗余。（）16、有失真信源編碼指的是保真度準則下的信源編碼。（）17、變長無失真信源編碼比定長編碼的編碼效率高。（）18、香農編碼是最佳編碼。（）19、卷積、交織都可以達到差錯隨機化的目的。。（）20、卷積碼的序列距離決定了其檢錯和糾錯能力。第61頁，課件共107頁，創作于2023年2月復習

第三節線性分組碼四、線性分組碼1、基本概念2、最簡單的線性分組碼—奇偶檢驗碼3、錯誤圖樣4、矢量空間和碼空間5、線性分組碼的生成矩陣和校驗矩陣6、伴隨式和標準陣列譯碼7、完備碼第62頁，課件共107頁，創作于2023年2月8、循環碼——由循環移位特性而界定的一類線性分組碼設n位碼組：c=(c0,c1,…,cn-2,cn-1),ci∈{0,1}則右移一位：c(1)

=(cn-1,c0,c1,…,cn-2),右移i位：c(i)

=(cn-i,cn+1-i,…,cn-1,c0,c1,…,cn-1-i),

i=1~n第63頁，課件共107頁，創作于2023年2月（1）循環碼的多項式描述1.碼字的多項式表示：（n，k）碼例:c(x)=c0+c1x+…+cn-1xn-1,(n-1次)(1)一般形式f(x)=f0+f1x+…+fnxn,(n次)(2)性質①多項式次數②零次多項式——f(x)=f0③零多項式——f(x)=0④兩多項式四則運算——同一般多項式第64頁，課件共107頁，創作于2023年2月（1）循環碼的多項式描述(續)1.碼字的多項式表示(3)模運算——與整數模運算相同如：3=1(mod2)，x2+1=1(modx2)一般式：如有h(x)=q(x)f(x)+r(x)則有h(x)=r(x)(modf(x))對于循環碼，有：

c(i)(x)

=c(x)xi

(modxn+1)

如：c=(c0,c1,…,cn-2,cn-1),ci∈{0,1}

碼多項式為：c(x)=c0+c1x+…+cn-1xn-1,

右移一位：c(1)(x)=c(x).x(modxn+1)

=c0x+c1x2+…+cn-2xn-1+cn-1xn

(modxn+1)

第65頁，課件共107頁，創作于2023年2月相應的碼字為：

c(1)

=(cn-1,c0,c1,…,cn-2)=c0x+c1x2+…+cn-2xn-1+cn-1xn

(modxn+1)

=c0x+c1x2+…+cn-2xn-1-cn-1

=cn-1+c0x+c1x2+…+cn-2xn-1

同理：右移2位：c(2)(x)=c(x).x2

(modxn+1)

=c0x2+c1x3+…+cn-3xn-1+cn-2xn+cn-1xn+1

(modxn+1)

=c0x2+c1x3+…+cn-3xn-1-cn-2-cn-1x=cn-2+cn-1x+c0x2+c1x3+…+cn-3xn-1相應的碼字為：

c(2)

=(cn-2,cn-1,c0,c1,…,cn-3)第66頁，課件共107頁，創作于2023年2月結論：c(i)(x)

=c(x)xi

(modxn+1)n位碼字的循環右移i位等價于相應的碼多項式乘以xi后取xn+1的模剩余2.定義——若一個線性分組碼的任意一個碼字c，都是另一個碼字c’的循環移位，則稱為循環碼3.生成多項式g(x)(1)定義(n,k)循環碼c(x)中存在著唯一的一個生成多項式g(x)，其最高次為r=n-k，常數項為1，且是xn+1的一個因子g(x)=xr

+gr-1xr-1+…+g1x+1(2)性質：①任一碼多項式必是g(x)的倍式：c(x)=a(x)g(x)②任一次數≤k-1的多項式a(x)與g(x)相乘，必為碼多項式第67頁，課件共107頁，創作于2023年2月（2）循環碼的構造方法

對xn+1作因式分解，求出所有的最小多項式，從而求出n-k次的因式作為生成多項式g(x)。用生成多項式g(x)乘以信息多項式m(x),得到碼多項式c(x)。例題：研究構造一個長度n=7的循環碼的構造方法。解：對x7+1作因式分解(二元域）：

x7+1=（x+1）（x3+

x2+1）（x3+

x

+1）驗證：（x+1）（x3+

x2+1）（x3+

x

+1）=x7+2x6+2x5+4x4+2x2+2

x

+1mod(2)=x7+1第68頁，課件共107頁，創作于2023年2月共有4種因式：1次----x+13次----x3+

x2+1和x3+

x

+14次----x4+x2+

x

+1和x4+x3+x2+16次----x6+x5+x4+x3+x2+

x

+1選擇生成多項式：g(x)=x+1，n-k=1,k=6→(7,6)循環碼g(x)=x3+

x2+1或x3+

x

+1→(7,4)循環碼g(x)=x4+x2+

x

+1或x4+x3+x2+1→(7,3)循環碼g(x)=x6+x5+x4+x3+x2+

x

+1→(7,1)循環碼第69頁，課件共107頁，創作于2023年2月以g(x)=x4+x3+x2+1為例構造(7,3)循環碼：m1=(000),m(x)=0,c(x)=

m(x)g(x)=0→c=(0000000)m2

=(001),m(x)=1,c(x)=

m(x)g(x)=g(x)

→c=(0011101)m3=(010),m(x)=x,c(x)=

m(x)g(x)=x5+x4+x3+x

→c=(0111010)m4=(011),m(x)=x+1,c(x)=

m(x)g(x)=x5+x2+x+1

→c=(0100111)m5=(100),m(x)=x2,c(x)=

m(x)g(x)=x6+x5+x4+x2

→c=(1110100)m6=(101),m(x)=x2+1,c(x)=

m(x)g(x)=x6+x5+x3+1→c=(1101001)m7=(110),m(x)=x2+x,c(x)=

m(x)g(x)=x6+x3+x2+x

→c=(1001110)m8=(111),m(x)=x2+x+1,c(x)=

m(x)g(x)=x6+x4+x+1→c=(0111010)第70頁，課件共107頁，創作于2023年2月（3）循環碼的校驗多項式生成多項式g(x)是xn+1的一個因子，即：xn+1=g(x).h(x)那么，對于任意碼多項式c(x)有：c(x)h(x)=m(x)g(x)h(x)=m(x)(xn+1)=0mod(xn+1)。定義h(x)=(xn+1)/g(x)=h0+h1x+…+hk-1xk-1+hkxk為循環碼的校驗多項式。正如普通線性分組碼的生成矩陣G和校驗矩陣H的關系，(n,k)循環碼的校驗多項式h(x)是(n,n-k)對偶碼的生成多項式。第71頁，課件共107頁，創作于2023年2月

=[mk-1mk-2…m0] =[mk-1mk-2…m0]

其中，g(x)=gn-kxn-k+…+g1

x+g0

（4）循環碼的生成矩陣和校驗矩陣第72頁，課件共107頁，創作于2023年2月將矩陣中的多項式改寫成對應的n重矢量形式，得矢量的矩陣表達式：

C=(cn-1,…c1,c0)=[mk-1,…m1,m0]=mG這里，我們定義(k

n)矩陣G為循環碼的生成矩陣第73頁，課件共107頁，創作于2023年2月循環碼的(n-k)n階的校驗矩陣可寫為：H= 循環碼生成矩陣G與校驗矩陣的乘積一定是的零陣。GHT＝0

第74頁，課件共107頁，創作于2023年2月(5)系統循環碼設信息多項式m(x)=mk-1xk-1+…+m1x+m0則系統循環碼c(x)=xn-km(x)+r(x),r(x)---監督式∵c(x)=a(x)g(x)=0modg(x)∴r(x)=xn-km(x)modg(x)構碼步驟：①升幕：信息多項式乘以xn-k→xn-km(x),即右移n-k位②求余：r(x)=xn-k

m(x)modg(x)③拼合：c(x)=xn-km(x)+r(x)——循環碼多項式第75頁，課件共107頁，創作于2023年2月例6-6(7,3)循環碼g(x)=x4+x3+x2+1,構造系統碼以m=(011),m(x)=x+1為例：升冪：xn-km(x)=x5+x4余式：r(x)=x5+x4mod(x4+x3+x2+1)=x3+x拼合：c(x)=xn-km(x)+r(x)=x5+x4+x3+x即：c=(0111010)同理：可求出其它信息序列m=(xxx)對應的編碼輸出第76頁，課件共107頁，創作于2023年2月（6）循環碼編碼電路非系統碼編碼電路——乘法編碼電路c(x)=m(x)·

g(x)如：(7,4)循環碼g(x)=x3+x2+1,設m(x)=x3+x，低冪次在前可用下圖實現編碼：s2s1s0m(x)g0=1c(x)g2=1g3=1節拍ms2s1s0c123401010000001000100100567000101010001111關系s2′=m,s1′=s2,s0′=s1,c=m+s1+

s0,“′”——下一個值m=0101(升冪)，

c=0100111第77頁，課件共107頁，創作于2023年2月2.系統循環碼編碼—除法編碼電路如：(7.4)系統循環碼,g(x)=x3+x2+1,設：m(x)=x3+x+G1p0p1p2g0=1G2m(x)(m3m2

m1

m0000)c(x)(c6c5…c0)g2=1g3=1節拍mp0p1p2cG1G2關系12341010000101111011101010101010p

0=m+p2p

1=p0p

2=p

0+p1567000100010001001010101p

0=0p

1=p0p

2=p1結論：m=1010，

c=1010001第78頁，課件共107頁，創作于2023年2月9、BCH碼和RS碼

BCH碼是糾錯能力可控的糾隨機差錯碼，是循環碼的子類。該碼有嚴格的代數結構，生成多項式g(x)與最小距離d有密切關系，使設計者可以根據對d的要求，輕易地構造出具有預定糾錯能力的碼。BCH編、譯碼電路比較簡單，易于工程實現，在中、短碼長情況下的性能接近理論最佳值。因此BCH碼不僅在編碼理論上占有重要地位，而且也是實際使用最廣泛的碼之一Bose

ChandhariBCH

HocquenghemBCH碼最初是定義在GF(2)域上的二進制碼，后被推廣到多元域GF(q)上。第79頁，課件共107頁，創作于2023年2月（1）什么是GF域？對于任何質數p，存在一個有限域，域中含有p個元素；任何兩個元素的和、積仍在域中，且滿足交換率、結合率和分配率，稱此域為GF(p)域。如：二元域GF(2)={0,1)（2）GF域多項式如：二元域多項式

p(x)=x3+x2+1，x取值為0或1

二元域本原多項式：m次的二元域多項式，若滿足以下條件，稱為本原多項式。既約（不能再因式分解）；能整除xn+1,n=2m-1

；不能整除xq+1,q<n第80頁，課件共107頁，創作于2023年2月（3）GF(pm)擴域如：二元擴域GF(2m)，可以用二元域上的本原多項式來產生。以p(x)=x3+x+1為例，m=3,GF(23)={0、1、

1、

2、

3、

4、

5、

6}。其中，

為本原元，它是本原多項式在擴域上的的根。域不同則多項式的分解亦不同，在一個域的既約不等于在另一個域的既約。如：（x4-1）在不同域上的因式分解在實數域的分解：x4-1=

(x2+1)(x+1)(x-1)在復數域的分解：x4-1=

(x+i)(x-i)(x+1)(x-1)在二元域的分解：x4-1=x4+1=(x+1)(x+1)(x+1)(x+1)本原多項式（既約的）在GF(2)上不能再分解，但在二元擴域GF(2m)未必就不能再分解，因GF(2m)是多項式域，系數取值于{0、1、

1、

2、…、}。第81頁，課件共107頁，創作于2023年2月（4）二元域本原多項式在GF(2m)擴域上的根

則：

3=

+1；

4=

3=

(

+1)=

2+

;

5=

3

2=(

+1)(

2+

)=

2+

+1

；

6=

2+1;8個元素都可以表示為的最高冪次為m-1(這里m=3)的多項式

此外，

2和

4是p(x)=x3+x+1

的另外兩個根：p(

2)=

6+

2

+1=2+1+2+1=0;p(

4)=

12+

4

+1=6

6+

4+1=24+22+2=0;據近世代數理論，冪次為m的多項式，必有m個根。如：本原多項式p(x)=x3+x+1產生的二元擴域為GF(23)，本原元

為其中的一個根，p(

)=

3+

+1=0而

、

3、

5不是它的根；當然0和1也不是它的根。第82頁，課件共107頁，創作于2023年2月

、

2、

4是p(x)=x3+x+1

在擴域上的三個根，可作如下因式分解：x3+x+1

=(x+)(x+

2)(x+

4)

(5)

xn+1

在其本原多項式定義的擴域上的根n個根;以n=7為例，x7+1在其本原多項式p(x)=x3+x+1定義的擴域GF(23)={0,1,

,

2,

3,

4,

5,

6

}有7個根。

普通的循環碼(n,k)，其生成多項式g(x)是xn+1在二元域上的因式；而BCH碼的生成多項式g(x)則是xn+1在二元擴域上的因式。所以，關心xn+1

在其本原多項式定義的擴域上的根。除了0以外,1,

,

2,

3,

4,

5,

6都是x7+1的根。第83頁，課件共107頁，創作于2023年2月實際上x7+1的7個根1,

,

2,

3,

4,

5,

6是其三個最小多項式在擴域上的根的集合。x7+1=(x+1)(x3+x+1)=(x3+x2+1)(二元域上）其中：x+1在擴域上的根為1

x3+x+1在擴域上的3個根為

,

2,

4x3+x2

+1在擴域上的3個根為

3,

5,

6每一個根都對應于一個最小多項式

(6)

BCH碼用xn+1

在其本原多項式定義的擴域GF(2m)上的2t個連續冪次的根

,

2,…

,

2t所對應的最小多項式mi(x)的最小公倍式作為生成多項式生成的循環碼。(t為糾錯能力)糾錯能力可控第84頁，課件共107頁，創作于2023年2月總結：本原BCH碼構造法①由關系式n=2m-1算出m，查表，找到一個m次本原多項式P(x)，產生一個GF(2m)擴域。②在GF(2m)上找一個本原元

，分別計算2t個連續冪次根

、

2、…、

2t所對應的GF(2)域上的最小多項式m1(x)、m2(x)…m2t(x)。m

8時連續冪次根

i所對應的最小多項式見表。③計算這些最小多項式的最小公倍式，得到生成多項式g(x)g(x)=LCM[m1(x)m2(x)…m2t(x)] ④由關系式C(x)=m(x)g(x)求BCH碼字。例題6-8設計一個碼長n=7的二元本原BCH碼，在不同糾錯能力下的生成多項式是怎樣的？第85頁，課件共107頁，創作于2023年2月解：①n=7m=3查表：m=13(8進制表示，即001011）；本原多項式為p(x)=x3+x+1②dmin≤n=2m-1→t≤(dmin-)/2=2m-1-1=3分別計算2t個連續冪次的根對應的最小多項式：t=1,2t=2;2個連續冪次的根

,

2

→(x3+x+1),

2→(x3+x+1)∴g(x)=x3+x+1生成(7,4)碼。t=2,2t=4;4個連續冪次的根

,

2,

3,

4

,

2,

4→(x3+x+1),

3→(x3+x2+1)∴g(x)=(x3+x+1)(x3+x2+1)=x6+x5

+x4+x3

+x2+x+1,(7,1)碼。t=3，結果同上第86頁，課件共107頁，創作于2023年2月

(6)

RS碼---多進制BCH碼RS---Reed-Solomon里德-索洛蒙碼，BCH碼最重要的一個子類符號集由本原多項式產生的擴域GF(2m)中的元素構成。

BCH碼二元域：GF(2)={0,1}本原多項式：如p(x)=(x3+x+1)擴域：GF(2m)={0,1,

,

2,….}符號集：{0，1}多項式：g(x)=gn-k

xn-k+….+g1

x+g0

m(x)=mk-1

xk-1+….+m1

x+m0

c(x)=cn-1

xn-1+….+c1

x+c0

各多項式以0或1為系數g(x)---2t個連續冪次的根對應的最小多項式的最小公倍式。

RS碼二元域：GF(2)={0,1}本原多項式：如p(x)=(x3+x+1)擴域：GF(2m)={0,1,

,

2,….}符號集：{0,1,

,

2,….

q-2}多項式：g(x)=gn-k

xn-k+….+g1

x+g0

m(x)=mk-1

xk-1+….+m1

x+m0

c(x)=cn-1

xn-1+….+c1

x+c0

各多項式以0,1,

,

2,….

q-2為系數g(x)---2t個連續冪次的根。g(x)=(x-

)(x-

2)…(x-

2t)第87頁，課件共107頁，創作于2023年2月總復習（二）信息、消息、信號的定義是什么？三者的關系是什么？什么樣的馬爾可夫鏈是遍歷的？簡述離散信源的最大熵定理。簡述信息率失真函數的物理意義。敘述變長信源編碼定理。惟一可譯碼存在的充要條件是什么？什么是差錯圖樣？有哪些差錯圖樣類型？什么是本原多項式？對于信道編碼，有哪兩種譯碼算法？簡述之。為什么說BSC信道的最小距離譯碼就是最大似然譯碼？什么是完備嗎？舉出兩種完備嗎的例子。寫出卷積碼的解析表達式。說明為什么稱之為卷積碼？第88頁，課件共107頁，創作于2023年2月設在一只布袋中裝有100個大小相同的乒乓球，（1）若紅色球和白色球各50個，從中隨機取出一個球，問猜測其顏色需要的信息量是多少？（2）若紅色球99個，白色球1個，從中隨機取出一個球，猜測其顏色需要的信息量又是多少？某信道為強對稱信道（即均勻信道）輸入符號和輸出符號的個數均為m，正確的傳輸概率為1—ε,錯誤概率為ε被對稱的均勻分給m—1個輸出符號，試寫出轉移概率矩陣及其信道容量的表達式。第89頁，課件共107頁，創作于2023年2月一個平均功率受限的連續信道，其通頻帶為1MHZ,信道上存在白色高斯噪聲。（1）已知信道上的信號和噪聲的平均功率比值為10，求該信道的信道容量。（2）信道上的信號和噪聲的平均功率比值降為5，要達到相同的信道容量，信道的通頻帶應為多大？（3）若信道通頻帶減少為0.5MHZ,信道上的信號和噪聲的平均功率比值應為多大？（4）。。。。設有離散無記憶信源P(X)={0.37,0.25,0.18,0.10,0.07,0.03},（1）、求該信源的符號熵。（2）、用哈夫曼編碼編成二元變長碼，計算其編碼效率。（3）、要求其譯碼錯誤小于10采用定長二元碼要達到（2）中的哈夫曼編碼效率，問需要多少個信源符號連在一起編？第90頁，課件共107頁，創作于2023年2月卷積碼——convolutionalcode發展1955年，埃里亞斯(Elias)提出卷積碼1957年，伍成克拉夫特(Wozencraft)提出序列譯碼1963年，梅西(Massey)提出門限譯碼1967年，維特比(Viterbi)提出最大似然譯碼優點——簡單、性能好主要應用——FEC（前向糾錯）系統，糾錯6.4卷積碼

6.4.1卷積碼概述第91頁，課件共107頁，創作于2023年2月特點輸出的n個碼元中，每個碼元不僅與本段的k比特信息碼元有關，而且還與前m段的信息碼元有關記作——(n,k,m)n、k較小，m較大(m＜10)參數碼率——k/n記憶長度m——有效工作的移存器段數編碼約束度N=m+1——相互關聯的碼段個數編碼約束長度Nn——相互關聯的碼元個數第92頁，課件共107頁，創作于2023年2月編碼輸出每次輸入k比特1k…1k…1k…1k…………

1…k…2k3kNk……………

…………

12nNk級移存器n個模2加法器每輸入k比特旋轉1周輸出n比特6.4.2卷積碼編碼原理第93頁，課件共107頁，創作于2023年2月特點工作流程——按段工作：對每段k比特信息碼元輸入，產生一段n比特輸出連環碼——每一碼段與前后碼段皆有關，環環相扣卷積碼——能以離散卷積表達式表示線性非分組碼分析方法解析法——離散卷積法、生成矩陣法、碼多項式法圖解法——狀態圖法、樹圖法、網格圖法6.4.2卷積碼編碼原理(續)第94頁，課件共107頁，創作于2023年2月每輸入1比特，編碼器輸出3比特c1c2c3輸入為1101時，編碼器的工作狀態表如下123b3b1輸入b2編碼輸出c2c1c3b11101000b3b200011110011000c1c2c3111110010100001011000狀態abdcbca卷積碼編碼器實例——（3,1,2）碼第95頁，課件共107頁，創作于2023年2月000111001110011100010101000111001110011100010101c1c2c3000100111011001101110010c1c2c3111000001110c1c2c3abcdabcdabcdabcd上半部下半部信息位 1 1 0 1ba起點信息位000111c1c2c310aabcdabcdcdab↑0↓1↓1↑0↑0↓16.4.3卷積碼的分析方法1.樹圖法——[例](3,1,2)卷積碼樹圖(0走上，1走下)狀態b3b2abcd00011011第96頁，課件共107頁，創作于2023年2月2.狀態表和狀態圖123b3b1輸入b2編碼輸出c2c1c3b1/1101/111adc0/0001/1000/0010/0100/0111/101當前狀態b3b2輸入

b1輸