第四章卷积码的编码 第四章卷积码 卷积码与分组码不同，其编码器具有记忆性，即编码器的当前输出不仅与当前输入有关， 还跟以前时刻的输入有关。速率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（国际电子电气 工程师协会会士）,美国总统国家科学和工程委员会成员
第四章卷积码的编码 4.1卷积码的编码 卷积码的编码分为两类：前馈和反馈，在每类中又可分为系统和非系统形式。首先考虑 非系统形式的前馈编码器。 例4.1速率R=1/2的非系统前馈卷积编码器 图4.1为速率R=1/2、存储器阶数m=3的非系统前馈卷积编码器框图，该编码器中输 入信息比特k=1、n=2个模2加法器、m=3个延时单元。由于模2加法器是一个线性运算， 因此编码器是一个线性系统，所有卷积码都可用这类线性前馈移位寄存器编码器实现。 图41速率R=1/2的非系统前馈卷积编码器 信息序列u=(4o,4,42,)进入编码器，每次1比特，由于编码器是一个线性系统，两 个编码器输出序列v0=(,,°，…)和v0=(,,”,…)可通过输入序列u和两 个编码器脉冲响应的卷积得到。计算脉冲响应时，可设=(100..)，然后观测两个输出序 列。对一个具有m阶存储器的编码器，脉冲响应能够持续最多+1个时间单元，可写为 g)=(g60,g,g°，，g)和g=(g6,g",g,g)。对上图的编码器，有 g0=(1011) (4.1) g9=1111) 脉冲响应g和g称为编码器的生成器序列。这样，编码方程为： vo)=u⑧g (4.2) v"=u⑧g9 其中⑧表示离散卷积，且所有运算都是模2加运算，对于所有1≥0，有： 90-24-89 (4.3) =48+4-1g+…+4-mgR,j=0,1 其中对于所有<i,山兰0，这样对图4.1所示的编码器，有： 0=山 +41-2+4-3 (4.4) y0=4,+41+4-2+4- 2 Copyright by周武旸
第四章 卷积码的编码 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）
第四章卷积码的编码 编码后，两个输出序列复用成一个序列，称为码字(codeword),表示为 v=(0,9,0,",,,） (4.5) 例如信息序列u=(10111),则输出序列为： vo,=(10111)⑧(1011)=(10000001) (4.6) v0=(10111)⑧(1111)=(11011101) 复用成一个序列为：v=(11,01,00,01,01,01,00,11) (4.7) 如果将生成器序列g和g写出矩阵形式，为： 「gggg"gg"…gg9 G= g60g”gg…g9g9 gg (4.8) 86g…8,828889g9 其中空白区域为全0，这样编码方程可写为矩阵形式： y=uG (4.9) G称为该编码器的生成矩阵。我们注意到G中的每一行都与前一行相同，只是向右移 位了=2位，它是一个半无限矩阵，对应于信息序列u是一个任意长度的序列。如果u只 有有限长h,则G具有h行、2(m+h)列，v的长度为2(m+h)。例如上例中u=(10111),则 v=uG 「11011111 11011111 =(10111) 11011111 (4.10) 11011111 11011111 =(1101000101010011) 与我们前面的计算一致！ =二二===三=三=====三三三 例4.2速率R=23的非系统前馈卷积编码器 v(0 图4.2 Copyright by周武旸
第四章 卷积码的编码 3 Copyright by 周武旸 编码后，两个输出序列复用成一个序列，称为码字（codeword），表示为 (0) (1) (0) (1) (0) (1) 0 01 1 2 2 v = ( , , , , , ,) vvvvvv （4.5） 例如信息序列 u=(1 0 1 1 1)，则输出序列为： (0) (1) (1 0 1 1 1) (1 0 1 1) (1 0 0 0 0 0 0 1) (1 0 1 1 1) (1 1 1 1) (1 1 0 1 1 1 0 1) = ⊗= = ⊗= v v （4.6） 复用成一个序列为： v = (11,01,00,01,01,01,00,11) （4.7） 如果将生成器序列 (0) g 和 (1) g 写出矩阵形式，为： (0) (1) (0) (1) (0) (1) (0) (1) 00 11 22 (0) (1) (0) (1) (0) (1) (0) (1) 00 11 1 1 (0) (1) (0) (1) (0) (1) (0) (1) 0 0 2 2 1 1 m m m m mm m m m m mm gg gg gg gg gg gg g g gg gg g g g g gg − − − − −− = G （4.8） 其中空白区域为全 0，这样编码方程可写为矩阵形式： v uG = （4.9） G 称为该编码器的生成矩阵。我们注意到 G 中的每一行都与前一行相同，只是向右移 位了 n=2 位，它是一个半无限矩阵，对应于信息序列 u 是一个任意长度的序列。如果 u 只 有有限长 h，则 G 具有 h 行、2(m+h)列，v 的长度为 2(m+h)。例如上例中 u=(1 0 1 1 1)，则 11 01 11 11 11 01 11 11 (1 0 1 1 1) 11 01 11 11 11 01 11 11 11 01 11 11 (11 01 00 01 01 01 00 11) = = = v uG （4.10） 与我们前面的计算一致！！ ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 例 4.2 速率 R=2/3 的非系统前馈卷积编码器 (0) v (1) v (1) u (2) u (2) v 图 4.2
第四章卷积码的编码 编码速率R=2/3、存储器阶数=1的编码器结构如图4.2所示，该编码器由k=2个移位 寄存器、m=1个时延单元、=3个模2加法器组成。信息序列进入编码器时每次进入k=2 个比特，可写为u=(u,山1，）=(2,42,442，)，或作为两个输入序列 u0=(,,”,)和2)=(2,42,2，)。对应于每个输入序列，都有三个生成 器序列。设g=(g,g,,8)表示对应于输入i和输出j的生成器序列，这样我们可 得到图4.2所示编码器的生成器序列为： g0=(11)g"=(0)g2=11) (4.11) g=(01)g=(10)g2=10) 这样我们可写出编码方程如下： vo=u0⑧g0+u②⑧g v=u0⑧g"+u2)图g (4.12) v2=u0⑧g2+u2⑧g2 卷积运算意味着 y0=49+ +唱+2 0= 42+4唱 (4.13) 2=49+42+49 复用后，码字为： V=(2,0"2,"2,） (4.14) 例如：如果u=(101)和u②=(110，则 vo,=(101)⑧(11)+(110)⑧(01)=(1001) v=(101)⑧(01)+(110)⑧(10)=(1001) (4.15) v2)=(101)⑧(11)+(110)⑧(10)=(0011) 所以输出序列为： v=(110,000,001,111) (4.16) 生成矩阵为： g0g1gt g0gHg8…g10mgmg1m 80g8 gYgg…g9gg9 G= sgigt g10-g”g2 (4.17) gE8 g9-80-8gm88 编码方程仍写为v=uG,注意：G中每k=2行都与前2行相同，只是向右移=3位。 如上例中，u0=(101)和u2=(110),则u=(uo,1,u2)=(11,01,10),有： Copyright by周武肠
第四章 卷积码的编码 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) ，有：
第四章卷积码的编码 T101111 011100 101 111 v=uG=(11,01,10) 011100 (4.18) 101111 011100 =(110,000,001,111) 与我们前面的计算一致！ ================ 在上两例中，从存储输入序列的k个移位寄存器到个模2加法器的连接，直接对应于 在kn个生成器序列中的非零项，如式(4.1)和(4.11)所示。从上述的例子中可以看出， 当输入序列数k>1时，复杂度明显增加。 下面给出与移位寄存器长度有关的四个定义： 定义4.1：设y,是卷积编码器（有k个输入序列）第i个移位寄存器的长度，i=1,2,k。 例如图4.1中速率R=1/2的编码器，v=3:图4.11中速率R=2/3的编码器，v1=V2=1。 定义4.2：编码器的存储器阶数m定义为： m max vi (4.19) 1≤i≤k 即m是所有k个移位寄存器的最大值。 例如图4.1中速率R=1/2的编码器，m=v1=3:图4.11中速率R=2/3的编码器，m=max(v1,2) =max(1.1=l。 定义4.3：编码器的全局约束长度v定义为： v=∑y (4.20) 即，v是所有k个移位寄存器的总和。 例如图4.1中速率R=1/2的编码器，v=v1=3:图4.11中速率R=2/3的编码器，v=v1+2=2。 定义4.4：全局约束长度为v、编码速率R=kn的卷积编码器常表示为一个(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,2=1,=2。存储器 阶数m=2,全局约束长度v=3,生成器序列为： g0=(100)g"=(100)g12=(100)g)=(100) g°=(000)g=(110)g2=(010)g=(100) (4.21) g°=(000)8"=(010)82=(101)g=101) Copyright by周武旸
第四章 卷积码的编码 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）