第6章634幾種重要的碼

第6章信道編碼6.1信道編碼的概念6.2線性分組碼6.3循環(huán)碼6.4卷積碼16.3循環(huán)碼線性分組碼對碼的選取做了線性約束，使得計算量變小。譯碼算法是一種通用譯碼算法，效率不高。循環(huán)碼是1957年由一個叫Prange的科學家開始研究。循環(huán)碼在線性約束的基礎(chǔ)上增加了約束條件，是目前研究最為成熟的一類碼，大多數(shù)有實用價值的糾錯碼都屬于循環(huán)碼的范疇。2定義定義：對于一個（n，k）線性分組碼，若某一碼字為C=[c1,c2,...

,cn]該碼字向左循環(huán)1位后為C(1)=[c2,c3,...

,cn,c1]該碼字向左循環(huán)i位后為C(i)=[ci+1,ci+2,...

,cn,c1,...

,ci]直至向左循環(huán)n－1位為

C(n-1)=[cn,cn-1,...

,c1]若C(i),i=1,2,...,n－1均為碼字，則稱這個（n，k）線性分組碼為循環(huán)碼。循環(huán)碼一般也記為（n，k）碼，其中n為碼字的長度，k為信息位的長度。3循環(huán)碼的碼多項式循環(huán)碼的特點是，若C是一個碼字，那么它的循環(huán)移位所形成的新序列同樣也是一個碼字。循環(huán)碼是線性分組碼的一個重要子類，它具有完整的代數(shù)結(jié)構(gòu)，其編碼和譯碼相對比較簡單，易于實現(xiàn)。

循環(huán)碼也是線性分組碼，因此可用校驗矩陣或生成矩陣來構(gòu)成。但由于循環(huán)碼具有循環(huán)移位特性，且是自封閉的，故采用多項式的方法描述更為方便。

n長的循環(huán)碼字C=[c1,c2,...

,cn]可以用一個xn-1次多項式來表示，稱為碼多項式，表示為

C(x)=c1xn-1

+c2xn-2+...+

cn-1x+cn

4碼多項式的運算一元多項式多項式的次數(shù)定義為：零次多項式：零多項式：多項式加法：多項式乘法：5碼多項式的運算碼多項式的模運算和整數(shù)的模運算類似：長除法。例如：6碼多項式的運算因式和倍式：余式：7碼多項式的運算循環(huán)碼的循環(huán)特性可由多項式的模運算來表示

當碼字向左移1位，相當于乘以x后的模(xn+1)

運算，即C(1)(x)=xC(x)mod(xn+1)

C(1)(x)=c1xn+c2xn-1+...+cn-1x2+cnxmod(xn+1)C(1)(x)=c2xn-1+c3xn-2+...+cnx+c1如果碼字向左移i位，相當于乘以xi后的模(xn+1)運算，即C(i)(x)=xiC(x)mod(xn+1)

C(i)(x)=c1xn+i-1+c2xn+i-2+...+cn-1xi+1+cnximod(xn+1)C(i)(x)=ci+1xn-1+ci+2xn-2+...+ci-1x+ci8例子：例如：其中：CA是線性循環(huán)碼，CB是非循環(huán)線性分組碼，而CC是非線性循環(huán)碼。CA的碼字可用多項式：0,x2+x,x+1,x2+1表示。n=3循環(huán)碼仍是線性碼，由循環(huán)碼構(gòu)成的線性子空間為循環(huán)子空間。將碼表示成C或C(x)。9生成多項式g(x)的兩個定理定理一

(n,k)循環(huán)碼C(x)中存在唯一的一個非零的、首一的和最低次數(shù)為r(r<n)的碼多項式g(x)滿足并且，c(x)是碼式當且僅當c(x)是g(x)的倍式。10定理一證明唯一性：g0證明:若g0=0，則

即g(x)是另一個更底的碼式g’(x)的循環(huán)移位，矛盾。碼式是g(x)的倍式：

由循環(huán)移位特性知：xi

g(x)，i=1,2…n-1-r均是碼式。11定理一證明（續(xù)）由碼的線性分組特性：an-1-rg(x)xn-1-r+…+a1g(x)x+a0g(x)=a(x)g(x)(1)

也是碼式。故g(x)的倍式若次數(shù)小于n則是碼式。反之：f(x)若是碼式，則可表示為：

f(x)=a(x)g(x)+r(x)，r(x)的次數(shù)小于g(x)的次數(shù)，或r(x)=0。若r(x)0，則r(x)＝f(x)－a(x)g(x)也是碼式，但r(x)的次數(shù)<r，矛盾。所以r(x)＝０=>f(x)是g(x)的倍式。r=n-k證明：由碼式必是g(x)的倍式及(1)式知a0，

a1…

an-1-r有n-r個，故可組成2n-r個碼式，而(n，k)碼的碼字個數(shù)為2k個且碼式必是g(x)的倍式=>n-r=k。證畢12生成多項式定義：由定理一確定的碼式g(x)稱為（n，k）循環(huán)碼的生成多項式。循環(huán)碼由生成多項式g(x)的倍式組成，表示為：定理二

g(x)是(n,k)循環(huán)碼的生成多項式，當且僅當g(x)是xn-1的r=n–k次因式。證明：必要性

若g(x)是生成多項式，則有：由循環(huán)移位定義得，r(x)是g(x)的循環(huán)移位碼式，所以

故g(x)是xn-1

的因式。13定理二證明（續(xù)）充分性：

設(shè)n-k=r次g(x)是xn-1的因式，則線性組合：共有２k個多項式。其中：故c(x)的一次循環(huán)c(1)(x)均是g(x)的倍式。同理c(x)的任意次循環(huán)c(i)(x)均是g(x)的倍式。所以，此２k個多項式組成（n,k）循環(huán)碼。證畢14例題—構(gòu)造循環(huán)碼例題：構(gòu)造一個（7，3）循環(huán)碼。解：由于n＝7，對(x7+1)因式分解得：x7+1=(x+1)(x3+x2+1)(x3+x+1)

由于k=3，則n–k=4，因此(7,3)

循環(huán)碼的兩個可選的生成多項式為：g1(x)=(x+1)(x3+x2+1)g2(x)=(x+1)(x3+x+1)15循環(huán)碼的生成矩陣

由于（n，k）循環(huán)碼共有2k

個碼字，從碼組中取出一個前面k－1位都是0的碼字，用g(x)

表示，不難看出g(x)的多項式次數(shù)為（n－k）。因為xig(x),i=0,1,2,...,k-1均是碼字且相互獨立，故可用xig(x),i=0,1,2,...,k-1作為生成矩陣G的k行。綜上所述，由多項式g(x)可以構(gòu)成生成多項式矩陣為

16生成矩陣G(n,k)循環(huán)碼的生成矩陣在g(x)確定后可以表示為G17生成多項式g(x)與循環(huán)碼的生成由于循環(huán)碼是線性分組碼，因此對于碼字C有

C(x)=[m1m2...mk]G(x)式中[m1m2...mk]為k位信息元矢量。

上式表明，循環(huán)碼的所有碼字可由g(x)產(chǎn)生，g(x)稱為循環(huán)碼的生成多項式。在(n，k)循環(huán)碼中，g(x)是唯一的一個(n－k)次多項式，且次數(shù)最低。每個碼多項式C(x)都是g(x)的倍式，而每個為g(x)的倍式且次數(shù)小于或等于(n－1)的多項式必是一個碼多項式。

18校驗多項式h(x)循環(huán)碼的生成多項式g(x)是xn＋1的因式，即

xn＋1=

h(x)g(x)

k次多項式h(x)稱為碼的校驗多項式。設(shè)則g(x)和h(x)的系數(shù)滿足以下關(guān)系

19校驗方程的獲得校驗方程可由如下方法得到：20循環(huán)碼的校驗矩陣H和生成矩陣G校驗矩陣可以表示為右邊矩陣H，滿足xn+1=h(x)g(x)。注意到生成矩陣G的行向量為g(x)系數(shù)的升冪排列，校驗矩陣H的行向量為h(x)系數(shù)的降冪排列。如果G為降冪排列，則對應(yīng)的H為升冪排列。21循環(huán)碼的伴隨多項式假設(shè)發(fā)送的碼多項式C(x)和錯誤圖樣多項式e(x)以及接收端接收的碼多項式R(x)分別為則對于加性信道有

R(x)=C(x)+e(x)

設(shè)g(x)為碼的生成多項式，由于碼字多項式C(x)能夠被g(x)除盡，故有R(x)modg(x)=e(x)modg(x)即：定義伴隨多項式為S(x)=e(x)modg(x)22循環(huán)碼的檢糾錯根據(jù)伴隨式的定義，若無錯誤傳輸，則S(x)=0，否則S(x)≠0，由此可實現(xiàn)循環(huán)碼的檢錯。

因為g(x)的次數(shù)為n－k，e(x)的次數(shù)為n－1，所以伴隨式的最高次數(shù)為n－k－1，那么S(x)共有n－k項，故有2n-k種可能的伴隨式。若滿足2n-k≥n+1，則循環(huán)碼具有糾錯能力。

BCH碼是一類重要的循環(huán)碼，它能夠最有效地糾正多個獨立錯誤。BCH碼把生成多項式與碼的最小距離和糾錯能力聯(lián)系起來，根據(jù)所需要的糾錯能力，選取適當?shù)膅(x)，可以編出非常有效地糾正多個獨立錯誤的BCH碼。（略）

23例題—校驗多項式和生成矩陣例題：對上例的（7,3）循環(huán)碼，求其校驗多項式和生成矩陣。解：校驗多項式為h(x)=(x7+1)/g(x)=(x3+x+1)

生成多項式矩陣為G(x)、生成矩陣為G

24例題—循環(huán)碼的生成例題：對上例的（7,3）循環(huán)碼，若輸入信息碼字為110，求其循環(huán)碼字。解：信息碼字110的碼式為m(x)=x2+x

得循環(huán)碼式為c(x)=m(x)g(x)=(x2+x)(x4+x2+x+1)=x6+x5+x4+x則其循環(huán)碼字為1110010。25例題—循環(huán)碼的檢錯例題：對上例的（7,3）循環(huán)碼，若接收碼字為1100100，判斷是否是許用碼字。解：接收碼字1100100的碼式為R(x)=x6+x5+x2

由伴隨式S(x)=e(x)modg(x)=R(x)modg(x)S(x)=x6+x5+x2

mod(x4+x2+x+1)=1因為S(x)≠0

，因此該碼字不是（7，3）循環(huán)碼的許用碼字。26小結(jié)循環(huán)碼為線性分組碼；卷積碼為線性非分組碼。循環(huán)碼的特點是具有循環(huán)移位特性，因此可以用多項式法描述。本節(jié)介紹了循環(huán)碼利用多項式的編譯碼方法，包括生成多項式的構(gòu)造，利用生成多項式生成碼字，校驗多項式及其與生成多項式的關(guān)系、利用伴隨多項式譯碼等。討論了多項式描述與一般線性分組碼的矩陣描述（生成矩陣、校驗矩陣、伴隨式）間的關(guān)系。27第6章信道編碼6.1信道編碼的概念6.2線性分組碼6.3循環(huán)碼6.4卷積碼286.4卷積碼在分組碼中，任何特定的時間單位內(nèi)編碼器所產(chǎn)生的n個碼元的碼組，僅取決于該時間單位內(nèi)k個消息位。存在著另一種碼，由編碼器在特定的時間內(nèi)所產(chǎn)生的碼元不但取決于這個特定的時間段內(nèi)進入的信息組，而且也與前面的時間段內(nèi)的信息組有關(guān)，這種碼稱為卷積碼。卷積碼的編碼可用移位寄存器來完成。卷積碼與分組碼相似，具有糾正隨機錯誤、突發(fā)錯誤或同時糾正這兩類錯誤的能力。對于許多實際的誤差控制，卷積碼的性能優(yōu)于分組碼。

29卷積碼的概念定義：對于任一給定時刻，編碼器的一個輸出碼字不僅與該時刻的當前輸入碼字有關(guān)，還與編碼器的移位寄存器中存貯的前面m個輸入信息碼字有關(guān)。因此卷積碼記為(n,k,m)卷積碼。其中n為輸出的每個碼字的位數(shù)k為輸入的每個信息碼字的位數(shù)m為移位寄存器中存貯的信息碼字個數(shù)。

定義m為卷積碼的記憶長度，而(m+1)為卷積碼的碼字約束長度，相應(yīng)的比特（碼元）約束長度為(m+1)n。對L段輸入的信息碼進行編碼，由于初始寄存器為全0，結(jié)束時也要額外輸入m段無效的全0碼字，故共產(chǎn)生L+m段輸出碼字，所以卷積碼的碼率為R=Lk/(L+m)n。當L很大時，R=>

k/n，我們一般用R=

k/n表示卷積碼的編碼效率。卷積碼是線性碼，但不是分組碼，因為卷積碼是有記憶的編碼。

30(3，2，1)

卷積碼舉例以下給出了一個(3，2，1)卷積碼編碼器的原理圖。

mi(1)

ci(1)

mi(2)

ci(2)

ci(3)

該編碼器由2個移位寄存器構(gòu)成。編碼器每并行輸入一個2位信息碼字mi=[

mi(1),

mi(2)]，則并行輸出一個3位卷積碼碼字ci=[

ci(1),

ci(2),

ci(3)]=[

mi(1),

mi(2),pi]

其中pi為監(jiān)督元，有

pi=

mi(1)+

mi(2)+mi-1(1)+

mi-1(2)可見，卷積碼當前輸出的碼字的監(jiān)督元不僅與當前輸入的信息元有關(guān)，還與前次輸入的2個信息碼元有關(guān)。

31卷積碼的校驗關(guān)系式下面以（3，1，3）卷積碼為例，討論卷積碼的生成矩陣和校驗矩陣。把給定的信息序列(m1,m2,m3,...)進行分組，使每個信息組只包含一個信息位。輸出的每組碼字由三位組成，其中有一個信息位和兩個校驗位，則輸出的碼序列為

(m1p11p12,m2p21p22,m3p31p32,...)設(shè)校驗位與信息位滿足以下校驗關(guān)系：pi1=mi+mi-1+mi-3;pi2=mi+mi-1+mi-2校驗關(guān)系式表明，當前的校驗位與當前的信息位和過去的三個信息位有關(guān)，且滿足一定的線性關(guān)系。某一信息碼字會影響4個卷積碼字，為此稱這個卷積碼為約束長度為4個碼字的卷積碼。

32編碼器框圖下圖為（3，1，3）卷積碼的編碼器原理框圖輸入信息序列為m=(m1,m2,m3,...)

輸出碼字序列為C=(c11c12c13,c21c22c23,c31c32c33,...)C=(m1p11p12,m2p21p22,m3p31p32,...)33生成矩陣G改寫校驗關(guān)系式pi1=mi+mi-1+mi-3

pi2=mi+mi-1+mi-2可以得到m和C滿足以下關(guān)系

34生成矩陣G（續(xù)）改寫的校驗關(guān)系式若寫成矩陣形式，則得到m和C間的矩陣關(guān)系為

式中的矩陣G稱為卷積碼的生成矩陣。

35卷積碼的描述方法：卷積碼的描述方法有兩類：1)解析法：包括離散卷積法、生成矩陣法、碼多項式法等，多用于編碼。2)圖形法：包括狀態(tài)圖、樹圖、柵格圖等，常用于譯碼，特別是網(wǎng)格圖。特點：用碼多項式法表示卷積碼編碼器的生成多項式最為方便；柵格圖對于分析卷積碼的譯碼算法十分有用；狀態(tài)圖表明卷積碼編碼器是一種有限狀態(tài)的馬爾科夫過程。36１離散卷積法設(shè)在l時段，輸入的信息碼組為：輸出的卷積碼組為：移位寄存器中存有前m個時段輸入的m個信息碼組。由于v(l)與當前時段及此前m個時段的輸入碼組呈線性關(guān)系。若以v(l-i,l)表示l-I時段的輸入u(l-i)對v(l)的貢獻，則有：v(l)=v(l,l)+v(l-1,l)+v(l-2,l)+…+v(l-m,l)各v(l-i,l)與u(l-i,l)為線性關(guān)系，類似線性分組中C=mG?？杀硎緸椋?7離散卷積法（續(xù)）

38２生成矩陣描述法卷積碼的矩陣描述：卷積碼是線性碼，故有生成矩陣和一致校驗矩陣。由以上的離散卷積式，展開得：39生成矩陣描述法（續(xù)）若將輸入的信息碼字序列表示為如下的半無限矩陣：

u={u(0),u(1),…,u(m),…,u(l)…}輸出卷積碼字也表示為如下的半無限矩陣：

v={v(0),v(1),…,,v(m),…,,v(l)…}則生成矩陣與信息碼的關(guān)系可表示為：其中：為卷積碼的生成矩陣。40生成矩陣描述法（續(xù)）為一個半無限矩陣，特點：每一個k行都是前一k行右移n列的結(jié)果。故中的第一個k行的前(m+1)列完全決定了，將其提出，稱為卷積碼的基本生成矩陣GB。式中，G0,G1…Gm都是k行n列矩陣，其中第i行表示各組信息碼字的第i位對輸出v(l)的貢獻。41生成矩陣描述法（續(xù)）將GB中第i行第j列表示為gi,t，則其中，t可表示為t=j+hm，j=1,2,…,n，h=0,1,2…,n則gi,t＝１表示輸入移位寄存器中的第h段的第i位輸入比特u(l-t,i)參與第j位輸出比特的編碼，gi,t＝０則不參與輸出編碼．由于記憶長度為m，即第i位輸入比特u(l-t,i)將對m+1位輸出產(chǎn)生作用．這種影響可用如下構(gòu)造的m+1元組g(i,j)來描述：｛gi,j｝稱為卷積碼的子生成元或生成序列．(n，k，m)卷積碼共有個生成元．42生成矩陣描述法（例子）例子：一個(2,1,2)非系統(tǒng)卷積碼如圖所示：uu(l-2)/v2(l)/v2v1(l)/v1u(l)/u(l-1)/++原理圖u(l)u(l-1)u(l-2)++v(l)電路圖43生成矩陣描述法（例子）44系統(tǒng)碼的生成矩陣形式以上（3，1，3）卷積碼是系統(tǒng)碼，其碼字的第一位總是信息碼字。其生成矩陣可以寫成下列形式

式中I

為k×k＝1×1階單位陣0為k×k＝1×1階全0方陣，Pi為k×（n－k）＝1×2階矩陣，有生成矩陣具有如上形式時生成的卷積碼為系統(tǒng)碼，一般的表示為。

45由生成矩陣產(chǎn)生碼序列已知生成矩陣，可以產(chǎn)生所有卷積碼字。對以上（3，1，3）碼，若輸入信息序列為（0100101011…），則對應(yīng)的碼字序列為

對于所生成的碼序列，每3個數(shù)字組成一個碼字，其中包括一個信息位和兩個校驗位。

46基本一致校驗矩陣（3，1，3）卷積碼的校驗關(guān)系式可以表示為

mi-3+mi-1+mi+pi1=0;mi-2+pi2+mi-1+mi=0令C0=(mi-3pi-3,1pi-3,2,mi-2pi-2,1pi-2,2,mi-1pi-1,1pi-1,2,mipi1pi2)

則校驗關(guān)系式可寫成矩陣形式：

其中

稱為（3，1，3）卷積碼的基本一致校驗矩陣?；疽恢滦ｒ灳仃嚳梢耘袛嗟趇－3，i－2，i－1，i個輸出碼字是否碼序列中的4個碼字，與線性碼的一致校驗矩陣一樣，起著校驗作用，但它只對4個碼字起校驗作用。

47一致校驗矩陣令C=(m1p11p12,m2p21p22,m3p31p32,...)由校驗關(guān)系式展開得如下關(guān)系式

48一致校驗矩陣（續(xù)）校驗關(guān)系式的展開式寫成矩陣形式為系數(shù)矩陣為H稱為（3，1，3）卷積碼的一致校驗矩陣。

49校驗矩陣的表示式以上校驗矩陣可以寫為如下表示式：式中PiT為（n－k）×k＝2×1維矩陣0為（n－k）×（n－k）＝2×2維全方陣I

為（n－k）×（n－k）＝2×2維單位矩陣。由卷積碼的生成矩陣G和校驗矩陣H的表示式可知，G和H有一定的關(guān)系，即GHT＝0。對于系統(tǒng)碼，由G可以得到H，反之，由H可以得到G。

50３卷積碼的多項式描述法記信息碼字序列u={u(0),u(1),…u(m),…,u(l),…}對應(yīng)的多項式為51卷積碼的多項式描述法（續(xù)）同理，輸出的卷積碼字序列為v={v(0),v(1),…v(m),…,v(l),…}對應(yīng)的多項式為52卷積碼的多項式描述法（續(xù)）線性(n,k,m)卷積碼得多項式表達式為：

[v(x)]T=[u(x)]TG(x)G(x)為k×n的多項式矩陣，稱為線性卷積碼得多項式生成矩陣．G(x)的第i行第j列元素為

g(i,j)(x)=gi,j+gi,n+jx+…+gi,mn+jxm是生成元g(i,j)的多項式表達，故G(x)可寫成

G(x)＝[g(i,j)(x)]k×n前例(2,1,2)非系統(tǒng)卷積碼中，G(x)＝[1+x+x21+x2]．53４卷積碼的狀態(tài)轉(zhuǎn)移圖描述法卷積碼和分組碼的主要區(qū)別在于卷積碼的編碼要存儲m段消息，這些消息隨新的輸入而改變，并影響當前輸出．因此可將這些存儲數(shù)據(jù)作為描述編碼器變化的內(nèi)部狀態(tài)．對二元(n,k,m)卷積碼，存儲器（移位寄存器）共有M=km個單元，即共有2M個不同的狀態(tài)，記為：l時刻的狀態(tài)用狀態(tài)矢量表示：下一時刻的狀態(tài)取決于當前狀態(tài)和當前輸入u(l)，其關(guān)系成為狀態(tài)轉(zhuǎn)移方程：54卷積碼的狀態(tài)轉(zhuǎn)移圖描述法(續(xù)）當前時刻的輸出v(l)取決于當前時刻的輸入u(l)和當前狀態(tài)，其關(guān)系稱為輸出方程：卷積碼有2M個可能狀態(tài)，在某一時刻同時輸入一段k位信息碼，有2k個可能取值，故每一時刻的狀態(tài)轉(zhuǎn)移只能有個可能．狀態(tài)圖有兩種:開放型和閉合型.如(2,1,2)非系統(tǒng)卷積碼：狀態(tài)向量，共有S0,S1,S2,S3四種狀態(tài)，其狀態(tài)變化如下：55卷積碼的狀態(tài)轉(zhuǎn)移圖描述法(續(xù)）(01)/(0)=(v1v2)/(u)(01)=S1(10)=S2(00)=S0(11)=S3(11)/(1)(01)/(1)(00)/(1)(10)/(0)(00)/(0)(11)/(0)(10)/(1)(2,1,2)碼狀態(tài)轉(zhuǎn)移圖（閉合型）56卷積碼的狀態(tài)轉(zhuǎn)移圖描述法(續(xù)）S0S3S2S1(00/0,11/1)(10/0,01/1)(11/0,00/1)(01/0,10/1)(2,1,2)碼狀態(tài)轉(zhuǎn)移圖（開放型）57柵格圖（網(wǎng)格圖、籬笆圖）閉合型的狀態(tài)轉(zhuǎn)移圖直接反映了編碼器在任一時刻的工作狀態(tài)；而開放型的狀態(tài)轉(zhuǎn)移圖則更適合描述特定輸入序列的編碼過程，但