A sender is transmitting the value string 31 52 71 Each valu

A sender is transmitting the value string (31, 52, 71). Each value is encoded in 8 bits (e.g., 31 encodes as 00011111).

• (2 points) What is the encoding of each value in the string?

• (2 points) What is the resulting checksum? Show your work.

Solution

Solution:

31 encodes as 00011111

52 encodes as 00011110

71encodes as 001000111

What is the resulting checksum?

A checksum “adds” together “chunks” of data.
The “add” operation may not be normal integer addition.
The chunk size is typically 8, 16, or 32 bits.

Integer Addition Checksum
• Same as LRC, except use integer “+” instead of XOR
– The carries from addition promote bit mixing between adjacent columns
• Can detect errors that make two bits go 0 -->1 or 1 --> 0 (except top-most bits)
• Cannot detect compensating errors (one bit goes 0-->1 and another 1 -->0)
– Carry out of the top bit of the sum is discarded
• No pairs of bit errors are detected in top bit position

Example:

   0 0 1 0 0 1 0 0

+1 0 1 1 1 0 0 0

+ 1 1 1 1 1 1 1 1

+ 0 0 0 0 0 0 0 0

-------------------------

1 1 1 0 1 1 1 0 0 carry propagates along bits of the sum carry out put is dropped

------------------------------

Integer Addition Checksum
• Same as LRC, except use integer “+” instead of XOR
– The carries from addition promote bit mixing between adjacent columns
• Can detect errors that make two bits go 0 -->1 or 1 -->0 (except top-most bits)
• Cannot detect compensating errors (one bit goes 0 -->1 and another 1 --> 0)
– Carry out of the top bit of the sum is discarded
• No pairs of bit errors are detected in top bit position

One’s Complement Addition Checksum
• Same as integer checksum, but add Carry-Out bits back
– Plugs error detection hole of two top bits flipping with the same polarity
– But, doesn’t solve problem of compensating errors
– Hamming Distance 2 (HD=2); some two-bit errors are undetected.

Fletcher Checksum
• Use two running one’s complement checksums
For fair comparison, each running sum is half width
E.g., 16-bit Fletcher Checksum is two 8-bit running sums
Initialize: A = 0; B = 0;
For each byte in data word: A = A + Bytei; B = B + A;
• One’s complement addition!
Result is A concatenated with B (16-bit result)
• Significant improvement comes from the running sum B
B = ByteN-1 + 2*ByteN-2 + 3*ByteN-3 + …
Makes checksum order-dependent (switched byte order detected)
Gives HD=3 until the B value rolls over
• For example, 256*ByteN-256 does not affect B

Adler Checksum
• Intended to be an improvement on Fletcher Checksum
One’s complement addition is the same as modulo 255 addition
Adler checksum uses a prime integer as a modulus
• 251 instead of 255 for Adler 16 (two 8-bit sums)
• 65521 instead of 65535 for Adler 32 (two 16-bit sums)

One of the simplest methods to do this is to use checksums. A checksum is an algorithm run on a document whose resulting number is referred to as the checksum value. The checksum value is a unique number assigned to a document based on the document’s content at the bit level. After this checksum value is known, a checksum can be re-calculated on the document again at any time. Comparing checksum values, if the numbers are identical then the document has not changed; if the same number was not generated then the document has changed somehow. If differences are detected, this method does not tell you what has changed or when something was changed, just that the two documents are no longer identical at the bit level.