说明教案成果

华侨大学通信工程 ： : 上次课循环码C

g1x0C(x)cxn1 C(i)(x)xiC(x)g1x0

g(x)

xnk

h(x)hkxk

xn1g(x)h(x)

xk1g(x) xk2g(x) G(x)

H(x)

h*(x) n

xnk2h*(x)C(x)m(x)x r(x)

xnk1h*(x)r(x)m(x)xnkmodg(x)InInk

g(x)

Hc2xns(x)R(x)modg(x) SRHTc2xn4.3.7常用的循循环冗在数据通信中，信息都是先划分成小块再组装成帧后组包) 的，一般都留有、、或位用作差错校验。k位kn,ki)缩短循环码的特点。只要以一个选定的i,k)循环码为基础，改变i的值得到任何信息这种应用下的缩短循环码称为循环冗 (CRC3循环冗 是系统的缩短循环码，码的结构如图所示(n-i)(k-i)图中，码字用码多项式C(x)表示，r(x)是xnkm(x除g(x)后的余式，g(x)为n-k次多项式，它们之间满足C(x)xnkm(x)r(x) 如果传输过程无差错，则接收码字R(x)应等于发送码C(x)，这时R(x)能被g(x)整除；如果不能整除，则说明输过程中出现了误

C(x)+e(x)=C(x)+eg g g 4.3.7]某g(x)x4x1CxRx解：本题信息码字多项式m(x

1，k=6，从生多项式g(x)的阶数得校验位数r等于4，因此n=10g1x0xnkm(x)g(x)g1x0r(x)xnkm(x)modx4(x5x41)modx3

g(x)

xnk 于是，发送码字多项式C(xxnkm(xr(xx9x8x4x3对应的发送码字为 在接收端，Rxgx不为“0”，则说明一定有差错 例4.3.8假设m(x)x6x4x31，即信息码字为 g(x)x4x31，求 解由题得x4m(x)x10x8x7用g(x)去除 ，有是冗余r(x)所以，发送为6如果本例的发送码字(10110011010)经传输后受噪声在接收端变成为(10110011100)。求余式求得余式不为零，表示接有错误再是C(x)，而C(x)+e(x)。若e(x)g则这种差错就能检测出e(x)g那么由于接收到的码字多项式仍然可被g(x)整除，错误检测不出来，也即发生了漏检 理论上可以证明，循环冗 的检错能力如下 长度n-k的突发错误④n-k+1位的突发性错误，查出概率为1-2-(r-⑤对于多于n-k+1位的突发性错误，查出概率为1-2-r8CRC-12，其生成

g(x)x12x11x3x2xCRC-16，其生成多项

g(x)

x2CRC-CCITT(ITU)，其生成多项式g(xCRC-32，其生成多项

x15x5g(x)

x26x23x22x16x12x11

x8x7x5x4x2x1余 的编译码程通用采硬件实为除法运算易于用移位寄器和2加法来实，可以度。着集电路艺的展环冗余码的产生校均集电产，送能自动成速大大高。9BCHBCHBCH等一系列优点。本原BCH码与非本原BCH二进制本原BCH码具有下n2mnk 2t式中m(3)和纠错能力t(<2m-1)是任意的正整BCH码的码长为n

1n

1的因通常称前者为本原BCH码，称后者为非本原BCH码BCHBCH这里我们重点讨论BCH码的实际应用，即利用已知BCH码表格，构造出对应生成多项式的BCH码表4.4.1(P109)给出的是一些本原BCH码的有关参[例4.3.9m=4n24115的二元BCH解：①若t1，则查表可得g(x)x4x故可构成一个(15,11)BCH码，可纠正单个错误。显然，纠单个错误的本原BCH码就是前面所述的循环汉明码t2，则查表可得其生成多g(x)(x4x1)(x4x3x2x1)x8x7x6x41故可构成一个(15,7)BCH码，具有纠正两个错误的能③若t3，则查表可得其生成多项式g(x)(x4x1)(x4x3x2x1)(x2xx10x8x5x4x2x可构成一个(15,)BCHBCHCRS的情况，得到了RS（Reed-Solomon）码。(n,kRS码中，输入信号分成k*m比特一组，每组包括k个符号，每个符号由m比特组成，而不是前面介绍的二元BCH码中的一个比一个可纠正t个错误的RS码有如下参数码长：n2m信息位：

位符号位符号

(2mk

监督位：nk2t位符m(nk)2mt比特最小码距n2t1位符号 或mdminm(2t1)比特S有：总长度为总长度为

b1(t1)m1b2(t3)m

比特的单个突发错比特的两个突发错误总长度为it2i1)m2i1比特的i个突发错20世纪70 始，RS码在 器、器、DVB(数字电视广播标准)、磁 、光纤信中得到了广泛的应]m=4的RS码的参解：已知t=3，m=4，求码距dmin2t1监督位：nk2t

个符号，或24信息位knnk156

个符号，或36比特码长

n

个符号，或60比特所以该码应为：(1,)S60,36RS码的编码过程与BCH码一样，也是除以同样可以用带反馈的移位寄存器是硬算法，从而造成了一定程度的增益损失。 (J.M.Wozencraft)提出了序列的译 (J.L.Massey)提出效果稍差但卷积码是组码，与分组码的主要差别是它是一种有的编码，即在任意时段，编的nk(L。

Elias,1923-n,N=L1和k可以同的条件下，（较小）。一、卷积 卷积码编码的原理图如图4.4.1所示 卷积码具有以下特点下面，用具体实例说明各种描述方法例4.4.1设二元卷积码的 结构如下图所示，如果输信息流为m(10111)，求 的输出码字序列C1 C2 端)、L=3(即三级移位寄存器)所组成的有限状态的 系。离散卷若输入信息序则对应输出为两个码字C2C2

(c1,c1 (c2,c2 其相应编码由输入信息序列m和编 m m式中“*”表示卷积运算，G1,G2为编 是当输入信息为[1000….]时，所观察到的两个输出序列(2,1,3)卷积码 有L=3级寄存器，其冲激响应至可持续到L+1=4位，由图4.4.4可写出冲激响应G1(1011),G2经 后，两个输出序列合并为一个输出码字序列C(c1,c2,c1,c2 i当输入信息序列为m(10111)，利用离散卷积运算来进行具体的计算。第一路 c1的各位码元值可由式i（P115）计算，为：C1(10111)(1011) 其具体的运算过程10111011011101110111000000m

G1(1011),G2所C1 同理可计算C2 所以，最后(2,1,3)卷积码 输出的码字序列为C(11010001010100生成矩阵上述冲激响应G1G2又称为生成序列，若将该生成序列G1进行交织，并构成如下生成矩阵(L=3时g1g g1g g1g g1g G

g g g g g g g g g1g g1g g1g g1g2 3上述编码方程可改写成如下矩阵C矩阵G称为卷积码的生成矩阵)］显然当输入信息序列为一无限序列时［即m)］生成矩阵则为一个半无限m

g1g g1g g1g g1g G

g g g g g g g g g1g g1g g1g g1g2

3码多项G110111x2x3G211111xx2x3m10111)1x2x3x4则卷积码可以用下列码多项式形C1mG1(1x2x3x4)(1x2x3)1x2x3x4x2x4x5x6x3x5x61x7 C2mG2(1x2x3x4)(1xx2x31xx3x4x5 因而，其输出的码字序列C(11010001010100例4.4.3设二元(2,1,2)卷积码的编 )，求其输出码字序列。则由图4.4.6G1(111)1xx2,G2(101)1如果输入信息流为 )，则其对应的多项式表示式为m1x2x3因此输出的码序列为C1mG1(1x2x3x4)(1xx21x2x22x33x42x51xx4x6 C2mG2(1x2x3x4)(1x212x2x32x4x5 即：C111000011001除了上述三种比较形象的状态图、树图和格图来描述下面，以上述二元（2,1,2）卷积码为例讨论卷积码状态由图4.4.6可知，移位寄存器总的可能状态数为2 22a00,b10,c01,d11来表示表元（1设输入信息序列其状态图可以按以下步骤输输 输输(00)(11)(10)(00)(01)(10)(01)(11)状 输状输输输状树图如果要展示出编的输入、输出所有可能的情况，则可采用树图描述，它是将上述编的状态图按时间展开得到状C(11100001100111 ：：状00”作为树根，对每个时刻可l分为两个分支：当1=0则向上，即“0”1=1则向下，即“1”l1l2下两个分支，并推进到相应的二级节点(l’=2)，依此类推，a,b,,d表示编对于特定输入信息))而经过的状态为(a)bcbddcaa在输入上述特定信息序列时，树图中的路径如粗线所示结构重复性太多 (2,1, 图中实线表示输入为“0入为“1”82发所延伸的树结构完全—任给定一个输入信息序列格图就存一条定如 其输出编码为即为图中粗黑线所表示的卷积码的Trellis若编码信息序列 则编码过程即为在Trellis图上寻找一条路得到C111000011001

格图是研究维特比译码算法的重二、卷积码1967(tb。。维特比算的本依在同刻l=L+1,L+2,…,L+l，对格中相列的每点对应编 中该态，按最大然准比较有以为终点的路径，只保留一条具有大似值或等于最似值的路径保留的路径称为幸存径，而其他径堵，用。保留下幸l=L+l下的一条路径就是所要求的最大似然译码的解。由此可见，维特比算法的主要优使得每次局部都等效于全局最优的一部分，它满足②局部及例4.4.4对最简单的(2,1,2）卷积码，设发送的信息序m

，经过编码后输出的码组(字)为C(111000011001接收到的信号序列为：R(101001011001试用维特比算法译 L=2，对给定的输入信息序列l=5，则l’=l+L+1=8，在图中用l’=0,1,…,7来表示。BS(4.4.6和(4.4.4.4.10和图 R(101001011001

aab1011序号2|输入码距aab002002cbd11111daab0000300003cbd001140011acb11101110cdd110111015序号4|输入daab111011111011bcd1110004111000cab11010141101014dcd001