How is a 1s complement checksum useful for error detection?_问答_开发者

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

开发者_StackOverflow中文版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.

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.

Example, You have three words in UDP packet need to send.

0110011001100000
0101010101010101
1000111100001100

UDP at the sender side performs the 1s complement of the sum of all the 16-bit words. The sum of first two of these 16-bit words is

0110011001100000 +
0101010101010101 =
1011101110110101

Adding the third word to the above sum gives, Note that this last addition had overflow, which was wrapped around

--> 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. If no errors are introduced into the packet, then clearly the sum at the receiver will be 1111111111111111. If one of the bits is a 0, then we know that errors have been introduced into the packet.

The one's complement (bit inversion) of a checksum is useful in at least two ways.

Simplifies the checksum verifying process

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. The reasoning: by complementing the final checksum, the final result will always be 255 when including the checksum digit in the sum calculation. Performing the complement a second time with 255 will produce 0, which for CPUs at the time, was a more efficient way to confirm that the checksum is valid without having to compare two numbers.

Allows one undetectable error to be detected

Calculating a message of n zeroes produces a checksum of zero. This means a legitimate message consisting of zeroes is indistinguishable from a memory loss or erasure situation which should be detected as an error. By complementing the final checksum of 0 in this case, the result is 255 instead, preventing a result of zero from still being valid.

By "adding bits" I assume you mean calculating parity bits. According to this Wikipedia entry on checksums, for a parity checksum "the probability of a two-bit error being undetected is 1/n" while with a modular sum (such as 1s complement) "the probability that a two-bit error will go undetected is a little less than 1/n."

This "Ask Dr. Math" column discusses how to calculate 1s complement (most commonly for TCP/IP).

Checksum is very important for networking as partickmdnet mentioned. Basically, for every datagram transmitted in the IP protocol, there is a checksum that was computed ahead of time and transmitted. If even one bit is corrupted and sent incorrectly in the data portion of the datagram, then the checksum computed at the receiving router will be different than that provided with the datagram. This tells the router that the datagram is corrupted (either the data or the checksum portion itself) and the router will discard the datagram.