差错控制码编码原理.doc

1．垂直奇偶校验码： 编码原理： （1）将整个发送的数据块分为定长为m的n个组，一般m为字符位数或位数的倍数，一组称为一个码字。 （2）每组末位按“1”的个数位奇数或者偶数的规律加一个校验位（），使得每组包括校验位在内“1”的个数为奇数或偶数。为偶数的称为偶校验，为奇数的称为奇校验。 （为一个比特位，运算为二进制运算） 校验位计算为： 偶校验 奇校验 举例说明： 每一列代表一个码字： 偶校验计算的校验位为： 奇校验计算的校验位为： 校验能力：只能检测每列码字中的奇数个错误，所有偶数个错误全部漏检。 实现方法：用硬件和软件均可，可以边发送边产生冗余位，接收时可以边接收边去掉冗余位。 2．水平奇偶校验码 编码原理： （1）将整个发送的数据块分为定长为m的n个组，一般m为字符位数或位数的倍数，一组称为一个码字。 （2）将n个码字排成一个矩阵，对各个码字相应横向位进行奇偶校验。（校验位的生成与垂直奇偶校验码生成方式一致）。 偶校验 奇校验 （3）发送时将所有码字发送完后发送校验位。 举例说明： 奇 偶 每一列代表一个码字： 校验能力：可以检测各个码字同一位上的奇数位错，对于长度小于或等于m的突发错误，由于分布在不同行中，可以检测到。 实现方式：用硬件和软件均可，需要借助存储器。 3．水平垂直奇偶校验 编码原理：同时进行垂直和奇偶校验。 （过程略） 校验能力：冗余度大，具有更强检错能力。可检验3位以下的全部错误，所有奇数位错，突发长度小于或等于m+1的突发错误以及绝大多数偶数位错。 4、斜奇偶校验 编码原理：在水平垂直奇偶校验码的基础上，按照斜对角线的方向计算出校验位。 校验能力：冗余位更多，编、译码较为复杂，校验能力更强。 正反码： 举例说明： 码长n＝10，信息位k＝5，校验位r＝5，若信息位为11001，校验位为11001，码字为1100111001；若信息位为10001，校验位为01110，码字为1000101110。 纠错规则： 校验码组 差错情况 全0 无差错 4个1，1个0 信息位有一位错，对应于校验位中0的位置 4个0，1个1 校验位有一位错，对应于校验位中1的位置 其他情况 差错在两位或两位以上 若发送码字1100111001， 接收码字1100111001（传输中无错）， 合成码为11001＋11001＝00000， 接收码信息位有3个1，校验码为00000。据上表，没有发生错误。 接收码字1000111001 合成码为10001＋11001＝01000， 接收码信息位有偶数个1，校验码为合成码的反码10111，据上表，信息位第二位出错。 （同学自己举例说明其他情况）。 循环冗余校验码 1、码多项式 如果把一个码字中的各位看作是一个多项式的系数，则长为n的码字可以表示为一个多项式： 该多项式称为码字的码多项式。 如：码字11001的码多项式为： 2、多项式的按模运算 在CRC中，常需要进行码多项式的运算，运算规则为按模2运算。若任意的n次多项式被一个k次多项式除，得到商式和余式（次数必然小余k），则表示为 。 3、循环冗余码 长为n的码，信息位为k位的码记为（n，k）码。若一个码字集合满足以下两个条件：（1）循环性：码集中的任一个码字向左或右循环一位，得到的新的码字，仍为码集中的码字。 （2）封闭性：码集中任意两个码字之和仍为码集中的码字。 则称此码集为（n，k）循环码。 例：是码集中的码字，是码集中的码字，全零码字必然是码集中的码字。 4、循环冗余码的生成多项式 定理1 在循环冗余码（n，k）中，存在且只有一个（n－k）次的码多项式 满足： （1）此循环冗余码中任一多项式都是的倍式； （2）任意一个（n－1）次或（n－1）次以下的，又是倍式的多项式必定是此循环码中的一个码多项式。 （生成多项式的寻找有严密的代数背景，略） 5、循环冗余码的编码 一般是已知信息位，根据信息位求冗余位。 信息位为，码多项式为 冗余位为，码多项式为 码字为，码多项式为 （1） 码字是生成多项式的倍式，则 （2） 由（1）（2）两式得 ＝ 即 ＝ 所以用去除以生成多项式得到的余式就是码字的校验位。 编码算法： （1）用乘以信息位对应的码多项式； （2）用生成多项式去除，得余式； （3）将对应的码字加在信息位后发送即可。 6、循环冗余码的译码 （1）检错过程 发送方发送码字，设接收方接收码字为，根据 若＝，则有 即除以没有余式。 若，则