第四章卷积码的编码 u uR) (2 3) 图43(4,3,3)非系统前馈卷积编码器 通常，一个存储器阶数为m的(n,k,v)前馈编码器，其生成矩阵可写为： G。G1G2… G= G。G1…GmGm (4.22) G0… Gm-2 Gm- Gm 其中G,是一个k×n的子矩阵，表示为： gp g 8%-7 G1= g g … 8 (4.23) 89 ε用 … g 仍需要注意的是：生成矩阵G中的k行（一组）都与前k行（一组）相同，只是向右 移n位。对于一个信息序列u=(,u,）=(2.…,4"42…4,）,码字 v=uG=(6p"v哈a-,y0y"ym-,…）。 码字v是生成矩阵G的线性组合，因此(n,k,v)是一个线性码。 在线性系统中，时域中的卷积可用更方便的多项式乘法来代替。这样编码方程中每个序 列都可以用一个对应的多项式来代替，例如对一个(2,1，v)编码器，编码方程变为： v(D)=u(D)g(D) (4.24) v(D)=u(D)g(D) 其中 u(D)=4+4D+4D2+… (4.25a) 是信息序列。 6 Copyright by周武旸
第四章 卷积码的编码 6 Copyright by 周武旸 (0) v (1) v (1) u (2) u (2) v (3) u (3) v 图 4.3 （4，3，3）非系统前馈卷积编码器 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 通常，一个存储器阶数为 m 的（n，k，v）前馈编码器，其生成矩阵可写为： 01 2 01 1 0 21 m m m m mm − − − = GGG G GG G G G G GGG （4.22） 其中Gl 是一个 k×n 的子矩阵，表示为： (0) (1) ( 1) 1, 1, 1, (0) (1) ( 1) 2, 2, 2, (0) (1) ( 1) ,, , n ll l n ll l l n kl kl k l gg g gg g gg g − − − = G （4.23） 仍需要注意的是：生成矩阵 G 中的 k 行（一组）都与前 k 行（一组）相同，只是向右 移 n 位。对于一个信息序列 (1) (2) ( ) (1) (2) ( ) 01 00 0 11 1 (,,)( , ,) k k u uu = = uu u uu u ，码字 (0) (1) ( 1) (0) (1) ( 1) 00 0 11 1 ( , ,) n n vv v vv v − − v uG = = 。 码字 v 是生成矩阵 G 的线性组合，因此（n，k，v）是一个线性码。 在线性系统中，时域中的卷积可用更方便的多项式乘法来代替。这样编码方程中每个序 列都可以用一个对应的多项式来代替，例如对一个（2，1，v）编码器，编码方程变为： (0) (0) (1) (1) () () () () () () D DD D DD = = v ug v ug （4.24） 其中 2 01 2 u( ) D u uD uD =+ + + （4.25a） 是信息序列
第四章卷积码的编码 v0(D)=0+0D+D2+… (4.25b) v(D)=喝+D+0D2+ 是编码后的序列。 g(D)=go)+gD+...+gD" (4.25c) g(D)=g6+g"D+…+g"Dm 是生成多项式。 这样码字可写为： V(D)=[v(D),v"(D)] (4.26a) 或经过复用后，写为： v(D)=v0(D2)+Dv(D2) (4.26b) D可看作为一个时延算子，D的指数表示相对于序列中的初始bit延时了多少时间单元。 例如图4.1所示的(2,1,3)编码器，生成多项式g(D)=1+D2+D3及 g"(D)=1+D+D2+D3,对信息序列u(D)=1+D2+D3+D4,编码方程为： v0(D)=(1+D2+D3+D4)1+D2+D3)=1+D (4.27) v(D)=(1+D2+D3+D4)1+D+D2+D3)=1+D+D3+D4+D+D7 码字可写为： V(D)=[1+D,1+D+D+D+D+D] (4.28a) 或 V(D)=1+D+D3+D'+D+D'+D4+D5 (4.28b) 注意：生成多项式的最低阶项（常数项）对应于移位寄存器连接的最左端，最高阶项对应于 移位寄存器连接的最右端。例如图4.1中，从移位寄存器到输出v0)的连接是g,=(1011), 对应的生成多项式为g(D)=1+D+D。 在(，1，v)编码器中，由于移位寄存器的最右端必须连接到至少一个输出上，因此 至少有一个生成多项式的阶数必然等于移位寄存器的长度m,即 m=max degg((D) (4.29) 05jsn-1 在k>1的(n,k,v)编码器中，对于每个输入（共有k个输入），都有n个生成多项式。 每一组n个生成多项式表示着从移位寄存器到n个输出的连接序列，因此，有 y-max[degg(D)],l≤i≤k (4.30) 其中g”(D)是第个输入到第j个输出的生成多项式。 7 Copyright by周武旸
第四章 卷积码的编码 7 Copyright by 周武旸 (0) (0) (0) (0) 2 01 2 (1) (1) (1) (1) 2 01 2 ( ) ( ) D v vDvD D v vD vD =+ + + =+ + + v v （4.25b） 是编码后的序列。 (0) (0) (0) (0) 0 1 (1) (1) (1) (1) 0 1 ( ) ( ) m m m m D g gD gD D g gD gD = + ++ = + ++ g g （4.25c） 是生成多项式。 这样码字可写为： (0) (1) ( ) ( ), ( ) D DD = V vv （4.26a） 或经过复用后，写为： (0) 2 (1) 2 vv v () ( ) ( ) D DDD = + （4.26b） D 可看作为一个时延算子，D 的指数表示相对于序列中的初始 bit 延时了多少时间单元。 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 例如图 4.1 所示的（ 2 ， 1 ， 3 ）编码器，生成多项式 (0) 2 3 g ()1 D DD =+ + 及 (1) 2 3 g ()1 D DD D =+ + + ，对信息序列 234 u()1 D DDD =+ + + ，编码方程为： (0) 234 23 7 (1) 234 23 3457 ( ) (1 )(1 ) 1 ( ) (1 )(1 ) 1 D DDD DD D D D D D DD D DD D D D = + + + + + =+ = + + + + + + =+ + + + + v v （4.27） 码字可写为： 7 3457 ( ) 1 ,1 D D DD D D D =+ ++ + + + V （4.28a） 或 3 7 9 11 14 15 v()1 D DD D D D D D =+ + + + + + + （4.28b） ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 注意：生成多项式的最低阶项（常数项）对应于移位寄存器连接的最左端，最高阶项对应于 移位寄存器连接的最右端。例如图 4.1 中，从移位寄存器到输出 (0) v 的连接是 (0) g = (1011)， 对应的生成多项式为 (0) 2 3 g ()1 D DD =+ + 。 在（n，1，v）编码器中，由于移位寄存器的最右端必须连接到至少一个输出上，因此 至少有一个生成多项式的阶数必然等于移位寄存器的长度 m，即 ( ) 0 1 max deg ( ) j j n m D ≤≤− = g （4.29） 在 k>1 的（n，k，v）编码器中，对于每个输入（共有 k 个输入），都有 n 个生成多项式。 每一组 n 个生成多项式表示着从移位寄存器到 n 个输出的连接序列，因此，有 ( ) 0 1 max deg ( ) , 1 j i i j n v D ik ≤≤− = ≤ ≤ g （4.30） 其中 ( ) ( ) j gi D 是第 i 个输入到第 j 个输出的生成多项式
第四章卷积码的编码 由于编码器是一个线性系统，Ⅱ(D)表示第i个输入序列，v(D)表示第j个输出序 列，生成多项式g(D)可解释为输入i到输出的转移函数。对于有k个输入、n个输出的 线性系统，共有kn个转移函数，可用k×n的生成矩阵表示： g(D)g(D)…ga-(D) … G(D)= g(D)g(D) g-(D) (4.31) g(D)g(D)…g-(D)」 使用生成矩阵，(n,k,v)前馈编码器的编码方程可写为： V(D)-U(D)G(D) (4.32) 其中U(D)u(D),u2(D),…u(D)]是k--tuple 输入序列， V(D)兰[vo(D),v(D),y-(D)]是n--tuple输出序列（码字），复用后，码字可表示 为： v(D)=vo(D")+Dv四(D")+…+D-vm-(D) (4.33) 对于图4.2的(3,2,2)编码器 (0 ⊕D v(D g=(1)g"=(0)g2-11) g=(0)g=10)g2=10) v2) G(D)-D11 1+DD 1+D (4.34) 对于输入序列u(D)=1+D2和u2(D)=1+D,码字为： V(D)=[v(D),v"(D),v2(D)] -+2”1+ (4.35a) =1+D3,1+D3,D2+D] 也可写为： Copyright by周武旸
第四章 卷积码的编码 8 Copyright by 周武旸 由于编码器是一个线性系统， ( ) ( ) i u D 表示第 i 个输入序列， ( ) ( ) j v D 表示第 j 个输出序 列，生成多项式 ( ) ( ) j gi D 可解释为输入 i 到输出 j 的转移函数。对于有 k 个输入、n 个输出的 线性系统，共有 kn 个转移函数，可用 k×n 的生成矩阵表示： (0) (1) ( 1) 11 1 (0) (1) ( 1) 22 2 (0) (1) ( 1) () () () () () () ( ) () () () n n n kk k DD D DD D D DD D − − − = gg g gg g G gg g （4.31） 使用生成矩阵，（n，k，v）前馈编码器的编码方程可写为： V(D)=U(D)G(D) （4.32） 其 中 (1) (2) ( ) ( ) ( ), ( ), ( ) k D DD D U uu u 是 k-tuple 输入序列， (0) (1) ( 1) ( ) ( ), ( ), ( ) n D DD D − V vv v 是 n-tuple 输出序列（码字），复用后，码字可表示 为： (0) (1) 1 ( 1) () ( ) ( ) ( ) n n nn n D DDD D D − − vv v v = + ++ （4.33） ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 对于图 4.2 的（3，2，2）编码器 (0) v (1) v (1) u (2) u (2) v 1 1 ( ) 1 1 DD D D D + + = G （4.34） 对于输入序列 (1) 2 u ()1 D D = + 和 (2) u ()1 D D = + ，码字为： (0) (1) (2) 2 3 3 23 ( ) ( ), ( ), ( ) 1 1 1 ,1 1 1 1 ,1 , D DDD DD D D D D D D DD = + + =+ + =+ + + V vvv （4.35a） 也可写为： (0) (1) (2) 1 11 (0) (1) (2) 2 22 (1 1) (0 1) (1 1) (0 1) (1 0) (1 0) = = = = = = ggg ggg
第四章卷积码的编码 V(D)=1+D+D8+D°+D0+D川 (4.35b) 我们也可以将式(431)、(4.32)、(433)的复用码字v(D)写成： v(D)=(Dg(D) (4.36) 其中 g,(D)=g(D)+Dg"(D)+…+D-g"-(D),1≤i≤k (4.37) 是第i个输入到输出的复合生成多项式。 例如图4.1所示的(2,1,3)编码器，复合生成多项式为： g(D)=g(D2)+Dg(D2) (4.38) =1+D+D3+D4+D3+D+D7 当输入信息多项式u(D)=1+D+D3+D4时，码字为： v(D)=u(D2)g(D) =(1+D+D+D8)1+D+D3+D4+D5+D+D) (4.39) =1+D+D3+D7+D9+D11+D14+D15 卷积编码器的一个重要子类是系统编码器，在一个系统编码器中，前k个输出序列（称 为系统输出序列)正好是k个输入序列的拷贝，即： vi-)=u0,i=1,2,…,k (4.40) 生成器序列满足： gu= (1,if j=i-1 i=1,2,…k (4.41) 0,fj≠i-1 在系统前馈编码器中，生成矩阵可表示为： 「1P。0P0P2…0P G= I。0P…0Pm-10Pnm (4.42) IP。…0Pnm-20Pnm-10Pm 其中I是kXk的单位阵，0是kXk的全0阵，P,是k×(n-k)的矩阵，为： 9 Copyright by周武旸
第四章 卷积码的编码 9 Copyright by 周武旸 8 9 10 11 v()1 D DD D D D =+ + + + + （4.35b） ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 我们也可以将式（4.31）、（4.32）、（4.33）的复用码字 v(D)写成： ( ) 1 () ( )() k i n i i D DD = v ug = ∑ （4.36） 其中 (0) (1) 1 ( 1) () ( ) ( ) ( ), 1 n n nn n ii i D D D D D D ik i − − gg g g = + + + ≤ ≤ （4.37） 是第 i 个输入到输出的复合生成多项式。 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 例如图 4.1 所示的（2，1，3）编码器，复合生成多项式为： (0) 2 (1) 2 34567 () ( ) ( ) 1 D DDD DD D D D D = + =+ + + + + + gg g （4.38） 当输入信息多项式 234 u()1 D DDD =+ + + 时，码字为： 2 468 34567 3 7 9 11 14 15 ( ) ( )( ) (1 )(1 ) 1 D DD D D D DD D D D D DD D D D D D = =+ + + ++ + + + + =+ + + + + + + v ug （4.39） ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 卷积编码器的一个重要子类是系统编码器，在一个系统编码器中，前 k 个输出序列（称 为系统输出序列）正好是 k 个输入序列的拷贝，即： ( 1) ( ) , 1,2, , i i i k − v u = = （4.40） 生成器序列满足： ( ) 1, 1 1,2, 0, 1 j i if j i i k if j i = − = = ≠ − g （4.41） 在系统前馈编码器中，生成矩阵可表示为： 012 01 1 0 21 m m m m mm − − − = IP 0P 0P 0P IP 0P 0P 0P G IP 0P 0P 0P （4.42） 其中 I 是 k×k 的单位阵，0 是 k×k 的全 0 阵，Pl是k nk × − ( ) 的矩阵，为：
第四章卷积码的编码 g g 8-7 g P= g g5- (4.43) g g ge 类似地，k×n的生成矩阵变为： 0… 0 g(D) g-(D) 01.. 0 … G(D)= g(D) g-(D) (4.44) : 0 0…1 g(D) … g-(D) 由于前k个输出序列是系统的，即为k个输入序列，它们也被称为输出信息序列，后面 的n一k个输出序列被称为输出校验序列。通常，需要kn个生成多项式来定义(n,k,v) 非系统前馈编码器，需要kX(一k)个生成多项式来定义系统前馈编码器。 对于式(4.42)或(4.44)生成矩阵所示的系统前馈编码器，其对应的系统校验矩阵可 直接表示为： P I 0 P I 吲 0 P" 0 P H= (4.45) P0P0P20…P1 P0P0…P0PI P 0…P0P 0P1 其中I是(n-k)×(n-k)的单位阵，0是(n一k)×(n-k)的全零矩阵，类似地，(n 一k)×n的校验矩阵可表示为： g(D) g (D) … g(D) 10. 0 H(D)= g(D)g(D)…g*(D)01 0 (4.46a) g-(D)g-(D)…g-(D)00 1 其中H(D)的后(n一k)列是(n-k)×(n-k)的单位阵，上式也可写为： h(D)h(D)… h-(D)10…0 h(D)h(D)…h-(D)01… H(D)= 0 (4.46b) ho(D)h"(D)…h(D)00 .…1 其中与第（ⅰ一1）个输出信息序列相联系的第(j一k+1)个校验多项式定义为 h(D)=g(D),j=kk+L,,n-l,i=1,2,,k。为了简化表达，可用h(D),i=1, 2,…n-k,j=0,1,…,k-1来表达。 任何一个有效的码字V(或VD)必须满足校验方程： 10 Copyright by周武肠
第四章 卷积码的编码 10 Copyright by 周武旸 ( ) ( 1) ( 1) 1, 1, 1, ( ) ( 1) ( 1) 2, 2, 2, ( ) ( 1) ( 1) ,, , kk n ll l kk n ll l l kk n kl kl k l gg g gg g gg g + − + − + − = P （4.43） 类似地，k×n 的生成矩阵变为： ( ) ( 1) 1 1 ( ) ( 1) 2 2 ( ) ( 1) 1 0 0 () () 01 0 () () ( ) 00 1 () () k n k n k n k k D D D D D D D − − − = g g g g G g g （4.44） 由于前 k 个输出序列是系统的，即为 k 个输入序列，它们也被称为输出信息序列，后面 的 n－k 个输出序列被称为输出校验序列。通常，需要 kn 个生成多项式来定义（n，k，v） 非系统前馈编码器，需要 k×(n－k)个生成多项式来定义系统前馈编码器。 对于式（4.42）或（4.44）生成矩阵所示的系统前馈编码器，其对应的系统校验矩阵可 直接表示为： 0 1 0 21 0 12 0 1 10 21 0 T T T TT T TT T T mm m T T TT m m T TTT m − − − = P I P 0P I P 0P 0P H P 0P 0P 0 P I P 0P 0 P 0P I P 0 P 0P 0P I （4.45） 其中 I 是（n－k）×（n－k）的单位阵，0 是（n－k）×（n－k）的全零矩阵，类似地，（n －k）×n 的校验矩阵可表示为： ( ) ( ) ( ) 1 2 ( 1) ( 1) ( 1) 1 2 ( 1) ( 1) ( 1) 1 2 () () () 1 0 0 () () ()01 0 ( ) () () () 00 1 kk k k kk k k nn n k DD D DD D D DD D ++ + −− − = gg g gg g H gg g （4.46a） 其中 H(D)的后（n－k）列是（n－k）×（n－k）的单位阵，上式也可写为： (0) (1) ( 1) 11 1 (0) (1) ( 1) 22 2 (0) (1) ( 1) () () ()1 0 0 () () () 01 0 ( ) () () () 00 1 k k k nk nk n k DD D DD D D DD D − − − −− − = hh h hh h H hh h （4.46b） 其中与第（i－1）个输出信息序列相联系的第（j－k＋1）个校验多项式定义为 ( 1) ( ) 1() () i j j k D D i − h g − + = ，j＝k, k+1, …, n-1，i＝1, 2, …, k。为了简化表达，可用 ( ) ( ) j hi D ，i＝1， 2，…,n－k，j＝0，1，…,k－1 来表达。 任何一个有效的码字 v（或 V(D)）必须满足校验方程：