第6章信道編碼1 2012

1第6章信道編碼6.1信道編碼的概念

6.2信道編碼定理

6.3線性分組碼2第6章信道編碼

信道編碼是以信息在信道上的正確傳輸為目標(biāo)的編碼，可分為兩個(gè)層次上的問(wèn)題：如何正確接收載有信息的信號(hào) －－線路編碼如何避免少量差錯(cuò)信號(hào)對(duì)信息內(nèi)容的影響 －－糾錯(cuò)編碼36.1信道編碼的概念進(jìn)行信道編碼是為了提高信號(hào)傳輸?shù)目煽啃?，改善通信系統(tǒng)的傳輸質(zhì)量，研究信道編碼的目標(biāo)是尋找具體構(gòu)造編碼的理論與方法。從原理上看，構(gòu)造信道碼的基本思路是根據(jù)一定的規(guī)律在待發(fā)送的信息碼元中人為地加入一定的多余碼元(稱為監(jiān)督碼)，以引入最小的多余度為代價(jià)來(lái)?yè)Q取最好的抗干擾性能。

46.1.1信道編碼的分類

對(duì)不同的信道需要設(shè)計(jì)不同類型的信道編碼方案，按照信道特性進(jìn)行劃分，信道編碼可分為：以糾獨(dú)立隨機(jī)差錯(cuò)為主的信道編碼、以糾突發(fā)差錯(cuò)為主的信道編碼和糾混合差錯(cuò)的信道編碼。從功能上看，信道編碼可分為檢錯(cuò)(可以發(fā)現(xiàn)錯(cuò)誤)碼與糾錯(cuò)(不僅能發(fā)現(xiàn)而且能自動(dòng)糾正)碼兩類，糾錯(cuò)碼一定能檢錯(cuò)，檢錯(cuò)碼不一定能糾錯(cuò)，平常所說(shuō)的糾錯(cuò)碼是兩者的統(tǒng)稱。

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

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

66.1.1信道編碼的分類按照對(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)。

76.1.1信道編碼的分類其中分組碼又可分循環(huán)碼和非循環(huán)碼：對(duì)循環(huán)碼而言，其碼書(shū)的特點(diǎn)是，若將其全部碼字分成若干組，則每組中任一碼字中碼元循環(huán)移位后仍是這組的碼字；對(duì)非循環(huán)碼來(lái)說(shuō)，任一碼字中的碼元循環(huán)移位后不一定再是該碼書(shū)中的碼字。86.1.1信道編碼的分類

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

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

96.1.1信道編碼的分類106.1.2與糾錯(cuò)編碼有關(guān)的基本概念

在通信系統(tǒng)的接收端，若接收到的消息序列R和發(fā)送的碼符號(hào)序列C不一樣，例如R=(11000)，而C=(10001)，R與C中有兩位不同，即出現(xiàn)兩個(gè)錯(cuò)誤，這種錯(cuò)誤是由信道中的噪聲干擾所引起的。116.1.2與糾錯(cuò)編碼有關(guān)的基本概念1.碼長(zhǎng)、碼重和碼距碼字中碼元的個(gè)數(shù)稱為碼字的長(zhǎng)度，簡(jiǎn)稱碼長(zhǎng)，用n表示。碼字中非“0”碼元的個(gè)數(shù)稱為碼字的漢明重量(簡(jiǎn)稱碼重，記作W)。對(duì)二進(jìn)制碼來(lái)說(shuō)，碼重W就是碼字中所含碼元“1”的數(shù)目，例如碼字“110000”，其碼長(zhǎng)n=6，碼重W=2。兩個(gè)等長(zhǎng)碼字之間對(duì)應(yīng)碼元不相同的數(shù)目稱為這兩個(gè)碼組的漢明距離(簡(jiǎn)稱碼距)。例如碼字“110000”與“100001”，它們的漢明距離D=2。

126.1.2與糾錯(cuò)編碼有關(guān)的基本概念在某一碼集C中，任意兩個(gè)碼字之間漢明距離的最小值稱為該碼的最小距離dmin，即：例如：碼組C={0111100，1011011，1101001}的最小碼距dmin=3。從避免碼字受干擾而出錯(cuò)的角度出發(fā)，總是希望碼字間有盡可能大的距離，因?yàn)樽钚〈a距代表著一個(gè)碼組中最不利的情況。

136.1.2與糾錯(cuò)編碼有關(guān)的基本概念2.錯(cuò)誤圖樣為了定量地描述信號(hào)的差錯(cuò)，定義收、發(fā)碼之“差”為差錯(cuò)圖樣。差錯(cuò)圖樣E＝發(fā)碼C-

收碼R

（模M）。例：8進(jìn)制(M=8)碼元，若發(fā)碼 ：C=（0,2,5,4,7,5,2）收碼變?yōu)椋篟=（0,1,5,4,7,5,4）差錯(cuò)圖樣 E=C-R=（0,1,0,0,0,0,6）（模8）二進(jìn)制碼：E=CR或

C=RE。

146.1.3錯(cuò)誤的種類1、隨機(jī)錯(cuò)誤：由隨機(jī)干擾引起。(前后位置無(wú)關(guān)，時(shí)間無(wú)關(guān)，差錯(cuò)以等概率發(fā)生)特點(diǎn)：因?yàn)楦蓴_是隨機(jī)的，所以各碼元是否發(fā)生錯(cuò)誤是相互獨(dú)立的，不會(huì)成片出錯(cuò)。2、突發(fā)錯(cuò)誤：由突發(fā)干擾引起（前后相關(guān)，成堆出現(xiàn)）。特點(diǎn)：因?yàn)橥话l(fā)干擾是突然出現(xiàn)的，且能持續(xù)一段時(shí)間，同時(shí)相對(duì)功率較大，所以錯(cuò)誤往往成片出現(xiàn)。常見(jiàn)錯(cuò)誤有兩種：隨機(jī)錯(cuò)誤和突發(fā)錯(cuò)誤

（在一個(gè)突發(fā)錯(cuò)誤持續(xù)長(zhǎng)度內(nèi)，開(kāi)頭和末尾的碼元總是錯(cuò)的，中間一些碼元不一定都錯(cuò)，但錯(cuò)的碼元數(shù)較多）如閃電和開(kāi)關(guān)瞬態(tài)往往引起突發(fā)錯(cuò)誤。156.1.2與糾錯(cuò)編碼有關(guān)的基本概念3.重復(fù)碼和奇偶校驗(yàn)碼

1)重復(fù)碼構(gòu)成重復(fù)碼的方法是當(dāng)發(fā)送某個(gè)信源符號(hào)ai時(shí)，不是只發(fā)一個(gè)，而是連續(xù)重發(fā)多個(gè)，連續(xù)重發(fā)的個(gè)數(shù)越多，重復(fù)碼的抗干擾能力就越強(qiáng)，當(dāng)然效率也越低。

166.1.2與糾錯(cuò)編碼有關(guān)的基本概念不重復(fù)時(shí)為(1，1)重復(fù)碼，如圖所示：重復(fù)一次時(shí)為(2，1)重復(fù)碼，如圖所示：

176.1.2與糾錯(cuò)編碼有關(guān)的基本概念重復(fù)二次時(shí)為(3，1)重復(fù)碼，如圖所示：

186.1.2與糾錯(cuò)編碼有關(guān)的基本概念

2)奇偶檢驗(yàn)碼奇偶校驗(yàn)是一種最基本的校驗(yàn)方法。構(gòu)成奇偶檢驗(yàn)碼的方法是在每k個(gè)二進(jìn)制信息位后加上一個(gè)奇(偶)監(jiān)督位(或稱校驗(yàn)位)，使碼長(zhǎng)n=k+r，同時(shí)使碼中“1”的個(gè)數(shù)恒為奇數(shù)(或偶數(shù))，如圖所示。在奇偶校驗(yàn)碼中，監(jiān)督位r=1，它是一種碼重W為奇數(shù)(或偶數(shù))的系統(tǒng)分組碼。

196.1.2與糾錯(cuò)編碼有關(guān)的基本概念206.1.2與糾錯(cuò)編碼有關(guān)的基本概念

奇校驗(yàn)----如果信息碼元中“1”值的個(gè)數(shù)為奇數(shù)個(gè)，則校驗(yàn)碼元值為“0”；如果信息碼元中“1”值的個(gè)數(shù)為偶數(shù)個(gè)，則校驗(yàn)碼元值為“1”。即所有信息碼元與校驗(yàn)碼元的模二和等于“1”。偶校驗(yàn)----如果信息碼元中“1”值的個(gè)數(shù)為偶數(shù)個(gè)，則校驗(yàn)碼元值為“0”；如果信息碼元中“1”值的個(gè)數(shù)為奇數(shù)個(gè)，則校驗(yàn)碼元值為“1”。即所有信息碼元與校驗(yàn)碼元的模二和等于“0”。

216.1.3檢錯(cuò)與糾錯(cuò)原理

要糾正傳輸差錯(cuò)，首先必須檢測(cè)出錯(cuò)誤。而要檢測(cè)出錯(cuò)誤，常用的方法是將發(fā)送端要傳送的信息序列(常為二進(jìn)制序列)中截取出長(zhǎng)度相等的碼元進(jìn)行分組，每組長(zhǎng)度為k，組成k位碼元信息序列M，并根據(jù)某種編碼算法以一定的規(guī)則在每個(gè)信息組的后面產(chǎn)生r個(gè)冗余碼元，由冗余碼元和信息碼元一起形成“n位編碼序列”，即信號(hào)碼字C，n位的碼字比信息碼長(zhǎng)(有n=k+r個(gè)碼元)，因而糾錯(cuò)編碼是冗余編碼。226.1.3檢錯(cuò)與糾錯(cuò)原理譯碼就是利用校驗(yàn)關(guān)系進(jìn)行檢錯(cuò)、糾錯(cuò)的，在接收端收到的位碼字中，信息碼元與冗余碼元之間也應(yīng)符合上述編碼規(guī)則，并根據(jù)這一規(guī)則進(jìn)行檢驗(yàn)，從而確定是否有錯(cuò)誤。這就是差錯(cuò)控制的基本思想。

236.1.3檢錯(cuò)與糾錯(cuò)原理分組碼一般用符號(hào)(n,k)表示，其中k是每組二進(jìn)制信息碼元的數(shù)目，n是編碼組的長(zhǎng)度(簡(jiǎn)稱碼長(zhǎng))，即編碼組的總位數(shù)，n-k=r為每碼組中的校驗(yàn)碼元(或稱監(jiān)督位)數(shù)目。通常，將分組碼規(guī)定為具有如圖所示的結(jié)構(gòu)。圖中前面k位為信息位，后面附加r個(gè)校驗(yàn)位。

24奇偶校驗(yàn)方法。增加偶(或奇)校驗(yàn)位使得對(duì)消息序列而言校驗(yàn)方程成立，當(dāng)校驗(yàn)位數(shù)增加時(shí)，可以檢測(cè)到差錯(cuò)圖樣的種類數(shù)也增加，但同時(shí)碼率減小。n重復(fù)碼方法。重復(fù)消息位使之可以檢測(cè)出任意小于n個(gè)差錯(cuò)的錯(cuò)誤圖樣。等重碼方法。設(shè)計(jì)碼字中的非“0”符號(hào)個(gè)數(shù)(若是二進(jìn)制碼則為“1”的個(gè)數(shù))恒為常數(shù)，使碼集C由全體重量恒等的n長(zhǎng)矢量組成。6.1.3檢錯(cuò)與糾錯(cuò)原理256.1.3檢錯(cuò)與糾錯(cuò)原理表所示為一種用于表示數(shù)字“0”到“9”的五中取三等重碼(所有碼字的碼重都等于“3”)的例子。

123456789001011110011011011010001111010111100011101001101101266.1.4檢錯(cuò)與糾錯(cuò)方式和能力

1.檢錯(cuò)與糾錯(cuò)方式自動(dòng)請(qǐng)求重發(fā)方式----用于檢錯(cuò)的糾錯(cuò)碼在譯碼器輸出端給出當(dāng)前碼字傳輸是否可能出錯(cuò)的指示，當(dāng)有錯(cuò)時(shí)按某種協(xié)議通過(guò)一個(gè)反向信道請(qǐng)求發(fā)送端重傳已發(fā)送的全部或部分碼字，這種糾錯(cuò)碼的應(yīng)用方式稱為自動(dòng)請(qǐng)求重發(fā)方式(ARQ，Automatic-Repeat-reQuest)。27前向糾錯(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ò)誤。6.1.4檢錯(cuò)與糾錯(cuò)方式和能力286.1.4檢錯(cuò)與糾錯(cuò)方式和能力29ARQ方式：發(fā)送端用編碼器對(duì)發(fā)送數(shù)據(jù)進(jìn)行差錯(cuò)編碼，通過(guò)正向信道送到接收端，而接收端經(jīng)譯碼器處理后只是檢測(cè)有無(wú)差錯(cuò)，不作自動(dòng)糾正。如檢測(cè)到差錯(cuò)，則利用反向信道反饋信號(hào)，請(qǐng)求發(fā)送端重發(fā)有錯(cuò)的數(shù)據(jù)單元，直到接收端檢測(cè)不到差錯(cuò)為止。

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

2.檢錯(cuò)與糾錯(cuò)能力一個(gè)糾錯(cuò)碼的每個(gè)碼字都可以形成一個(gè)漢明球，因此要能夠糾正所有不多于t位的差錯(cuò)，糾錯(cuò)碼的所有漢明球均應(yīng)不相交，判定糾錯(cuò)碼的檢、糾錯(cuò)能力可根據(jù)任意兩個(gè)漢明球不相交的要求，由碼的最小距離dmin來(lái)決定。

6.1.4檢錯(cuò)與糾錯(cuò)方式和能力33定理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ò)，則6.1.4檢錯(cuò)與糾錯(cuò)方式和能力34

6.1.4檢錯(cuò)與糾錯(cuò)方式和能力35定理說(shuō)明，碼的最小距離dmin越大，碼的糾(檢)錯(cuò)誤的能力越強(qiáng)。但是，隨著多余碼元的增多，信息傳輸速率會(huì)降低得越多。通常用=k/n來(lái)表示碼字中信息碼元所占的比例，稱為編碼效率，它是衡量碼性能的又一個(gè)重要參數(shù)。碼率越高，信息傳輸率就越高，但此時(shí)糾錯(cuò)能力要降低，若=1時(shí)就沒(méi)有糾錯(cuò)能力了?？梢?jiàn)，碼率與糾錯(cuò)能力之間是有矛盾。6.1.4檢錯(cuò)與糾錯(cuò)方式和能力366.1.5矢量空間與碼空間F表示碼元所在的數(shù)域，對(duì)于二進(jìn)制碼，F(xiàn)代表二元域{0,1}。設(shè)n重有序元素的集合V={Vi

},若滿足條件：V中矢量元素在矢量加運(yùn)算下構(gòu)成加群；V中矢量元素與數(shù)域F元素的標(biāo)乘封閉在V中；分配律、結(jié)合律成立，則稱集合V是數(shù)域F上的n維矢量空間，或稱n維線性空間，n維矢量又稱n重(n-tuples)。376.1.5矢量空間與碼空間對(duì)于域F上的若干矢量

線性組合：

線性相關(guān)：其中任一矢量可表示為其它矢量的線性組合

線性無(wú)關(guān)或線性獨(dú)立：一組矢量中的任意一個(gè)都不可能用其它矢量的線性組合來(lái)代替。386.1.5矢量空間與碼空間一組線性無(wú)關(guān)的矢量，線性組合的集合就構(gòu)成了一個(gè)矢量空間V，這組矢量就是這個(gè)矢量空間的基底。n維矢量空間應(yīng)包含n個(gè)基底基底不是唯一的，例：線性無(wú)關(guān)的兩個(gè)矢量（1,0）和（0,1）以及（-1,0）和（0,-1）可張成同一個(gè)兩維空間。396.1.5矢量空間與碼空間以（100）為基底可張成一維三重子空間V1，含21=2個(gè)元素，即以(010)(001)為基底可張成二維三重子空間V2，含22=4個(gè)元素，即以(100)(010)(001)為基底可張成三維三重空間V,含23=8個(gè)元素，V1和V2都是V的子空間。406.1.5矢量空間與碼空間每個(gè)矢量空間或子空間中必然包含零矢量?jī)蓚€(gè)矢量正交：V1V2＝0兩個(gè)矢量空間正交：某矢量空間中的任意元素與另一矢量空間中的任意元素正交正交的兩個(gè)子空間V1、V2互為對(duì)偶空間(DualSpace)，其中一個(gè)空間是另一個(gè)空間的零空間（nullspace，也稱零化空間）。416.1.5矢量空間與碼空間碼空間通常qn>>qk，分組編碼的任務(wù)是要在n維n重矢量空間的qn種可能組合中選擇其中的qk個(gè)構(gòu)成一個(gè)碼空間，其元素就是許用碼的碼集。

消息k長(zhǎng) (n,k)碼字n長(zhǎng)

qk

種分組編碼器qn種

k維k重矢量n維n重矢量426.1.5矢量空間與碼空間分組編碼的任務(wù)：

①選擇一個(gè)ｋ維n重子空間作為碼空間。

②確定由k維k重信息空間到ｋ維n重碼空間的映射方法。碼空間的不同選擇方法，以及信息組與碼組的不同映射算法，就構(gòu)成了不同的分組碼。436.1.6隨機(jī)編碼運(yùn)用概率統(tǒng)計(jì)方法在特定信道條件下對(duì)編碼信號(hào)的性能作出統(tǒng)計(jì)分析，求出差錯(cuò)概率的上下限邊界，其中最優(yōu)碼所能達(dá)到的差錯(cuò)概率上界稱作隨機(jī)碼界。用這種方法不能得知最優(yōu)碼是如何具體編出來(lái)的，卻能得知最優(yōu)碼可以好到什么程度，并進(jìn)而推導(dǎo)出有擾離散信道的編碼定理，對(duì)指導(dǎo)編碼技術(shù)具有特別重要的理論價(jià)值。446.1.6隨機(jī)編碼在(N,K)分組編碼器中隨機(jī)選定的碼集有qNM種，第m個(gè)碼集(記作{c}m)被隨機(jī)選中的概率是：設(shè)與這種選擇相對(duì)應(yīng)的條件差錯(cuò)概率是Pe({c}m)，那么全部碼集的平均差錯(cuò)概率是：456.1.6隨機(jī)編碼必定存在某些碼集某些碼集若，就必然存在一批碼集即差錯(cuò)概率趨于零的好碼一定存在466.1.6隨機(jī)編碼碼集點(diǎn)數(shù)M=qK占N維矢量空間總點(diǎn)數(shù)qN的比例是F=qK/qN

=q-(N-K)

。當(dāng)K和N的差值拉大即冗余的空間點(diǎn)數(shù)增加時(shí)，平均而言碼字的分布將變得稀疏，碼字間的平均距離將變大，平均差錯(cuò)概率將變小。當(dāng)F0即(N-K)時(shí)，能否讓平均差錯(cuò)概率？Gallager在1965年推導(dǎo)了的上邊界，并證明這個(gè)上邊界是按指數(shù)規(guī)律收斂的。47

E(R)為可靠性函數(shù)，也叫誤差指數(shù)。碼率：R=(lbM)

/N

，

M是可能的信息組合數(shù)，M=qK，N是每碼字的碼元數(shù)，R表示每碼元攜帶的信息量，單位是每符號(hào)比特（bit/symbol）。R在[0,R0]區(qū)間時(shí)E(R)~R曲線是斜率為-1（-45）的直線，E(R)反比于R；而當(dāng)R=C時(shí)E(R)=0即可靠性為零。

6.1.7信道編碼定理486.1.7信道編碼定理49

正定理：只要傳信率R小于信道容量C，總存在一種信道碼（及解碼器），可以以所要求的任意小的差錯(cuò)概率實(shí)現(xiàn)可靠的通信。逆定理：信道容量C是可靠通信系統(tǒng)傳信率R的上邊界，如果R>C，就不可能有任何一種編碼能使差錯(cuò)概率任意小。6.1.7信道編碼定理506.2糾錯(cuò)編譯碼的基本原理與分析

R不變，信道容量大者其可靠性函數(shù)E(R)也大；C不變，碼率減小時(shí)其可靠性函數(shù)E(R)增大E(R) R0R1<R2C1

<C2

增大E(R)的途徑516.2.1糾錯(cuò)編碼的基本思路對(duì)于同樣的碼率，信道容量大者其可靠性函數(shù)E(R)也大；對(duì)于同樣的信道容量，碼率減小時(shí)其可靠性函數(shù)E(R)增大?？刹扇∫韵麓胧p小差錯(cuò)概率。(1)增大信道容量C增大E(R)的途徑①擴(kuò)展帶寬。②加大功率。③降低噪聲。52(2)減小碼率R①q，N不變而減小K，這意味著降低信息源速率，每秒少傳一些信息。②q，K不變而增大N，這意味著提高符號(hào)速率（波特率），占用更大帶寬。③N，K不變而減小q，這意味著減小信道的輸入、輸出符號(hào)集，在發(fā)送功率固定時(shí)提高信號(hào)間的區(qū)分度，從而提高可靠性。6.2.1糾錯(cuò)編碼的基本思路53(3)增加碼長(zhǎng)N隨著N增大，矢量空間以指數(shù)量級(jí)增大，從統(tǒng)計(jì)角度而言碼字間距離也將加大，從而可靠性提高。另外，碼長(zhǎng)N越大，其實(shí)際差錯(cuò)概率就越能符合統(tǒng)計(jì)規(guī)律。6.2.1糾錯(cuò)編碼的基本思路54糾錯(cuò)能力的獲取

(1)利用冗余度冗余度：在信息流中插入冗余比特，這些冗余比特與信息比特之間存著特定的相關(guān)性。冗余的資源：時(shí)間，頻帶，功率，設(shè)備復(fù)雜度。

6.2.1糾錯(cuò)編碼的基本思路556.2.1糾錯(cuò)編碼的基本思路

(2)噪聲均化噪聲均化：讓差錯(cuò)隨機(jī)化，以便更符合編碼定理的條件從而得到符合編碼定理的結(jié)果?；舅枷耄涸O(shè)法將危害較大的、較為集中的噪聲干擾分?jǐn)傞_(kāi)來(lái)，使不可恢復(fù)的信息損傷最小。①增加碼長(zhǎng)N②卷積③交錯(cuò)（或稱交織）

566.2.2最優(yōu)譯碼與最大似然譯碼譯碼器的任務(wù)是從受損的信息序列中盡可能正確地恢復(fù)出原信息。譯碼算法的已知條件是：①實(shí)際接收到的碼字序列{r},r=(rn,rn-1,…,r1)②發(fā)端所采用的編碼算法和該算法產(chǎn)生的碼集Xn,滿足③信道模型及信道參數(shù)。576.2.2最優(yōu)譯碼與最大似然譯碼586.2.2最優(yōu)譯碼與最大似然譯碼1.最佳譯碼(最大后驗(yàn)概率譯碼)在已知r的條件下找出可能性最大的發(fā)碼作為譯碼估值，即令596.2.2最優(yōu)譯碼與最大似然譯碼2.最大似然譯碼在已知r的條件下使先驗(yàn)概率最大的譯碼算法

也叫似然函數(shù)。利用貝葉斯公司可以建立先驗(yàn)概率和后驗(yàn)概率之間的關(guān)系：606.2.2最優(yōu)譯碼與最大似然譯碼如果①構(gòu)成碼集的個(gè)碼字以相同概率發(fā)送，滿足。②對(duì)于任何r都有相同的值，滿足。則最大等效于的最大，在此前提下最佳譯碼等效于最大似然譯碼。616.2.2最優(yōu)譯碼與最大似然譯碼對(duì)于無(wú)記憶信道，

例：BSC信道的最大似然譯碼可以簡(jiǎn)化為最小漢明距離譯碼。漢明距離譯碼是一種硬判決譯碼。由于BSC信道是對(duì)稱的，只要發(fā)送的碼字獨(dú)立、等概，漢明距離譯碼也就是最佳譯碼。626.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è)信息元組以什么算法一一對(duì)應(yīng)映射到碼空間。

碼率－－編碼效率：Rc

=k/n

636.3線性分組碼為了敘述方便，以下認(rèn)為碼失、碼字、碼組是同義詞，對(duì)n重矢量、1n矩陣、行矢量等的數(shù)學(xué)表達(dá)式也不作嚴(yán)格區(qū)別。646.3線性分組碼設(shè)有等概出現(xiàn)的M組待傳信源消息，每組有k位，即。今加上r個(gè)多余位，使每組消息變成n=k+r位。而n位長(zhǎng)的二進(jìn)制序列共有2n個(gè)，但由于信息組只有2k個(gè)，故有2n-2k個(gè)n位序列不是碼字。設(shè)碼字的形式為：656.3.1生成矩陣和校驗(yàn)矩陣

線性分組碼碼空間C是由k個(gè)線性無(wú)關(guān)的基底張成的k維n重子空間，碼空間的所有元素（即碼字）都可以寫(xiě)成k個(gè)基底的線性組合，即這種線性組合特性正是線性分組碼名稱的來(lái)歷。顯然，研究線性分組碼的關(guān)鍵是研究基底、子空間和映射規(guī)則，如圖所示

666.3.1生成矩陣和校驗(yàn)矩陣Hn-k維n重對(duì)偶空間Dk維k重信息組空間mk維n重碼空間cGn維n重空間Vn676.3.1生成矩陣和校驗(yàn)矩陣用gi表示第i個(gè)基底并寫(xiě)成矩陣再將k個(gè)基底排列成k行n列的G矩陣686.3.1生成矩陣和校驗(yàn)矩陣碼空間的所有元素（即碼字）都可以寫(xiě)成k個(gè)基底的線性組合。由于k個(gè)基底即G的k個(gè)行矢量線性無(wú)關(guān)，矩陣G的秩一定等于k。當(dāng)信息元確定后，碼字僅由G矩陣決定，因此我們稱這k×n矩陣G為該(n,k)線性分組碼的生成矩陣。696.3.1生成矩陣和校驗(yàn)矩陣1.生成矩陣G(k×n)的特點(diǎn)想要保證(n,k)線性分組碼能夠構(gòu)成k維n重子空間，G

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

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

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

716.3.1生成矩陣和校驗(yàn)矩陣3.生成的碼字C

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

稱此方程為該（7,3）線性分組碼的校驗(yàn)方程，由于該碼系的所有碼字都按同一規(guī)則確定與校驗(yàn)，故又稱為一致校驗(yàn)方程。776.3.1生成矩陣和校驗(yàn)矩陣如：信息組為101，即代入一致校驗(yàn)方程得：所以由信息組101編出的可送給信道傳輸?shù)?、具有一定糾錯(cuò)能力的碼字為：1010011。同理可求出與其他7個(gè)信息組相對(duì)應(yīng)的碼字見(jiàn)下表：信息組對(duì)應(yīng)碼字對(duì)應(yīng)碼字信息組00000101001111111010110001110100100111001110100000001110100110100110100111001110786.3.1生成矩陣和校驗(yàn)矩陣為了運(yùn)算方便，可將一致校驗(yàn)方程組寫(xiě)成矩陣形式：796.3.1生成矩陣和校驗(yàn)矩陣設(shè)則：或：（4×3）單位子陣806.3.1生成矩陣和校驗(yàn)矩陣線性分組碼的一致生成矩陣與一致校驗(yàn)矩陣之間有著非常密切的關(guān)系，這種關(guān)系非常重要。下面說(shuō)明它們的關(guān)系：由于生成矩陣G的每一行都是一個(gè)碼字，而或者816.3.1生成矩陣和校驗(yàn)矩陣更進(jìn)一步：結(jié)論：(n,k)線性分組碼的一致生成矩陣G與一致校驗(yàn)矩陣H之間可方便地相互轉(zhuǎn)換。或者826.3.1生成矩陣和校驗(yàn)矩陣?yán)?.1(6,3)線性分組碼，其生成矩陣是836.3.1生成矩陣和校驗(yàn)矩陣求：(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à)出編碼器電原理圖。846.3.1生成矩陣和校驗(yàn)矩陣解(1)由得

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

866.3.1生成矩陣和校驗(yàn)矩陣(3)876.3.1生成矩陣和校驗(yàn)矩陣(4)m0m1m2c0c1c2輸入輸出886.3.2線性分組碼的糾錯(cuò)能力

N重碼矢可與N維矢量空間XN中的一個(gè)點(diǎn)對(duì)應(yīng)，全體碼字所對(duì)應(yīng)的點(diǎn)構(gòu)成矢量空間里的一個(gè)子集。發(fā)碼一定在這個(gè)子集里，傳輸無(wú)誤時(shí)的收碼也一定位于該子集。當(dāng)出現(xiàn)差錯(cuò)時(shí)，接收的N重矢量有兩種可能：一種是對(duì)應(yīng)到子集外空間某一點(diǎn)；另一種對(duì)應(yīng)到該子集，卻對(duì)應(yīng)到該子集的另一點(diǎn)上。

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

dmin=min{w(Ci

)} CiC

及Ci

0906.3.2線性分組碼的糾錯(cuò)能力

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

定理6.4(n,k)線性分組碼的最小距離必定小于等于(n-k+1)916.3.2線性分組碼的糾錯(cuò)能力例：(7，4)線性碼

926.3.2線性分組碼的糾錯(cuò)能力各列都不相同，任意2列之和不等于0，2列線性無(wú)關(guān)；任意2列之和一定等于矩陣中某一列，任意3列線性相關(guān)。所以該碼的最小距離為3，小于n-k+1=4。

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

(MDC–MaximizedminimumDistanceCode)。936.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼

定義差錯(cuò)圖案E

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

及R=C+E

1.伴隨式S的定義因?yàn)镃HT=0(碼字和校驗(yàn)矩陣的正交性)所以RHT=(C+E)HT=CHT+EHT=EHT946.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼

1、如果收碼無(wú)誤：必有R=C即E=0，則EHT=0RHT=0。

2、如果收碼有誤：即E

0，則RHT

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

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

956.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼

2.伴隨式S的意義從物理意義上看，伴隨式S并不反映發(fā)送的碼字是什么，而只是反映信道對(duì)碼字造成怎樣的干擾。

差錯(cuò)圖案E是n重矢量，共有2n個(gè)可能的組合，而伴隨式S是(n-k)重矢量，只有2n-k個(gè)可能的組合，因此不同的差錯(cuò)圖案可能有相同的伴隨式。

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

；如果能知道對(duì)應(yīng)的E，則通過(guò)C=R+E而求得C。966.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼

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

976.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼得到線性方程組：

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+e0h00986.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼上述方程組中有n個(gè)未知數(shù)en-1,…e1,e0

，卻只有n-k個(gè)方程，可知方程組有多解。在有理數(shù)或?qū)崝?shù)域中，少一個(gè)方程就可能導(dǎo)致無(wú)限多個(gè)解，而在二元域中，少一個(gè)方程導(dǎo)致兩個(gè)解，少兩個(gè)方程四個(gè)解，以此類推，少n-(n-k)=k個(gè)方程導(dǎo)致每個(gè)未知數(shù)有2k個(gè)解。到底取哪一個(gè)作為附加在收碼R上的差錯(cuò)圖案E的估值呢？

996.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼概率譯碼：把所有2k個(gè)解的重量(差錯(cuò)圖案E中1的個(gè)數(shù))作比較，選擇其中最輕者作為E的估值。該方法概念上很簡(jiǎn)單但計(jì)算效率不高。依據(jù)：若BSC信道的差錯(cuò)概率是p，則長(zhǎng)度n的碼中錯(cuò)誤概率：1006.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼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)則，即最大似然譯碼。依據(jù)：若BSC信道的差錯(cuò)概率是p，則長(zhǎng)度n的碼中錯(cuò)誤概率：1016.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼

方法：(1)按最可能出現(xiàn)的2r個(gè)差錯(cuò)圖案E，計(jì)算相應(yīng)的伴隨式S，并構(gòu)造伴隨式一差錯(cuò)圖案表[(S,E)]。(2)對(duì)接收向量R計(jì)算伴隨式S。(3)查[(S,E)]表得E。(4)糾錯(cuò)計(jì)算C=R-E。1026.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼例：設(shè)某（7,3）線性分組碼的一致校驗(yàn)矩陣為：發(fā)送端發(fā)送的碼字為（注：接收端譯碼器并不知道發(fā)送碼字）。試討論下面三種接收情況下的判錯(cuò)情形：1036.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼①接收端接收的碼字為②接收端接收的碼字為③接收端接收的碼字為解:①當(dāng)接收端接收的碼字為時(shí)，故譯碼器判為沒(méi)錯(cuò)。1046.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼②當(dāng)接收端接收的碼字為時(shí)，又由其H陣知該(7,3)碼為能糾1個(gè)錯(cuò)誤的碼型，且ST正好等于H陣中的第二列，因此可判定第二位有錯(cuò)。1056.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼③當(dāng)接收端接收的碼字為時(shí)，譯碼器判為有錯(cuò)。又由于此時(shí)的伴隨式ST與H中任一列均不同，故一定出現(xiàn)了兩位或兩位以上的錯(cuò)誤，譯碼器無(wú)法判定錯(cuò)誤究竟出現(xiàn)在哪些位上。1066.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼伴隨式計(jì)算電路(以上例中的(7,3)碼為例)設(shè)接收字為1076.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼碼字輸入移位寄存器組半加器1086.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼伴隨式計(jì)算電路組合邏輯電路糾錯(cuò)譯碼電路…………輸入（信道輸出）譯碼輸出1096.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼4.標(biāo)準(zhǔn)陣列譯碼表上述的概率譯碼，如每接收一個(gè)碼R就要解一次線性方程，那就太麻煩了。好在伴隨式S的數(shù)目是有限的2n-k個(gè)，如果n-k不太大，我們可以預(yù)先把不同S下的方程組解出來(lái)，把各種情況下的最大概率譯碼輸出列成一個(gè)碼表。這樣，在實(shí)時(shí)譯碼時(shí)就不必再去解方程，而只要象查字典那樣查一下碼表，這樣構(gòu)造的表格叫做標(biāo)準(zhǔn)陣列譯碼表。1106.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼表中所列碼字是接收到的碼字R；將沒(méi)有任何差錯(cuò)時(shí)的收碼R放在第一行，收碼等于發(fā)碼R=C(CCi,i=0,1,…2k-1),差錯(cuò)圖案為全零E0=(0,0…0)，伴隨式為全零S0=(0,0…0)。由于有2k個(gè)碼字，碼表有2k列。

在第2到第n+1的n行中差錯(cuò)圖案的所有重量為1(共n個(gè))。1116.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼如果(1+n)<2n-k，再在下面行寫(xiě)出全部帶有2個(gè)差錯(cuò)的圖案(共個(gè))。如果總行數(shù)(1+n+)仍然小于2n-k，再列出帶有3個(gè)差錯(cuò)的圖案，以此類推，直到放滿2n-k行，每行一個(gè)Ej,對(duì)應(yīng)一個(gè)不同的伴隨式Sj。這樣，表的行數(shù)2n-k正好等于伴隨式的數(shù)目。1126.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼S0E0S1E1

SjEj

E0+C0=0+0=0E0+C1=C1E0+Ci=CiE1+C0=E1

E1+CiEj+C0=EjEj+C1Ej+Ci

E1+C1

1136.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼譯碼表中有2n-k行，每行是一個(gè)陪集，每陪集的第一個(gè)元素(位于第一列)叫陪集首。同一陪集（同一行）中的所有元素對(duì)應(yīng)共同的一個(gè)伴隨式。第一行陪集的陪集首是全零伴隨式S0所對(duì)應(yīng)的全零差錯(cuò)圖案E0(無(wú)差錯(cuò))，而第j行陪集的陪集首是伴隨式Sj所對(duì)應(yīng)的重量最小的差錯(cuò)圖案Ej(C0=0,Rj=Ej)。1146.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼譯碼表中有2k列，每列是一個(gè)子集，每子集的第一個(gè)元素(位于第一行)叫子集頭。同一子集（同一列）中的所有元素對(duì)應(yīng)同一個(gè)碼字，第一列子集的子集頭是全零碼字C0，而第i列子集的子集頭是碼字Ci(E0=0,Ri=Ci)。1156.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼例6.3一個(gè)(5,2)系統(tǒng)線性碼的生成矩陣是G=設(shè)收碼R=(10101)，構(gòu)造標(biāo)準(zhǔn)陣列譯碼表，譯出發(fā)碼的估值解：(1)構(gòu)造標(biāo)準(zhǔn)陣列譯碼表。分別以信息組m=(00)、(01)、(10)、(11)及已知的G求得4個(gè)許用碼字為C1=(00000)、C2=(10111)、C3=(01101)、C4=(11010)。1166.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼求出校驗(yàn)矩陣：1176.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼列出方程組：伴隨式有2n-k=23=8種組合，差錯(cuò)圖案中代表無(wú)差錯(cuò)的有一種，代表一個(gè)差錯(cuò)的圖案有種，代表兩個(gè)差錯(cuò)的圖案有種。只需挑選其中的兩個(gè)，挑選方法可有若干種，不是唯一的。1186.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼先將Ej=(00000)、(10000)、(01000)、(00100)、(00010)、(00001)代入上面的線性方程組，解得對(duì)應(yīng)的Sj分別是(000)、(111)、(101)、(100)、(010)、(001)。剩下的伴隨式中，(011)所對(duì)應(yīng)的差錯(cuò)圖案是2k個(gè)即(00011)、(10100)、(01110)、(11001),其中(00011)和(10100)并列重量最輕，任選其中一個(gè)如(00011)。同樣可得伴隨式(110)所對(duì)應(yīng)的最輕差錯(cuò)圖案之一是(00110)。1196.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼S0=000E0+C0=00000C1=10111C2=01101C3=11010S1=111E1=10000001111110101010S2=101E2=01000111110010110010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=00001101100110011011S6=011E6=00011101000111011001S7=110E7=001101000101011111001206.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼將接收碼R＝10101譯碼可選以下三種方法之一譯碼：(1)直接搜索碼表，查得(10101)所在列的子集頭是(10111)，因此譯碼輸出取為(10111)。

(2)先求伴隨式RHT=(10101)

HT=(010)=S4，確定S4所在行，再沿著行對(duì)碼表作一維搜索找到(10101),最后順著所在列向上找出碼字(10111)。1216.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼

(3)先求出伴隨式RHT=(010)=S4并確定S4所對(duì)應(yīng)的陪集首（差錯(cuò)圖案）E4=(00010)，再將陪集首與收碼相加得到碼字C=R+E4=(10101)+(00010)=(10111)。上述三種方法由上而下，查表的時(shí)間下降而所需計(jì)算量增大，實(shí)際使用時(shí)可針對(duì)不同情況選用。1226.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼對(duì)上例作進(jìn)一步分析，還可以看到，該(5,2)碼的dmin=3,糾錯(cuò)能力是t=INT[(3-1)/2]=1。因此，譯碼陣列中只有前6行具有唯一性、可靠性，真正體現(xiàn)了最大似然譯碼準(zhǔn)則，而第7、8行的差錯(cuò)圖案(00011)和(00110)中包含兩個(gè)“1”，已超出了t=1的糾錯(cuò)能力，譯碼已不可靠。1236.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼比如，當(dāng)收碼R＝(10100)時(shí)，根據(jù)碼表譯出的碼字是(10111)，與收碼R的漢明距離是2，然而收碼R與全零碼字(00000)的漢明距離也是2，為什么不能譯成(00000)呢？事實(shí)上，碼表的第7、8行本身就不是唯一的。注意在碼表計(jì)算過(guò)程中，伴隨式(011)所對(duì)應(yīng)的4個(gè)差錯(cuò)圖案中有兩個(gè)并列重量最輕，如果當(dāng)時(shí)選的不是(00011)而是(10100)，那么碼表第7行就不是現(xiàn)在這樣了。1246.3.4完備碼(Perfectcode)任何一個(gè)二元(n,k)線性分組碼都有2n-k個(gè)伴隨式，假如該碼的糾錯(cuò)能力是t，則對(duì)于任何一個(gè)重量小于等于t的差錯(cuò)圖案，都應(yīng)有一個(gè)伴隨式與之對(duì)應(yīng)，也就是說(shuō)，伴隨式的數(shù)目滿足條件上式稱作漢明限，任何一個(gè)糾t碼都應(yīng)滿足上述條件。1256.3.4完備碼(Perfectcode)某二元(n,k)線性分組碼能使等式

成立，即該碼的伴隨式數(shù)目不多不少恰好和不大于t個(gè)差錯(cuò)的圖案數(shù)目相等，相當(dāng)于在標(biāo)準(zhǔn)譯碼陣列中能將所有重量不大于t的差錯(cuò)圖案選作陪集首，而沒(méi)有一個(gè)陪集首的重量大于t，這時(shí)的校驗(yàn)位得到最充分的利用。這樣的二元(n,k)線性分組碼稱為完備碼。

1266.3.4完備碼(Perfectcode)1.漢明碼(HammingCode)

漢明碼不是指一個(gè)碼，而是代表一類碼。漢明碼的糾錯(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)……。1276.3.4完備碼(Perfectcode)漢明碼是完備碼，因?yàn)樗鼭M足上述等式。1286.3.4完備碼(Perfectcode)漢明碼的校驗(yàn)矩陣H具有特殊的性質(zhì)，能使構(gòu)造方法簡(jiǎn)化。一個(gè)(n,k)碼的校驗(yàn)矩陣有n-k行和n列，二進(jìn)制時(shí)n-k個(gè)碼元所能組成的列矢量總數(shù)是2n-k-1,恰好和校驗(yàn)矩陣的列數(shù)n=2m-1相等。只要排列所有列，通過(guò)列置換將矩陣H轉(zhuǎn)換成系統(tǒng)形式，就可以進(jìn)一步得到相應(yīng)的生成矩陣G。1296.3.4完備碼(Perfectcode)例6.4構(gòu)造一個(gè)m=3的二元(7，4)漢明碼。解：先利用漢明碼的特性構(gòu)造一個(gè)(7，4)漢明碼的校驗(yàn)矩陣H，再通過(guò)列置換將它變?yōu)橄到y(tǒng)形式：

0001111列置換1110100 H= 0110011 0111010=[PT

I3] 1010101 1101001再得生成矩陣G為

1000101 G=[I4

P]=0100111 0010110 0001011 1306.3.4完備碼(Perfectcode)

2.高萊（Golay）碼是二進(jìn)制（23，12）線性碼，其最小距離dmin＝7，糾錯(cuò)能力t=3。是完備碼，因?yàn)闈M足等式

223-12=2048=在(23,12)碼上添加一位奇偶位即得二進(jìn)制線性（24，12）擴(kuò)展高萊碼，其最小距離dmin＝8。1316.3.5循環(huán)碼

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

(0000000)

(0010111)(0101110)(1011100)(0111001)(1110010)(1100101)(1001011)1326.3.5循環(huán)碼又如：(7,4)循環(huán)碼分成四個(gè)組

(0000000)

(1111111)

(1000101)(0001011)(0010110)(0101100)(1011000)(0110001)(1100010)

(1001110)(0011101)(0111010)(1110100)(1101001)(1010011)(0100111)1336.3.5循環(huán)碼

定義2:一個(gè)(n,k)線性分組碼C，若它一個(gè)碼矢的每一循環(huán)移位都是C的一個(gè)碼字，則C是一個(gè)循環(huán)碼。

循環(huán)碼是一種線性碼，因此線性碼的一切特性均適合于循環(huán)碼；但它的特殊性是其循環(huán)性，碼字集合或者說(shuō)碼組中任意一個(gè)碼字的循環(huán)移位得到的序列仍是該碼字集合中的碼字，即它對(duì)循環(huán)操作滿足封閉性。1346.3.5循環(huán)碼2.循環(huán)碼的多項(xiàng)式描述一般(n,k)線性分組碼的k個(gè)基底之間不存在規(guī)則的聯(lián)系，因此需用k個(gè)基底組成生成矩陣來(lái)表示一個(gè)碼的特征。而循環(huán)碼的k個(gè)基底可以是同一個(gè)基底循環(huán)k次得到，因此用一個(gè)基底就足以表示一個(gè)碼的特征。既然只有一個(gè)基底，就無(wú)需矩陣，只要用多項(xiàng)式作為數(shù)學(xué)工具就足夠了。1356.3.5循環(huán)碼3.循環(huán)碼的多項(xiàng)式定義把碼字C＝[cn-1cn-2

…c1c0]與一個(gè)不大于n-1次的碼多項(xiàng)式C(x)對(duì)應(yīng)起來(lái)。

碼多項(xiàng)式C(x)定義為：

C(x)=cn-1xn-1+cn-2xn-2

+…+c1x+c0

對(duì)于二進(jìn)制碼，ci{0,1},i=0,…，n-1。1366.3.5循環(huán)碼循環(huán)移一位：(cn-1cn-2

…c1c0)(cn-2

…c1c0cn-1)循環(huán)移一位：C0(x)=cn-1xn-1+cn-2xn-2+…+c1x+c0

C1(x)=

cn-2xn-1+cn-3xn-2+…+c0x+cn-1比較循環(huán)移位的前后，可用如下的多項(xiàng)式運(yùn)算來(lái)表達(dá)循環(huán)移位

移1位：

C1(x)=xC0(x) mod(xn+1)

移2位：

C2(x)=xC1(x)=x2C0(x) mod(xn+1)

移n-1位：Cn-1(x)=xCn-2(x)=xn-1C0(x) mod(xn+1)1376.3.5循環(huán)碼4.碼字的組成根據(jù)碼空間封閉性，碼字的線性組合仍是碼字。C(x)=a0C0(x)+a1xC0(x)+a2x2C0(x)+…+an-1xn-1C0(x)=(a0+a1x

+a2x2+…+an-1xn-1)C0(x)=A(x)C0(x) mod(xn

+1) 其中C0(x)是一個(gè)碼多項(xiàng)式，而A(x)是次數(shù)不大于n-1的任意多項(xiàng)式。對(duì)于二進(jìn)制碼，ai{0,1},i=0,…，n-1。1386.3.5循環(huán)碼5.生成多項(xiàng)式C(x)=m(x)g(x)碼多項(xiàng)式信息多項(xiàng)式生成多項(xiàng)式

生成多項(xiàng)式不是唯一的；

g(x)＝x

n-k

+gn-k-1x

n-k-1+…+g2x2+g1x+1

是(n-k)次的首一碼多項(xiàng)式，即(n-k)次項(xiàng)的系數(shù)為1。g(x)一定是(xn+1)的因子。1396.3.5循環(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)式。1406.3.5循環(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)碼碼系。以上幾個(gè)定理說(shuō)明：構(gòu)建一個(gè)(n,k)循環(huán)碼時(shí)，只要分解多項(xiàng)式xn+1的因式，從中取出(n-k)次因式作生成多項(xiàng)式即可。1416.3.5循環(huán)碼6.校驗(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)1426.3.5循環(huán)碼例6.5研究一個(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)1436.3.5循環(huán)碼構(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)=x5+x2+x1+

1， 對(duì)應(yīng)碼矢C=(0100111)。1446.3.5循環(huán)碼信息矢量m(m2m1m0)碼矢C(c6c5c4c3c2c1c0)000001010011100101110111000000000111010111010010011111101001101001100111010100111456.3.5循環(huán)碼6.系統(tǒng)循環(huán)碼碼字的前k位原封不動(dòng)照搬信息位而后面(n-k)位為校驗(yàn)位：C(x)=xn-km(x)+r(x)產(chǎn)生系統(tǒng)循環(huán)碼的方法：將信息多項(xiàng)式m(x)預(yù)乘xn-k，即右移(n-k)位；將xn-km(x)除以g(x)，得余式r(x)；得系統(tǒng)循環(huán)碼的碼多項(xiàng)式：C(x)=xn-km(x)+r(x)。1466.3.5循環(huán)碼例6.6(7,3)循環(huán)碼生成多項(xiàng)式是g(x)=x4+x3+x2+1，產(chǎn)生系統(tǒng)循環(huán)碼。解：先以輸入信息m=(011)即m(x)=(x+1)為例，①.xn-km(x)=x4(x+1)=x5+x4

②.(x5+x4)除以(x4+x3+x2+

1)，得余式(x3+x)③.C(x)=xn-km(x)

+r(x)＝(x5+x4)+(x3+x),