Checksum
-
Suppose we want to sent five 4-bit numbers
: 7, 11, 12, 0, 6 -
Add all numbers and place the sum as the last number
: 7, 11, 12, 0, 6, 36 -
The receiver checks for errors by adding all numbers and comparing with the last number
: 7 + 11 + 12 + 0 + 6 = 36 -> no error -
We can also do this by adding minus sign to the sum
: 7, 11, 12, 0, 6, -36 -
The receiver simply adds all numbers and see if it is zero
: 7 + 11 + 12 + 0 + (-36) = 0 -> no error
Wrapped sum
문제는 36은 4-bit가 아니다.
-
We calculate a wrapped sum
-
36 = 100100
-
keep the lower 4 bits, and add the number to the higher 2 bits
0100
+ `10
----
0110 -
The wrapped sum of 36 is 6
63의 wrapped sum
-
63 = 111111
1111
+ 11
----
10010 -
여전히 4-bit가 아니다!
한번 더 돌린다
0010
+ ``1
----
0011 -
The wrapped sum of 63 is 3
1's complement
- Now we need to make the number negative(-6) using 4 bits
- 1's complement : toggle all bits
6 : 0110
-6 : 1001
그런데 1001은 9 아니냐
Final
- The sender place '0' as the last number
: 7, 11, 12, 0, 6, 9 - The receiver receives the numbers and adds them
: 7 + 11 + 12 + 0 + 6 + 9 = 45 - Calculate a wrapped sum of 45(101101)
1101
+ 10
----
1111 - Finds 1's complement of 1111 = 0000 -> correct!
- If the final value is not 0, there is an error
