第6章信道編碼

第6章信道編碼信道編碼是以信息在信道上的正確傳輸為目標的編碼，可分為兩個層次上的問題：如何正確接收載有信息的信號－－線路編碼如何避免少量差錯信號對信息內(nèi)容的影響－－糾錯編碼

描述編碼：用于對特定數(shù)據(jù)信號的描述:

不歸零碼（NotReturntoZero，NRZ）約束編碼：用于對特定信號特性的約束:HDB3碼擴頻編碼：用于擴展信號頻譜為近似白噪聲譜并滿足某些

相關(guān)特性:m序列糾錯編碼：用于檢測與糾正信號傳輸過程中因噪聲干擾導

致的差錯：循環(huán)碼信道編碼的作用和分類消息m信道編碼

編碼信道

信道譯碼

碼字C接收向量R消息^m編碼信道模型編碼信道n-1

當碼字C和接受向量R均由二元序列表示，稱編碼信道為二元信道。如果對于任意的n都有：P(r/c)=∏p(ri/ci)則稱此二進制信道為無記憶二元信道如果轉(zhuǎn)移概率：p(0/1)=p(1/0)=pb則稱此信道為無記憶二元對稱信道BSC幾個概念BSC轉(zhuǎn)移概率BSC編碼信道BSC輸入輸出關(guān)系等效為差錯圖案：隨機序列或

第i位上的一個隨機錯誤：差錯圖案e例如:C=[10000],e=[01000],R=?R=(11000)碼元的組成及關(guān)系消息序列m總以k個碼元為一組傳輸，稱k個碼元的碼組為信息碼組。信道編碼器按一定規(guī)則對每個信息碼組附加一些多余的碼元，構(gòu)成長為n個碼元的碼組c（信道編碼）。附加的r=n-k個碼元稱為監(jiān)督碼元。檢糾錯是根據(jù)信道輸出序列r,判斷r是否可能是發(fā)送的c，或糾正導致r不等于c的錯誤。冗余編碼：碼字c的長度n一定大于消息m的長度k

糾錯編碼編碼碼率R：每個碼字的序列符號（或碼元）平均傳送的消息比特數(shù)檢錯和糾錯目的性質(zhì)偶（或奇）校驗方法：實現(xiàn)檢糾錯目的的一個基本方法。

一個偶校驗位P是對消息m使得如下校驗方程成立的二進制符號，即一個偶校驗碼碼字

校驗方程為1表明一定有奇數(shù)個差錯，校驗方程為0表明可能有偶數(shù)個差錯。

檢錯和糾錯方法重復消息位：實現(xiàn)檢糾錯目的第二個基本方法

一個n重復碼是一個碼率R為1/n的碼，僅有兩個碼字C0和C1，傳送1比特（k=1）消息。n重復碼可以檢測出任意小于n個差錯的錯誤圖案，糾正任意小于n/2個差錯的錯誤圖案。等重碼或定比碼：實現(xiàn)檢糾錯的第三個方法。

設計碼字重量(碼字中非0元素個數(shù))w(c)恒為常數(shù)，即

5中取3等重碼

1234567890010111100110110110100011110101111000111010011011015中取3等重碼可以檢測出全部奇數(shù)位差錯，對某些碼字的傳輸則可以檢測出部分偶數(shù)位差錯。糾錯碼的應用方式：前向糾錯方式（FEC），自動請求重發(fā)（ARQ）方式，混合糾錯（HEC）方式以及信息反饋（IRQ方式）FEC與ARQ糾錯應用方式

檢錯和糾錯方式

常用漢明距離來描述檢糾差錯的數(shù)目，對于兩n長向量u，v漢明距離為：

最小漢明距離dmin（最小碼距d）：任意兩碼字之間的漢明距離的最小值。檢錯和糾錯能力定理:

對一個最小距離為dmin糾錯碼，如下三個結(jié)論僅有其中任意一個結(jié)論成立，

（1）

可以檢測出任意小于等于個差錯；

（2）

可以糾正任意小于等于個差錯；（3）可以檢測出任意小于等于l同時糾正小于等于t個差錯，其中l(wèi)和t滿足最小碼距與檢糾錯能力

糾錯碼的分類根據(jù)信息元和監(jiān)督元之間的關(guān)系分為：線性碼：信息元與監(jiān)督元之間呈線性，可用一組線性方程聯(lián)系起來；非線性碼：信息元與監(jiān)督元之間不具有線性關(guān)系?！?.2線性分組碼

§6.2.1線性分組碼的矩陣描述根據(jù)對信息碼元處理方法的不同分為：

分組碼：信息序列以每k個碼元進行分組，每組k個信息元按一定規(guī)律產(chǎn)生r個監(jiān)督碼元，輸出序列長為n=k+r，r只與k個信息位有關(guān)，記（n，k）。分組碼分為循環(huán)碼和非循環(huán)碼。卷積碼：以k個碼元分段，r不僅與k個信息位有關(guān)，還與前面L段的信息元有關(guān)，記為（n，k，L）。線性分組碼：通過預定的線性運算將長為k的信息碼組變成長為n的碼字（n>k），由2n個碼字組成的集合稱為線性分組碼。（n，k）線性碼：信息位長k，碼字長n，監(jiān)督位r=n-k，編碼效率線性分組碼線性分組碼的矩陣描述一個（n,k）線性分組碼C是稱為碼字c的n維向量的集合

C={c|c=mG}其中m為任意的k維向量并稱為消息向量。線性分組碼的生成矩陣例:(6,3)二進制分組碼的輸入信息組是m=(m2m1m0),碼組輸出是c=(c5c4c3c2c1c0)。已知輸入、輸出碼元之間的關(guān)系式c5=m2,c4=m1,c3=m0,c2=m2+m1,c1=m2+m1+m0,c0=m2+m0，求碼集C以及編碼時的映射算法。解：將關(guān)系式列成線性方程組，然后寫成矩陣形式如下：生成矩陣信息組

(m2m1m0)

碼字（c5c4c3c2c1c0

)000000000000001011010010110011011101100100111101101100110110001111111010例6.2.13重復碼是一個（3，1）線性分組碼例6.2.2（4，3）偶校驗碼是一個（4，3）線性分組碼n-k個校驗位可用k個已知的信息位表示出來一致校驗矩陣一致校驗矩陣H與任意一個碼字之積為零，因此有由G的每一行都是一個碼字，因此有一直校驗矩陣與生成矩陣的關(guān)系G是k行n列的秩為k（n≥k）的生成矩陣系統(tǒng)碼：生成矩陣G具有如下形式對于系統(tǒng)碼相應的一致校驗矩陣Hs對偶碼：以線性分組碼的一致校驗矩陣為生成矩陣稱為原線性分組碼的對偶碼。例6.2.3一個（5，3）線性分組碼的其中到的行初等變換過程為：？

例：考慮一個（7，4）碼，其生成矩陣是：①對于信息組m=(1011),編出的碼字是什么？②若接收到一個7位碼r=(1001101),檢驗它是否為碼字？解：設輸入信息組編碼后的碼字①由c=mG可知，將m和G的值代入，可得對應碼字本題由于是系統(tǒng)碼，

前4位不必計算，后3個校驗位可以根據(jù)生成矩陣G的分塊陣P列出現(xiàn)行方程組如下將代入方程組，得所以碼字為c=[1011000]。②H矩陣如下：根據(jù)式，如果接受到的r是屬于碼集C的某碼字，必有；反之，如，說明r必定不是碼字。將H和r=[1001101]代入式，得：說明r與H不正交，接收的r=(1001101)不是碼字。檢錯譯碼：譯碼器輸出為當前接收向量r和r是否有差錯的標志s，即y=(r,s)?！?.2.2線性分組碼的譯碼糾錯譯碼的譯碼成功狀態(tài)：譯碼器能夠在達到譯碼碼字差錯概率最小條件下輸出一個確切的碼字，即。糾錯譯碼的譯碼失敗狀態(tài)：譯碼器不能輸出一個確切的碼字，通常此時的輸出y與檢錯譯碼輸出相同。

伴隨式S：(n,k）線性分組碼的伴隨式是一個r(r=n-k)維向量，則傳輸中一定有錯誤發(fā)生。，則傳輸中要么無差錯發(fā)生，要么差錯圖案恰好為一個碼字。

（1）漢明碼漢明碼不是指一個碼，而是代表一類碼；漢明碼碼長n和信息位k服從以下規(guī)律：(n,k)=(2m-1,2m-m-1)；漢明碼的最小距離d=3；所以，糾錯能力t=1；§6.2.3碼例與碼的重構(gòu)例6.2.4一個二元（7，4）Hamming碼的系統(tǒng)碼形式的矩陣和校驗矩陣分別為

等價的編碼方程為

伴隨式計算方程：（2）Hadamard碼Hadamard碼是由Hadamard矩陣派生出的一種糾錯碼

階實Hadamard矩陣由元素為+1，-1的矩陣遞歸定義：Hadamard矩陣為正交矩陣，即中的任意不同兩行（列）的點積為0，即

超正交矩陣：Hadamard矩陣中的第1列（全+1列）去掉后任兩行的點積為-1。

將Hadamard矩陣元素+1/-1映射為0/1，則Hadamard矩陣映射后的行向量為一個二元向量，以這些二元向量的部份或全體就構(gòu)成標準0/1二元意義上的分組碼，并稱為Hadamard碼。具體的Hadamard碼的選擇構(gòu)成有正交碼、雙正交碼和超正交碼三種形式。

（A）正交碼：以的全部行向量的0/1映射向量為碼字。（B）雙正交碼：以和-的全部行向量的0/1映射向量為碼字。

（C）超正交碼：以的全部行向量的0/1映射向量為碼字。

例6.2.5（7，3）超正交碼的超正交矩陣H8和生成矩陣G分別為

(3)里德-穆勒（Reed-Muller）碼r階碼RM(r,m)是一種(n,k,d)線性分組碼，滿足其中各個子矩陣的定義為：1）G0為矩陣，由全1向量構(gòu)成。2）G1為矩陣，由所有可能的m元組組成矩陣的列向量。3）G2為G1的所有兩個不同行向量的叉積構(gòu)成其全部行向量的矩陣。兩向量的叉積為4）G3為G1的所有三不同行向量的叉積構(gòu)成其全部行向量的矩陣。5）Gr為G1的所有r個不同行向量的叉積構(gòu)成其全部行向量的矩陣。例6.2.6m=3的r階RM碼的各個子矩陣有（4）戈雷碼

二元戈雷碼是一種就糾3個錯的完備線形分組碼，滿足：{n=23k=12由于

因此某種二元（23,12）碼一定可以糾正任意小于等于3個差錯，所以

(1)擴展(2)打孔(3)增廣(4)刪信(5)延長(6)縮短(7)乘積(8)級聯(lián)(9)交織6.3循環(huán)碼循環(huán)碼是一種特殊的線性分組碼，屬于線性分組碼的一個重要子類，也是目前研究最為透徹的一類碼，大多數(shù)有實用價值的糾錯碼都是循環(huán)碼。循環(huán)碼與一般的線性分組碼相比具有以下優(yōu)點：循環(huán)碼的編碼及譯碼易于用簡單的具有反饋連接的移位寄存器來實現(xiàn)。

定義：一個線性分組碼，若具有下列特性，稱為循環(huán)碼。設碼字c＝（cn-1，cn-2，…，c1，c0）若將碼元左移一位，得c(1)＝（cn-2，…，c1，c0，cn-1）c(1)是同一個碼序列C的一個碼字。循環(huán)碼的主要特點是：①理論成熟：可利用成熟的代數(shù)結(jié)構(gòu)深入探討其性質(zhì)；②實現(xiàn)簡單：可利用循環(huán)移位特性在工程上進行編、譯碼；③循環(huán)碼的描述方式有很多，但在工程上最常用的是采用多項式的描述方法。信息碼元碼字00000000000010011101010010011101101110101001001110101101001111011010011111110100表1循環(huán)碼的例子循環(huán)碼的多項式描述

設有循環(huán)碼字c=(cn-1cn-2…c1c0)

，則可以用一個次數(shù)不超過n-1的多項式惟一確定，其相應的多項式可表示為：

(1)

由循環(huán)碼的特性可知，若c=(cn-1cn-2…c1c0)是循環(huán)碼C的一個碼字，則c(1)

=(cn-2cn-3…c0cn-1)

也是該循環(huán)碼的一個碼字，它的碼多項式為：

(2)

比較式(1)和式(2)，得：

碼多項式的系數(shù)碼多項式的次數(shù)(cn-1≠0)該式說明，碼字循環(huán)一次的碼多項式C(1)(x)是原碼多項式乘x后再除以xn+1所得的余式，即：

由此可以推知，C(x)的i次循環(huán)移位C(i)(x)是原碼多項式C(x)乘xi

后再除以xn+1所得的余式，即：

表2(7,3)循環(huán)碼的循環(huán)移位循環(huán)次數(shù)碼字碼多項式00011101x4+x3+x2+110111010x(x4+x3+x2+1)mod(x7+1)=x5+x4+x3+x21110100x2(x4+x3+x2+1)mod(x7+1)=x6+x5+x4+x231101001x3(x4+x3+x2+1)mod(x7+1)=x6+x5+x3+141010011x4(x4+x3+x2+1)mod(x7+1)=x6+x4+x+150100111x5(x4+x3+x2+1)mod(x7+1)=x5+x2+x+161001110x6(x4+x3+x2+1)mod(x7+1)=x6+x3+x2+x循環(huán)碼的生成多項式定義：若g(x)是一個(n-k)次多項式，且是(xn+1)的因式，則由g(x)可以生成一個（n，k）循環(huán)碼，g(x)稱為該循環(huán)碼的生成多項式。兩個結(jié)論（1）（n，k）循環(huán)碼中，存在著一個次數(shù)為(n-k)的首一碼多項式g(x)（首一：多項式最高冪次項系數(shù)gn-k=1

）（gn-k=1）

使得所有碼多項式v(x)都是g(x)的倍式，即：

故循環(huán)碼完全由它的生成多項式確定。(2)(n，k)循環(huán)碼的生成多項式g(x)一定是(xn+1)的因子，即

相反，如果g(x)是xn+1的n-k次因子，則g(x)一定是（n，k）循環(huán)碼的生成多項式。生成多項式不唯一。（n，k）循環(huán)碼的構(gòu)造（1）對(xn+1)做因式分解，找出(n–k)次因式；（2）以該(n–k)次因式為生成多項式g(x)與不高于k–1次信息多項式u(x)相乘，即得到對應消息序列的碼多項式v(x)?！纠恳粋€長度n=7的循環(huán)碼的構(gòu)造方法（1）對x7+1作因式分解

故x7+1有如下因式：

一次因式：

三次因式：

四次因式：

（一個）

（兩個）

（兩個）

六次因式：

（一個）

n–k=1，k=6，生成一種（7，6）循環(huán)碼；n–k=3，k=4，生成兩種（7，4）循環(huán)碼；n–k=4，k=3，生成兩種（7，3）循環(huán)碼；n–k=6，k=1，生成一種（7，1）循環(huán)碼；（2）若以n-k次因式作為生成多項式，可供選擇的有:例：要得到（7，4）循環(huán)碼，可選n–k=3次多項式1+x2+x3或1+x+x3為生成多項式：

以g（x）=1+x2+x3為例，（信息位長度為4）

設信息多項式為：

則：循環(huán)碼編碼后的碼多項式為：

例：

對于上述（7，4）循環(huán)碼，有4個信息位，對應有16個信息序列，利用16個信息序列多項式與生成多項式的乘法運算，可得全部（7，4）循環(huán)碼得16個碼字，如下表所示：信息位碼字信息位碼字信息位碼字信息位碼字00010010010010000111111010110001011001011001011001011000011000111000101000101001101101100111110010101101000111010111010111010011010011010011010011110011100000000000011011111111循環(huán)組1循環(huán)組2循環(huán)組3循環(huán)組4任何碼字的循環(huán)移位仍是碼字，并非由一個碼字循環(huán)移位可以得到所有碼字，上述（7，4）碼的碼集由4組碼字循環(huán)構(gòu)成。結(jié)論：當一個循環(huán)碼給定其生成多項式g（x）后，根據(jù)生成多項式就可以進行編碼。（n，k）循環(huán)碼是n維線性空間一個具有循環(huán)特性的k維的子空間，故（n，k）循環(huán)碼的生成矩陣可用碼空間中任一組k個線性無關(guān)的碼字構(gòu)成，即k個線性無關(guān)的碼字構(gòu)成（n，k）循環(huán)碼的基底，基底不唯一。如何得到k個線性無關(guān)的碼字？

方法：當循環(huán)碼的生成多項式g（x）給定后，可以取g（x）本身加上移位k–1次所得到的k–1碼字作為k個基底，即：

→構(gòu)成基底

循環(huán)碼的生成矩陣

若：

則：

各多項式對應的矢量分別為：

這k個矢量是線性無關(guān)的，且由g（x）循環(huán)移位得到，故都是碼字，由它們構(gòu)成一個k×n的矩陣，它們就是循環(huán)碼的生成矩陣。按照g(x)系數(shù)的升冪排列【例】（7，4）循環(huán)碼：

當一個循環(huán)碼的生成矩陣確定后，其編碼規(guī)則為：

按照g(x)依次循環(huán)右移得到xg(x)等等循環(huán)碼的校驗多項式一般情況下，多項式xn+1可因式分解為xn+1=g(x)·h(x)

g(x):(n，k)循環(huán)碼的生成多項式，

h(x):(n，k)循環(huán)碼的一致校驗多項式，在因式分解中，g(x)和h(x)處于同等地位，既可以用g(x)去生成一個循環(huán)碼，也可以用h(x)去生成一個循環(huán)碼。設由g(x)生成的碼為C，在由h(x)生成的碼就是C的對偶碼C⊥。

循環(huán)碼的校驗矩陣設

則：將上述矢量按逆序排列作為一個（n-k）×n矩陣的行矢量，則該矩陣就是碼C的校驗矩陣。按照h(x)系數(shù)的降冪排列注意若：G按照g(x)系數(shù)的升冪排列，則H要按照h(x)系數(shù)的降冪排列；若：G按照g(x)系數(shù)的降冪排列，則H要按照h(x)系數(shù)的升冪排列；系統(tǒng)循環(huán)碼

1、系統(tǒng)循環(huán)碼的編碼步驟：(1)將k個消息位按升冪排列的次序?qū)懗上⒍囗検絬（x）

；

(2)用xn–k

乘以u（x）得到一個次數(shù)≤(n-1)的多項式；

(3)用xn–k

u（x）除以生成多項式g（x）得余式p(x)（一致校驗元）；

(4)聯(lián)合p(x)和xn–k

u(x)得到系統(tǒng)循環(huán)碼多項式v(x)=p(x)+xn–k

u(x)；

(5)將碼多項式轉(zhuǎn)換為碼字?！纠浚?，4）循環(huán)碼：

求

的系統(tǒng)循環(huán)碼字。

【解】

，n＝7，k＝4

（1）

（2）P(x)（3）（4）2、系統(tǒng)循環(huán)碼的生成矩陣（1）由生成矩陣做初等行變換，將其變?yōu)樾问?，即為系統(tǒng)循環(huán)碼的生成矩陣（單位陣在后，信息位在尾部）。

求系統(tǒng)形式的生成矩陣?！纠浚?，4）循環(huán)碼：

(2)分別求除以g(x)的余式（記為），由余式對應的矢量作行矢量構(gòu)成的k×(n-k)的分塊矩陣P，聯(lián)合k×k的單位陣I就構(gòu)成系統(tǒng)形式的生成矩陣：求系統(tǒng)形式的生成矩陣?！纠浚?，4）循環(huán)碼：

3、系統(tǒng)循環(huán)碼的校驗矩陣

（1）對非系統(tǒng)形式的校驗矩陣作初等行變換，

變成[In-k，PT]的形式；（2）

(3)分別求除以h(x)的余式記為，由余式對應的逆矢量可得到系統(tǒng)形式的校驗矩陣：【例】（7，4）循環(huán)碼：

（1）（2）（3）k=4，n–k–1=2

循環(huán)碼的伴隨多項式若接收向量r的多項式表示為r(x)r(x)=c(x)+e(x)則s(x)=r(x)modg(x)=e(x)modg(x)若s(x)=0則無差錯，若s(x)不等于0，則一定有差錯產(chǎn)生。6.4卷積碼將信息序列分隔成長度為k的一個個分組某一時刻的編碼輸出不僅取決于本時刻的分組，而且取決于本時刻以前的m個分組。稱m為記憶長度稱m＋1為約束長度最重要的三個參數(shù)(n,k,m)卷積碼定義(n,k,m)卷積編碼示意圖

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

輸入

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

c0ic1i…cn-2icn-1i

…………………………編碼輸出C

i卷積編碼器的一般結(jié)構(gòu)m0i-L……m0i-2m0i-1m0im1i-L……m1i-2m1i-1m1i串并變換線性組合器并串變換mk-1i-L……mk-1i-2mk-1i-1mk-1ic0ic1icn-2icn-1i…...........信號mi編碼輸出ci一個簡單的卷積碼編碼例子初始狀態(tài)：00設輸入m