CRC的检错能力

第11周LectureNotes112006/4/251/3一.CyclicRedundancyCheck什么是CRC？循环码xc是xg的倍数，使得我们可以用图9.3.3这样的除法电路方便地得到伴随式xs。另外对于(n,k)循环码，xg是1nx的因子，这一点是循环性的来源，正是它使得具有循环关系的错误图样可以共享识别电路。如果我们只想检错，不打算纠错，则可以不要求xg是1nx的因子。事先选定一个r次的xg，将任意k个信息码组xu用类似图9.3.2这样的编码器编成系统码，得到一个长为rkn的码xc，则xc是xg的倍数。这就是CRC。由于k是任意的，因此xg将不一定是11krnxx的因子，故xc的循环移位1modnixxcx不一定是xg的倍数，即循环封闭的特性不能保证，即CRC不是循环码。但因为这种方法直接源自循环码，所以归在循环码中。CRC常用的生成多项式见表9.3.4CRC编译码器CRC编码器就是系统码的循环码编码器，如图9.3.5所示。CRC接收端（检错）和循环码译码器相同，但因为只是检错，所以不需要识别非0错误图样，不需要纠错电路，只需要识别余式是不是全零，如图9.3.6所示。CRC的检错能力1．CRC的编码结果是一个krk,分组码。前面讲过，分组码可保证检出1minde个错。但用最小码距来判断．．．．．．．．CRC．．．的检错能力是很不充分的．．．．．．．．．．．，因为CRC的最小码距有可能很小。线性分组码的最小码距是非0码的最小码重。码重就是xgxb（0xb，xb的次数不超过1k）中系数不为0的项的个数，例如xx4的码重是2。假如存在某个xb，使得1mxxgxb，则最小码距仅为2。如果出现121mmxx，021mm，则最小码距仅为3。而k的任意性不能排除这种情况的发生。注意前面我们说的是保证．．检出e位错，不是只能．．检出e位错。2．CRC的编码结果有k2种不同，它们都是xg的倍数。信道中可能发生的非全0错误图样共有1212rkn种。当错误图样能被xg整除，也即错误图样自身是编码器的可能输出之一时，这样的错误将骗过接收端。这种错误图样的个数是12k个，占总错误图样的比例为rrkk21212。例如：CRC-16不能检出的错误图样只是总可能错误图样的1621，约为六万分之一。3．上述的讨论不涉及信道中发生的错误是随机错还是突发错。突发错的定义是：错误只出现在连续L个比特内（这L个不一定都错，但这L个之外无错）。突发长度为L的突发错的第11周LectureNotes112006/4/252/3错误图样可以表示为xexm的形式，其中11Lxxe。注意到如果xe的次数1L小于xg的次数r，则xe不可能被xg整除，同样xexm也不能被xg整除。因此CRC可保证检出长度不超过11knr的突发错。比如CRC-16可以检出一切突发长度不超过16位的突发错。二.BCH码BCH码是循环码的一个子集，它的特点是(1)存在系统的方法设计各种需要的码。表9.4.1和表9.4.2是根据这些设计方法设计出的结果。注1：对于一般的线性分组码，我们没有一套系统的方法来回答像“设计一个(n,k)码使它能保证纠t个错”这样的问题。许多情况下，我们甚至不能判断这个问题有解还是无解。BCH能。注2：表9.4.1和表9.4.2中给出了八进制表示的xg。例如对于BCH(15,11)，表中给出的生成多项式是23，代表二进制的010011，即14xxxg(2)存在一些实用的译码算法三.RS码迄今为止，我们谈论的都是二进制编码。前述的分组码、线性分组码、循环码、BCH码的概念也可以是多进制的。q进制编码中的“数”不再是0、1，而是0、1、…q-1。所有二进制编码中的概念都可以拿到这里。比如生成矩阵、监督矩阵、生成多项式等。唯一的差别是：现在不是GF(2)上的运算，而是GF(q)上的运算。虽然GF(2)上的运算就是普通十进制运算的结果模二，但GF(q)上的运算不一定是普通运算模q。要想完全弄明白这些，你需要学更多的有限域（伽罗华域，GaloisField）方面的知识。RS码是q进制BCH的一个子类。四.加长与缩短实际中可能会遇到这样的情形，所设计出的编码的长度由于硬件位数或者其它原因感到不很方便。比如BCH可以给出(31,21)这样的设计，但设计硬件时也许更希望编码是32位的。此时可以把BCH(31,21)的编码结果再做一次偶校验补上一个校验位，从而形成一个(32,21)编码。这样的操作叫加长。接收端可以不理睬这个增加的校验比特，仍然按BCH(31,21)译码以便能够继续使用BCH的译码算法。不过这个比特也可以利用，比如至少可以用来判断BCH译码的结果是否正确。如果我们设计出的是BCH(17,9)，相应也有缩短的操作使它变成一个(16,8)编码。具体做法是，把BCH(17,9)的系统码编码器的9个输入信息位中的最高位固定为0（实际输入的只有8位信息），编码结果（是17位）的最高位自然也是固定的0，这个已知的比特没有必第11周LectureNotes112006/4/253/3要传送，故可删去，从而使编码器实际的输出只有16位。译码端在收到16位后，在最高位补上一个0，再按BCH(17,9)去译码，译码结果删去最高位，得到发送的8位信息。如果BCH(17,9)的译码结果最高位不是0（即译码器以为最高位有错），则知道译错了。Fig.1(17,9)缩短为(16,8)Fig.2用(17,9)译码器来译(16,8)编码注1：如果不借助BCH的设计，直接设计(32,21)或者(16,8)线性分组码将不是一件容易的事情。如果不借助BCH的译码器，设计出来以后怎么译也可能是个问题。注2：循环码经过上述的加长或者缩短后一般不再有循环封闭性。例如将生成多项式为13xx的(7,4)循环汉明码增加一位偶校验成为(8,4)码。(7,4)码的输出xc1是13xx的倍数。再对xc1作偶校验得到的结果xc2是1x的倍数。因此(8,4)码是1112343xxxxxxxg的倍数。但xg不是8811xx的因子，所以这个(8,4)码不是循环码。