第6章634几种重要的码

1、HUST - Information and Coding Theory1第第6章章 信道编码信道编码o6.1 信道编码的概念o6.2 线性分组码o6.3 循环码循环码o6.4 卷积码HUST - Information and Coding Theory26.3 6.3 循环码循环码o线性分组码对码的选取做了线性约束，使得计算量变小。o译码算法是一种通用译码算法，效率不高。o循环码是1957年由一个叫Prange的科学家开始研究。o循环码在线性约束的基础上增加了约束条件，是目前研究最为成熟的一类码，大多数有实用价值的纠错码都属于循环码的范畴。HUST - Information and Co

2、ding Theory3定义定义o定义：定义：对于一个（n，k）线性分组码， 若某一码字为 C=c1 ,c2 , . ,cn 该码字向左循环 1 位后为 C(1)=c2 ,c3 , . ,cn ,c1 该码字向左循环 i 位后为 C(i)=ci+1 ,ci+2 , . ,cn ,c1 , . ,ci 直至向左循环 n1 位为 C(n-1)=cn ,cn-1 , . ,c1o若 C(i) , i = 1, 2, . , n1 均为码字，则称这个（n，k）线性分组码为循环码循环码。 o循环码一般也记为（n，k）码，其中 n 为码字的长度， k 为信息位的长度。HUST - Information

3、and Coding Theory4循环码的码多项式循环码的码多项式o循环码的特点是，若循环码的特点是，若 C 是一个码字，那么它的循环移位是一个码字，那么它的循环移位所形成的新序列同样也是一个码字。所形成的新序列同样也是一个码字。o循环码是线性分组码的一个重要子类，它具有完整的代循环码是线性分组码的一个重要子类，它具有完整的代数结构，其编码和译码相对比较简单，易于实现。数结构，其编码和译码相对比较简单，易于实现。 o循环码也是线性分组码，因此可用校验矩阵或生成矩阵循环码也是线性分组码，因此可用校验矩阵或生成矩阵来构成。但由于循环码具有循环移位特性，且是自封闭来构成。但由于循环码具有循环移位特

4、性，且是自封闭的，故采用多项式的方法描述更为方便。的，故采用多项式的方法描述更为方便。 on 长的循环码字长的循环码字 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多项式的次数定义为：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码多项式的模运算和整数的模运算类似：长除法。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循环码的循环特性可由多项式的模运算来表示循环码的循环特性可由多项式的模运算来表示 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是线性循环码，CB是非循环线性分组码，而CC是非线性循环码。oCA的码字可用多项式：0,x2+x,x+1,x2+1表示。n=3o循环码仍是线性码，由循环码构成的线性子空间为循环子空间。将码表示成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) 循环码C(x)中存在唯一的一个非零的、首一的和最低次数为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)的循环移位，矛盾。o码式是码式是

10、g(x)的倍式：的倍式：由循环移位特性知： xi g(x) ，i=1,2n-1-r均是码式。( )( )( )( )( )0)rrgxg xgxg xgxrxx若是另一个最低次r的非零首一码式，则仍为码式。但的次数（因为。21121( )(.)( ) mod1rrrng xx gg xgxxxg xxgxxHUST - Information and Coding Theory12定理一证明（续）定理一证明（续）o由码的线性分组特性： an-1-rg(x)xn-1-r+a1g(x)x+a0g(x)=a(x)g(x) (1) 也是码式。故g(x)的倍式若次数小于n则是码式。o反之：f(x)若是码

11、式，则可表示为： f(x)=a(x)g(x)+r(x)，r(x)的次数小于g(x)的次数，或r(x)=0。 若r(x) 0，则r(x) f(x)a(x)g(x)也是码式，但 r(x)的次数 f(x)是g(x)的倍式。or=n-k证明证明：由码式必是g(x)的倍式及(1)式知a0 ， a1 an-1-r有n-r个，故可组成2n-r个码式，而(n，k)码的码字个数为2k个且码式必是g(x)的倍式=n-r=k。证毕证毕HUST - Information and Coding Theory13生成多项式生成多项式o定义定义：由定理一确定的码式g(x)称为（n，k）循环码的生成多项式。循环码由生成多项

12、式g(x)的倍式组成，表示为： g(x) 是(n,k) 循环码的生成多项式，当且仅当 g(x) 是 xn - -1 的 r = n k 次因式。o证明：必要性证明：必要性 若g(x)是生成多项式，则有： 由循环移位定义得， r(x)是g(x)的循环移位码式，所以 故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定理二证明（续）定理二证明（续）o充分性：充分性： 设n-k=r次g(x)是xn -1的因式，则线性组合： 共有k个多项式。其中： 故c(x)的一次循环c(1)(x)均是g(x)的倍式。同理c(x) 的任意次循环c(i)(x)均是g(x)的倍式。所以，此k个多项式组成（n,k）循环码。证毕证毕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例题例题 构造循环码构造循环码o例题：例题：构造一个（7，3）循环码。o解解：n由于 n7，对 (x7+1) 因式分解得： x7 + 1 = ( x + 1 ) ( x3 + x2 + 1 ) ( x3 + x + 1 ) n由于 k=3，则 n k = 4，因此 ( 7 , 3 ) 循环码的两个可选的生成多项式为：ng1(x) = (x+1) (x3+x2+1)ng2(x) = (x+1) (x3+x+1)HUST - Informatio

15、n and Coding Theory16循环码的生成矩阵循环码的生成矩阵o由于（n，k）循环码共有 2k 个码字，从码组中取出一个前面 k1 位都是 0 的码字，用 g(x) 表示，不难看出 g(x) 的多项式次数为（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) 可以构成生成多项式矩阵生成多项式矩阵为 12( )( )( )( )( )kkxg xxg xG xxg xg xHUST - Information

16、and Coding Theory17生成矩阵生成矩阵Go ( n , k ) 循环码的生成矩阵在 g(x) 确定后可以表示为 G1012101212011.0 . 0( )0. 0( )( )00 .0.krrrrrkrrk ngggggxg xgggggxg xg xggggGHUST - Information and Coding Theory18生成多项式生成多项式 g(x) 与循环码的生成与循环码的生成o由于循环码是线性分组码，因此对于码字C 有 C(x) = m1 m2 . mk G(x) 式中 m1 m2 . mk 为 k 位信息元矢量。 o上式表明，循环码的所有码字可由 g(

17、x) 产生，g(x) 称为循环码的生成多项式。生成多项式。o在 ( n，k ) 循环码中，g(x) 是唯一的一个 ( nk ) 次多项式，且次数最低。o每个码多项式C(x) 都是g(x)的倍式，而每个为g(x) 的倍式且次数小于或等于(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循环码的生成多项式 g(x) 是 xn1 的因式，即

18、 xn1 = h (x)g(x) k 次多项式 h(x) 称为码的校验多项式校验多项式。o设则 g(x) 和 h(x) 的系数满足以下关系 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 由循环码的码式 有式中，,.共 项的系数为 ，另一方面110)0 0(1)kkkknkin ijixxxxh cjnkr 比较这两式中同幂次项系数，由,.项的系数为 ，得到校验方程为：HUST - Information and Coding Theory21循环码的校验矩阵循环码的校验矩阵 H 和生成矩阵和生成矩阵Go校验矩阵可以表示为右边矩阵H， 满足xn+1=h(x)g(x)。o注意到生成矩阵G的行向量为g(x)系数的升幂排列，校验矩阵H的行向量

20、为h(x)系数的降幂排列。如果G为降幂排列，则对应的H为升幂排列。101000000000kkkkhhhhhhhhH01210121011.0 . 00. 000 .0.rrrrrrrggggggggggggggGHUST - Information and Coding Theory22循环码的伴随多项式循环码的伴随多项式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循环码的检纠错循环码的检纠错o根据伴随式的定义，若无错误传输，则 S(x) = 0 ，否则S(x)0，由此可实现循环码的检错检错。 o因为g(x)的次数为nk，e(x)的次数为n1，所以伴随式的最高次数为nk1，那么S(x)共有nk项，故有2n-k种可能的伴随式。若满足2n-k n+1，则循环码具有纠错纠错能力。

22、oBCH 码码是一类重要的循环码，它能够最有效地纠正多个独立错误。BCH 码把生成多项式与码的最小距离和纠错能力联系起来，根据所需要的纠错能力，选取适当的 g(x) ，可以编出非常有效地纠正多个独立错误的 BCH 码。（略） HUST - Information and Coding Theory24例题例题 校验多项式和生成矩阵校验多项式和生成矩阵o例题：例题：对上例的（7 , 3）循环码，求其校验多项式和生成矩阵。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例题例题 循环码的生成循环码的生成o例题：例题：对上例的（7 , 3）循环码，若输入信息码字为 110 ，求其循环码字。o解：解：n信息码字 110 的码式为 m(x) = x2 + x n得循环码式为 c(x)= m(x)g(x) = (x2 + x)(x4 + x2 + x+1)= x6+x5+ x4+xn则其循环码字为 1110010 。 HUST - I

24、nformation and Coding Theory26例题例题 循环码的检错循环码的检错o例题：例题：对上例的（7 , 3）循环码，若接收码字为 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）循环码的许用码字。 HUST - Information and Coding Theory27小

25、结o循环码为线性分组码；卷积码为线性非分组码。o循环码的特点是具有循环移位特性，因此可以用多项式法描述。n本节介绍了循环码利用多项式的编译码方法，包括生成多项式的构造，利用生成多项式生成码字，校验多项式及其与生成多项式的关系、利用伴随多项式译码等。n讨论了多项式描述与一般线性分组码的矩阵描述（生成矩阵、校验矩阵、伴随式）间的关系。HUST - Information and Coding Theory28第第6章章 信道编码信道编码o6.1 信道编码的概念o6.2 线性分组码o6.3 循环码o6.4 卷积码卷积码HUST - Information and Coding Theory296.4

26、 6.4 卷积码卷积码o在分组码中，任何特定的时间单位内编码器所产生的在分组码中，任何特定的时间单位内编码器所产生的 n个码元的码组，仅取决于该时间单位内个码元的码组，仅取决于该时间单位内 k 个消息位。个消息位。o存在着另一种码，由编码器在特定的时间内所产生的码存在着另一种码，由编码器在特定的时间内所产生的码元不但取决于这个特定的时间段内进入的信息组，而且元不但取决于这个特定的时间段内进入的信息组，而且也与前面的时间段内的信息组有关，这种码称为也与前面的时间段内的信息组有关，这种码称为。o卷积码的编码可用移位寄存器来完成。卷积码的编码可用移位寄存器来完成。o卷积码与分组码相似，具有纠正随机错

27、误、突发错误或卷积码与分组码相似，具有纠正随机错误、突发错误或同时纠正这两类错误的能力。对于许多实际的误差控制，同时纠正这两类错误的能力。对于许多实际的误差控制，卷积码的性能优于分组码。卷积码的性能优于分组码。 HUST - Information and Coding Theory30卷积码的概念卷积码的概念o定义：定义：对于任一给定时刻，编码器的一个输出码字不仅与该时刻的当前输入码字有关，还与编码器的移位寄存器中存贮的前面m个输入信息码字有关。因此。n其中n为输出的每个码字的位数nk为输入的每个信息码字的位数nm为移位寄存器中存贮的信息码字个数。 o定义 m 为卷积码的记忆长度，而为卷积码

28、的记忆长度，而 ( m + 1 ) 为卷积码的码字约束长为卷积码的码字约束长度度，相应的比特（码元）约束长度比特（码元）约束长度为 ( m + 1 ) n。o对L段输入的信息码进行编码，由于初始寄存器为全0，结束时也要额外输入m段无效的全0码字，故共产生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 个移位寄存器构成。o编码器每并行输入一个2 位信息码字mi = mi(1), mi(2)， 则并行输出一个 3 位卷积码码字 ci = ci(1), ci(2) , ci(3) = mi(1), mi(2) , pi 其中 pi 为监督元，有 pi = mi(1) + mi(2) + mi-1(1) + mi-1(2) o可见，卷积码当前输出的码字的监督元不仅与当前输入可见，卷积码当前输出的码字的监督元不仅与当前输入的信息元有关，还与前次输入的的信息元有关，还与前次输入的 2 个信息码元

30、有关。个信息码元有关。 HUST - Information and Coding Theory32卷积码的校验关系式卷积码的校验关系式o下面以下面以（3，1，3）卷积码为例，讨论卷积码的生成矩阵卷积码为例，讨论卷积码的生成矩阵和校验矩阵。和校验矩阵。o把给定的信息序列 (m1 , m2 , m3 , . ) 进行分组，使每个信息组只包含一个信息位。o输出的每组码字由三位组成，其中有一个信息位和两个校验位，则输出的码序列为 ( m1 p11 p12 , m2 p21 p22 , m3 p31 p32 , . )o设校验位与信息位满足以下校验关系：校验关系： pi1 = mi + mi-1 +

31、mi-3 ; pi2 = mi + mi-1 + mi-2 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改写校验关系式改写校验关系式 pi1 = mi + mi-1 + mi-3 pi2 = mi + mi-1 + mi-2o可以得到可以得到 m 和和 C 满足以下关系满足以下关系 111212123231234134234mmmmmmmmmmmmmmmmmmmmmTCHUST - Information and Coding

33、 Theory35生成矩阵生成矩阵 G（续）续）o改写的校验关系式若写成矩阵形式，则得到改写的校验关系式若写成矩阵形式，则得到 m 和和 C 间的间的矩阵关系为矩阵关系为 n式中的矩阵 G 称为卷积码的生成矩阵生成矩阵。 000000000000000000000000000000011110110111100000000000111110110111101111111CmGmHUST - Information and Coding Theory36卷积码的描述方法：卷积码的描述方法：o卷积码的描述方法有两类： 1)解析法：包括离散卷积法、生成矩阵法、码多项式法等，多用于编码。 2)图形法：

34、包括状态图、树图、栅格图等，常用于译码，特别是网格图。o特点：n用码多项式法表示卷积码编码器的生成多项式最为方便；n栅格图对于分析卷积码的译码算法十分有用；n状态图表明卷积码编码器是一种有限状态的马尔科夫过程。HUST - Information and Coding Theory37离散卷积法离散卷积法o设在l时段，输入的信息码组为：o输出的卷积码组为：o移位寄存器中存有前m个时段输入的m个信息码组。o由于v(l)与当前时段及此前m 个时段的输入码组呈线性关系。若以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)为线性关系，类似线性分组中C=mG。可表示为：011( )( )( ).( )ku lu l u lul011( )( ) ( ).( )nv lv l v lvlHUST - Information and Coding Theory38离散卷积法（续）离散卷积法（续） 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生成矩阵描述法（续）生成矩阵描述法（续）o若将输入的信息码字序列表示为如下的半无限矩阵：u=u(0), u(1) , u(m) , u(l)o输出卷积码字也表示为如下的半无限矩阵： v=v(0),v(1), ,v(m), ,v(l)o则生成矩阵与信息码的关系可表示为： 其中：为卷积码的卷积码的生成矩阵。生成矩阵。vuGGHUST - Information and Coding Theory41生成矩阵描述法（续）生成矩阵描述法（续）o为一个半无

38、限矩阵，特点：每一个k行都是前一k行右移n列的结果。故中的第一个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生成矩阵描述法（续）生成矩阵描述法（续）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位输出产生作用这种影响可用如下构造的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)非系统卷积码如图所示：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系统码的生成矩阵形式系统码的生成矩阵形式o以上（3，1，3）卷积码是系统码系统码，其码字的第一位总是信息码字。其生成矩阵可以写成下列形式 n式中 I 为 kk 11 阶单位阵n0为 kk 11 阶全 0 方阵，nPi为 k （nk） 12 阶矩阵，有o生成矩阵具有如上形式时生成的卷积码为系统码，一般的表示为。生成矩阵具有如上形式时生成的卷积码为系统码，一般的表示

42、为。 1234P =11,P =11P =01,P =104123412312312P0IIIPPPPPPPPP0000000G00PIPP000001, 2,.,()kknhhknhGI PGPhmPPknk其 中，均 为矩 阵 。HUST - Information and Coding Theory46由生成矩阵产生码序列由生成矩阵产生码序列o已知生成矩阵，可以产生所有卷积码字。o对以上（3，1，3）码，若输入信息序列为（0 1 0 0 1 0 1 0 1 1 ），则对应的码字序列为 o对于所生成的码序列，每 3 个数字组成一个码字，其中包括一个信息位和两个校验位。 1110110010

43、10000000111011001010000000111011001000111011000000000111011000000000000111CmGmHUST - Information and Coding Theory47基本一致校验矩阵基本一致校验矩阵o（3，1，3）卷积码的校验关系式可以表示为卷积码的校验关系式可以表示为 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 ) 则则 校验校验 关系式可关系式可 写成矩阵写成矩阵 形式：形式： 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由校验关系式展开由校验关系式展开 得如下关系式得如下关系式 1111121221122212332134412344224551345523321000000000.0.mpmpmmpmmpmmmpmmmpmmmpmmmmmppmmmpHUST - Information and Coding Theory49一致校验矩阵（续）一致校验矩阵（续）o校验关系式的展开式写成矩阵形式为校验关系式的展开式写成矩阵形式为o系数矩阵为 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 有一定的关系，即 G HT0 。对于系统码，由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卷积码的多项式描述法（续）卷积码的多项式描述法（续）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卷积码的多项式描述法（续）卷积码的多项式描述法（续）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)非系统卷积码中， G(x)1+x+x2 1+x2HUST - Information and Coding Theory54卷积码的状态转移图描述法卷积码的状态转移图描述法o卷积码和分组码的主要区别在于卷积码的编码要存储m段消息，这些消息随新的输入而改变，并影响当前输出因此可将这些存储数据作为描述编码器变化的内部状态o对二元(n,k,

51、m)卷积码，存储器（移位寄存器）共有M=km个单元，即共有2M个不同的状态，记为：ol时刻的状态用状态矢量表示：o下一时刻的状态取决于当前状态和当前输入u(l)，其关系成为状态转移方程状态转移方程：0121, . . . ,MSSS121( )( ),( ),.,( ),( )MMlllll( )(1)ll或用表示）( , )u HUST - Information and Coding Theory55卷积码的状态转移图描述法卷积码的状态转移图描述法( (续）续）o当前时刻的输出v(l)取决于当前时刻的输入u(l)和当前状态，其关系称为输出方程：输出方程：o卷积码有2M个可能状态，在某一时刻

52、同时输入一段k位信息码，有2k个可能取值，故每一时刻的状态转移只能有个可能o状态图有两种:开放型和闭合型.o如(2,1,2)非系统卷积码：状态向量 ，共有S0,S1,S2,S3四种状态，其状态变化如下： ( , )vu 21() HUST - Information and Coding Theory56卷积码的状态转移图描述法卷积码的状态转移图描述法( (续）续）(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)码状态转移图（闭合型）HUST - Information and Coding Theory57卷积码的状态转移图描述法卷积码的状态转移图描述法( (续）续）S0S3S2S10S1S2S3S(00/0,11/1)(10/0,01/1)(11/0,00/1)(01/0,10/1)(2,1,2)码状态转移图（开放型）11122122uvuvu状态转移方程为输出方程：HUST - Information and Coding Theory58栅格图（网格图、篱笆图）栅格图（网格图、篱笆图）o闭合型的状态转移图直接反映了编码器在任一时刻的工作状态；而开放型的状态转移图则更适合描述特定输