Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How is a 1s complement checksum useful for error detection?

Tags:

A checksum can be generated simply by adding bits. How is the extra step of taking the 1s complement useful?

I understand the theory. I know how to calculate 1s complement and I know about how adding the complements makes the result all 1s.

I would like to see a simple example of how an error is detected.

like image 809
node ninja Avatar asked Apr 09 '11 21:04

node ninja


People also ask

How can checksum detect errors?

For error detection by checksums, data is divided into fixed sized frames or segments. Sender's End − The sender adds the segments using 1's complement arithmetic to get the sum. It then complements the sum to get the checksum and sends it along with the data frames.

Can checksum detect 1 bit error?

A 16-bit sum-of-words checksum will detect all single bit errors and all error bursts of length 16 bits or fewer. It will also detect 99.998% of longer error bursts. A 32-bit sum will detect even more errors.

Why does UDP use 1s complement instead of the sum?

Why is it that UDP takes the 1s complement of the sum; that is, why not just use the sum? With the 1s complement scheme, how does the receiver detect errors? No – any 1-bit error will be detected. It will cause a 1 to become a 0 or a 0 to become a 1 in the sum.

What number of bit errors will a UDP checksum be able to detect?

The UDP checksum cannot detect all errors, but it does detect many. It will detect any single bit flip, but if the packet is altered such that the sum of all the data as 16 bit values remains constant, the checksum will not detect the error.

What is the one's complement of a checksum?

The one's complement (bit inversion) of a checksum is useful in at least two ways. If for example there is a final checksum byte of 56, the complement (bit inversion) will be 199. Add them together and the result is 255.

What is checksum error detection scheme?

Checksum error detection scheme, the data is divided into k segments each of m bits. In checksum error detection scheme, the data is divided into k segments each of m bits. In the sender’s end the segments are added using 1’s complement arithmetic to get the sum. The sum is complemented to get the checksum.

What is the 1s complement of the sum 0100101011000010?

The 1s complement is obtained by converting all the 0s to 1s and converting all the 1s to 0s. Thus the 1s complement of the sum 0100101011000010 is 1011010100111101, which becomes the checksum. At the receiver, all four 16-bit words are added,including the checksum.

Why does the receiver perform 1s complement arithmetic sum of frames?

The receiver performs 1s complement arithmetic sum of all the frames including the checksum. The result is complemented and found to be 0. Hence, the receiver assumes that no error has occurred.


1 Answers

I believe the example you're looking for can be found here.

The reason we do 1's complement is that when the 1's complement is added to the sum of all the values, and the result is trimmed to the bit-length of the machine (16 bits in the example above), it is all 1's. CPUs have a feature to take 1's complement of numbers, and taking the 1's complement of all-1 is all-0.

The reason: CPUs hate to work with bits except in chunks of however many it normally use. So adding two 64-bit numbers may take 1 cycle, but checking all the bits of that number individually will take many more (in a naive loop, perhaps as high as 8x64 cycles). CPUs also have capability to trivially take 1's complements, and detect that the result of the last calculation was zero without inspecting individual bits and branch based on that. So basically, it's an optimization that lets us check checksums really fast. Since most packets are just fine, this lets us check the checksum on the fly and get the data to the destination much faster.

like image 185
Sajid Avatar answered Sep 29 '22 14:09

Sajid