編碼理論第6章

1、v1955年，埃利斯年，埃利斯( (P. Elias) )首次提出卷積碼首次提出卷積碼的概念的概念v1957年，年，J. M. Wozencraft提出卷積碼的序提出卷積碼的序列譯碼算法列譯碼算法v1963年，年，J. L. Massey提出較易實現(xiàn)的門限提出較易實現(xiàn)的門限譯碼算法譯碼算法v1967年，年，A. J. Viterbi提出卷積碼的一種最提出卷積碼的一種最大似然譯碼算法大似然譯碼算法v卷積碼在深空通信、衛(wèi)星通信、移動通訊卷積碼在深空通信、衛(wèi)星通信、移動通訊等領(lǐng)域得到了應用等領(lǐng)域得到了應用v卷積碼是同分組碼相對應的另一大類糾錯碼卷積碼是同分組碼相對應的另一大類糾錯碼v卷積碼必須用卷積

2、碼必須用序列邏輯電路序列邏輯電路來實現(xiàn)，更適用于前來實現(xiàn)，更適用于前向糾錯系統(tǒng)向糾錯系統(tǒng)v分組碼是用分組碼是用組合邏輯電路組合邏輯電路來實現(xiàn)來實現(xiàn)v有記憶性：有記憶性：在任意給定的時間單元內(nèi)，卷積碼編在任意給定的時間單元內(nèi)，卷積碼編碼器輸出的碼器輸出的n個碼元，其中每個碼元不僅與此單個碼元，其中每個碼元不僅與此單位時間內(nèi)輸入的位時間內(nèi)輸入的k個信息有關(guān)系，而且與此前連個信息有關(guān)系，而且與此前連續(xù)輸入的續(xù)輸入的m個信息有關(guān)系，稱個信息有關(guān)系，稱(n, k, m)卷積碼卷積碼v無記憶性：無記憶性：分組碼編碼器輸出的分組碼編碼器輸出的n個碼元，僅與個碼元，僅與此單位時間內(nèi)輸入的此單位時間內(nèi)輸入的k個

3、信息有關(guān)系個信息有關(guān)系v卷積碼充分利用了各組信息之間的相關(guān)性，卷積碼充分利用了各組信息之間的相關(guān)性，信息序列不被分段，而是被連續(xù)處理信息序列不被分段，而是被連續(xù)處理v通常，卷積碼的通常，卷積碼的n和和k比分組碼的比分組碼的n和和k要小要小的多的多v在同樣的編碼效率下，卷積碼的性能優(yōu)于在同樣的編碼效率下，卷積碼的性能優(yōu)于分組碼分組碼v在相似的糾錯能力下，卷積碼的實現(xiàn)比分在相似的糾錯能力下，卷積碼的實現(xiàn)比分組碼簡單組碼簡單v定義：定義：設(shè)設(shè)f(n)和和g(n)是兩個序列，則序列是兩個序列，則序列f和和g的離的離散卷積運算為散卷積運算為v例子：例子：若若f=(10011), g=(111), 則則f

4、*g的計算過程如的計算過程如下下 (f*g)(0)= 11001 111 + = 1 (f*g)(1)= 11001 111 + = 1 nnmgnfmgf * (f*g)(2)= 11001 111 + = 1 (f*g)(3)= 11001 111 + = 1 (f*g)(4)= 11001 111 + = 0 (f*g)(5)= 11001 111 + = 0 (f*g)(6)= 11001 111 + = 1 故故 f*g=(1001111)+D0D1+V(1)V(2)u圖圖6.1 二元二元(2,1,2)(2,1,2)卷積碼的編碼器的電路圖卷積碼的編碼器的電路圖v該編碼器主要由該編碼器

5、主要由m=2級移位寄存器，級移位寄存器，n=2個個模模2加法器組成加法器組成v所有的卷積碼編碼器都可以用這種類型的所有的卷積碼編碼器都可以用這種類型的線性前饋移位寄存器線性前饋移位寄存器來實現(xiàn)來實現(xiàn)v該編碼器的沖激響應就是通過令該編碼器的沖激響應就是通過令u=(100)所得所得到的兩個輸出序列到的兩個輸出序列v因為編碼器有因為編碼器有m個存儲單元，所以沖激響應個存儲單元，所以沖激響應( (生生成序列成序列) )至多持續(xù)至多持續(xù)m+1個時間單元，且可以寫成個時間單元，且可以寫成v其中上標表示第幾個輸出端其中上標表示第幾個輸出端v圖圖6.1的的(2,1,2)卷積碼的沖激響應為卷積碼的沖激響應為g(

6、1)=(111), g(2)=(101)v另外，沖激響應向量還可以表示輸入、移位寄另外，沖激響應向量還可以表示輸入、移位寄存器和輸出之間的連接關(guān)系，存器和輸出之間的連接關(guān)系，1表示有連接，表示有連接，0表示沒有連接表示沒有連接 221202111101,., ,.,mmggggggggv信息序列信息序列u=(u1,u2,u3,)每次進入編碼器每次進入編碼器1比特比特v編碼器的兩個輸出序列編碼器的兩個輸出序列v可以通過輸入序列可以通過輸入序列u和編碼器的兩個沖激響應和編碼器的兩個沖激響應作卷積運算而得到作卷積運算而得到v若若u=(1011), 圖圖6.1的的(2,1,2)卷積碼的沖激響應為卷積碼

7、的沖激響應為g(1)=(111), g(2)=(101)，則該卷積碼的輸出序列為則該卷積碼的輸出序列為V(1)=u*g(1)=(110001), V(2)=u*g(2)=(100111) ., .,22212021211101vvvvvvvvv輸出序列分別為輸出序列分別為的的(2,1,m)的卷積碼的碼字，為的卷積碼的碼字，為V(1)和和V(2)的交錯的交錯v即即v舉例：舉例：圖圖6.1的的(2,1,2)卷積碼，若卷積碼，若u=(1011), 沖激沖激響應為響應為g(1)=(111), g(2)=(101)，該卷積碼的輸出序該卷積碼的輸出序列為列為V(1)=u*g(1)=(110001), V(

8、2)=u*g(2)=(100111)，得到的碼字為得到的碼字為v=(11,10,00,01,01,11) ., .,22212021211101vvvvvvvv ,.),(221221112010vvvvvvv v以以u=(u1,u2,u3,)為輸入為輸入,以以為生成序列的為生成序列的(2,1,m)卷積碼的輸出序列分別由方卷積碼的輸出序列分別由方程程V(1)=u*g(1)和和V(2)=u*g(2)得到得到v舉例：舉例：圖圖6.1的的(2,1,2)卷積碼的編碼方程為卷積碼的編碼方程為v另外，編碼方程中每一項的系數(shù)，還可以表示另外，編碼方程中每一項的系數(shù)，還可以表示輸入、移位寄存器和輸出之間的連接

9、關(guān)系，輸入、移位寄存器和輸出之間的連接關(guān)系，1表表示有連接，示有連接，0表示沒有連接表示沒有連接 221202111101,., ,.,mmgggggggg 110111 212122211lllllllllllluuuVVuuVuuuV，v(2,1, m)卷積碼卷積碼的生成矩陣：將生成序列的生成矩陣：將生成序列g(shù)(1)和和g(2)交織后形成的半無限矩陣交織后形成的半無限矩陣v舉例：舉例：圖圖6.1的的(2,1,2)卷積碼沖激響應為卷積碼沖激響應為g(1)=(111), g(2)=(101)，該碼，該碼的生成矩陣為的生成矩陣為 .0000.00.00.0000.2121112212201021

10、21112111201021221221112010mmmmmmmmmmmmggggggggggggggggggggggggG.1101110000.11011100.110111Gv以以u=(u1,u2,u3,)為輸入為輸入, G為生成矩陣的為生成矩陣的(2,1,m)的卷積碼的碼字為的卷積碼的碼字為V=uGv舉例：舉例：圖圖6.1的的(2,1,2)卷積碼，若卷積碼，若u=(1011), 則則碼碼字為字為v=(11,10,00,01,01,11)1101111101111101111101111011uGV+D0D1+V(1)V(2)u圖圖6.2 二元二元(2,1,3)(2,1,3)卷積碼的編

11、碼器的電路圖卷積碼的編碼器的電路圖D2v該編碼器的沖激響應就是通過令該編碼器的沖激響應就是通過令u=(100)所得所得到的兩個輸出序列到的兩個輸出序列v因為編碼器有因為編碼器有m個存儲單元，所以沖激響應個存儲單元，所以沖激響應( (生生成序列成序列) )至多持續(xù)至多持續(xù)m+1個時間單元，且可以寫成個時間單元，且可以寫成v其中上標表示第幾個輸出端其中上標表示第幾個輸出端v圖圖6.2的的(2,1,3)卷積碼的沖激響應為卷積碼的沖激響應為g(1)=(1011), g(2)=(1111)v另外，沖激響應向量還可以表示輸入、移位寄另外，沖激響應向量還可以表示輸入、移位寄存器和輸出之間的連接關(guān)系，存器和輸

12、出之間的連接關(guān)系，1表示有連接，表示有連接，0表示沒有連接表示沒有連接 221202111101,., ,.,mmggggggggv信息序列信息序列u=(u1,u2,u3,)每次進入編碼器每次進入編碼器1比特比特v編碼器的兩個輸出序列編碼器的兩個輸出序列v可以通過輸入序列可以通過輸入序列u和編碼器的兩個沖激響應和編碼器的兩個沖激響應作卷積運算而得到作卷積運算而得到v若若u=(10111), 圖圖6.2的的(2,1,3)卷積碼的沖激響應卷積碼的沖激響應為為g(1)=(1011), g(2)=(1111)，則該卷積碼的輸出序則該卷積碼的輸出序列為列為V(1)=u*g(1)=(10000001),

13、V(2)=u*g(2)=(11011101) ., .,22212021211101vvvvvvvvv輸出序列分別為輸出序列分別為的的(2,1,m)的卷積碼的碼字，為的卷積碼的碼字，為V(1)和和V(2)的交錯的交錯v即即v舉例：舉例：圖圖6.2的的(2,1,3)卷積碼，若卷積碼，若u=(10111), 沖激沖激響應為響應為g(1)=(1011), g(2)=(1111)，該卷積碼的輸出該卷積碼的輸出序列為序列為V(1)=u*g(1)=(10000001), V(2)=u*g(2)=(11011101)，得到的碼字為，得到的碼字為v=(11,01,00,01,01,01,00,11) ., .

14、,22212021211101vvvvvvvv ,.),(221221112010vvvvvvv v以以u=(u1,u2,u3,)為輸入為輸入,以以為生成序列的為生成序列的(2,1,m)卷積碼的輸出序列分別由方卷積碼的輸出序列分別由方程程V(1)=u*g(1)和和V(2)=u*g(2)得到得到v舉例：舉例：圖圖6.2的的(2,1,3)卷積碼的編碼方程為卷積碼的編碼方程為v另外，編碼方程中每一項的系數(shù)，還可以表示另外，編碼方程中每一項的系數(shù)，還可以表示輸入、移位寄存器和輸出之間的連接關(guān)系，輸入、移位寄存器和輸出之間的連接關(guān)系，1表表示有連接，示有連接，0表示沒有連接表示沒有連接 22120211

15、1101,., ,.,mmgggggggg 3212321llllllllluuuuVuuuVv(2,1, m)卷積碼卷積碼的生成矩陣：將生成序列的生成矩陣：將生成序列g(shù)(1)和和g(2)交織后形成的半無限矩陣交織后形成的半無限矩陣v舉例：舉例：圖圖6.2的的(2,1,3)卷積碼沖激響應為卷積碼沖激響應為g(1)=(1011), g(2)=(1111)，該碼，該碼的生成矩陣為的生成矩陣為 .0000.00.00.0000.212111221220102121112111201021221221112010mmmmmmmmmmmmggggggggggggggggggggggggG.1111101

16、10000.1111101100.11111011Gv以以u=(u1,u2,u3,)為輸入為輸入, G為生成矩陣的為生成矩陣的(2,1,m)的卷積碼的碼字為的卷積碼的碼字為V=uGv舉例：舉例：圖圖6.2的的(2,1,3)卷積碼，若卷積碼，若u=(10111), 則則碼碼字為字為v=(11,01,00,01,01,01,00,11).1111101100000000.11111011000000.111110110000.1111101100.1111101110111uGV+D0+V(1)V(2)u圖圖6.3 二元二元(3,2,1)(3,2,1)卷積碼的編碼器的電路圖卷積碼的編碼器的電路圖+

17、D0V(3)Vv該編碼器有該編碼器有2個輸入，個輸入，3個輸出，主要由個輸出，主要由m=1級移級移位寄存器，位寄存器，n=3個模個模2加法器組成加法器組成v對于一般的對于一般的(3,2,m)卷積碼，由于卷積碼，由于k=2，即每次有，即每次有2比特進入編碼器，所以輸入序列比特進入編碼器，所以輸入序列u可以寫成可以寫成v或分開寫成或分開寫成2 2個序列個序列 ,.,221221112010uuuuuuu ,.,.,22212021211101uuuuuuuuv令令u(1)=(100), 得到得到3個輸出序列個輸出序列(長度均為長度均為m+1)v再令再令u(2)=(100), 又得到又得到3個輸出序

18、列個輸出序列v則稱下面的序列為則稱下面的序列為(3,2,m)卷積碼的生成序列卷積碼的生成序列 313123113013121212211201211111211110111,.,., ,.,mmmggggggggggggggg 323223123023222222212202221212211210212,.,., ,.,mmmggggggggggggggg 32121, 210,j,i,.,g,g,gggjimjijijijiv舉例：舉例：圖圖6.3的的(3,2,1)卷積碼的生成序列為卷積碼的生成序列為 11,.,01,., 11,.,3131231130131212122112012111

19、11211110111mmmggggggggggggggg 10,.,10,., 01,.,323223123023222222212202221212211210212mmmgggggggggggggggv輸出序列為輸出序列為的的(3,2,m)的卷積碼的碼字，為的卷積碼的碼字，為v舉例：舉例：圖圖6.3的的(3,2,1)卷積碼，若卷積碼，若u(1)=(101), u(2)=(110)v得到的碼字為得到的碼字為v=(110, 000, 001, 111) .,., .,323130322212021211101vvvvvvvvvvvv ,.),(322212312111302010vvvvvv

20、vvvv 001111001111101101110110011100010110110011011001011011110111011101322311322221121221111guguVguguVguguVv圖圖6.3的的(3,2,1)卷積碼的編碼方程為卷積碼的編碼方程為v另外，編碼方程中每一項的系數(shù)，還可以表示另外，編碼方程中每一項的系數(shù)，還可以表示輸入、移位寄存器和輸出之間的連接關(guān)系，輸入、移位寄存器和輸出之間的連接關(guān)系，1表表示有連接，示有連接，0表示沒有連接表示沒有連接 112131122211111llllllllllluuuVuuVuuuVv(3,2, m)卷積碼卷積碼的生

21、成矩陣：生成序列為的生成矩陣：生成序列為v舉例：舉例：圖圖6.3的的(3,2,1)的生成矩陣為的生成矩陣為 .322212312212112320220120312111311211111310210110322212321221121320220120312111211211111310210110mmmmmmmmmmmmmmmmmmggggggggggggggggggggggggggggggggggggG010111110100011110111101001110111101G 3 , 2 , 1, 2 , 1,jigjiv以以u為輸入為輸入, G為生成矩陣的為生成矩陣的(3,2,m)的卷

22、積碼的碼的卷積碼的碼字為字為V=uGv舉例：舉例：圖圖6.3的的(3,2,1)卷積碼，若卷積碼，若u(1)=(101), u(2)=(110),即即u=(11,01,10),則則碼字為碼字為V=uG=(110,000,001,111)111,001,000,110(01011111010001111011110100111011110110,01,11 uGVv(3,2, m)卷積碼卷積碼的生成矩陣為的生成矩陣為v其中每個其中每個GL都是一個都是一個kn階子陣階子陣.120110210mmmmmmGGGGGGGGGGGGG nklklklnlllnlllLgggggggggG.21222121

23、2111v對于對于(n,k,m)卷積碼，圖卷積碼，圖6.1-6.3這幾個例子充分表這幾個例子充分表明，當明，當k1時，編碼器及用來描述它的符號都比時，編碼器及用來描述它的符號都比較復雜，并且該編碼器所含的較復雜，并且該編碼器所含的k個移位寄存器的個移位寄存器的長度未必相同長度未必相同v例如：例如：圖圖6.3中，中，m=1v存儲級數(shù)：存儲級數(shù)：若若ki是第是第i個移位寄存器的長度，則稱個移位寄存器的長度，則稱所有所有k個移位寄存器中的最大長度為存儲級數(shù)，個移位寄存器中的最大長度為存儲級數(shù)，即編碼器的存儲級數(shù)即編碼器的存儲級數(shù)m定義為定義為ikikm1maxv對于對于(n,k,m)卷積碼，編碼器中

24、每個信息位要保持卷積碼，編碼器中每個信息位要保持m+1時間個單位，每個時間單位都可以影響編碼時間個單位，每個時間單位都可以影響編碼器輸出中的任何一個，這由移位寄存器的連接決器輸出中的任何一個，這由移位寄存器的連接決定定v約束長度：約束長度：對于對于(n,k,m)卷積碼，編碼器的約束長卷積碼，編碼器的約束長度定義為度定義為v約束長度可以解釋成約束長度可以解釋成1比特信息對編碼器輸出可比特信息對編碼器輸出可以造成影響的最大數(shù)目以造成影響的最大數(shù)目v例如：例如：圖圖6.1中中(2,1,2)卷積碼卷積碼nA=6，圖，圖6.2中中(2,1,3)卷積碼卷積碼nA=8，圖，圖6.3中中(3,2,1)卷積碼卷

25、積碼nA=61mnnAv對于對于(n,k,m)卷積碼，其碼速度卷積碼，其碼速度r=k/nv注意：注意：對于對于(n,k,m)卷積碼，信息序列為有限長卷積碼，信息序列為有限長kL時，對應的碼字長度為時，對應的碼字長度為n(L+m)v例如：例如：圖圖6.1中中(2,1,2)卷積碼，若卷積碼，若L=4，信息序列，信息序列長度為長度為4，則碼字長度為，則碼字長度為12；圖；圖6.2中中(2,1,3)卷積卷積碼，若碼，若L=5，信息序列長度為，信息序列長度為5，則碼字長度為，則碼字長度為16；圖；圖6.3中中(3,2,1)卷積碼，若卷積碼，若L=3，信息序列長，信息序列長度為度為3，則碼字長度為，則碼字

26、長度為12v其中其中nm個輸出是為了使得編碼器的存儲器最后個輸出是為了使得編碼器的存儲器最后全部能夠清零全部能夠清零v若把卷積碼看成是由生成矩陣得到的線性分組碼，若把卷積碼看成是由生成矩陣得到的線性分組碼，則其碼速度則其碼速度r= kL/n(L+m)v注意：注意：當當L遠大于遠大于m的時候，的時候， L/(L+m)近似等于近似等于1，此時，卷積碼和分組碼的速率就近似相等此時，卷積碼和分組碼的速率就近似相等v速率損失系數(shù)：速率損失系數(shù)：當當L較小的時候，信息傳輸?shù)挠休^小的時候，信息傳輸?shù)挠行?，即效率，即kL/n(L+m)將比碼速率降低一個分數(shù)將比碼速率降低一個分數(shù)v稱稱m/(L+m)為速率損失

27、系數(shù)。為了使得速率損失為速率損失系數(shù)。為了使得速率損失系數(shù)盡量小，一般假定系數(shù)盡量小，一般假定L遠大于遠大于mmLmnkmLnkLnk/v例例1：圖圖6.2中中(2,1,3)卷積碼，若卷積碼，若L=5，則速率損失，則速率損失系數(shù)為系數(shù)為m/(L+m)=3/(5+3)=3/8=37.5%v例例2：圖圖6.2中中(2,1,3)卷積碼，若卷積碼，若L=1000，則速率，則速率損失系數(shù)為損失系數(shù)為m/(L+m)=3/(1000+3)=3/10030.299%v在任一線性系統(tǒng)中，涉及卷積的時域運算，都可在任一線性系統(tǒng)中，涉及卷積的時域運算，都可以轉(zhuǎn)換成多項式乘法的變換域運算來實現(xiàn)以轉(zhuǎn)換成多項式乘法的變換

28、域運算來實現(xiàn)v由于卷積碼是線性系統(tǒng)，編碼方程中的每一序列由于卷積碼是線性系統(tǒng)，編碼方程中的每一序列都可以用相應的多項式來表示，卷積運算可以用都可以用相應的多項式來表示，卷積運算可以用多項式乘法運算來替代多項式乘法運算來替代v在二元序列的多項式表示中，序列本身可以用多在二元序列的多項式表示中，序列本身可以用多項式的系數(shù)來表示，序列項式的系數(shù)來表示，序列a=(a0a1)被表示成多被表示成多項式項式 0iiixaxAv信息序列：信息序列：u表示成表示成u(x)v生成多項式：生成多項式：g(1)表示成表示成g(1)(x), g(2)表示成表示成g(2)(x)v輸出序列：輸出序列：V(1)表示成表示成V

29、(1)(x), V(2)表示成表示成V(2)(x)v碼字：碼字：V表示成表示成V(x)v于是于是V(1)(x)=u(x)g(1)(x)，V(2)(x)=u(x)g(2)(x)v碼字碼字V(x)=V(1)(x2)+xV(2)(x2)v例如：例如：圖圖6.1的的(2,1,2)卷積碼卷積碼v信息序列：信息序列：若若u=(1011), 則則u(x)=1+x2+x3v生成多項式：生成多項式：沖激響應為沖激響應為g(1)=(111), g(2)=(101),則則g(1)(x)=1+x+x2, g(2)(x)=1+x2v于是于是, 編碼方程為編碼方程為V(1)(x)=u(x)g(1)(x)=(1+x2+x3)(1+x+x2)=1+x+x5，V(2)(x)=u(x)g(2)(x)=(1+x2+x3)(1+x2)=1+x3+x4+x5v碼字為碼字為V(x)=V(1)(x2)+xV(2)(x2)=1+x+x2+x7+x9+x10+x11v例如：例如：圖圖6.2的的(2,1,3)卷積碼卷積碼v信息序列：信息序列：若若u=(10111), 則則u(x)=1+x2+x3+x4v生成多項式：生成多項式：沖激響應為沖激響應