第8章糾錯(cuò)編碼8.1糾錯(cuò)編碼的基本概念8.2糾錯(cuò)編碼分類8.3線性分組碼8.4循環(huán)碼8.1糾錯(cuò)編碼的基本概念信源編碼提高數(shù)字信號有效性將信源的模擬信號轉(zhuǎn)變?yōu)閿?shù)字信號 降低數(shù)碼率,壓縮傳輸頻帶(數(shù)據(jù)壓縮)信道編碼提高數(shù)字通信可靠性

數(shù)字信號在信道的傳輸過程中,由于實(shí)際信道的傳輸特性不理想以及存在加性噪聲,在接收端往往會產(chǎn)生誤碼。8.1糾錯(cuò)編碼的基本概念目的在于提高通信（或存儲）的可靠性，減低誤碼率。假設(shè)信源信息是二進(jìn)制數(shù)字序列，將信源編碼其的輸出序列構(gòu)成長度為n的段，記為CC=c1,c2,…,cn8.1糾錯(cuò)編碼的基本概念設(shè)有m個(gè)不同的信息序列，每個(gè)不同的序列由k（k<n)位（信息位），它由碼元組成。[C]為編碼器的輸出，稱為碼字矢量，它由n位碼元組成，其中有k位信息元，r=n-k位監(jiān)督元。8.1糾錯(cuò)編碼的基本概念

對于二元符號表上的分組碼C，由表示消息序列的長度為n的m個(gè)二元序列構(gòu)成的集合，稱為二元分組碼。

對于2k個(gè)n長碼字全體構(gòu)成的分組碼，其碼字中的k位稱為信息位，n-k位稱為校驗(yàn)位或監(jiān)督位。線性分組碼：監(jiān)督元與信息元之間的關(guān)系可用一組線性方程組來描述的(n,k)分組碼。8.1糾錯(cuò)編碼的基本概念編碼效率：一個(gè)組中信息所占的比重k：信息碼元的數(shù)目n：編碼組碼元的總數(shù)目n=k+rr：監(jiān)督碼元的數(shù)目8.1糾錯(cuò)編碼的基本概念

若（n，k）分組碼中k個(gè)信息位同原始k個(gè)信息位相同，且位于n長碼字的前（或后）k位，為校驗(yàn)位位于其后（或前），則稱該分組碼為系統(tǒng)碼，否則為非系統(tǒng)碼。

兩個(gè)序列之間的漢明距離定義為兩個(gè)序列之間對應(yīng)位不同的位數(shù)。8.1糾錯(cuò)編碼的基本概念例如：α和β為碼組X中的兩個(gè)不同碼字，X為一個(gè)長度為N的二元碼組，其中：

α=[a1,a2,……aN]ai∈{0,1}β=[b1,b2,……bN]bi∈{0,1}

則α與β的漢明距離為：

d=0表明為全同碼，d=N表明為全異碼8.1糾錯(cuò)編碼的基本概念如果用模2加法的概念，有模2加法等同于“異或”運(yùn)算8.1糾錯(cuò)編碼的基本概念碼的最小漢明距離是衡量碼的糾、檢錯(cuò)能力的重要參數(shù)，碼的最小距離越大，其糾、檢錯(cuò)能力越強(qiáng)。最小碼距：在一個(gè)碼字集合中，任何兩個(gè)碼字之間的漢明距離組成一個(gè)元素集合，D(α,β),這個(gè)集合中的最小值稱為這個(gè)碼字集合的最小漢明距離，簡稱最小碼距，記為：dmin。dmin=min{d(α,β)α,β∈X

α≠β}8.1糾錯(cuò)編碼的基本概念

對于碼C中的某一碼字，其非零元素的個(gè)數(shù)稱為該碼字的漢明重量。8.2糾錯(cuò)編碼分類8.2糾錯(cuò)編碼分類對不同的信道需要設(shè)計(jì)不同類型的信道編碼方案，按照信道特性進(jìn)行劃分，信道編碼可分為：以糾獨(dú)立隨機(jī)差錯(cuò)為主的信道編碼、以糾突發(fā)差錯(cuò)為主的信道編碼和糾混合差錯(cuò)的信道編碼。從功能上看，信道編碼可分為檢錯(cuò)(可以發(fā)現(xiàn)錯(cuò)誤)碼與糾錯(cuò)(不僅能發(fā)現(xiàn)而且能自動糾正)碼兩類，糾錯(cuò)碼一定能檢錯(cuò)，檢錯(cuò)碼不一定能糾錯(cuò)，平常所說的糾錯(cuò)碼是兩者的統(tǒng)稱。

8.2糾錯(cuò)編碼分類根據(jù)信息碼元與監(jiān)督碼元之間的關(guān)系，糾錯(cuò)碼分為線性碼和非線性碼。

線性碼——信息碼元與監(jiān)督碼元之間呈線性關(guān)系，它們的關(guān)系可用一組線性代數(shù)方程聯(lián)系起來。非線性碼——信息碼元與監(jiān)督校元之間不存在線性關(guān)系。

8.2糾錯(cuò)編碼分類按照對信息碼元處理的方法的不同，糾錯(cuò)碼分為分組碼和卷積碼。

分組碼----把信息序列以每k個(gè)碼元分組，然后把每組k個(gè)信息元按一定規(guī)律產(chǎn)生r個(gè)多余的監(jiān)督碼元，輸出序列每組長為n=k+r，則每一碼字的r個(gè)校驗(yàn)元只與本碼字的k個(gè)信息位有關(guān)，與別的碼字的信息位無關(guān)，通常記分組碼為(n,k)。

8.2糾錯(cuò)編碼分類其中分組碼又可分循環(huán)碼和非循環(huán)碼：對循環(huán)碼而言，其碼書的特點(diǎn)是，若將其全部碼字分成若干組，則每組中任一碼字中碼元循環(huán)移位后仍是這組的碼字；對非循環(huán)碼來說，任一碼字中的碼元循環(huán)移位后不一定再是該碼書中的碼字。8.2糾錯(cuò)編碼分類

卷積碼----把信息序列以每k0(通常較小)個(gè)碼元分段，編碼器輸出該段的監(jiān)督碼元r=n-k0

不但與本段的k0個(gè)信息元有關(guān)，而且還與其前面L段的信息碼元有關(guān)，故記卷積碼為(n,k0,L)。按照每個(gè)碼元的取值來分，可有二元碼和多元碼。由于目前的傳輸或存儲系統(tǒng)大都采用二進(jìn)制的數(shù)字系統(tǒng)，所以一般提到的糾錯(cuò)碼都是指二元碼。

8.2糾錯(cuò)編碼分類1.檢錯(cuò)與糾錯(cuò)方式自動請求重發(fā)方式----用于檢錯(cuò)的糾錯(cuò)碼在譯碼器輸出端給出當(dāng)前碼字傳輸是否可能出錯(cuò)的指示，當(dāng)有錯(cuò)時(shí)按某種協(xié)議通過一個(gè)反向信道請求發(fā)送端重傳已發(fā)送的全部或部分碼字，這種糾錯(cuò)碼的應(yīng)用方式稱為自動請求重發(fā)方式(ARQ，Automatic-Repeat-reQuest)。8.2糾錯(cuò)編碼分類前向糾錯(cuò)方式----用于糾錯(cuò)的糾錯(cuò)碼在譯碼器輸出端總要輸出一個(gè)碼字或是否出錯(cuò)的標(biāo)志，這種糾錯(cuò)碼的應(yīng)用方式稱為前向糾錯(cuò)方式(FEC，F(xiàn)orward-errorcontrol)。另外用于檢錯(cuò)與糾錯(cuò)的方式還有混合糾錯(cuò)(HEC，HybridErrorCorrection)。如圖所示為上述幾種檢錯(cuò)與糾錯(cuò)方式示意圖，圖中有斜線的方框表示在該端檢出錯(cuò)誤。8.2糾錯(cuò)編碼分類8.2糾錯(cuò)編碼分類ARQ方式：發(fā)送端用編碼器對發(fā)送數(shù)據(jù)進(jìn)行差錯(cuò)編碼，通過正向信道送到接收端，而接收端經(jīng)譯碼器處理后只是檢測有無差錯(cuò)，不作自動糾正。如檢測到差錯(cuò)，則利用反向信道反饋信號，請求發(fā)送端重發(fā)有錯(cuò)的數(shù)據(jù)單元，直到接收端檢測不到差錯(cuò)為止。

8.2糾錯(cuò)編碼分類FEC方式：發(fā)送端用編碼器對發(fā)送數(shù)據(jù)進(jìn)行差錯(cuò)編碼，在接收端用譯碼器對接收到的數(shù)據(jù)進(jìn)行譯碼后檢測有無差錯(cuò)，通過按預(yù)定規(guī)則的運(yùn)算，如檢測到差錯(cuò)，則確定差錯(cuò)的具體位置和性質(zhì)，自動加以糾正，故稱為“前向糾錯(cuò)”。8.2糾錯(cuò)編碼分類HEC方式：是檢錯(cuò)重發(fā)和前向糾錯(cuò)兩種方式的混合。發(fā)送端用編碼器對發(fā)送數(shù)據(jù)進(jìn)行便于檢錯(cuò)和糾錯(cuò)的編碼，通過正向信道送到接收端，接收端對少量的接收差錯(cuò)進(jìn)行自動前向糾正，而對超出糾正能力的差錯(cuò)則通過反饋重發(fā)方式加以糾正，所以是一種糾檢結(jié)合的混合方式。

定理1若糾錯(cuò)碼的最小距離為dmin，那么如下三個(gè)結(jié)論的任何一個(gè)結(jié)論獨(dú)立成立：①若要發(fā)現(xiàn)e個(gè)獨(dú)立差錯(cuò)，則要求最小碼距

②若要糾正t個(gè)獨(dú)立差錯(cuò)，則要求最小碼距

③若要求發(fā)現(xiàn)e個(gè)同時(shí)又糾正t個(gè)獨(dú)立差錯(cuò)，則8.3線性分組碼m=(mk-1,…,m1,m0)c=(cn-1,…,c1,c0)碼字c消息m(n,k)分組編碼器

碼集C能否構(gòu)成n維n重矢量空間的一個(gè)k維n重子空間？如何尋找最佳的碼空間？qk個(gè)信息元組以什么算法一一對應(yīng)映射到碼空間。碼率－－編碼效率：Rc

=k/n

8.3線性分組碼為了敘述方便，以下認(rèn)為碼失、碼字、碼組是同義詞，對n重矢量、1n矩陣、行矢量等的數(shù)學(xué)表達(dá)式也不作嚴(yán)格區(qū)別。8.3線性分組碼設(shè)有等概出現(xiàn)的M組待傳信源消息，每組有k位，即。今加上r個(gè)多余位，使每組消息變成n=k+r位。而n位長的二進(jìn)制序列共有2n個(gè)，但由于信息組只有2k個(gè)，故有2n-2k個(gè)n位序列不是碼字。設(shè)碼字的形式為：8.3線性分組碼線性分組碼碼空間C是由k個(gè)線性無關(guān)的基底張成的k維n重子空間，碼空間的所有元素（即碼字）都可以寫成k個(gè)基底的線性組合，即這種線性組合特性正是線性分組碼名稱的來歷。顯然，研究線性分組碼的關(guān)鍵是研究基底、子空間和映射規(guī)則，如圖所示

8.3線性分組碼Hn-k維n重對偶空間Dk維k重信息組空間mk維n重碼空間cGn維n重空間Vn8.3線性分組碼用gi表示第i個(gè)基底并寫成矩陣再將k個(gè)基底排列成k行n列的G矩陣8.3線性分組碼碼空間的所有元素（即碼字）都可以寫成k個(gè)基底的線性組合。由于k個(gè)基底即G的k個(gè)行矢量線性無關(guān)，矩陣G的秩一定等于k。當(dāng)信息元確定后，碼字僅由G矩陣決定，因此我們稱這k×n

矩陣G為該(n,k)線性分組碼的生成矩陣。8.3線性分組碼1.生成矩陣G(k×n)的特點(diǎn)想要保證(n,k)線性分組碼能夠構(gòu)成k維n重子空間，G

的k個(gè)行矢量gk-1,…,g1,g0必須是線性無關(guān)的，只有這樣才符合作為基底的條件。由于基底不是唯一的，所以G也就不是唯一的。不同的基底有可能生成同一碼集，但因編碼涉及碼集和映射兩個(gè)因素，碼集一樣而映射方法不同也不能說是同樣的碼。8.3線性分組碼2.系統(tǒng)形式的生成矩陣

(n,k)碼的任何生成矩陣都可以通過行運(yùn)算（以及列置換）簡化成“系統(tǒng)形式”。

Ik是k×k單位矩陣，P是k×(n-k)矩陣。

8.3線性分組碼3.生成的碼字C

前k位由單位矩陣Ik決定，等于把信息組m原封不動搬到碼字的前k位；其余的n-k位叫冗余位或一致校驗(yàn)位，是前k個(gè)信息位的線性組合。這樣生成的（n,k）碼叫做系統(tǒng)碼。若生成矩陣G不具備系統(tǒng)形式，則生成的碼叫做非系統(tǒng)碼。系統(tǒng)化不改變碼集，只是改變了映射規(guī)則。8.3線性分組碼4.系統(tǒng)碼若通過行運(yùn)算和列置換能將兩個(gè)生成矩陣G互等，則稱這兩個(gè)G等效。非系統(tǒng)碼的G可通過運(yùn)算轉(zhuǎn)變?yōu)橄到y(tǒng)碼的G。等效的兩個(gè)G生成的兩個(gè)(n,k)線性碼也是等效的。因此，每個(gè)(n,k)線性碼都可以和一個(gè)系統(tǒng)的(n,k)線性碼等效。8.3線性分組碼5.空間構(gòu)成n維n重空間有相互正交的n個(gè)基底，選擇k個(gè)基底構(gòu)成碼空間C，選擇另外的(n-k)個(gè)基底構(gòu)成空間H，C和H是對偶的CHT＝0,GHT=0。8.3線性分組碼6.校驗(yàn)矩陣將H空間的n-k個(gè)基底排列起來可構(gòu)成一個(gè)(n-k)×n矩陣，稱為校驗(yàn)矩陣H。用來校驗(yàn)接收到的碼字是否是正確的；G是(n,k)碼的生成矩陣，H是它的校驗(yàn)矩陣；H是(n,n-k)對偶碼的生成矩陣，它的每一行是一個(gè)基底。G則是它的校驗(yàn)矩陣。8.3線性分組碼以(7,3)線性分組碼為例。信息位k=3，則校驗(yàn)元個(gè)數(shù)為r=n-k，設(shè)碼字為：,其中為信息元；為校驗(yàn)元。每個(gè)碼元取值為“0”或“1”。設(shè)某(7,3)線性分組碼各碼字的校驗(yàn)元與信息元之間的關(guān)系由下述方程決定：8.3線性分組碼

稱此方程為該（7,3）線性分組碼的校驗(yàn)方程，由于該碼系的所有碼字都按同一規(guī)則確定與校驗(yàn)，故又稱為一致校驗(yàn)方程。8.3線性分組碼如：信息組為101，即代入一致校驗(yàn)方程得：所以由信息組101編出的可送給信道傳輸?shù)摹⒕哂幸欢m錯(cuò)能力的碼字為：1010011。同理可求出與其他7個(gè)信息組相對應(yīng)的碼字見下表：信息組對應(yīng)碼字對應(yīng)碼字信息組000001010011111110101100011101001001110011101000000011101001101001101001110011108.3線性分組碼為了運(yùn)算方便，可將一致校驗(yàn)方程組寫成矩陣形式：8.3線性分組碼設(shè)則：或：（4×3）單位子陣8.3線性分組碼線性分組碼的一致生成矩陣與一致校驗(yàn)矩陣之間有著非常密切的關(guān)系，這種關(guān)系非常重要。下面說明它們的關(guān)系：由于生成矩陣G的每一行都是一個(gè)碼字，而或者8.3線性分組碼更進(jìn)一步：結(jié)論：(n,k)線性分組碼的一致生成矩陣G與一致校驗(yàn)矩陣H之間可方便地相互轉(zhuǎn)換。或者8.3線性分組碼例6.1(6,3)線性分組碼，其生成矩陣是8.3線性分組碼求：(1)計(jì)算碼集，列出信息組與碼字的映射關(guān)系。(2)將該碼系統(tǒng)化處理后，計(jì)算系統(tǒng)碼碼集并列出映射關(guān)系。(3)計(jì)算系統(tǒng)碼的校驗(yàn)矩陣H。若收碼r=[100110],檢驗(yàn)它是否碼字？(4)根據(jù)系統(tǒng)碼生成矩陣畫出編碼器電原理圖。8.3線性分組碼解(1)由得

令得信息碼字系統(tǒng)碼字000000000000000001 011101 001011010 110001 010110011 101100 011101100 111010 100111101 100111 101100110 001011 110001111010110 1110108.3線性分組碼(2)對G作行運(yùn)算，得系統(tǒng)化后的生成矩陣Gs

8.3線性分組碼(3)8.3線性分組碼(4)m0m1m2c0c1c2輸入輸出8.3線性分組碼

定理8.1任何最小距離dmin的線性分組碼，其檢錯(cuò)能力為（dmin-1）,糾錯(cuò)能力t為定理8.2線性分組碼的最小距離等于碼集中非零碼字的最小重量

dmin=min{w(Ci

)}CiC

及Ci

08.3線性分組碼

定理8.3(n,k)線性分組碼最小距離等于dmin的充要條件是：校驗(yàn)矩陣H中有（dmin-1)列線性無關(guān)。定理8.4(n,k)線性分組碼的最小距離必定小于等于(n-k+1)8.3線性分組碼

例：(7，4)線性碼

8.3線性分組碼

各列都不相同，任意2列之和不等于0，2列線性無關(guān)；任意2列之和一定等于矩陣中某一列，任意3列線性相關(guān)。所以該碼的最小距離為3，小于n-k

+1=4。

(n,k)線性碼最小距離dmin的上邊界是n-k+1。如果我們設(shè)計(jì)的(n,k)線性碼的dmin達(dá)到了n-k+1，就是達(dá)到了設(shè)計(jì)性能的極點(diǎn)。因此，dmin=n-k+1的碼稱為極大最小距離碼(MDC–MaximizedminimumDistanceCode)。

8.3線性分組碼

定義差錯(cuò)圖案E

二進(jìn)制碼中模2加與模2減是等同的，因此有E=R+C

及R=C+E

1.伴隨式S的定義因?yàn)镃HT=0所以RHT=(C+E)HT=CHT+EHT=EHT8.3線性分組碼

如果收碼無誤：必有R=C即E=0，則EHT=0RHT=0。如果收碼有誤：即E

0，則RHT=EHT0。在HT固定的前提下，RHT僅僅與差錯(cuò)圖案E有關(guān)，而與發(fā)送碼C無關(guān)。定義伴隨式S

S=(sn-k-1,…,s1,s0)=RHT=EHT

8.3線性分組碼

2.伴隨式S的意義從物理意義上看，伴隨式S并不反映發(fā)送的碼字是什么，而只是反映信道對碼字造成怎樣的干擾。差錯(cuò)圖案E是n重矢量，共有2n個(gè)可能的組合，而伴隨式S是(n-k)重矢量，只有2n-k個(gè)可能的組合，因此不同的差錯(cuò)圖案可能有相同的伴隨式。

8.3線性分組碼

接收端收到R后，因?yàn)橐阎狧T，可求出S=RHT

；如果能知道對應(yīng)的E，則通過C=R+E而求得C。

8.3線性分組碼

3.差錯(cuò)圖案E的求解可以通過解線性方程求解E：

8.3線性分組碼得到線性方程組：

sn-k-1=en-1h(n-k-1)(n-1)+…+e1h(n-k-1)1+e0h(n-k-1)0

s1=en-1h1(n-1)+…+e1h11+e0h10

s0=en-1h0(n-1)+…+e1h01+e0h008.3線性分組碼上述方程組中有n個(gè)未知數(shù)en-1,…e1,e0

，卻只有n-k個(gè)方程，可知方程組有多解。在有理數(shù)或?qū)崝?shù)域中，少一個(gè)方程就可能導(dǎo)致無限多個(gè)解，而在二元域中，少一個(gè)方程導(dǎo)致兩個(gè)解，少兩個(gè)方程四個(gè)解，以此類推，少n-(

n-k)=k個(gè)方程導(dǎo)致每個(gè)未知數(shù)有2k個(gè)解。到底取哪一個(gè)作為附加在收碼R上的差錯(cuò)圖案E的估值呢？8.3線性分組碼概率譯碼：把所有2k個(gè)解的重量(差錯(cuò)圖案E中1的個(gè)數(shù))作比較，選擇其中最輕者作為E的估值。該方法概念上很簡單但計(jì)算效率不高。依據(jù)：若BSC信道的差錯(cuò)概率是p，則長度n的碼中錯(cuò)誤概率：8.3線性分組碼0個(gè)錯(cuò)1個(gè)錯(cuò)2個(gè)錯(cuò)…n個(gè)錯(cuò)

(1-p)n

p(1-p)n-1

p2(1-p)n-2

pn

>>>>>>…>>由于p<<1，出錯(cuò)越少的情況，發(fā)生概率越大，E的重量越輕，所以該譯碼方法實(shí)際上體現(xiàn)了最小距離譯碼準(zhǔn)則，即最大似然譯碼。8.3線性分組碼方法：(1)按最可能出現(xiàn)的2r個(gè)差錯(cuò)圖案E，計(jì)算相應(yīng)的伴隨式S，并構(gòu)造伴隨式一差錯(cuò)圖案表[(S,E)]。(2)對接收向量R計(jì)算伴隨式S。(3)查[(S,E)]表得E。(4)糾錯(cuò)計(jì)算C=R-E。8.3.3漢明碼常見的線性分組碼有重復(fù)碼、漢明碼、里得-穆勒(Reed-Muller)碼(RM碼)、戈雷(Golay)碼等。漢明碼是漢明1950年提出的糾一個(gè)錯(cuò)誤的線性分組碼，也是第一個(gè)被人研究應(yīng)用的糾錯(cuò)碼。由于其編譯碼電路簡單，故至今在通信系統(tǒng)和數(shù)據(jù)存儲系統(tǒng)中應(yīng)用廣泛。8.3.3漢明碼1、漢明碼的構(gòu)筑思路由知：糾一個(gè)錯(cuò)誤，則,即要求中任意兩列線性無關(guān)。也就是要求的任意兩列不相同，且無全“0”列。8.3.3漢明碼在(n,k)線性分組碼中，校驗(yàn)元個(gè)數(shù)r=n-k，陣中每列有r個(gè)元素，至多可構(gòu)成2r-1種互不相同的非0列。故對于任意的正整數(shù)，存在具有以下參數(shù)的漢明碼：碼長信息位數(shù)校驗(yàn)位數(shù)碼的最小距離如（7，4）漢明碼，（15，11）漢明碼8.3.3漢明碼2、漢明碼的兩種形式1)標(biāo)準(zhǔn)形式：依據(jù)一致校驗(yàn)矩陣的標(biāo)準(zhǔn)形式所編出的漢明碼，它是一種系統(tǒng)碼。其中的陣為一個(gè)m行和列的矩陣。8.3.3漢明碼2)非標(biāo)準(zhǔn)形式：若按照其一致校驗(yàn)矩陣的一種特殊形式(校驗(yàn)陣中的各列就是1到所對應(yīng)的二進(jìn)制數(shù))所編出的漢明碼，它是一種非系統(tǒng)完備碼。這種形式的漢明碼最常用，因?yàn)樗哂芯幾g碼簡單、擴(kuò)展方便等優(yōu)點(diǎn)，下面對此稍作說明。8.3.3漢明碼說明：①例如m=3時(shí)的(7,4)漢明碼其一致校驗(yàn)陣為據(jù)此所對應(yīng)的一致生成矩陣來構(gòu)筑的編碼十分簡單。8.3.3漢明碼②依據(jù)上一介紹的內(nèi)容知：由于漢明碼是只能糾單個(gè)錯(cuò)誤的碼,因此當(dāng)接收端譯碼器接收到的經(jīng)信道傳輸而來的這類碼字時(shí)，其伴隨式所對應(yīng)的二進(jìn)制數(shù)值正是陣中對應(yīng)列，也就是接收碼字中錯(cuò)誤碼元的位置號，據(jù)此譯碼十分方便。如：上例中，若在譯碼輸出端通過伴隨式計(jì)算電路算得某接收碼字的伴隨式為則可直接判定接收碼字的第5位出錯(cuò)。8.3.3漢明碼③漢明碼可糾錯(cuò)誤圖樣數(shù)為n=2m-1,等于該漢明碼的碼長，故漢明碼是完備碼。④若將漢明碼加以改造，使它除了能糾單個(gè)錯(cuò)誤外，還能發(fā)現(xiàn)兩個(gè)錯(cuò)誤，這樣所得到的“糾1檢2錯(cuò)碼”稱為“擴(kuò)展?jié)h明碼”（或者“增余漢明碼”、“推廣漢明碼”）。8.3.3漢明碼設(shè)原漢明碼的一致校驗(yàn)陣為,則擴(kuò)展?jié)h明碼的一致校驗(yàn)陣應(yīng)為8.3.3漢明碼∵∴故至少應(yīng)在原碼基礎(chǔ)上增加一個(gè)校驗(yàn)位，且應(yīng)使新的一致校驗(yàn)矩陣陣中任意兩列之和不等于其它任一列，這就要求陣的任三列線性無關(guān)。8.3.3漢明碼例：設(shè)某（7,3）線性分組碼的一致校驗(yàn)矩陣為：發(fā)送端發(fā)送的碼字為（注：接收端譯碼器并不知道發(fā)送碼字）。試討論下面三種接收情況下的判錯(cuò)情形：8.3.3漢明碼①接收端接收的碼字為②接收端接收的碼字為③接收端接收的碼字為解:①當(dāng)接收端接收的碼字為時(shí)，故譯碼器判為沒錯(cuò)。8.3.3漢明碼②當(dāng)接收端接收的碼字為時(shí)，又由其H陣知該(7,3)碼為能糾1個(gè)錯(cuò)誤的碼型，且ST正好等于H陣中的第二列，因此可判定第二位有錯(cuò)。8.3.3漢明碼③當(dāng)接收端接收的碼字為時(shí)，譯碼器判為有錯(cuò)。又由于此時(shí)的伴隨式ST與H中任一列均不同，故一定出現(xiàn)了兩位或兩位以上的錯(cuò)誤，譯碼器無法判定錯(cuò)誤究竟出現(xiàn)在哪些位上。8.3.3漢明碼

伴隨式計(jì)算電路(以上例中的(7,3)碼為例)設(shè)接收字為8.3.3漢明碼8.3.3漢明碼碼字輸入移位寄存器組半加器8.3.3漢明碼伴隨式計(jì)算電路組合邏輯電路糾錯(cuò)譯碼電路…………輸入（信道輸出）譯碼輸出8.4循環(huán)碼

循環(huán)碼是線性分組碼的一個(gè)重要子類。由于它具有循環(huán)特性和優(yōu)良的代數(shù)結(jié)構(gòu)，使得它在發(fā)送端可用簡單的反饋移位寄存器實(shí)現(xiàn)編碼，而在接收端也可由簡單的反饋移位寄存器實(shí)現(xiàn)伴隨式計(jì)算，從而實(shí)現(xiàn)簡單有效的編譯碼。所以循環(huán)碼已成為研究最深入、理論最成熟、應(yīng)用最廣泛的一類線性分組碼。8.4.1循環(huán)碼的描述

1.循環(huán)碼的定義定義1：如將一個(gè)碼系的全部碼字分成若干組，則每組的所有碼字可由其中任一碼字的循環(huán)移位得到。如(7,3)循環(huán)碼的個(gè)數(shù)為：23個(gè)，分成兩個(gè)組8.4.1循環(huán)碼的描述

(0000000)

(0010111)(0101110)(1011100)(0111001)(1110010)(1100101)(1001011)8.4.1循環(huán)碼的描述又如：(7,4)循環(huán)碼，碼的個(gè)數(shù)為24個(gè)，分成四個(gè)組

(0000000)

(1111111)

(1001110)(0011101)(0111010)(1110100)(1101001)(1010011)(0100111)

(1000101)(0001011)(0010110)(0101100)(1011000)(0110001)(1100010)8.4.1循環(huán)碼的描述定義2:一個(gè)(n,k)線性分組碼C，若它一個(gè)碼矢的每一循環(huán)移位都是C的一個(gè)碼字，則C是一個(gè)循環(huán)碼。循環(huán)碼是一種線性碼，因此線性碼的一切特性均適合于循環(huán)碼；但它的特殊性是其循環(huán)性，碼字集合或者說碼組中任意一個(gè)碼字的循環(huán)移位得到的序列仍是該碼字集合中的碼字，即它對循環(huán)操作滿足封閉性。8.4.1循環(huán)碼的描述例分析二進(jìn)制碼組{000,110,101,011},{00000,01111,10100,11011},{0000,1101,0111,1011,1110}是不是循環(huán)碼。解看碼組符不符合線性和循環(huán)的條件。對于碼組{000,110,101,011}，它既是線性碼又是循環(huán)碼。事實(shí)上，它是對00,01,10,11進(jìn)行偶校驗(yàn)得到的碼，是(3,2)循環(huán)碼。8.4.1循環(huán)碼的描述對于碼組{00000,01111,10100,11011}，它是線性碼但不是循環(huán)碼。事實(shí)上，它是對消息序列00,01,10,11進(jìn)行編碼得到的線性分組碼(5,2)碼。對于碼組{0000,1101,0111,1011,1110}，它盡管滿足循環(huán)性但由于不是線性碼，故也不是循環(huán)碼。8.4.1循環(huán)碼的描述2.循環(huán)碼的碼多項(xiàng)式由此可以建立碼序列和碼多項(xiàng)式的一一對應(yīng)關(guān)系。設(shè)碼序列為

則它可用多項(xiàng)式表示為

將它進(jìn)行i次循環(huán)左移，得

稱為碼序列循環(huán)移位i次后的碼多項(xiàng)式。8.4.1循環(huán)碼的描述定理設(shè)循環(huán)碼的碼多項(xiàng)式為循環(huán)移位i次后的碼多項(xiàng)式為，則是xn+1除多項(xiàng)式xi

C(x)所得之余式。即(模xn+1)

8.4.1循環(huán)碼的描述則上式表明：碼矢循環(huán)一次的碼多項(xiàng)式是原碼多項(xiàng)式乘除以的余式：記作(模xn+1)8.4.1循環(huán)碼的描述由此類推：(模xn+1)即：循環(huán)碼的碼矢的次循環(huán)移位等效于將碼多項(xiàng)式乘后再模8.4.1循環(huán)碼的描述移位次數(shù)碼字碼多項(xiàng)式模x7+100011101x4+x3+x2+1

10111010x(x4+x3+x2+1)x5+x4+x3+x21110100x2(x4+x3+x2+1)x6+x5+x4+x231101001x3(x4+x3+x2+1)x6+x5+x3+141010011x4(x4+x3+x2+1)x6+x4+x2+150100111x5(x4+x3+x2+1)x5+x2+x+161001110x6(x4+x3+x2+1)x6+x3+x2+x如（7，3）循環(huán)碼：8.4.1循環(huán)碼的描述3.循環(huán)碼的生成多項(xiàng)式在(n,k)循環(huán)碼的2k個(gè)碼字中，取前k-1位皆為0的碼字所對應(yīng)的碼多項(xiàng)式g(x)(其次數(shù)r=n-k)，再經(jīng)k-1次循環(huán)移位，共得k個(gè)碼字：g(x)，xg(x)，…，xk-1g(x)。這k個(gè)碼字顯然是相互獨(dú)立的?？勺鳛榇a生成矩陣的k行，得到(n,k)循環(huán)碼的生成矩陣G(x)。稱g(x)為生成多項(xiàng)式。

其中

為n-k次首1多項(xiàng)式。8.4.1循環(huán)碼的描述幾個(gè)關(guān)于生成多項(xiàng)式的定理定理1：在(n,k)循環(huán)碼中，生成多項(xiàng)式g(x)是唯一的(n-k)次多項(xiàng)式，且次數(shù)是最低的。定理2：在(n,k)循環(huán)碼中，每個(gè)碼多項(xiàng)式C(x)都是生成多項(xiàng)式g(x)的倍式，而每個(gè)g(x)倍式的次數(shù)小于或等于(n-1)的多項(xiàng)式必為(n,k)循環(huán)碼的碼多項(xiàng)式。8.4.1循環(huán)碼的描述定理3：(n,k)循環(huán)碼的生成多項(xiàng)式g(x)是xn+1的因式，即xn+1=h(x)g(x)定理4：若g(x)是一個(gè)(n-k)次多項(xiàng)式，且為xn+1的因式，則g(x)生成唯一一個(gè)(n-k)循環(huán)碼碼系。8.4.1循環(huán)碼的描述以上幾個(gè)定理說明：構(gòu)建一個(gè)(n,k)循環(huán)碼時(shí)，只要分解多項(xiàng)式xn+1的因式，從中取出(n-k)次因式作生成多項(xiàng)式即可。8.4.1循環(huán)碼的描述例求(7,3)循環(huán)碼的生成多項(xiàng)式。解：分解多項(xiàng)式x7+1，取4次因式作生成多項(xiàng)式因?yàn)榭蓪⒁淮魏腿我粋€(gè)三次因式的乘積作為生成多項(xiàng)式，所以8.4.2循環(huán)碼的生成矩陣在(n,k)循環(huán)碼的2k個(gè)碼字中，取前k-1位皆為0的碼字所對應(yīng)的碼多項(xiàng)式g(x)(其次數(shù)r=n-k)，再經(jīng)k-1次循環(huán)移位，共得k個(gè)碼字：g(x)，xg(x)，…，xk-1g(x)。這k個(gè)碼字顯然是相互獨(dú)立的?？勺鳛榇a生成矩陣的k行，得到(n,k)循環(huán)碼的生成矩陣G。8.4.2循環(huán)碼的生成矩陣8.4.3校驗(yàn)多項(xiàng)式和校驗(yàn)矩陣設(shè)g(x)為(n,k)循環(huán)碼的生成多項(xiàng)式，則g(x)必為xn+1的因式，若有xn+1=h(x)g(x)

其中h(x)為k次因式，那么g(x)為n-k次因式則稱h(x)為(n,k)循環(huán)碼的一致校驗(yàn)多項(xiàng)式。既然(n,k)循環(huán)碼可由g(x)唯一生成，那么(n,k)循環(huán)碼亦可由h(x)完全確定。8.4.3校驗(yàn)多項(xiàng)式和校驗(yàn)矩陣?yán)?7,3)循環(huán)碼因?yàn)?/p>

由等式兩端同次項(xiàng)系數(shù)相等得：8.4.3校驗(yàn)多項(xiàng)式和校驗(yàn)矩陣的系數(shù)：的系數(shù)：的系數(shù)：的系數(shù)：8.4.3校驗(yàn)多項(xiàng)式和校驗(yàn)矩陣將方程組寫成矩陣形式：8.4.3校驗(yàn)多項(xiàng)式和校驗(yàn)矩陣由上式可見：列陣的元素是生成多項(xiàng)式的系數(shù)，是一個(gè)碼字。則第一個(gè)矩陣為（7，3）循環(huán)碼的校驗(yàn)矩陣，記為的構(gòu)成特點(diǎn)：①的第一行是碼的校驗(yàn)多項(xiàng)式的系數(shù)的反序排列，記為8.4.3校驗(yàn)多項(xiàng)式和校驗(yàn)矩陣②第二、三、四、行是第一行的移位。又因?yàn)樗?.4.3校驗(yàn)多項(xiàng)式和校驗(yàn)矩陣所以

循環(huán)碼的校驗(yàn)矩陣可推廣到一般：8.4.4循環(huán)碼編碼

1.基