CRC에서 detect 불가한 burst error

CRC의 divisor는 가장 좋은 퍼포먼스가 나오는 형태인, x^0 term과 x^n term을 가진 꼴이라고 가정하자. (e.g. x^n + 1)
이때 divisor는 n+1개의 bit로 이루어져 있다

Performance of CRC
발생한 burst error가 divisor로 나누어떨어지는 경우 detect 불가하다.
이것이 발생할 확률을 burst error의 크기에 따라 구해보자.
burst error의 크기는, 발생한 error의 width가 총 몇 개의 bit로 이루어져 있는지를 의미한다.
따라서 burst error 크기가 k라는 것은 그것을 이루는 k개의 bit 중 첫 번째와 k번째의 값은 1임을 내포한다.
(burst error에서 특정 bit가 1이라는 것은 해당 bit에 에러가 발생했다는 것이고, 0은 그렇지 않다는 것이다.)

 

burst error 크기가 n 이하면
detect 불가한 burst error는 없다.
모든 burst error는 divisor로 나누어떨어지지 않기 때문.

burst error size == n + 1인 경우
detect 불가한 burst error가 나타날 확률은 (1/2) ^ (n - 1). 왜?
burst error가 divisor와 동일한 경우 제외하고 모두 detect 가능하다.
burst error size가 n+1이라는 건 error의 양 끝이 1이라는 것이 전제된 것이기 때문에, 그 둘을 제외한 것들이 divisor와 동일하면 됨.
따라서 (1/2) ^ ((n+1) - 2) = (1/2) ^ (n - 1)

burst error size > n + 1인 경우 (여기가 포인트임)
등장할 확률이 (1/2)^n이라고 나와 있다. 왜?
divisor로 나누어떨어지는 burst error의 경우의 수를 구해보자.
- 일단 burst error size가 k로 두자 (k > n + 1). 그리고 그 양 끝에는 1이 있다.
- 그리고 divisor의 양 끝에도 1이 있다.
- 따라서, burst error의 조건을 만족하기 위해서는 (divisor << (k - (n + 1)))와 divisor가 일단 무조건 더해져야 함.
- 그리고 나머지 k - (n + 1) -1 가지의 위치에서 divisor가 더해질지는 각각 선택할 수 있다.
- 따라서 서로 다른 detectable 한 error를 만들 수 있는 경우의 수는 2 ^ (k - (n + 1) - 1) = 2 ^ (k - n - 2)

각 burst error가 발생할 확률은 (1/2) ^ (k - 2)
따라서 detectable 한 error가 발생할 전체 확률은 2 ^ (k - n - 2) * (1/2) ^ (k - 2) = (1/2) ^ n

---

 

burst error 크기가 커져도 detectable 할 확률이 일정하다는 것이 매우 인상적이다.

error 크기에 따라서 detect 할 수 있는지 여부가 달라지는 hamming code 등과 비교된다.

그렇지만 또 생각해보니 hamming code는 2bit error 까지는 무조건 detect 가능인데 CRC에서는 그게 확실이 보장되는 건 아니네. 둘 다 장단점이 있다.

시험 기간에 이 부분 보고 혼자 고민하고 깨달아서 신났던 부분이라 꼭 기록하고 싶었는데 뭔가 말로 표현이 잘 안 돼서 미루다가 이러다 영영 올리지 않을까 봐 또 그냥 올려버림.

이런 식으로 생각 많이 해봐야만 풀 수 있는 문제들이 시험에 더 많이 나오면 좋겠다.

 

 

 

 

https://blog.naver.com/mini_gb/223443398788

CRC에서 detect 불가한 burst error