信息論與編碼第八章1

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

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

將信源的模擬信號轉變?yōu)閿?shù)字信號

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

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

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

則α與β的漢明距離為：

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

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

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

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

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

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

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

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

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

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

H=HCT=0或CHT=0H稱為一致校驗矩陣。定義8.6對于k位信息位n長的線性分組碼，可有下面關系存在

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

G=[IP]生成矩陣與校驗矩陣的關系：HGT=0或GHT=0校驗矩陣可以寫成H=[QI]只有當PT=Q或P=QT時等式才成立。生成矩陣可以寫成G=[IP]例(6,3)線性分組碼，其生成矩陣是求：(1)計算碼集，列出信息組與碼字的映射關系。(2)將該碼系統(tǒng)化處理后，計算系統(tǒng)碼碼集并列出映射關系。(3)計算系統(tǒng)碼的校驗矩陣H。若收碼r=[100110],檢驗它是否碼字？(4)根據(jù)系統(tǒng)碼生成矩陣畫出編碼器電原理圖。

解(1)由得

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

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

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

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

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

其中m=n-k，是正整數(shù)。當m＝3、4、5、6、7、8…時，有漢明碼(7,4)、(15,11)、(31,26)、(63,57)、(127,120)……。二是校驗矩陣的列是按二進制的自然順序從左到右排列的非零列。對于(7,4)線性分組碼，按這種校驗矩陣編出的碼是非系統(tǒng)碼。當發(fā)生單個錯誤時，伴隨式是H中與錯誤位置對應的列，所以伴隨式二進制數(shù)的值就是錯誤位置的序列。漢明碼只表明了糾正單個錯誤的能力，但沒有發(fā)現(xiàn)兩個錯誤的能力?？梢愿倪M漢明碼，使它除了具有糾正單個錯誤的能力外，還能發(fā)現(xiàn)兩個錯誤。因為當出現(xiàn)一個錯誤時，其伴隨式的最后一位數(shù)是1，即[**…*1]形式；當出現(xiàn)兩個錯誤時，其伴隨式為某兩列之和，故最后一位數(shù)為0，即為[**…*0]形式，因為它與H’中的任何一列都不相同，所以與單個錯誤的伴隨式不同，因此具備檢查出2個錯誤的能力。8.4循環(huán)碼循環(huán)碼是線性代數(shù)分組碼，一般記為（n，k）碼，其中n為碼字長度，k為信息位長度。特點：若C=[c1,c2,…,cn]是一個碼字，那么他的循環(huán)移位C’=[c2，c3，…,cn,c1]同樣也是一個碼字。定義8.7對于(n,k)線性分組碼，若一個碼字為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）均為碼字，則稱這個（n，k）線性分組碼為循環(huán)碼。循環(huán)碼采用多項式表示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)移位的前后，可用如下的多項式運算來表達循環(huán)移位根據(jù)碼空間的封閉性，碼字的線性組合仍是碼字。碼多項式由于（n，k）循環(huán)碼共有2k個碼字，從碼組中取出一個前面（k-1）位都是0的碼字，用g（x)表示，g(x)＝x

n-k

+gn-k-1x

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

碼多信息元生成項式矩陣C(x)=m(x)g(x)碼多信息生成項式多項式多項式校驗多項式多項式xn+1可因式分解為xn+1＝g(x)h(x)的形式；如果g(x)代表(n，k)循環(huán)碼的生成多項式，則h(x)代表該循環(huán)碼的一致校驗多項式，其階次為k。h(x)的校驗作用表現(xiàn)在：任何碼多項式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)次多項式

稱為碼的校驗多項式。設和

系數(shù)滿足以下關系設即

是

的倒多項式，則校驗矩陣可以表示為由于

，故有校驗矩陣可表示為例研究一個長度n=7的循環(huán)碼的構成方法

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

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

n-k

因式g(x)對偶式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)構成(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)。當輸入信息m=(011)時，m(x)=(x+1)，C(x)=(x+

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