第九章糾錯編碼1

第九章糾錯編碼1糾錯碼的分類2糾錯碼的基本概念3線性分組碼4漢明碼5循環(huán)碼香農(nóng)第二定理證明，當(dāng)時的碼存在。證明過程采用的是隨機編碼的方法：隨機編碼所得的碼集很大，通過搜索得到好碼的方法在實際上很難實現(xiàn)；即時找到了好碼，這種碼的碼字也沒有規(guī)律，不便于譯碼。真正實用的信道編碼方法還需要通過各種數(shù)學(xué)工具來構(gòu)造，使碼具有好的結(jié)構(gòu)性以便于譯碼。

糾錯編碼的基本思路：根據(jù)一定的規(guī)律在待發(fā)送的信息碼元中人為的加入一些冗余碼元，這些冗余碼元與信息碼元之間以某種確定的規(guī)則相互關(guān)聯(lián)（約束）。在接收端按照既定的規(guī)則檢驗信息碼元與監(jiān)督碼元之間的關(guān)系。如果傳輸過程出錯，則信息碼元與監(jiān)督碼元之間的關(guān)系將受到破壞，從而可以發(fā)現(xiàn)錯誤乃至糾正錯誤。概述干擾一般分為兩種形式：一是隨機噪聲，它主要來源于設(shè)備的熱噪聲和散彈噪聲以及傳播媒介的熱噪聲，它是通信系統(tǒng)中的主要噪聲；二是脈沖干擾和信道衰落，它的特點是突發(fā)出現(xiàn)，主要來源于雷電、通電開關(guān)、負荷突變或設(shè)備故障等。概述信道可分為三類：1.只產(chǎn)生隨機錯誤的信道稱為隨機信道。比如衛(wèi)星信道、同軸電纜、光纜信道以及大多數(shù)微波中繼信道。2.產(chǎn)生突發(fā)錯誤的信道稱為突發(fā)信道。實際的短波信道、移動通信信道、由于差傷造成成串差錯的光盤和磁盤，均為這一類信道。3.有些實際信道既有隨機錯誤又有突發(fā)錯誤，稱為混合信道。根據(jù)不同的信道類型設(shè)計的信道編碼分為糾隨機錯誤碼、糾突發(fā)錯誤碼和糾混合錯誤碼。概述在通信系統(tǒng)中，糾檢錯的工作方式有：(1)反饋重傳(ARQ)(2)前向糾錯(FEC)(3)混合糾錯概述發(fā)送端經(jīng)編碼后發(fā)出能夠發(fā)現(xiàn)錯誤的碼，接收端收到后經(jīng)檢驗，如果發(fā)現(xiàn)傳輸中有錯誤，則通過反饋系統(tǒng)把這一判斷結(jié)果反饋回發(fā)端，然后發(fā)送端把前面發(fā)出的信息重新傳送一次，直到接收端認為正確地收到信息為止。

(1)反饋重傳(ARQ)檢錯編碼信道檢錯譯碼反饋(2)前向糾錯(FEC)糾錯編碼信道糾錯譯碼發(fā)送端發(fā)出的是具有糾錯能力的糾錯碼，接收端根據(jù)譯碼規(guī)則進行譯碼。當(dāng)誤碼個數(shù)在碼的糾錯能力范圍內(nèi)時，譯碼器可以自動糾正錯誤。特點：1）前向糾錯方式不需要反饋信道，特別適合于只能提供單向信道的場合。2）由于能自動糾錯，不要求檢錯重發(fā)，因而延時小，實時性好。3）隨著糾錯能力的增強，譯碼設(shè)備也變得復(fù)雜。(3)混合糾錯對發(fā)送端進行適當(dāng)?shù)木幋a。當(dāng)錯誤不嚴重，在碼的糾錯能力范圍之內(nèi)時，采用自動糾錯；當(dāng)產(chǎn)生的差錯超出碼的糾錯能力范圍時，通過反饋系統(tǒng)要求發(fā)端重發(fā)。(1)按功能分：檢錯碼：僅能檢測誤碼糾錯碼：可糾正誤碼糾刪碼：兼糾錯和檢錯能力糾錯碼1糾錯碼的分類(2)按信息碼元與監(jiān)督碼元之間的檢驗關(guān)系分：--線性碼：滿足線性關(guān)系--非線性碼：不存在線性關(guān)系(3)按信息碼元與監(jiān)督碼元之間的約束方式不同分：分組碼：本碼組的監(jiān)督碼元僅和本碼組的信息元相關(guān)。卷積碼：本碼組的監(jiān)督碼元不僅和本碼組的信息元相關(guān)，而且與前面碼組的信息碼元有關(guān)。碼與碼相互影響不能分開，又稱數(shù)碼或鏈碼重點討論線性分組碼(4)按信息碼元在編碼后是否保持原形式不變：

即：根據(jù)信息元在分組碼中的位置分為系統(tǒng)碼，非系統(tǒng)碼系統(tǒng)碼：信息碼元與監(jiān)督碼元在分組內(nèi)有確定位置，編碼后的信息碼元保持不變；非系統(tǒng)碼：信息位打亂，與編碼前不同。(5)按糾正差錯的類型可分為：

糾隨機錯誤碼糾突發(fā)錯誤碼糾隨機和突發(fā)錯誤碼糾錯碼按結(jié)構(gòu)分類如下：

1糾錯碼的分類(續(xù))分組碼的表示方法：（二元分組碼）信息碼組由k

個信息碼元組成，共有2k

個不同的信息碼組；信息位

附加

個校驗碼元，每個校驗碼元是該信息碼組的某些信息碼元模2和；校驗位或監(jiān)督位

編碼器輸出長度為n的碼字；碼字的數(shù)目共有2k

；這2k

個碼字的集合稱為(n,k)

分組碼；2糾錯碼的基本概念信息傳輸率（碼率），編碼效率對二進制(n,k)線性分組碼，合法碼字數(shù)為2k，可用編碼空間的序列數(shù)為2n個。許用序列，禁用序列

任一種2k信息集合到二進制序列集合(2n)的映射都是一種(n,k)碼。因此總共可能的編碼方案有種。2糾錯碼的基本概念（續(xù)）發(fā)現(xiàn)或構(gòu)造好碼是信道編碼研究的主要問題：編碼方案太多，以至全局搜索是不可能的?，F(xiàn)實的做法是對編碼方案加以一定的約束，在一個子集中尋找局部最優(yōu)。這種約束即要能包含盡可能好的碼，又要便于分析，便于譯碼。線性分組碼是最具實用價值的一類碼，比如漢明碼、循環(huán)碼、BCH碼、RS碼等。2糾錯碼的基本概念（續(xù)）2糾錯碼的基本概念（續(xù)）對信道編碼的一般要求是：①糾錯檢錯能力強；②信息傳輸率高；③編碼規(guī)律簡單，實現(xiàn)設(shè)備簡單且費用合理；④與信道的差錯統(tǒng)計特性相匹配。漢明距離漢明距離滿足距離公理(1)

非負性對稱性(3)三角不等式2糾錯碼的基本概念漢明重量

碼C的最小漢明距離線性分組碼的最小漢明距離等于非零碼字的最小重量。2糾錯碼的基本概念3線性分組碼3.1校驗矩陣與生成矩陣(1)校驗矩陣則令被稱為校驗矩陣。對線性分組碼，校驗矩陣為維矩陣。對于系統(tǒng)碼，校驗矩陣可以表示為其中為維矩陣，為維單位矩陣。由校驗方程，得到(2)生成矩陣令其中為維矩陣，為維單位矩陣。被稱為生成矩陣。對線性分組碼，生成矩陣為維矩陣。對于系統(tǒng)碼，生成矩陣可以表示為把生成矩陣的每一行用一個行向量來表示，則生成矩陣可以表示為令，則由于生成矩陣G的每一行都是一個碼字，所以G的每行都滿足

，則有對于標(biāo)準(zhǔn)形式的校驗矩陣和監(jiān)督矩陣，有(3)校驗矩陣和生成矩陣的關(guān)系線性分組碼的封閉性：線性分組碼中任意兩個碼字之后仍然是該碼的碼字。證明：設(shè)和分別是碼中的兩個碼字，因此有即滿足監(jiān)督方程，所以是碼中的一個碼字。例：重復(fù)碼是一個（3,1）線性分組碼。其生成矩陣為例：（4,3）偶校驗碼是一個（4,3）線性分組碼，其生成矩陣為例已知生成矩陣為

求生成的線性分組碼及由H生成的線性分組碼。11111111111111010011101101001110111000101100101100010111010011101010011101001100010110000111010011101100010110010110001010100111010000111010011001011000100001011000100000000000Cm關(guān)于碼的最小距離與糾、檢錯能力的關(guān)系有以下結(jié)論：對于（n，k）線性分組碼，設(shè)為最小漢明距離。（１）這組碼有糾正u個錯誤的充要條件是uu2u+1對于一個二進制對稱信道，當(dāng)輸入為2k個等可能的n長碼字，則最大后驗概率準(zhǔn)則等效于最小漢明距離譯碼準(zhǔn)則。3.2線性分組碼的糾、檢錯能力lll+1（２）具有檢測l個錯誤的充要條件是uutlt+l+1（３）具有糾正t個錯誤，同時可以發(fā)現(xiàn)l個錯誤的充分必要條件為碼的糾錯能力u與碼字的長度n和消息數(shù)M滿足以下關(guān)系：3.3校驗矩陣與最小距離的關(guān)系對于（n，k）線性分組碼：校驗矩陣H中的任意t列線性無關(guān)而t+1列線性相關(guān)，則碼的最小距離(碼字的最小重量)為t+1。反過來說，若碼的最小距離(碼字的最小重量)為t+1則H的任意t列線性無關(guān)而t+1列線性相關(guān)。3.4線性分組碼的伴隨式R=C+EE=[e1

e2…en]1)，說明R是一個碼字;2)，說明R不是碼字，傳輸過程產(chǎn)生了誤碼。令則（其中表示的列向量）

結(jié)論：1)當(dāng)傳輸過程沒有錯誤時，即，2)當(dāng)發(fā)生一位錯誤時，是校驗矩陣的某一列。3)當(dāng)發(fā)生多個錯誤時，為校驗矩陣對應(yīng)列的模2和。例：設(shè)(7,3)線性分組碼的校驗矩陣為（1）接收碼字R=(1010011)，傳輸過程中沒有誤碼，（2）接收碼字R=(1110011)，，第2位出錯，（3）接收碼字R=(0011011)，與中的任一列都不相同，不能確定到底是哪兩位出錯，不能正確譯碼。線性分組碼的伴隨式譯碼

若（n，k）線性分組碼能夠糾正u個錯誤，則其校驗位的數(shù)目必須滿足完備碼漢明碼是一種能夠糾正單個錯誤的完備碼。漢明碼最小碼距設(shè)監(jiān)督碼共有m位，對于漢明碼必然有。通常漢明碼可以表示成。4漢明碼

在同樣的糾錯能力下，漢明碼的碼率是最高的

漢明碼監(jiān)督矩陣構(gòu)成的兩種方式：構(gòu)成H陣的標(biāo)準(zhǔn)形式，

。按m位的二進制數(shù)的自然順序從左到右排列（不包括全0列）。當(dāng)發(fā)生可糾的單個錯誤時，伴隨式為H陣中對應(yīng)的列，譯碼比較方便。非標(biāo)準(zhǔn)形式的監(jiān)督矩陣可以通過列置換變成標(biāo)準(zhǔn)形式的監(jiān)督矩陣，糾錯能力保持不變。如果給漢明碼添加一位奇偶校驗位，可得到擴展?jié)h明碼：

信息位保持不變，監(jiān)督位增加一位。最小碼距，可糾正一位錯誤，同時發(fā)現(xiàn)兩位錯誤。擴展?jié)h明碼的監(jiān)督方程：循環(huán)碼是線性分組碼的一個重要子集。循環(huán)碼除了具有線性分組碼的一般性質(zhì)外，還具有循環(huán)性：循環(huán)碼中任一許用碼組經(jīng)過循環(huán)移位后，所得到的碼組仍然是許用碼組。循環(huán)碼有嚴密的代數(shù)學(xué)理論基礎(chǔ)，檢錯和糾錯能力較強，而且編碼和解碼設(shè)備都不太復(fù)雜。5

循環(huán)碼5

循環(huán)碼1)對于二進制碼，碼多項式的每個系數(shù)不是0就是1。

2)僅是碼元位置的標(biāo)記。我們并不關(guān)心的取值。

設(shè)循環(huán)碼的碼字為，用碼多項式表示為碼字（1100101）可以表示為：

循環(huán)碼的循環(huán)特性可以用碼多項式來證明。在整數(shù)運算中，有模n運算。若一個整數(shù)m可以表示為:

則

在模n運算下，一整數(shù)m等于其被n除所得的余數(shù)。

5

循環(huán)碼在碼多項式運算中也有類似的按模運算法則。若一任意多項式F(x)被一個n次多項式N(x)除，得到商式Q(x)和一個次數(shù)小于n的余式R(x)，也就是：

則可以寫為：

在循環(huán)碼中，若

是一個長為n的許用碼字，則在模運算下，也是一個許用碼字。例某循環(huán)碼的一個碼字為1100101，則

若將此碼左移一位，得：

對應(yīng)的碼字為1001011，與將碼字1100101循環(huán)左移一位相同。5

循環(huán)碼…5

循環(huán)碼從碼中取出一個前面k-1位都是0的碼字，定義這個碼字的碼多項式為生成多項式。在

循環(huán)碼中，除了全0碼字以外，其他碼字的連0個數(shù)最多只有k-1個。

碼多項式的次數(shù)為

，且常數(shù)項不為0。5

循環(huán)碼信息比特碼字