CRC的检错能力-Read.doc

Cyclic Redundancy Check 什么是CRC？ 循环码是的倍数，使得我们可以用图9.3.3这样的除法电路方便地得到伴随式。另外对于(n,k)循环码，是的因子，这一点是循环性的来源，正是它使得具有循环关系的错误图样可以共享识别电路。 如果我们只想检错，不打算纠错，则可以不要求是的因子。事先选定一个r次的，将任意k个信息码组用类似图9.3.2这样的编码器编成系统码，得到一个长为的码，则是的倍数。这就是CRC。 由于k是任意的，因此将不一定是的因子，故的循环移位不一定是的倍数，即循环封闭的特性不能保证，即CRC不是循环码。但因为这种方法直接源自循环码，所以归在循环码中。 CRC常用的生成多项式见表9.3.4 CRC编译码器 CRC编码器就是系统码的循环码编码器，如图9.3.5所示。CRC接收端（检错）和循环码译码器相同，但因为只是检错，所以不需要识别非0错误图样，不需要纠错电路，只需要识别余式是不是全零，如图9.3.6所示。 CRC的检错能力 1．CRC的编码结果是一个分组码。前面讲过，分组码可保证检出个错。但用最小码距来判断CRC的检错能力是很不充分的，因为CRC的最小码距有可能很小。 线性分组码的最小码距是非0码的最小码重。码重就是（，的次数不超过）中系数不为0的项的个数，例如的码重是2。假如存在某个，使得，则最小码距仅为2。如果出现，，则最小码距仅为3。而k的任意性不能排除这种情况的发生。注意前面我们说的是保证检出e位错，不是只能检出e位错。 2．CRC的编码结果有种不同，它们都是的倍数。信道中可能发生的非全0错误图样共有种。当错误图样能被整除，也即错误图样自身是编码器的可能输出之一时，这样的错误将骗过接收端。这种错误图样的个数是个，占总错误图样的比例为。例如：CRC-16不能检出的错误图样只是总可能错误图样的，约为六万分之一。 3．上述的讨论不涉及信道中发生的错误是随机错还是突发错。突发错的定义是：错误只出现在连续L个比特内（这L个不一定都错，但这L个之外无错）。突发长度为L的突发错的错误图样可以表示为的形式，其中。注意到如果的次数小于的次数r，则不可能被整除，同样也不能被整除。因此CRC可保证检出长度不超过的突发错。比如CRC-16可以检出一切突发长度不超过16位的突发错。 BCH 码 BCH码是循环码的一个子集，它的特点是 存在系统的方法设计各种需要的码。表9.4.1和表9.4.2是根据这些设计方法设计出的结果。 注1：对于一般的线性分组码，我们没有一套系统的方法来回答像“设计一个(n,k)码使它能保证纠t个错”这样的问题。许多情况下，我们甚至不能判断这个问题有解还是无解。BCH能。 注2：表9.4.1和表9.4.2中给出了八进制表示的。例如对于BCH(15,11)，表中给出的生成多项式是23，代表二进制的010 011，即 存在一些实用的译码算法 RS码 迄今为止，我们谈论的都是二进制编码。前述的分组码、线性分组码、循环码、BCH码的概念也可以是多进制的。 q进制编码中的“数”不再是0、1，而是0、1、…q-1。所有二进制编码中的概念都可以拿到这里。比如生成矩阵、监督矩阵、生成多项式等。唯一的差别是：现在不是GF(2)上的运算，而是GF(q)上的运算。虽然GF(2)上的运算就是普通十进制运算的结果模二，但GF(q)上的运算不一定是普通运算模q。要想完全弄明白这些，你需要学更多的有限域（伽罗华 Fig. 1 (17,9)缩短为(16,8) Fig. 2 用(17,9)译码器来译(16,8)编码 注1：如果不借助BCH的设计，直接设计(32,21)或者(16,8)线性分组码将不是一件容易的事情。如果不借助BCH的译码器，设计出来以后怎么译也可能是个问题。 注2：循环码经过上述的加长或者缩短后一般不再有循环封闭性。例如将生成多项式为 的(7,4)循环汉明码增加一位偶校验成为(8,4)码。(7,4)码的输出是的倍数。再对作偶校验得到的结果是的倍数。因此(8,4)码是的倍数。但不是的因子，所以这个(8,4)码不是循环码。 第11周 Lecture Notes 11 2006/4/25 1/3