[Error detection and Correction] Checksum

임승섭·2023년 4월 18일
0

Computer Network

목록 보기
7/27

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

0개의 댓글