信息论基础 第七章信道编码

1、P.12022/4/1 目的：提高通信系统传输的可靠性； 目标：寻找具体构造编码的理论与方法； 在理论上，Shannon第二编码定理已指出，只要当实际传信率Rk）的二进制码组。 线性分组码线性分组码 P.182022/4/1 按数学上更为一般的定义可表示为： ，其中nk， 若f进一步满足下列线性关系： 其中： 由上述定义，可见线性分组码f可看成： 线性分组码（续）线性分组码（续） nkCUf:) ()() (ufufuuf1 , 0)2(,GF)2(,kGFuu)2()2(:nknkGFGFCUf线性空间的变换有限域空间的变换P.192022/4/1 线性分组码是分组码中最重要最有实用价值的一

2、个子类，下面将从具体例子入手，阐明它的一些基本概念。 例：以（7，3）二元线性分组码为例，其中： ， ， ，这时输入编码器的信息分成三个一组，即 ，它可按下列线性方程组编码： 线性分组码（续）线性分组码（续） 7n3k437kn73nk)(210uuuu P.202022/4/1 写成矩阵形式 称G为生成矩阵，若 即能分解出单位方阵为子阵，且I的位置可任意，则称 为系统码（或组织码）若将上述监督线性方程组改写为:线性分组码（续）线性分组码（续） C()uI Q()GI QP.212022/4/1即 线性分组码（续）线性分组码（续） 2121610105210210420203CCuuCCCuu

3、CCCCuuuCCCuuC00006215103210320CCCCCCCCCCCCCP.222022/4/1再改变为矩阵形式: 即 HCT= OT (PI)CT=OT 称H为监督(校验)矩阵，若H=(PI)，即能分解出单位方阵为子阵，且I的位置可任意，则称C为系统（组织）码。线性分组码（续）线性分组码（续） 012345610110000111010001100010001100010CCCCCCC P.232022/4/1 生成矩阵G一般用于发端编码，而监督矩阵H则一般用于接收端的译码。由于生成矩阵G中的每一行及其线性组合都是线性（n,k）码的码组（字），因此有： HGT= OT或GHT=

4、O 它说明矩阵G与H互为零化空间。 由线性空间理论，一个n维的线性空间Vn可以分解为一对互为对偶的正交子空间Vk与Vn-k。 即： 线性分组码（续）线性分组码（续） 互为对偶码3337444GVHVHVG可构成(7,3)线性分组码可构成(7,4)线性分组码P.242022/4/1 结合上面n=7的例子,则有 显然有：(7,3)码的生成矩阵G3就是(7,4)码监督矩阵H3 ，(7,3)码的监督矩阵H4就是(7,4)码的生成矩阵G4采用系统（组织）码来描述生成矩阵G与监督矩阵H，仅是其中的一种。在很多情况下是采用非系统码的描述方式，那么两者之间有没有什么实质上的差别？ 线性分组码（续）线性分组码（

5、续） knn kGVHVHVG可构成(n,k)线性分组码可构成(n,n-k)线性分组码互为对偶码P.252022/4/1由线性代数理论，任何一个非系统的生成矩阵G均可以通过矩阵的初等变换得到相应的系统码的生成矩阵G。因此，我们可以得到如下结论：任何一个线性分组（n,k）码，均可找到一个等价的系统码，而且还可以进一步证明只要在码率R和码长n相同的条件下，最优的系统码与最优的线性分组码具有相同的错误概率。 线性分组码特别是系统码的编码器极其简单，其具体结构可参见书上有关章节，这里就不再赘述。 线性分组码（续）线性分组码（续） P.262022/4/1线性分组码（续）线性分组码（续） 线性分组码的译

6、码，特别是系统码也比较简单，在数据通信中，最优译码即为最小误码准则下的译码，它在信源等概率即p0=p1时，可等效为最大似然准则，当信道为BSC时，它又可等效为最小汉明距离准则，关于准则问题将在后面讨论卷积码的译码时进一步详细讨论。译码时，在接收端收到的信号为： 且 其中 表示发送的码组（字） 表示传输中的差错。 011,nyy yyyxn ce 011,ncc cc011,neeeeP.272022/4/1 由监督方程： 即只要在传输中不产生差错，即 则必满足上式。实际上传输中一定产生差错，这时 ，则有 且有 我们称s为伴随子（校正子），这是由于s仅与e有关，而与码组(字)c无关。 对于一个(

7、n,k)线性分组码，H矩阵是一个(n-k)行n列的矩阵，所以s为一个（n-k）维的矢量。 它仅可以给出（n-k）个独立方程组，监督(n-k)位的差错。然而在信线性分组码（续）线性分组码（续） 0TTHc 0e 0e 0TTTTTTTTH yHceHcHeHeHesTTTTTTTTTssHyyHce HcHeHeHP.282022/4/1线性分组码（续）线性分组码（续） 道中传输的差错e是一个n维矢量，有可能产生n位差错。因此仅上述伴随子方程不能求解n位差错，由于2n=2n-k2k，半随子方程仅能解出2n-k个差错图样，也可以说有2k个差错图样共用一个伴随子方程，真正的差错是2n-k中的某一个。

8、在二进制对称信道BSC条件下，最可能出现的错误图样是接收码组中汉明重量最小的码组，即非0个数最小的码组。 下面以(7,4)线性分组码为例，不过这里的(7,4)码不是直接与(7,3)码互为对偶码，而是将其对偶码再经过矩阵初等变换后的(7,4)码，监督矩阵和生成矩阵分别如下：P.292022/4/1线性分组码（续）线性分组码（续） 111101000100101101101000101110111001000101111010001(1001011)(1001001)(0000010)HGCye若待发送的码组为：接收的码组为：信道产生的差错图样：P.302022/4/1线性分组码（续）线性分组码（

9、续） 11001011(1001001) 0101110(111)0010111216(0000010)(1001001),16(0000010)1(0000010),(1001001)(1001001)(0000010)(10TTksyHweycye由伴随矩阵有：由前面分析，应有种差错图样满足：在这种差错中，最小因此可以判断且可以将接收的矢量译为：01011)(7,4)c由上述码的特例可以总结出：P.312022/4/1线性分组码（续）线性分组码（续） 122222kkn kkssBSC-：将同一伴随式 所对应的差错图样排成一行，它共有个彼此正交的码组，构成一个集合，称它为陪集合。：将个正交

10、码组中汉明重量最轻的放在该行的首位，称它为陪集首。3：将不同种类的伴随式 所决定的种个元素组成的行放在不同的列，而在不同列中行的排列与第一行相同，并完全对应。4：所有各行的第一列构成一个陪集首集合，它是信道最小距离准则下最可能产生差错的集合。P.322022/4/1 按照上述规则，可以将一个（n，k）线性分组码的译码，按照伴随式的规则划分为 个行矢量乘以 个列矢量所构成的下列标准阵列： 线性分组码（续）线性分组码（续） 2n k2k001211111121121121212121210kkkn kn kn kn kkmmlllmlmecccceecececeecececeececec P.33

11、2022/4/1 称这种译码为伴随式译码，或称为查表译码。它原则上适合于任何（n，k）线性分组码。 伴随式译码步骤可归纳如下： 1）计算接收矢量 的伴随式： 2）由伴随式 决定相对应的陪集首 3）将 译成 其具体实现框图如下： 线性分组码（续）线性分组码（续） yTsy Hs eycyeP.342022/4/1线性分组码（续）线性分组码（续） 接收矢量缓冲器伴随式计算电路错误图样检测电路已纠正的输出接收矢量0y1y1ny0s1s1n ks 0e1e1ne0y1y1ny0c1c1ncyP.352022/4/1线性分组码（续）线性分组码（续） 伴随式 陪集首0 0 00 0 0 0 0 0 0 1

12、 0 01 0 0 0 0 0 00 1 00 1 0 0 0 0 0 0 0 10 0 1 0 0 0 01 1 00 0 0 1 0 0 0 0 1 10 0 0 0 1 0 01 1 10 0 0 0 0 1 01 0 10 0 0 0 0 0 1(7,4)码的陪集首集合012(,)ss s s0123456( , ,)ee e e e e e eP.362022/4/1 对于(7,4)码，若 其具体运算和纠正差错过程可参考书上的(7,4)线性分组码译码电路图。线性分组码（续）线性分组码（续） )1001011(c)1001001(y)0000010(e(111)TsyH可求出，P.37

13、2022/4/1 循环码是线性分组码中最主要，最有适用价值的一类，它是1957年由Prange首先提出 循环码循环码P.382022/4/1 基本定义：一个（n,k）线性分组码，经任意循环移位之后，仍然是线性分组码，则称它为循环码主要特点主要特点 1）理论成熟：可利用成熟的代数结构深入探讨其性质； 2）实现简单；可利用循环移位特性在工程上进行编，译码； 3）循环码的描述方式有很多，但在工程上可采用最有用的多项式的描述方法。 一一对应： n元码组(字) n阶(含0阶)码多项式 有限域 多项式域模运算 码组模2运算 多项式乘积运算 循环码（续）循环码（续）0 11()ncc cc1011( )nn

14、c xcc xcx(2 )nGFP.392022/4/1在多项式描述中，我们可以将“同余”（模）运算推广到多项式中。即循环码（续）循环码（续）( )( )( )( )( )C xr xQ xp xp x( ),mod( )C xr xp x记为： （ ）例：110101101001101101111+x+x31+x+x31+x1+x +x3x+x2 +x41+ x2+x3+x4*P.402022/4/1则有下列多项式除法: 循环码（续）循环码（续）3567: ( )C xxxxx例7( )1p xx 71356773561 ( )11 ( )xQ xxxxxxxxx r x ( )p xP.4

15、12022/4/1下面给出(7,3)码循环移位特性：（见下页）循环码（续）循环码（续）35673567:1,mod(1)xxxxxxxx 故有P.422022/4/1循环码（续）循环码（续）码组 码多项式0 1 0 1 1 1 0 0 1+x2+x3+x41 0 1 0 1 1 1 0 x(1+x2+x3+x4)2 0 0 1 0 1 1 1 x2(1+x2+x3+x4)3 1 0 0 1 0 1 1 x3(1+x2+x3+x4)= 1+ x3 +x5 +x6,mod(1+x7)4 1 1 0 0 1 0 1 x4(1+x2+x3+x4)= 1+ x +x4 +x6,mod(1+x7)5 1

16、1 1 0 0 1 0 x5(1+x2+x3+x4)= 1+ x +x2 +x5,mod(1+x7)6 0 1 1 1 0 0 1 x6(1+x2+x3+x4)= x+ x2+x3 +x6,mod(1+x7)7 1 0 1 1 1 0 0 x7(1+x2+x3+x4)= 1+ x2 +x3 +x4,mod(1+x7)x0 x1 x2 x3 x4 x5 x6移位次数P.432022/4/1 可见推移7位后出现周期性循环特性. 下面进一步研究(7,3)循环码生成矩阵表达式: 循环码（续）循环码（续）101110001011100010111001110101001111001110初等变换G245

17、62234345234234234(1)(1)11(1)xxxxxxxxxxxxxxxxxxxxxx2()()1()xg xx g xg xP.442022/4/1 可见,在循环码中,其生成矩阵结构更加简化,它是由生成多项式g(x)循环推移构成.书中给出k位信息位的一般化表达式,以及在一般情况下,当为系统码时循环码的生成矩阵表达式.有兴趣者可进一步仔细阅读. 在线性分组码中有: 对应于循环码中有: 例:仍以(7,3)循环码为例:循环码（续）循环码（续）0TG H( )( )0,mod(1)ng x h xx( )( )1ng x h xx 或)1)(1)(1 (13327xxxxxxP.452

18、022/4/1 (7,3)码生成多项式的阶次为:n-k=7-3=4,故有 或者 由线性分组码的对偶性,可求得对应(7,4)码的生成多项式与监督多项式如下: 或循环码（续）循环码（续）)1 ()()1)(1 ()(31321xxxhxxxxg)1 ()()1)(1 ()(32232xxxhxxxxg)1)(1 ()()()1 ()()(3213313xxxxgxhxxxhxg)1)(1 ()()()1 ()()(3243224xxxxgxhxxxhxgP.462022/4/1循环码的编码循环码的编码 例:若输入信息码元为:u=(1001)即 ,下面将简介最简单的系统循环码的编译码.仍以(7,4)

19、系统循环码为例: 我们所选的多项式 ,由系统码生成规则: 即： 循环码（续）循环码（续）31)(xxu)1 ()()(33xxxgxg32633471)(mod,)1 ()(xxxgxxxxxxxuxknP.472022/4/1循环码（续）循环码（续）33363464242 ( )1( ) ( )( )( )( )( )( )( )( )( )( )n kn kxx Q xxxxx xu xxxxxxxxxxr xC xr xxu xr xQ xg xr xQ xg x27 43236(1)xxxxxxxx01 1 1001CP.482022/4/1其中最右边的4位是信息元，这样编码器结构图如

20、下： 循环码（续）循环码（续）输入信息码字输出门D0D1D2P.492022/4/1循环码（续）循环码（续）输出码字为: 01234560111001CCCCCCCCD0D1D2D2D1D01P.502022/4/1上述编码过程如下： 三级寄码器的初态为000，信息元组以(即1001）分两路, 一路直接输出，另一路送入g(x)除法电路； 经四次移位后，信息元组1001全部输出，另一路也全部送入g(x)除法电路并完成除法电路运算。这时寄存器中的状态为余式r(x)即监督元 输出开关由1倒向2，并经三次移位，将监督元 跟在信息元 后依次输出得到 c = = (0111001)。 循环码（续）循环码（

21、续）37436( )(1)uku xxxxxx)(210ccc)(210ccc)(6543cccc)(6543210cccccccP.512022/4/1（7,4）循环码译码过程如下： 若 即 y=(1111001) 将其输入译码器，其译码过程如下列表格所示： 循环码（续）循环码（续）66332210)(xyxyxyxyyxyP.522022/4/1循环码（续）循环码（续）i次移位后伴随矢量错误图样 伴随式 1+x+x2 伴随矢量移位次数 e6 1+x2 1 0 1 0 1 0 1 e5 1 1 1 1 1 0 1 e4x+x2 0 1 1 2 1 0 1 e31+x 1 1 0 3 1 0

22、1 e2x2 0 0 14 1 0 1 e1 x 0 1 0 5 1 0 1 e01 1 0 0 6 1 0 1e(x)s(x)s0 s1 s2is0 s1 s2P.532022/4/1生成的（7,4）循环码译码器原理图循环码（续）循环码（续）3( )1g xxx复用器门1门2门0s2s1s( )y xP.542022/4/1上述译码器工作步骤如下： 首先将移位寄存器复0，清洗到初始状态； 输入y分两路进入译码器，一路进入缓存器，另一路经门1进入伴随式计算电路，分别计算s0s1s2； 在输出y的同时，s0s1s2依次循环移位，无差错时，错误检测电路无输出，最后输出码元与接收的y中码元一致；有错

23、误时，错误检测电路输出为1，它正好与y中的错误位在模2加中相遇，并自动予以纠正。 这一循环译码器与前面线性分组（7，4）码的译码器比较是实现结构简化了，在线性分组码中，对每一种伴随式要设计一个相对应的伴随式计算电路，而在循环（7，4）码中，可利用码的循环特性共用一套设备。 循环码（续）循环码（续）P.552022/4/1 循环码特别适合于检测错误，这是由于它具有很强的检测错误的能力，同时实现起来也较简单；CRC一般能检测如下错误： 突发长度 n-k+1的突发错误，其中不可检测错误仅占2-( n-k) ； 所有与许用码组码距dmin-1的错误； 所有奇数个错误；常用的CRC码，已成为国际标准的有

24、： CRC-12，其生成多项式：g(x)=1+x+x2+x3+x11+x12CRC检错码（检错码（cyclic redundancy check） P.562022/4/1 CRC-16，其生成多项式：g(x)=1+x2+x15+x16 CRC-CCITT，其生成多项式：g(x)=1+x5+x12+x16 CRC-32，其生成多项式： g(x)=1+x+x2+x4+x5+x7+x8+x10+x11+x12+x16+x22+x23+x26+x32 其中CRC-12用于6bit字符，其余则用于8bit字符。 CRC检错码（续）检错码（续） P.572022/4/1 BCH 码是一类最重要的循环码，

25、它能纠正多个随机错误，它是1959-1960年由Hocquenghem，Bose与Chandari 三位学者独立发现的二元线性循环码。人们将三人名字的字头BCH命名为BCH码。 BCH 码具有纠错能力强，构造方便，编、译码易于实现的一系列优点。 我们这里不讨论BCH码的理论与性质，因为它要涉及更深的近世代数的群、环、域的知识；重点侧重于对BCH码的工程上的使用，即利用已知的BCH码表格，构造对应的生成多项式。 若循环码生成多项式为： g(x) = LCM m1(x),m3(x),m2t-1(x) 这里t为纠错的位数，mi(x)为素多项式，LCM为求最小公倍数。 BCH码码P.582022/4/

26、1 则 由 此 生 成 多 项 式 生 成 的 循 环 码 称 为 B C H 码 ， 其 最 小 距 ： dmind0=2t+1(d0为设计码距)，它能纠正t个随机独立差错。 BCH码的码长为n=2m1或是n=2m1的因子，通常称前者为本原BCH码，称后者为非本原BCH码。 书中列出n127的本原BCH码，和部分非本原BCH码的生成多项式表与部分不可约的多项式表。 例1： BCH(15，5)码。 它是一个可纠正3个随机独立差错的BCH码，即t=3; dd0 = 2t+1 = 2*3+1=7;BCH码（续）码（续）P.592022/4/1 n=15=2m-1=24-1, m =4;查不可约多项

27、式，可求得 m1(x) =(23)*8 = 010011 = x4 + x + 1 * m3(x) =(37)8 = 011111 = x4 + x3 + x2 + x + 1 m5(x) =(07)8 = 000111 = x2 + x + 1 g(x)=LCMm1(x),m3(x),m5(x) =LCM(x4+x+1)(x4+x3+x2+x+1)(x2+x+1) =x10+x8+x5+x4+x2+x+1 注：*.(x x)8 是八进制表达式 *.本节中编码序列与以前相反，它是从高位向低位排列，其原因，这里引用的三个表格是从高向低排。BCH码（续）码（续）P.602022/4/1 它是一类纠

28、错能力很强的特殊的非二进制BCH码.对于任选正整数S可构造一个相应的码长为n=qS-1的q进制BCH码,其中码元符号取自有限域GF(q),而q作为某个素数的幂.当S=1，q2时所建立的码长n=q-1的q进制BCH码,称它为RS码.当q=2m(m1),其码元符号取自于F(2m)的二进制RS码可用来纠正突发差错，它是最常用的RS码 RS码的构造码的构造一个可纠正t个符号错误的RS码有如下参数： 码长：n=2m-1 符号， 或m(2m-1) 比特； 信息位：k 符号， 或km 比特； 监督位：n-k=2t 符号， 或m(n-k)=2mt 比特； RS(Reed Solomen)码码 P.612022

29、/4/1 最小码距：dmin=d0=2t+1, 或mdmin=m(2t+1)比特RS码的纠错能力码的纠错能力 具有同时纠正随机与突发差错的能力 它可纠正的错误图样有： 总长度为：b1=(t-1)m+1 比特的单个突发； 总长度为：b2=(t-3)m+3 比特的两个突发； 总长度为： bi=(t-2i+1)m2i-1 比特的i个突发 RS(Reed Solomen)码码 (续续)P.622022/4/1 例：试构造一个能纠正三个符号错误，码长n=15，m=的RS码 已知t=3，n=4，m=4； 求得码距为：d=2t+1 =2*3+1 =7个符号 =7*4=28比特； 监督位：n-k2t=2*3

30、=6个符号； =6*4=24比特； RS(Reed Solomen)码码(续续)P.632022/4/1 信息位：k=n-(n-k) =156=9个符号； =9*436比特； 码长：n=15个符号=15*4=60比特； 该码应为：(15,9)RS码 或(15*4，9*4) =(60,36)二进制码 RS(Reed Solomen)码码 (续续)P.642022/4/1 卷积码是非分组码，它与分组码的主要差别是有记忆编码，即在任意时段，编码器的n个输出不仅与此时段的k个输入有关，而且还与存贮其中的前m个输入有关，故卷积码一般可表示为(n，k，m)， 典型的卷积码一般选n和k(nk)较小，但m值较

31、大(m10左右)，以获取高性能 卷积码是1955年Elias 最早提出； 1957年Wozencraft提出了序列的译码法; 1963年，Massey 提出比较实用的门限译码法； 1967年，Viterbi提出最大似然的Viterbi译码法 卷积码卷积码 P.652022/4/1 卷积码的编码卷积码的编码 卷积码卷积码 （续）（续） 卷积码编码器是由一个有k个输入端口,n个输出端且具有m节移位寄存器所构成的有限状态有记忆系统,通常也称它为时序网络。 P.662022/4/1描述卷积码的方法很多，它大致可划分为两大类 卷积码卷积码 （续）（续）;离散卷积法解析法生成矩阵法 它们多用于编码的描述码

32、多项式法它们多用于译码的描述格图法树图法状态图法图形法;P.672022/4/1 具体例子 下列图形给出一个（2,1,3）卷积码编码器结构： 卷积码卷积码 （续）（续） 若输入信息序列为： )(210uuuu 1g2g1C2CC输出码组序列输入信息序列uP.682022/4/1 对应输出两码组为： 对应的编码方程为： 其中“*”表示卷积运算，故卷积码因此而得名。而 表示编码的两个脉冲冲击响应。一般情况下， 最后可求得 卷积码卷积码 （续）（续）11 1 10 1 222220 12()()cc c ccc c c1122*cugcug12g g、11111012()mgg g gg222220

33、12()mgg g gg12120011()cc c c cP.692022/4/1 卷积码卷积码 （续）（续）121122(10111)(1011)(1111)*(10111)*(1011)(10000001)*(10111)*(1111)(11011101)uggcu gcu g 若：则有至于离散卷积应在信号与系统中学过，不了解者可参见书中有关介绍。 P.702022/4/1下面介绍解析法中的生成矩阵法： 若将冲击响应看成 生成序列，则将该生成序列 进行交织，可构成如下生成矩阵： 则前面的编码方程可改写为下列矩阵形式： 若输出信息序列为一半无限序列： 则上述生成矩阵就是一个半无限的矩阵。

34、卷积码卷积码 （续）（续）121212001122121212001122121212001122g gg gg gg gg gg gGg gg gg gGuc12gg、12gg、012()uu u uP.712022/4/1 例：若 则有： 它与卷积运算结果完全一致。 卷积码卷积码 （续）（续）1101 11111101 1111(10111)1101 11111101 11 111101 11 11(11010001010100 11)cu G 12(10111),(1011),(1111)uggP.722022/4/1下面介绍解析法中的码多项式法: 卷积码卷积码 （续）（续）112212

35、23411232223( )( )( )( )( )( )( )( ( )( )(10111)( )1(1011)( )1(1111)( )1c xu x gxcxu x gxc xc x cxuu xxxxggxxxggxxxx 若P.732022/4/1则有: 卷积码卷积码 （续）（续）1123423234245635677122234232343452456356734572( )( )( )(1)(1)11(10000001)( )( )( )(1)(1)11(110c xu x gxxxxxxxxxxxxxxxxxxccxu x gxxxxxxxxxxxxxxxxxxxxxxxxxx

36、xc 1211101)()(1101000101010011)cc cP.742022/4/1 它亦与前面两种方法所求得的结果完全一致.再举两个例子 若给出一个二元(3,2,1)卷积码编码器如下: 卷积码卷积码 （续）（续） 它是由k=2两个输入端，n=3三个输出端，m=1一节移位寄存器构成的编码器。 输入信息序列u输出码组cP.752022/4/1若输入 ，则它可分两路并行由上述编码器结构图可求出生成序列如下： 卷积码卷积码 （续）（续）(110110)u 12101(110)uu（）123111123222(1,1)(0,1)(1,1)(0,1)(1,0)(1,0)ggggggP.7620

37、22/4/1则 卷积码卷积码 （续）（续）101111011100101111(110110)011100101111011100110000001111cu G P.772022/4/1再给出一个(2,1,2) 卷积码的例子。 若已知码的生成多项式为：g1(x)=1+x+x2 g2(x)=1+x2 输入信息为: u(x)=1+x2+x3+x4 试求1)卷积码编码器的结构图 2)输出码组c=? 解：由生成多项式可给出卷积码编码器结构如下： 卷积码卷积码 （续）（续）P.782022/4/1 卷积码卷积码 （续）（续）12342234345245646223422342456356146( )(

38、1)(1) 1 1( )(1)(1) 1 1( )1 c xxxxxxxxxxxxxxxxxxxxcxxxxxxxxxxxxxxxc xxxx 122356 (1100101)( )1 (1001011)(11100001100111)ccxxxxcc 且P.792022/4/1下面讨论图形表示法，首先从状态图入手： 对于(2,1,2) 卷积码：k=1，n=2，m=2，其总状态数为2km =212=22=4个，即a=00，b=10，c=01，d=11。每状态可能输入和输出有2k =21=2个，用0和1表示。 若输入序列为u=(1011100)，其状态图可以按以下步骤画出：对照（2,1,2）编码

39、器结构图 1)首先，移位寄存器复0，其状态为00 2)输入u0=1，状态改为10，输出 3)输入u1=0,状态改为01,输出c11=1,c12=0,求得c1=（10）； 卷积码卷积码 （续）（续）102001001101,(11);ccc P.802022/4/1 4)输入u2=1,状态改为10，输出c21=0，c22=0，求得 c2=(00)； 5)输入u3=1,状态改为11，输出c31=0，c32=1，求得 c3=(01) ； 6)输入u4=1,状态仍为11，输出c41=1，c42=0，求得 c4=(10) ； 7)输入u5=0,状态改为01，输出c51=0，c52=1，求得 c5=(01

40、) ； 8)输入u6=0,状态改为00, 输出c61=1，c62=1，求得 c6=(11) ； 9)输入u7=0,状态仍为00，输出c71=0，c72=0，求得 c7=(00) ；按以上步骤可画出如下状态图: 卷积码卷积码 （续）（续）P.812022/4/1 再讨论树图结构:它是由状态图展开成的.即按输入信息序列u的输入顺序按时间l=0,1,2,展开,并展示所有可能的输入,输出情况如下: 卷积码卷积码 （续）（续）a00c01d11b1011(1)00(0)11(0)01(0)10(0)00(1)10(1)01(1)P.822022/4/1l分支分支树根P.832022/4/1 由图可见，以

41、初始状态s0=a=00为树根（l=0）,若节点级数用l表示，每个节点分为两个分支：0分支向上，1分支向下，即可求得l=0,1,27不断延伸的树状结构。它是按上述状态图按照l值展开的。 对特殊的输入信息序列u=(1011100)相对应的输出码组c=(11 10 00 01 10 01 11)图中我们用红线表示，且它与前面状态中用红线表示的结果完全一致。 树图最大特点是按时间顺序展开的（即l=0,1,2）且能将所有时序状态表示为不相重合的路径，但是它也存在很大的缺点：结构太复杂，结构重复性太多。 卷积码卷积码 （续）（续）P.842022/4/1 最后讨论格图（又称篱笆图） 格图的最大特点是保持了

42、树图的时序展开性，同时又克服了树图中太复杂的缺点，它将树图中产生的重复状态合并起来，形成格状结构如下： 卷积码卷积码 （续）（续）P.852022/4/1 卷积码卷积码 （续）（续）l=0l=1l=2l=3l=4l=5l=6l=7d=11c=01b=10a=00P.862022/4/1格图在Viterbi 译码中特别有用。 将树图转化为格图是很方便的。在树图中，当l= m+1 = 3 时， 状态 a,b,c,d呈现重复，如果将重复状态，折合起来加以合并，就可以得到纵深宽度（有称高度）为2km =21*2 =22=4的格状图。图中实线表示输入为“0”时所走的分支，虚线则表示输入为“1”时所走的分

43、支。 由于格图既能体现时序关系，又能较简洁的表示状态结构，所以它是卷积码的一种简洁的表达形式。 卷积码卷积码 （续）（续）P.872022/4/1 图 中 粗 红 线 是 表 示 输 入 u = ( 1 0 111 0 0 ) 时 其 对 应 编 码 为c=(11100001100111),这一结果与前面状态图方式，树图方式所得结果完全一致。 不同的信息序列在树图上所对应路径完全不重合，但是在格图上则有可能有部分重合，这样两个不同输入序列，只需计算格图中不相重合部分即可，所以在译码时利用格图更加方便。 卷积码卷积码 （续）（续）P.882022/4/1 卷积码的译码可分为两大类型:代数译码与概

44、率译码.属于代数译码的有Massey1963年提出的门限(或称为大数逻辑)译码;属于概率译码的有1957年Wozencraft提出的序列译码和1967年Viterbi提出的最大似然译码(后来人们就称它为Viterbi译码).在分组码中,我们重点介绍了代数译码,这里只重点介绍Viterbi译码. 卷积码的译码卷积码的译码P.892022/4/1首先介绍译码准则: 在数字、数据通信中常用的准则是最小平均误码率准则.卷积码的译码（续）卷积码的译码（续）:( ) ( / )( / )(/ ),minmin( ) (/ )min(/ )max(/ )eyeypp y p e yp e yp cc ycc

45、pp y p cc yp cc yp cc y即其中为译码后的码组 为发送的码组P.902022/4/1由Bayes公式：若发送码组（字）是等概率的，这时 为常数，当已知接受码组（字）时， 亦为常数，则 结论：当发送码组等概率时，最小平均误码率 准则与最大后验概率准则以及最大似然准则等效。对于离散无记忆信道（DMC）有： 由于对数函数为单调函数，故可将其改写为对数函数形式： 卷积码的译码（续）卷积码的译码（续）( )P c( )P y( ) ()()( )P c P y cP c yP ymax()max()P cc yP y cc10max( /)max(/)LeeelP y ccP ycc

46、ePP.912022/4/1我们称按上述公式进行译码的算法为最大似然译码算法，同时称 为对数似然函数，有时简称为似然函数。进一步，对于二进制对称信道BSC，似然函数可以进一步改写为： 其中 为 与 之间的汉明距离，由于且 为常数，而 ，则有卷积码的译码（续）卷积码的译码（续）log()eeeP ycc)1log(1log),()(logpnppcydccyp),(cydyc1log0(),12ppp)1log(pn10),(),(Lleecydcyd1100maxlog()maxlog()LLeeeeeellPPyycccc10maxlog()min ( , )min(,)Leelp y cc

47、d y cd y cP.922022/4/1 结论：对于BSC最大似然译码等效于最小汉明距离译码。 Viterbi算法的举例：在二进制对称信道BSC下卷积码译码的Viterbi算法就是建立在前面介绍的格图基础上的最小汉明距离算法，下面仍以具体例子入手来分析。例：以最简单的(2,1,2)卷积码为例 若发送的信息序列为 ，即L=5, 经过编码后输出的码组(字)为 接收到的信号序列为：卷积码的译码（续）卷积码的译码（续）)01111110000110(c)01111010010110(y2)0000101 (),(cyd(10111)u P.932022/4/1 在BSC下，其译码在格图上的每一步的

48、计算结果（距离图）和累计计算结果幸存路径图如下述两个图形所示： 卷积码的译码（续）卷积码的译码（续）a=00b=10c=01d=11l=0l=1l=2l=3l=4l=5l=6l=7状态数P.942022/4/1 结论:最后求得的最小汉明距离路径如图中粗黑线表示为: a0b1c2b3d4d5c6a7,最小汉明距离值为2. 卷积码的译码（续）卷积码的译码（续）l=0l=1l=2l=3l=4l=5l=6l=7a=00b=10c=01d=11P.952022/4/1Viterbi 算法算法 由上面的例子可以总结出如下规律: 维特比算法,对于DMC信道(或BSC信道),主要体现在上述格形图中寻找具有最大

49、似然值的路径,具体是采用迭代法进行处理. 即在每一步中,它将进入每一状态的所有路径的度量值进行比较,保存并度量最大度量值(或最小汉明距离值),称为幸存路径,并丢弃其他路径; DMC(或BSC)中viterbi算法可归结为如下三步: 1. 从时刻l=m 开始,(lm为起始状态)计算进入每一状态的单个路径的部分度量值,并存入每一状态下的幸存路径及其度量值. 2. l增加1,即l=m+1,将进入某一状态的分支度量值, 与前一时段的幸存度量值相加,然后计算进入该状态的所有最大度量的路径(或最小汉明距离路径)即幸存路径及其度量,并删去所有其它路径. 卷积码的译码（续）卷积码的译码（续）P.962022/

50、4/1 3. 若lL+m=5+2=7,重复步骤2,否则停止. 上述三个步骤中,1是2的初始化,3是2的延续,关键在于第2步,它主要包括两部分,一是对每个状态进行度量和比较,并决定幸存路径,另一个是记录幸存路径与度量值.上述三步的进一步细化: 1. 从l=m=2时刻开始,使网格图充满状态,将路径存储器(PM)和路径度量存储器(MM)从l=0到l=m=2进行初始化; 2. l=l+1=2+1=3 3. 接收到新的一组数据,它代表l=l+1的分支上接收符号组; 4. 对每一状态: a. 进行分支度量计算; 卷积码的译码（续）卷积码的译码（续）P.972022/4/1 b. 从MM中取出第l时刻幸存路径度量值; c. 进行累加-比较-选择(ACS)基本运算,产生新的幸存路径; d. 将新的幸存路径及其度量值分别存入PM及MM中; 5. 如果lM 的突发差错，经交织后可将长突发差错变成长度为l1= 的突发差错； 3）完成上述交织与去交织变换在不计信道延时条件下，将产生2MN个符号的时延，其中收、发端各占一半； 4）在很特殊情况下，周期为M的k个单独差错，经交织与去交织后将会产生长度为L的突发差错； 为了克服分组交织器的两个主要缺点： 时延大与在特殊情况下，可将周期性单个差错交织成突发差错，人们又提出了卷积交织器与随机交织器，可进一步参见教科书。交织编码交织