《信道编码(中).ppt》由会员分享，可在线阅读，更多相关《信道编码(中).ppt（85页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章第三章 信道编码信道编码 3.4 循环码循环码本节的主要内容本节的主要内容v 码多项式码多项式v 循环移位的数学表达循环移位的数学表达v 循环码的生成多项式循环码的生成多项式v 循环码的编码循环码的编码v 循环码的译码循环码的译码v 编、译码的电路实现编、译码的电路实现循环码：循环码：cyclic code 码多项式：码多项式：code polynomial生成多项式：生成多项式：generator polynomial求模运算：求模运算：modular arithmetic系统码：系统码：systematic（regular）code循环移位运算：循环移位运算：cycle shift
2、operation外外语语关关键词键词上节回顾：线性分组码上节回顾：线性分组码基本概念基本概念：表达方式：表达方式：(n,k)码，码，k是信息位数，是信息位数，r是监督位数，是监督位数，n=k+r是码长。是码长。编码：编码：已知信息已知信息K（k位二进序列），求相应码字的方位二进序列），求相应码字的方法是法是 C=KG，G叫生成矩阵，是叫生成矩阵，是k行行n列的，列的，一般一般G具具有有Ik Q的形式，的形式，Ik 是是k行行k列单位方阵，列单位方阵，Q是是k行行r列的列的矩阵。矩阵。生成矩阵的设计，应使许用码字之间的最小汉明距生成矩阵的设计，应使许用码字之间的最小汉明距离尽量地大。离尽量地大
3、。译玛：译玛：当收到码字当收到码字R时，首先计算伴随子向量：时，首先计算伴随子向量：S=RHT；若若S=0，则，则R=C为正确码字；若为正确码字；若S 0，则，则RC为错误码为错误码字。字。这里这里H叫一致监督矩阵，是叫一致监督矩阵，是r行行n列的。一般列的。一般H具有具有 P Ir 的形式，的形式，Ir 是是r行行r列单位方阵，列单位方阵，P是是r行行k列的矩阵，列的矩阵，P与与Q互为转置关系互为转置关系。纠正纠正1位错：位错：当当S 0时，由时，由S=RHT 求出求出S，比较，比较S 与与HT，HT的那一行与的那一行与S相同，相应的错误格式向量相同，相应的错误格式向量E的那的那一位就等于一
4、位就等于1，于是，于是R的那一位就是错误的。最后根据的那一位就是错误的。最后根据 C=RE进行将其纠正。进行将其纠正。纠正多位错错：纠正多位错错：当当S 0时，根据时，根据S=RHT=EHT，可以预先由可以预先由S=EHT计算出各种错误格式计算出各种错误格式E所对所对应的伴随子向量应的伴随子向量S，得到，得到ES对照表。查表就能找对照表。查表就能找到接收码字到接收码字R（即（即S=RHT）所对应的）所对应的E。纠错能力不等式：纠错能力不等式：2r Cno+Cn1+Cn2+Cnt这是因为伴随子这是因为伴随子S是是1行行r列的向量，它有列的向量，它有2r 种不同种不同的状态，除了用全零态表示正确码
5、之外，最多只的状态，除了用全零态表示正确码之外，最多只能区别开能区别开2r1种不同的错误格式。种不同的错误格式。引言：引言：构造线性分组码关键是设计出一个好的生成构造线性分组码关键是设计出一个好的生成矩阵，使所有码字之间的汉明距离尽量大。怎矩阵，使所有码字之间的汉明距离尽量大。怎样找这样的矩阵呢？循环码的出现提供了一整样找这样的矩阵呢？循环码的出现提供了一整套理论和方法，使人们能够借助数学工具来寻套理论和方法，使人们能够借助数学工具来寻找更好的线性分组码，并由此引发出一大类很找更好的线性分组码，并由此引发出一大类很常用检、纠错编译码。常用检、纠错编译码。3.4 循环码循环码上节讨论过上节讨论过
6、(7,3)(7,3)线性分组码线性分组码:C0=(0000000);C1=(0011101);C2=(0100111);C3=(0111010);C4=(1001110);C5=(1010011);C6=(1101001);C7=(1110100);不难发现它们具不难发现它们具有循环移位特性：有循环移位特性：C0=(0000000);C1=(0011101);C3=(0111010);C7=(1110100);C6=(1101001);C5=(1010011);C2=(0100111);C4=(1001110);循环码是线性分组码中的一个子集。循环码是线性分组码中的一个子集。对于循环码，有了一
7、个的码字，按循环移对于循环码，有了一个的码字，按循环移位规律就能写出位规律就能写出n个码字。从中选出个码字。从中选出k个个来构造生成矩阵来构造生成矩阵G，就能生成全部，就能生成全部2k个许个许用码字。用码字。循环码与近代数学有密切联系。使我们可循环码与近代数学有密切联系。使我们可以借助数学工具来设计编码。以借助数学工具来设计编码。3.4.1 3.4.1 码多项式码多项式二进制自然码可表达为以二进制自然码可表达为以2 2为底的多项式表达，如：为底的多项式表达，如：C=(1010111)=126+025+124+023+122+121+120；把底换为把底换为x，则得到，则得到“码多项式码多项式”
8、：C(x)=1x6+0 x5+1x4+0 x3+1x2+1x1+1x0 =x6+x4+x2+x+1 码长为码长为n时，可写时，可写：C(x)=cn-1 xn-1+cn-2 xn-2 +c1x1+c0 x0 如三位二元码的如三位二元码的8个码字对应的码多项式为：个码字对应的码多项式为：000，001，010，011，100，101，110，111；0，1，x,x+1,x2,x2+1,x2+x,x2+x+13.4.2 3.4.2 循环移位的数学表达循环移位的数学表达对二进数，左移一位相当于乘以对二进数，左移一位相当于乘以2，而将最高位的进位，而将最高位的进位(2n位位)上的数码拿回到上的数码拿回到
9、20位，叫做循环移位，位，叫做循环移位，相当于作相当于作模模2 2n n -1-1运算。运算。如：如：1011010011 1011010011 实际是实际是 5 52 mod 7=3 mod 7=3码多项式的码多项式的循环移位，实际是乘循环移位，实际是乘x后作模后作模 xn-1运算运算。如：如：1 1100010 100010 1 11000101000100 0 100010 1000101 1 (x6+x5+x)x(x6+x5+x)mod (x7-1)=(x7+x6+x2)mod(x7-1)=x6+x2+1（7,4）循环码及其码多项式的循环移位：循环码及其码多项式的循环移位：循环次数循环
10、次数循环码循环码码多项式码多项式模模x7-1运算后运算后 0 0001011x3+x+1x3+x+110010110 x(x3+x+1)x4+x2+x20101100 x2(x3+x+1)x5+x3+x231011000 x3(x3+x+1)x6+x4+x340110001x4(x3+x+1)x5+x4+151100010 x5(x3+x+1)x6+x5+x61000101x6(x3+x+1)x6+x2+13.4.3 3.4.3 循环码的生成多项式循环码的生成多项式(1)(1)生成多项式的定义和特点生成多项式的定义和特点循环码的码多项式中幂次最低的非零多项式叫做生成多循环码的码多项式中幂次最低
11、的非零多项式叫做生成多项式，记做项式，记做g(x)。如如(7,4)码的码的x3+x+1。有了它，有了它，其它码其它码字都可由字都可由xi g(x)的模的模 xn-1-1得到。得到。生成多项式的常数项为生成多项式的常数项为1。否则，通过循环移位还能继续否则，通过循环移位还能继续降低幂次，它就不是幂次最低的多项式了。降低幂次，它就不是幂次最低的多项式了。生成多项式的幂次为生成多项式的幂次为r。因为因为幂次最低的码多项式是幂次最低的码多项式是信息信息为为0001,后面跟上后面跟上r个监督位的那个码字所对应的码多个监督位的那个码字所对应的码多项式，它的最高位是项式，它的最高位是 xr，是，是r次的次的
12、多项式多项式。(2)(2)生成多项式的两个性质：生成多项式的两个性质：1任意码多项式任意码多项式T(x)都是生成多项式都是生成多项式 g(x)的倍式的倍式。证明：（证明：（n,k）循环码作为线性分组码，其生成）循环码作为线性分组码，其生成矩阵矩阵G是是k行行n列的，可由列的，可由k个不同的码字构成：个不同的码字构成：任给一个信息码任给一个信息码K=(cn-1cn-2cn-k)，利用生成，利用生成矩阵和公式矩阵和公式C=KG，不难求出它对应的码字，不难求出它对应的码字 T(x)=KG=(cn-1cn-2cn-k)=（cn-1xk-1+cn-2xk-2+cn-k）g(x)；即：即：T(x)=h(x
13、)g(x)；表明任意码多项式表明任意码多项式T(x)都应能被都应能被g(x)整除整除。2生成多项式生成多项式g(x)是是 xn-1的一个因式的一个因式。证明：因为证明：因为g(x)循环左移循环左移k位位,即即g(x)乘以乘以xk后再作后再作模模xn-1-1运算运算,应当仍为一个码多项式。应当仍为一个码多项式。xk g(x)为为n次多项式，除以次多项式，除以xn-1的商式必为的商式必为1 1，设余式为设余式为T T(x),),于是有：于是有：移项即证得：移项即证得：xn-1=g(x)xk h(x)；即：即：xk g(x)=xn-1+T(x)=xn-1+h(x)g(x)（3 3）生成多项式）生成多
14、项式g(x)的的确定：确定：由性质由性质2 2知，知，g(x)是是xn-1的一个因式的一个因式。可。可根据设根据设定的码长定的码长n和监督位和监督位r，将将xn-1因式分解，从中选择因式分解，从中选择一个一个r次的因子作为次的因子作为g(x)。例如：例如：(7,4)码，码，n=7，k=4，r=3；分解：分解：x7-1=(x-1)(x3+x+1)(x3+x2+1)g(x)应应是是x7-1 的的一一个个r=3次次的的因因子子，可可取取为为：g(x)=x3+x+1 或或 g(x)=x3+x2+1；二者任选其一，一旦选定，就不再考虑另一个了。二者任选其一，一旦选定，就不再考虑另一个了。插件插件1：查表
15、分解查表分解x xn n-1-1的方法的方法（1）并非所有的）并非所有的xn-1都具有都具有r次的既约次的既约(不能再分解不能再分解)的因式。的因式。但只要满足但只要满足n=2r-1，xn-1就具有就具有r次的既约因式。因此次的既约因式。因此P194页表页表4中只列出满足中只列出满足n=2m-1的的xn-1的分解情况。的分解情况。（2）不论）不论n取何值，取何值，xn-1总有一个总有一个m0(x)=x+1的因式。的因式。（3）xn-1其它因式是其它因式是mi(x),i=1,3,5,7（4）mi(x)的表达由的表达由8进制数给出进制数给出，将它换成二进制自然码就，将它换成二进制自然码就是是mi(
16、x)各位的系数。如各位的系数。如m=5阶时，阶时，n=31，可分解，可分解x31-1为为：第第i=1类因式查表得到类因式查表得到(45)8=(100101)2，表示，表示m1(x)=x5+x2+1；第；第i=3类因式查表得到类因式查表得到(75)8=(111101)2，m3(x)=x5+x4+x3+x2+1；第；第i=5类因式查表得到类因式查表得到(67)8=(110111)2，m5(x)=x5+x4+x2+x+1；（5）表中并未列出）表中并未列出xn-1所有的因式，所有的因式，与已列出因式对偶的因与已列出因式对偶的因式式都被省略了都被省略了。所谓对偶指的是将二进制自然码高低位倒置的。所谓对偶
17、指的是将二进制自然码高低位倒置的表达，如：表达，如：与与(100101)2对称的是对称的是(101001)2，表示，表示m15(x)=x5+x3+1；与与(111101)2对称的是对称的是(101111)2，表示，表示m7(x)=x5+x3+x2+x+1；与与(110111)2对称的是对称的是(111011)2，表示，表示m11(x)=x5+x4+x3+x+1；值得注意的是，有的二进制自然码本身就是对称的，如：值得注意的是，有的二进制自然码本身就是对称的，如：(11111)2与与(10001)2，高低位倒置后不变，高低位倒置后不变,不会出现新的因式。不会出现新的因式。（6）xn-1分解为以上因
18、式之积，诸因式中幂次最高为分解为以上因式之积，诸因式中幂次最高为r。（7）类序号类序号i与与n互素的那些因式互素的那些因式mi(x)被称为本原多项式；类被称为本原多项式；类序号序号i与与n可约的那些因式可约的那些因式mi(x)被称为非本原多项式。如果被称为非本原多项式。如果n为为素数，所有的因式都是本原多项式。素数，所有的因式都是本原多项式。例例查表分解查表分解x63-1因为因为26-1=63，所以应查，所以应查P194页表页表4中中m=6阶阶。i=1：(103)8=(1000011)2，得知，得知m1(x)=x6+x+1；由对偶式由对偶式(1100001)2和和187页表得知页表得知m31(
19、x)=x6+x5+1；i=3：(127)8=(1010111)2，得知，得知m3(x)=x6+x4+x2+x+1；由对偶式由对偶式(1110101)2和和187页表知页表知m15(x)=x6+x5+x4+x2+1；i=5：(147)8=(1100111)2，得知，得知m5(x)=x6+x5+x2+x+1；由对偶式由对偶式(1110011)2和和187页表知页表知m23(x)=x6+x5+x4+x+1；i=7：(111)8=(1001001)2，得知，得知m7(x)=x6+x3+1；对偶式还是自己。对偶式还是自己。i=9：(015)8=(1101)2，得知，得知m9(x)=x3+x2+1；由对偶
20、式由对偶式(1011)2和和187页表知页表知m27(x)=x3+x+1；i=11：(155)8=(1101101)2，得知，得知m11(x)=x6+x5+x3+x2+1；由对偶式由对偶式(1011011)2和和187页表知页表知m13(x)=x6+x4+x3+x+1；i=21：(007)8=(111)2，得知，得知m21(x)=x2+x+1；其对偶式仍是自己；其对偶式仍是自己；最终结果：最终结果：1）x63-1=m0(x)m1(x)m3(x)m5(x)m7(x)m9(x)m11(x)m13(x)m15(x)m21(x)m23(x)m27(x)m31(x)；2)本原多项式是本原多项式是m1(x
21、),m5(x),m11(x),m13(x),m23(x)和和m31(x)；(1)(1)循环码的生成矩阵循环码的生成矩阵求出了生成多项式求出了生成多项式g(x)，等于得到了一个码字，通过循，等于得到了一个码字，通过循环移位不难得到其它码字。环移位不难得到其它码字。果然如此简单吗？果然如此简单吗？实际上，通过循环移位最多可写出实际上，通过循环移位最多可写出n个码字，得不到全个码字，得不到全部码字，因为部码字，因为(n,k)码应当共有码应当共有2k个许用码字。个许用码字。例如例如(7,4)循环码共有循环码共有1616个许用码字。个许用码字。取取g(x)=x3 3+x+1+1，等于知道了中信息，等于知
22、道了中信息K=(0001)=(0001)所对应所对应的那个码字：的那个码字：C1 1=(=(0001 0001 011)011)。3.4.4 3.4.4 循环码的编码循环码的编码C1 1经过循环移位只能得到经过循环移位只能得到7 7个码字：个码字：序号序号 信息位信息位 许用码字许用码字 C1 0001(0001 0001 011)011)C2 0010 0010 （0010 0010 110110）C5 0101 0101 （0101 0101 100100）C11 1011 1011 （1011 1011 000000）C6 0110 0110 （0110 0110 001001）C12
23、1100 1100 （1100 1100 010010）C8 1000 1000 （1000 1000 101101）（7,47,4）共有）共有1616个许用码字，还缺个许用码字，还缺 9 9个。个。从循环组中随便取从循环组中随便取4个许用码字，比如前个许用码字，比如前4个，用它们个，用它们构成的生成矩阵为构成的生成矩阵为G1：再利用再利用C=KG1 就能求得全部许用码字。就能求得全部许用码字。比如：比如：(0100)(0100)G1=(0101100);(1000)(1000)G1=(1011000);然而发现码字然而发现码字不具备信息位在前，监督位在后的形式。不具备信息位在前，监督位在后的
24、形式。原因是原因是G1不不具备具备G=Ik Q的形式，这样编码叫的形式，这样编码叫非系统码，非系统码，非系统码在译码时是比较困难的。非系统码在译码时是比较困难的。实际上，为了构造实际上，为了构造G=Ik Q形式的生成矩阵形式的生成矩阵。需要如下的需要如下的4个码字：个码字：1000010000100001才能排列出才能排列出44的单位矩阵的单位矩阵Ik。通过对通过对C1=(0001 0001 011)011)的循环移位可以得到的循环移位可以得到 （0010 0010 110110）和（）和（1000 1000 101)101)，但是却无法得到但是却无法得到(0100)011110101原因何在
25、？原因何在？原来原来0100所对应的码字所对应的码字（0100 0100 111)111)位于位于另一循环组中另一循环组中:第一循环组第一循环组 第二循环组第二循环组 序号序号 信息信息 许用码字许用码字 序号序号 信息信息 许用码字许用码字 C1 0001（0001 011)0001 011)C4 0100（0100 111)0100 111)C2 0010 0010（0010 1100010 110）C9 1001 1001（10011001 110110）C5 0101 0101（0101 1000101 100）C30011 0011（0011 1010011 101）C11 1011
26、 1011（1011 0001011 000）C70111 0111（0111 0100111 010）C6 0110 0110（0110 0010110 001）C141110 1110（11101110 100100）C12 1100 1100（11001100 010010）C131101 1101（11011101 001001）C8 1000 1000（1000 1011000 101）C101010 1010（10101010 011011）第三循环组第三循环组 第四循环组第四循环组 C0 0000 0000（0000 0000000 000）C151111 1111（111111
27、11 111111）直接写不出系统码生成矩阵直接写不出系统码生成矩阵，但但可以经过线性变换，可以经过线性变换，将将G1最下行加到第二行上，将最下面两行加到第一行上，最下行加到第二行上，将最下面两行加到第一行上，也能得到也能得到Ik Q的形式的形式的系统码生成矩阵的系统码生成矩阵G:非系统码非系统码生成矩阵生成矩阵系统码系统码生成矩阵生成矩阵线性线性变换变换得到了系统码生成矩阵，就可以用得到了系统码生成矩阵，就可以用C=KG得到所有码字。得到所有码字。（2 2）直接计算系统码的监督元）直接计算系统码的监督元:以以(7,4)码为例，设信息位为码为例，设信息位为k3 k2 k1 k0，对应的多项式，
28、对应的多项式为：为：k(x)=k3x3+k2x2+k1x+k0；设监督位为设监督位为r2 r1 r0，监督位对应的多项式为，监督位对应的多项式为:r(x)=r2x2+r1x+r0；系统码系统码码字码字C=(k3 k2 k1 k0 r2 r1 r0)对应的码多项式为对应的码多项式为:C(x)=k3x6+k2x5+k1 x4+k0 x3+r2 x2+r1 x+r0；=x3(k3x3+k2x2+k1x+k0)+(r2x2+r1x+r0)=x3 k(x)+r(x)推广到一般，码多项式可写为为：推广到一般，码多项式可写为为：C(x)=x r k(x)+r(x)-(1)根据生成多项式根据生成多项式性质性质
29、1，任何码多项式一定能被，任何码多项式一定能被g(x)整除整除：C(x)mod g(x)=0即：即：x r k(x)mod g(x)+r(x)mod g(x)=0；移项，并考虑到模移项，并考虑到模2运算可把负号变正号，于是：运算可把负号变正号，于是：r(x)mod g(x)=x r k(x)mod g(x)；因为因为r(x)是是r-1次多项式，次多项式，g(x)是是r 次多项式，所以次多项式，所以r(x)mod g(x)=r(x)得到直接得到直接计算系统码码字监督多项式的公式是计算系统码码字监督多项式的公式是：r(x)=x r k(x)mod g(x)-(2)再由公式再由公式(1)就得到了相应
30、的码字。就得到了相应的码字。例例1求求(7,4)循环码中信息位循环码中信息位K=(0100)对应的码字：对应的码字：解：解：k(x)=x2,r=3,xr k(x)=x5,g(x)=x3+x+1；由由(2):r(x)=x5 mod x3+x+1=x2+x+1；由由(1):C(x)=xr k(x)+r(x)=x5+x2+x+1；C=(0100111)；同法可得到所有同法可得到所有16个信息个信息(00001111)的码字。的码字。小结：循环码的编码步骤：小结：循环码的编码步骤：1、确确定定(n,k)循循环环码码的的生生成成多多项项式式：将将xn-1分分解解因因 式，从中选择一个式，从中选择一个r次
31、的因子作为次的因子作为g(x)。2、根据信息、根据信息K，由由r(x)=x r k(x)mod g(x)计算计算出它的监督位。出它的监督位。3、由、由 信息位信息位+监督位监督位 直接写出编码直接写出编码C；4、间接编码方法：、间接编码方法：由由g(x)得到一个码字，循环移位得到一个码字，循环移位得到得到k个码字，写出生成矩阵，通过线性变换得个码字，写出生成矩阵，通过线性变换得到系统码生成矩阵到系统码生成矩阵G，最后由生成方程，最后由生成方程C=KG 求出相应码字。求出相应码字。例例2 求求(7,3)循环码的生成多项式，并为信息循环码的生成多项式，并为信息K=(110)编码。编码。解：解：(1
32、)n=7,k=3,r=4由：由：x7-1=(x+1)(x3+x+1)(x3+x2+1)取：取：g(x)=(x+1)(x3+x+1)=x4+x3+x2+1；(2)由由:k(x)=x2+x,xr k(x)=x4(x2+x)=x6+x5 知知:r(x)=x6+x5 mod x4+x3+x2+1=x3+1；(3)(3)R=(1001)；C=(1101001)；或由：或由：g(x)=x4+x3+x2+1 (0011101)循环左移三次得到：循环左移三次得到：C=(1101001)；3.4.5 循环码的译码（纠错）循环码的译码（纠错）(1)由接收码字由接收码字R，写出其接收码多项式，写出其接收码多项式R(
33、x)；(2)求伴随子多项式求伴随子多项式S(x)=R(x)mod g(x)；(3)若若 S(x)=0（即接收码多项式能被（即接收码多项式能被g(x)整除）整除）,则表明接收码无误。则表明接收码无误。(4)若若 S(x)0，表明接收码有误，此时定义，表明接收码有误，此时定义错误格式多项式：错误格式多项式：E(x)=en-1xn-1+en-2xn-2+e2x2+e1x+e0；(5)由由S(x)求求对应的对应的E(x)。因因S(x)=C(x)+E(x)mod g(x)=E(x)mod g(x)；为了找到为了找到S(x)对应的对应的E(x)，我们可以预先将我们可以预先将纠错能力纠错能力t 位位 以内的
34、各种错误格式以内的各种错误格式E(x)除以除以g(x)的余式都计算出来，列成一张的余式都计算出来，列成一张S(x)-E(x)对照表，对照表，由由S(x)就能直接查出就能直接查出E(x)。(6)纠错译码：纠错译码：由由C(x)=R(x)+E(x)就能写出译码就能写出译码C。例例3 已已知知(7,4)码码的的生生成成多多项项式式是是g(x)=x3+x+1；请请为为R=(0110010)译码。译码。解：解：设接收码为设接收码为R=(r6 r5 r4 r3 r2 r1 r0)；由；由S(x)=E(x)mod g(x)；可列出可列出S(x)E(x)对照表：对照表：当当R=(0110010)时时，R(x)
35、=x5+x4+x；S(x)=（x5+x4+x）mod（x3+x+1）=x+1；查表知：查表知：E(x)=x3；纠错：纠错：C(x)=R(x)+E(x)=x5+x4+x3+x；即：即：C=(0111010)；译码结果是译码结果是K=0111误码位置误码位置r0 r1 r2 r3 r4 r5 r6 E(x)1 x x2 x3 x4 x5 x6 S(x)1 x x2 x+1 x2+x x2+x+1 x2+1计算机中对公式的计算其实仍归结为数值计算，对所有的计算机中对公式的计算其实仍归结为数值计算，对所有的赋值都能正确得到结果，就等于对公式的计算。赋值都能正确得到结果，就等于对公式的计算。笔算时是从被
36、除数的高位开始，依次对除数求商、求积、笔算时是从被除数的高位开始，依次对除数求商、求积、求余，然后右移一位，继续前述过程，直至到被除数末尾求余，然后右移一位，继续前述过程，直至到被除数末尾。现在的道理相同，只不过把除数固定在电路上（就是反馈现在的道理相同，只不过把除数固定在电路上（就是反馈的位置），的位置），让被除数逐位右移通动寄存器，通过反馈电路让被除数逐位右移通动寄存器，通过反馈电路实现求商、求积、求余的运算。实现求商、求积、求余的运算。由于是二进制代码，商只由于是二进制代码，商只有有1和和0两个可能值，积就是除数本身或是零。商为两个可能值，积就是除数本身或是零。商为0时反时反馈为馈为0，
37、被除数不变；商为，被除数不变；商为1时反馈为时反馈为1，被除数与除数相，被除数与除数相减，但模二减等于模二加。最后减，但模二减等于模二加。最后留在寄存器中的就是余数留在寄存器中的就是余数,上轮余数的首位被输出，它的就是商。上轮余数的首位被输出，它的就是商。3.4.6 编、译码的电路实现编、译码的电路实现1.除法求余电路除法求余电路：设被除数是设被除数是x r k(x)=x5=0100000，除数是，除数是g(x)=x3+x+1=1011，相除的过程见表所示。相除的过程见表所示。xr K(x)D0D1D2输入输入 输出输出xrK(x)输入输入D0D1D2输出输出 x6位位00000 x5位位11
38、000 x4位位00100 x3位位00010 x2位位01101 x1位位00110 x0位位01111电路原理电路原理:现在的除数现在的除数g(x)是是3次多项式，余数至多次多项式，余数至多2次，故可取次，故可取3位寄位寄存器来存放余数。存器来存放余数。余数初值为零，覆盖值是被除数减去商与除数之积。因此余数初值为零，覆盖值是被除数减去商与除数之积。因此将被除数诸位推入寄存器中，寄存器兼有减法计算功能，将被除数诸位推入寄存器中，寄存器兼有减法计算功能，每次移位后都只计算每次移位后都只计算3位长的一段。位长的一段。寄存器最高位寄存器最高位(x2位位)为为0时，移位后除以时，移位后除以g(x)的
39、商必然为的商必然为0；寄存器最高位为寄存器最高位为1时商必然为时商必然为1；因此该位的；因此该位的输出的就是商。输出的就是商。该商被反馈回去，反馈位置是该商被反馈回去，反馈位置是g(x)的非的非0位，就相当于用商位，就相当于用商去乘除数，其乘积不是去乘除数，其乘积不是0就是就是g(x)。模模2加等价于模加等价于模2减，减，就就实现了与寄存器中原先余数的相减运算。实现了与寄存器中原先余数的相减运算。如果商为如果商为1，1 g(x)的最高位在与原先余数相减的运算中总的最高位在与原先余数相减的运算中总是相抵消的，所以只须考虑其余是相抵消的，所以只须考虑其余3位的反馈即可。位的反馈即可。2.编码电路编
40、码电路：把输入的把输入的K(x)从从D0端移到端移到D2后面，就得到了如图所后面，就得到了如图所示的实用编码电路。示的实用编码电路。PD0D1D2输出Q输入KK(x)输入输入D0D1D2输出输出x3位位00000 x2位位11101x1位位00110 x0位位01110111首首先先开开关关P置置向向上上，开开关关Q闭闭合合，得得到到上上面面四四行行的的数数据据；输输出出的的就就是是信信息息K。然然后后P置置向向下下，Q开开启启，继继续续将将寄寄存存器器中中的的余余数数输输出出；就就是是接接在在后面的监督。后面的监督。电路工作原理电路工作原理：(1)(1)在在D2端加入端加入K(x)，就等于在
41、，就等于在D0端加端加x r k(x)，这样，这样 就省去了前置的乘以就省去了前置的乘以x3的乘法的乘法(移位移位)器。器。(2)将将Q闭合，闭合，P置向上，就可以在进行除法运算的置向上，就可以在进行除法运算的同时，将信息同时，将信息K送到输出，形成编码的前半段。送到输出，形成编码的前半段。(3)无须移位无须移位7次，只要移位次，只要移位4次，就可以完成求模次，就可以完成求模 运算的工作，接着把运算的工作，接着把P置下，置下，Q开启，就可以把开启，就可以把 D0D1D2中的余数，顺序接在编码的后半段上，中的余数，顺序接在编码的后半段上，形成完整的编码。形成完整的编码。3、译码电路译码电路：首先
42、断开首先断开K2，接通，接通K1，利用除法求余电路，把接收码，利用除法求余电路，把接收码字字R(x)除以除以g(x)的余式，即伴随子的余式，即伴随子S(x)计算出来，存计算出来，存于于D0D1D2中；与此同时，中；与此同时，R(x)也被缓存在也被缓存在R0R6中。中。R0R1R2R3R4R5R6 K1 D0 D1D2K2然后，断开然后，断开K1，接通，接通K2。与门设计是对输入（与门设计是对输入（101）有响应。若）有响应。若e e6 6位错，则求余位错，则求余结果结果S=101=101，恰使与门有输出，正好纠正，恰使与门有输出，正好纠正R R6 6位。此后，位。此后，移位继续进行，移位继续进
43、行，D0D1D2值发生变化，与门关闭，不再影值发生变化，与门关闭，不再影响响R R5R0的输出。的输出。若若e e5 5位错，则求余得出的位错，则求余得出的S=(111)=(111)，与门无输出，但，与门无输出，但经过一个节拍后经过一个节拍后D0D1D2变成变成(101)(101)，与门变得有输出，与门变得有输出，正好轮到缓存器中正好轮到缓存器中R5 5位的输出，将它纠正；再继续移位，位的输出，将它纠正；再继续移位，与门又关闭了。与门又关闭了。其其它它位位有有错错时时，同同样样引引起起类类似似于于上上述述变变化化的的纠纠错错过过程程。巧巧就就巧巧在在正正好好轮轮到到R R有有错错的的那那一一位
44、位输输出出时时，寄寄存存器器恰恰变变为为101101，与门便输出纠错信号，与门便输出纠错信号“1 1”，将该位错码纠正。，将该位错码纠正。如此巧妙的玄机在哪里呢如此巧妙的玄机在哪里呢?因为伴随子因为伴随子S(x)=R(x)mod g(x)=E(x)mod g(x)，所，所以分析电路对以分析电路对R(x)的作用与分析的作用与分析E(x)是等价的。是等价的。当当R(x)为正确码时，为正确码时，E(x)是全是全0，除法器求余结果为除法器求余结果为0 0，与门不会打开，与门不会打开，R(x)从缓冲器中原样输出。从缓冲器中原样输出。当当R(x)有一位不正确时，有一位不正确时，E(x)的相应位是的相应位是
45、1，其它全，其它全0；除法器求余逻辑是按照除法器求余逻辑是按照x3 3+x+1+1设计的设计的,初值为初值为000,000,当有当有1 1输入时才变为输入时才变为100,100,此后由于输入全为此后由于输入全为0,0,寄存器则按照寄存器则按照100010 001110011111101100010 001110011111101的规律变化的规律变化,共共7 7步变到步变到101101。E(x)为为1的码位进入运算器的同时也进入的码位进入运算器的同时也进入缓冲器，经过缓冲器，经过7 7步才能缓冲才能输出，这时正好与门打开，将其纠正。步才能缓冲才能输出，这时正好与门打开，将其纠正。译码电路逐次移位
46、的数据变化译码电路逐次移位的数据变化 错误格式错误格式伴随式伴随式寄存器寄存器继续移位继续移位又移位后又移位后纠正位纠正位 e(x)S(x)D0D1D2次数次数ND0D1D2R e6=1x2+11010101R6 e5=1x2+x+11111101R5e4=1x2+x 0112101R4 e3=1x+11103101R3 e2=1x20014101R2 e1=1x 0105101R1 e0=111006101R0本节要点本节要点1.1.循环码的基本概念：循环码的基本概念：(1)(1)码字的循环移位码字的循环移位 (2)(2)码多项式及其两个重要性质码多项式及其两个重要性质 (3)(3)循环码的
47、生成多项式循环码的生成多项式2.2.循环码的编码：循环码的编码：根据信息根据信息K，直接由，直接由 r(x)=x r k(x)mod g(x)求出监督位，添在信息位后，即得到编码。求出监督位，添在信息位后，即得到编码。3.3.循环码的译码循环码的译码：（1）由接收码字由接收码字R，写出其接收码多项式，写出其接收码多项式R(x)；（2）求伴随子多项式求伴随子多项式S(x)=R(x)mod g(x)；（3）若若 S(x)=0（即即接接收收码码多多项项式式能能被被g(x)整整除除）,则则表表明明接收码无误。接收码无误。（4）若若 S(x)0，表表明明接接收收码码有有误误，此此时时应应将将纠纠错错能能
48、力力t 位位以以内内的的各各种种错错误误格格式式E(x)除除以以g(x)的的余余式式都都计计算算出出来来，列列成一张成一张S(x)-E(x)对照表。对照表。（5 5）由）由S(x)直接查表得到直接查表得到E(x)。（6 6）由由C(x)=R(x)+E(x)进行纠错。进行纠错。思考：思考：是否任意码长是否任意码长n和任意信息位和任意信息位k都能构都能构成成(n,k)循环码？（提示：考虑生成多项式）循环码？（提示：考虑生成多项式）。作业：作业：P114页：页：14、17题题 第三章第三章 信道编码信道编码 3.5 循环码的扩展循环码的扩展本节的主要内容本节的主要内容v增余汉明码增余汉明码v截短循环
49、码截短循环码v循环冗余校验码循环冗余校验码v二元本原二元本原BCH码码v二元非本原二元非本原BCH码码 增余汉明码：增余汉明码：extended Hamming code截短循环码：截短循环码：shortened cyclic code循环冗余校验码：循环冗余校验码：Cyclic Redundancy Check Code(CRC)本原本原BCH码码：primitive BCH code 非本原非本原BCH码码:non-primitive BCH code 外外语语关关键词键词上节回顾：循环码上节回顾：循环码基本概念基本概念：循环码的特点，码多项式，循环移位的数学表达。循环码的特点，码多项式，
50、循环移位的数学表达。生成多项式：生成多项式：（1）码多项式中幂次最低（幂次为）码多项式中幂次最低（幂次为r）常数项为）常数项为1的非的非 零多项式。零多项式。（2）通过对）通过对g(x)的循环移位可获得其它一些码多项式。的循环移位可获得其它一些码多项式。（3）任意码多项式）任意码多项式T(x)都应能被都应能被g(x)整除。整除。（4）g(x)是是xn-1的一个因式。的一个因式。循环码的编码：循环码的编码：（1）分解）分解xn-1，以获得生成多项式，以获得生成多项式g(x)；（2）求监督多项式：）求监督多项式：r(x)=x r k(x)mod g(x)；（3）写出相应码字：）写出相应码字：C(x