CN, Snippets

Implementation of Cyclic Redundancy Check Algorithm in C++

6 Comments

Cyclic Redundancy Check (CRC) is one of the most widely used error-detection techniques in data communications. The sender treats the data frame as a binary number, appends zeros equal to one less than the generator polynomial length, and then divides the extended frame by the generator using XOR (modulo-2) division. The remainder — called the CRC bits — is appended to the original frame before transmission.

At the receiver, the same division is performed on the received frame. If the remainder is zero, the frame arrived without errors; a non-zero remainder indicates corruption. This C++ program demonstrates both the sender-side CRC generation and the receiver-side error check for a user-supplied frame and generator.

C++ Program: CRC Algorithm

#include <iostream.h>
#include <conio.h>

void main()
{
    int frameIndex, genIndex, scanIndex, appendIndex;  // Loop counters

    // --- Sender: read the original data frame ---
    int frameSize;
    cout << "\n Enter Frame size: ";
    cin >> frameSize;

    int frame[20];
    cout << "\n Enter Frame (bit by bit): ";
    for (frameIndex = 0; frameIndex < frameSize; frameIndex++)
    {
        cin >> frame[frameIndex];
    }

    // --- Read the generator polynomial ---
    int generatorSize;
    cout << "\n Enter Generator size: ";
    cin >> generatorSize;

    int generator[20];
    cout << "\n Enter Generator (bit by bit): ";
    for (genIndex = 0; genIndex < generatorSize; genIndex++)
    {
        cin >> generator[genIndex];
    }

    // Display sender-side inputs
    cout << "\n Sender Side:";
    cout << "\n Frame: ";
    for (frameIndex = 0; frameIndex < frameSize; frameIndex++)
        cout << frame[frameIndex];

    cout << "\n Generator: ";
    for (genIndex = 0; genIndex < generatorSize; genIndex++)
        cout << generator[genIndex];

    // --- Append (generatorSize - 1) zeros to the frame ---
    int appendedZeros = generatorSize - 1;
    cout << "\n Number of 0s to be appended: " << appendedZeros;
    for (appendIndex = frameSize; appendIndex < frameSize + appendedZeros; appendIndex++)
    {
        frame[appendIndex] = 0;
    }

    // Keep a copy of the augmented frame for division
    int workingFrame[20];
    for (frameIndex = 0; frameIndex < 20; frameIndex++)
    {
        workingFrame[frameIndex] = frame[frameIndex];
    }

    cout << "\n Message after appending 0s: ";
    for (frameIndex = 0; frameIndex < frameSize + appendedZeros; frameIndex++)
        cout << workingFrame[frameIndex];

    // --- Perform modulo-2 (XOR) division ---
    for (frameIndex = 0; frameIndex < frameSize; frameIndex++)
    {
        genIndex = 0;
        scanIndex = frameIndex;

        // Only divide when the leading bit is 1 (i.e., >= generator[0])
        if (workingFrame[scanIndex] >= generator[genIndex])
        {
            for (genIndex = 0, scanIndex = frameIndex; genIndex < generatorSize; genIndex++, scanIndex++)
            {
                // XOR: same bits give 0, different bits give 1
                if ((workingFrame[scanIndex] == 1 && generator[genIndex] == 1) ||
                    (workingFrame[scanIndex] == 0 && generator[genIndex] == 0))
                {
                    workingFrame[scanIndex] = 0;
                }
                else
                {
                    workingFrame[scanIndex] = 1;
                }
            }
        }
    }

    // --- Extract CRC remainder bits ---
    int crcBits[15];
    for (frameIndex = 0, scanIndex = frameSize; frameIndex < appendedZeros; frameIndex++, scanIndex++)
    {
        crcBits[frameIndex] = workingFrame[scanIndex];
    }

    cout << "\n CRC bits: ";
    for (frameIndex = 0; frameIndex < appendedZeros; frameIndex++)
        cout << crcBits[frameIndex];

    // --- Build the transmitted frame: original data + CRC ---
    int transmittedFrame[15];
    for (frameIndex = 0; frameIndex < frameSize; frameIndex++)
        transmittedFrame[frameIndex] = frame[frameIndex];
    for (frameIndex = frameSize, genIndex = 0; frameIndex < frameSize + appendedZeros; frameIndex++, genIndex++)
        transmittedFrame[frameIndex] = crcBits[genIndex];

    cout << "\n Transmitted Frame: ";
    for (frameIndex = 0; frameIndex < frameSize + appendedZeros; frameIndex++)
        cout << transmittedFrame[frameIndex];

    // --- Receiver side: verify the received frame ---
    cout << "\n Receiver side: ";
    cout << "\n Received Frame: ";
    for (frameIndex = 0; frameIndex < frameSize + appendedZeros; frameIndex++)
        cout << transmittedFrame[frameIndex];

    // Copy transmitted frame into workingFrame for re-division
    for (frameIndex = 0; frameIndex < frameSize + appendedZeros; frameIndex++)
        workingFrame[frameIndex] = transmittedFrame[frameIndex];

    // Perform division again on the full received frame
    for (frameIndex = 0; frameIndex < frameSize + appendedZeros; frameIndex++)
    {
        genIndex = 0;
        scanIndex = frameIndex;
        if (workingFrame[scanIndex] >= generator[genIndex])
        {
            for (genIndex = 0, scanIndex = frameIndex; genIndex < generatorSize; genIndex++, scanIndex++)
            {
                if ((workingFrame[scanIndex] == 1 && generator[genIndex] == 1) ||
                    (workingFrame[scanIndex] == 0 && generator[genIndex] == 0))
                {
                    workingFrame[scanIndex] = 0;
                }
                else
                {
                    workingFrame[scanIndex] = 1;
                }
            }
        }
    }

    // Extract the remainder at the receiver
    int receiverRemainder[15];
    for (frameIndex = frameSize, genIndex = 0; frameIndex < frameSize + appendedZeros; frameIndex++, genIndex++)
    {
        receiverRemainder[genIndex] = workingFrame[frameIndex];
    }

    cout << "\n Remainder: ";
    for (frameIndex = 0; frameIndex < appendedZeros; frameIndex++)
        cout << receiverRemainder[frameIndex];

    // --- Check for errors ---
    int errorFlag = 0;
    for (frameIndex = 0; frameIndex < appendedZeros; frameIndex++)
    {
        if (receiverRemainder[frameIndex] != 0)
        {
            errorFlag = 1;
        }
    }

    if (errorFlag == 0)
    {
        cout << "\n Since Remainder Is 0, Message Transmitted Is Correct";
    }
    else
    {
        cout << "\n Since Remainder Is Not 0, Message Transmitted Contains Error";
    }

    getch();
}

How the Code Works

Step 1 — Input: The user provides the data frame bits one by one and the generator polynomial bits.

Step 2 — Append Zeros: (generatorSize - 1) zeros are appended to the frame. This augmented frame is used for division, ensuring the remainder has the correct number of bits.

Step 3 — Modulo-2 Division (Sender): The program scans the augmented frame bit by bit. Whenever it finds a leading 1, it XORs the next generatorSize bits with the generator. Identical bits produce 0; different bits produce 1. This continues until all original frame positions are processed.

Step 4 — CRC Extraction: The last appendedZeros bits of the working frame after division are the CRC bits. These are appended to the original data frame to form the transmitted frame.

Step 5 — Receiver Verification: The receiver performs the same XOR division on the full transmitted frame. If the remainder is all zeros, the frame is accepted as correct; otherwise, an error is reported.

Sample Output


 Enter Frame size: 6

 Enter Frame (bit by bit): 1
0
0
1
0
0

 Enter Generator size: 4

 Enter Generator (bit by bit): 1
1
0
1

 Sender Side:
 Frame: 100100
 Generator: 1101
 Number of 0s to be appended: 3
 Message after appending 0s: 100100000
 CRC bits: 001
 Transmitted Frame: 100100001
 Receiver side:
 Received Frame: 100100001
 Remainder: 000
 Since Remainder Is 0, Message Transmitted Is Correct

Output Explanation

The 6-bit data frame 100100 is augmented with 3 zeros (generator length 4 minus 1), giving 100100000. After XOR division by generator 1101, the remainder is 001. These CRC bits are appended to the original frame, producing the 9-bit transmitted frame 100100001.

At the receiver, dividing 100100001 by 1101 yields a remainder of 000, confirming error-free transmission. Had any bit been flipped during transmission, the remainder would be non-zero and the error would be flagged.

See Also

Conclusion

CRC is a cornerstone of reliable data communication, used in Ethernet frames, USB transfers, ZIP files, and disk storage. By appending a mathematically derived checksum to each transmission, the receiver can instantly detect accidental bit flips with very high probability. This program illustrates the core XOR-division mechanics that underpin all practical CRC implementations.

6 thoughts on “Implementation of Cyclic Redundancy Check Algorithm in C++”

  1. There is a mistake in the code. In the receiver side program, while dividing the received message by the generator the for loop i limit should be fs only. Otherwise the crc bits will also be divided by the generator even though they are smaller in size when compared to the generator. So it produces a wrong result.

    Reply

    1. U r getting it wrong way receiving side while dividing with generator it should be divided till last element so it can verified that remainder is 0/not

      Reply

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.