logo资料库

海明纠错码与CRC循环冗余校验.doc

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：0.30M 资料格式：doc 举报 版权申诉
第1页 / 共20页
第2页 / 共20页
第3页 / 共20页
第4页 / 共20页
第5页 / 共20页
第6页 / 共20页
第7页 / 共20页
第8页 / 共20页
资料共20页，剩余部分请下载后查看
    (一)CRC循环冗余校验
    一、循环冗余校验的数学模型
    二、基本思想
    三、代码编写
    (二)海明纠错码
    一、基本思想
    二、纠错机制
    三、代码编写
    (三)心得体会
    计算机网络作业： 海明纠错码与 CRC 循环冗余校验 院系：控制科学与工程系 姓名：许伟波 U200813539 陈龙 U200813648 班级：自动化 0806 班
    (一) CRC 循环冗余校验 一、 循环冗余校验的数学模型 循环冗余校验简称循环码或CRC 码(Cyclic Redundancy Check) , 是一种高效能的检错和纠错码, 在数据通信中应用甚广。 循环码编码通过模2运算来建立信息位和校验位之间的约束关系。首 先将所传数据看成高次多项式, 把此多项式除以预先给定的生成多 项式, 其余 数作为校验位附加在所传数据的尾部一并传送, 即在一个长度为n 的码组中有k 个信息和r 个校验位。译码时用同样的生成多项式去除, 若余数为零, 则可判断收到的数据是正确的。 假设待编码的k 位信息是: M = (mk- 1,mk - 2, ⋯,m2,m1,m0) 它所对应的信息多项式是: M (x ) = mk- 1xk- 1+ mk- 2x k- 2+ ⋯+ m2x2+ m1x + m0 用xn-k乘M (x ) 得: xn- kM (x ) = mk- 1x n- 1+ mk- 2xn- 2+ ⋯+ m2xn- k+ 2+ m1xn- k+ 1+ m0xn- k 用给定的(n, k ) 循环码生成多项式g (x ) 除xn- k·M (x ) 得: xn- k·M (x ) = q (x ) ·g (x ) + R (x ) (1) 式中q (x ) 和R (x ) 分别是除法的商式和余式。因为生成多项式g (x ) 是(n- k ) 次, 所以R (x )一定是等于或小于(n- k - 1) 次, 即: R (x ) = rn- k- 1xn- k - 1+ rn- k - 2xn- k- 2+ ⋯+ r2x 2+ r1x + r0 由(1) 式得xn- k·M (x ) + R (x ) = q (x ) ·g (x ) , 上式表明
    xn- k·M (x ) + R (x ) 是g (x )的倍式, 其次数等于或小于(n- 1)。 所以xn- k·M (x ) + R (x ) 是g (x ) 生成的循环码的一个 码多项式, 把xn- k·M (x ) + R (x ) 展开得: xn- k·M(x) + R(x) = mk- 1·xn- 1+ m k- 2·x n- 2+ ⋯+ m2xn- k+ 2+ m1xn-k+1 + m0xn- k+ rn- k- 1xn- k- 1+ rn- k- 2xn- k - 2+ ⋯+ r2x2+ r1x + r0 此码多项式对应的码字是: (mk- 1,m k- 2 , ⋯m 2,m 1,m0, rn- k - 1, rn- k- 2⋯r2, r1, r0) 所以码字是由不加改变的k 位信息码元, 其后再附加(n- k) 位校验 码元组成的。 在接收端, 对收到的码字进行译码, 即除以g (x ) [x n- k·M (x ) + R (x ) ]/g (x ) = [q (x ) ·g (x ) + R (x ) + R (x ) ]/g (x ) = q (x ) ·g (x )/g (x ) = q (x ) 若传输正确, 则余数为零, 当余数为非零时, 判断数据传送有误, 以达到数据通信的检错目的。 例如: 对于(7, 3) 循环码, 待编码的信息为M = 101, 生成多项 式g (x ) = x 4+ x 3+ x2+ 1, 则M (x ) = x2+ 1 x7- 3·M (x ) = x 4 (x2+ 1) = x 6+ x 4, 其码字为1010000, 运用 长除法, 所以码字为1010011, 传送时将信息位与校验位一同发出, 在接收方译码时, 也采用相同的长除法。若余数为零, 则接收正确。
    二、 基本思想 首先了解一下 CRC 的工作方法，CRC 是指在发送端产生一个 循环冗余码，附加在信息位后面一起发送到接收端，接收端收到 的信息按发送端形成循环冗余码同样的算法进行校验，若有错， 需重发，这与海明纠错码不同。 CRC 校验码的编码方法是用待发送的二进制数据 t（x）除以 生成多项式 g（x），将最后的余数作为 CRC 校验码。 其实现步骤如下： （1）设待发送的数据块是 m 位的二进制多项式 t（x） （2）生成多项式为 r 阶的 g（x）。在数据块的末尾添 加 r 个 0 （3） 数据块的长度增加到 m+r 位 （4） 对应的二进制多项式为 t（x）左移 r 位。 （5） 用生成多项式 g（x）去除 （6） 求得余数为阶数为 r-1 的二进制多项式 y（x）。此二进制 多项式 y（x）就是 t（x）经过生成多项式 g（x）编码的 CRC 校 验码。 （7） 用 以模 2 的方式减去 y（x） （8） 得到二进制多项式就是包含了 CRC 校验码的待发送字符串。 从 CRC 的编码规则可以看出，CRC 编码实际上是将代发送的 m 位二进制多项式 t（x）转换成了可以被 g（x）除尽的 m+r 位二进 制多项式 ，所以解码时可以用接受到的数据去除 g（x），如果 余数位零，则表示传输过程没有错误；如果余数不为零，则在传
    输过程中肯定存在错误。许多 CRC 的硬件解码电路就是按这种方 式进行检错的。 同时可以看做是由 t（x）和 CRC 校验码的组合，所以解码时 将接收到的二进制数据去掉尾部的 r 位数据，得到的就是原始数 据。 三、 代码编写 CRC 循环冗余校验可以利用 verilog 和 c 语言实现，考虑到多种因素 我们采用 c 语言进行实现。 具体程序如下： #include "stdio.h"/*头文件*/ void Crc(int A[],int G[], int x,int n);/*对函数进行声明，此函数是 CRC 校验算法 的工作函数*/ void main()/*News[x]为信息码，Out[x]为生成码，A[x]为 News[x]的多项式和 Out[x] 的多项式的积所对应的码字,m 和 n 分别为 News[x]和 Out[x]的码长度*/ { int m,n; int A[20],News[20],Out[20],i,j; printf("请输入 News[x]的长度 m=");/*输入信息码的长度 m*/ scanf("%d",&m); printf("请输入 Out[x]的长度 n=");/*输入生成码的长度 n*/ scanf("%d",&n); printf("\n 请输入 News[x]=");/*输入信息码 News[x]*/ for(i=0;i<=m-1;i++) scanf("%d",&News[i]);
    printf("\n 请输入 G[n]=");/*输入生成码 G[n]*/ for (j=0;j<=n-1;j++) scanf("%d",&Out[j]); for (i=0;i<=m-1;i++)/*先把信息码放入数组 A 中*/ A[i]=News[i]; for (i=m;i<=m+n-2;i++)/*把 A 数组中余下的长度补 0，A 数组将是被除数，即 A[x]为 News[x]的多项式和 Out[x]的多项式的积所对应的码字*/ A[i]=0; printf("\n"); printf("News[x] 的 多 项 式 和 Out[x] 的 多 项 式 的 积 所 对 应 的 码 字:");/* 输 出 News[x]的多项式和 Out[x]的多项式的积所对应的码字*/ for(i=0;i<=m+n-2;i++) printf(" %d",A[i]); printf("\n"); Crc(A,Out,m+n-1,n); /*调用 CRC 函数*/ printf("\n\n"); printf("输出冗余码:");/*输出冗余码*/ for(i=0;i<=m+n-2;i++) printf(" %d",A[i]); printf("\n"); for (i=0;i<=m-1;i++)/*将余数拼到信息码左移后空出的位置,得到完整的 CRC 码.*/ A[i]=A[i]+News[i]; printf ("\n 结果为：");/*输出 CRC 校验结果*/ for (i=0;i<=m+n-2;i++) printf("%d",A[i]); printf("\n"); }
    void Crc(int A[],int Out[], int x,int n)/*A[x]为 News[x]的多项式和 Out[x]的多项 式的积所对应的码字，Out[]为生成码*/ { int i,j,k; printf("\n"); for (k=0;k<=x-1;k++)/*输出 A[x]*/ printf("%d",A[k]); for (i=0;i<=x-n+1;i++)/*开始运算*/ { if (A[i]==1) /*看首位是否为 1，若为 1 继续*/ { for (j=0;j<=n-1;j++) { if(A[i+j]==Out[j])/*若相同为 0，不同为 1*/ else A[i+j]=0; A[i+j]=1; } printf("\n");/*输出每次比较运算后的结果*/ for (k=0;k<=x-1;k++) printf("%d",A[k]);/*输出最后的余数,注意此处的 A 数组已经变了，和 函数入口处的 A 数组时不同的，此处存放的是运算后的余数*/ } } } 其中：News[x]为信息码，Out[x]为生成码，A[x]为 News[x]的多项式和 Out[x]的 多项式的积所对应的码字，m 和 n 分别为 News[x]和 Out[x]的码长度； void Crc(int A[],int G[], int x,int n);为 CRC 算法的核心函数，其原理是通过一种异 或的思想得出模 2 运算所需的余数
    在调用 void Crc(int A[],int G[], int x,int n)之后 A[x]内存储的是余数，而不是之前 的数据。 运行结果： (二) 海明纠错码 一、 基本思想 将有效信息按某种规律分成若干组，每组安排一个校验位，做奇 偶测试，就能提供多位检错信息，以指出最大可能是哪位出错，从而 将其纠正。实质上，海明校验是一种多重校验。
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料