Cyclic redundancy check implementation using C

Cyclic redundency Check

Cyclic Redundency Check

A cyclic redundancy check (CRC) or polynomial code checksum is a hash function designed to detect accidental changes to raw computer data, and is commonly used in digital networks and storage devices such as hard disk drives. A CRC-enabled device calculates a short, fixed-length binary sequence, known as the CRC code or just CRC, for each block of data and sends or stores them both together. When a block is read or received the device repeats the calculation; if the new CRC does not match the one calculated earlier, then the block contains a data error and the device may take corrective action such as rereading or requesting the block be sent again, otherwise the data is assumed to be error free (though, with some small probability, it may contain undetected errors; this is the fundamental nature of error-checking).

CRCs are so called because the check (data verification) code is a redundancy (it adds zero information to the message) and the algorithm is based on cyclic codes. The term CRC may refer to the check code or to the function that calculates it, which accepts data streams of any length as input but always outputs a fixed-length code. CRCs are popular because they are simple to implement in binary hardware, are easy to analyze mathematically, and are particularly good at detecting common errors caused by noise in transmission channels. The CRC was invented by W. Wesley Peterson in 1961; the 32-bit polynomial used in the CRC function of Ethernet and many other standards is the work of several researchers and was published in 1975.

A CRC is an error-detecting code. Its computation resembles a polynomial long division operation in which the quotient is discarded and the remainder becomes the result, with the important distinction that the polynomial coefficients are calculated according to the carry-less arithmetic of a finite field. The length of the remainder is always less than the length of the divisor (called the generator polynomial), which therefore determines how long the result can be. The definition of a particular CRC specifies the divisor to be used, among other things.

Although CRCs can be constructed using any finite field, all commonly used CRCs employ the finite field GF(2). This is the field of two elements, usually called 0 and 1, comfortably matching computer architecture. The rest of this article will discuss only these binary CRCs, but the principles are more general.

An important reason for the popularity of CRCs for detecting the accidental alteration of data is their efficiency guarantee. Typically, an n-bit CRC, applied to a data block of arbitrary length, will detect any single error burst not longer than n bits (in other words, any single alteration that spans no more than n bits of the data), and will detect a fraction 1−2⁻ⁿ of all longer error bursts. Errors in both data transmission channels and magnetic storage media tend to be distributed non-randomly making CRCs' properties more useful than alternative schemes such as multiple parity checks.

The simplest error-detection system, the parity bit, is in fact a trivial 1-bit CRC: it uses the generator polynomial x+1.

Cyclic redundancy check using C

//Program to add crc check bit

#include<stdio.h>
#include<string.h>
#define N strlen(g)

char t[28],cs[28],g[]="10001000000100001";
int a,e,c;

void xor(){
	for(c = 1;c < N; c++)
	cs[c] = (( cs[c] == g[c])?'0':'1');
}

void crc(){
	for(e=0;e<N;e++)
		cs[e]=t[e];
	do{
		if(cs[0]=='1')
			xor();
		for(c=0;c<N-1;c++)
			cs[c]=cs[c+1];
		cs[c]=t[e++];
	}while(e<=a+N-1);
}

int main()
{
	printf("\nEnter data : ");
	scanf("%s",t);
	printf("\n----------------------------------------");
	printf("\nGeneratng polynomial : %s",g);
	a=strlen(t);
	for(e=a;e<a+N-1;e++)
		t[e]='0';
	printf("\n----------------------------------------");
	printf("\nModified data is : %s",t);
	printf("\n----------------------------------------");
	crc();
	printf("\nChecksum is : %s",cs);
	for(e=a;e<a+N-1;e++)
		t[e]=cs[e-a];
	printf("\n----------------------------------------");
	printf("\nFinal codeword is : %s",t);
	printf("\n----------------------------------------");
	printf("\nTest error detection 0(yes) 1(no)? : ");
	scanf("%d",&e);
	if(e==0)
	{
		do{
			printf("\nEnter the position where error is to be inserted : ");
			scanf("%d",&e);
		}while(e==0 || e>a+N-1);
		t[e-1]=(t[e-1]=='0')?'1':'0';
		printf("\n----------------------------------------");
		printf("\nErroneous data : %s\n",t);
	}
	crc();
	for(e=0;(e<N-1) && (cs[e]!='1');e++);
		if(e<N-1)
			printf("\nError detected\n\n");
		else
			printf("\nNo error detected\n\n");
			printf("\n----------------------------------------\n");
		return 0;
}

Makefile

a.out:crc.c
	gcc -ggdb crc.c
PHONY:clean
clean:
	rm a.out *~

Example output

Enter data : 1101

----------------------------------------
Generatng polynomial : 10001000000100001
----------------------------------------
Modified data is : 11010000000000000000
----------------------------------------
Checksum is : 1101000110101101
----------------------------------------
Final codeword is : 11011101000110101101
----------------------------------------
Test error detection 0(yes) 1(no)? : 0

Enter the position where error is to be inserted : 2

----------------------------------------
Erroneous data : 10011101000110101101

Error detected

----------------------------------------

More Codes

Implementation of Handwritten lexer and parser
Overview β - parse language is the beta version of parsing of our own language. It involves the best possibilities that we have seen from the classic language ‘C’. Our language is purely a subset of the higher level language - ’C’. It takes... - 15 months ago
C for TCS placement
1. Which of the following is invalid (a) a+=b (b) a*=b (c) a>>=b (d) a**=b 2. What is y value of the code if input x=10 y=5; if (x==10) else if(x==9) else y=8; (a)9 ... - 17 months ago
Toughest Interview Questions
1. Talk about yourself. 2. What was your last salary? 3. Have you ever laid off or fired a person? 4. How do you react when you realize that you have made a mistake? 5. Are you willing to lower your salary... - 17 months ago
simulation of solar system using OpenGL
#include<GL/glut.h> #include<stdio.h> #include<math.h> #include<stdlib.h> #include<string.h> #define XCOORDINATE 0 #define YCOORDINATE 1 #define ZCOORDINATE 2 #define ROT_ANGLE 2 #define SUN 0 #define MERCURY... - 17 months ago
some C problems for placement
1. what is the error in the following sequence of program. int i1; switch(i1) { printf("The value of I1 is :"); case 1: printf("%d",i1); break; case... - 17 months ago
tricky pacement c language questions
1: Why doesn't the code "a[i] = i++;" work? A: The variable i is both referenced and modified in the same expression. 2: Under my compiler, the code "int i = 7; ... - 17 months ago
best aptitude questions for placement
Aptitude Questions 1.If 2x-y=4 then 6x-3y=? (a)15 (b)12 (c)18 (d)10 Ans. (b) 2.If x=y=2z and xyz=256 then what is the value of x? (a)12 (b)8 (c)16 (d)6 Ans. (b) 3. (1/10)18 - (1/10)20 = ? ... - 17 months ago
C# ,NET assembles
Each of the applications developed in this book’s first ten chapters were along the lines of traditional “stand-alone” applications, given that all of your custom programming logic was contained within a single executable file (*.exe).... - 17 months ago