九章基本信道编码技术说明

1、现代数字通信的两个基本理1、现代数字通信的两个基本理论基础：信息论和纠错编码；2、通信中信源编码，信道编码和数据转换编码常常同时使用；本章介绍信道编码的基本的概念、也介绍最为常用的纠错编码，即分组码，循环码和卷积信道数据信源信数据信道信源分组纠用于纠分组信道编码器的输分组纠用于纠分组信道编码器的输入是一列长度为k的字符序列m，其中字符是信源字符表M中取值miM,m(m0,m1,,mk1i0,1,2,,k信道编码器把输入消息序列映射成由n个信道字符组成的码字ciM,c(c0,c1,c2,,cn1i0,2,,nnk－冗余位长度或称校验码Rnm0,m1,,mk 分组编码二元对T表示码字中符号错误数目P(Tt)二元对T表示码字中符号错误数目P(Tt)Ctpt(1ntP{Tt}1P{TP(Tt)Cpnjj,njE{(TT)2}np(1t 1- P 1 1-信道容 C1H(p)1plogp(1p)log(19.1.3检错是9.1.3检错是指当码字在信道上传输发生错误时，译码器能发现传输有误；纠错则是指译码器能自动纠正这个错误检测错[例9.1.1]3次重复编码，（n3,k1,r2“0”→“000”，“1”→“11纠正纠正错[例9.1.2][例9.1.2]r3的重复码“0”→“000纠正检测“1”→“111自动重发请求（ARQ）在半双工或双自动重发请求（ARQ）在半双工或双工情况下，收端发现有误时，可以通过反向信道对方重发一次，直到正确接收到为止。这种通过检测错误，发而且自动请求重发的通信方式称为ARQ1、等待式p，要成功传送码字，发方平均要发码字码字出错概1N1NN步3、选择性重发最大似然译码和最小Hamming距离译c(c0,c最大似然译码和最小Hamming距离译c(c0,c1,,cn1erc(e1,e2,,en1发送码字接收序列二元错误矢量erci0,1,2,,niiierc(e0,e1,,en10)11)二元对称信mcre信道信道最大后验概率译码ˆargmaxP(ci|ci最大后验概率译码ˆargmaxP(ci|ci最大似然译码准则：cargmaxP(r|ci先等ci|r)P(ci)P(r|ci最大后验概率译码＝最大irc的Hamming距离为d指这两个序列有d位不同dH(rci)序列r和ci两个对于差错概率为p的二元对称信pP(r|c)pd(1logP(r|c)nlog(1p)dp1cargmaxP(r|cicargmindH(r,ci最小Hamming距离与检错、纠错能力最小Hamming距离与检错、纠错能力把二个长度为n的序列uv之间的HammingdH(uv)定义和v之间对应分量取不同值的u定义9.1.1长度为n的分组码C的最小Hamming距离dd dH(ci,cjci,cjC,i分组码的三个最重码字长度n，信息位数目k，最小Hamming距离对于一个k）分组码来说，最小Hamming距d与纠错、检力有如下关定理9.1.1任定理9.1.1任何一个（n,k）分组码，若要在任何码能检测e个随机错误，则要求最小Hamming距离d≥e+1能纠正t个随机错误，则要求d≥2t+1c.能纠正t个随机错误，同时检测出(≥t)个错误，则要求d≥t+e+1[证明§9.2线性分组编码的生成矩阵和校验矩阵线性分组码的基本特§9.2线性分组编码的生成矩阵和校验矩阵线性分组码的基本特征是它具有“线性”的结即两个码字合仍是码字，对于二元码，即两个码字之和仍为码字。可以利用数学工具线性空间来研究线性分组码，使得编码器和译码器的实现更为简单。定义9.2.1一个码率为Rkn的线性分组码（n,k），k比特的消矢量m(m0m1mk1线性地n比特c(c0c1,cn1{0,1j0,1,n1mi{01i0,1,k线性映射c1cm1212mc22全体码字集合称为码字空间C，它n维空间中的一个kg0(g00,g01,,g0,n1g0(g00,g01,,g0,n1g1(g10,g11,,g1,n1gk1(gk10,gk11,,gk1,n1k个线性独立的二元n消息cm0g0m1mk1m所m(m0,m1,,mk1g矩G1 k1[例9.2.1]G生成的（6,3）线 0G 1 cm0g0m1g1m2g2,mi0,1,i1,2,m(01 cg1g2成矩列交GG成矩列交GG系统生成矩阵生成系统线Ikkr=n-k校验k系统线性码的校验H]mGHTcrcHT[例例9.2.1中的（6.3）线性码的校H[例例9.2.1中的（6.3）线性码的校Hm01m2cHTcmm29.2.2u(u0,u19.2.2u(u0,u1,,un1v(vpvr,vn1)内积和uvuvu1v1u和vn维空间中与一个k维子空间正交的所有矢量的全体构成一个n-维空间，它称为的对偶空间，或称的正交补，用C⊥定义9.2.2生成矩阵为G，校验矩阵为H的（n,k）线性分组码CC⊥是一个生成矩阵为H，校验矩阵为G的n–k）线性分组线性分组码的最小Hamming距离和最小Hamming定义9.2.3线性分组码的最小Hamming距离和最小Hamming定义9.2.3一个n维矢量的Hamming重量wH(v)定义为该矢量中非量的个数，对于二元矢量也就是矢量中“1”分量的个c1,c2c1c2因dH(ci,cj)cicci,cjwH(cicj所cicci,cjminwHc线性分组码的最小Hamming距离等于该码中非零码字的最[例由9.2.3中生成矩阵所生成的线性分组码总共有8设cc0c1,cn1ccHcih为Hi设cc0c1,cn1ccHcih为HihhhhhHhhhhk1,n1kkkk012iw，则相w列的和为若码字重量如果一个线性分组码的最小Hamming距离为d，也就是说该最小Hamming重量为d，则它的校验矩阵H中任意d–1线性线性分组码c，从信道接收到的二元矢v发送的二元码字矢，错ev线性分组码c，从信道接收到的二元矢v发送的二元码字矢，错evc(e0,e1,,en1最大似然译码法则要求把v译成与之距离最近的码字。完全译码器把接收到的二元矢量v译成与它最近码字c；限定距离t译码器，选与v最近的码字c，dH(c,v)时，则译器就译成c；当dH(cv)t时，译码器声称纠错失败一、标准阵cc0e2e1c1,e2c1c2e1c2e2c2k2e1k2ck2e c2 2e2e2c2二元 k）线性码C，若二元 k）线性码C，若是任意一个非码字n维矢量，则称的一个陪集，其中aCaccC}为称为陪集意二个倍集或者不相交或者重合，所以标准阵列是线性码的陪集分解v，若它落在标准阵列中的第j行，则可能的对于任何接收到的误形式是该行中的所有矢量，最大似然译码准则要求把与接收矢量近的码字译为发送码字，所以相当于在第j行中为错误形式，即把该行的首项作为错误对于限定矩离译码来说，不需要构造出完整的标准阵列，只需重量不大于的陪集首项所对应的陪集。若接收到的矢量没有出现在这个不完整阵列表中，则说明这时发生了不可纠正的错误。[例一个具有4个码字，能纠错一位的（6，2）线性码C={(000000),(010101),(101010),陪集首[例一个具有4个码字，能纠错一位的（6，2）线性码C={(000000),(010101),(101010),陪集首项重量不大于1的不完全阵列如果一个线性码的标准阵列中的陪集首项正好是所有重量不大元矢量，该线性码称为完备码t的00000010101010111111000000101010101111110000101011101001111000010010001011111101001000111010001110110100000010111011011110000110100010101111 二、伴随式接收矢量v所对应的伴随式s是一个二、伴随式接收矢量v所对应的伴随式s是一个rnk维矢量svHT1、v相应的伴随s为零矢量的充要条件是v为一个码字e0,0,1,0,,,1第c,2、第a第bseihihahbhc则i3、二个矢量出现在的同一陪集中的充要条件是他们具有相同的伴随式所以伴随式与陪集一一对应s如果接收到矢量为v，首先计算出它的伴随式，如，则表示s收到的是码字，没有错。如果不为0，则根查出对应的错误形译码错误概误码M1P{译码输出c|ci被发送M1译码错误概误码M1P{译码输出c|ci被发送M1错误形式陪集首项|}iMiP{错误形式陪集首项n1ipi(1p)i为重量为 的陪集首项数目误比 k9.2.6二元Hamming定义9.2.4长度为n=2r–1（r≥2）的二元Hamming码是一个9.2.6二元Hamming定义9.2.4长度为n=2r–1（r≥2）的二元Hamming码是一个矢量组成[例对于系统（7.4）Hamming码，它的校验矩1011011110000100001000100011101GH011从一个已知线性分组码来从一个已知线性分组码来构造一个新的线性分组码缩短（cn–1HammingHr(2r–1,2r–1–r例（15,11,(2r–1,2r–2–r,4)例（15,10,(2r,2r–1–r,例（16,11,§9.3线性码的纠错能力是由给定n,§9.3线性码的纠错能力是由给定n,k条件下，最小距离d的上，下界限来表征的。下面3个定理给出关于最小距离d的上限。定理（Singleton限任何线性（n,k）码的最小Hammingddnk定理9.3.2（Hamming限长度为n，能 个错误的二元分组码所含有码字数MtM2nC定理（Plotkin限长度为n，码字数为M的分组码，它的最小Hamming距离dd2(M定理（Varsharmov-Gilbert下限可以构成定理（Varsharmov-Gilbert下限可以构成一个最小距离为d的dk）线性分组码，其中参数dnk j2j循环码定义与码字的多项v(v0,v1,,vn1循环码定义与码字的多项v(v0,v1,,vn1,v,v,,) 一个（n,k）线性码定义，若它的每个码字矢量的循环移位是该码的码字，则我们称为循环码[例一个由4个码字构成的，最小重量为3的（6，2）循环C{(000000),(010101),(101010),用多项式表示码字矢v(x)vxv(v,v,,x) 012xv(x)v(1)(x)(xn因v(1)(x)xmod(xn9.4.2定理9.4.1循环码C中次数最低的非零码字多项式是唯一rxxrg9.4.2定理9.4.1循环码C中次数最低的非零码字多项式是唯一rxxrg(x)gx是码C中一个次数最[证明]r01的非零码字多项式。若不是唯一的，则必然存在另一个次数为的码多项式 g'(x)g'0g'1xg'rxrxr由于是线性的，所g(x)g'(x)(g0g'0)(g1g'1)x(gr1g'r1)xr1这与假设g(x)是次数最低非零码字多项式相矛rg(x)g0g1xgr1xr是（nk）循环码C定理g01最低次数非零码多项式，则常数[证明]g0 rg(x)g1xg2x rx(g1g2xgr1rxr1xrggx与假设矛盾所r12xrg(x)gxxrg(x)gxx是（n,k）循环码C定理9.4.3r01次数最低的非零码字多项式，则任何一个次数不大于n–1的二元多项式当且仅当它是g(x)倍式时，才可成为一个码字多项[证明]充分性令v(x)是次数不大于n–1的二元多项式，且是g(x)的倍式v(x)(a0a1xanr1xnr1)g(x)ag(x)axg(x) xnr1g(x) nr上式中的被加项均是码字多项式，所以v(x)必要性是也一个码字多项式是码 中一个码字多项式，用g(x)令得v(x)a(x)g(x)b(x)v(x)a(x)gb(x)次数小于g(x)总结上面3条定理定理9.4.4在一个总结上面3条定理定理9.4.4在一个二元（nk）循环码中，存在唯一的次数为n–k的码字多项式g(x)，使得每个码字多项式都是g(x)的倍式，反之每个次数不大于n–1而且为gx)倍式的多项式均对应于一个码字多项式。所有次数不大于n–1，而且是g(x)倍式的多项式是由一切形xnru(x)uxnr01多项式与g(x)相乘的结果，总共有2n–r个。故2n–r应该等于，即rn。称g(x)为这个k）循环码的生成多项式，u(x)为消息多项式[例9.4.2]由gx1生成的（6.2）循环码的码生成多项式必须满足一些条件生成多项式必须满足一些条件xkgxxkxkxkg[证明nk12xn11xkxn1xknk1b(x)是g(x)连续向右移位k次后所得多项式，故b(x)是一个码字多项式bxuxgx即故1xkgxuxgxxkuxgxg(x是xn1的因式9.4.6若g(x是n–k次多项式，而且是xn1的因式，则g(x生成个（n,9.4.6若g(x是n–k次多项式，而且是xn1的因式，则g(x生成个（n,k）循环码[证明]令g(x)是xn+1的一个次数为n–k的因式，vxagxaxgxxk1gxk01aax xk1k01是一个次数小于或等于（n–1）的多项式，且g的倍式。总共有k个这样多项式。这些多项式组成一个（n,k）线性分组码下面证明这个线性分组码是循环的(x)的一个倍式，xvxvxvx21xnxn01vxk01v1gx,xgx,,xk1gx所以v(1)(x)也是g(x)的倍式。从而(x)也的性组合，所以(x)也是一个码字多项式1可分解成：x[例9.4.3]多项gx1xx3生成的（7,4）循环§9.5系统循环码的编码及译9.5.1在k）系统循环码中 位§9.5系统循环码的编码及译9.5.1在k）系统循环码中 位消息位集中在码字矢量的右侧（最高位）构成系统循环码的步骤如下xk1、用xnk乘以消息多项式m(xmxk01xnkm(x)，得到余b(x)（校验位多项式2、用生成多项式g(x)3、构成码字多项式c(x)xnkm(x；[例9.5.1]考虑由g(x)1xx3生成的（7.4）循环码，消息多项m(x)1xx3，求相应的系统码字多项式xnkm(x)x3m(x)x3x5m(x)g(x)(1xx2x3)12c(x)x3m(x)1x4x53c9.5.2一、多项式c(x)a(x)b)(ab)xb9.5.2一、多项式c(x)a(x)b)(ab)xb0011+多项式a(xb(x)的系数依次从高到低位输入模2加法器，和式的系数从高到低位依次二、多项式+++++c,c,…, a,a,…, ka(x)axb(x)bbxb01k01b)xkrrc(x)a(x)abxk(aa rk1 (a1b0a0b1)xaa)xkr(aba rk rk DDDD多项式乘法的另一种实现电DDDD+++++c,c,…, 多项式乘法的另一种实现电DDDD+++++c,c,…, a0,a1,…,a(x)1xb(x)1x[例c(x)a(x)b(x)1x++DDDD三、多项式g(x)gxd(x)dx01r0nd(x)q(x三、多项式g(x)gxd(x)dx01r0nd(x)q(x)g(x)r(x)0deg(r(x))d0,…,DDDDDD++++++q(x)出现在输出端，寄存器中保存的是余r(x)在n次移位后，商多项。g(x)xd(x)x5x4x3[例x11x7xx3xDDDDDD++++四、乘一个多项式后，再除一个多项式的电路a(x)axkaxkk10h(x)四、乘一个多项式后，再除一个多项式的电路a(x)axkaxkk10h(x)hhxrrxhxa(x)h(x)q(x)g(x)r(x)rr10g(x)grxgxg10rDDDDDD+++++++乘以多项式xx1xxxx1DDDDD+++++x乘以多项式xx1xxxx1DDDDD+++++xx1，再除以xx41的电乘以多项DDDDDD++++++DDDDD9.5.3一个 k）系统循环码的编码过程由三步组成xk1、用x9.5.3一个 k）系统循环码的编码过程由三步组成xk1、用xnk乘以消息多项式m(x)mxk01xnkm(x)，得到余b(x)（校验位多项式2、用生成多项式g(x)3、构成码字多项式c(x)xnkm(x；++++①②门 [例9.5.4]考虑由g(x)1xx3生成的[例9.5.4]考虑由g(x)1xx3生成的（7.4）系统循环码++①输移位寄存器中内000（初始状态110（第一次移位101（第二次移位100（第三次移位100（第四次移位②1101输出完整码字为DDD门循环码的译码及其伴随由于循环码的循环结构，使得伴随式有如下性质s(x循环码的译码及其伴随由于循环码的循环结构，使得伴随式有如下性质s(x是接收多项式r(x)rx定理的伴01g(x)的伴随xs(x)(xr(x)s式，则用生成多项环位移一位r(1)除所得的余xr(x)rn1(xn1)r(1)[证明由r(1)(x)(xn1)故r(x)q(x)g(x)s(x)若r(x)利1h(x)g(x)r(1)(x)h(x)xq(x)]g(x)得r除以g(x)的余式，我们记之为s(1)的伴随式是xs(x)。于类似的，把r(x)r(x)的伴随多项连续循环移位i次，所得的多项s(x除类似的，把r(x)r(x)的伴随多项连续循环移位i次，所得的多项s(x除以g(x)后的余式s(i)(x)++++(i计算接收多项式r(x)以及(x)的伴随式电由g(x)1xx3生成的（7,4）[例门DDD++sn-k-门门循环码的通用译码1、计算接收多项式r循环码的通用译码1、计算接收多项式r(x)对应的伴随s(x)；s(x)，查表寻找对应的错误多项式（陪集首项2、根据伴随3、把接收多项式和错误多项式相加就纠正了相应的错误++ s1梅吉特（Meggitt）错误形式分为二大类E1{梅吉特（Meggitt）错误形式分为二大类E1{e(x)|en1E0{e(x)|en1通过对接收到矢量r(x)对每位纠错目的逐次循环移位，每次检测、纠正首位错误，达门+门+门门门1、缓冲寄存器和伴随式寄存器1、缓冲寄存器和伴随式寄存器清零，门1，门2，门4接通，门3，门52、门1、门2断开，门3、门4、门5接通置i=0，检查伴随式s(x)对应的形式是否属E1，若是则E1错误形式匹配电路输出“1”，否则输出“0”3、i=i+1，缓存器输出最高位缓存内容，与E1错误形式匹配电路输出en-相加，纠正该位接收符号的错误。同时把en-1反馈到伴随式计算与寄路的输入，以消除该位错误对于伴随式的影响。缓存器和伴随寄存器时作一次循环位移，得到新的字(i(x)和它对应的伴随(i)x)4、利用新的伴随式s(i)x)来检查是否与E错误形式相匹配，若是则E11误匹配电路输出“1”，否则输出“0”5、若i=n则译码结束，不然重复第3[例9.5.6][例9.5.6]g(x)1xx3生成的（7,4）循环码，这个码的最小对应的伴随式示于下E1{e6E0{e0(x),e1(x),e2(x),e3(x),e4(x),e5+门DDD++门门DDDDDDD门门+门DDD++门门DDDDDDD门门§9.69.6.1Hamming循环由GF(2)上m次本原多项式生成的长度1(m的循环码(2m1,21m)Hamming对所有§9.69.6.1Hamming循环由GF(2)上m次本原多项式生成的长度1(m的循环码(2m1,21m)Hamming对所有i0,12,2m2m，用生成多项g(x)xmia(x)g(x)b b(x) i x ci(x)1这m)码字线性独立，故这些码字构成生成矩阵bbbbbbbb10001001bbbbGbbb00mmmm2222010000bbb2m0bbbH2010000bbb2m0bbbH2m001bm 可以证明中无全零列矢量，无二列矢量相同，故可纠正全部一位错误生成多项式的表示：常用八进制数字表示生成多项式；g(x)x3xg(x)x4xg(x)x7x3八进制八进制八进制二进制00101二进制01001二进制010001009.6.2BCH2m1），存在具有如下参数的9.6.2BCH2m1），存在具有如下参数的BCH对于任何正整mt（1、码长n2、校验位数目nk3、最小距离d2tBCH码的生成多项式的构成是GF(2m)的本原元，考虑的如下幂序列,2,3,4,,的最小多项式，则满足所列参数要求的im令是码生成多项式ig(x)LCM[m1(x),m2(x),m3(x),,m2t利用共轭元具有相同最小多项式的特点，则生成多项式可以写成g(x)LCM[m(x),m(x),, 2t[例9.6.1]在GF[24]上构造长度为 1[例9.6.1]在GF[24]上构造长度为 115，分别能纠一位和两位错误BCH长度为15的能纠一位错误的BCH码的生成多项式以1和2为根g(x)(x1)(x2)(x4)(x8)xgx)的八进制表示为“23”；生成(15，11)Hamming码x长度为15，能纠正二位错误的BCH码的生成多项式以1 ,324g(x)(x1)(x2)(x4)(x8)(x3)(x6)(x12)(x9(x4x1)(x4x3x2x1)xxxxg()的八进制表示为“723”；生成(15，7)BCH码，能纠正任意二位错误9.6.3Reed-Solomon(R-S)RS码是一类非二进制9.6.3Reed-Solomon(R-S)RS码是一类非二进制的BCH码，具有很强的纠错能力。RS码的码元的符号域和根域相同。能纠正t个错误的R-S码具有如下参数：nq码长校验位数目nk最小距离：d2tR-S码的最小距离为校验位数目加1，达到了Singleton限界当q2m，RS码的码元符号取自GF(2m，码字长度为n1。一能纠位符号错误的RS码的生成多项式g(x)(x)(x2)(x3)(x2t为GF(2m)的本原元其[注意GF(2m)中元素可用长度为m的二元矢量表示，长度为的字用二进制符号表示长度为m(2m1)，能纠正mt个二进制符号错[例一个符号取自GF（23），长度为7，能纠正2个八进制错误的码的生成多项式为g(x)(x)([例一个符号取自GF（23），长度为7，能纠正2个八进制错误的码的生成多项式为g(x)(x)(x2)(x3)(x4)3xx23x3x的根。信息位长度为3，监督位长度为4其为本原多项m(x)ii，系统码x对于消息多项ic(x)3xx23x3x0c(x)6xx22x3c1(x)x 2542 601000001311110010101G生成矩阵00101H校验矩阵用二元矢量来表示GF用二元矢量来表示GF(23信息位长度为9比特。例如m(6,5,2的元素，则（7,3）RS码字长度为21c(6,5,2)G(10,8,4,0,6,5,2(3,2,4,0,6,5,2c(110,001,011,000,101,111,对于BCH码和RS码的译码，已经有一些很有效的代数算法，纠错§9.7§9.7不仅和当前的一组k个输入比特有关，而且和以前M个时刻的输入组Rk/关，所以卷积码可用参数组（nkM）来描述。编码速对于卷积码来说，约束长度KM1也是一个重要参数。卷积码的构成和代M级数据帧移位寄存器(kM比特k kn123…M[例]（2,1,2）卷积码编码器+(v(1),v(1),v(1)012m[例]（2,1,2）卷积码编码器+(v(1),v(1),v(1)012m(v(2),v(2),v(2)v(2)+012一、卷积码编码器的冲击响应和生成矩长度)时，系统输出序列冲激响应是当系统输入序列为m0010上例中两个冲击响应为mm二个输出编码序列模2卷积运v(2)mg(jmi1,v(jg(jg(jg(j)l l l l DDg(1)g(2)g(1)g(2)g(1)g(2)g(1)g(2)00112233g(1),g(2)g(1)g(2)g(1)g(2)g(1)g(2)g(1)g(2)00112233g(1),g(2)g(1)g(2)g(1)g(2)g(1)g(2)00112233Gg(1)g(2)g(1)g(2)g(1)g(2)g(1)g(2)00112233vm编码方程[例]（3,2,1）卷积码编码器+21g(2)21mv2D+21m2v+g(1)[例]（3,2,1）卷积码编码器+21g(2)21mv2D+21m2v+g(1),g(2),gg(1),g(2),gg(1),g(2),gg(1),g(2),g (1),g(2),gg(1),g(2),gg(1),g(2),gg ,g(2),gg g(1),g(2),gg(1),g(2),gg,g(,gG1,M 1,M 1,M g(1),g(2),gg(1),g(2),gg ,g( ,g2,M 2,M 2,M vmDv(1)m(1)g(1)m(2) v(2)m(1)g(2)m(2)g(2) v(3) m(1)g(3)m(2) Gm(11,vmG(011,二、卷积码编码器的多项用多项式表示输入、输出、和冲击响应序列m(i)(x)m二、卷积码编码器的多项用多项式表示输入、输出、和冲击响应序列m(i)(x)m(i)m(i)xm(i)x2 012v(j)(x)v(j)v(j)xv(j)x2 j1,2,012g(j)(x)g(jg(j)xg(j)xMii输入、输出关系v(1)(x)m(1)(x)g(1)(x)m(2)(x)g(1)12v(2)(x)m(1)(x)g(2)(x)m(2)g(2)12v(3)(x)m(1)(x)g(3)(x)m(2)(x)g(3)12矩阵表示输入、输出关系v(1)(x),v(2)(x),v(3)(x)(m(1)(x),m(2)(x))g(1)g(2) g(3)(x)G(x)111g(1)g(2) g(3)(x) 21卷积码的图描述和 S0一、卷积码的树图 0 1 3S0 卷积码的图描述和 S0一、卷积码的树图 0 1 3S0 S1Sm(1101002 S0S1S2S3二、卷二、卷积码的网格状态S0出发，输入序列mS0S1S3S2S1S2S0三、卷积码的状态卷积码编码器是一个有三、卷积码的状态卷积码编码器是一个有限状态机，因此可以用状态转移图来描述（2,1,2）卷积码对应的状m(110100从S0状态出发，卷积码的重线性分组码中，码字重量分布对于分组卷积码的重线性分组码中，码字重量分布对于分组码的性能有重要的影响ig“1”SSSE012修正状态转移2、每条路径的总增益等于沿此路径的各分支增益之积，相应的码字等于路径增益中的幂次用状态变量Z0，Z1，Z2，Z3，ZE分别表示从S0出发用状态变量Z0，Z1，Z2，Z3，ZE分别表示从S0出发，终止于S3和E的所有路径增益和D2ZZ102DZ1DZDZ1DZD22ZZZT(D) 1D5(12D4D2Dl1D52D64D78D8从重量分布公式可见，重量为(l5)在分支增益上添加其它的因子，还能获得非零码字的其它结构信息。分在分支增益上添加其它的因子，还能获得非零码字的其它结构信息。分支增益中因子N的指数j表示相应输入k个比特消息的重量（输入据中“1”的个数），另外每个分支增益中增加一个因子L，表示一个j长度SSSE012含有输入重量、输出重量和支长度信息的修正状态转移D5L3T(D,L,N)ZE/1DL(1D5L3ND6L4(1L)N2D7L5(1L)2NNlDl5Ll3(1Z1D2 Z2DLZ1DLZ DNLZ D2LZ 9.7.49.7.4输入信息比特错误+m+E恶性码例DD卷积卷积码的Viterbi译码算Viterbit算法等价于在加权图上求最短路径；Viterbi算法是卷积码的最似然译码算法考虑图9.7.2所示的(2,1,2)卷积码，它的生成多项式矩阵G(x)(1xx2,1x2编码器状态从S0起始，并回到S0。前面M个时刻，对应于起始阶段；而后M编码器状态从S0起始，并回到S0。前面M个时刻，对应于起始阶段；而后M个时刻，通过输入M个“0”，使译码器返回S0mivj长度为kL的消息序m(m0m1,mL1v(v0,v1,,vLM1r(r,r,,rn)接收到序列LM jYY二元硬判决信道高斯信道vr在接收时，发送序的似然函数LMLMP(r|v)logP(r|v)log|viP(ri|vi最大似然估计码字序为ˆargmaxlogP(r|LMlog路径v的度量(r|□logP(r||viiLM(ri|viLMlog路径v的度量(r|□logP(r||viiLM(ri|vi(ri|vilogP(ri|vi分支度量所以一条路径的度量为该路径上各分支度量之和一条路径前l个分支所构成的部分路径度量表示为l(r|(r|vl10ii1、硬判决P(r|v)(1pdiiip(r|v)dnlog(1p)iii1ipLMLM(r|v)(ri|vi)di(LMp最大似然译最小Hamming距离译2+EErixinini1,xini2,,xin2+EErixinini1,xini2,,xinninxEn1|x)P(r|v)iiii2jnD常nn(ri|vi)logP(ri|vi)C jLMn(r|v)xijD(LM选互相关最大的路最大似然译Viterbi译码rViterbi译码r(00,01,10,00,00,00,m(0,0,0,0,0,0,接收序列最后幸存路判定发送序列以作为前向动态规划解的ViterbiM）卷积码为例，说明Viterbi算法是在加权网格以作为前向动态规划解的ViterbiM）卷积码为例，说明Viterbi算法是在加权网格图上寻找最路径值的前向动态规划解卷积码编码器输入序列m(m0,m1,m2mi编码器具有M个寄存器，在tkT时刻编码器状态),,,kkkkkT时刻编码器输出码字 f(mk,k))f(mk,mk1,,mk状态转移kkLM(r|v)(ri|viLM[ri|f(mi,mi1,,限定路径起始于全零状态，最后终止于全零状态，m1 mM限定路径起始于全零状态，最后终止于全零状态，m1 mMmL1mLM最大似然译码就是在网络图上寻找一条满足初始和终止条件的路,0,m,m,,MML01L1使得路径度量值为最大LM[ri|f(mi,mi1,,miMJjJk(k)Jk(mk1,mk2,,mkMk1[r|f(m,,,iiiiikM{mj递归计算Jk1(k1)Jk1(mk,mk1,,mkM递归计算Jk1(k1)Jk1(mk,mk1,,mkM1[ri|f(mi,mi1,,miMkk|f(mi,mi1,,miM)]{mjk1}kMj[rf(m,,,kkkkmaxJk(mk1,mk2,,mk)[rk|f(mk,,mkmkmaxJk(mk1,,mkM1,0)[rk|f(mk,,mkM1,,1)[r|f(m,, ,,kkMkMkkJ0(00)J0[0(0,0,,0)]J0(00)初始条件为对于二元对称信道 min， ，(ri,vi)dH(ri,vi实现Viterbi译码算法的一些实现Viterbi译码算法的一些具体一、译码器存贮器数在Viterbi译码中，对每个状态必须提供存贮器来寄存幸存路径及其度量状态数M指数地增长，一般M取10左右二、路径存贮的截截短译码器的路径存贮：对每条幸存路径只寄存其最个消息据，其中L。译码器处理了接收序列的组数据后，译码贮器就满了，必须作出强制性判决，确定第一个消息数据比特，在任何时刻k(k)，强制性判决可以有下面3种可能方1、在2M条幸存1、在2M条幸存路径中，任选一条，并把该路径中第时刻（即退时刻）的消息数据为译码输出比特2、在2M个可能的第(k)时刻消息数据中选一个出现次数最多的数为译码输出比3、 时刻条幸存路径中，具有最大部分路径度量的那一条的(k时刻消息数据作为译码输出比特状态同步译码器可能从一个未知的编码状态开始工作，或者说译码器在开始工作时，可能处在任何一个状态中；译码器的所有状态寄存器，必须都初始on比特同步位同步错误，则所有幸存路径的度量没有明显差别，以此作同步识别四、分四、分支度量的量化精在软判决信道上卷积码译码比硬判决信道具有性能上优越，一般信输出量化电平数越多，性能越好；但8电平（Q=8）量化所得的性能无量化理想情况下性能仅相差无几(0.25dB)9.8.4卷积码Viterbi译码输出序列中平均9.8.4卷积码Viterbi译码输出序列中平均错误比特Pb总的传输比特数一、节点错误概图中横贯全零状态的全零路，代表正确路；下面实线通路是由tri算法所选择的，译码器输出路径。它和正确路有不重合的地方，表明出了错误。按tri算法，在这些不重合的路径片段上正确路所积累的路径度量小于不正确路径的路径度量积累。我们把这种错误称为发生在节点i，j和k上的节点错误。在节点j出现节点错误的必要，但并非充分的积累了更大的路径度量jikj上的节点错误概[(r|v')j上的节点错误概[(r|v')(r|v'V'(jV'(Pr{(r|v')(r|Pe(j)v'V'(j可以证明成对错误概率为Pr{(r|v')(r|v)}P0(r)P1(r)ZZP0(r)1(r)，P0(r)P(r|v0)1(r)P(r|vrddH(v,v')wH(vddPr{(r|v')(r|Pe(j)所v'Bd(jddA(d)Z其中Bd(