[Error Detection and Correction] CRC

Cyclic Redundancy Check(CRC)

• Complexity and power of CRC can be controlled by selecting "divisor(generator)"

• Use Modulo-2
  0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0
  0 - 0 = 0, 0 - 1 = 1, 1 - 0 = 1, 1 - 1 = 0
  Addition과 Subtraction이 같은 결과를 내놓는다!!
  또한 그 값은 XOR의 결과와 동일하다

---

Example

Sender

• Suppose we use the divisor '1011'
• We want to sent the dataword '1001'
• Add '000' after the dataword -> '1001000'
• Divide '1001000' by the divisor '1001'
  (Use modulo-2 arithmetic)

• Then, the remainder is '110'
• Add this to the dataword to make the codeword
  -> '1001110'
• Send this codeword

Receiver

• receives the codeword and divide the number by the divisor
• If the remainder is not 0, then error detected
• If the remainder is 0, then there is no error

---

Polynomial

• dataword : M(x)
• divisor : g(x)
• codeword : T(x)

• T(x) is divisible by g(x)

• Sender sends T(x)
• Receiver receives T'(x)
• Receiver calculates T'(x)/g(x)
• If the remainder is zero, the receiver presumes T(x) = T'(x) (no error)

---

Fail to detect error

• 만약 error가 발생했는데도 T'(x)가 여전히 g(x)로 나눠지게 된다면, error detection에 실패하게 된다.

• error가 발생했다면,
  T'(x) = T(x) + e(x)
  이 때, T'(x)가 g(x)로 나눠진다는 건 결국 error인 e(x)가 g(x)로 나눠진다는 것이다.

• 즉, CRC의 error detection performance는 g(x)에 따라 달라진다.
  십진수 형태로 예를 들면, divisor를 2로 하는 것보다 29같은 큰 소수로 하는 것이 훨씬 유리할 것이다.

• Suppose that the divisor has x0 term, and has at least one other term
  e.g. g(x) = x2 + 1
  Then, all 1-bit errors can be detected

  예를 들어,
  Take T(x) = 101101 and g(x) = x3 + 1,
  가능한 1-bit error의 e(x) = 1, x, x2, x3, x4, x5.
  이 e(x)들은 절대 g(x)로 나눠지지 않는다.

---

Performance of CRC

If degree of the polynomial is n,

• detects all burst errors of size n or smaller
• If size of the burst is n+1, the error can be detected with probability 1 - (1/2)n-1
• If size of the burst is larger than n + 1, the error can be detected with probability 1 - (1/2)n

• Example
  • Suppose the divisor is x6 + 1
    1. All burst error with size 6 or less are detected.

       차수가 5 이하인 e(x) 중에는 x6 + 1로 나눠지는 게 없다

    2. If the length of the burst is 7, then error detection probability is 31/32

       1000001
       끝에는 1로 고정이기 때문에(length of burst), 에러 발생 case = 25
       이 중 x^6 + 1로 나눠지는 건 자기 자신밖에 없다
       => 31/32

    3. If the length of the burst is 8 or higher, then error detection probability is 63/64

       10000001
       에러 발생 case = 26
       이 중 나눠지는 건 11000011 하나
       x^7 + x^6 + x + 1
       = {x^7 + x} + {x^6 + 1}
       => 63/64

       100000001
       에러 발생 case = 27
       이 중 나눠지는 거
       (1). 101000101
       x^8 + x^6 + x^2 + 1
       = {x^8 + x^2} + {x^6 + 1}
       (2). 111000111
       x^8 + x^7 + x^6 + x^2 + x + 1
       = {x^8 + x^2} + {x^7 + x} + {x^6 + 1}
       => 126/128

    • 맨 왼쪽 x^n은 무조건 x^(n-6) 하나 필요하고,
      맨 오른쪽 1은 무조건 x^6 필요하다고 생각하면 조금 쉽다.

어쨌든, CRC의 error detection probability가 아주 높은 것을 확인할 수 있다.
"Powerful error detection method"