第六章信道編碼

（1）信道編碼目的：提高通信系統(tǒng)傳輸?shù)目煽啃?；?）目標：尋找具體構造編碼的理論與方法；只要當實際傳信率R<C（信道容量），無差錯的信道編、譯碼是存在的。（3）信道編碼原理：根據(jù)一定的規(guī)律在待發(fā)送的信息碼元中人為的加入一定的多余碼元，以保證在傳輸中，發(fā)送碼元的可靠性。（4）信道編碼任務：就是構造出以最小冗余度代價換取最大抗干擾性能的好的碼字第六章信道編碼§6.1概述信道編碼又稱糾錯編碼，是提高數(shù)字傳輸可靠性的一種技術一.有擾離散信道的信道編碼定理(香農第二定理)在信息傳輸速率小于信道容量的條件下，可通過增加代碼組長度m的編碼方法，使得接收端恢復消息的誤碼率小于任意給定的小數(shù)ε。反之，若信息傳輸速率大于信道容量時，則誤碼率為一固定值，即使增加代碼組長度m也不能使誤碼率任意小該定理也就是說，只要R<C，就存在速率為R的糾錯碼收端結論：不重復，方法簡單，但沒有任何抗干擾能力，既不能發(fā)現(xiàn)，更不能糾正錯誤?！恢貜蜁r例：簡單的信道編碼（重復碼）—重復一次：發(fā)端收端能發(fā)現(xiàn)一個錯結論：重發(fā)一次，效率降低一倍?？梢該Q取在傳輸過程中允許產生一個錯誤（收端能發(fā)現(xiàn)它），但不能糾正?！貜投危喊l(fā)端收端能糾正一個錯或發(fā)現(xiàn)兩個錯結論：重發(fā)二次，效率降低二倍，但換取了可糾正一個差錯或發(fā)現(xiàn)兩個差錯的性能改善。說明：由此可見，糾錯編碼之所以具有檢錯和糾錯能力，是因為在信息碼之外附加了校驗碼（監(jiān)督碼）。校驗碼不荷載信息，它的作用是用來監(jiān)督信息碼在傳輸中有無差錯，對用戶來說是多余的，最終也不傳送給用戶，但它提高了傳輸?shù)目煽啃浴Ｐｒ灤a的引入，降低了信道的傳輸效率。一般來說，引入校驗碼元越多，碼的檢錯、糾錯能力越強，但信道的傳輸效率下降也越多。人們研究的目標是尋找一種編碼方法使所加的校驗碼元最少,而檢錯、糾錯能力又高且又便于實現(xiàn)。

二.通信系統(tǒng)三.錯誤的種類若發(fā)送碼字v＝(11000)接收矢量r＝(10001)由于噪聲，出現(xiàn)兩個錯誤設v＝(v1，v2，v3，…，vn)r＝(r1，r2，r3，…，rn)e＝v+r＝(v1+r1，v2+r2，v3+r3，…，vn+rn)

若ei＝vi+ri＝1，則表示碼字中第i位受到干擾，出現(xiàn)錯誤錯誤類型先檢錯，后糾錯

檢錯碼——有發(fā)現(xiàn)錯誤能力的碼。通常用檢錯碼的通信系統(tǒng)必須具有反饋信道。當發(fā)現(xiàn)收到消息有錯誤時，接收端通過反饋信道發(fā)出一個信號，要求發(fā)送端把消息再次發(fā)送，直到接收端認為正確為止。

糾錯碼——有發(fā)現(xiàn)并糾正錯誤能力的碼隨機錯誤——由隨機噪聲引起的(各碼元是否發(fā)生錯誤是相互獨立的，不會成片的出現(xiàn)錯誤)突發(fā)錯誤——由突發(fā)噪聲引起的(各碼元是否發(fā)生錯誤存在相關性，錯誤成片出現(xiàn))

四.糾錯碼的分類校驗位與信息位的關系線性碼——校驗位與信息位之間呈線性關系非線性碼——校驗位與信息位之間不存在線性關系對信息位處理方法分組碼——如碼組長度為n位，信息位數(shù)為k，則每一碼組

的(n－k)個校驗位與本碼組的k個信息位有關卷積碼——如碼段長度為n0位，該段有k0個信息位，則該

碼一個碼段的(n0－k0)個校驗位不僅與本段的

k0個信息位有關，而且與前m段的信息位有關碼字之間的關系循環(huán)碼非循環(huán)碼按糾錯碼的類型糾隨機錯誤碼糾突發(fā)錯誤碼糾隨機與突發(fā)錯誤碼(n,k)編碼后信息碼元是否保持原樣系統(tǒng)碼非系統(tǒng)碼1）域：域是由一些元素所構成的集合，在集合里，可以定義任意兩個元素在某種意義上的加法和乘法，則這個集合稱為域。記做：F。F中的成員叫做元素或簡稱元。域中任意兩個元素的和、積仍是域中的元素，并且滿足交換律和分配律。常用的有F2常用的運算包括：模2加2）階：域F中元素的個數(shù)叫做F的階.基本概念3）有限域：如果F的階是有限的，就把F叫做有限域。也稱伽羅華域4）線性無關：對于域F上的若干矢量，若滿足（非零系數(shù)）：則稱V1,V2,…,Vi矢量線性相關，否則稱線性無關。碼重是指碼字中所含“1”的數(shù)目，比如：

（5）碼重漢明重量

設碼字v＝(v0，v1，v2，…，vn-1)∈Vn(F2)，令w(v)為碼字v中那些不為0的碼元個數(shù)，即則稱w(v)是碼字v的漢明重量，簡稱重量而稱C中那些不等于0的碼字的重量的最小值wmin(v)為C的最小重量

任一碼字的漢明重量都可以看作是該碼字與0碼字間的漢明距離若v＝(0111000)則w(v)＝3；u＝(1000111)則w(u)＝4

（6）碼距：碼距是指兩個碼字Ci與Cj中相應碼元不相同的數(shù)目。比如：（2，1）重復碼（1，1）重復碼（3，1）重復碼

漢明距離設a和b是集合Vn(F2)中的任意兩個碼字，令a＝(a0，a1，a2，…，an-1)b＝(b0，b1，b2，…，bn-1)

并規(guī)定d(a，b)表示a和b的各相應碼元之間不相同的個數(shù)，即我們把d(a，b)稱為a和b之間的漢明距離，簡稱距離性質1.自反性對任意a∈Vn(F2)d(a，a)＝02.對稱性對任意a，b∈Vn(F2)d(a，b)＝d(b，a)3.三角不等式對任意a，b，c∈Vn(F2)d(a，b)+d(b，c)＝d(a，c)

例：u＝（10010110001）v＝（11001010101）d(u，v)＝5

①糾隨機錯誤碼設碼字間的最小距離為dmin，則該碼的糾錯能力t(即具有糾t個隨機錯誤的能力)可用下式表示：該碼的檢錯能力t，可用下式表示：dmin是指在某碼范圍內，所有可能的漢明距離中的最小數(shù)值②糾突發(fā)錯誤碼設n為碼字的位數(shù)，k為信息位數(shù)，該碼的糾錯能力(能糾正長l位的突發(fā)錯誤)可用下式表示：

③糾隨機與突發(fā)錯誤碼以交錯碼為例，如能把糾t個錯誤的(n，k)碼中λ個碼字作為矩陣的λ行，然后按列發(fā)送，就可構成(λn，λk)交錯碼。即構成即能糾t個隨機錯誤，又能糾t個長為λ的突發(fā)錯誤碼為什么要引入線性碼發(fā)現(xiàn)或構造好碼是信道編碼研究的主要問題編碼方案太多，以至全局搜索是不可能的，現(xiàn)實的做法是對編碼方案加以一定的約束，在一個子集中尋找局部最優(yōu)。這種約束即要能包含盡可能好的碼，又要便于分析，便于譯碼。目前對線性系統(tǒng)的研究遠比非線性系統(tǒng)充分假設有M個等概率出現(xiàn)的消息，長度都為k位，存在M＝2k加上r個多余位，每個碼字長度k+r＝n位。這就使n位的二進制數(shù)字序列共有2n個，但可能的消息數(shù)只有2k個，故只能有2k個碼字（即(2n－2k)個n位序列不是碼字）§6.2線性分組碼

線性特性——碼組內校驗碼與信息碼間為線性關系分組特性——每碼組內的校驗碼只與本組信息碼有關，與其他碼組無關。表示——(n,k)線性分組碼信息碼k位，碼組n位

此時的碼字形式為：m1m2…mkp1p2…pr，mi表示第i個信息位，pj表示第j個校驗位。各個校驗位，可從下列線性方程組求得：

式中hij是常數(shù)，等于0或1。式中每個方程都代表校驗位(p1p2…pr)和信息位(m1m2…mk)之間的線性關系一、線性分組碼數(shù)字結構（1）校驗矩陣

從方程組可寫成校驗矩陣：該矩陣具有r行，n列，是碼的一種數(shù)學結構若把碼字寫成行向量，有：v＝（m1m2…mkp1p2…pr）則方程組可寫成：vHT＝0或HvT＝0此式中設v為發(fā)送矢量，若信道無干擾，接收矢量r就是vrHT≠0發(fā)生錯誤（≥1個）

rHT＝0無錯誤錯誤太大，無法檢出錯誤

糾正錯誤的方法設發(fā)送矢量為v，接收矢量為r，出現(xiàn)的信道錯誤為e，則有下列關系式：r＝v+e為了糾錯，必須知道r中哪些位上存在錯誤，這可由校正子(伴隨式)s來確定s＝rHT＝eHT+vHT＝eHT令設r第i位是錯誤的，因此錯誤圖樣為e＝(00…010…0)（第i位為1）

例：設要把16個等概率出現(xiàn)的消息構造成線性分組碼，設信息位為k，校驗位為r,碼子長度為n=k+r。解：從題意可知，16＝2k，k＝4。為了糾正一個錯誤，r＝2，即n＝4+2＝6。這種編碼方式不行，校驗矩陣H只有2行，6列，無法排出各不相同的6列。6列各不相同，主要目的是使校正子s能定出錯誤位置進行糾正（即存在相同列時，無法判斷到底哪一列出錯?。┤魊＝3，可排出（7，4）分組碼的校驗矩陣H：

如消息為1010，則從上列關系可得出：即可得碼字為1010010該碼編碼方法如下：下表列出了（7，4）碼的24＝16個碼字對于糾錯，從表中看出最小漢明距離dmin＝3故根據(jù)式，該碼能糾正個錯誤如接收矢量r＝(1010111)，則由s可知，發(fā)送矢量應為(1000111)

生成矩陣G是碼的另一種數(shù)學結構，它是k行，n列的矩陣

(n，k)線性碼的碼字都可由G中各行的線性組合生成，即碼字＝(消息組)×(生成矩陣)線性分組碼數(shù)字結構（2）：生成矩陣

生成矩陣與校驗矩陣之間可以相互轉換

式中PT為P的轉置矩陣，Ir×r和Ik×k為單位矩陣例：例：若校驗矩陣H為

則生成矩陣G為用生成矩陣G也可求得碼字，若m1m2m3m4＝1010

生成矩陣G和校驗矩陣H的關系生成矩陣G一般用于發(fā)端編碼，而檢驗矩陣H則一般用于接收端的譯碼。由于生成矩陣G中的每一行及其線性組合都是線性（n,k）碼的碼組（字），所以根據(jù)公式H·vT=OT(v=m×G)有H·GT=OT它說明矩陣G與H互為零空間由線性空間理論，一個n維的線性空間Vn可以分解為一對互為對偶的正交子空間Vk與Vn-k。即：

互為對偶碼可構成(7,3)線性分組碼可構成(7,4)線性分組碼顯然有：(7,3)碼的生成矩陣G3就是(7,4)碼校驗矩陣H’3，(7,3)碼的校驗矩陣H4就是(7,4)碼的生成矩陣G’4可構成(n,k)線性分組碼可構成(n,n-k)線性分組碼互為對偶碼結合上面n=7的例子,則有二、線性分組碼及其檢、糾錯能力的獲得一般來說，編碼器將k位消息u=（u0,u1,…,uk-1)映射成n位數(shù)字組v=(v0,v1,…,vn-1)所依據(jù)的規(guī)則不外乎是一組函數(shù)關系或一種對應關系例：設一個（6，3）分組碼的編碼規(guī)則為如果把分組消息序列(u0，u1，u2)映射成碼序列(v0，v1，…，v5)的關系用矩陣表示，有：此例中v0，v1，v2是消息位，v3，v4，v5是校驗位寫成齊次，以矩陣表示：例：設一個原始數(shù)字消息為u0，其編碼規(guī)則為：它是一個(n，1)線性分組碼，是一個重復碼例：它是一個(n，n－1)線性碼，是奇偶校驗碼。

此例中所定義的每個碼字中，1的個數(shù)一定是偶數(shù)，當接收到一個碼字中1的個數(shù)若不是偶數(shù)，可確定它不是碼字，它只能檢出單個或奇數(shù)個錯誤，但不能發(fā)現(xiàn)偶數(shù)個錯誤重復碼——編碼效率η＝1/n，這是長為n的分組碼中效率最低的，糾錯能力強奇偶校驗碼——編碼效率η＝n-1/n，這是長為n的分組碼中效率最高的，糾錯能力低

糾錯編碼的中心任務——要在這兩個極端類型的碼之間尋找一些性能良好的碼，使我們可根據(jù)不同干擾特性的信道，設計出編碼效率高、抗干擾能力好而編譯碼設備又簡單的碼這兩種編碼方式是線性分組碼的兩個極端類型先引入信道錯誤圖樣的概念。所謂信道錯誤圖樣，就是長為n的二元序列：如果其中某個元的數(shù)字為1，則表示該位出現(xiàn)錯誤。序列中1的個數(shù)稱為錯誤圖樣的錯誤重數(shù)，但重數(shù)為t時，就稱該圖樣為t重錯誤。在引入錯誤圖樣的概念后，任何由碼字出現(xiàn)錯誤而得到的接收字都可以表示為碼字和錯誤圖樣的模2加。碼字C在傳輸過程中受到各種干擾，接收端的收碼r不一定等于發(fā)碼，兩者之間的差異定義為差錯e。e=r－C對于二進制，模2減等于模2加，所以：e=r＋Cr=C+e又有CHT＝0收碼無誤收碼有誤定義S=rHT的運算結果為伴隨式。譯碼過程如下圖所示計算SC=r+e計算eCer輸出可知，這是n=2的重復碼，也是（2，1）奇偶校驗碼，所以它只能發(fā)現(xiàn)一個錯誤，但無法糾正。①在集合{ei+vj,i=1,2,…,6}(j=1,2)中，設有vj(j=1,2)，因而當信道出現(xiàn)錯誤ei，i=1,2,…,6時，可以發(fā)現(xiàn)此時的接收字是錯誤的，從而可以檢出所有不多于二個的錯誤；②在集合{ei+v1,i=1,2,3}和集合{ei+v2,i=1,2,3}中沒有碼字v1/v2，而且它們之間也沒有公共的接收字。因此，可以將接收字ei+vj（i=1,2,3）判定為vj，從而可以糾正所有單重錯誤的錯誤圖樣e1，e2和e3；③但是，這個碼并不兼有能糾正所有單重錯誤并檢出所有二重錯誤的能力。例如：如有e4+v1＝e3+v2，就可能將e4+v1誤認為v2。(1)要使碼具有檢、糾錯能力，必須附加多余的碼元，即增加消息的冗余度，這相當于n>k。而且一般來說，碼的冗余度越大，檢、糾錯能力就越強；(2)任何一種檢錯或糾錯碼都不可能檢出或糾正所有的錯誤。事實上，如果碼中至少有兩個碼字v1和v2。則錯誤圖樣e=v1+v2，就不能夠被檢出或糾正；(3)如果錯誤圖樣集{ei,i=1,2,..,l}使得每個碼字vj(j=1,2,…,m)變成的接收字集{ei＋vj}中不包含碼字vj，則這個碼就可以檢出所有的錯誤圖樣ei；(4)如果錯誤圖樣集{ei,i=1,2,..,l}使得任一對碼字vj，vk變成的接收字集{ei＋vj}和{ei＋vk}之間無公共的接收字，而且不含任一碼字，那么就只需要把ei＋vj判為vj；(5)如果錯誤圖樣集可以分為無公共部分的集{ei,i=1,2,..,l}和集{e’i,i=1,2,..,l’}，而且碼字集{vj,j=1,2,…,m}對于{ei,i=1,2,..,l}滿足第4點，則該碼可以糾正所有ei，并且對集{e’i,i=1,2,..,l’}有如下的性質：任一碼字vj的相應接收字集{e’i＋vj}中都不含{ei＋vr}（r≠j）中的接收字以及vr，則此碼可兼有糾正所有的錯誤圖樣ei和檢出所有的錯誤圖樣e’i三、線性分組碼的檢、糾錯能力最小距離dmin與碼率R是碼的兩個最主要參數(shù)，dmin表示了碼的糾錯能力。用（n，k，d）表示距離為d，碼率R＝k／n的線性分組碼。糾錯碼的基本任務之一就是構造出R一定且dmin盡可能大的碼，或dmin一定且R盡可能大的碼。檢測e個錯誤，則要求最小碼距：dmin≥e＋1編碼的最小碼距為dmin，則最多能檢出（dmin-1）個錯誤。e+1eC1(a)糾正t個錯碼，則要求最小碼距為：

dmin≥2t＋12t+11ttC1C2糾正t個錯碼，同時能檢測e(e>t)個錯碼，則要求最小碼距為dmin≥e＋t＋1,e>te+t+11etC1C2定理：線性分組碼的最小距離等于碼中碼字的最小重量。定理：(n，k，d)線性分組碼有最小距離dmin的充要條件是H矩陣中任意d－1列線性無關，存在d列線性相關。推論：(n，k，d)線性分組碼的最小距離dmin≤n－k＋1。若系統(tǒng)碼的最小距離dmin＝n－k＋1，則稱此碼為極大最小距離可分碼，簡稱MDS碼。定理：設C是個線性分組碼，H是它的校驗矩陣，那么C是可以糾正單個錯誤的糾錯碼的充要條件是H中沒有元素全為0的列矢量，且H的任意兩個列矢量都不相同定義：令H是個二元r×(2r-1)矩陣，這個矩陣的列是Vm(F2)中按某種次序排列的2r-1個非零矢量。那么，定義為F2上的n＝2r-1，k＝2r-1-r的線性分組碼(其校驗矩陣為H)，就稱為長2r-1的漢明碼設線性碼的校驗矩陣四.常用線性分組碼-------漢明碼漢明最早提出的一類能糾正單個錯誤的糾錯碼如果接收矢量r＝(101000101)，根據(jù)s＝rHT有s＝(1100)，即r中第五位數(shù)出錯，經糾錯后r＝(101010101)如果接收矢量r＝(001000101),根據(jù)s＝rHT有s＝(1101)，s不等于H中任意一列，實際上該碼有兩個錯誤定理：二元(2r-1，2r-1-r)漢明碼是能糾正所有單個錯誤的線性碼，而且是校驗位數(shù)為r的所有二元線性碼中編碼效率最高的碼,它的最小重量為3漢明碼是一種特殊的(n，k，d)線性分組碼，在多進制（m進制）中，它的參數(shù)n，k和d分別為:構造一個二元的（7，4，3）漢明碼。根據(jù)已知條件知，r＝n－k＝3，所以有23＝8個元素，除全0以外的所有其余7個元素，均可作為校驗矩陣Ｈ的列，所以該碼的校驗矩陣為：求三進制r＝3的漢明碼的參數(shù)及H矩陣和G矩陣。n=13，k=10漢明碼dmin＝3，只要任意兩列線性無關就行，所以可以直接寫出H矩陣(不是惟一的)：循環(huán)碼是線性分組碼中最主要，最有適用價值的一類，它是1957年由Prange首先提出。在循環(huán)碼中BCH碼是其中最主要的一大類。漢明碼、R―M碼、Golay碼、RS碼等均可變換成或納入循環(huán)碼內，1970年發(fā)現(xiàn)的Goppa碼類中有一子類也屬于循環(huán)碼。§6.3循環(huán)碼

基本定義：一個（n,k）線性分組碼，若滿足循環(huán)移位特性：碼集C中任何一個碼字循環(huán)移位后仍是碼字，則稱它為循環(huán)碼主要特點1）理論成熟：可利用成熟的代數(shù)結構深入探討其性質；2）實現(xiàn)簡單；可利用循環(huán)移位特性在工程上進行編，譯碼；3）循環(huán)碼的描述方式有很多，但在工程上可采用最有用的多項式的描述方法。一一對應：

n元碼組(字)n階(含0階)碼多項式

有限域多項式域模運算碼組模2運算多項式乘積運算循環(huán)碼（續(xù)）—個n維碼字C＝(cn－1，cn－2，…，c1,c0)的分量循環(huán)右移一位就可以得到：RC(1)＝(c0，cn－1,cn－2,…，c2,c1)將矢量C循環(huán)左移1位后就得到：SC（i）＝(cn－2，cn－3,…，c1,c0，cn－1)RC（n-i）＝SC（i）循環(huán)碼（續(xù)）在多項式描述中，我們可以將“同余”（模）運算推廣到多項式中。即循環(huán)碼（續(xù)）例：則有下列多項式除法:循環(huán)碼（續(xù)）（7，3）碼循環(huán)移位特性根據(jù)循環(huán)碼的循環(huán)特性，可由一個碼字的循環(huán)移位得到其他非0碼字。在(n，k)循環(huán)碼的2k個碼多項式中，取前k-1位皆為0的碼多項式g(x)(其次數(shù)r＝n-k)，再經k-1次循環(huán)移位，共得到k個碼多項式:g(x)，xg(x)，…,xk-1g(x)。這k個碼多項式顯然是相互獨立的，可作為碼生成矩陣的k行。于是得到(n，k)循環(huán)碼的生成矩陣G(x)為：（n,k)循環(huán)碼可由一個(n-k)次碼多項式g(x)來確定，所以稱g(x)為生成多項式。例:設(7,4)循環(huán)碼生成多項式為

，求其生成矩陣和