Chapter 10. ERROR DETECTION AND CORRECTION

---

◆ Error 의 분류

ㆍsingle-bit error 

한 비트 오류

 

ㆍburst error

2개 이상의 비트 오류

length of burst error : 틀리기 시작한 부분부터 끝부분까지 길이

- 전선 등의 문제로 특히 오류가 많이 나는 구간이 있음!!

 

---

◆ Redundancy

에러를 탐지하기 위해서 보내는 데이터에 추가적인 정보를 붙여서 보내는 것.

- 블록 코딩 따위의 방식으로 구현!!

 

---

◆ Error detection vs Error correction
: 에러 탐지 및 에러 수정

 

ㆍError detection 

에러가 났는지 안났는지 탐지하는 것

 

ㆍError correction

어디가 잘못됐고 어떻게 바꿔야 하는지 에러를 수정하는 것

(당연히 error detection 보다 어려움!!)

 

---

◆ FEC(Forward Error Correction) vs Retransmission

 

ㆍFEC

수신자 입장에서 추가비트를 활용해 에러 비트의 원래 비트를 추정하고 수정하는 것

 

ㆍRetransmission (재전송)

에러를 탐지하면 다시 보내달라고 하는 것

 

---

◆ Coding 이란?

정보에 추가 비트를 붙여 가공하는 작업

- 블록 코딩, Convolution 코딩 등의 방법이 있음

 

---

◆ XOR 연산 (exclusive or)

두 비트가 같으면 0, 다르면 1 반환

 

---

◆ Data word vs Code word

Data word : 데이터(k)

Code word : 데이터(k) + 추가 비트(r)

n = k + r 로 표현!!

 

C(m, n)

m = 코드워드 길이

n = 데이터워드 길이

 

---

◆ Hamming distance (해밍 거리)

ㆍHamming distance

한 코드워드와 서로 다른 비트의 수

(==XOR 연산 했을 때 1의 수)

 

ㆍd_min = 최소 해밍 거리 (전체 코드워드끼리 서로 최소 몇개부터 다른지)

 

d_min = s + 1

※ minimum hamming distance 가 d_min일 때, d_min - 1 개의 오류까지 탐지 가능함!

 

---

◆ Linear block Code (선형 블록 코드)

code word 중 아무거나 두 개 골라서 XOR 연산 했을 때, 그 결과가 다른 존재하는 code word가 되는 것.

오늘날 사용되는 대부분의 블록코드는 선형 블록 코드임! (비선형은 구조가 어렵고 복잡해서 잘 안씀)

 

종류

• Parity-check code (패리티 확인 코드)
• Hamming code (해밍 코드)
• CRC (Cyclic Redundancy Check)

 

---

■ Parity-check code

ㆍSimple parity-check code

전체 코드워드에서 1의 개수가 짝수가 나오도록 하는 한 비트 추가함!

 

n = k + 1, d_min = 2 (=> 한 개 오류 탐지 가능)

추가하는 한 비트를 parity bit 라고 부름!!

- 표와같이 결과 나옴

 

=> 홀수 개의 오류 탐지 가능!!

 

 

ㆍtwo-dimensional parity-check code

하나의 세팅으로 여러개를 계산해놓고 보내자 => 2차원

x 축과 y 축에 대해서 parity bit를 넣어줌.

b. 행, 열 중에서 한 비트만 잘못되면 correction도 가능함!!

c. 한 행 또는 한 열 안에서 두 비트가 잘못되면 detection만 가능함. correction은 힘듦.

e. 네 비트가 연속으로(행 두개 열 두개) 잘못되면 detection도 못함.

 

---

■ Hamming code (해밍 코드)

012 123 013

 

데이터워드를 바탕으로, 계산 공식에 의해 추가 비트 생성.

도착한 코드워드도 같은 방식으로 에러 탐지 및 수정 가능.

 

 

해밍 코드에서, 

n : codeword, m : redundancy, k : dataword 일 때
n = 2^m - 1
k = n - m

예를들어 redundancy를 4 개 넣을거면 n = 15, k =11  ->  C(15,11)

 

 

코드워드를 수신한 후 Syndrome을 계산한다.

구한 syndrome을 보면서 어디가 잘못됐는지 공식에 의해 수정할 수 있음!!

 

※ syndrome이 000이면 에러 X

 

---

※ 해밍코드 계산하기

기호는 위 그림과 연관시켜서 보면 됨

 

 

<보낼 때>

r0 r1 r2를 계산해서 붙여서 보냄 (Redundancy)

 

 

<받을 때>

받은 코드워드를 바탕으로 s0 s1 s2를 구함 (Syndrome)

 

아래 표와 매치시켜보면 에러 있는지, 어디에 있는지 확인 가능!

 

---

※ 해밍코드 예제

---

■ CRC (Cyclic Redundancy Check)
: LAN, WAN 에서 쓰임

Divisor 사용.

bit shift한 코드워드도 유효 코드워드임.

 

데이터워드를 바탕으로, 어떤 공식에 의해 추가 비트 생성.

도착한 코드워드도 같은 방식으로 에러 탐지 가능.

 

해밍 코드랑 연산만 다름!!

 

데이터 워드에다 Divisor의 최고차항 차수만큼 0을 붙이고, Divisor로 나눈 나머지를 코드에 추가해서 보냄.

받은 코드워드를 다시 Divisor로 나눴을 때 Syndrome(나머지)이 0이 나오면 오류 없음을 의미!! (아니면 오류 있음)

 

 

<비교>

해밍 코드는 코드워드 길이가 길어지면 계산 조합이 많아짐.

but CRC는 관계없이 Divisor만 어떤 조건에 성립하면 Syndrome 나옴!! 

 

Pairity check 방식은 한 행, 열 내에서 연속적으로 짝수개 오류가 발생하면 탐지하지 못하곤 했음.

but CRC는 관계없이 전부 잡을 수 있음!!

 

=>  Error detection 용도로 CRC가 굉~장히 강력함!!!

 

---

※ CRC Divisor 찾기

이런 식으로 매칭 가능함!!

 

 

Prime polynomial (소수 다항식) 을 찾아야 함.

 

 

차수가 높은 Divisor을 쓸수록, 한번에 연산할 수 있는 bit가 많아짐!!

 

---

※ CRC 국제 표준 Divisor

 

CRC는 지금도 쓰는 기술이기 때문에, 차수에 따라 어떤 Divisor을 쓸지 국제 표준 Divisor을 정해놓음.

 LAN 에서는 CRC-32

---

◆ Check Sum

데이터 링크 계층에서만 쓰지 않고, 다른 계층(특히 3계층) 에서 헤더들을 연산할 때 많이 씀!!