Forward Error Correction, 순방향 오류 정정법

시작하기에 앞서 몇 가지 알고 넘어갈 점.

Hamming Distance은 두 개의 문자열 사이에 서로 다른 비트의 개수이다. 1111과 1110은 마지막 자릿수 하나가 다르니 Hamming Distance = 11111과 1100은 마지막 두 자릿수가 다르니 Hamming Distance = 2

아래 본문 내용은 Hamming Distance가 1 일 경우에만 적용이 가능하다. D_n의 개수를 늘리고 추가적인 계산을 통해 Hamming Distance > 1 의 경우에도 푸는 방법이 존재한다.

 

빠른 이해를 위해 설명하기에 앞서 바로 간단한 Error Correction 예제를 풀어보자. 여러 가지 FEC 방법이 있는데 아래 방법은 가장 널리 쓰이는 Hamming Code Error Correction 방법이다.

 

1. 데이터 전송을 시작하기 전에 Data = D_n과 Parity = P_n을 아래와 같이 분리한다.

D7	D6	D5	P4	D3	P2	P1

2. 4비트의 정보를 Data 부분에 차례로 입력하면 된다.

예를 들어서 4비트의 정보 1011을 보내고 싶다. 그러면 D7=1, D6=0, D5=1, D3=1 이렇게 순서대로 입력하면된다.

D7	D6	D5	P4	D3	P2	P1
1	0	1		1

자 그럼 이제 Parity값을 어떻게 입력해야 하는지 궁금할 것이다. 

예전 고등학생 때처럼 수학의 정석에서 암기했듯이 우선은 암기하자.

 

3. 아래의 공식적용.

P1= D3D5D7 = 111 = 1이 홀수이므로 => P1= 1 

P2= D3D6D7 = 101 = 1이 짝수이므로 => P2= 0

P4= D5D6D7 = 101 = 1이 짝수이므로 => P4= 0

D7	D6	D5	P4	D3	P2	P1
1	0	1	0	1	0	1

왜 쓸때없이 Parity를 추가해서 전송하는지 이해 안 가는 분들이 있을 것이다. 이렇게 Parity를 추가로 전송을 하고 나면 Parity와 Data의 로직 관계로 오류를 수정할 수 있다.

 

만약에 위의 정보가 전달 과정에서 기상악화나 아니면 케이블 문제로 특정 비트가 전송이 잘못되었다고 가정해보자.

위의 정보 1010101이 전송되어야 했는데 잘못해서 예를 들어 5번째 자리 D5가 잘못 전송되어 0으로 전송되었다고 가정해보자.

 

4. 잘못된 비트 전달이 되는 경우.

D7	D6	D5	P4	D3	P2	P1
1	0	0	0	1	0	1

정보를 받는 입장에서 원래 어떤 정보를 보냈는지 확인할 수 있다. 하지만 이게 Error를 가지고 있는 정보인지 확인을 해야 한다. 이때 Parity가 사용된다.

 

Parity 확인 없이 수신된 정보를 확인하면 1001이다. 원래 보내려고 했던 정보인 1010과 차이가 있다.

이제 어느 정보가 정확하게 전송이 되었는지, 혹은 오류가 있다면 어느 부분에서 문제가 있는지 Parity를 가지고 확인을 해보자.

 

P4'= P4D5D6D7 = 0 0 0 1 = 1이 홀수개 => P4' = 1

P2'= P2D3D6D7 = 0 1 0 1 = 1이 짝수개 => P2' = 0

P1'= P1D3D5D7 = 1 1 0 1 = 1이 홀수개 => P1' = 1

 

Error 가 있는 자릿수는 = (P4' P2' P1')_2 = (1 0 1)_2 = 5 

 

즉 5번째 자리에 있는 D5에 오류가 있다는 걸 확인 할 수 있다.

 

5. 추가적인 예제.

D7	D6	D5	P4	D3	P2	P1
1	0	1	1	1	0	1

예를 들어 Parity가 잘못 전송되었다고 가정해보자.

위와 동일한 공식을 적용하면

 

P4'= P4D5D6D7 = 1 1 0 1 = 1이 홀수개 => P4' = 1

P2'= P2D3D6D7 = 0 1 0 1 = 1이 짝수개 => P2' = 0

P1'= P1D3D5D7 = 1 1 1 1 = 1이 짝수개 => P1' = 0

 

Error 가 있는 자릿수는 = (P4' P2' P1')_2 = (1 0 0)_2 = 4 

 

즉 4번째 자리에 있는 P4에 오류가 있다는 걸 확인 할 수 있다.