Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/articles/c-tutorials/)
-   -   Detecting errors using CRC-32 (for IEEE802.3) code (http://www.go4expert.com/articles/detecting-errors-using-crc-32-ieee8023-t23115/)

blitzcoder 27Aug2010 20:14

Detecting errors using CRC-32 (for IEEE802.3) code
 
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)
-----------------------------------------------------
0000100001100000100011101101101110000      (taking down 4 0s from the data above)
    100000100110000010001110110110111
-----------------------------------------------------------
    000001000110100001100011011000111000 (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
-----------------------------------------------------
0000100000100110000010001110110110111                (XOR result)
    100000100110000010001110110110111
-----------------------------------------------------------
    000000000000000000000000000000000000 (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:

1010101001000110100001100011011000111000 //Transmission with error
100000100110000010001110110110111
-----------------------------------------------------
00101000001001100000100011101101101
  100000100110000010001110110110111
--------------------------------------------------------
  00100010111110001010110101101101011
    100000100110000010001110110110111
-----------------------------------------------------------
    000010011000001000111011011011100000 (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

shabbir 4Sep2010 12:21

Re: Detecting errors using CRC-32 (for IEEE802.3) code
 
Nominate this article for Article of the month - Aug 2010 before September 15 2010.


All times are GMT +5.5. The time now is 06:11.