Checksum: Error Detection Code

NOTE: The checksum code is added as redundant bits to the data to be transmitted.

Calculation of Checksum:

  • The original message is broken into ‘k’ number of blocks with ‘n’ bits each. Typically ‘n’ is 16bits.
  • All the ‘k’ number of data blocks are added.
  • If there is any carry, it is added to the sum.
  • 1’s compliment of the sum is then calculated. This is called the checksum.

NOTE: This checksum is also of ‘n’ bits.

NOTE: This addition is binary addition. Here are some rules of binary addition:

    \[ \begin{itemize}   \item {1 + 0  = 1}   \item {0 + 1 =1}   \item 1 + 1 = 10   \item 1 + 1 +1 = 11   \item 1 + 1 + 1 + 1 = 100   \item 1 + 1 + 1 + 1 + 1 = 101 \end{itemize} \]

Let’s take an example:

Suppose data to be transmitted is: 11001010 00101100 10111001

  • Step1: Divide the original data into k blocks of n bits each.

In the above example, say, we decide to divide the data into 3 blocks of 8 bits each:

Thus, k = 3 and n = 8.

1100101000101100 10111001
Divividing data into datablocks.
  • Step2: Sum all the ‘k’ data blocks:

In this case k = 3. We sum all three data blocks together

11001010
00101100
10111001
110101111
110101111 is the result of adding all 3 data blocks
  • Step 3: Add carry, if any.

The final checksum is of ‘n’ bits. In this case, n = 8. Whereas, our result is of 9 bits. Thus , there is an extra bit in the result of the addition. This extra bit is the carry we got duing the addition.

Carry in Checksum

As there is a carry, we add the carry to the sum.

10101111
1
10110000
We add the carry to the sum

This results in a sequence of ‘n = 8’ bits. The sequence we got is 10110000

Step 4: 1’s compliment of the result of addition and carry.

Calculating the 1’s compliment of the final sequence after addition gives us the checksum code.

NOTE: To get 1’s complement, we invert the bit. So:

    \[ \begin{itemize}   \item 1's compliment of 1 is 0.    \item 1's compliment of 0 is 1. \end{itemize} \]

In this case:

10110000
01001111
One’s compliment to calculate checksum code.

Final checksum is : 01001111

Transmission of Data with Checksum

The final checksum is appended to the left of the data. This data is then transmitted to the receiver such that, the checksum is the last block to be sent.

In this example, the checksum code, 01001111, is appended such that it is on the left of the original data blocks:

010011111100101000101100 10111001
Checksum appended to the original data block.

This data is then sent in the order such that the checksum is the last data block received.

Direction of Data transmission in case of checksum.

Receiver’s Side

On receiving the transmitted data, the receiver:

  • Collects all the datablocks, including the checksum
  • Adds all the datablocks together
  • If there is any carry, it is added to the result.
  • If the final result is all 1 bits, the data is accepted. If however, this is not the case, the data was corrupted during network transmission.

Let’s assume in our example, that data is transmitted over the network with no errors. Then the receiver would do the following calculation:

Data block 111001010
Data block 200101100
Data block 310111001
Checksum01001111
111111110
Adding the data blocks and the checksum together gives 111111110 as the result.

This leaves a carry. This carry is added back to the answer:

Result11111110
Carry1
Final Result11111111
Final result after addition of received data.

As the final result consists of all 1-bits, the receiver knows that no error occured during network transmission. It thus, accepts the data.

Advantages of Checksum:

  • Efficiency: Checksums provide a quick and efficient method of error detection, requiring minimal computational resources.
  • Simplicity: Checksum calculations are relatively straightforward, making them widely applicable and compatible with different systems and protocols.
  • Wide Adoption: Checksums are extensively used in various domains, including networking, file transfers, and storage systems, ensuring data integrity across diverse environments.

Limitations of Checksum:

  • Limited Error Detection: Checksums may fail to detect certain types of errors, especially when they result in the same checksum value as the correct data.
  • Inability to Correct Errors: Checksums can only detect errors but lack the capability to correct them. Additional mechanisms are required for error correction.

FAQs

  • Can checksum work on messages of any length?

Yes. Checksum can work on messages of any length. It would break the message into ‘k’ blocks of ‘n’ length each and then continue with it’s normal protocol.

  • What value of ‘n’ is usually used?

16 bits. ‘n’ is the length of bits in each segment of data. So we can say, data is divided into ‘k’ number of datablocks of 16 bits each.

  • What are some various checksum algorithms used for error detection?

Internet Checksum, CRC (Cyclic Redundancy Check), Adler-32 Checksum, Fletcher’s Checksum, MD5 and SHA-1 are some checksum algorithms

  • Is checksum more reliable than LRC?

Yes. As checksum uses addition over parity used in LRC, checksum is better than LRC.

  • Is checksum more reliable than VRC?

Yes. As checksum uses addition over parity used in VRC, checksum is better than VRC. Checksum error detection detects both odd and even number of bits error.

  • Is checksum more reliable than CRC?

No. The error detection capabilities of a CRC make it better than checksum.

  • Can a checksum correct errors?

No. Checksums can only detect errors. It can’t correct them.

  • Is checksum and crc the same thing?

No. CRC is a type of checksum algorithm.

  • Is md5 a checksum?

Yes, MD5 (Message Digest Algorithm 5) is commonly used as a checksum in addition to its cryptographic applications.

  • Is SHA1 a checksum?

Yes. While SHA-1 (Secure Hash Algorithm 1) is primarily designed as a cryptographic hash function, it can be used as a form of checksum for error detection purposes.

1 thought on “Checksum: Error Detection Code”

Leave a Comment

Your email address will not be published. Required fields are marked *