1. We have moved from vBulletin to XenForo and you are viewing the site in the middle of the move. Though the functional aspect of everything is working fine, we are still working on other changes including the new design on Xenforo.
    Dismiss Notice

Detecting errors using CRC-32 (for IEEE802.3) code

Discussion in 'C' started by blitzcoder, Aug 27, 2010.

  1. blitzcoder

    blitzcoder New Member

    Joined:
    Aug 24, 2010
    Messages:
    12
    Likes Received:
    2
    Trophy Points:
    0
    Occupation:
    Student
    Location:
    Surat, India
    Home Page:
    Networking is all about transmitting messages from one node to another. The simplest example can be to transmit "Hello World" from one computer to another. Socket programming in C/C++[/URL] has already been covered. Today we will see how to check if the transmitted data has any errors.

    There are many error detecting codes that are used while performing data transmission. Since data is transmitted in form of signals from one node to another through wired and wireless media, there is a high probability of the signal being distorted when it reaches the other end. A simple change of a couple of 0s to 1s can make all the difference in the world. Thus we need to apply some error detecting technique.

    CRC-32 is an error detecting technique applied by IEEE802.3 while transmitting packets. CRC is an abbreviation for "Cyclic Redundancy Check". In this, there is a particular 33 bit divisor which performs binary division (using XOR) on the block of binary data to be transmitted after adding 32 0s to the end of the data. (See example below)

    This is divided by a polynomial which is as follows,
    x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1 (IEEE802.3 standards have this polynomial predefined)

    This, when written as a 33-bit code turns out to be,
    100000100110000010001110110110111 (our divisor)
    All we did there was convert to binary as if x=2.

    Now XOR operation is performed repeatedly, thus resulting in binary division of data wit divisor, finally leaving us with a remainder. This remainder then replaces the 32 0s we added. Thus, IF the final remainder is 1000101110011001101001 , we will replace the 32 0s by 00000000001000101110011001101001

    Let us see how this is done --

    Taking the following data: 10001010

    Code:
    1000101000000000000000000000000000000000 (data after adding 32 0s)
    100000100110000010001110110110111	         (writing the divisor and XOR-ing in next step)
    -----------------------------------------------------
    000010000110000010001110110110111[I]0000[/I]       (taking down 4 0s from the data above)
        100000100110000010001110110110111
    -----------------------------------------------------------
        000001000110100001100011011000111[I]000[/I] (taking down the 3 remaining zeros)
    
    But now the number (starting with the 1st one is less than 33 bits and thus cannot be XOR-ed any further. Thus, this is the remainder.

    So when you write this in the form of 32 bits, it is -
    01000110100001100011011000111000

    Remember that we added 32 0s previously to data? Now replace those with this 32-bit code. So data with 32 appended bits would now look like,
    1000101001000110100001100011011000111000

    This is transmitted to the other side where the same operation that has been performed above (i.e., repeated XOR to get a remainder). If the data is unchanged, the remainder will consist of only 0s. However, if any bit is modified, the remainder will consist of 1s as well thus flagging an error. :)

    Lets see what happens when the code is transmitted as it is,
    Code:
    1000101001000110100001100011011000111000
    100000100110000010001110110110111
    -----------------------------------------------------
    000010000010011000001000111011011[I]0111[/I]		(XOR result)
        100000100110000010001110110110111
    -----------------------------------------------------------
        000000000000000000000000000000000[I]000[/I] (there it is, a zero remainder as a result of XOR)
    
    Now let me change bit number 3 in my generated code (data+appended CRC code). So the other side recieves,
    1010101001000110100001100011011000111000

    Now let us perform the same operation again
    Code:
    10[B]1[/B]0101001000110100001100011011000111000 //Transmission with error
    100000100110000010001110110110111
    -----------------------------------------------------
    001010000010011000001000111011011[I]01[/I]
      100000100110000010001110110110111
    --------------------------------------------------------
      001000101111100010101101011011010[I]11[/I]
        100000100110000010001110110110111
    -----------------------------------------------------------
        000010011000001000111011011011100[I]000[/I] (oops, there must have been some error as remainder did not come out to be all 0s :) Error detected! ) 
    
    Now that we are clear on what CRC-32 works, lets look at the code,

    Code:
    #include<iostream.h>
    #include<conio.h>
    #include<fstream.h>
    void crc32()
    {
    	char c;
    	int data[1000],temp[1000],i=0,l=0,crc[33]={1,0,0,0,0,0,1,0,0,1,1,0,0,0,0,0,1,0,0,0,1,1,1,0,1,1,0,1,1,0,1,1,1},div[33]; //storing the CRC-32 binary code
    	fstream a("crc_b.txt",ios::in); //file with binary data
    	while(!a.eof())
    	{
    		a.get(c);
    		data[i]=(int)c-48;
    		temp[i]=data[i]; //receiving data and converting to integer 1 or 0 and storing in "temp" as well
    		i++;
    	}
    	l=--i;
    	for(i=l;i<(l+32);i++)
    	{
    		data[i]=0;  //adding 32 0s to the data
    	}
    	int m=0;
    	//from here on, the loops XOR the 32 bits found after each "1" is encountered and store it back in data
    	for(i=0;i<l;i++)  
    	{
    		if(data[i]==1)
    		{
    			m=0;
    			for(int j=i;j<i+33;j++)
    			{
    				data[j]=data[j]^crc[m]; //XOR-ing with CRC-32 code
    				m++;
    			}
    		}
    	}
    	a.close();
    
    	fstream o("crc_c.txt",ios::out); // the final output file with data + appended 32 bits
    	for(i=0;i<l;i++)
    		o<<temp[i]; //printing original data to file
    	for(i=l;i<l+32;i++)
    	{
    		cout<<data[i]<<"\n"; //printing CRC generated to stdout.
    		o<<data[i]; //printing CRC generated to file
    	}
    	// Now we will check to see if the (Data+generated CRC bits) / (CRC-32 divisor) gives no remainder.
    	for(i=l;i<l+32;i++)
    	{
    		temp[i]=data[i];
    	}
    	temp[l-20]=1-temp[l-20];
    	// temp[l-10]=0; //activate this line to see the difference when an error is introduced
    	for(i=0;i<l;i++)
    	{
    		if(temp[i]==1)
    		{
    			m=0;
    			for(int j=i;j<i+33;j++)
    			{
    				temp[j]=temp[j]^crc[m]; //performing XOR-ing operation in virtual-received data
    				m++;
    			}
    		}
    	}
    	for(i=l;i<l+32;i++)
    	{
    		cout<<temp[i];
    	}
    	//The output(remainder) comes out to be 0 if no bit has been changed. Try changing a bit //by removing the above comment and there will be 1s as well, which will depict an error.
    }
    void main()
    {
    	clrscr();
    	int as;
    	fstream in("crc.txt",ios::in); //this file has data in ASCII format. Eg,  "Hello World"
    	fstream out("crc_b.txt",ios::out);
    	int ch[8],cs[100];
    	long sum=0;
    	for(int j=0;j<8;j++)
    		ch[j]=0;
    	char c;
    	while(!in.eof())
    	{
    		for(j=0;j<8;j++)
    			ch[j]=0;
    		in.get(c);
    		as=(int)c;
    		if(as!=-1)
    		{
    			sum+=as;
    			cout<<as<<" ";
    			int i=0;
    			while(as>0)
    			{
    				ch[i]=as%2;
    				as=as/2;
    				i++;
    			}
    
    			for(i=7;i>=0;i--)
    			{
    				out<<ch[i];
    				cout<<ch[i];
    			}
    			cout<<endl;
    		}
    	}
    	//what we have done till now is to convert the ASCII code of each character into binary and print it to a file (in blocks of 8 bits)
    	in.close();
    	out.close();
    	crc32();
    	getch();
    }
    
    The comments are self explanatory. This brings us to the end of how to generate a CRC error detecting code as it is done by IEEE802.3 standards!

    Happy Coding! :D
     
  2. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,276
    Likes Received:
    364
    Trophy Points:
    83

Share This Page