1、（1）信道編碼目的信道編碼目的：提高通信系統傳輸的可靠性；：提高通信系統傳輸的可靠性；（2）目標目標：尋找具體構造編碼的理論與方法；：尋找具體構造編碼的理論與方法； 只要當實際傳信率只要當實際傳信率RC（信道容量），無差錯的信道編、（信道容量），無差錯的信道編、譯碼是存在的。譯碼是存在的。（3）信道編碼原理信道編碼原理：根據一定的規律在待發送的信息碼元中：根據一定的規律在待發送的信息碼元中人為的加入一定的多余碼元人為的加入一定的多余碼元，以保證在傳輸中，發送碼元的，以保證在傳輸中，發送碼元的可靠性。可靠性。（4）信道編碼任務信道編碼任務：就是構造出以最小冗余度代價換取最大：就是構造出以最小冗余

2、度代價換取最大抗干擾性能的好的碼字抗干擾性能的好的碼字第六章第六章 信道編碼信道編碼6.1 .1 概述概述信道編碼又稱糾錯編碼，是提高數字傳輸可靠性的一種技術信道編碼又稱糾錯編碼，是提高數字傳輸可靠性的一種技術一一. .有擾離散信道的信道編碼定理有擾離散信道的信道編碼定理( (香農第二定理香農第二定理) ) 在信息傳輸速率小于信道容量的條件下，可通過增加代碼組在信息傳輸速率小于信道容量的條件下，可通過增加代碼組長度長度m m的編碼方法，使得接收端恢復消息的誤碼率小于任意給的編碼方法，使得接收端恢復消息的誤碼率小于任意給定的小數定的小數。反之，若信息傳輸速率大于信道容量時，則誤碼。反之，若信息傳

3、輸速率大于信道容量時，則誤碼率為一固定值，即使增加代碼組長度率為一固定值，即使增加代碼組長度m m也不能使誤碼率任意小也不能使誤碼率任意小 該定理也就是說，只要該定理也就是說，只要 R C R k。而且一般來說，碼的冗余度越。而且一般來說，碼的冗余度越大，檢、糾錯能力就越強；大，檢、糾錯能力就越強；(2)任何一種檢錯或糾錯碼都不可能檢出或糾正所有的錯誤。事任何一種檢錯或糾錯碼都不可能檢出或糾正所有的錯誤。事實上，如果碼中至少有兩個碼字實上，如果碼中至少有兩個碼字v1和和v2。則錯誤圖樣。則錯誤圖樣e=v1+v2，就不能夠被檢出或糾正；就不能夠被檢出或糾正；(3)如果錯誤圖樣集如果錯誤圖樣集ei

4、,i=1,2,.,l使得每個碼字使得每個碼字vj(j=1,2,m)變成變成的接收字集的接收字集 eivj中不包含碼字中不包含碼字vj，則這個碼就可以檢出所，則這個碼就可以檢出所有的錯誤圖樣有的錯誤圖樣ei；(4)如果錯誤圖樣集如果錯誤圖樣集ei,i=1,2,.,l使得任一對碼字使得任一對碼字vj，vk變成的接變成的接收字集收字集 eivj和和 eivk之間無公共的接收字，而且不含任之間無公共的接收字，而且不含任一碼字，那么就只需要把一碼字，那么就只需要把eivj判為判為vj；(5)如果錯誤圖樣集可以分為無公共部分的集如果錯誤圖樣集可以分為無公共部分的集ei,i=1,2,.,l 和集和集ei,i

5、=1,2,.,l，而且碼字集，而且碼字集vj,j=1,2,m對于對于ei,i=1,2,.,l 滿滿足第足第4點，則該碼可以糾正所有點，則該碼可以糾正所有ei，并且對集，并且對集ei,i=1,2,.,l有有如下的性質：如下的性質： 任一碼字任一碼字vj的相應接收字集的相應接收字集 eivj中都不含中都不含 eivr（rj）中的接收字以及中的接收字以及vr，則此碼可兼有糾正所有的錯誤圖樣，則此碼可兼有糾正所有的錯誤圖樣ei和和檢出所有的錯誤圖樣檢出所有的錯誤圖樣ei三、線性分組碼的檢、糾錯能力三、線性分組碼的檢、糾錯能力 最小距離最小距離dmin與碼率與碼率R是碼的兩個最主要參數，是碼的兩個最主要

6、參數，dmin表示了碼的表示了碼的糾錯能力。糾錯能力。用（用（n，k，d）表示距離為）表示距離為d，碼率，碼率Rkn的線性分組碼。的線性分組碼。糾錯碼的基本任務之一就是構造出糾錯碼的基本任務之一就是構造出R一定且一定且dmin盡可能大的碼，盡可能大的碼，或或dmin一定且一定且R盡可能大的碼。盡可能大的碼。檢測檢測e個錯誤，則要求最小碼距：個錯誤，則要求最小碼距： dmine1 編碼的最小碼距為編碼的最小碼距為dmin，則最多能檢出（，則最多能檢出（dmin-1）個錯誤。）個錯誤。e+1eC1(a)糾正糾正t個錯碼，則要求最小碼距為：個錯碼，則要求最小碼距為： dmin2t12t+11ttC1

7、C2糾正糾正t個錯碼，同時能檢測個錯碼，同時能檢測e(et)個錯碼，則要求最小個錯碼，則要求最小碼距為碼距為 dminet1, ete+t+11etC1C2定理：線性分組碼的最小距離等于碼中碼字的最小重量。定理：線性分組碼的最小距離等于碼中碼字的最小重量。定理：定理：(n，k，d)線性分組碼有最小距離線性分組碼有最小距離dmin的充要條件是的充要條件是 H矩陣中任意矩陣中任意d1列線性無關，存在列線性無關，存在d列線性相關。推列線性相關。推論：論：(n，k，d)線性分組碼的最小距離線性分組碼的最小距離 dminnk1。若系統碼的最小距離若系統碼的最小距離dminnk1，則稱此碼為極大最，則稱此

8、碼為極大最小距離可分碼，簡稱小距離可分碼，簡稱MDS碼。碼。 定理：設定理：設C C是個線性分組碼，是個線性分組碼，H H是它的校驗矩陣，那么是它的校驗矩陣，那么C C是可以糾正單個錯誤的是可以糾正單個錯誤的糾錯碼的充要條件是糾錯碼的充要條件是H H中沒有元素全為中沒有元素全為0 0的列矢量，且的列矢量，且H H的任意兩個列矢量都不的任意兩個列矢量都不相同相同定義：令定義：令H H是個二元是個二元r r(2(2r r-1)-1)矩陣，這個矩陣的列是矩陣，這個矩陣的列是V Vm(F(F2 2) )中按某種次序排列中按某種次序排列的的2 2r r-1-1個非零矢量。那么，定義為個非零矢量。那么，定

9、義為F F2 2上的上的n n2 2r r-1-1，k k2 2r r-1-r-1-r的線性分組碼的線性分組碼( (其其校驗矩陣為校驗矩陣為H)H)，就稱為長，就稱為長2 2r r-1-1的漢明碼的漢明碼 設線性碼的校驗矩陣設線性碼的校驗矩陣000111 1 10001110 1 01011100 1 10111000 1 01H 四四. .常用線性分組碼常用線性分組碼-漢明碼漢明碼 漢明最早提出的一類能糾正單個錯誤的糾錯碼漢明最早提出的一類能糾正單個錯誤的糾錯碼 如果接收矢量如果接收矢量r r(101000101)(101000101)，根據，根據s srHrHT T有有 s s(1100)

10、(1100)，即，即r r中第五位數出錯，經糾錯后中第五位數出錯，經糾錯后r r(101010101)(101010101) 如果接收矢量如果接收矢量r r(001000101),(001000101),根據根據s srHrHT T有有 s s(1101)(1101)，s s不等于不等于H H中任意一列，實際上該碼有兩個錯誤中任意一列，實際上該碼有兩個錯誤定理：二元定理：二元(2(2r r-1-1， 2 2r r-1-r)-1-r)漢明碼是能糾正所有單個錯誤的線性漢明碼是能糾正所有單個錯誤的線性碼，而且是校驗位數為碼，而且是校驗位數為r r的所有二元線性碼中編碼效率最高的碼的所有二元線性碼中編

11、碼效率最高的碼, ,它的最小重量為它的最小重量為3 3漢明碼是一種特殊的漢明碼是一種特殊的(n，k，d)線性分組碼，在多進制線性分組碼，在多進制（m進制）中，它的參數進制）中，它的參數n，k和和d分別為分別為:構造一個二元的（構造一個二元的（7，4，3）漢明碼。）漢明碼。根據已知條件知，根據已知條件知，rnk3，所以有，所以有238個元素，個元素，除全除全0以外的所有其余以外的所有其余7個元素，均可作為校驗矩陣個元素，均可作為校驗矩陣的列，所以該碼的校驗矩陣為：的列，所以該碼的校驗矩陣為：000111101100111010101H1000011010010100101100001111G求三

12、進制求三進制r3的漢明碼的參數及的漢明碼的參數及 H矩陣和矩陣和G矩陣。矩陣。n=13，k=10 漢明碼漢明碼dmin3，只要任意兩列線性無關，只要任意兩列線性無關就行，所以可以直接寫出就行，所以可以直接寫出H矩陣矩陣(不是惟一的不是惟一的)：111111110010000111222110101201201212001H2101000000000110010000000022100100000001210001000000021000010000021100000100001110000001000011000000010020100000000101010000000001G 循環碼是線性

13、分組碼中最主要，最有適用價值的一類，它是循環碼是線性分組碼中最主要，最有適用價值的一類，它是1957年年由由Prange首先提出首先提出 。在循環碼中。在循環碼中BCH碼是其中最主要的一大類。漢明碼、碼是其中最主要的一大類。漢明碼、RM碼、碼、Golay碼、碼、RS碼等均可變換成或納入循環碼內，碼等均可變換成或納入循環碼內，1970年發現的年發現的Goppa碼類中有一子類也屬于循環碼。碼類中有一子類也屬于循環碼。6.3 循環碼循環碼 基本定義基本定義：一個（：一個（n n, ,k k）線性分組碼，若滿足循環移位特性：碼集）線性分組碼，若滿足循環移位特性：碼集C C中任何一個碼字循環移位后仍是碼

14、字，則稱它為循環碼中任何一個碼字循環移位后仍是碼字，則稱它為循環碼主要特點主要特點 1）理論成熟：可利用成熟的代數結構深入探討其性質；）理論成熟：可利用成熟的代數結構深入探討其性質； 2）實現簡單；可利用循環移位特性在工程上進行編，譯碼；）實現簡單；可利用循環移位特性在工程上進行編，譯碼； 3）循環碼的描述方式有很多，但在工程上可采用最有用的多項式的）循環碼的描述方式有很多，但在工程上可采用最有用的多項式的描述方法。描述方法。 一一對應一一對應： n元碼組元碼組(字字) n階階(含含0階階)碼多項式碼多項式 有限域有限域 多項式域模運算多項式域模運算 碼組模碼組模2運算運算 多項式乘積運算多項

15、式乘積運算 循環碼（續）循環碼（續）0 11()ncc cc1011( )nnc xcc xcx(2 )nGF個個n維碼字維碼字C(cn1，cn2，c1,c0)的分量循環右的分量循環右移一位就可以得到：移一位就可以得到： RC(1)(c0，cn1,cn2,，c2,c1) 將矢量將矢量C循環左移循環左移1位后就得到：位后就得到：SC（i）(cn2，cn3,，c1,c0，cn1) RC（n-i）SC（i）循環碼（續）循環碼（續）在多項式描述中，我們可以將在多項式描述中，我們可以將“同余同余”（模）運算推廣到多項式中。即（模）運算推廣到多項式中。即循環碼（續）循環碼（續）( )( )( )( )(

16、)C xr xQ xp xp x( ),mod( )C xr xp x記為： （ ）例：例：則有下列多項式除法則有下列多項式除法: 循環碼（續）循環碼（續）3567: ( )C xxxxx例7( )1p xx 71356773561 ( )11 ( )xQ xxxxxxxxx r x ( )p x（7，3）碼循環移位特性）碼循環移位特性根據循環碼的循環特性，可由一個碼字的循環移位得到其他非根據循環碼的循環特性，可由一個碼字的循環移位得到其他非0碼字。在碼字。在(n，k)循環碼的循環碼的2k個碼多項式中，取前個碼多項式中，取前k-1位皆為位皆為0的碼多項式的碼多項式g(x)(其次數其次數rn-k

17、)，再經，再經k-1次循環移位，共得次循環移位，共得到到k個碼多項式個碼多項式:g(x)，xg(x)，,xk-1 g(x)。這。這k個碼多項式顯個碼多項式顯然是相互獨立的，可作為碼生成矩陣的然是相互獨立的，可作為碼生成矩陣的k行。于是得到行。于是得到(n，k)循環碼的生成矩陣循環碼的生成矩陣G(x)為：為：（n,k)循環碼可由一個循環碼可由一個(n-k)次碼多項式次碼多項式g(x)來確定，所以稱來確定，所以稱g(x)為生成多項式。為生成多項式。1)(3xxxg例例:設設(7,4)循環碼生成多項式為循環碼生成多項式為 ，求其生成矩陣和碼字求其生成矩陣和碼字例：求例：求(7，3)循環碼的生成多項式

18、。循環碼的生成多項式。 分解多項式分解多項式x71，取其，取其4次因式作生成多項式：次因式作生成多項式：x7+1(x1)(x3x21)(x3x1)g1(x)(x1)(x3x21)x4x2x1g2(x)(x1)(x3x1)x4x3x21g1(x)和和 g2(x) 都可以作為生成多項式。都可以作為生成多項式。因為因為(n，k)線性碼的生成矩陣線性碼的生成矩陣G和校驗矩陣和校驗矩陣H滿足滿足GHT0,循環循環碼也是線性碼碼也是線性碼,如果設如果設g(x)為為(n，k)循環碼的生成多項式，它循環碼的生成多項式，它必為必為xn1的因式，則有的因式，則有 xn1h(x)g(x) 因為因為g(x)為為n-k

19、次多項式，以次多項式，以g(x)為生成多項式，則生成一個為生成多項式，則生成一個(n，k)循環碼，以循環碼，以h(x)為生成多項式，則生成為生成多項式，則生成(n，n-k)循環碼，這兩個循環碼，這兩個循環碼互為對偶碼。循環碼互為對偶碼。 h(x)hkxkhk-1xk-1h1xh0 11111110011( )0110( )1100( )kkn kkhhh xhhxh xHhhxh x h*(x)為為h(x)反多項式反多項式h(x)為為(n，k)循環碼的校驗多項式或監督多項式循環碼的校驗多項式或監督多項式 可得校驗矩陣（監督矩陣）：可得校驗矩陣（監督矩陣）：產生系統循環碼的方法：產生系統循環碼的

20、方法：1.將信息多項式將信息多項式m(x)預乘預乘xn-k,即右移（即右移（n-k）位。）位。2.將將xn-k m(x)除以除以g(x),得余式得余式r(x)。3.得系統循環碼的碼多項式得系統循環碼的碼多項式C(x)=xn-k m(x)+r(x)。循環碼的編碼循環碼的編碼例例: :若輸入信息碼元為若輸入信息碼元為: :u u=(1001)=(1001)即即 , ,下面將簡介最下面將簡介最簡單的系統循環碼的編譯碼簡單的系統循環碼的編譯碼. .仍以仍以(7,4)(7,4)系統循環碼為例系統循環碼為例: :我們所選的多項式我們所選的多項式 , ,由系統碼生成規則由系統碼生成規則: : 31)(xxu)1 ()()(33xxxgxg32633471)(mod,)1 ()(xxxgxxxxxxxuxkn33363464242 ( )1(