信息論

InformationTheory哈爾濱工程大學(xué)

2013王逸林Tel:82519503E-mail:wangyilin@第4章抗干擾信道編碼目的：提高通信系統(tǒng)傳輸?shù)目煽啃裕荒繕?biāo)：尋找具體構(gòu)造編碼的理論與方法；抗干擾編碼的基本思想在理論上，Shannon第二編碼定理已指出，只要當(dāng)實際傳信率R<C（信道容量）幾乎無差錯的信道編、譯碼是存在的。理論上的存在性并不等于實際上的可構(gòu)造性，本章就是研究如何構(gòu)造如何實現(xiàn)信道編碼的理論與方法。從原理上看，構(gòu)造信道碼的基本思路是根據(jù)一定的規(guī)律在待發(fā)送的信息碼元中人為的加入一定的多余碼元，以保證在傳輸中，發(fā)送碼元的可靠性。信道編碼器：將信源編碼后的符號加上冗余符號，提高傳輸?shù)目煽啃浴?.信道編碼概述1.信道編碼概述圖1編碼信道模型信道編碼器信道譯碼器信道2.譯碼規(guī)則對錯誤概率的影響例1：二進(jìn)制對稱信道

01012.譯碼規(guī)則對錯誤概率的影響（續(xù)1）譯碼規(guī)則1：信道譯碼器收到符號“0”——>譯為“0”

信道譯碼器收到符號“1”——>譯為“1”

正確譯碼概率0.1，錯誤譯碼概率01012.譯碼規(guī)則對錯誤概率的影響（續(xù)2）譯碼規(guī)則2：信道譯碼器收到符號“0”——>譯為“1”

信道譯碼器收到符號“1”——>譯為“0”

正確譯碼概率0.9，錯誤譯碼概率定義4.1設(shè)信道的輸入符號集為，輸出符號集為。若對每一個輸出符號都有一個確定的函數(shù)，使對應(yīng)于唯一的一個輸入符號，則稱這樣的一個函數(shù)為譯碼規(guī)則，記為3.譯碼規(guī)則XYx1x2xry1y2ysp(yj|xi)3.譯碼規(guī)則（續(xù)1）信道共有rs種譯碼規(guī)則譯碼規(guī)則例：01013.譯碼規(guī)則（續(xù)2）3.譯碼規(guī)則（續(xù)3）例2：設(shè)一個信道的信道矩陣為，根據(jù)此信道矩陣，設(shè)計譯碼規(guī)則。解：譯碼規(guī)則A譯碼規(guī)則B

對于有r個輸入符號，s個輸出符號的信道，總共可以設(shè)計出種譯碼規(guī)則，到底哪一種譯碼規(guī)則最好？依據(jù)什么標(biāo)準(zhǔn)來選擇譯碼規(guī)則？問題：3.譯碼規(guī)則（續(xù)4）4.錯誤譯碼概率設(shè)譯碼規(guī)則為當(dāng)輸入符號是xi時，譯碼正確當(dāng)輸入符號為除xi以外的(r-1)種符號時，譯碼錯誤正確譯碼的概率：錯誤譯碼的概率：4.錯誤譯碼概率（續(xù)1）

平均正確譯碼概率：

平均錯誤譯碼概率：5.兩種重要的譯碼規(guī)則

為提高規(guī)則通信的可靠性，所采用的譯碼應(yīng)當(dāng)使平均錯誤譯碼概率最小。----

最大后驗概率譯碼規(guī)則

最常用的譯碼規(guī)則，包括：

極大似然譯碼規(guī)則

最大后驗概率譯碼規(guī)則5.兩種重要的譯碼規(guī)則（續(xù)1）(1)最大后驗概率譯碼規(guī)則

已知：

當(dāng)求和項中的每一項都達(dá)到最小值時，就最小。要最小。要最大。定義4.2令，，而應(yīng)滿足條件5.兩種重要的譯碼規(guī)則（續(xù)2）稱滿足上述條件的譯碼函數(shù)對應(yīng)的譯碼規(guī)則為最大后驗概率譯碼規(guī)則。5.兩種重要的譯碼規(guī)則（續(xù)3）5.兩種重要的譯碼規(guī)則（續(xù)4）5.兩種重要的譯碼規(guī)則（續(xù)5）問題：

最大后驗概率通常是未知的，使用不方便。我們能否推導(dǎo)出更便于使用的譯碼規(guī)則?5.兩種重要的譯碼規(guī)則（續(xù)6）當(dāng)輸入符號等概分布時(2)極大似然譯碼規(guī)則5.兩種重要的譯碼規(guī)則（續(xù)7）1)當(dāng)輸入符號等概分布時，采用極大似然譯碼準(zhǔn)則等價于最大后驗概率準(zhǔn)則。2)當(dāng)輸入符號不等概分布或先驗概率未知時，采用極大似然譯碼準(zhǔn)則不一定使最小。

關(guān)于極大似然譯碼準(zhǔn)則：5.兩種重要的譯碼規(guī)則（續(xù)8）當(dāng)輸入符號等概分布時5.兩種重要的譯碼規(guī)則（續(xù)9）例3：設(shè)信道矩陣為，且輸入符號等概分布，即，求譯碼規(guī)則和平均錯誤譯碼概率。5.兩種重要的譯碼規(guī)則（續(xù)10）解：因為輸入符號為等概分布，所以由最大似然譯碼規(guī)則可得譯碼規(guī)則5.兩種重要的譯碼規(guī)則（續(xù)11）譯碼規(guī)則A譯碼規(guī)則B例4.3假設(shè)輸入等概，求以下兩種譯碼規(guī)則的平均錯誤譯碼概率。5.兩種重要的譯碼規(guī)則（續(xù)12）5.兩種重要的譯碼規(guī)則（續(xù)13）5.兩種重要的譯碼規(guī)則（續(xù)14）6.Fano不等式

定理6.1

平均錯誤概率與信道疑義度H(X|Y)滿足不等式：

雖然PE與譯碼規(guī)則有關(guān)，但是不管采用什么譯碼規(guī)則該不等式都是成立的。費諾不等式物理意義：接收到Y(jié)后對X的平均不確定性可分為兩部分，第一部分是指接收到Y(jié)后是否產(chǎn)生錯誤的不確定性H(PE)；第二部分表示當(dāng)錯誤發(fā)生后，到底是哪個輸入符號發(fā)送引起的錯誤的最大不確定性，它是(r-1)（減去一個正確的符號）個符號不確定性的最大值log(r-1)與PE的乘積。選擇最佳譯碼規(guī)則只能使錯誤概率有限地減少，無法任意小。要想進(jìn)一步減少PE，必須優(yōu)選信道編碼方法。01017.簡單重復(fù)編碼7.簡單重復(fù)編碼（續(xù)1）二元對稱信道的三次擴(kuò)展信道M=2由最大似然譯碼規(guī)則，可得7.簡單重復(fù)編碼（續(xù)2）自動糾正一位錯7.簡單重復(fù)編碼（續(xù)3）

在輸入符號集（M個符號）等概的條件下，每個符號平均攜帶的最大信息量是。當(dāng)用n個碼元符號來傳輸M個信源符號時，每個碼符號攜帶的平均信息量，即信道信息傳輸率為：

不重復(fù)編碼時(n=1)，重復(fù)編碼時(n=3)，

n=1, R=1,

n=3,R=1/3,

n=5, R=1/5,

n=7, R=1/7,

n=9, R=1/9,

n=11,R=1/11,

增加重復(fù)次數(shù)n，可使減小很多，但信息傳輸率R也減少很多。7.簡單重復(fù)編碼（續(xù)4）7.簡單重復(fù)編碼（續(xù)5）

如果在擴(kuò)展信源的

個碼符號序列中任意選擇M個序列作為信道的輸入，以代表M個信源消息。

因此若選擇“000”和“001”代表消息“0”和“1”，則7.簡單重復(fù)編碼（續(xù)6）

有沒有一種很簡便的方法，幫我們選擇平均錯誤概率最小的M個序列？7.簡單重復(fù)編碼（續(xù)7）8.漢明距離1）漢明距離2）碼的最小距離3）漢明距離與極大似然譯碼準(zhǔn)則8.漢明距離（續(xù)1）定義4.4設(shè)

和

表示兩個長度為n的碼符號序列，定義稱為碼字和之間的漢明距離。1）漢明距離8.漢明距離（續(xù)2）例4：求下面兩個碼字之間的漢明距離。解：8.漢明距離（續(xù)3）定義4.5在二元碼C中，任意兩個碼字之間的漢明距離的最小值，被稱為碼C的最小距離：2）碼的最小距離碼的最小漢明距離為碼的最小漢明距離為8.漢明距離（續(xù)4）例5：設(shè)有n=3的兩組碼，分別求它們的最小漢明距離。解：

碼1碼2碼3碼4碼5碼6000111000001000011101110000001100010000000110110111110100000010100111001011101118.漢明距離（續(xù)5）

碼1碼2碼3碼4碼5碼字00011100001110111000000110001000000011011011111010000001010011100101110111消息數(shù)M24448

信息傳輸率R1/32/32/32/51碼的最小距離32131平均錯誤概率（最大似然譯碼）8.漢明距離（續(xù)7）結(jié)論：

碼的最小距離越大，平均譯碼錯誤概率越小。

設(shè)

和

表示兩個長度為n的碼符號序列，為信道的輸入，為信道的輸出。和的漢明距離為D。8.漢明距離（續(xù)8）3)漢明距離與極大似然譯碼準(zhǔn)則對于離散平穩(wěn)無記憶二元對稱信道，有

通常情況下，，，D越小，就越大。8.漢明距離（續(xù)9）

根據(jù)極大似然譯碼準(zhǔn)則，極大似然譯碼準(zhǔn)則就等價于，當(dāng)接收到一個長為n的碼符號序列時，在輸入碼字集中尋找一個，使最小距離譯碼準(zhǔn)則信道編碼器：將信源編碼后的符號加上冗余符號，提高傳輸?shù)目煽啃浴?.信道編碼概述1.有噪信道編碼定理定理4.2（香農(nóng)第二定理）設(shè)有一離散無記憶平穩(wěn)信道，其信道容量為C，只要待傳送的信息傳輸率R<C，當(dāng)碼長n足夠大時，則至少存在一種編碼，使譯碼錯誤概率任意小。1.有噪信道編碼定理（續(xù)1）說明：1)信息傳輸速率

2)香農(nóng)第二定理僅指出了滿足這種要求的信道編碼的存在性，沒有給出具體的編碼方法。1.有噪信道編碼定理（續(xù)2）定理4.3（有噪信道編碼逆定理）

設(shè)有一離散無記憶平穩(wěn)信道，其信道容量為C，如果信息傳輸率R>C，即，則無論碼長n取多大，也不可能使譯碼錯誤概率任意小。1.有噪信道編碼定理（續(xù)3）

信道容量是在信道中可靠傳輸信息的最大信息傳輸率。結(jié)論：糾錯編碼1糾錯碼的分類2糾錯碼的基本概念3線性分組碼4漢明碼5循環(huán)碼*6卷積碼概述

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

近世代數(shù)是信道編碼理論用到的最重要的數(shù)學(xué)工具，它包括群論、環(huán)論、域論、格論、線性代數(shù)等許多分支。

廣義信道編碼包括：調(diào)制、成形濾波、擴(kuò)頻、上下變頻等。糾錯編碼是提高傳輸可靠性的最主要的措施之一。概述

糾錯編碼的基本思路：根據(jù)一定的規(guī)律在待發(fā)送的信息碼元中人為的加入一些冗余碼元，這些冗余碼元與信息碼元之間以某種確定的規(guī)則相互關(guān)聯(lián)（約束）。在接收端按照既定的規(guī)則檢驗信息碼元與監(jiān)督碼元之間的關(guān)系。如果傳輸過程出錯，則信息碼元與監(jiān)督碼元之間的關(guān)系將受到破壞，從而可以發(fā)現(xiàn)錯誤乃至糾正錯誤。概述N概述

mmsgCcodeR

NoisycodeNewmsg干擾一般分為兩種形式：一是隨機(jī)噪聲，它主要來源于設(shè)備的熱噪聲和散彈噪聲以及傳播媒介的熱噪聲，它是通信系統(tǒng)中的主要噪聲；二是脈沖干擾和信道衰落，它的特點是突發(fā)出現(xiàn)，主要來源于雷電、通電開關(guān)、負(fù)荷突變或設(shè)備故障等。概述信道可分為三類：1.只產(chǎn)生隨機(jī)錯誤的信道稱為隨機(jī)信道。比如衛(wèi)星信道、同軸電纜、光纜信道以及大多數(shù)微波中繼信道。2.產(chǎn)生突發(fā)錯誤的信道稱為突發(fā)信道。實際的短波信道、移動通信信道、由于擦傷造成成串差錯的光盤和磁盤，均為這一類信道。3.有些實際信道既有隨機(jī)錯誤又有突發(fā)錯誤，稱為混合信道。

根據(jù)不同的信道類型設(shè)計的信道編碼分為糾隨機(jī)錯誤碼、糾突發(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ā)出的信息重新傳送一次，直到接收端認(rèn)為正確地收到信息為止。

(1)反饋重傳(ARQ)檢錯編碼信道檢錯譯碼反饋概述(2)前向糾錯(FEC)糾錯編碼信道糾錯譯碼

發(fā)送端發(fā)出的是具有糾錯能力的糾錯碼，接收端根據(jù)譯碼規(guī)則進(jìn)行譯碼。當(dāng)誤碼個數(shù)在碼的糾錯能力范圍內(nèi)時，譯碼器可以自動糾正錯誤。概述特點：1）前向糾錯方式不需要反饋信道，特別適合于只能提供單向信道的場合。2）由于能自動糾錯，不要求檢錯重發(fā)，因而延時小，實時性好。3）隨著糾錯能力的增強(qiáng)，譯碼設(shè)備也變得復(fù)雜。概述(3)混合糾錯

對發(fā)送端進(jìn)行適當(dāng)?shù)木幋a。當(dāng)錯誤不嚴(yán)重，在碼的糾錯能力范圍之內(nèi)時，采用自動糾錯；當(dāng)產(chǎn)生的差錯超出碼的糾錯能力范圍時，通過反饋系統(tǒng)要求發(fā)端重發(fā)。概述(1)按功能分：檢錯碼：僅能檢測誤碼糾錯碼：可糾正誤碼糾刪碼：兼糾錯和檢錯能力(2)按信息碼元與監(jiān)督碼元之間的檢驗關(guān)系分：線性碼：滿足線性關(guān)系非線性碼：不存在線性關(guān)系糾錯碼1糾錯碼的分類(3)按信息碼元與監(jiān)督碼元之間的約束方式不同分：

分組碼：本碼組的監(jiān)督碼元僅和本碼組的信息元相關(guān)。

樹碼：本碼組的監(jiān)督碼元不僅和本碼組的信息元相關(guān)，而且與前面碼組的信息碼元有關(guān)。如果是線性關(guān)系則稱為卷積碼。(4)按信息碼元在編碼后是否保持原形式不變：系統(tǒng)碼：信息碼元與監(jiān)督碼元在分組內(nèi)有確定位置，編碼后的信息碼元保持不變；非系統(tǒng)碼：信息位打亂，與編碼前不同。1糾錯碼的分類(5)按糾正差錯的類型可分為：

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

1糾錯碼的分類分組碼：記作（n,k）其中n>kr=n-k效率η=k/n=k/(k+r)卷積碼：效率η=k/n=k/(k+r)

分組碼的表示方法：（二元分組碼）信息碼組由k

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

個不同的信息碼組；附加

個校驗碼元（校驗位或監(jiān)督位），每個校驗碼元是該信息碼組的某些信息碼元模2和；編碼器輸出長度為n的碼字；碼字的數(shù)目共有2k

；這2k

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

分組碼；2糾錯碼的基本概念對二進(jìn)制(n,k)線性分組碼，合法碼字?jǐn)?shù)為2k，可用編碼空間的序列數(shù)為2n個。許用序列，禁用序列任一種2k信息集合到二進(jìn)制序列集合2n的映射都是一種(n,k)碼，因此總共可能的編碼方案有種。2糾錯碼的基本概念

信息傳輸率（碼率）

編碼效率發(fā)現(xiàn)或構(gòu)造好碼是信道編碼研究的主要問題。線性分組碼是最具實用價值的一類碼，比如漢明碼、循環(huán)碼、BCH碼、RS碼等。2糾錯碼的基本概念2糾錯碼的基本概念對信道編碼的一般要求是：①糾錯檢錯能力強(qiáng)；②信息傳輸率高；③編碼規(guī)律簡單，實現(xiàn)設(shè)備簡單且費用合理；④與信道的差錯統(tǒng)計特性相匹配。漢明距離漢明距離滿足距離公理(1)

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

碼C的最小距離線性分組碼的最小距離等于非零碼字的最小重量。2糾錯碼的基本概念

碼1碼2碼3碼4碼5碼6000111000001000011101110000001100010000000110110111110100000010100111001011101112糾錯碼的基本概念3線性分組碼3.1校驗矩陣與生成矩陣(1)校驗矩陣3線性分組碼

被稱為校驗矩陣。對線性分組碼，校驗矩陣為維矩陣。對于系統(tǒng)碼，校驗矩陣可以表示為其中為維矩陣，為維單位矩陣。3線性分組碼由校驗方程，得到(2)生成矩陣3線性分組碼令3線性分組碼其中為維矩陣，為維單位矩陣。

被稱為生成矩陣。對線性分組碼，生成矩陣為維矩陣。對于系統(tǒng)碼，生成矩陣可以表示為3線性分組碼令，則把生成矩陣的每一行用一個行向量來表示，則生成矩陣可以表示為3線性分組碼由于生成矩陣G的每一行都是一個碼字，所以G的每行都滿足

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

求生成的線性分組碼3線性分組碼3線性分組碼3.2線性分組碼的糾、檢錯能力

對于一個二進(jìn)制對稱信道，當(dāng)輸入為2k個等可能的n長碼字，則最大后驗概率準(zhǔn)則等效于最小漢明距離譯碼準(zhǔn)則。3線性分組碼關(guān)于碼的最小距離與糾、檢錯能力的關(guān)系有以下結(jié)論：對于（n，k）線性分組碼，設(shè)為碼的最小距離則（１）這組碼有糾正u個錯誤的充要條件是uu2u+13線性分組碼lll+1（２）具有檢測l個錯誤的充要條件是3線性分組碼ulu+l+1（３）具有糾正u個錯誤，同時可以發(fā)現(xiàn)l個錯誤的充分必要條件為3線性分組碼(n-k)碼的糾錯能力u與碼字的長度n和信息碼的長度k滿足以下關(guān)系：3線性分組碼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線性分組碼3.4線性分組碼的伴隨式R=C+EE=[e1

e2…en]1)，說明R是一個碼字;2)，說明R不是碼字，傳輸過程產(chǎn)生了誤碼。3線性分組碼例：某（5,2）系統(tǒng)線性碼的生成矩陣是設(shè)收碼是，問它是否是碼字。

3線性分組碼（其中Hi表示H的列向量）

令

則3線性分組碼

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

3線性分組碼3線性分組碼檢錯碼一致監(jiān)督碼（奇偶校驗碼）1．檢錯原理偶一致監(jiān)督檢錯能力：奇數(shù)個錯誤。奇一致監(jiān)督例：（4,3）偶校驗碼是一個（4,3）線性分組碼，其生成矩陣為一致監(jiān)督碼一致監(jiān)督碼2．漏檢概率當(dāng)n為偶數(shù)時：當(dāng)n為奇數(shù)時：一致監(jiān)督碼3．編碼效率

（5，4）=80%（9，8）=90%編碼效率的提高導(dǎo)致漏檢概率的提高。所以要在兩者之間平衡。定比碼1．五三定比碼主要用于中文電報碼長為5，碼中包含“1”的個數(shù)為3。許用碼字為10，禁用碼字22個。漏檢概率：編碼效率：漏檢概率五三定比碼：差錯碼元數(shù)為奇數(shù)，則必能發(fā)現(xiàn)錯誤

只有差錯碼元數(shù)為偶數(shù)，且10與01的數(shù)目相等時，才不能發(fā)現(xiàn)設(shè)碼元錯誤概率pe=10-4發(fā)生一對錯誤，而不能發(fā)現(xiàn)錯誤的概率：發(fā)生兩對錯誤，而不能發(fā)現(xiàn)錯誤的概率：2．七三定比碼主要用于英文電報碼長為5，碼中包含“1”的個數(shù)為3。許用碼字為35，禁用碼字93個。漏檢概率：編碼效率：ARQ系統(tǒng)（自動請求重發(fā)系統(tǒng)）ARQ系統(tǒng)：反饋糾錯方式，須具備的條件：1）具備反向信道2）發(fā)送端須具有寄存器3）收、發(fā)端須具備統(tǒng)一的重發(fā)信息控制設(shè)備ARQ系統(tǒng)的優(yōu)點：設(shè)備比前向糾錯系統(tǒng)簡單，具有自適應(yīng)特點;可以糾成片的錯誤。ARQ系統(tǒng)的缺點：不適用于廣播方式，僅適用于單向信道的簡單糾錯碼正反碼1.編碼規(guī)則：

10位，前5位是信息位，后5位是監(jiān)督位。信息位：12345監(jiān)督位：ABCDE12345ABCDEA監(jiān)督2345B監(jiān)督1345偶數(shù)一致監(jiān)督：C監(jiān)督1245D監(jiān)督1235E監(jiān)督1234例：1011001001（重復(fù)）

0011000110（反碼）2．糾錯原理無錯=全0信息位出1錯=單0監(jiān)督位出1錯=單1正反碼檢糾錯能力：長度為10的正反碼有糾正一位錯碼的能力，并能檢測出全部兩位以下的錯誤，和大部分兩位以上的錯誤。編碼效率：5/10=1/2若（n，k）線性分組碼能夠糾正u個錯誤，則其校驗位的數(shù)目必須滿足4漢明碼

上式等號成立則稱為完備碼如果是能糾正一位錯誤的完備碼則完備碼具有下述特性：（1）以每個發(fā)送碼字為球心，以u為半徑畫一個球，那么每一個接收碼字都落在其中一個球中，因此接收碼字與發(fā)送碼字的距離至多為u；（2）所有差錯數(shù)小于等于u的接收碼字都能得到糾正；（3）差錯數(shù)大于等于u+1的接收碼字，因為落在另一個球內(nèi)被糾正為其他的發(fā)送碼字。完備碼并不多見，我們知道的有u=1的漢明碼、u=3的高萊碼，以及(n,1)中n為奇數(shù)的重復(fù)碼等。4漢明碼

01000110100111完備碼非完備碼00011100000101010101100000011010000000001000100010010000000111001101101011000111101001001011110101110111001011110111...1101011010...4漢明碼

漢明碼是一種能夠糾正單個錯誤的完備碼。漢明碼最小碼距設(shè)監(jiān)督碼共有r位，對于漢明碼必然有。通常漢明碼可以表示成。4漢明碼

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

漢明碼監(jiān)督矩陣構(gòu)成的兩種方式：按r位的二進(jìn)制數(shù)的自然順序從左到右排列（不包括全0列）。當(dāng)發(fā)生可糾的單個錯誤時，伴隨式為H

陣中對應(yīng)的列，譯碼比較方便。構(gòu)成H陣的標(biāo)準(zhǔn)形式，

。非標(biāo)準(zhǔn)形式的監(jiān)督矩陣可以通過列置換變成標(biāo)準(zhǔn)形式的監(jiān)督矩陣，糾錯能力保持不變。4漢明碼

例：構(gòu)造一個r=3的二元（7,4）漢明碼解：r=3的漢明碼，列置換4漢明碼

4漢明碼

信息比特碼字（循環(huán)1）信息比特碼字（循環(huán)2）信息比特碼字000100100101011010001011110000010110010110010110001100011000101101100011000100011010001111001101011011110001110101001110111010100111010100111101001111010000001111000000011111114漢明碼

如果給漢明碼添加一位奇偶校驗位，可得到擴(kuò)展?jié)h明碼：信息位保持不變，監(jiān)督位增加一位。最小碼距，可糾正一位錯誤，同時發(fā)現(xiàn)兩位錯誤。擴(kuò)展?jié)h明碼的監(jiān)督方程：4漢明碼

5

循環(huán)碼信息比特碼字（循環(huán)1）信息比特碼字（循環(huán)2）信息比特碼字00010010010101101000101111000001011001011001011000110001100010110110001100010001101000111100110101101111000111010100111011101010011101010011110100111101000000111100000001111111（1）(7,4)漢明碼。狹義漢明碼。

校驗子監(jiān)督矩陣校驗表：S100111100S201011010S301101001錯誤無錯X’1X’2X’3X’4X’5X’6X’7（1）(7,4)漢明碼。狹義漢明碼。

校驗子監(jiān)督矩陣校驗表：S100001111S200110011S301010101錯誤無錯X’1X’2X’3X’4X’5X’6X’7循環(huán)碼是線性分組碼的一個重要子集。循環(huán)碼除了具有線性分組碼的一般性質(zhì)外，還具有循環(huán)性：循環(huán)碼中任一碼字經(jīng)過循環(huán)移位后，所得到的碼字仍然是該碼的碼字。循環(huán)碼有嚴(yán)密的代數(shù)學(xué)理論基礎(chǔ)，檢錯和糾錯能力較強(qiáng)，而且編碼和解碼設(shè)備都不太復(fù)雜。5

循環(huán)碼5

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

2)X僅是碼元位置的標(biāo)記。我們并不關(guān)心X的取值。設(shè)循環(huán)碼的碼字為，用碼多項式表示為碼字（1100101）可以表示為：

…5

循環(huán)碼循環(huán)碼的循環(huán)特性可