信息論與編碼第八章1

第8章糾錯(cuò)編碼8.2糾錯(cuò)編碼的分類(lèi)8.1糾錯(cuò)編碼的基本概念8.3線性分組碼8.4循環(huán)碼8.1糾錯(cuò)編碼的基本概念信道編碼提高數(shù)字通信可靠性

數(shù)字信號(hào)在信道的傳輸過(guò)程中,由于實(shí)際信道的傳輸特性不理想以及存在加性噪聲,在接收端往往會(huì)產(chǎn)生誤碼。信源編碼提高數(shù)字信號(hào)有效性

將信源的模擬信號(hào)轉(zhuǎn)變?yōu)閿?shù)字信號(hào)

降低數(shù)碼率,壓縮傳輸頻帶(數(shù)據(jù)壓縮)目的在于提高通信（或存儲(chǔ)）的可靠性，減低誤碼率。從原理上看，構(gòu)造信道碼的基本思路是根據(jù)一定的規(guī)律在待發(fā)送的信息碼元中人為地加入一定的多余碼元(稱(chēng)為監(jiān)督碼)，以引入最小的多余度為代價(jià)來(lái)?yè)Q取最好的抗干擾性能。設(shè)有m個(gè)不同的信息序列，每個(gè)不同的序列由k（k<n)位（信息位），它由碼元組成。[C]為編碼器的輸出，稱(chēng)為碼字矢量，它由n位碼元組成，其中有k位信息元，r=n-k位監(jiān)督元。假設(shè)信源信息是二進(jìn)制數(shù)字序列，將信源編碼其的輸出序列構(gòu)成長(zhǎng)度為n的段，記為C定義8.1對(duì)于二元符號(hào)表上的分組碼C，由表示消息序列的長(zhǎng)度為n的m個(gè)二元序列構(gòu)成的集合，稱(chēng)為二元分組碼。定義8.2對(duì)于2k個(gè)n長(zhǎng)碼字全體構(gòu)成的分組碼，其碼字中的k位稱(chēng)為信息位，n-k位稱(chēng)為校驗(yàn)位或監(jiān)督位。線性分組碼：監(jiān)督元與信息元之間的關(guān)系可用一組線性方程組來(lái)描述的(n,k)分組碼。編碼效率：一個(gè)組中信息所占的比重。k：信息碼元的數(shù)目n：編碼組碼元的總數(shù)目n=k+rr：監(jiān)督碼元的數(shù)目定義8.3若（n，k）分組碼中k個(gè)信息位同原始k個(gè)信息位相同，且位于n長(zhǎng)碼字的前（或后）k位，為校驗(yàn)位位于其后（或前），則稱(chēng)該分組碼為系統(tǒng)碼，否則為非系統(tǒng)碼。定義8.4兩個(gè)序列之間的漢明距離定義為兩個(gè)序列之間對(duì)應(yīng)位不同的位數(shù)。例如：α和β為碼組X中的兩個(gè)不同碼字，X為一個(gè)長(zhǎng)度為N的二元碼組，其中：

α=[a1,a2,……aN]ai∈{0,1}

β=[b1,b2,……bN]bi∈{0,1}

則α與β的漢明距離為：

d=0表明為全同碼，d=N表明為全異碼碼的最小漢明距離是衡量碼的糾、檢錯(cuò)能力的重要參數(shù)，碼的最小距離越大，其糾、檢錯(cuò)能力越強(qiáng)。最小碼距：在一個(gè)碼字集合中，任何兩個(gè)碼字之間的漢明距離組成一個(gè)元素集合，D(α,β),這個(gè)集合中的最小值稱(chēng)為這個(gè)碼字集合的最小漢明距離，簡(jiǎn)稱(chēng)最小碼距，記為：dmin。

dmin=min{d(α,β)α,β∈X

α≠β}定義8.5對(duì)于碼C中的某一碼字，其非零元素的個(gè)數(shù)稱(chēng)為該碼字的漢明重量。對(duì)于二元碼，其碼字的重量是碼字中1的個(gè)數(shù)。若碼字

，其重量可以表示為：如碼字

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

線性碼——信息碼元與監(jiān)督碼元之間呈線性關(guān)系，它們的關(guān)系可用一組線性代數(shù)方程聯(lián)系起來(lái)。非線性碼——信息碼元與監(jiān)督校元之間不存在線性關(guān)系。按照對(duì)信息碼元處理的方法的不同，糾錯(cuò)碼分為分組碼和卷積碼。

分組碼----把信息序列以每k個(gè)碼元分組，然后把每組k個(gè)信息元按一定規(guī)律產(chǎn)生r個(gè)多余的監(jiān)督碼元，輸出序列每組長(zhǎng)為n=k+r，則每一碼字的r個(gè)校驗(yàn)元只與本碼字的k個(gè)信息位有關(guān)，與別的碼字的信息位無(wú)關(guān)，通常記分組碼為(n,k)。其中分組碼又可分循環(huán)碼和非循環(huán)碼：對(duì)循環(huán)碼而言，其碼書(shū)的特點(diǎn)是，若將其全部碼字分成若干組，則每組中任一碼字中碼元循環(huán)移位后仍是這組的碼字；對(duì)非循環(huán)碼來(lái)說(shuō)，任一碼字中的碼元循環(huán)移位后不一定再是該碼書(shū)中的碼字。卷積碼----把信息序列以每k0(通常較小)個(gè)碼元分段，編碼器輸出該段的監(jiān)督碼元r=n-k0

不但與本段的k0個(gè)信息元有關(guān)，而且還與其前面L段的信息碼元有關(guān)，故記卷積碼為(n,k0,L)。從功能上看，信道編碼可分為檢錯(cuò)(可以發(fā)現(xiàn)錯(cuò)誤)碼與糾錯(cuò)(不僅能發(fā)現(xiàn)而且能自動(dòng)糾正)碼兩類(lèi)，糾錯(cuò)碼一定能檢錯(cuò)，檢錯(cuò)碼不一定能糾錯(cuò)，平常所說(shuō)的糾錯(cuò)碼是兩者的統(tǒng)稱(chēng)。發(fā)送端的信道編碼器將信息碼組編成具有一定糾錯(cuò)能力的碼。接收端信道譯碼器對(duì)接收碼字進(jìn)行譯碼,若傳輸中產(chǎn)生的差錯(cuò)數(shù)目在碼的糾錯(cuò)能力之內(nèi)時(shí),譯碼器對(duì)差錯(cuò)進(jìn)行定位并加以糾正。1、前向糾錯(cuò)(FEC)：發(fā)端發(fā)送檢錯(cuò)碼，收端譯碼器判斷當(dāng)前碼字傳輸是否出錯(cuò)；當(dāng)有錯(cuò)時(shí)按某種協(xié)議通過(guò)一個(gè)反向信道請(qǐng)求發(fā)送端重傳已發(fā)送的碼字(全部或部分)。2、自動(dòng)請(qǐng)求重發(fā)(ARQ)：是FEC與ARQ方式的結(jié)合。發(fā)端發(fā)送同時(shí)具有自動(dòng)糾錯(cuò)和檢測(cè)能力的碼組,收端收到碼組后,檢查差錯(cuò)情況,如果差錯(cuò)在碼的糾錯(cuò)能力以內(nèi),則自動(dòng)進(jìn)行糾正。如果信道干擾很?chē)?yán)重,錯(cuò)誤很多,超過(guò)了碼的糾錯(cuò)能力,但能檢測(cè)出來(lái),則經(jīng)反饋信道請(qǐng)求發(fā)端重發(fā)這組數(shù)據(jù)。3、混合糾錯(cuò)(HEC)4、信息反饋(IRQ)：收端把收到的數(shù)據(jù),原封不動(dòng)地通過(guò)反饋信道送回到發(fā)端,發(fā)端比較發(fā)的數(shù)據(jù)與反饋來(lái)的數(shù)據(jù),從而發(fā)現(xiàn)錯(cuò)誤,并且把錯(cuò)誤的消息再次傳送,直到發(fā)端沒(méi)有發(fā)現(xiàn)錯(cuò)誤為止。8.3線性分組碼線性分組碼是編碼方式是將信息序列進(jìn)行分組，稱(chēng)為信息組，每個(gè)信息組由相繼的k位信息組成，然后按照一定編碼規(guī)則，把信息組成n為二進(jìn)制數(shù)字序列，形成碼字。它的基本關(guān)系一個(gè)碼字包括獨(dú)立的信息元和監(jiān)督元，其監(jiān)督元與信息元之間是一種代數(shù)關(guān)系，如果這種代數(shù)關(guān)系為線性的則稱(chēng)為線性分組碼。8.3.1校驗(yàn)矩陣與生成矩陣分組碼信息序列碼字M=(mk-1…m0)C=(cn-1…c0){M}{C}f

(?)線性分組碼有一組信息元的模2線性方程生成，假設(shè)k=3，n=7，構(gòu)成的線性分組碼為

C=[c1,c2,c3,c4,c5,c6,c7]式中，c1,c2,c3為信息元c4,c5,c6,c7為校驗(yàn)元校驗(yàn)元可用下列方程組得到校驗(yàn)方程或監(jiān)督方程改寫(xiě)矩陣形式為令

H=HCT=0或CHT=0H稱(chēng)為一致校驗(yàn)矩陣。定義8.6對(duì)于k位信息位n長(zhǎng)的線性分組碼，可有下面關(guān)系存在

C=mG式中C為n維矢量，m為k為矢量，稱(chēng)矩陣G（k×n維）為線性分組碼C的生成矩陣。生成矩陣可以寫(xiě)成分塊矩陣，即

G=[IP]生成矩陣與校驗(yàn)矩陣的關(guān)系：HGT=0或GHT=0校驗(yàn)矩陣可以寫(xiě)成H=[QI]只有當(dāng)PT=Q或P=QT時(shí)等式才成立。生成矩陣可以寫(xiě)成G=[IP]例(6,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)碼生成矩陣畫(huà)出編碼器電原理圖。

解(1)由得

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

m0m1m2c0c1c2輸入輸出8.3.2線性分組碼的糾、檢錯(cuò)能力定理8.1對(duì)于一個(gè)二進(jìn)制對(duì)稱(chēng)信道，若輸出為k個(gè)等可能的n長(zhǎng)碼字，則最大后驗(yàn)概率譯碼準(zhǔn)則應(yīng)為最小漢明距離。定理8.2線性分組碼的最小距離等于非零碼字的最小重量。定理8.3對(duì)于（n，k）線性分組碼，設(shè)最小距離為dmin，那么有以下結(jié)論存在：⑴這組碼具有糾正u個(gè)錯(cuò)誤的充分必要條件是⑵這組碼具有檢測(cè)l個(gè)錯(cuò)誤的充分必要條件是dmin=2u+1dmin=l+1（3）這組碼具糾正t個(gè)錯(cuò)誤，同時(shí)可以發(fā)現(xiàn)l（l>t）個(gè)錯(cuò)誤的充分必要條件是dmin=t+l+1設(shè)有m個(gè)n長(zhǎng)碼Xi，i=1，2，…，m,顯然n長(zhǎng)碼字的總數(shù)為2n。當(dāng)發(fā)送某一碼字的錯(cuò)誤碼元小于或等于u時(shí)，即對(duì)接收碼字滿足d(Xi,Y)≤u接收碼字的可能數(shù)為對(duì)于可能發(fā)送的所有m個(gè)碼字，若能使校正小于或等于u位錯(cuò)誤，則接收碼字的總個(gè)數(shù)為并且一定滿足8.3.3校驗(yàn)矩陣與最小距離的關(guān)系定理8.4對(duì)于（n，k）線性分組碼，設(shè)其校驗(yàn)矩陣為H，若H中的任意t列線性無(wú)關(guān)，而有t+1列線性相關(guān)，則碼字的最小距離或最小重量為t+1；若碼字的最小重量或最小距離為t+1，則校驗(yàn)矩陣H的任意t列線性無(wú)關(guān)，而又t+1列線性相關(guān)。各列都不相同，任意2列之和不等于0，2列線性無(wú)關(guān)；任意2列之和一定等于矩陣中某一列，任意3列線性相關(guān)。所以該碼的最小距離為3，小于n-k

+1=4。8.3.4線性分組碼的伴隨式為了糾正碼字的某位發(fā)生的錯(cuò)誤，必須使每一位發(fā)生錯(cuò)誤的標(biāo)志互不相同，我們稱(chēng)這個(gè)標(biāo)志為伴隨式。設(shè)發(fā)送碼字為C，接收碼字為Y,校驗(yàn)矩陣為H，令S=YHT或

ST=HYT當(dāng)S=0時(shí)，則接收的Y為一碼字，即滿足校驗(yàn)方程若S≠0，說(shuō)明Y不是碼字。設(shè)發(fā)送碼字為C＝[c1c2…cn]接受碼字應(yīng)為發(fā)送碼字與錯(cuò)誤圖樣的和Y＝C+E=[y1y2…yn]S=YHT=(C+E)HT=CHT+EHT因?yàn)镃是碼字，故CHT=0所以有S=EHT當(dāng)碼字的第i位發(fā)生錯(cuò)誤時(shí)，則ei=1，否則ei=0碼字在傳輸過(guò)程中，由于干擾和噪聲的存在，將產(chǎn)生差錯(cuò)這個(gè)差錯(cuò)稱(chēng)為錯(cuò)誤圖樣

E＝[e1e2…en]8.3.5線性分組碼的譯碼當(dāng)求得錯(cuò)誤圖樣后，其發(fā)送碼字的估值為若有兩個(gè)或兩個(gè)以上錯(cuò)誤時(shí)，只能檢錯(cuò)，不能糾錯(cuò)。在傳輸過(guò)程中，錯(cuò)誤個(gè)數(shù)不超過(guò)糾錯(cuò)能力時(shí)，伴隨式與錯(cuò)誤圖樣有對(duì)應(yīng)關(guān)系。假設(shè)一組碼具有糾正單個(gè)錯(cuò)誤能力時(shí)，且碼字在傳輸過(guò)程中只有一個(gè)錯(cuò)誤，顯然錯(cuò)誤圖樣中只有一個(gè)為1，所以伴隨式為校驗(yàn)矩陣中的某一列。定理8.5若（n，k）線性分組碼能糾正u個(gè)錯(cuò)誤，則其校驗(yàn)位的數(shù)目必須滿足8.3.6漢明碼漢明碼是能夠糾正一個(gè)錯(cuò)誤的線性分組碼。漢明碼有兩種構(gòu)造方式：1、校驗(yàn)矩陣的標(biāo)準(zhǔn)形式即H=[PI]2、校驗(yàn)矩陣的列按二進(jìn)制的自然順序從左到右排列的非零列。改進(jìn)漢明碼使它除了具有糾正但個(gè)錯(cuò)誤外，還能發(fā)現(xiàn)兩個(gè)錯(cuò)誤。漢明碼的糾錯(cuò)能力t=1，既有二進(jìn)制的，也有非二進(jìn)制的。二進(jìn)制時(shí)，漢明碼碼長(zhǎng)n和信息位k服從以下規(guī)律：(n,k)=(2m-1,2m-1-m)

其中m=n-k，是正整數(shù)。當(dāng)m＝3、4、5、6、7、8…時(shí)，有漢明碼(7,4)、(15,11)、(31,26)、(63,57)、(127,120)……。二是校驗(yàn)矩陣的列是按二進(jìn)制的自然順序從左到右排列的非零列。對(duì)于(7,4)線性分組碼，按這種校驗(yàn)矩陣編出的碼是非系統(tǒng)碼。當(dāng)發(fā)生單個(gè)錯(cuò)誤時(shí)，伴隨式是H中與錯(cuò)誤位置對(duì)應(yīng)的列，所以伴隨式二進(jìn)制數(shù)的值就是錯(cuò)誤位置的序列。漢明碼只表明了糾正單個(gè)錯(cuò)誤的能力，但沒(méi)有發(fā)現(xiàn)兩個(gè)錯(cuò)誤的能力。可以改進(jìn)漢明碼，使它除了具有糾正單個(gè)錯(cuò)誤的能力外，還能發(fā)現(xiàn)兩個(gè)錯(cuò)誤。因?yàn)楫?dāng)出現(xiàn)一個(gè)錯(cuò)誤時(shí)，其伴隨式的最后一位數(shù)是1，即[**…*1]形式；當(dāng)出現(xiàn)兩個(gè)錯(cuò)誤時(shí)，其伴隨式為某兩列之和，故最后一位數(shù)為0，即為[**…*0]形式，因?yàn)樗cH’中的任何一列都不相同，所以與單個(gè)錯(cuò)誤的伴隨式不同，因此具備檢查出2個(gè)錯(cuò)誤的能力。8.4循環(huán)碼循環(huán)碼是線性代數(shù)分組碼，一般記為（n，k）碼，其中n為碼字長(zhǎng)度，k為信息位長(zhǎng)度。特點(diǎn)：若C=[c1,c2,…,cn]是一個(gè)碼字，那么他的循環(huán)移位C’=[c2，c3，…,cn,c1]同樣也是一個(gè)碼字。定義8.7對(duì)于(n,k)線性分組碼，若一個(gè)碼字為C＝[c1c2

…cn-1

cn

]該碼向左循環(huán)一位后為：C（1）＝[c2

c3

…cn-1cnc1

]向左再循環(huán)i位后為：C（i）＝[ci+1

ci+2

…cn-1cnc1….ci

]若C（i）均為碼字，則稱(chēng)這個(gè)（n，k）線性分組碼為循環(huán)碼。循環(huán)碼采用多項(xiàng)式表示C(x)=c1xn-1+c2xn-2

+…+cn-1x+cn循環(huán)左移一位：(c1c2

…cn)(c2c3

…cnc1)C0(x)=c1xn-1+c2xn-2

+…+cn-1x+cnC1(x)=

xC0(x)=c2xn-1+c3xn-2+…+cn

x+c1

移1位：C1(x)=xC0(x) mod(xn

+1)

移2位：C2(x)=xC1(x)=x2C0(x)mod(xn+1)

移i位：Ci(x)=xiC0(x) mod(xn+1)比較循環(huán)移位的前后，可用如下的多項(xiàng)式運(yùn)算來(lái)表達(dá)循環(huán)移位根據(jù)碼空間的封閉性，碼字的線性組合仍是碼字。碼多項(xiàng)式由于（n，k）循環(huán)碼共有2k個(gè)碼字，從碼組中取出一個(gè)前面（k-1）位都是0的碼字，用g（x)表示，g(x)＝x

n-k

+gn-k-1x

n-k-1+…+g2x2+g1x+1由xig（x)構(gòu)成生成矩陣為C(x)=[m1m2…mk]G(x)

碼多信息元生成項(xiàng)式矩陣C(x)=m(x)g(x)碼多信息生成項(xiàng)式多項(xiàng)式多項(xiàng)式校驗(yàn)多項(xiàng)式多項(xiàng)式xn+1可因式分解為xn+1＝g(x)h(x)的形式；如果g(x)代表(n，k)循環(huán)碼的生成多項(xiàng)式，則h(x)代表該循環(huán)碼的一致校驗(yàn)多項(xiàng)式，其階次為k。h(x)的校驗(yàn)作用表現(xiàn)在：任何碼多項(xiàng)式C(x)與h(x)的模xn+1乘積一定等于0，而非碼字與h(x)的乘積必不為0。C(x)h(x)=

m(x)g(x)h(x)=

m(x)(xn+1)=0mod(xn+1)次多項(xiàng)式

稱(chēng)為碼的校驗(yàn)多項(xiàng)式。設(shè)和

系數(shù)滿足以下關(guān)系設(shè)即

是

的倒多項(xiàng)式，則校驗(yàn)矩陣可以表示為由于

，故有校驗(yàn)矩陣可表示為例研究一個(gè)長(zhǎng)度n=7的循環(huán)碼的構(gòu)成方法

對(duì)(x7+1)作分解，找出n-k次因式。

x7+1＝(x+1)(x3+x2+1)(x3+x+1)，

n-k

因式g(x)對(duì)偶式h(x)循環(huán)碼

1(x+1) (x3+x2+1)(x3+x+1)(7,6)3(x3+x2+1)(x+1)(x3+x+1)(7,4)3(x3+x+1)(x+1)(x3+x2+1)(7,4)4(x+1)(x3+x2+1)(x3+x+1)(7,3)4(x+1)(x3+x+1)(x3+x2+1)(7,3)6(x3+x2+1)(x3+x+1)(x+1) (7,1)構(gòu)成(7,3)循環(huán)碼： 選g(x)=(x+1)(x3+x+1)=(x4+x3+x2+1)，則C(x)=m(x)g(x)=(m2x2+m1x+m0)(x4+x3+x2+1)。當(dāng)輸入信息m=(011)時(shí)，m(x)=(x+1)，C(x)=(x+

1)(x4＋x3＋x2＋1)=x