中国科学技术大学：《编码理论》课程教学资源（课件讲义）第四章卷积码.pdf_大学文库

第四章卷积码的编码第四章卷积码卷积码与分组码不同，其编码器具有记忆性，即编码器的当前输出不仅与当前输入有关，还跟以前时刻的输入有关。速率R=kn、存储器阶数为m的卷积编码器可用k个输入、n个输出、输入存储器阶数为m的线性序贯电路实现，即输入在进入编码器后仍会多呆m个时间单元。通常，n和k都是比较小的整数，k<n,信息序列被分成长度为k的分组，码字(codeword) 被分成长度为的分组。当k=1时，信息序列无需分组，处理连续进行。值得注意的是，卷积码不象分组码，较大的最小距离和低错误概率不是通过增加k和实现的，而是通过增加存储器阶数m实现的。我们这一章关注卷积编码过程、卷积编码器如何用状态图表示、如何推导卷积码的重量枚举(weight--enumerating)函数、卷积码的几种距离测量方法。卷积码是1955年由Elias(1923~2001)首次提出的，随后Wozencraft和Reiffen提出了序贯译码方法（对具有较大约束长度的卷积码非常有效）。1963年，Massey提出了一个效率不高、但易于实现的译码方法一一门限译码，这使得卷积码大量应用于卫星和无线信道的数字传输中。 On December 7,2001,the field of information theory lost another of its true giants,Peter Elias, who passed away at his home in Cambridge, Massachusetts,a victim of the mysterious and dreadful ailment,Creutzfeld-Jakob Disease. Peter Elias AJ.Viterbi毕业于麻省理工学院(MT),分别获博士/硕士 /学士学位，是无线通信领域国际权威专家，被称为CDMA 之父。现为美国Qualcomm公司首席科学家，加州大学Los Angeles分校(UCLA)教授，IEEE Fellow(国际电子电气工程师协会会士)，美国总统国家科学和工程委员会成员。 I967年，Viterbi提出了最大似然(ML,Maximum Likelihood)译码算法，易于实现具有较小约束长度的卷积码的软判决译码。Viterbi算法配合序贯译码的软判决，使卷积码在 20世纪70年代广泛应用在深空和卫星通信系统。1974年，Bahl,Cocke,Jelinek以及Raviv (BCJR)对具有不等先验概率信息比特的卷积码，提出了最大后验概率(MAP,maximum a posteriori probability)译码算法。BCJR算法近年来广泛应用到软判决迭代译码方案中，其中信息比特的先验概率在每次迭代时都发生变化。对卷积码描述最详尽的书籍是： R.Johannesson and K.S.Zigangirov,Fundamentals of Convolutional Coding.IEEE Press,Piscataway,N.J.,1999. Copyright by周武旸

第四章卷积码的编码 1 Copyright by 周武旸第四章卷积码卷积码与分组码不同，其编码器具有记忆性，即编码器的当前输出不仅与当前输入有关，还跟以前时刻的输入有关。速率 R=k/n、存储器阶数为 m 的卷积编码器可用 k 个输入、n 个输出、输入存储器阶数为 m 的线性序贯电路实现，即输入在进入编码器后仍会多呆 m 个时间单元。通常，n和k都是比较小的整数，k<n，信息序列被分成长度为k的分组，码字(codeword) 被分成长度为 n 的分组。当 k＝1 时，信息序列无需分组，处理连续进行。值得注意的是，卷积码不象分组码，较大的最小距离和低错误概率不是通过增加 k 和 n 实现的，而是通过增加存储器阶数 m 实现的。我们这一章关注卷积编码过程、卷积编码器如何用状态图表示、如何推导卷积码的重量枚举（weight-enumerating）函数、卷积码的几种距离测量方法。卷积码是 1955 年由 Elias（1923～2001）首次提出的，随后 Wozencraft 和 Reiffen 提出了序贯译码方法（对具有较大约束长度的卷积码非常有效）。1963 年，Massey 提出了一个效率不高、但易于实现的译码方法――门限译码，这使得卷积码大量应用于卫星和无线信道的数字传输中。 1967 年，Viterbi 提出了最大似然（ML, Maximum Likelihood）译码算法，易于实现具有较小约束长度的卷积码的软判决译码。Viterbi 算法配合序贯译码的软判决，使卷积码在 20 世纪 70 年代广泛应用在深空和卫星通信系统。1974 年，Bahl, Cocke, Jelinek 以及 Raviv （BCJR）针对具有不等先验概率信息比特的卷积码，提出了最大后验概率（MAP，maximum a posteriori probability）译码算法。BCJR 算法近年来广泛应用到软判决迭代译码方案中，其中信息比特的先验概率在每次迭代时都发生变化。对卷积码描述最详尽的书籍是： R. Johannesson and K.S. Zigangirov, Fundamentals of Convolutional Coding. IEEE Press, Piscataway , N. J., 1999. On December 7, 2001, the field of information theory lost another of its true giants, Peter Elias, who passed away at his home in Cambridge, Massachusetts, a victim of the mysterious and dreadful ailment, Creutzfeld-Jakob Disease. A.J.Viterbi 毕业于麻省理工学院（MIT），分别获博士/硕士 /学士学位,是无线通信领域国际权威专家，被称为 CDMA 之父。现为美国 Qualcomm 公司首席科学家，加州大学 Los Angeles 分校（UCLA）教授，IEEE Fellow（国际电子电气工程师协会会士）,美国总统国家科学和工程委员会成员

第四章卷积码的编码 2 Copyright by 周武旸 4.1 卷积码的编码卷积码的编码分为两类：前馈和反馈，在每类中又可分为系统和非系统形式。首先考虑非系统形式的前馈编码器。＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝例 4.1 速率 R＝1/2 的非系统前馈卷积编码器图 4.1 为速率 R＝1/2、存储器阶数 m＝3 的非系统前馈卷积编码器框图，该编码器中输入信息比特 k=1、n＝2 个模 2 加法器、m＝3 个延时单元。由于模 2 加法器是一个线性运算，因此编码器是一个线性系统，所有卷积码都可用这类线性前馈移位寄存器编码器实现。 (0) v (1) v u 图 4.1 速率 R＝1/2 的非系统前馈卷积编码器信息序列 012 u = ( , , ,...) uuu 进入编码器，每次 1 比特，由于编码器是一个线性系统，两个编码器输出序列 (0) (0) (0) (0) 01 2 v = ( , , ,...) vvv 和 (1) (1) (1) (1) 01 2 v = ( , , ,...) vvv 可通过输入序列 u 和两个编码器脉冲响应的卷积得到。计算脉冲响应时，可设 u=(1 0 0 … )，然后观测两个输出序列。对一个具有 m 阶存储器的编码器，脉冲响应能够持续最多 m+1 个时间单元，可写为 (0) (0) (0) (0) (0) 01 2 ( , , ,..., ) m g = ggg g 和 (1) (1) (1) (1) (1) 01 2 ( , , ,..., ) m g = ggg g 。对上图的编码器，有 (0) (1) (1 0 1 1) (1 1 1 1) = = g g （4.1）脉冲响应 (0) g 和 (1) g 称为编码器的生成器序列。这样，编码方程为： (0) (0) (1) (1) = ⊗ = ⊗ v ug v ug （4.2）其中⊗ 表示离散卷积，且所有运算都是模 2 加运算，对于所有l ≥ 0，有： ( ) ( ) 0 () () ( ) 0 11 , 0,1 m j j l li i i jj j l l lm m v ug ug u g u g j − = − − = = + ++ = ∑  （4.3）其中对于所有 l<i， 0 l i u −  ，这样对图 4.1 所示的编码器，有： (0) 2 3 (1) 123 ll ll l ll l l vu uu v uu u u − − −− − = ++ =+ + + （4.4）

第四章卷积码的编码 4 Copyright by 周武旸编码速率 R=2/3、存储器阶数 m=1 的编码器结构如图 4.2 所示，该编码器由 k=2 个移位寄存器、m=1 个时延单元、n=3 个模 2 加法器组成。信息序列进入编码器时每次进入 k=2 个比特，可写为 (1) (2) (1) (2) (1) (2) 01 00 11 22 u uu = = (,,)( , , ,)   uu uu uu ，或作为两个输入序列 (1) (1) (1) (1) 01 2 u = ( , , ,) uuu  和 (2) (2) (2) (2) 01 2 u = ( , , ,) uuu  。对应于每个输入序列，都有三个生成器序列。设 () () () () ,0 ,1 , ( , ,, ) j jj j i i i im g = gg g  表示对应于输入 i 和输出 j 的生成器序列，这样我们可得到图 4.2 所示编码器的生成器序列为： (0) (1) (2) 1 11 (0) (1) (2) 2 22 (1 1) (0 1) (1 1) (0 1) (1 0) (1 0) = = = = = = ggg ggg （4.11）这样我们可写出编码方程如下： (0) (1) (0) (2) (0) 1 2 (1) (1) (1) (2) (1) 1 2 (2) (1) (2) (2) (2) 1 2 =⊗+⊗ =⊗+ ⊗ =⊗+⊗ vugu g vu gu g vugu g （4.12）卷积运算意味着 (0) (1) (1) (2) 1 1 (1) (2) (1) 1 (2) (1) (2) (1) 1 l l ll l ll l ll l v u uu v uu v uuu − − − − =+++ = + =++ （4.13）复用后，码字为： (0) (1) (2) (0) (1) (2) (0) (1) (2) 0 00 1 11 2 22 v = ( , , ,) vvv vvv vvv  (4.14) 例如：如果 (1) u = (1 0 1)和 (2) u = (1 1 0) ，则 (0) (1) (2) (101) (11) (110) (01) (1001) (101) (01) (110) (10) (1001) (101) (11) (110) (10) (0011) = ⊗+ ⊗ = = ⊗+ ⊗= = ⊗+ ⊗ = v v v (4.15) 所以输出序列为： v = (110,000,001,111) （4.16）生成矩阵为： (0) (1) (2) (0) (1) (2) (0) (1) (2) 1,0 1,0 1,0 1,1 1,1 1,1 1, 1, 1, (0) (1) (2) (0) (1) (2) (0) (1) (2) 2,0 2,0 2,0 2,1 2,1 2,1 2, 2, 2, (0) (1) (2) (0) (1) (2) (0) (1) (2) 1,0 1,0 1,0 1, 1 1, 1 1, 1 1, 1, 1, mmm mmm m m m mmm ggg ggg ggg ggg ggg g g g ggg g g g ggg g −−− G =   (0) (1) (2) (0) (1) (2) (0) (1) (2) 2,0 2,0 2,0 2, 1 2, 1 2, 1 2, 2, 2, m m m mmm gg g g g g g g −−−         (4.17) 编码方程仍写为 v uG = ，注意：G 中每 k＝2 行都与前 2 行相同，只是向右移 n=3 位。如上例中， (1) u = (101) 和 (2) u = (110) ，则 012 u uuu = = ( , , ) (11,01,10) ，有：

第四章卷积码的编码 5 Copyright by 周武旸 101 111 011 100 101 111 (11,01,10) 011 100 101 111 011 100 (110,000,001,111)     = =   = v uG (4.18) 与我们前面的计算一致！！＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝在上两例中，从存储输入序列的 k 个移位寄存器到 n 个模 2 加法器的连接，直接对应于在 kn 个生成器序列中的非零项，如式（4.1）和（4.11）所示。从上述的例子中可以看出，当输入序列数 k>1 时，复杂度明显增加。下面给出与移位寄存器长度有关的四个定义：定义 4.1：设 vi是卷积编码器（有 k 个输入序列）第 i 个移位寄存器的长度，i＝1, 2,…,k。例如图 4.1 中速率 R＝1/2 的编码器，v＝3；图 4.11 中速率 R＝2/3 的编码器，v1 = v2 =1。定义 4.2：编码器的存储器阶数 m 定义为： 1 max i i k m v ≤ ≤ = （4.19）即 m 是所有 k 个移位寄存器的最大值。例如图4.1中速率R＝1/2的编码器，m＝v1＝3；图4.11中速率R＝2/3的编码器，m＝max(v1,v2) ＝max(1,1)=1。定义 4.3：编码器的全局约束长度 v 定义为： 1 i i k v v ≤ ≤ = ∑ （4.20）即，v 是所有 k 个移位寄存器的总和。例如图 4.1 中速率 R＝1/2 的编码器，v＝v1＝3；图 4.11 中速率 R＝2/3 的编码器，v＝v1+v2=2。定义 4.4：全局约束长度为 v、编码速率 R＝k/n 的卷积编码器常表示为一个（n,k,v）编码器。例如图 4.1 中速率 R＝1/2 的编码器是（2，1，3）编码器，图 4.11 中速率 R＝2/3 的编码器是（3，2，2）编码器。因此，对于（n，1，v）编码器，全局约束长度 v 就等于存储器阶数 m。＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝例 4.3：（4，3，3）非系统前馈卷积编码器（4，3，3）非系统前馈卷积编码器如图 4.3 所示，寄存器长度 v1=0, v2=1, v3=2。存储器阶数 m＝2，全局约束长度 v＝3，生成器序列为： (0) (1) (2) (3) 1 11 1 (0) (1) (2) (3) 2 22 2 (0) (1) (2) (3) 3 33 3 (100) (100) (100) (100) (000) (110) (010) (100) (000) (010) (101) (101) gggg gggg gggg = = = = = = = = = = = = （4.21）

第四章卷积码的编码 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 个输出的生成多项式

第四章卷积码的编码 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)）必须满足校验方程：

中国科学技术大学：《编码理论》课程教学资源（课件讲义）第四章 卷积码

中国科学技术大学：《编码理论》课程教学资源（课件讲义）第四章卷积码