第6章信道編碼信道編碼是以信息在信道上的正確傳輸為目標的編碼，可分為兩個層次上的問題：如何正確接收載有信息的信號 －－線路編碼如何避免少量差錯信號對信息內(nèi)容的影響 －－糾錯編碼1本章內(nèi)容有擾離散信道的編碼定理糾錯編譯碼的基本原理與分析方法線性分組碼卷積碼26.1 有擾離散信道的編碼定理差錯和差錯控制系統(tǒng)分類矢量空間與碼空間隨機編碼信道編碼定理3差錯類型差錯符號：由符號發(fā)生差錯引起，也叫信號差錯，信號差錯概率用誤碼元率表示；差錯比特：由信息比特發(fā)生差錯引起，也叫信息差錯，信息差錯概率用誤比特率表示；對于二進制傳輸系統(tǒng)，符號差錯等效于比特差錯；對于多進制系統(tǒng)，一個符號差錯到底對應(yīng)多少比特差錯卻難以確定。因為一個符號由多個比特組成。4差錯圖樣（errorpattern）為了定量地描述信號的差錯，定義收、發(fā)碼之“差”為： 差錯圖樣E＝發(fā)碼C－收碼R

（模M）例：8進制(M=8)碼元， 若發(fā)碼 C=（0,2,5,4,7,5,2） 收碼變?yōu)?R=（0,1,5,4,7,5,4） 差錯圖樣 E=C－R=（0,1,0,0,0,0,6）（模8）5差錯圖樣（errorpattern）二進制碼：E=CR或

C=RE

，差錯圖樣中的“１”既是符號差錯也是比特差錯，差錯的個數(shù)叫漢明距離。6差錯圖樣類型隨機差錯：若差錯圖樣上各碼位的取值既與前后位置無關(guān)又與時間無關(guān)，即差錯始終以相等的概率獨立發(fā)生于各碼字、各碼元、各比特；突發(fā)差錯：前后相關(guān)、成堆出現(xiàn)。突發(fā)差錯總是以差錯碼元開頭、以差錯碼元結(jié)尾，頭尾之間并不是每個碼元都錯，而是碼元差錯概率超過了某個額定值。7糾錯碼分類從功能角度：檢錯碼、糾錯碼對信息序列的處理方法：分組碼、卷積碼碼元與原始信息位的關(guān)系：線性碼、非線性碼差錯類型：糾隨機差錯碼、糾突發(fā)差錯碼、介于中間的糾隨機/突發(fā)差錯碼。構(gòu)碼理論：代數(shù)碼、幾何碼、算術(shù)碼、組合碼等8差錯控制系統(tǒng)分類前向糾錯（FEC）：發(fā)端信息經(jīng)糾錯編碼后傳送，收端通過糾錯譯碼自動糾正傳遞過程中的差錯反饋重發(fā)（ARQ）：收端通過檢測接收碼是否符合編碼規(guī)律來判斷，如判定碼組有錯，則通過反向信道通知發(fā)端重發(fā)該碼混合糾錯（HEC）：前向糾錯和反饋重發(fā)的結(jié)合，發(fā)端發(fā)送的碼兼有檢錯和糾錯兩種能力96.1.2矢量空間與碼空間基本的糾錯碼為（n,k）分組碼（塊碼）每塊為k個符號由n個碼元組成碼字碼字可視為n重矢量（n個矢量元素）106.1.2矢量空間與碼空間F表示碼元所在的數(shù)域(對于二進制碼，F(xiàn)代表二元域{0,1})設(shè)n重有序元素的集合V={Vi

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

對于域F上的若干矢量線性組合：

線性相關(guān)：

其中任一矢量可表示為其它矢量的線性組合線性無關(guān)或線性獨立：一組矢量中的任意一個都不可能用其它矢量的線性組合來代替.。12矢量空間與基底一組線性無關(guān)的矢量，其線性組合的集合就構(gòu)成了一個矢量空間V，這組矢量就是這個矢量空間的基底。n維矢量空間應(yīng)包含n個基底基底不是唯一的，例：線性無關(guān)的兩個矢量（1,0）和（0,1）以及（-1,0）和（0,-1）可張成同一個兩維空間。13二元域GF(2)上三重矢量空間以（100）為基底可張成一維三重子空間V1，含21=2個元素，即以(010)(001)為基底可張成二維三重子空間V2，含22=4個元素，即以(100)(010)(001)為基底可張成三維三重空間V,含23=8個元素，V1和V2都是V的子空間。14概念重數(shù)構(gòu)成矢量的有序元素的個數(shù)維數(shù)構(gòu)成矢量空間的基底的個數(shù)15矢量空間每個矢量空間或子空間中必然包含零矢量兩個矢量正交：V1V2＝0兩個矢量空間正交：某矢量空間中的任意元素與另一矢量空間中的任意元素正交正交的兩個子空間V1、V2互為對偶空間

(DualSpace)，其中一個空間是另一個空間的零空間（nullspace，也稱零化空間）。16碼空間

17

消息k長 (n,k)碼字n長

qk

種分組編碼器qn種

k維k重矢量n維n重矢量

通常qn>>qk，分組編碼的任務(wù)是要在n維n重矢量空間的qn種可能組合中選擇其中的qk個構(gòu)成一個碼空間，其元素就是許用碼的碼集。分組編碼的任務(wù)選擇一個ｋ維n重子空間作為碼空間。確定由k維k重信息空間到ｋ維n重碼空間的映射方法。碼空間的不同選擇方法，以及信息組與碼組的不同映射算法，就構(gòu)成了不同的分組碼。186.1.3隨機編碼編碼的分析設(shè)計途徑：1.數(shù)學解析途徑，即將代數(shù)、幾何、數(shù)論等理論運用到編解碼，如分組碼，卷積碼。2.運用概率統(tǒng)計方法在特定信道條件下對編碼信號的性能作出統(tǒng)計分析，求出差錯概率的上下限邊界，其中最優(yōu)碼所能達到的差錯概率上界稱作隨機碼界。用這種方法不能得知最優(yōu)碼是如何具體編出來的，卻能得知最優(yōu)碼可以好到什么程度，并進而推導出有擾離散信道的編碼定理，對指導編碼技術(shù)具有特別重要的理論價值。196.1.3隨機編碼對于一個(N,K)分組編碼器對K個q進制組成的消息組m=(m0,m1,…,mk-1)編碼；生成N個q進制符號組成的碼字c=(c0,c1,…cN-1)；在(N,K)分組編碼器中隨機選定的碼集有qNM種一個消息組的編碼有qN種選擇（N個碼元，q進制）qK個消息組共有種選擇令M=qK，可得上式206.1.3隨機編碼在(N,K)分組編碼器中隨機選定的碼集有qNM個第m個碼集(記作{c}m)被隨機選中的概率是設(shè)與這種選擇相對應(yīng)的條件差錯概率是Pe({c}m)全部碼集的平均差錯概率是216.1.3隨機編碼必定存在某些碼集某些碼集若，就必然存在一批碼集即差錯概率趨于零的好碼一定存在；226.1.3隨機編碼碼集點數(shù)M=qK占N維矢量空間總點數(shù)qN的比例是 F=qK/qN

=q-(N-K)

當K和N的差值拉大即冗余的空間點數(shù)增加時，平均而言碼字的分布將變得稀疏，碼字之間的平均距離將變大，平均差錯概率將變小。當F0即(N-K)時，能否讓平均差錯概率？

Gallager在1965年推導了的上邊界，并證明這個上邊界是按指數(shù)規(guī)律收斂的。236.1.4信道編碼定理E(R)為可靠性函數(shù)，也叫誤差指數(shù)；碼率：R=(lbM)

/N

M是可能的信息組合數(shù)，M=qKN是每碼字的碼元數(shù)，R表示每碼元攜帶的信息量，單位是比特每符號（bit/symbol）246.1.4信道編碼定理R在[0,R0]區(qū)間時：E(R)~R曲線是斜率為-1（-45）的直線，E(R)反比于R；而當R=C（信道容量）時：E(R)=0，即可靠性為零。25

E(R)

C

R0R0-45

E(R)和R的關(guān)系曲線6.1.4信道編碼定理正定理：只要傳信率R小于信道容量C，總存在一種信道碼（及解碼器），可以以所要求的任意小的差錯概率實現(xiàn)可靠的通信。逆定理：信道容量C是可靠通信系統(tǒng)傳信率R的上邊界，如果R>C，就不可能有任何一種編碼能使差錯概率任意小。266.2糾錯編譯碼的基本原理與分析內(nèi)容：糾錯編碼的基本思路譯碼方法－最優(yōu)譯碼與最大似然譯碼276.2.1糾錯編碼的基本思路R不變，信道容量大者其可靠性函數(shù)E(R)也大；C不變，碼率減小時其可靠性函數(shù)E(R)增大。28E(R) R0R1<R2C1

<C2

增大E(R)的途徑信道編碼定理6.2.1糾錯編碼的基本思路增大信道容量C

擴展帶寬：開發(fā)新的寬帶媒體加大功率：提高發(fā)送功率、提高天線增益降低噪聲：采用低噪聲器件減小碼率R

（R=(lbM)

/N

）Q、N不變而減小K

Q、K不變而增大NN、K不變而減小Q增大碼長N296.2.1糾錯編碼的基本思路另一種思路是從概念上分析糾錯編碼的基本原理，可以把糾錯能力的獲取歸結(jié)為兩條：一條是利用冗余度，另一條是噪聲均化（隨機化、概率化）30冗余度就是在信息流中插入冗余比特。例：3bit表示4種意義。為了傳輸這些冗余位，必然動用冗余的資源。這些資源可以是：時間、頻帶、功率、設(shè)備復雜度噪聲均化就是讓差錯隨機化，就是設(shè)法將危害較大的、較為集中的噪聲干擾分攤開來。1、增加碼長N例：設(shè)某BSC信道誤碼率Pe=0.01，假如編碼后的糾錯能力是10%。先設(shè)碼長N=10，碼字中多于1位誤碼時就會產(chǎn)生譯碼差錯，差錯概率為：6.2.1糾錯編碼的基本思路31如果保持碼率不變，將碼長增加到N=40，那么當碼字中多于4位誤碼時，會產(chǎn)生譯碼差錯，差錯的概率為卷積：卷積碼在一定約束長度內(nèi)的若干碼字之間加進了相關(guān)性，譯碼時不是根據(jù)單個碼字，而是一串碼字，這樣就可以將噪聲分攤到碼字序列而不是一個碼字上。交錯：交錯是對付突發(fā)差錯的有效措施。6.2.2最優(yōu)譯碼與最大似然譯碼譯碼器的任務(wù)是從受損的信息序列中盡可能正確地恢復出原信息。譯碼算法的已知條件是：實際接收到的碼字序列{r},r=(r1,r2,…,rN)發(fā)端所采用的編碼算法和該算法產(chǎn)生的碼集XN，滿足信道模型及信道參數(shù)。326.2.2最優(yōu)譯碼與最大似然譯碼最佳譯碼，也叫最大后驗概率譯碼(MAP:Maximumaposteriori)已知r的條件下找出可能性最大的發(fā)碼作為譯碼估值通過經(jīng)驗與歸納推測發(fā)碼的方法實現(xiàn)困難33

消息組mi

碼字ci

接收碼r

估值

消息編碼器信道譯碼消息還原6.2.2最優(yōu)譯碼與最大似然譯碼最大似然譯碼(MLD:MaximumLikelihoodDecoding)已知r的條件下使先驗概率最大的譯碼算法346.2.2最優(yōu)譯碼與最大似然譯碼如果構(gòu)成碼集的2K個碼字以相同概率發(fā)送，滿足P(ci)=1/2K

，i=1,2,…,2K

P(r)對于任何r都有相同的值，滿足P(r)=1/2K

則P(ci/r)最大等效于P(r/ci)的最大，在此前提下最佳譯碼等效于最大似然譯碼。356.2.2最優(yōu)譯碼與最大似然譯碼對于無記憶信道，

例：BSC信道的最大似然譯碼可以簡化為最小漢明距離譯碼。漢明距離譯碼是一種硬判決譯碼。由于BSC信道是對稱的，只要發(fā)送的碼字獨立、等概率，漢明距離譯碼也就是最佳譯碼。

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

=k/n

（二進制）；

Rc

=k*lbq/n(q進制)38

消息m (n,k)碼字c

m=(mk-1,…,m1,m0)

分組編碼器c=(cn-1,…,c1,c0)

qk<qn6.3.1

生成矩陣和校驗矩陣c＝mG1×n1×k

k×n

碼字消息生成矩陣

G＝[gk-1…g1g0]T，有k個(1×n)行矢量，如何選擇呢？

39線性分組碼的形成c=

mk-1

gk-1+…+

m1

g1+m0g0

碼空間的所有元素（即碼字）都可以寫成k個基底的線性組合；由于k個基底即G的k個行矢量線性無關(guān)，矩陣G的秩一定等于k。當信息元確定后，碼字僅由G矩陣決定，因此稱這k×n矩陣G為該(n,k)線性分組碼的生成矩陣。

40生成矩陣G(k×n)的特點想要保證(n,k)線性分組碼能夠構(gòu)成k維n重子空間，G的k個行矢量gk-1,…,g1,g0必須是線性無關(guān)的，只有這樣才符合作為基底的條件。由于基底不是唯一的，所以G也就不是唯一的。不同的基底有可能生成同一碼集，但因編碼涉及碼集和映射兩個因素，碼集一樣而映射方法不同也不能說是同樣的碼。41系統(tǒng)形式的生成矩陣(n,k)碼的任何生成矩陣都可以通過行運算（以及列置換）簡化成“系統(tǒng)形式”。G=[Ik

P]=Ik是k×k單位矩陣，P是k×(n-k)矩陣。42生成的碼字C前k位由單位矩陣Ik決定，等于把信息組m原封不動搬到碼字的前k位；其余的n-k位叫冗余位或一致校驗位，是前k個信息位的線性組合。這樣生成的（n,k）碼叫做系統(tǒng)碼。若生成矩陣G不具備系統(tǒng)形式，則生成的碼叫做非系統(tǒng)碼。系統(tǒng)化不改變碼集，只是改變了映射規(guī)則。43空間構(gòu)成n維n重空間有相互正交的n個基底選擇k個基底構(gòu)成碼空間C選擇另外的(n-k)個基底構(gòu)成空間DC和H是對偶的

CDT＝0,GHT=044

n維n重空間V

k維k重k維n重n-k維信息組碼空間n重對偶

空間mC空間D

GH對偶空間與(n,k)分組線性碼的碼空間C相對應(yīng)，必然存在一個對偶空間D：碼空間基底數(shù)為k,找出另外n-k個基底，可找到對偶空間；用n-k個基底生成的(n,n-k)分組線性碼，稱為(n,k)分組線性碼的對偶碼。45校驗矩陣將H空間的n-k個基底排列起來可構(gòu)成一個(n-k)×n矩陣，稱為校驗矩陣H。用來校驗接收到的碼字是否是正確的；cHT=0(任意碼字正交與H的任意行矢量)G是(n,k)碼的生成矩陣，H是它的校驗矩陣；H是(n,n-k)對偶碼的生成矩陣，它的每一行是一個基底。G則是它的校驗矩陣。（對偶是相互的）GHT=0，H＝[－

PTIn-k]，二進制時，負號可省略。46例6-2 (6,3)線性分組碼，其生成矩陣是

G=求：(1)計算碼集，列出信息組與碼字的映射關(guān)系。(2)將該碼系統(tǒng)化處理后，計算系統(tǒng)碼碼集并列出映射關(guān)系。(3)計算系統(tǒng)碼的校驗矩陣H。若收碼r=[100110],檢驗它是否碼字？(4)根據(jù)系統(tǒng)碼生成矩陣畫出編碼器電原理圖。

47111010①110001②011101③例6-2碼集與映射關(guān)系（1）

c=

mk-1

gk-1+…+

m1

g1+m0g0

48信息碼字系統(tǒng)碼字000000000000000001 011101 001011010 110001 010110011 101100 011101100 111010 100111101 100111 101100110 001011 110001111 010110 111010111010①110001②011101③例6-2計算系統(tǒng)碼碼集（2）

將G改寫成=[Ik

P]形式：49111010①110001②011101③原①③行相加作為第1行；原①②③行相加作為第2行；原①②行相加作為第3行；得到矩陣：100111①010110②001011③例6-2計算系統(tǒng)碼碼集（2）

c=

mk-1

gk-1+…+

m1

g1+m0g0

，結(jié)果如下：50信息碼字系統(tǒng)碼字000000000000000001 011101 001011010 110001 010110011 101100 011101100 111010 100111101 100111 101100110 001011 110001111 010110 111010100111①010110②001011③碼集未變，但映射關(guān)系變了！例6-2計算校驗矩陣H（3）

51100|111010|110001|011G==[I3|P],H=[PT|In-k]=110|100111|010101|001不同的3個基底分別構(gòu)成了碼空間和對偶碼空間；若收碼r=[100110]，rHT=[100110]=[001]≠0,不是碼字。

例6-2編碼器電原理圖（4）：52C=(c5,c4,c3,c2,c1,c0=(m2,m1,m0,c2,c1,c0)=m2[100111]+m1[010110]+m0[001011],求解得到：C5=m2C4=m1C3=m0c2=m2+m1C1=m2+m1+m0C0=m2+m0100|111010|110001|011例6-2編碼器電原理圖（4）：53m0

m1

m2

輸入 輸出

c0

c1

c26.3.2伴隨式與標準陣列譯碼mC=(cn-1,…,c1,c0)R=(rn-1,…,r1,r0)

(n,k)信道定義差錯圖案EE＝(en－1,…,e1,e0)＝R－C

＝(rn-1－cn-1,…,r1－c1,r0－c0)二進制碼中模2加與模2減是等同的，因此有 E=R＋C及 R=C＋E 54伴隨式S的定義因為CHT=0（碼字與校驗矩陣的正交性）所以RHT＝(C＋E)HT＝CHT＋EHT=EHT如果收碼無誤：必有R＝C即E＝0，則EHT=0RHT=0。如果收碼有誤：即E0，則RHT=EHT0。在HT固定的前提下，RHT僅僅與差錯圖案E有關(guān)，而與發(fā)送碼C無關(guān)。定義伴隨式S

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

55

伴隨式S的意義從物理意義上看，伴隨式S并不反映發(fā)送的碼字是什么，而只是反映信道對碼字造成怎樣的干擾。差錯圖案E是n重矢量，共有2n個可能的組合，而伴隨式S是(n-k)重矢量，只有2n-k個可能的組合，因此不同的差錯圖案可能有相同的伴隨式。接收端收到R后，因為已知HT，可求出S＝RHT；如果能知道對應(yīng)的E，則通過C=R＋E而求得C。

56RHT=S ?C=R＋ERSEC

只要E正確，譯出的碼也就是正確的。

差錯圖案E的求解(1)可以通過解線性方程求解E：

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

=(en-1,…e1,e0)得到線性方程組：

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+e0h0057差錯圖案E的求解(2)上述方程組中有n個未知數(shù)en－1,…e1,e0

，卻只有n-k個方程，可知方程組有多解。在有理數(shù)或?qū)崝?shù)域中，少一個方程就可能導致無限多個解，而在二元域中，少一個方程導致兩個解，少兩個方程四個解，以此類推，少n-(n-k)=k個方程導致每個未知數(shù)有2k個解。因此，由上述方程組解出的E可以有2k個解。到底取哪一個作為附加在收碼R上的差錯圖案E的估值呢？概率譯碼：把所有2k個解的重量(差錯圖案E中1的個數(shù))作比較，選擇其中最輕者作為E的估值。該方法概念上很簡單但計算效率不高。5859依據(jù)：若BSC信道的差錯概率是p，則長度n的碼中錯誤概率：

0個錯1個錯2個錯…n個錯

(1-p)n

p(1-p)n-1

p2(1-p)n-2

pn

由于p<<1,>>>>>>…>>

出錯越少的情況，發(fā)生概率越大，E的重量越輕。所以該譯碼方法實際上體現(xiàn)了最小距離譯碼準則，即最大似然譯碼。標準陣列譯碼表

上述的概率譯碼，如每接收一個碼R就要解一次線性方程，太麻煩！伴隨式S的數(shù)目是有限的2n-k個，如果n-k不太大，可以預先把不同S下的方程組解出來，把各種情況下的最大概率譯碼輸出列成一個碼表。在實時譯碼時就不必再去解方程，而只要象查字典那樣查一下碼表就可以了。這樣構(gòu)造的表格叫做標準陣列譯碼表。60標準陣列譯碼表的構(gòu)成表中所列碼字是接收到的碼字R；將沒有任何差錯時的收碼R放在第一行，收碼等于發(fā)碼R=C(CCi,i=0,1,…2k-1),差錯圖案為全零E0=(0,0…0)，伴隨式為全零S0=(0,0…0)。由于有2k個碼字，碼表有2k列。在第2到第n+1的n行中差錯圖案的所有重量為1(共n個)。61如果總行數(shù)(1+n+)仍然小于2n-k，再列出帶有3個差錯的圖案，以此類推，直到放滿2n-k行，每行一個Ej,對應(yīng)一個不同的伴隨式Sj。這樣，表的行數(shù)2n-k正好等于伴隨式的數(shù)目。如果(1+n)<2n-k，再在下面行寫出全部帶有2個差錯的圖案(共個)。62S0E0S1E1

SjEj

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

E1+CiEj+C0=EjEj+C1Ej+Ci

標準陣列譯碼表在碼表的第j行、第i列填入Ci+Ej：E1+C1

陪集和子集譯碼表中有2n-k行，每行是一個陪集，每陪集的第一個元素(位于第一列)叫陪集首。同一陪集（同一行）中的所有元素對應(yīng)共同的一個伴隨式。第一行陪集的陪集首是全零伴隨式S0所對應(yīng)的全零差錯圖案E0(無差錯)，而第j行陪集的陪集首是伴隨式Sj所對應(yīng)的重量最小的差錯圖案Ej(C0=0,Rj=Ej)。譯碼表中有2k列，每列是一個子集，每子集的第一個元素(位于第一行)叫子集頭。同一子集（同一列）中的所有元素對應(yīng)同一個碼字，第一列子集的子集頭是全零碼字C0，而第i列子集的子集頭是碼字Ci(E0=0,Ri=Ci)。6364例

6-3

一個(5,2)系統(tǒng)線性碼的生成矩陣是G=設(shè)收碼R=(10101)，構(gòu)造標準陣列譯碼表，譯出發(fā)碼的估值解：(1)構(gòu)造標準陣列譯碼表。分別以信息組m=(00)、(01)、(10)、(11)及已知的G求得4個許用碼字為（c=

mk-1

gk-1+…+

m1

g1+m0g0=mG)C1=(00000)、C2=(10111)、C3=(01101)、C4=(11010)。求出校驗矩陣：

H=[PTI3]=列出方程組：S=EHT65伴隨式有2n-k＝23＝8種組合，差錯圖案中代表無差錯的有一種，代表一個差錯的圖案有種，已有6種。代表兩個差錯的圖案有種。只需挑選其中的兩個就可湊足8種組合。挑選方法可有若干種，不是唯一的。先將Ej=(00000)、(10000)、(01000)、(00100)、(00010)、(00001)代入上面的線性方程組，解得對應(yīng)的Sj分別是(000)、(111)、(101)、(100)、(010)、(001)。剩下的伴隨式中，(011)所對應(yīng)的差錯圖案是2k個即(00011)、(10100)、(01110)、(11001),其中(00011)和(10100)并列重量最輕，任選其中一個如(00011)。同樣可得伴隨式(110)所對應(yīng)的最輕差錯圖案之一是(00110)。例6-3譯碼表的構(gòu)成66S0=000E0+C0=00000C1=10111C2=01101C3=11010S1=111E1=10000001111110101010S2=101E2=01000111110010110010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=00001101100110011011S6=011E6=00011101000111011001S7=110E7=00110100010101111100例6-3標準陣列譯碼表（第j行、第i列填入Ci+Ej）例6-3將接收碼R＝10101譯碼

可選以下三種方法之一譯碼：直接搜索碼表，查得(10101)所在列的子集頭是(10111)，因此譯碼輸出取為(10111)。先求伴隨式RHT=(10101)HT=(010)=S4，確定S4所在行，再沿著行對碼表作一維搜索找到(10101),最后順著所在列向上找出碼字(10111)。先求出伴隨式RHT=(010)=S4并確定S4所對應(yīng)的陪集首（差錯圖案）E4=(00010)，再將陪集首與收碼相加得到碼字C=R+E4=(10101)+(00010)=(10111)。上述三種方法由上而下，查表的時間下降而所需計算量增大，實際使用時可針對不同情況選用。6768

對上例作進一步分析，還可以看到，該(5,2)碼的dmin=3,糾錯能力是t=INT[(3-1)/2]=1。因此，譯碼陣列中只有前6行具有唯一性、可靠性，真正體現(xiàn)了最大似然譯碼準則，而第7、8行的差錯圖案(00011)和(00110)中包含兩個“1”，已超出了t=1的糾錯能力，譯碼已不可靠。比如，當收碼R＝(10100)時，根據(jù)碼表譯出的碼字是(10111)，與收碼R的漢明距離是2，然而收碼R與全零碼字(00000)的漢明距離也是2，為什么不能譯成(00000)呢？事實上，碼表的第7、8行本身就不是唯一的。注意在碼表計算過程中，伴隨式(011)所對應(yīng)的4個差錯圖案中有兩個并列重量最輕，如果當時選的不是(00011)而是(10100)，那么碼表第7行就不是現(xiàn)在這樣了。對例6-3的分析6.3.3碼距、糾錯能力、MDC碼及重量譜N重碼矢c=(cn-1,cn-2,…c1,c0)可與N維矢量空間XN中的一個點對應(yīng)，全體碼字所對應(yīng)的點構(gòu)成矢量空間里的一個子集；發(fā)碼一定在這個子集里，傳輸無誤時的收碼也一定位于該子集；當出現(xiàn)差錯時，接收的N重矢量:對應(yīng)到子集外空間某一點；對應(yīng)到該子集，卻對應(yīng)到該子集的另一點上；696.3.3碼距、糾錯能力、MDC碼及重量譜碼集各碼字間的距離是不同的，碼距最小者決定碼的特性，稱之為最小距離dmin；dmin表明各碼字差異程度，差異越大，抗干擾能力越強；這里dmin=3，糾錯能力是1，檢錯能力是270td=7dmin=3d=5C1C2C3C4C56.3.3碼距、糾錯能力、MDC碼及重量譜定理6.1

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

dmin=min{w(Ci)} CiC及Ci

0 6.3.3碼距、糾錯能力、MDC碼及重量譜定理6.3(n,k)線性分組碼最小距離等于dmin的充要條件是：校驗矩陣H中有（dmin-1)列線性無關(guān)。定理6.4(n,k)線性分組碼的最小距離必定小于等于(n-k+1) dmin

(n-k+1) 726.3.3碼距、糾錯能力、MDC碼及重量譜例：

H＝(7，4)線性碼各列都不相同，任意2列之和不等于0，2列線性無關(guān)；任意2列之和一定等于矩陣中某一列，任意3列線性相關(guān)。所以該碼的最小距離為3，小于n-k+1＝4。736.3.3碼距、糾錯能力、MDC碼及重量譜（n,k）線性碼最小距離dmin的上邊界是n-k+1。如果我們設(shè)計的（n,k）線性碼的dmin達到了n-k+1，就是達到了設(shè)計性能的極點。因此，dmin＝n-k+1的碼稱為極大最小距離碼

(MDC–MaximizedminimumDistanceCode)?？傮w的、平均的糾錯能力不但與最小距離有關(guān)，而且與其余碼距或者說與碼字的重量分布特性有關(guān)。746.3.4 完備碼(Perfectcode)任何一個二元(n,k)線性分組碼都有2n-k個伴隨式，假如該碼的糾錯能力是t，則對于任何一個重量小于等于t的差錯圖案，都應(yīng)有一個伴隨式與之對應(yīng)，也就是說，伴隨式的數(shù)目滿足條件75上式稱作漢明限，任何一個糾t碼都應(yīng)滿足上述條件。6.3.4 完備碼

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

漢明碼(HammingCode)漢明碼不是指一個碼，而是代表一類碼。漢明碼的糾錯能力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)、(255,247)…。漢明碼是完備碼，因為它滿足下述等式：77高萊（Golay）碼是二進制（23，12）線性碼，其最小距離dmin＝7，糾錯能力t=3。是完備碼，因為滿足等式

223-12=2048=78在(23,12)碼上添加一位奇偶位即得二進制線性（24，12）擴展高萊碼，其最小距離dmin＝8。

6.3.5循環(huán)碼循環(huán)碼是線性碼的一個子類；滿足下列循環(huán)移位特性：碼集C中任何一個碼字的循環(huán)移位仍是碼字。79循環(huán)碼的多項式描述一般(n,k)線性分組碼的k個基底之間不存在規(guī)則的聯(lián)系，因此需用k個基底組成生成矩陣來表示一個碼的特征。而循環(huán)碼的k個基底可以是同一個基底循環(huán)k次得到，因此用一個基底就足以表示一個碼的特征。既然只有一個基底，就無需矩陣，只要用多項式作為數(shù)學工具就足夠了。80循環(huán)碼的多項式定義把碼字C＝[cn-1cn-2

…c1c0]與一個不大于n-1次的碼多項式C(x)對應(yīng)起來。碼多項式C(x)定義為：

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

+…+c1x+c0

對于二進制碼，ci{0,1},i=0,…，n-1。81循環(huán)碼的循環(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)移位的前后，可用如下的多項式運算來表達循環(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)82碼字的組成根據(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)是一個碼多項式，而A(x)是次數(shù)不大于n-1的任意多項式。對于二進制碼，ai{0,1},i=0,…，n-1。83生成多項式

C(x)=m(x)g(x)

碼多信息生成項式多項式多項式生成多項式不是唯一的；g(x)＝x

n-k

+gn-k-1x

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

是(n-k)次的首一碼多項式，即(n-k)次項的系數(shù)為1。g(x)一定是(xn+1)的因子。84校驗多項式多項式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)85例6.5

研究一個長度n=7的循環(huán)碼的構(gòu)成方法(1) 對(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)86例6.5

研究一個長度n=7的循環(huán)碼的構(gòu)成方法若構(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)。當輸入信息m=(011)時，m(x)=(x+1)，C(x)=(x+

1)(x4＋x3＋x2＋1)=x5+x2+x1+

1， 對應(yīng)碼矢C=(0100111)。87例6.5

研究一個長度n=7的循環(huán)碼的構(gòu)成方法信息矢量m(m2m1m0)碼矢C(c6c5c4c3c2c1c0)0000010100111001011101110000000001110101110100100111111010011010011001110101001188作業(yè)89復習并掌握課堂上講概念的例題！系統(tǒng)循環(huán)碼碼字的前k位原封不動照搬信息位而后面(n－k)位為校驗位：C(x)=xn-km(x)+r(x)產(chǎn)生系統(tǒng)循環(huán)碼的方法：將信息多項式m(x)預乘xn-k；將xn-km(x)除以g(x)，得余式r(x)；得系統(tǒng)循環(huán)碼的碼多項式：C(x)=xn-km(x)

+r(x)。9091例6.6

(7,3)循環(huán)碼生成多項式是g(x)=x4+x3+x2+1，用式(6-3-35)產(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),對應(yīng)碼矢(0111010)。依次將(000)…(111)代入，可得全部碼矢如表6-6。此表與表6-5對比，可見碼集未變而映射規(guī)則變了，表6-6滿足系統(tǒng)循環(huán)碼要求。

擴展碼

如果給每個碼字添加一位奇偶校驗位c校，構(gòu)成（n＋1，k）線性碼，稱為擴展碼。

[cn-1,…,c1,c0] [cn-1,…,c1,c0,c校] c

n－1…c1c0

c

校＝0在二進制偶校驗時：原來碼字中1的個數(shù)為偶數(shù)，則添加校驗位0；原來碼字中1的個數(shù)為奇數(shù)，則添加校驗位1。如果某碼原來的最小重量dmin是奇數(shù)，則新的最小距離變?yōu)閐min+1，檢錯能力增1。

校驗矩陣He＝92

H縮短碼

把第一位為1的所有碼字舍去，剩下另一半第一位為0的碼字舍去它們的第一位后組成一個新的(n－1，k－1)碼，稱為縮短碼。碼長n－1和信息位長度k－1均縮短了。(n－1，k－1)縮短碼共包含2k2=2k-1個碼字。由于原先保留的均是第一位為0的碼，舍去它們的第一位不會改變碼的最小重量，因此縮短碼與原碼具有同樣的dmin。稱為（n-1,k-1,dmin）縮短碼。9394例：(7,4)碼的生成矩陣為

4×7m3m2m1m0ci2ci1ci000000000001011001011000111010100111010110001100010111010Ci＝mG

＝[m3m2m1m0]

碼字中的c6去掉，c6是信息位m與G的第一列相乘結(jié)果，所以G的第一列應(yīng)去掉；m3去掉，而m3是與G的第一行相乘，所以G的第一行也去掉。95得到新的生成矩陣為G’＝

3×6原來的校驗矩陣H為H＝

3×7校驗時，計算rHT，因r的第一位已沒有，故HT的第一行應(yīng)去掉，即H的第一列去掉。得到新的校驗矩陣H’為

H’＝dmin不變，為3。

3×6循環(huán)冗余校驗(CRC)碼信息位k和碼長n可變，校驗位長度n-k固定，符合(n-i,k-i)縮短循環(huán)碼的特點。以一個選定的(n,k)循環(huán)碼為基礎(chǔ)，改變i值，得出任意信息長度的碼字，而糾檢錯能力保持不變。循環(huán)冗余校驗碼（(CRC-CyclicRedundancyCheck)）是系統(tǒng)的縮短循環(huán)碼。9697例6－10

某CRC碼的生成多項式g(x)=x4+x+1。如果想發(fā)送一串信息110001…的前6位并加上CRC校驗，發(fā)碼應(yīng)如何安排？收碼又如何檢驗？解：本題信息多項式m(x)=x5+x4+1,即k=6，因此n=10，deg[g(x)]=4=n-k

。將xn-km(x)除以g(x),得余式

r(x)=xn-km(x)modg(x)=x4(x5+x4+1)modg(x)=(x9+x8+x4)modg(x)=x3+x2

于是發(fā)碼C(x)=xn-km(x)+r(x)=x9+x8+x4

+x3+x2，對應(yīng)的碼字是(1100011100)。接收端的CRC校驗實際上就是做除法。如果收碼無誤，R(x)除以g(x)應(yīng)得余式0；反之，如果余式不等于零就說明一定有差錯。6.4卷積碼卷積碼的產(chǎn)生分組碼以孤立碼塊為單位編譯碼信息流割裂為孤立塊后喪失了分組間的相關(guān)信息分組碼長n越大越好，但譯碼運算量隨n指數(shù)上升本節(jié)內(nèi)容卷積碼的基本概念和描述方法卷積碼的最大似然譯碼維特比算法卷積碼的性能限與距離特點98996.4.1卷積碼的基本概念和描述方法將信息序列分隔成長度k的一個個分組某一時刻的編碼輸出不僅取決于本時刻的分組，而且取決于本時刻以前的L個分組。稱L＋1為約束長度最重要的三個參數(shù)(n,k,L)100(n,k,L)卷積編碼示意

第i分組第i-1分組第i-2分組……第i-L分組

m0im1i…mk-1im0i-1…mk-1i-1m0i-2…mk-1i-2………m0i-Lm1i-L…mk-1i-L輸入

…… …………

卷積編碼器（線性組合器）

c0ic1i…cn-2icn-1i

編碼輸出Ci101mk-1i-2mk-1i-2mk-1i-2…mk-1i-Lm0im0i-1m0i-2…m0i-Lm1im1i-1m1i-2…m1i-L102串并變換線性組合器…………串并變換C0iC1iCn-2iCn-1i編碼輸出

例6-11二進制(3,2,1)卷積編碼器103

c0i信號入

m

c1iCi

編碼輸出

c2im0im0i-1m1im1i-1本時刻m0=(m00,m10)=(01),上一時刻m1=(m01,m11)=(10)gknl表示記憶陣列第k行(k=0,1)第l列(l=0,1)對第n個(n=0,1,2)碼元的影響,共N×K×(L+1)=

3×2×2個系數(shù)：

g000=1,g001=1,g010=0,g011=1,g020=1,g021=1,g100=0,g101=1,g110=1,g111=0,g120=1,g121=0。用矩陣表示104本時刻編碼輸出：

C0=(c00,c10,c20)=m0G0+m1G1=(01)+(10)=(011)+(111)=(100)105卷積碼名稱的由來設(shè)編碼器的初始狀態(tài)為零（記憶陣列全體清0），隨著時刻i的遞推和k比特信息組(m0,m1,…,mL,mL+1,…)源源不斷地輸入，碼字(C0,C1,…,CL,CL+1,…)源源不斷地輸出。在時刻i=0時，C0

=m0G0 i=1時，C1=m1G0+m0G1

i=L

時，CL=mLG0+mL-1G1…m0GLi=L+1時，CL+1=mL+1G0+mLG1…m1GL

于是任何時刻i的輸出碼字：Ci=mi-lGl

106多項式表示G(D)=G0+G1D+…+GLDL=gkn(D)=gkn0+gkn1D+gkn2D2+…+gknLDL=gknlDl例6-11中

107例6－12

二元(3,1,2)卷積碼的轉(zhuǎn)移函數(shù)矩陣G(D)=(1,1+D,1+D+D2)，根據(jù)轉(zhuǎn)移函數(shù)矩陣，

g00(D)=g000+g001D+g002D2=1

g01(D)=g010+g011D+g012D2=1＋D

g02(D)=g020+g021D+g022D2=1+D+D2得 g000=1,g001=0,g002=0, g010=1,g011=1,g012=0, g020=1,g021=1,g022=1。

108

c0i

信號入

m

c1i

輸出Ci

c2im0im0i-1m0i-2例6-13同例6-12的（3，1，2）卷積碼，轉(zhuǎn)移函數(shù)矩陣G(D)=(1,1+D,1+D+D2)試用狀態(tài)流圖來描述該碼。假如輸入信息序列是10110，而輸出碼字是什么？狀態(tài)m0i-1m0i-2S000S101S210S311m0i=0m0i=1S0000111S1001110S2011100S3010101109m0i=0m0i=1S0S0S2S1S0S2S2S1S3S3S1S3編碼器狀態(tài)的定義不同狀態(tài)與輸入時編出的碼字不同狀態(tài)Si與輸入時的下一狀態(tài)Si+1圖6-20(3,1,2)卷積碼狀態(tài)流圖假如輸入信息序列 是10110…，

S0

1/111S2

0/011S11/110S2

1/100S30/010S1……

1100/000S01/1110/0011/110S2S10/0111/1000/010S3