多项式域编码(修改)

1、1有限域多项式码有限域多项式码2汇报内容汇报内容Reed-Muller码循环码31948年，年，Bell实验室的实验室的C.E.Shannon发表的发表的通信的数学理论通信的数学理论，是关，是关于现代信息理论的奠基性论文，它的发表标志着信息与编码理论这一学科于现代信息理论的奠基性论文，它的发表标志着信息与编码理论这一学科的创立。的创立。Shannon在该文中指出，任何一个通信信道都有确定的信道容量在该文中指出，任何一个通信信道都有确定的信道容量C，如果通信系统所要求的传输速率如果通信系统所要求的传输速率R小于小于C，则存在一种编码方法，当码长，则存在一种编码方法，当码长n充分大并应用最大似然译

2、码（充分大并应用最大似然译码（MLD，MaximumLikelihoodDecoding）时，）时，信息的错误概率可以达到任意小。信息的错误概率可以达到任意小。Shannon指出了可以通过差错控制码在信息传输速率不大于信道容量指出了可以通过差错控制码在信息传输速率不大于信道容量的前提下实现可靠通信，但却没有给出具体实现差错控制编码的方法。的前提下实现可靠通信，但却没有给出具体实现差错控制编码的方法。20世纪世纪40年代，年代，R.Hamming和和M.Golay提出了第一个实用的差错控制编码方提出了第一个实用的差错控制编码方案，使编码理论这个应用数学分支的发展得到了极大的推动。案，使编码理论这

3、个应用数学分支的发展得到了极大的推动。4虽然汉明码的思想是比较先进的，但是它也存在许多难以接受的缺点。虽然汉明码的思想是比较先进的，但是它也存在许多难以接受的缺点。首先，汉明码的编码效率比较低，它每首先，汉明码的编码效率比较低，它每4个比特编码就需要个比特编码就需要3个比特的个比特的冗余校验比特。冗余校验比特。另外，在一个码组中只能纠正单个的比特错误。另外，在一个码组中只能纠正单个的比特错误。Reed-Muller码是码是Muller为交换电路的设计和错误检测于为交换电路的设计和错误检测于1954年首先提年首先提出的，此后出的，此后Reed在在Muller提出的分组码的基础上得到了一种新的分组

4、码，提出的分组码的基础上得到了一种新的分组码，称为称为Reed-Muller码，简记为码，简记为RM码，将它用于通信和数据存储领域，并设码，将它用于通信和数据存储领域，并设计出了计出了RM码的第一个页码算法，也就是著名的大数逻辑译码算法。在码的第一个页码算法，也就是著名的大数逻辑译码算法。在1969年到年到1977年之间，年之间，RM码在火星探测方面得到了极为广泛的应用。即使在今码在火星探测方面得到了极为广泛的应用。即使在今天，天，RM码也具有很大的研究价值，其快速的译码算法非常适合于光纤通信码也具有很大的研究价值，其快速的译码算法非常适合于光纤通信系统。系统。5Reed-Muller码的优点

5、码的优点相比汉明码和格雷码能够纠正多个随机错误，同时，它的译码算法也相比汉明码和格雷码能够纠正多个随机错误，同时，它的译码算法也比较简单，可以在很低的译码复杂度下，获得较好的误码性能。比较简单，可以在很低的译码复杂度下，获得较好的误码性能。678两个两个n重重x，y之间，对应位取值不同的个数称为它们之间的汉明距离；之间，对应位取值不同的个数称为它们之间的汉明距离；n重重x中非零码元的个数，称为它们的汉明重量，简称距重，用中非零码元的个数，称为它们的汉明重量，简称距重，用w（x）表示表示9r阶的阶的Reed-Muller码码R(r,m)，是，是n,k,d码，码，n=2m,k=1,d=2（m-r）

6、 考虑两个极端情况，即阶数为考虑两个极端情况，即阶数为0和和m。0阶的阶的Reed-Muller码码R(0,m)=0,1，因此，因此0阶阶Reed-Muller码只是长度为码只是长度为2m的的0或或1的重复码。而的重复码。而m阶的阶的Reed-Muller码码R(m,m)则包括了长度为则包括了长度为2m的所有二进制向量。的所有二进制向量。10Reed-Muller码的构造方法可以描述如下：码的构造方法可以描述如下：首先，产生如下的长为首先，产生如下的长为2m的二元向量的二元向量 0=000； 1=111； x1=111000; x2=111000111000; xm=10101010向量向量1

7、和和0分别是长为分别是长为2m的全的全1和全和全0的向量，向量的向量，向量x1则有则有2(m-1)个个1， 2(m-1)个个0，x2为为2(m-2)个个1，之后，之后2(m-2)个个0，再重复，再重复2(m-2)个个1和和2(m-2)个个0。由此递推得，。由此递推得，xi由由2(m-i)个个1之后之后2(m-i)个个0构成并重复构成并重复 直至达到长度直至达到长度2m。11为了定义为了定义Reed-Muller码码R(r,m)的编码矩阵，首先令矩阵的第一行为的编码矩阵，首先令矩阵的第一行为1，即长度即长度2m的全的全1向量，如果向量，如果r为为0，则它是矩阵唯一的一行。如果，则它是矩阵唯一的一

8、行。如果r为为1，则在，则在R(0,m)的矩阵中添加的矩阵中添加m行行x1,x2,x3xm。例例1：当：当m=3，我们得到，我们得到R(1,3)的生成矩阵：的生成矩阵：010101013001100112000011111111111111xxx12将将x1x2=(11000000),x1x3=（10100000),x2x3=（10001000）添加到矩阵）添加到矩阵中后，得到中后，得到R(2,3)的矩阵：的矩阵：000100013200000101310000001121010101013001100112000011111111111111xxxxxxxxx13添加添加x1x2x3=（10

9、000000）到矩阵，得到）到矩阵，得到R(3,3)的矩阵：的矩阵：00000001321000100013200000101310000001121010101013001100112000011111111111111xxxxxxxxxxxx14Reed-Muller码的编码直接简单，生成矩阵码的编码直接简单，生成矩阵M为为nk大小。我们发送的大小。我们发送的信息长度为信息长度为k，设为，设为m= 则生成的则生成的 是矩阵是矩阵M中的第中的第i行行, 是编码后的码字是编码后的码字M的第的第n个码元。个码元。例例2：如果发送的信息：如果发送的信息m=(0110),在在R(1,3)的情况下，得

10、到它的码字为：的情况下，得到它的码字为：0 *(11111111) + 1 * (11110000) + 1 * (11001100) + 0 *(10101010) = (00111100)2mod1,nkiiinmRCmmmmk.,321cnRin,15Reed-Muller码的译码比编码复杂得多，编码与译码的理论建立在汉明码的译码比编码复杂得多，编码与译码的理论建立在汉明距离的基础上，汉明距离定义为两个向量之间取值不同的位数，在距离的基础上，汉明距离定义为两个向量之间取值不同的位数，在R(r,m)码码中，任意两个向量之间的距离都为中，任意两个向量之间的距离都为2（m-r）,译码的基础建立

11、在与接收码译码的基础建立在与接收码字最接近的码字是原始发送码字这一假设之上，因此，当要纠正字最接近的码字是原始发送码字这一假设之上，因此，当要纠正e个错误时，个错误时，任意两个向量之间的汉明距离应大于任意两个向量之间的汉明距离应大于2e。这种译码方法并不高效，但是算法的实现直接而不复杂。它检查矩阵这种译码方法并不高效，但是算法的实现直接而不复杂。它检查矩阵中每一行，利用逻辑值的大多数来决定这一行是否被用来编码，这使得我中每一行，利用逻辑值的大多数来决定这一行是否被用来编码，这使得我们确定出错很少的编码产生的码字是什么以及原始信息是什么成为可能。们确定出错很少的编码产生的码字是什么以及原始信息是

12、什么成为可能。16这种译码算法的具体步骤如下：这种译码算法的具体步骤如下：步骤一：选择步骤一：选择R(r,m)生成矩阵中的一行阶数为生成矩阵中的一行阶数为r，找到这一行的，找到这一行的2(m-r)个特征向量，然后对接收码字和这些特征向量中的每一个进行点积运算。个特征向量，然后对接收码字和这些特征向量中的每一个进行点积运算。步骤二：找到这些点积结果中占大多数的值，用它作为矩阵中这一行步骤二：找到这些点积结果中占大多数的值，用它作为矩阵中这一行的系数。的系数。步骤三：从生成矩阵的最底行开始，对每一行进行步骤一和步骤二，步骤三：从生成矩阵的最底行开始，对每一行进行步骤一和步骤二，除了最高一行，之后给

13、每一行乘以得出的系数构成一个新的矩阵除了最高一行，之后给每一行乘以得出的系数构成一个新的矩阵My。将。将My与接收到的码字相加，如果结果向量中与接收到的码字相加，如果结果向量中1多于多于0则生成矩阵最高一行的系则生成矩阵最高一行的系数为数为1，反之则为，反之则为0。给最高一行乘以它的系数，然后添加到。给最高一行乘以它的系数，然后添加到My矩阵中，便矩阵中，便得到了原始的码字，于是我们可以判断错误，而由生成矩阵的最高行开始得到了原始的码字，于是我们可以判断错误，而由生成矩阵的最高行开始到最底行的系数构成的向量即为原始信息。到最底行的系数构成的向量即为原始信息。17为了得到生成矩阵中任一行的特征向

14、量，用为了得到生成矩阵中任一行的特征向量，用r表示该行向量，用表示该行向量，用E表示表示生成矩阵中不属于生成矩阵中不属于r的所有向量的所有向量xi的集合，特征向量就是与的集合，特征向量就是与E中向量中向量 , 有关的有关的向量。向量。例如，在例如，在R(2,4)的生成矩阵中，最后一行与的生成矩阵中，最后一行与x3x4有关，所以特征向量与有关，所以特征向量与 x1，x2 ，x1 ，x2 的结合有关，即：的结合有关，即： x1x2，x1x2 ，x2x1 ，x1x2 ，特征向量，特征向量与生成矩阵中除了与之有关的向量之外的任一行，都有点积为与生成矩阵中除了与之有关的向量之外的任一行，都有点积为0。1

15、81920循环码是一种特殊的循环码是一种特殊的线性分组码线性分组码，属于线性分组码的一个重要子类，属于线性分组码的一个重要子类，也是目前研究最为透彻的一类码，大多数有实用价值的纠错码都是循环码。也是目前研究最为透彻的一类码，大多数有实用价值的纠错码都是循环码。循环码与一般的线性分组码相比具有以下优点：循环码的编码及译码易于循环码与一般的线性分组码相比具有以下优点：循环码的编码及译码易于用简单的具有反馈连接的移位寄存器来实现。用简单的具有反馈连接的移位寄存器来实现。212.1.1 2.1.1 线性生成码原理简介线性生成码原理简介线性分组码的构成方式是把信息序列分成每线性分组码的构成方式是把信息序

16、列分成每k 个码元一段，并由这个码元一段，并由这k 个码元按一定规则产生个码元按一定规则产生r 个校验位，组成长度为个校验位，组成长度为n = k + r 的码字，用的码字，用(n, k) 表示信息码元与校验位之间为线性关系。一个表示信息码元与校验位之间为线性关系。一个n,k线性分组码，线性分组码，是把从信源输出的以是把从信源输出的以k个码元为一组的信息组个码元为一组的信息组m，通过信道编码器后，通过信道编码器后，变成长度为变成长度为nk的码组（码字）的码组（码字）c作为作为n,k线性分组码的一个码字线性分组码的一个码字。22设设GF(q)是一个含有是一个含有q个元素的有限数域，若每位码元的取

17、值有个元素的有限数域，若每位码元的取值有q种（取自种（取自GF(q)），则信息组），则信息组m共有共有 种不同的状态，因此，需要种不同的状态，因此，需要 个码个码字字c。而长为。而长为n的数组共有的数组共有 个，二进制时个，二进制时(q=2)共有共有 个。显然，个。显然， 个个n维维向量组成有限域向量组成有限域GF(q)上的一个上的一个n维线性空间维线性空间V，编码就是要在这个，编码就是要在这个n维维线性空间中选出线性空间中选出 个向量作为合法码字，其余的个向量作为合法码字，其余的 - 个向量为禁用码字。个向量为禁用码字。如果选出的如果选出的 个作为合法码字的向量的集合构成了个作为合法码字的向

18、量的集合构成了V的一个的一个k维线性维线性子空间，则称它是一个子空间，则称它是一个q进制进制n,k线性分组码。线性分组码。如果值取自如果值取自GF(q)上的上的n,k分组码的分组码的 个码字的集合个码字的集合C，便构成了有，便构成了有限域限域GF(q)上的上的n维线性空间维线性空间V的一个的一个k维线性子空间，则称维线性子空间，则称C是一个是一个q进制进制n,k线性分组码。线性分组码。23设有设有(n,k)线性分组码线性分组码C，如果它的任意一个码字的每一次循环移位仍，如果它的任意一个码字的每一次循环移位仍然是然是C中的一个码字，则称中的一个码字，则称C为循环码。也即，如果为循环码。也即，如果

19、C=(cncn-1c2c1)是循是循环码环码C的一个码字，那么的一个码字，那么C=(cn-1cn-2c1cn) 等也都是等也都是C的码字时，则所有的码字时，则所有这些具有循环特性的码字的全体便构成了循环码这些具有循环特性的码字的全体便构成了循环码C。24循环码具有线性码的一般性质循环码具有线性码的一般性质(即封闭性指一种线性分组码的任即封闭性指一种线性分组码的任意两个码组之和仍是该分组码的另一个码组意两个码组之和仍是该分组码的另一个码组)外，还具有循环性，即循外，还具有循环性，即循环码中任一码组循环一位环码中任一码组循环一位(将最右端码元移至左端，或反之将最右端码元移至左端，或反之)以后，仍以

20、后，仍为该码组中的一个码组。为该码组中的一个码组。(n，k)循环码表示其中信息位为循环码表示其中信息位为k，监督位为，监督位为n-k位。位。循环码的主要特点是：循环码的主要特点是：理论成熟：可利用成熟的代数结构深入探讨其性质；理论成熟：可利用成熟的代数结构深入探讨其性质；实现简单：可利用循环移位特性在工程上进行编、译码；实现简单：可利用循环移位特性在工程上进行编、译码； 循环码的描述方式有很多，但在工程上最有用的是采用多项式的描循环码的描述方式有很多，但在工程上最有用的是采用多项式的描述方法。述方法。25设有循环码字设有循环码字C=(cncn-1c2c1) ，则可以用一个次数不超过，则可以用一

21、个次数不超过n-1的多项式的多项式惟一确定，其相应的多项式可表示为：惟一确定，其相应的多项式可表示为： 由循环码的特性可知，若由循环码的特性可知，若C =(cncn-1c2c1)是循环码是循环码C的一个码字，则的一个码字，则C(1) =(cn-1c1cn) 也是该循环码的一个码字，它的码多项式为：也是该循环码的一个码字，它的码多项式为： 比较式两式，得：比较式两式，得： 121( )nnC xc xc xc (1)111( )nnnCxcxc xc261(1)11( )( )111nnnnnnnncxc xcxC xCxccxxx (1)( )( )mod(1)nCxxC xx ( )( )(

22、 )mod(1)iinCxx C xx 该式说明，码字循环一次的码多项式该式说明，码字循环一次的码多项式C(1)(x)是原码多项式是原码多项式 乘乘x后再除后再除以以xn+1所得的余式，即：所得的余式，即： 由此可以推知，由此可以推知，C(x)的的i 次循环移位次循环移位C(i)(x) 是原码多项式是原码多项式C(x) 乘乘xi 后再后再除以除以xn+1所得的余式，即：所得的余式，即： 27例例4： (7,3)循环码的循环移位循环码的循环移位循环次数码字码多项式000000000011101 x4+x3+x2+110111010 x(x4+x3+x2+1)mod(x7+1) =x5+x4+x3

23、+x21110100 x2(x4+x3+x2+1)mod(x7+1)=x6+x5+x4+x231101001 x3(x4+x3+x2+1)mod(x7+1)=x6+x5+x3+141010011 x4(x4+x3+x2+1)mod(x7+1)=x6+x4+x+150100111 x5(x4+x3+x2+1)mod(x7+1)=x5+x2+x+161001110 x6(x4+x3+x2+1)mod(x7+1)=x6+x3+x2+x28 循环码可由它的一个循环码可由它的一个n-k次首一多项式次首一多项式g(x) 来确定，因此称它为码来确定，因此称它为码的生成多项式，即：的生成多项式，即： 码的生成

24、多项式具有如下性质：码的生成多项式具有如下性质： 在在(n,k)循环码中，循环码中， n-k 次码多项式是最低次的码多项式。次码多项式是最低次的码多项式。 在在(n,k)循环码中，循环码中， g(x) 是惟一是惟一n-k次多项式，次多项式， 。 在在(n,k)循环码中，每个码多项式循环码中，每个码多项式C(x) 都是都是g(x)的倍式。的倍式。 任意任意(n,k)循环码的生成多项式循环码的生成多项式g(x) 一定整除一定整除xn+1 。 10( )n kn kg xgxg xg 00g29在循环码的码多项式中，每一个能整除在循环码的码多项式中，每一个能整除xn+1的的(n-k)次首一多项式次首

25、一多项式都是该都是该码的生成多项式码的生成多项式，记为，记为g(x) 。将。将g(x)经过经过k-1次循环移位，共得次循环移位，共得到到k个码多项式：个码多项式： g(x) 、 xg(x) 、 xk-1g(x) 。这。这k 码多项式显然是码多项式显然是相互独立的，于是得到循环码的相互独立的，于是得到循环码的生成矩阵生成矩阵G(x)： 12( )( )( )( )( )kkxg xxg xG xxg xg x 30 例例 5 ： 求二进制求二进制 (7,3) 循环码的生成多项式。循环码的生成多项式。 解：分解多项式解：分解多项式x7+1，取其四次首一多项式作为生成多项式：，取其四次首一多项式作为

26、生成多项式： x7+1=(x+1)(x3+x+1)(x3+x2+1) 可将一次和任一个三次多项式的乘积作为生成多项式：可将一次和任一个三次多项式的乘积作为生成多项式：g(x)=(x+1)(x3+x2+1)=x4+x2+x+1或或 g(x)= =(x+1)(x3+x+1)=x4+x3+x2+131系统循环码的生成矩阵系统循环码的生成矩阵系统的一致校验矩阵是系统的一致校验矩阵是例例6： 以以g(x)=(x3+x+1)为生成多项式生成一个为生成多项式生成一个(7,4)循环码，要求生成的循循环码，要求生成的循 环码是系统码。环码是系统码。 解：由定义得对应给定解：由定义得对应给定g(x)的循环码的一般

27、生成矩的循环码的一般生成矩阵为：阵为：kGIP Tn kHPI 1011000 (1)0101100 (2)0010110 (3)0001011 (4)G 32 对矩阵对矩阵G的行进行运算，将第、行相加后作为第的行进行运算，将第、行相加后作为第1行，第、行，第、行相加后作为第行相加后作为第2行，得：行，得： 对应：对应： 这样，就得到系统循环码的生成矩阵和一致校验矩阵。这样，就得到系统循环码的生成矩阵和一致校验矩阵。 01000101 (1)(3)(4)0100111(2)(4)00101100001011G 0111010001110101101001H 在数据通信中，信息都是先划分成小块再

28、组装成帧后在数据通信中，信息都是先划分成小块再组装成帧后(或叫分组、包等，或叫分组、包等，仅名称不同而已仅名称不同而已)在线路上统计复用传送或存入共同物理介质的，帧尾一般在线路上统计复用传送或存入共同物理介质的，帧尾一般都留有都留有8、12、16或或32位用作差错校验。如把一帧视为一个码字，则其校位用作差错校验。如把一帧视为一个码字，则其校验位长度验位长度 不变而信息位不变而信息位 和码长和码长 是可变的，其结构符合是可变的，其结构符合 缩短循环码的特点。只要以一个选定的缩短循环码的特点。只要以一个选定的 循环码为基础，改变循环码为基础，改变 的值，就能得到任何信息长度的帧结构，而纠错能力保持

29、不变。这种应用的值，就能得到任何信息长度的帧结构，而纠错能力保持不变。这种应用下的缩短循环码称为下的缩短循环码称为循环冗余校验码循环冗余校验码(Cyclic Redundancy Check，CRC)。 nkkn(,)n i ki( , )n ki2.7.1 2.7.1 循环冗余校验码循环冗余校验码 循环冗余校验码是系统的缩短循环码，码的结构如图所示。循环冗余校验码是系统的缩短循环码，码的结构如图所示。 图图 循环冗余校验码循环冗余校验码(CRC)结构结构 图中，码字用码多项式图中，码字用码多项式 表示，表示， 是是 除以除以 后的余式，后的余式， 为为 次多项式，它们之间满足：次多项式，它们

30、之间满足： 。虽然循环冗余。虽然循环冗余校验码指的是整个码字校验码指的是整个码字 ，但人们习惯上仅把校验部分称为，但人们习惯上仅把校验部分称为CRC码。码。 如果传输过程无差错，则接收码字如果传输过程无差错，则接收码字 应等于发送码字应等于发送码字 这时这时 能被能被 整除；如果不能被整除，则说明在传输过程中出整除；如果不能被整除，则说明在传输过程中出现了误码。现了误码。 ( )C x( )r x( )n kxm x( )g xnk( )( )( )n kC xxm xr x( )C x( )C x( )g x( )C x例例7：某：某CRC的生成多项式为的生成多项式为 。如果想发送一串信息。

31、如果想发送一串信息“110001”的前的前6位，并加上位，并加上CRC校验，发送码字校验，发送码字 应如何安排，应如何安排，接收码字接收码字 又如何校验？又如何校验？解：本题信息码字多项式解：本题信息码字多项式 ， ，从生成多项式，从生成多项式 的的阶数得校验位数等于阶数得校验位数等于4，因此，因此 。 将将 除以除以 得余式得余式 ： 于是，发送码字多项式于是，发送码字多项式 对应对应的发送码字为的发送码字为(1100011100)。 4( )1g xxx( )C x( )r x54( )1m xxx6k( )g x10n( )nkxm x( )g x( )r x45432( )( )mod

32、 ( ) (1)mod ( ) n kr xxm xg xxxxg xxx( )( )( )n kC xxm xr x98432xxxxx在接收端，在接收端，CRC校验实际上就是做除法运算：如果传输过程无差错，则校验实际上就是做除法运算：如果传输过程无差错，则 能被能被 整除，余式为整除，余式为“0”；如果余式不为；如果余式不为“0”，则说明一定有差错。，则说明一定有差错。 例例8 假设假设 ，即信息码字为，即信息码字为(1011001)， ，求，求CRC校验码。由题得：校验码。由题得： 用用 去除去除 ，有，有： ( )g x643( )1m xxxx43( )1g xxx410874( )

33、 x m xxxxx( )g x4( )x mx( )C x经相除后得到的最后余数经相除后得到的最后余数1010就是冗余校验码就是冗余校验码 。所以，发送码字。所以，发送码字(10110011010)。 需要注意的是，这里所涉及的运算与前面一样都是模需要注意的是，这里所涉及的运算与前面一样都是模2运算。运算。如果例子中的发送码字如果例子中的发送码字(10110011010)经传输后受噪声的干扰，在接收端变经传输后受噪声的干扰，在接收端变成为成为(10110011100)。求余式的除法如下：。求余式的除法如下： ( )r x求得余式不为零，相当于在发送码字上加了差错图样求得余式不为零，相当于在发

34、送码字上加了差错图样“00000000110”。差错图样相应的多项式为差错图样相应的多项式为 。有差错时，接收端收到的不再。有差错时，接收端收到的不再是是 ，而是，而是 + 。由于：。由于： 若若 ，则这种差错就能检测出来，若，则这种差错就能检测出来，若 ，那么由于接收到，那么由于接收到的码字多项式仍然可被的码字多项式仍然可被 整除，错误就检测不出来，也即发生了漏检。整除，错误就检测不出来，也即发生了漏检。理论上可以证明，循环冗余校验码的检错能力如下：理论上可以证明，循环冗余校验码的检错能力如下： 可检测出所有奇数个错；可检测出所有奇数个错； 可检测出所有单比特和双比特的错；可检测出所有单比特

35、和双比特的错； 2( ) e xxx( )C x( )Cx( )e x ( )+ ( ) ( ) ( )=+ ( ) ( ) ( )C xe xC xe xg xg xg x( )( )e x0g x ( )( )e x0g x ( )g x 可检测出所有小于、等于校验码长度可检测出所有小于、等于校验码长度 的突发错误；的突发错误； 对于对于 位的突发性错误，查出概率为位的突发性错误，查出概率为 ； 对于多于对于多于 位的突发性错误，查出概率为位的突发性错误，查出概率为 。由此可以看出，只要选择足够的冗余校验位，可以使得漏检率减到任意由此可以看出，只要选择足够的冗余校验位，可以使得漏检率减到任

36、意小的程度。小的程度。循环冗余编码法在数据传输中得到了最广泛的应用。循环冗余编码法在数据传输中得到了最广泛的应用。CRC本身具有纠错本身具有纠错功能，但网络中一般不用其纠错功能，仅用其强大的检错功能，检出错误功能，但网络中一般不用其纠错功能，仅用其强大的检错功能，检出错误后要求重发。后要求重发。 nk1nk(1)1 2r1nk1 2rCRC-12，其生成多项式：，其生成多项式：CRC-16，其生成多项式：，其生成多项式：CRC-CCITT，其生成多项式：，其生成多项式：CRC-32，其生成多项式：，其生成多项式： 循环冗余校验码的编译码过程通常用采用硬件来实现，因为除法运算易循环冗余校验码的编

37、译码过程通常用采用硬件来实现，因为除法运算易于用移位寄存器和模于用移位寄存器和模2加法器来实现，可以达到比较高的处理速度。随着集加法器来实现，可以达到比较高的处理速度。随着集成电路工艺的发展，循环冗余码的产生和校验均有集成电路产品，发送端成电路工艺的发展，循环冗余码的产生和校验均有集成电路产品，发送端能够自动生成能够自动生成CRC码，接收端可自动校验，速度大大提高。码，接收端可自动校验，速度大大提高。 121132( )1g xxxxxx16152( )1g xxxx16155( )1g xxxx322623221612111087542( )1g xxxxxxxxxxxxxxx目前广泛使用的

38、目前广泛使用的CRC码已成国际标准，生成多项式主要有下述四种：码已成国际标准，生成多项式主要有下述四种： BCH码是一类最重要的循环码，能纠正多个随机错误。这种码可以是码是一类最重要的循环码，能纠正多个随机错误。这种码可以是二进制码，也可以是非二进制码。二进制码，也可以是非二进制码。BCH码具有纠错能力强，构造方便，编、译码易于实现等一系列优点。码具有纠错能力强，构造方便，编、译码易于实现等一系列优点。二进制本原二进制本原BCH码具有下列参数：码具有下列参数： (码长码长) （监督元位数）（监督元位数） （最小码距）（最小码距） 式中式中 和纠错能力和纠错能力 是任意的正整数。是任意的正整数。

39、 BCH码的码长为码的码长为 或或 的因子，通常称前者为的因子，通常称前者为本原本原BCH码码，称后者为非本原，称后者为非本原BCH码码。 min2121mnnkmtdt(3)m1(2)mt21mn21mn2.7.2 BCH2.7.2 BCH码码 BCH码的基本特点是其生成多项式码的基本特点是其生成多项式 包含包含 个连续幂次的根，个连续幂次的根，由该由该 生成的循环码，其纠错能力不小于生成的循环码，其纠错能力不小于 。由于码的生成多项式与。由于码的生成多项式与码的最小距离有关，容易根据纠错能力要求来直接确定码的构造，因此，码的最小距离有关，容易根据纠错能力要求来直接确定码的构造，因此，它是一

40、类应用广泛的差错控制码。它是一类应用广泛的差错控制码。 这里我们重点讨论这里我们重点讨论BCH码的实际应用，即利用已知的码的实际应用，即利用已知的BCH码表格，码表格，构造出对应生成多项式的构造出对应生成多项式的BCH码。码。( )g x2t( )g xt（1 1）最小多项式）最小多项式43令令是是GF(2GF(2m m) )中的一个元素，某个形成循环周期并对中的一个元素，某个形成循环周期并对的所有根均满的所有根均满足足m(m()=0)=0的最低多项式的最低多项式m(x),m(x),称为称为的最小多项式。这个最小多项式是既的最小多项式。这个最小多项式是既约的。而且，当约的。而且，当为为m(x)

41、m(x)的根时，的根时， 2 2, , 4 4，8 8，也比是也比是m(x)m(x)的根的根以以GF(2GF(24 4) )为例，当有根为例，当有根a a时时, ,则则a,aa,a2 2,a,a2222=a=a4 4, a, a2323=a=a8 8, ,均为根均为根(a(a2424=a=a16 16 =a=a不是新根不是新根) )。因此，包括全部根的最小多项式为：。因此，包括全部根的最小多项式为：m mi i(x)=(x)=(x+ax+a)(x+a)(x+a2 2) (x+a) (x+a4 4) (x+a) (x+a8 8) ) =x =x4 4+ x+ x3 3 (a+a(a+a2 2 +

42、a+a4 4 +a+a8 8)+ x)+ x2 2(a(a3 3 +a+a5 5+a+a9 9 +a+a6 6+a+a10 10 +a+a1212) ) +x(a+x(a14 14 +a+a1313+a+a11 11 +a+a7 7) +a) +a151544利用利用GF(2GF(24 4) )域中域中a a4 4+a+a +1=0+1=0所生成的所生成的元素表元素表，可以将上式简化为，可以将上式简化为: : m mi i(x)= x(x)= x4 4+x+x +1+1当当a a3 3 时，则时，则2 2 a a6 6 ， 2222 a a1212， 2323 a a24 24 a a9 9

43、，均为根，均为根( (2424 a a48 48 a a3 3 不是新根不是新根) )。因此，类似地得到。因此，类似地得到m m3 3(x)=(x+a(x)=(x+a3 3) (x+a) (x+a5 5) (x+a) (x+a9 9) (x+a) (x+a1212)=x)=x4 4+ x+ x3 3 + x+ x2 2 +x+1 +x+1同理同理a a5 5 时，则时，则2 2 a a10 10 也为根也为根( (4 4 a a2020 a a5 5 不是新根不是新根) )。因此。因此m m5 5(x)=(x+a(x)=(x+a5 5) (x+a) (x+a1010) = x) = x2 2 +x+1 +x+1由于由于x x1616 +1 +1(x+1)(x(x+1)(x2 2 +x+1)(x +x+1)(x4 4+x+1)(x+x+1)(x4 4+ x+ x3 3