cyclic redundancy check

《cyclic redundancy check》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第11周LectureNotes112006/4/25一.CyclicRedundancyCheck什么是CRC？循环码是的倍数，使得我们可以用图9.3.3这样的除法电路方便地得到伴随式。另外对于(n,k)循环码，是的因子，这一点是循环性的来源，正是它使得具有循环关系的错误图样可以共享识别电路。如果我们只想检错，不打算纠错，则可以不要求是的因子。事先选定一个r次的，将任意k个信息码组用类似图9.3.2这样的编码器编成系统码，得到一个长为的码，则是的倍数。这就是CRC。由于k是任意的，因此将不一定是的因子，故的循环移位不一定是的倍数，即循环封闭的特性不能保证，即CRC不是循环码。

2、但因为这种方法直接源自循环码，所以归在循环码中。CRC常用的生成多项式见表9.3.4CRC编译码器CRC编码器就是系统码的循环码编码器，如图9.3.5所示。CRC接收端（检错）和循环码译码器相同，但因为只是检错，所以不需要识别非0错误图样，不需要纠错电路，只需要识别余式是不是全零，如图9.3.6所示。CRC的检错能力1．CRC的编码结果是一个分组码。前面讲过，分组码可保证检出个错。但用最小码距来判断CRC的检错能力是很不充分的，因为CRC的最小码距有可能很小。线性分组码的最小码距是非0码的最小码重。码重就是（，的次数不超过）中系数不为0的项的个数，例如的码重是2。假如存在某个，

3、使得，则最小码距仅为2。如果出现，，则最小码距仅为3。而k的任意性不能排除这种情况的发生。注意前面我们说的是保证检出e位错，不是只能检出e位错。2．CRC的编码结果有种不同，它们都是的倍数。信道中可能发生的非全0错误图样共有种。当错误图样能被整除，也即错误图样自身是编码器的可能输出之一时，这样的错误将骗过接收端。这种错误图样的个数是个，占总错误图样的比例为。例如：CRC-16不能检出的错误图样只是总可能错误图样的，约为六万分之一。3．上述的讨论不涉及信道中发生的错误是随机错还是突发错。突发错的定义是：错误只出现在连续L个比特内（这L个不一定都错，但这L个之外无错）。突发长度为L

4、的突发错的错误图样可以表示为的形式，其中。注意到如果的次数3/3第11周LectureNotes112006/4/25小于的次数r，则不可能被整除，同样也不能被整除。因此CRC可保证检出长度不超过的突发错。比如CRC-16可以检出一切突发长度不超过16位的突发错。一.BCH码BCH码是循环码的一个子集，它的特点是(1)存在系统的方法设计各种需要的码。表9.4.1和表9.4.2是根据这些设计方法设计出的结果。注1：对于一般的线性分组码，我们没有一套系统的方法来回答像“设计一个(n,k)码使它能保证纠t个错”这样的问题。许多情况下，我们甚至不能判断这个问题有解还是无解。BCH能。注

5、2：表9.4.1和表9.4.2中给出了八进制表示的。例如对于BCH(15,11)，表中给出的生成多项式是23，代表二进制的010011，即(2)存在一些实用的译码算法二.RS码迄今为止，我们谈论的都是二进制编码。前述的分组码、线性分组码、循环码、BCH码的概念也可以是多进制的。q进制编码中的“数”不再是0、1，而是0、1、…q-1。所有二进制编码中的概念都可以拿到这里。比如生成矩阵、监督矩阵、生成多项式等。唯一的差别是：现在不是GF(2)上的运算，而是GF(q)上的运算。虽然GF(2)上的运算就是普通十进制运算的结果模二，但GF(q)上的运算不一定是普通运算模q。要想完全弄明白

6、这些，你需要学更多的有限域（伽罗华域，GaloisField）方面的知识。RS码是q进制BCH的一个子类。三.加长与缩短实际中可能会遇到这样的情形，所设计出的编码的长度由于硬件位数或者其它原因感到不很方便。比如BCH可以给出(31,21)这样的设计，但设计硬件时也许更希望编码是32位的。此时可以把BCH(31,21)的编码结果再做一次偶校验补上一个校验位，从而形成一个(32,21)编码。这样的操作叫加长。接收端可以不理睬这个增加的校验比特，仍然按BCH(31,21)译码以便能够继续使用BCH的译码算法。不过这个比特也可以利用，比如至少可以用来判断BCH译码的结果是否正确。如果我

7、们设计出的是BCH(17,9)，相应也有缩短3/3第11周LectureNotes112006/4/25的操作使它变成一个(16,8)编码。具体做法是，把BCH(17,9)的系统码编码器的9个输入信息位中的最高位固定为0（实际输入的只有8位信息），编码结果（是17位）的最高位自然也是固定的0，这个已知的比特没有必要传送，故可删去，从而使编码器实际的输出只有16位。译码端在收到16位后，在最高位补上一个0，再按BCH(17,9)去译码，译码结果删去最高位，得到发送的8位信息。如果BCH(17,