[Network Basic] 패리티 비트, CRC, 해밍코드

(2) 에러 검출 방법  

  ① 패리티 비트 체크(Parity Bit Check) 

• 전송되는 데이터의 한쪽 블록 끝에 패리티 비트를 추가함으로써 오류를 검출하는 방법 
• 짝수 패리티(Even parity), 홀수 패리티(Odd Parity)로 나뉨 
• 짝수 패리티는 전송되는 7비트(데이터)에 한 개의 짝수 비트(패리티)를 더해 송신측에서 전송하고 수신측에서는 수신된 데이터를 검사해 패리티 비트가 홀수면 오류가 발생했음을 알 수 이고, 홀수는 패리티는 홀수 비트를 만들어 전송하고 패리티비트가 짝수면 오류가 발생했음을 알 수 있다. 
• 발생하는 오류가 홀수 개면 오류 검출이 용이하지만 짝수 개의 오류가 발생하면 검출하기 어려운 단점이 있다. 
• 전송되는 데이터 7비트마다 패리티 비트 1비트가 추가됨으로 전송의 효율이 떨어진다는 단점도 있다. 

  

Parity Bit Check  

 

② 순환 중복 검사(CRC : Cyclic Redundancy Check) 

• 버스트 오류를 검출하는 능력이 탁월함(버스트 오류 : 데이터 전송 시 한 무리의 데이터에 집단적으로 오류가 발생한 것) 
• CRC 검사는 송신측과 수신측이 동일한 생성 다항식을 사용하여 오류를 검사한다. 먼저 송신측에서는 데이터를 송신하기 전에 데이터를 생성 다항식을 사용하여 계산한 다음, 그 값을 FCS(Frame Check Sequence)에 삽입하여 수신측으로 전송하고 수신측에 서는 수신된 전체 데이터를 동일한 생성 다항식으로 계산하여 나머지 값이 0이면 오류가 없는 것이고 나머지가 0이 아니면 오류가 발생 한 것으로 판단한다. 이러한 방법으로 1개의 오류 비트가 아닌 복수 개의 오류 비트도 검출할 수 있다. 

  

순환 중복 검사의 처리 절차 

1.  송신 측이 데이터를 전송하기 이전에 송수신측은 동일한 다항식(Generator Polynomial)을 결정한다. 
2.  송신 측은 m 비트의 전송 데이터에 n 비트의 체크 순차 비트를 더한다. 
3.  m+n 비트의 데이터를 생성 다항식으로 나눈 n 비트의 나머지 값을 구한다. 
4.  송신 측은 m 비트의 전송 데이터에 n 비트의 나머지 값을 붙여 m+n 비트의 데이터를 수신 측으로 전송한다. 
5.  수신 측에서 수신된 m+n 비트의 데이터를 생성 다항식으로 나눈다. 이 때 나머지가 0이면 오류가 없는 것이고, 0이 아니면 오류 발생 

  

(3) 오류 정정 방법 

• 수신측에서 에러를 검출하여 곧 바로 정정하는 FEC(Forward Error Correction)과 다시 송신측으로 재전송 요청을 하여 정정하는  BEC(Backward Error Correction) 방법 등이 있다. 

  

 ① 전진 에러 수정(FEC : Forward Error Correction) 

• 수신측에서 에러를 검출해서 정정하는 방법 
  • ex) 해밍코드(Hamming Code) 

  

 가. 해밍코드(Hamming Code) 

• Parity bit를 사용해 에러를 검출하고 정정하는 방법 
• 먼저 송신측에서 데이터의 해밍비트를 계산하여 이 값을 데이터에 추가하여 전송하고 다시 수신측에서는 이 데이터를 해밍코드 방법으로 계산하여 오류 발생 여부를 판단한다. 만약 에러가 발생했다면 그 오류가 발생된 비트를 반대되는 비트로 변환하여 오류를 정정한다. 
  • ex) 원래 데이터가 10110010 때 해밍 비트를 부가하는 방법이다. 해밍비트는 2^m(m=0, 1, 2 3) 번쨰 삽입된다. 

    

  

해밍 비트 값 산출 방법은 다음과 같다. 

입력 정보열 중 1의 비트가 있는 곳의 가중치를 2진수로 표현한다. 즉, 위의 예에서 1이 위치한 자리수가 각각 12, 10, 9, 5 번째 자리이므로 12, 10, 9, 5를 각각 2진수로 표현한다. 

    12 → 1100, 10 → 1010, 9 → 1001, 5 → 0101 

계산된 2진수를 전부 XOR 연산을 수행한다. 

계산된 1010 을 각 해밍 비트 자리에 위치 시킨다. 

    

  

완성된 해밍 코드는 101110010010 이 된다. 이제 해밍코드가 어떻게 에러를 교정하는 지 살펴보도록 하자. 만약 9번째의 비트가 에러로 전송되었다고 가정하면 즉, 9번째 비트가 1인데 0으로 잘못 전송됐다고 가정하자. 

  

  

앞에서와 같은 방법으로 1이 위치한 자리수(각각 12, 10, 5, 번째 자리)를 각각 2진수로 변환하여 XOR 연산을 하면 다음과 같이 1001 이라는 값을 얻을 수 있다. 

  

  

여기에서 얻은 1001 이라는 값이 바로 오류가 난 비트의 자리수를 의미한다. 즉, 1001은 십진수로 변환하면 9이므로 9번재 자리가 잘못 전송됐다는 의미이다. 따라서 9번째 비트가 0에서 다시 제대로 된 데이터 비트인 1로 변환된다.