第6章634幾種重要的碼

1、HUST - Information and Coding Theory1第第6章章 信道編碼信道編碼o6.1 信道編碼的概念o6.2 線性分組碼o6.3 循環(huán)碼循環(huán)碼o6.4 卷積碼HUST - Information and Coding Theory26.3 6.3 循環(huán)碼循環(huán)碼o線性分組碼對碼的選取做了線性約束，使得計算量變小。o譯碼算法是一種通用譯碼算法，效率不高。o循環(huán)碼是1957年由一個叫Prange的科學家開始研究。o循環(huán)碼在線性約束的基礎上增加了約束條件，是目前研究最為成熟的一類碼，大多數(shù)有實用價值的糾錯碼都屬于循環(huán)碼的范疇。HUST - Information and Co

2、ding Theory3定義定義o定義：定義：對于一個（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) n1 位為 C(n-1)=cn ,cn-1 , . ,c1o若 C(i) , i = 1, 2, . , n1 均為碼字，則稱這個（n，k）線性分組碼為循環(huán)碼循環(huán)碼。 o循環(huán)碼一般也記為（n，k）碼，其中 n 為碼字的長度， k 為信息位的長度。HUST - Information

3、and Coding Theory4循環(huán)碼的碼多項式循環(huán)碼的碼多項式o循環(huán)碼的特點是，若循環(huán)碼的特點是，若 C 是一個碼字，那么它的循環(huán)移位是一個碼字，那么它的循環(huán)移位所形成的新序列同樣也是一個碼字。所形成的新序列同樣也是一個碼字。o循環(huán)碼是線性分組碼的一個重要子類，它具有完整的代循環(huán)碼是線性分組碼的一個重要子類，它具有完整的代數(shù)結(jié)構(gòu)，其編碼和譯碼相對比較簡單，易于實現(xiàn)。數(shù)結(jié)構(gòu)，其編碼和譯碼相對比較簡單，易于實現(xiàn)。 o循環(huán)碼也是線性分組碼，因此可用校驗矩陣或生成矩陣循環(huán)碼也是線性分組碼，因此可用校驗矩陣或生成矩陣來構(gòu)成。但由于循環(huán)碼具有循環(huán)移位特性，且是自封閉來構(gòu)成。但由于循環(huán)碼具有循環(huán)移位特

4、性，且是自封閉的，故采用多項式的方法描述更為方便。的，故采用多項式的方法描述更為方便。 on 長的循環(huán)碼字長的循環(huán)碼字 C = c1 , c2 , . , cn 可以用一個可以用一個 xn-1 次多次多項式來表示，稱為項式來表示，稱為，表示為，表示為 C(x)=c1 xn-1 + c2 xn-2 + . + cn-1 x+ cn HUST - Information and Coding Theory5碼多項式的運算碼多項式的運算o一元多項式o多項式的次數(shù)定義為：o零次多項式：零多項式：o多項式加法：o多項式乘法：01().nnfxff xf x0( )max( |0,0,1. )if xif

5、in0( )f xf( )0fx 0011( )( )()().()nnnf xg xfgfgxfgx010000( )( ) ( ).( )( )( ). 0,1. , . 1,2. llijijjnijijj i mh xf x g xhh xh xlh xf xg xnmf gim mnhf gimmmn HUST - Information and Coding Theory6碼多項式的運算碼多項式的運算o碼多項式的模運算和整數(shù)的模運算類似：長除法。o例如：63242263644342323221 mod (1) 1x1 1 1 1 1 1 xxxxxxxxxxxxxxxxxxxxxx

6、xHUST - Information and Coding Theory7碼多項式的運算碼多項式的運算o因式和倍式：因式和倍式：o余式：余式：()()()()()()()hxfxgxfxhxhxfx若， 則 稱是的 因 式 ，是 的倍 式 。00()()()()()()()()(), 0()()()()()()()()()() m o d()hxfx gxqxrxhxqxfxrxrxfxhxrxfxrxhxfxhxrxfx 若， 則 總 存 在 商 式和 余 式， 使 得。稱與模相 等 ，是模的 余 式 。 記 為 ：HUST - Information and Coding Theory8

7、碼多項式的運算碼多項式的運算o循環(huán)碼的循環(huán)特性可由多項式的模運算來表示循環(huán)碼的循環(huán)特性可由多項式的模運算來表示 n當碼字向左移 1 位，相當于乘以 x 后的模 (xn+1) 運算，即 C(1)(x) = x C(x) mod (xn+1) C(1)(x) = c1 xn + c2 xn-1+ . +cn-1 x2+ cn x mod (xn+1)C(1)(x) = c2 xn-1+ c3 xn-2+ . + cn x + c1n如果碼字向左移 i 位，相當于乘以 xi 后的模(xn+1)運算，即 C(i)(x) = xi C(x) mod (xn+1) C(i)(x) = c1 xn+i-1

8、+ c2 xn+i-2+ . +cn-1 xi+1+ cn xi mod (xn+1)C(i)(x) = ci+1 xn-1 + ci+2 xn-2 + . + ci-1 x + ciHUST - Information and Coding Theory9例子：例子：o例如：o其中：CA是線性循環(huán)碼，CB是非循環(huán)線性分組碼，而CC是非線性循環(huán)碼。oCA的碼字可用多項式：0,x2+x,x+1,x2+1表示。n=3o循環(huán)碼仍是線性碼，由循環(huán)碼構(gòu)成的線性子空間為循環(huán)子空間。將碼表示成C或C(x)。(000)(000)(000)(110)(100)(100) (011)(011)(010)(101)

9、(111)(001)ABCCCCHUST - Information and Coding Theory10生成多項式生成多項式g(x)的兩個定理的兩個定理 (n,k) 循環(huán)碼C(x)中存在唯一的一個非零的、首一的和最低次數(shù)為r ( r n ) 的碼多項式 g(x) 滿足 并且，c(x)是碼式當且僅當c(x)是g(x)的倍式。11100( ).0rrrg xxgxg xggrnkHUST - Information and Coding Theory11定理一證明定理一證明o唯一性：唯一性：og0證明證明: :若g0=0，則o即g(x)是另一個更底的碼式g(x)的循環(huán)移位，矛盾。o碼式是碼式是

10、g(x)的倍式：的倍式：由循環(huán)移位特性知： xi g(x) ，i=1,2n-1-r均是碼式。( )( )( )( )( )0)rrgxg xgxg xgxrxx若是另一個最低次r的非零首一碼式，則仍為碼式。但的次數(shù)（因為。21121( )(.)( ) mod1rrrng xx gg xgxxxg xxgxxHUST - Information and Coding Theory12定理一證明（續(xù)）定理一證明（續(xù)）o由碼的線性分組特性： an-1-rg(x)xn-1-r+a1g(x)x+a0g(x)=a(x)g(x) (1) 也是碼式。故g(x)的倍式若次數(shù)小于n則是碼式。o反之：f(x)若是碼

11、式，則可表示為： 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ù) f(x)是g(x)的倍式。or=n-k證明證明：由碼式必是g(x)的倍式及(1)式知a0 ， a1 an-1-r有n-r個，故可組成2n-r個碼式，而(n，k)碼的碼字個數(shù)為2k個且碼式必是g(x)的倍式=n-r=k。證畢證畢HUST - Information and Coding Theory13生成多項式生成多項式o定義定義：由定理一確定的碼式g(x)稱為（n，k）循環(huán)碼的生成多項式。循環(huán)碼由生成多項

12、式g(x)的倍式組成，表示為： g(x) 是(n,k) 循環(huán)碼的生成多項式，當且僅當 g(x) 是 xn - -1 的 r = n k 次因式。o證明：必要性證明：必要性 若g(x)是生成多項式，則有： 由循環(huán)移位定義得， r(x)是g(x)的循環(huán)移位碼式，所以 故g(x)是xn -1 的因式。0( ) ( )| ( )( ) ( ),( )C xc xc xa x g xa xk0( )1.(1)( ) ( )knx g xxr xr xn1( )( )( )( )( )( )( )nkkkxx g xr xx g xa x g xg xxa xHUST - Information and

13、Coding Theory14定理二證明（續(xù)）定理二證明（續(xù)）o充分性：充分性： 設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)碼。證畢證畢011( )( ).( )( ) ( )ka g xa g xag xa x g x10112211012(1)1(1)(1)1 ()()()()()() (.) (1)(.) (1)() ()()()()()()nnnnnnnnnnc xa x gxxc xxa x gxc

14、c xcxxcxcc xc xcxcxcxcfx gxcxcxb x gx 對HUST - Information and Coding Theory15例題例題 構(gòu)造循環(huán)碼構(gòu)造循環(huán)碼o例題：例題：構(gòu)造一個（7，3）循環(huán)碼。o解解：n由于 n7，對 (x7+1) 因式分解得： x7 + 1 = ( x + 1 ) ( x3 + x2 + 1 ) ( x3 + x + 1 ) n由于 k=3，則 n k = 4，因此 ( 7 , 3 ) 循環(huán)碼的兩個可選的生成多項式為：ng1(x) = (x+1) (x3+x2+1)ng2(x) = (x+1) (x3+x+1)HUST - Informatio

15、n and Coding Theory16循環(huán)碼的生成矩陣循環(huán)碼的生成矩陣o由于（n，k）循環(huán)碼共有 2k 個碼字，從碼組中取出一個前面 k1 位都是 0 的碼字，用 g(x) 表示，不難看出 g(x) 的多項式次數(shù)為（nk）。o因為 xi g (x), i = 0, 1, 2, . , k-1 均是碼字且相互獨立，故可用 xi g (x), i = 0, 1, 2, . , k-1 作為生成矩陣G 的 k 行。o綜上所述，由多項式 g(x) 可以構(gòu)成生成多項式矩陣生成多項式矩陣為 12( )( )( )( )( )kkxg xxg xG xxg xg xHUST - Information

16、and Coding Theory17生成矩陣生成矩陣Go ( n , k ) 循環(huán)碼的生成矩陣在 g(x) 確定后可以表示為 G1012101212011.0 . 0( )0. 0( )( )00 .0.krrrrrkrrk ngggggxg xgggggxg xg xggggGHUST - Information and Coding Theory18生成多項式生成多項式 g(x) 與循環(huán)碼的生成與循環(huán)碼的生成o由于循環(huán)碼是線性分組碼，因此對于碼字C 有 C(x) = m1 m2 . mk G(x) 式中 m1 m2 . mk 為 k 位信息元矢量。 o上式表明，循環(huán)碼的所有碼字可由 g(

17、x) 產(chǎn)生，g(x) 稱為循環(huán)碼的生成多項式。生成多項式。o在 ( n，k ) 循環(huán)碼中，g(x) 是唯一的一個 ( nk ) 次多項式，且次數(shù)最低。o每個碼多項式C(x) 都是g(x)的倍式，而每個為g(x) 的倍式且次數(shù)小于或等于(n1) 的多項式必是一個碼多項式。 11( )( )( )kkk ik iiiiiC xm xg xm xg x上式展開可得1( )( )( ) ( )kk iiim xm xC xm x g x令 則有HUST - Information and Coding Theory19校驗多項式校驗多項式 h(x)o循環(huán)碼的生成多項式 g(x) 是 xn1 的因式，即

18、 xn1 = h (x)g(x) k 次多項式 h(x) 稱為碼的校驗多項式校驗多項式。o設則 g(x) 和 h(x) 的系數(shù)滿足以下關(guān)系 101000000000000kkkkn khhhhhhghhg000( ),( )kn kk iiiiiih xhxg xg xHUST - Information and Coding Theory20校驗方程的獲得校驗方程的獲得o校驗方程可由如下方法得到：12121201201110101( )( ) ( ) ( ) ( )( ) ( ) ( )( )(1)( )( )(.)(.)0( ) ( )(.)(.nnnknknkkkkkkkknnnC xa

19、 x g xC x h xa x g x h xa xxa x xa xaxaxa xaxaxaxxxrC x h xcc xc xhh xh 由循環(huán)碼的碼式 有式中，,.共 項的系數(shù)為 ，另一方面110)0 0(1)kkkknkin ijixxxxh cjnkr 比較這兩式中同冪次項系數(shù)，由,.項的系數(shù)為 ，得到校驗方程為：HUST - Information and Coding Theory21循環(huán)碼的校驗矩陣循環(huán)碼的校驗矩陣 H 和生成矩陣和生成矩陣Go校驗矩陣可以表示為右邊矩陣H， 滿足xn+1=h(x)g(x)。o注意到生成矩陣G的行向量為g(x)系數(shù)的升冪排列，校驗矩陣H的行向量

20、為h(x)系數(shù)的降冪排列。如果G為降冪排列，則對應的H為升冪排列。101000000000kkkkhhhhhhhhH01210121011.0 . 00. 000 .0.rrrrrrrggggggggggggggGHUST - Information and Coding Theory22循環(huán)碼的伴隨多項式循環(huán)碼的伴隨多項式o假設 和 以及 分別為o則對于加性信道有 R(x) = C(x) + e(x) o設g(x)為碼的生成多項式，由于碼字多項式C(x) 能夠被g(x)除盡，故有R(x) mod g(x)=e(x) mod g(x) 即：o定義伴隨多項式伴隨多項式為 S(x) = e(x)

21、mod g(x)111( )( )( )nnnn in in iiiiiiiC xc xe xe xR xrx；( )( )( )( )( )( )( )( )R xC xe xe xp xg xg xg xHUST - Information and Coding Theory23循環(huán)碼的檢糾錯循環(huán)碼的檢糾錯o根據(jù)伴隨式的定義，若無錯誤傳輸，則 S(x) = 0 ，否則S(x)0，由此可實現(xiàn)循環(huán)碼的檢錯檢錯。 o因為g(x)的次數(shù)為nk，e(x)的次數(shù)為n1，所以伴隨式的最高次數(shù)為nk1，那么S(x)共有nk項，故有2n-k種可能的伴隨式。若滿足2n-k n+1，則循環(huán)碼具有糾錯糾錯能力。

22、oBCH 碼碼是一類重要的循環(huán)碼，它能夠最有效地糾正多個獨立錯誤。BCH 碼把生成多項式與碼的最小距離和糾錯能力聯(lián)系起來，根據(jù)所需要的糾錯能力，選取適當?shù)?g(x) ，可以編出非常有效地糾正多個獨立錯誤的 BCH 碼。（略） HUST - Information and Coding Theory24例題例題 校驗多項式和生成矩陣校驗多項式和生成矩陣o例題：例題：對上例的（7 , 3）循環(huán)碼，求其校驗多項式和生成矩陣。o解：解：n校驗多項式為 h(x) = ( x7 + 1 ) / g(x) = ( x3 + x + 1 ) n生成多項式矩陣為 G(x) 、生成矩陣為 G 6432253242

23、( )1 0 1 1 1 0 0( )( )0 1 0 1 1 1 0( )0 0 1 0 1 1 11xxxxx g xG xxg xxxxxGg xxxx；HUST - Information and Coding Theory25例題例題 循環(huán)碼的生成循環(huán)碼的生成o例題：例題：對上例的（7 , 3）循環(huán)碼，若輸入信息碼字為 110 ，求其循環(huán)碼字。o解：解：n信息碼字 110 的碼式為 m(x) = x2 + x n得循環(huán)碼式為 c(x)= m(x)g(x) = (x2 + x)(x4 + x2 + x+1)= x6+x5+ x4+xn則其循環(huán)碼字為 1110010 。 HUST - I

24、nformation and Coding Theory26例題例題 循環(huán)碼的檢錯循環(huán)碼的檢錯o例題：例題：對上例的（7 , 3）循環(huán)碼，若接收碼字為 1100100 ，判斷是否是許用碼字。o解：解：n接收碼字 1100100 的碼式為 R(x) = x6 + x5 + x2 n由伴隨式 S(x) = e(x) mod g(x) = R(x) mod g(x) n S(x)= x6 + x5 + x2 mod (x4 + x2 + x + 1) =1n因為 S(x) 0 ，因此該碼字不是（7，3）循環(huán)碼的許用碼字。 HUST - Information and Coding Theory27小

25、結(jié)o循環(huán)碼為線性分組碼；卷積碼為線性非分組碼。o循環(huán)碼的特點是具有循環(huán)移位特性，因此可以用多項式法描述。n本節(jié)介紹了循環(huán)碼利用多項式的編譯碼方法，包括生成多項式的構(gòu)造，利用生成多項式生成碼字，校驗多項式及其與生成多項式的關(guān)系、利用伴隨多項式譯碼等。n討論了多項式描述與一般線性分組碼的矩陣描述（生成矩陣、校驗矩陣、伴隨式）間的關(guān)系。HUST - Information and Coding Theory28第第6章章 信道編碼信道編碼o6.1 信道編碼的概念o6.2 線性分組碼o6.3 循環(huán)碼o6.4 卷積碼卷積碼HUST - Information and Coding Theory296.4

26、 6.4 卷積碼卷積碼o在分組碼中，任何特定的時間單位內(nèi)編碼器所產(chǎn)生的在分組碼中，任何特定的時間單位內(nèi)編碼器所產(chǎn)生的 n個碼元的碼組，僅取決于該時間單位內(nèi)個碼元的碼組，僅取決于該時間單位內(nèi) k 個消息位。個消息位。o存在著另一種碼，由編碼器在特定的時間內(nèi)所產(chǎn)生的碼存在著另一種碼，由編碼器在特定的時間內(nèi)所產(chǎn)生的碼元不但取決于這個特定的時間段內(nèi)進入的信息組，而且元不但取決于這個特定的時間段內(nèi)進入的信息組，而且也與前面的時間段內(nèi)的信息組有關(guān)，這種碼稱為也與前面的時間段內(nèi)的信息組有關(guān)，這種碼稱為。o卷積碼的編碼可用移位寄存器來完成。卷積碼的編碼可用移位寄存器來完成。o卷積碼與分組碼相似，具有糾正隨機錯

27、誤、突發(fā)錯誤或卷積碼與分組碼相似，具有糾正隨機錯誤、突發(fā)錯誤或同時糾正這兩類錯誤的能力。對于許多實際的誤差控制，同時糾正這兩類錯誤的能力。對于許多實際的誤差控制，卷積碼的性能優(yōu)于分組碼。卷積碼的性能優(yōu)于分組碼。 HUST - Information and Coding Theory30卷積碼的概念卷積碼的概念o定義：定義：對于任一給定時刻，編碼器的一個輸出碼字不僅與該時刻的當前輸入碼字有關(guān)，還與編碼器的移位寄存器中存貯的前面m個輸入信息碼字有關(guān)。因此。n其中n為輸出的每個碼字的位數(shù)nk為輸入的每個信息碼字的位數(shù)nm為移位寄存器中存貯的信息碼字個數(shù)。 o定義 m 為卷積碼的記憶長度，而為卷積碼

28、的記憶長度，而 ( m + 1 ) 為卷積碼的碼字約束長為卷積碼的碼字約束長度度，相應的比特（碼元）約束長度比特（碼元）約束長度為 ( m + 1 ) n。o對L段輸入的信息碼進行編碼，由于初始寄存器為全0，結(jié)束時也要額外輸入m段無效的全0碼字，故共產(chǎn)生L+m段輸出碼字，所以卷積碼的碼率碼率為R =Lk/(L+m)n 。當 L很大時，R= k / n ，我們一般用R= k / n表示卷積碼的。o卷積碼是線性碼，但不是分組碼，因為卷積碼是有記憶的編碼。 HUST - Information and Coding Theory31( 3，2，1 ) 卷積碼舉例卷積碼舉例o以下給出了一個( 3，2，

29、1 )卷積碼編碼器的原理圖。 mi(1) ci(1) mi(2) ci(2) ci(3) o該編碼器由 2 個移位寄存器構(gòu)成。o編碼器每并行輸入一個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) o可見，卷積碼當前輸出的碼字的監(jiān)督元不僅與當前輸入可見，卷積碼當前輸出的碼字的監(jiān)督元不僅與當前輸入的信息元有關(guān)，還與前次輸入的的信息元有關(guān)，還與前次輸入的 2 個信息碼元

30、有關(guān)。個信息碼元有關(guān)。 HUST - Information and Coding Theory32卷積碼的校驗關(guān)系式卷積碼的校驗關(guān)系式o下面以下面以（3，1，3）卷積碼為例，討論卷積碼的生成矩陣卷積碼為例，討論卷積碼的生成矩陣和校驗矩陣。和校驗矩陣。o把給定的信息序列 (m1 , m2 , m3 , . ) 進行分組，使每個信息組只包含一個信息位。o輸出的每組碼字由三位組成，其中有一個信息位和兩個校驗位，則輸出的碼序列為 ( m1 p11 p12 , m2 p21 p22 , m3 p31 p32 , . )o設校驗位與信息位滿足以下校驗關(guān)系：校驗關(guān)系： pi1 = mi + mi-1 +

31、mi-3 ; pi2 = mi + mi-1 + mi-2 n校驗關(guān)系式表明，當前的校驗位與當前的信息位和過去的三個信息位有關(guān)，且滿足一定的線性關(guān)系。n某一信息碼字會影響 4 個卷積碼字，為此稱這個卷積碼為約束長度為 4 個碼字的卷積碼。 HUST - Information and Coding Theory33編碼器框圖編碼器框圖o下圖為（下圖為（3，1，3）卷積碼的編碼器原理框圖）卷積碼的編碼器原理框圖o輸入信息序列為m = ( m1 , m2 , m3 , . ) o輸出碼字序列為C = ( c11 c12 c13 , c21 c22 c23 , c31 c32 c33 , . ) C

32、 = (m1 p11 p12 , m2 p21 p22 , m3 p31 p32 , . ) ci1=mi ci2=pi1 ci3=pi2 mi mi-1 mi-3 mi-2 HUST - Information and Coding Theory34生成矩陣生成矩陣 Go改寫校驗關(guān)系式改寫校驗關(guān)系式 pi1 = mi + mi-1 + mi-3 pi2 = mi + mi-1 + mi-2o可以得到可以得到 m 和和 C 滿足以下關(guān)系滿足以下關(guān)系 111212123231234134234mmmmmmmmmmmmmmmmmmmmmTCHUST - Information and Coding

33、 Theory35生成矩陣生成矩陣 G（續(xù)）續(xù)）o改寫的校驗關(guān)系式若寫成矩陣形式，則得到改寫的校驗關(guān)系式若寫成矩陣形式，則得到 m 和和 C 間的間的矩陣關(guān)系為矩陣關(guān)系為 n式中的矩陣 G 稱為卷積碼的生成矩陣生成矩陣。 000000000000000000000000000000011110110111100000000000111110110111101111111CmGmHUST - Information and Coding Theory36卷積碼的描述方法：卷積碼的描述方法：o卷積碼的描述方法有兩類： 1)解析法：包括離散卷積法、生成矩陣法、碼多項式法等，多用于編碼。 2)圖形法：

34、包括狀態(tài)圖、樹圖、柵格圖等，常用于譯碼，特別是網(wǎng)格圖。o特點：n用碼多項式法表示卷積碼編碼器的生成多項式最為方便；n柵格圖對于分析卷積碼的譯碼算法十分有用；n狀態(tài)圖表明卷積碼編碼器是一種有限狀態(tài)的馬爾科夫過程。HUST - Information and Coding Theory37離散卷積法離散卷積法o設在l時段，輸入的信息碼組為：o輸出的卷積碼組為：o移位寄存器中存有前m個時段輸入的m個信息碼組。o由于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-

35、2,l)+ + v(l-m,l)o各v(l-i,l)與u(l-i,l)為線性關(guān)系，類似線性分組中C=mG?？杀硎緸椋?11( )( )( ).( )ku lu l u lul011( )( ) ( ).( )nv lv l v lvlHUST - Information and Coding Theory38離散卷積法（續(xù)）離散卷積法（續(xù)） 01010( , )( )(1, )(1) .(, )() .(, )()( )( )(1).().,() () (0,1, 2.)( )0 0imimmhhv l lu l Gv llu lGv li lu li Gv lm lu lm Gv lu l

36、Gu lGu li Gu lm Gu lh Glu ll則 有 ：（ 表00l示 起 始 段時 ， 寄 存 器 的 初 始 值 為 ）此 式 稱 為 離 散 卷 積 表 達 式 。HUST - Information and Coding Theory39生成矩陣描述法生成矩陣描述法o卷積碼的矩陣描述：o卷積碼是線性碼，故有生成矩陣和一致校驗矩陣。o由以上的離散卷積式，展開得：, ( , )BGGg i j010210110110(0)(0)(1)(0)(1)(2)(0)(1)(2) .( )(0)(1).(1)( ) .( )()(1).(1)( )mmmmvuGvuGuGvuGuGuGv

37、muGuGu mGu m Gv lu lm Gu lmGu lGu l GHUST - Information and Coding Theory40生成矩陣描述法（續(xù)）生成矩陣描述法（續(xù)）o若將輸入的信息碼字序列表示為如下的半無限矩陣：u=u(0), u(1) , u(m) , u(l)o輸出卷積碼字也表示為如下的半無限矩陣： v=v(0),v(1), ,v(m), ,v(l)o則生成矩陣與信息碼的關(guān)系可表示為： 其中：為卷積碼的卷積碼的生成矩陣。生成矩陣。vuGGHUST - Information and Coding Theory41生成矩陣描述法（續(xù)）生成矩陣描述法（續(xù)）o為一個半無

38、限矩陣，特點：每一個k行都是前一k行右移n列的結(jié)果。故中的第一個k行的前(m+1)列完全決定了，將其提出，稱為卷積碼的基本生成矩陣卷積碼的基本生成矩陣GB。o式中，G0 ,G1Gm都是k行n列矩陣，其中第i行表示各組信息碼字的第i位對輸出v(l)的貢獻。012101210121.0.0.0.00.mmmmmmGGGGGGGGGGGGGGGGGGG0121(1).Bmm kmnGGGGGGHUST - Information and Coding Theory42生成矩陣描述法（續(xù)）生成矩陣描述法（續(xù)）o將GB中第i行第j列表示為gi,t，則o其中，t可表示為t=j+hm，j=1,2 ,n，h=

39、0,1,2,no則gi,t表示輸入移位寄存器中的第h段的第i位輸入比特u(l-t,i)參與第j位輸出比特的編碼， gi,t則不參與輸出編碼o由于記憶長度為m，即第i位輸入比特u(l-t,i)將對m+1位輸出產(chǎn)生作用這種影響可用如下構(gòu)造的m+1元組g(i,j)來描述：o gi,j 稱為卷積碼的子生成元或生成序列(n，k，m)卷積碼共有 個生成元,(1 )BitkmnGg,2,( , )(,.,.,)1,2,., 1,2,. 0,1,2,.i ji njinji hnji mnjg i jgggggikjnhmknHUST - Information and Coding Theory43生成矩陣

40、描述法（例子）生成矩陣描述法（例子）o例子：一個(2,1,2)非系統(tǒng)卷積碼如圖所示：uu(l-2)/v2(l)/ v2v1(l)/ v1u(l)/0u(l-1)/12+ + +原理圖u(l)12u(l-1)u(l-2)+ + +v(l)電路圖HUST - Information and Coding Theory44生成矩陣描述法（例子）生成矩陣描述法（例子）120 ,001211122 ,220120121,13)( ),( )()(1,1)(1),(1)(, 0 )(1, 0 )(2 ),(2 )()(1,1) 1 11 01 11 11 01 11 11 01 1.(1,1)(1 1 1

41、)Bk =mvlvlvlvlvlvlGGGGG G GGgg對 每 個 獨 立 的 輸 入 段 （， 分 別 有 ：可 以 得 到，(1, 2 )(1 0 1)HUST - Information and Coding Theory45系統(tǒng)碼的生成矩陣形式系統(tǒng)碼的生成矩陣形式o以上（3，1，3）卷積碼是系統(tǒng)碼系統(tǒng)碼，其碼字的第一位總是信息碼字。其生成矩陣可以寫成下列形式 n式中 I 為 kk 11 階單位陣n0為 kk 11 階全 0 方陣，nPi為 k （nk） 12 階矩陣，有o生成矩陣具有如上形式時生成的卷積碼為系統(tǒng)碼，一般的表示為。生成矩陣具有如上形式時生成的卷積碼為系統(tǒng)碼，一般的表示

42、為。 1234P =11,P =11P =01,P =104123412312312P0IIIPPPPPPPPP0000000G00PIPP000001, 2,.,()kknhhknhGI PGPhmPPknk其 中，均 為矩 陣 。HUST - Information and Coding Theory46由生成矩陣產(chǎn)生碼序列由生成矩陣產(chǎn)生碼序列o已知生成矩陣，可以產(chǎn)生所有卷積碼字。o對以上（3，1，3）碼，若輸入信息序列為（0 1 0 0 1 0 1 0 1 1 ），則對應的碼字序列為 o對于所生成的碼序列，每 3 個數(shù)字組成一個碼字，其中包括一個信息位和兩個校驗位。 1110110010

43、10000000111011001010000000111011001000111011000000000111011000000000000111CmGmHUST - Information and Coding Theory47基本一致校驗矩陣基本一致校驗矩陣o（3，1，3）卷積碼的校驗關(guān)系式可以表示為卷積碼的校驗關(guān)系式可以表示為 mi-3 + mi-1 + mi + pi1 = 0 ; mi-2 + pi2 + mi-1 + mi = 0 o令令C0 = ( mi-3 pi-3,1 pi-3,2 , mi-2 pi-2,1 pi-2,2 , mi-1 pi-1,1 pi-1,2 , mi

44、 pi1 pi2 ) 則則 校驗校驗 關(guān)系式可關(guān)系式可 寫成矩陣寫成矩陣 形式：形式： o其中其中 稱為稱為（3，1，3）卷積碼的基本一致校驗矩陣卷積碼的基本一致校驗矩陣。o基本一致校驗矩陣可以判斷第 i3，i2，i1，i 個輸出碼字是否碼序列中的 4個碼字，與線性碼的一致校驗矩陣一樣，起著校驗作用，但它只對 4個碼字起校驗作用。 1 0 00 0 01 0 011 00 0 01 0 01 0 01 0 1TT0B0C = H C = 01 0 00 0 01 0 011 00 0 01 0 01 0 01 0 1BHHUST - Information and Coding Theory4

45、8一致校驗矩陣一致校驗矩陣o令令C = ( m1 p11 p12 , m2 p21 p22 , m3 p31 p32 , . )o由校驗關(guān)系式展開由校驗關(guān)系式展開 得如下關(guān)系式得如下關(guān)系式 1111121221122212332134412344224551345523321000000000.0.mpmpmmpmmpmmmpmmmpmmmpmmmmmppmmmpHUST - Information and Coding Theory49一致校驗矩陣（續(xù)）一致校驗矩陣（續(xù)）o校驗關(guān)系式的展開式寫成矩陣形式為校驗關(guān)系式的展開式寫成矩陣形式為o系數(shù)矩陣為 H 稱為（3，1，3）卷積碼的。 1 00

46、 11 00 11 00 11 000 0 00 0 00 00 0 00 00 0 00 00 00 0 00 00 00 0 00 00 00 00 0 00 00 00 00 0 00 0 00 00 00 00 0 00 0 00 00 00 00 0 0111 00 1111111111111011001111011110TTCC= H=0HUST - Information and Coding Theory50校驗矩陣的表示式校驗矩陣的表示式o以上校驗矩陣可以寫為如下表示式：以上校驗矩陣可以寫為如下表示式：n式中 PiT 為（nk）k 21 維矩陣n0 為（nk）（nk） 22

47、維全方陣nI 為（nk）（nk） 22 維單位矩陣。o由卷積碼的生成矩陣 G 和校驗矩陣 H 的表示式可知，G和 H 有一定的關(guān)系，即 G HT0 。對于系統(tǒng)碼，由G 可以得到 H，反之，由 H 可以得到 G。 T3TT4T1TT21TT21TT213TTTT4231IIII000H000PPPPPPPPPP00000PIPPPHUST - Information and Coding Theory51卷積碼的多項式描述法卷積碼的多項式描述法o記信息碼字序列u=u(0), u(1), u(m), u(l),o對應的多項式為1111222211( )(0)(1).( ).( ).(0)(1)(

48、)( )(0)(1)( )( ). . . . .(0)(1)( )( )(0)(1).mlmlkkkku xuuxu m xu l xuuu mu luuu mu lxxxuuu mu luuxu11122222( ).( ).( )( )(0)(1).( ).( ). . .( )(0)(1).( ).( ).mlmlmlkkkkkm xu l xu xu xuuxu m xu l xu xuuxu m xu l xHUST - Information and Coding Theory52卷積碼的多項式描述法（續(xù)）卷積碼的多項式描述法（續(xù)）o同理，輸出的卷積碼字序列為v=v(0), v(

49、1), v(m), v(l),o對應的多項式為1111222212( )(0)(1).().( ).(0)(1)()( )(0)(1)()( ). . . . .(0)(1)()( )( )( ) .mlmlnnnnnv xvvxv m xv lxvvvmv lvvvmvlxxxvvvmvlvxvxv 0( )( ) (1,2,. )( )ljjlvxvl xj =nx其中，HUST - Information and Coding Theory53卷積碼的多項式描述法（續(xù)）卷積碼的多項式描述法（續(xù)）o線性(n,k,m)卷積碼得多項式表達式為： v(x)T=u(x)TG(x)oG(x)為k n

50、的多項式矩陣，稱為線性卷積碼得多項式生多項式生成矩陣成矩陣oG(x)的第i行第j列元素為 g(i,j)(x)=gi,j+gi,n+jx+gi,mn+jxmo是生成元g(i,j)的多項式表達，故G(x)可寫成 G(x) g(i,j)(x) k no前例(2,1,2)非系統(tǒng)卷積碼中， G(x)1+x+x2 1+x2HUST - Information and Coding Theory54卷積碼的狀態(tài)轉(zhuǎn)移圖描述法卷積碼的狀態(tài)轉(zhuǎn)移圖描述法o卷積碼和分組碼的主要區(qū)別在于卷積碼的編碼要存儲m段消息，這些消息隨新的輸入而改變，并影響當前輸出因此可將這些存儲數(shù)據(jù)作為描述編碼器變化的內(nèi)部狀態(tài)o對二元(n,k,

51、m)卷積碼，存儲器（移位寄存器）共有M=km個單元，即共有2M個不同的狀態(tài)，記為：ol時刻的狀態(tài)用狀態(tài)矢量表示：o下一時刻的狀態(tài)取決于當前狀態(tài)和當前輸入u(l)，其關(guān)系成為狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程：0121, . . . ,MSSS121( )( ),( ),.,( ),( )MMlllll( )(1)ll或用表示）( , )u HUST - Information and Coding Theory55卷積碼的狀態(tài)轉(zhuǎn)移圖描述法卷積碼的狀態(tài)轉(zhuǎn)移圖描述法( (續(xù)）續(xù)）o當前時刻的輸出v(l)取決于當前時刻的輸入u(l)和當前狀態(tài)，其關(guān)系稱為輸出方程：輸出方程：o卷積碼有2M個可能狀態(tài)，在某一時刻

52、同時輸入一段k位信息碼，有2k個可能取值，故每一時刻的狀態(tài)轉(zhuǎn)移只能有個可能o狀態(tài)圖有兩種:開放型和閉合型.o如(2,1,2)非系統(tǒng)卷積碼：狀態(tài)向量 ，共有S0,S1,S2,S3四種狀態(tài)，其狀態(tài)變化如下： ( , )vu 21() HUST - Information and Coding Theory56卷積碼的狀態(tài)轉(zhuǎn)移圖描述法卷積碼的狀態(tài)轉(zhuǎn)移圖描述法( (續(xù)）續(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)移圖（閉合型）HUST - Information and Coding Theory57卷積碼的狀態(tài)轉(zhuǎn)移圖描述法卷積碼的狀態(tài)轉(zhuǎn)移圖描述法( (續(xù)）續(xù)）S0S3S2S10S1S2S3S(00/0,11/1)(10/0,01/1)(11/0,00/1)(01/0,10/1)(2,1,2)碼狀態(tài)轉(zhuǎn)移圖（開放型）11122122uvuvu狀態(tài)轉(zhuǎn)移方程為輸出方程：HUST - Information and Coding Theory58柵格圖（網(wǎng)格圖、籬笆圖）柵格圖（網(wǎng)格圖、籬笆圖）o閉合型的狀態(tài)轉(zhuǎn)移圖直接反映了編碼器在任一時刻的工作狀態(tài)；而開放型的狀態(tài)轉(zhuǎn)移圖則更適合描述特定輸