信道编码中PPT讲稿.ppt

信道编码中第1页，共85页，编辑于2022年，星期四本节的主要内容本节的主要内容 码多项式码多项式 循环移位的数学表达循环移位的数学表达 循环码的生成多项式循环码的生成多项式 循环码的编码循环码的编码 循环码的译码循环码的译码 编、译码的电路实现编、译码的电路实现第2页，共85页，编辑于2022年，星期四循环码：循环码：cyclic code 码多项式：码多项式：code polynomial生成多项式：生成多项式：generator polynomial求模运算：求模运算：modular arithmetic系统码：系统码：systematic（regular）code循环移位运算：循环移位运算：cycle shift operation外外语语关关键词键词第3页，共85页，编辑于2022年，星期四上节回顾：线性分组码上节回顾：线性分组码基本概念基本概念：表达方式：表达方式：(n,k)码，码，k是信息位数，是信息位数，r是监督位数，是监督位数，n=k+r是是码长。码长。编码：编码：已知信息已知信息K（k位二进序列），求相应码字的方法位二进序列），求相应码字的方法是是 C=KG，G叫生成矩阵，是叫生成矩阵，是k行行n列的，列的，一般一般G具有具有Ik Q的形式，的形式，Ik 是是k行行k列单位方阵，列单位方阵，Q是是k行行r列的矩阵。列的矩阵。生成矩阵的设计，应使许用码字之间的最小汉明距离生成矩阵的设计，应使许用码字之间的最小汉明距离尽量地大。尽量地大。第4页，共85页，编辑于2022年，星期四译玛：译玛：当收到码字当收到码字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的那一位就等于的那一位就等于1，于是于是R的那一位就是错误的。最后根据的那一位就是错误的。最后根据 C=RE进行将其纠正。进行将其纠正。第5页，共85页，编辑于2022年，星期四纠正多位错错：纠正多位错错：当当S 0时，根据时，根据S=RHT=EHT，可可以预先由以预先由S=EHT计算出各种错误格式计算出各种错误格式E所对应的伴随所对应的伴随子向量子向量S，得到，得到ES对照表。查表就能找到接收码字对照表。查表就能找到接收码字R（即（即S=RHT）所对应的）所对应的E。纠错能力不等式：纠错能力不等式：2r Cno+Cn1+Cn2+Cnt这是因为伴随子这是因为伴随子S是是1行行r列的向量，它有列的向量，它有2r 种不同的状种不同的状态，除了用全零态表示正确码之外，最多只能区别开态，除了用全零态表示正确码之外，最多只能区别开2r1种不同的错误格式。种不同的错误格式。第6页，共85页，编辑于2022年，星期四引言：引言：构造线性分组码关键是设计出一个好的生成构造线性分组码关键是设计出一个好的生成矩阵，使所有码字之间的汉明距离尽量大。怎样矩阵，使所有码字之间的汉明距离尽量大。怎样找这样的矩阵呢？循环码的出现提供了一整套理找这样的矩阵呢？循环码的出现提供了一整套理论和方法，使人们能够借助数学工具来寻找更好论和方法，使人们能够借助数学工具来寻找更好的线性分组码，并由此引发出一大类很常用检、的线性分组码，并由此引发出一大类很常用检、纠错编译码。纠错编译码。3.4 循环码循环码第7页，共85页，编辑于2022年，星期四上节讨论过上节讨论过(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);第8页，共85页，编辑于2022年，星期四循环码是线性分组码中的一个子集。循环码是线性分组码中的一个子集。对于循环码，有了一个的码字，按循环移对于循环码，有了一个的码字，按循环移位规律就能写出位规律就能写出n个码字。从中选出个码字。从中选出k个个来构造生成矩阵来构造生成矩阵G，就能生成全部，就能生成全部2k个许个许用码字。用码字。循环码与近代数学有密切联系。使我们可循环码与近代数学有密切联系。使我们可以借助数学工具来设计编码。以借助数学工具来设计编码。第9页，共85页，编辑于2022年，星期四3.4.1 3.4.1 码多项式码多项式二进制自然码可表达为以二进制自然码可表达为以2 2为底的多项式表达，如：为底的多项式表达，如：C=(1010111)=126+025+124+023+122+121+120；把底换为把底换为x，则得到，则得到“码多项式码多项式”：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+1第10页，共85页，编辑于2022年，星期四3.4.2 3.4.2 循环移位的数学表达循环移位的数学表达对二进数，左移一位相当于乘以对二进数，左移一位相当于乘以2，而将最高位的进位，而将最高位的进位(2n位位)上的上的数码拿回到数码拿回到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 第11页，共85页，编辑于2022年，星期四（7,4）循环码及其码多项式的循环移位：循环码及其码多项式的循环移位：循环次数循环次数循环码循环码码多项式码多项式模模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+1第12页，共85页，编辑于2022年，星期四3.4.3 3.4.3 循环码的生成多项式循环码的生成多项式(1)(1)生成多项式的定义和特点生成多项式的定义和特点循环码的码多项式中幂次最低的非零多项式叫做生成多项式，循环码的码多项式中幂次最低的非零多项式叫做生成多项式，记做记做g(x)。如如(7,4)码的码的x3+x+1。有了它，有了它，其它码字都可由其它码字都可由xi g(x)的模的模 xn-1-1得到。得到。生成多项式的常数项为生成多项式的常数项为1。否则，通过循环移位还能继续降低幂次，否则，通过循环移位还能继续降低幂次，它就不是幂次最低的多项式了。它就不是幂次最低的多项式了。生成多项式的幂次为生成多项式的幂次为r。因为因为幂次最低的码多项式是幂次最低的码多项式是信息为信息为0001,后面跟上后面跟上r个监督位的那个码字所对应的码多项式，个监督位的那个码字所对应的码多项式，它的最高位是它的最高位是 xr，是，是r次的次的多项式多项式。第13页，共85页，编辑于2022年，星期四(2)(2)生成多项式的两个性质：生成多项式的两个性质：1任意码多项式任意码多项式T(x)都是生成多项式都是生成多项式 g(x)的倍式的倍式。证明：（证明：（n,k）循环码作为线性分组码，其生成矩阵）循环码作为线性分组码，其生成矩阵G是是k行行n列的，可由列的，可由k个不同的码字构成：个不同的码字构成：第14页，共85页，编辑于2022年，星期四任给一个信息码任给一个信息码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)g(x)；表明任意码多项式表明任意码多项式T(x)都应能被都应能被g(x)整除整除。第15页，共85页，编辑于2022年，星期四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)第16页，共85页，编辑于2022年，星期四（3 3）生成多项式）生成多项式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；二者任选其一，一旦选定，就不再考虑另一个了。二者任选其一，一旦选定，就不再考虑另一个了。第17页，共85页，编辑于2022年，星期四插件插件1：查表分解查表分解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(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；第18页，共85页，编辑于2022年，星期四（5）表中并未列出）表中并未列出xn-1所有的因式，所有的因式，与已列出因式对偶的因式都被与已列出因式对偶的因式都被省略了省略了。所谓对偶指的是将二进制自然码高低位倒置的表达，如：。所谓对偶指的是将二进制自然码高低位倒置的表达，如：与与(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分解为以上因式之积，诸因式中幂次最高为分解为以上因式之积，诸因式中幂次最高为r。（7）类序号类序号i与与n互素的那些因式互素的那些因式mi(x)被称为本原多项式；类序号被称为本原多项式；类序号i与与n可约的那些因式可约的那些因式mi(x)被称为非本原多项式。如果被称为非本原多项式。如果n为素数，所有的因为素数，所有的因式都是本原多项式。式都是本原多项式。第19页，共85页，编辑于2022年，星期四例例查表分解查表分解x63-1因为因为26-1=63，所以应查，所以应查P194页表页表4中中m=6阶阶。i=1：(103)8=(1000011)2，得知，得知m1(x)=x6+x+1；由对偶式由对偶式(1100001)2和和187页表得知页表得知m31(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；对偶式还是自己。对偶式还是自己。第20页，共85页，编辑于2022年，星期四i=9：(015)8=(1101)2，得知，得知m9(x)=x3+x2+1；由对偶式由对偶式(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),m5(x),m11(x),m13(x),m23(x)和和m31(x)；第21页，共85页，编辑于2022年，星期四(1)(1)循环码的生成矩阵循环码的生成矩阵求出了生成多项式求出了生成多项式g(x)，等于得到了一个码字，通过循环，等于得到了一个码字，通过循环移位不难得到其它码字。移位不难得到其它码字。果然如此简单吗？果然如此简单吗？实际上，通过循环移位最多可写出实际上，通过循环移位最多可写出n个码字，得不到全部码个码字，得不到全部码字，因为字，因为(n,k)码应当共有码应当共有2k个许用码字。个许用码字。例如例如(7,4)循环码共有循环码共有1616个许用码字。个许用码字。取取g(x)=x3 3+x+1+1，等于知道了中信息，等于知道了中信息K=(0001)=(0001)所对应的那个所对应的那个码字：码字：C1 1=(=(0001 0001 011)011)。3.4.4 3.4.4 循环码的编码循环码的编码第22页，共85页，编辑于2022年，星期四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 1100 1100 （1100 1100 010010）C8 1000 1000 （1000 1000 101101）（7,47,4）共有）共有1616个许用码字，还缺个许用码字，还缺 9 9个。个。第23页，共85页，编辑于2022年，星期四从循环组中随便取从循环组中随便取4个许用码字，比如前个许用码字，比如前4个，用它们构成个，用它们构成的生成矩阵为的生成矩阵为G1：再利用再利用C=KG1 就能求得全部许用码字。就能求得全部许用码字。比如：比如：(0100)(0100)G1=(0101100);(1000)(1000)G1=(1011000);然而发现码字然而发现码字不具备信息位在前，监督位在后的形式。不具备信息位在前，监督位在后的形式。原因原因是是G1不不具备具备G=Ik Q的形式，这样编码叫的形式，这样编码叫非系统码，非系统码，非系统码在译非系统码在译码时是比较困难的。码时是比较困难的。第24页，共85页，编辑于2022年，星期四实际上，为了构造实际上，为了构造G=Ik Q形式的生成矩阵形式的生成矩阵。需要如下的需要如下的4个码字：个码字：1000010000100001才能排列出才能排列出44的单位矩阵的单位矩阵Ik。通过对通过对C1=(0001 0001 011)011)的循环移位可以得到的循环移位可以得到 （0010 0010 110110）和（）和（1000 1000 101)101)，但是却无法得到但是却无法得到(0100)011110101第25页，共85页，编辑于2022年，星期四原因何在？原因何在？原来原来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 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（11111111 111111）第26页，共85页，编辑于2022年，星期四直接写不出系统码生成矩阵直接写不出系统码生成矩阵，但但可以经过线性变换，可以经过线性变换，将将G1最下行最下行加到第二行上，将最下面两行加到第一行上，也能得到加到第二行上，将最下面两行加到第一行上，也能得到Ik Q的形式的形式的系统码生成矩阵的系统码生成矩阵G:非系统码非系统码生成矩阵生成矩阵系统码系统码生成矩阵生成矩阵线性线性变换变换得到了系统码生成矩阵，就可以用得到了系统码生成矩阵，就可以用C=KG得到所有码字。得到所有码字。第27页，共85页，编辑于2022年，星期四（2 2）直接计算系统码的监督元）直接计算系统码的监督元:以以(7,4)码为例，设信息位为码为例，设信息位为k3 k2 k1 k0，对应的多项式为：，对应的多项式为：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)第28页，共85页，编辑于2022年，星期四根据生成多项式根据生成多项式性质性质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)就得到了相应的码字。就得到了相应的码字。第29页，共85页，编辑于2022年，星期四例例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)的码字。的码字。第30页，共85页，编辑于2022年，星期四小结：循环码的编码步骤：小结：循环码的编码步骤：1、确确定定(n,k)循循环环码码的的生生成成多多项项式式：将将xn-1分分解解因因 式式，从中选择一个从中选择一个r次的因子作为次的因子作为g(x)。2、根据信息、根据信息K，由由r(x)=x r k(x)mod g(x)计算出计算出它的监督位。它的监督位。3、由、由 信息位信息位+监督位监督位 直接写出编码直接写出编码C；4、间接编码方法：、间接编码方法：由由g(x)得到一个码字，循环移位得到得到一个码字，循环移位得到k个码字，写出生成矩阵，通过线性变换得到系统码生成个码字，写出生成矩阵，通过线性变换得到系统码生成矩阵矩阵G，最后由生成方程，最后由生成方程C=KG 求出相应码字。求出相应码字。第31页，共85页，编辑于2022年，星期四例例2 求求(7,3)循环码的生成多项式，并为信息循环码的生成多项式，并为信息K=(110)编码。编码。解：解：(1)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)；第32页，共85页，编辑于2022年，星期四3.4.5 循环码的译码（纠错）循环码的译码（纠错）(1)由接收码字由接收码字R，写出其接收码多项式，写出其接收码多项式R(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；第33页，共85页，编辑于2022年，星期四(5)由由S(x)求求对应的对应的E(x)。因因S(x)=C(x)+E(x)mod g(x)=E(x)mod g(x)；为了找到为了找到S(x)对应的对应的E(x)，我们可以预先将纠错我们可以预先将纠错能力能力t 位位 以内的各种错误格式以内的各种错误格式E(x)除以除以g(x)的余式都计的余式都计算出来，列成一张算出来，列成一张S(x)-E(x)对照表，由对照表，由S(x)就能就能直接查出直接查出E(x)。(6)纠错译码：纠错译码：由由C(x)=R(x)+E(x)就能写出译码就能写出译码C。第34页，共85页，编辑于2022年，星期四例例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)=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第35页，共85页，编辑于2022年，星期四计算机中对公式的计算其实仍归结为数值计算，对所有的赋值计算机中对公式的计算其实仍归结为数值计算，对所有的赋值都能正确得到结果，就等于对公式的计算。都能正确得到结果，就等于对公式的计算。笔算时是从被除数的高位开始，依次对除数求商、求积、求笔算时是从被除数的高位开始，依次对除数求商、求积、求余，然后右移一位，继续前述过程，直至到被除数末尾余，然后右移一位，继续前述过程，直至到被除数末尾。现在的道理相同，只不过把除数固定在电路上（就是反馈的位置），现在的道理相同，只不过把除数固定在电路上（就是反馈的位置），让被除数逐位右移通动寄存器，通过反馈电路实现求商、求积、求余让被除数逐位右移通动寄存器，通过反馈电路实现求商、求积、求余的运算。的运算。由于是二进制代码，商只有由于是二进制代码，商只有1和和0两个可能值，积就是除数两个可能值，积就是除数本身或是零。商为本身或是零。商为0时反馈为时反馈为0，被除数不变；商为，被除数不变；商为1时反馈为时反馈为1，被除数与除数相减，但模二减等于模二加。最后被除数与除数相减，但模二减等于模二加。最后留在寄存器中留在寄存器中的就是余数的就是余数,上轮余数的首位被输出，它的就是商。上轮余数的首位被输出，它的就是商。3.4.6 编、译码的电路实现编、译码的电路实现1.除法求余电路除法求余电路：第36页，共85页，编辑于2022年，星期四设被除数是设被除数是x r k(x)=x5=0100000，除数是，除数是g(x)=x3+x+1=1011，相除的过程见表所示。相除的过程见表所示。xr K(x)D0D1D2输入输入 输出输出xrK(x)输入输入D0D1D2输出输出 x6位位00000 x5位位11000 x4位位00100 x3位位00010 x2位位01101 x1位位00110 x0位位01111第37页，共85页，编辑于2022年，星期四电路原理电路原理:现在的除数现在的除数g(x)是是3次多项式，余数至多次多项式，余数至多2次，故可取次，故可取3位寄存器来存位寄存器来存放余数。放余数。余数初值为零，覆盖值是被除数减去商与除数之积。因此将被除数诸位余数初值为零，覆盖值是被除数减去商与除数之积。因此将被除数诸位推入寄存器中，寄存器兼有减法计算功能，每次移位后都只计算推入寄存器中，寄存器兼有减法计算功能，每次移位后都只计算3位长位长的一段。的一段。寄存器最高位寄存器最高位(x2位位)为为0时，移位后除以时，移位后除以g(x)的商必然为的商必然为0；寄存器；寄存器最高位为最高位为1时商必然为时商必然为1；因此该位的；因此该位的输出的就是商。输出的就是商。该商被反馈回去，反馈位置是该商被反馈回去，反馈位置是g(x)的非的非0位，就相当于用商去位，就相当于用商去乘除数，其乘积不是乘除数，其乘积不是0就是就是g(x)。模模2加等价于模加等价于模2减，减，就实现了与就实现了与寄存器中原先余数的相减运算。寄存器中原先余数的相减运算。如果商为如果商为1，1 g(x)的最高位在与原先余数相减的运算中总是相抵消的最高位在与原先余数相减的运算中总是相抵消的，所以只须考虑其余的，所以只须考虑其余3位的反馈即可。位的反馈即可。第38页，共85页，编辑于2022年，星期四2.编码电路编码电路：把输入的把输入的K(x)从从D0端移到端移到D2后面，就得到了如图所后面，就得到了如图所示的实用编码电路。示的实用编码电路。PD0D1D2输出Q输入KK(x)输入输入D0D1D2输出输出x3位位00000 x2位位11101x1位位00110 x0位位01110111首首先先开开关关P置置向向上上，开开关关Q闭闭合合，得得到到上上面面四四行行的的数数据据；输输出出的的就就是是信信息息K。然然后后P置置向向下下，Q开开启启，继继续续将将寄寄存存器器中中的的余余数数输出；就是接在后面的监督。输出；就是接在后面的监督。第39页，共85页，编辑于2022年，星期四电路工作原理电路工作原理：(1)(1)在在D2端加入端加入K(x)，就等于在，就等于在D0端加端加x r k(x)，这样，这样 就省去了前置的乘以就省去了前置的乘以x3的乘法的乘法(移位移位)器。器。(2)将将Q闭合，闭合，P置向上，就可以在进行除法运算的置向上，就可以在进行除法运算的同时，将信息同时，将信息K送到输出，形成编码的前半段。送到输出，形成编码的前半段。(3)无须移位无须移位7次，只要移位次，只要移位4次，就可以完成求模次，就可以完成求模 运算的工作，接着把运算的工作，接着把P置下，置下，Q开启，就可以把开启，就可以把 D0D1D2中的余数，顺序接在编码的后半段上，中的余数，顺序接在编码的后半段上，形成完整的编码。形成完整的编码。第40页，共85页，编辑于2022年，星期四3、译码电路译码电路：首先断开首先断开K2，接通，接通K1，利用除法求余电路，把接收码字，利用除法求余电路，把接收码字R(x)除除以以g(x)的余式，即伴随子的余式，即伴随子S(x)计算出来，存于计算出来，存于D0D1D2中；中；与此同时，与此同时，R(x)也被缓存在也被缓存在R0R6中。中。R0R1R2R3R4R5R6 K1 D0 D1D2K2第41页，共85页，编辑于2022年，星期四然后，断开然后，断开K1，接通，接通K2。与门设计是对输入（与门设计是对输入（101）有响应。若）有响应。若e e6 6位错，则求余结果位错，则求余结果S=101101，恰使与门有输出，正好纠正，恰使与门有输出，正好纠正R R6 6位。此后，移位继续进行，位。此后，移位继续进行，D0D1D2值发生变化，与门关闭，不再影响值发生变化，与门关闭，不再影响R R5R0的输出。的输出。若若e e5 5位错，则求余得出的位错，则求余得出的S=(111)=(111)，与门无输出，但经过一个，与门无输出，但经过一个节拍后节拍后D0D1D2变成变成(101)(101)，与门变得有输出，正好轮到缓存器中，与门变得有输出，正好轮到缓存器中R5 5位的输出，将它纠正；再继续移位，与门又关闭了。位的输出，将它纠正；再继续移位，与门又关闭了。其其它它位位有有错错时时，同同样样引引起起类类似似于于上上述述变变化化的的纠纠错错过过程程。巧巧就就巧巧在在正正好好轮轮到到R R有有错错的的那那一一位位输输出出时时，寄寄存存器器恰恰变变为为101101，与与门便输出纠错信号门便输出纠错信号“1 1”，将该位错码纠正。，将该位错码纠正。第42页，共85页，编辑于2022年，星期四如此巧妙的玄机在哪里呢如此巧妙的玄机在哪里呢?因为伴随子因为伴随子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)的相应位是的相应位是1，其它全，其它全0；除法除法器求余逻辑是按照器求余逻辑是按照x3 3+x+1+1设计的设计的,初值为初值为000,000,当有当有1 1输入时才变为输入时才变为100,100,此后由于输入全为此后由于输入全为0,0,寄存器则按照寄存器则按照100010 100010 001110011111101001110011111101的规律变化的规律变化,共共7 7步变到步变到101101。E(x)为为1的码位进入运算器的同时也进入的码位进入运算器的同时也进入缓冲器，经过缓冲器，经过7 7步才步才能缓冲才能输出，这时正好与门打开，将其纠正。能缓冲才能输出，这时正好与门打开，将其纠正。第43页，共85页，编辑于2022年，星期四译码电路逐次移位的数据变化译码电路逐次移位的数据变化 错误格式错误格式伴随式伴随式寄存器寄存器继续移位继续移位又移位后又移位后纠正位纠正位 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第44页，共85页，编辑于2022年，星期四本节要点本节要点1.1.循环码的基本概念：循环码的基本概念：(1)(1)码字的循环移位码字的循环移位 (2)(2)码多项式及其两个重要性质码多项式及其两个重要性质 (3)(3)循环码的生成多项式循环码的生成多项式2.2.循环码的编码：循环码的编码：根据信息根据信息K，直接由，直接由 r(x)=x r k(x)mod g(x)求出监督位，添在信息位后，即得到编码。求出监督位，添在信息位后，即得到编码。第45页，共85页，编辑于2022年，星期四3.3.循环码的译码循环码的译码：（1）由接收码字由接收码字R，写出其接收码多项式，写出其接收码多项式R(x)；（2）求伴随子多项式求伴随子多项式S(x)=R(x)mod g(x)；（3）若若 S(x)=0（即即接接收收码码多多项项式式能能被被g(x)整整除除）,则则表表明