加载中…
CRC校验原理，检错能力分析以及代码实现
(2015-04-29 09:44:38)
标签：
杂谈 |
看了计算机网络书上介绍CRC检错的部分，感觉关于检错能力分析的部分说得很不清楚，很难理解，最后看了英文原版的才终于看明白了，整理一下吧。
1.CRC校验介绍
在数据链路层，在成帧和发送帧的过程中，纠错机制或者检错机制是很必要的。在网络环境相对较好的网络中，由于错误率较低，所以往往检错码的效率更高，具体原因就不在这里介绍了，可以参看《计算机网络(第5版)》。这里主要要介绍一种常用的检错码，即循环冗余校验(CRC校验)。
另一种较出名的方法是简单的奇偶校验，即在数据最后加上以为奇偶校验位，使得整个数据流1的个数为奇数后者偶数(根据是 奇校验还是偶校验)。但是这种方法成功检错的概率只有50%( 想一想为什么？)。CRC和它不同的是利用了多项式除法，通过选取合适的生成多项式来达到良好的检错能力，下面来看看具体是怎么做的。
首先引进多项式编码的概念，即将位串看做多项式，位串中的0,1看做多项式系数，次数坐高右低，如位串110001即代表多项式
http://araleii.com/wp-content/uploads/2015/04/CRC1-300x45.jpg
多项式的算数运算都是模2运算，即加法无进位，减法无借位，其实就是加法减法都一样，都是异或运算。如：
http://araleii.com/wp-content/uploads/2015/04/CRC2-300x50.jpg
好了，现在知道了怎么把位串看成多项式和多项式的运算方式了，现在来看看CRC校验的整个过程，一共主要分3步，选择生成多项式，原串补0，加上余数。
使用CRC校验的时候，发送方和接收方必须要预先统一商定一个生成多项式G(x),生成多项式的最高和最低位必须都是1，
2.CRC检错能力分析
3.代码实现
3.1
#include<stdio.h>
#include<string.h>
char resFrame[1010];
void trim(char *s)
{
int i, j, len;
len = strlen(s);
for(i = 0; i < len; i++)
{
if(s[i] != '0')break;
}
for(j = 0; j < len - i; j++ )
{
s[j] = s[j + i];
}
s[len - i] = '\0';
}
char *generator(char *srcFrame, char *G)
{
int i, j, k;
int r, len, rlen;
r = strlen(G);
len = strlen(srcFrame);
for(i = 0; i < len; i++)
{
resFrame[i] = srcFrame[i];
}
for(i = 0; i < r - 1; i++)
{
resFrame[len + i] = '0';
resFrame[len + i + 1] = '\0';
}
len = strlen(resFrame);
char remainder[1010] = {'\0'};
i = 0;
while(i < len)
{
rlen = strlen(remainder);
while(strlen(remainder) < r && i < len)
{
rlen = strlen(remainder);
remainder[rlen] = resFrame[i];
remainder[rlen + 1] = '\0';
i++;
}
if(strlen(remainder) == r)
{
for(k = 0; k < r; k++)
{
remainder[k] = ((remainder[k] - '0') ^ (G[k] - '0')) + '0';
}
trim(remainder);
}
}
rlen = strlen(remainder);
//printf("~%s\n", remainder);
//printf("~%d %d\n", r,rlen);
for(i = 0; i < rlen; i++)//补上前导0
{
remainder[i + len - rlen] = remainder[i];
}
// printf("~%s\n", remainder);
for(i = 0; i < len - rlen; i++)
{
remainder[i] = '0';
}
remainder[len] = '\0';
//printf("~~~~%s\n", remainder);
// printf("res:%s\n", resFrame);
for(i = 0; i < len; i++ )//在结果帧上加上余数
{
resFrame[i] = ((resFrame[i ] - '0') ^ (remainder[i ] - '0')) + '0';
}
// printf("src:%s\n", srcFrame);
// printf("res:%s\n", resFrame);
// printf("pol:%s\n", G);
return resFrame;
}
char sourceFrame[1010],Gx[1010];
int main()
{
freopen("generatorIn","r",stdin);
freopen("generatorOut","w",stdout);
scanf("%s%s",sourceFrame,Gx);
printf("%s\n", generator(sourceFrame,Gx));
printf("%s",Gx);
//printf("res:%s\n", calCRC("1101011111", "10011"));
return 0;
}
3.2 verifier
#include<stdio.h>
#include<string.h>
void trim(char *s)
{
int i, j, len;
len = strlen(s);
for(i = 0; i < len; i++)
{
if(s[i] != '0')break;
}
for(j = 0; j < len - i; j++ )
{
s[j] = s[j + i];
}
s[len - i] = '\0';
}
int verifier(char *srcFrame,char *G)
{
int i, j, k;
int r, len, rlen;
r = strlen(G);
len = strlen(srcFrame);
char remainder[1010] = {'\0'};
i = 0;
while(i < len)
{
rlen = strlen(remainder);
while(strlen(remainder) < r && i < len)
{
rlen = strlen(remainder);
remainder[rlen] = srcFrame[i];
remainder[rlen + 1] = '\0';
i++;
}
if(strlen(remainder) == r)
{
for(k = 0; k < r; k++)
{
remainder[k] = ((remainder[k] - '0') ^ (G[k] - '0')) + '0';
}
trim(remainder);
}
}
rlen = strlen(remainder);
for(i=0;i<rlen;i++)
{
if(remainder[i]!='0')return 0;
}
return 1;
}
char sourceFrame[1010];
char Gx[1010];
int main()
{
freopen("generatorOut","r",stdin);
scanf("%s%s",sourceFrame,Gx);
if(verifier(sourceFrame,Gx)){
printf("True frame!\n");
}else{
printf("Bad frame!\n");
}
return 0;
}
3.3 alter
#include<stdio.h>
#include<string.h>
void alter(int ind,char *src)
{
int i;
int len = strlen(src);
for(i=ind-1;i<len;i++)
{
if(src[i]=='1')
{
src[i]='0';
}
}
}
char src[1010];
char G[1010];
int ind;
int main(int argc,char *argv[])
{
freopen("generatorOut","r",stdin);
//scanf("%d",&ind);
ind = argv[1][0]-'0';
scanf("%s%s",src,G);
alter(ind,src);
freopen("generatorOut","w",stdout);
printf("%s\n%s\n",src,G);
return 0;
}
#include<stdio.h>
#include<string.h>
char frameForSending[1010];
void deleteFrontSpace(char *s) {
int i, j, len;
len = strlen(s);
for(i = 0; i < len; i++)if(s[i] != '0')break;
for(j = 0; j < len - i; j++ )s[j] = s[j + i];
s[len - i] = '\0';
}
char *generator(char *srcData, char *G) {
int i, j, k, gLen, len, remainderLen;
char remainder[1010] = {'\0'};
gLen = strlen(G);
len = strlen(srcData);
for(i = 0; i < len; i++)frameForSending[i] = srcData[i];
for(i = 0; i < gLen - 1; i++) {
frameForSending[len + i] = '0';
frameForSending[len + i + 1] = '\0';
}
len = strlen(frameForSending);
i = 0;
while(i < len) {
remainderLen = strlen(remainder);
while(strlen(remainder) < gLen && i < len) {
remainderLen = strlen(remainder);
remainder[remainderLen] = frameForSending[i];
remainder[remainderLen + 1] = '\0';
i++;
}
if(strlen(remainder) == gLen) {
for(k = 0; k < gLen; k++)remainder[k] = ((remainder[k] - '0') ^ (G[k] - '0')) + '0';
deleteFrontSpace(remainder);
}
}
remainderLen = strlen(remainder);
for(i = 0; i < remainderLen; i++)remainder[i + len - remainderLen] = remainder[i];
for(i = 0; i < len - remainderLen; i++)remainder[i] = '0';
remainder[len] = '\0';
for(i = 0; i < len; i++ )frameForSending[i] = ((frameForSending[i ] - '0') ^ (remainder[i ] - '0')) + '0';
return frameForSending;
}
char sourceFrame[1010], Gx[1010];
int main() {
freopen("file", "r", stdin);
freopen("generatorOut", "w", stdout);
scanf("%s%s", sourceFrame, Gx);
printf("%s\n", generator(sourceFrame, Gx));
printf("%s", Gx);
return 0;
}
#include<stdio.h>
#include<string.h>
void deleteFrontSpace(char *s) {
int i, j, len;
len = strlen(s);
for(i = 0; i < len; i++) {
if(s[i] != '0')break;
}
for(j = 0; j < len - i; j++ ) {
s[j] = s[j + i];
}
s[len - i] = '\0';
}
int verifier(char *srcFrame, char *G) {
int i, j, k, gLen, len, remainderLen;
gLen = strlen(G);
len = strlen(srcFrame);
char remainder[1010] = {'\0'};
i = 0;
while(i < len) {
remainderLen = strlen(remainder);
while(strlen(remainder) < gLen && i < len) {
remainderLen = strlen(remainder);
remainder[remainderLen] = srcFrame[i];
remainder[remainderLen + 1] = '\0';
i++;
}
if(strlen(remainder) == gLen) {
for(k = 0; k < gLen; k++) {
remainder[k] = ((remainder[k] - '0') ^ (G[k] - '0')) + '0';
}
deleteFrontSpace(remainder);
}
}
remainderLen = strlen(remainder);
for(i = 0; i < remainderLen; i++) {
if(remainder[i] != '0')return 0;
}
return 1;
}
char srcData[1010];
char Gx[1010];
int main() {
freopen("generatorOut", "r", stdin);
scanf("%s%s", srcData, Gx);
if(verifier(srcData, Gx))printf("Good frame!\n");
else printf("Bad frame!\n");
return 0;
}
#include<stdio.h>
#include<string.h>
void alter(int dataIndex, char *srcData) {
int i;
int len = strlen(srcData);
for(i = dataIndex - 1; i < len; i++) {
if(srcData[i] == '1') {
srcData[i] = '0';
}
}
}
char srcData[1010];
char G[1010];
int dataIndex;
int main(int argc, char *argv[]) {
freopen("generatorOut", "r", stdin);
dataIndex = argv[1][0] - '0';
scanf("%s%s", srcData, G);
alter(dataIndex, srcData);
freopen("generatorOut", "w", stdout);
printf("%s\n%s\n", srcData, G);
return 0;
}
推荐的参考资料
1.wiki百科
喜欢
0
赠金笔
前一篇：回退N协议源码分析
后一篇：原来word也可以发布文章