第6章634幾種重要的碼

第6章信道編碼6.1信道編碼的概念6.2線性分組碼6.3循環(huán)碼6.4卷積碼16.3循環(huán)碼線性分組碼對(duì)碼的選取做了線性約束，使得計(jì)算量變小。譯碼算法是一種通用譯碼算法，效率不高。循環(huán)碼是1957年由一個(gè)叫Prange的科學(xué)家開始研究。循環(huán)碼在線性約束的基礎(chǔ)上增加了約束條件，是目前研究最為成熟的一類碼，大多數(shù)有實(shí)用價(jià)值的糾錯(cuò)碼都屬于循環(huán)碼的范疇。2定義定義：對(duì)于一個(gè)（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均為碼字，則稱這個(gè)（n，k）線性分組碼為循環(huán)碼。循環(huán)碼一般也記為（n，k）碼，其中n為碼字的長度，k為信息位的長度。3循環(huán)碼的碼多項(xiàng)式循環(huán)碼的特點(diǎn)是，若C是一個(gè)碼字，那么它的循環(huán)移位所形成的新序列同樣也是一個(gè)碼字。循環(huán)碼是線性分組碼的一個(gè)重要子類，它具有完整的代數(shù)結(jié)構(gòu)，其編碼和譯碼相對(duì)比較簡單，易于實(shí)現(xiàn)。

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

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

,cn]可以用一個(gè)xn-1次多項(xiàng)式來表示，稱為碼多項(xiàng)式，表示為

C(x)=c1xn-1

+c2xn-2+...+

cn-1x+cn

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

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

運(yùn)算，即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位，相當(dāng)于乘以xi后的模(xn+1)運(yùn)算，即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的碼字可用多項(xiàng)式：0,x2+x,x+1,x2+1表示。n=3循環(huán)碼仍是線性碼，由循環(huán)碼構(gòu)成的線性子空間為循環(huán)子空間。將碼表示成C或C(x)。9生成多項(xiàng)式g(x)的兩個(gè)定理定理一

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

即g(x)是另一個(gè)更底的碼式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個(gè)，故可組成2n-r個(gè)碼式，而(n，k)碼的碼字個(gè)數(shù)為2k個(gè)且碼式必是g(x)的倍式=>n-r=k。證畢12生成多項(xiàng)式定義：由定理一確定的碼式g(x)稱為（n，k）循環(huán)碼的生成多項(xiàng)式。循環(huán)碼由生成多項(xiàng)式g(x)的倍式組成，表示為：定理二

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

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

故g(x)是xn-1

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

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

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

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

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

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

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

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

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

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

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

xn＋1=

h(x)g(x)

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

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

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

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

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

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

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

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

24例題—循環(huán)碼的生成例題：對(duì)上例的（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)碼的檢錯(cuò)例題：對(duì)上例的（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因?yàn)镾(x)≠0

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

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

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

k/n，我們一般用R=

k/n表示卷積碼的編碼效率。卷積碼是線性碼，但不是分組碼，因?yàn)榫矸e碼是有記憶的編碼。

30(3，2，1)

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

mi(1)

ci(1)

mi(2)

ci(2)

ci(3)

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

mi(1),

mi(2)]，則并行輸出一個(gè)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)可見，卷積碼當(dāng)前輸出的碼字的監(jiān)督元不僅與當(dāng)前輸入的信息元有關(guān)，還與前次輸入的2個(gè)信息碼元有關(guān)。

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

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

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

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

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

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

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

35卷積碼的描述方法：卷積碼的描述方法有兩類：1)解析法：包括離散卷積法、生成矩陣法、碼多項(xiàng)式法等，多用于編碼。2)圖形法：包括狀態(tài)圖、樹圖、柵格圖等，常用于譯碼，特別是網(wǎng)格圖。特點(diǎn)：用碼多項(xiàng)式法表示卷積碼編碼器的生成多項(xiàng)式最為方便；柵格圖對(duì)于分析卷積碼的譯碼算法十分有用；狀態(tài)圖表明卷積碼編碼器是一種有限狀態(tài)的馬爾科夫過程。36１離散卷積法設(shè)在l時(shí)段，輸入的信息碼組為：輸出的卷積碼組為：移位寄存器中存有前m個(gè)時(shí)段輸入的m個(gè)信息碼組。由于v(l)與當(dāng)前時(shí)段及此前m個(gè)時(shí)段的輸入碼組呈線性關(guān)系。若以v(l-i,l)表示l-I時(shí)段的輸入u(l-i)對(duì)v(l)的貢獻(xiàn)，則有：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２生成矩陣描述法卷積碼的矩陣描述：卷積碼是線性碼，故有生成矩陣和一致校驗(yàn)矩陣。由以上的離散卷積式，展開得：39生成矩陣描述法（續(xù)）若將輸入的信息碼字序列表示為如下的半無限矩陣：

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

v={v(0),v(1),…,,v(m),…,,v(l)…}則生成矩陣與信息碼的關(guān)系可表示為：其中：為卷積碼的生成矩陣。40生成矩陣描述法（續(xù)）為一個(gè)半無限矩陣，特點(diǎn)：每一個(gè)k行都是前一k行右移n列的結(jié)果。故中的第一個(gè)k行的前(m+1)列完全決定了，將其提出，稱為卷積碼的基本生成矩陣GB。式中，G0,G1…Gm都是k行n列矩陣，其中第i行表示各組信息碼字的第i位對(duì)輸出v(l)的貢獻(xiàn)。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)將對(duì)m+1位輸出產(chǎn)生作用．這種影響可用如下構(gòu)造的m+1元組g(i,j)來描述：｛gi,j｝稱為卷積碼的子生成元或生成序列．(n，k，m)卷積碼共有個(gè)生成元．42生成矩陣描述法（例子）例子：一個(gè)(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階矩陣，有生成矩陣具有如上形式時(shí)生成的卷積碼為系統(tǒng)碼，一般的表示為。

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

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

46基本一致校驗(yàn)矩陣（3，1，3）卷積碼的校驗(yàn)關(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)

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

其中

稱為（3，1，3）卷積碼的基本一致校驗(yàn)矩陣?；疽恢滦ｒ?yàn)矩陣可以判斷第i－3，i－2，i－1，i個(gè)輸出碼字是否碼序列中的4個(gè)碼字，與線性碼的一致校驗(yàn)矩陣一樣，起著校驗(yàn)作用，但它只對(duì)4個(gè)碼字起校驗(yàn)作用。

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

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

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

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

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

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

g(i,j)(x)=gi,j+gi,n+jx+…+gi,mn+jxm是生成元g(i,j)的多項(xiàng)式表達(dá)，故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ū)別在于卷積碼的編碼要存儲(chǔ)m段消息，這些消息隨新的輸入而改變，并影響當(dāng)前輸出．因此可將這些存儲(chǔ)數(shù)據(jù)作為描述編碼器變化的內(nèi)部狀態(tài)．對(duì)二元(n,k,m)卷積碼，存儲(chǔ)器（移位寄存器）共有M=km個(gè)單元，即共有2M個(gè)不同的狀態(tài)，記為：l時(shí)刻的狀態(tài)用狀態(tài)矢量表示：下一時(shí)刻的狀態(tài)取決于當(dāng)前狀態(tài)和當(dāng)前輸入u(l)，其關(guān)系成為狀態(tài)轉(zhuǎn)移方程：54卷積碼的狀態(tài)轉(zhuǎn)移圖描述法(續(xù)）當(dāng)前時(shí)刻的輸出v(l)取決于當(dāng)前時(shí)刻的輸入u(l)和當(dāng)前狀態(tài)，其關(guān)系稱為輸出方程：卷積碼有2M個(gè)可能狀態(tài)，在某一時(shí)刻同時(shí)輸入一段k位信息碼，有2k個(gè)可能取值，故每一時(shí)刻的狀態(tài)轉(zhuǎn)移只能有個(gè)可能．狀態(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)移圖直接反映了編碼器在任一時(shí)刻的工作狀態(tài)；而開放型的狀態(tài)轉(zhuǎn)移圖則更適合描述特定輸入序列的編碼過程，但