K 개발자
다항 코드 본문
오류 검출
네트워크에서는 일반적으로 재전송Retransmission 방식을 이용해 오류를 복구한다.
이를 역방향 오류 복구BEC, Backward Error Correction 또는 ARQAutomatic Repeat reQuest 방식이라 한다.
역방향 오류 복구 기능을 수행하려면 수신한 프레임에 오류가 있는지 판단할 수 있어야 한다.
이를 위해서는 송신 호스트가 오류를 검출하기 위한 코드를 전송 데이터와 함께 송신해야 한다.
오류 검출 코드는 패리티 비트, 블록 검사, 다항 코드 등을 이용해 생성할 수 있다.
패리티 비트
1바이트(8비트) 구조에서 패리티Parity 비트는 7비트의 ASCII 코드를 제외한 나머지 1비트이다.
패리티 비트는 전송 과정에서 1비트 오류를 검출하기 위한 것으로, 패리티 비트를 포함해 1의 개수가 짝수나 홀수 개가 되도록 한다.
블록 검사
패리티 방식을 이용한 오류 검출 기법은 1비트 오류에 간단히 적용할 수 있다.
그러나 짝수 개의 비트에서 오류가 발생하면 오류가 검출되지 않는다는 문제점이 있다.
다수의 비트에서 오류가 발생할 때 오류를 검출하는 방법으로는 패리티 방식을 개선한 블록 검사Block Sum Check가 있다.
이 방식은 여러 개의 바이트를 하나의 블록으로 구성한 후 교차 검사를 한다.
즉, 블록 데이터의 수평과 수직 방향에 모두 패리티 비트를 둠으로써 오류 검출 확률을 높인다.
이 방식의 문제점은 전송되는 데이터의 양과 비교해 오류 검출을 위한 오버헤드가 크다는 점이다.
또 수평과 수직 방향에서 모두 사각형 형태로 짝수 개의 데이터 오류가 발생하면 이를 검출하지 못한다.
다항 코드
CRCCyclic Redundancy Code라고도 알려진 다항 코드Polynomial Code 방식은 현재의 통신 프로토콜에서 가장 많이 사용하는 오류 검출 기법이다.
특히 일반 네트워크에서 발생하는 오류는 특정 위치에서 집중적으로 발생하는 버스트 에러Burst Error 형태인 경우가 많은데, 다항 코드 방식은 이런 오류를 검출하는 확률이 높은 것으로 알려져 있다.
생성 다항식
다항 코드 방식은 계수가 0과 1인 다항식 형태를 기반으로 한다.
예를 들어, 100101의 다항 코드를 다항식으로 표시하면 $ 1 \times x^5 + 0 \times x^4 + 0 \times x^3 + 1 \times x^2 + 0 \times x^1 + 1 \times x^0 $이 되므로, 줄여서 생성 다항식 $ x^5 + x^2 + 1 $로 표현할 수 있다.
다항 코드 방식을 이용한 오류 검사의 동작 원리는 다음과 같다.
송신 호스트가 전송할 데이터가 m비트의 M(x)라면 데이터 전송 과정에서 n+1비트의 생성 다항식 G(x)를 사용해 오류 검출 코드를 생성함으로써 오류 제어 기능을 수행한다.
먼저 송신 호스트는 전송 데이터 M(x)를 생성 다항식 G(x)로 나누어 체크섬Checksum 정보를 얻는다.
나누기 연산 과정에서는 전송 데이터 뒤에 나머지를 보관할 n비트의 공간을 확보하고, 이 자리를 모두 0으로 채운 후에 나누기 연산을 수행한다.
연산에서 얻은 나머지 값을 체크섬이라 정의하며, 체크섬을 전송 데이터의 뒤에 추가해 수신 호스트에 전달해야 한다.
체크섬 계산인 나누기 과정에서 발생하는 다항 연산은 모듈로-2 방식으로 이루어진다.
따라서 덧셈의 자리 올림이나 뺄셈의 자리 빌림 과정이 이루어지지 않으므로 덧셈과 뺄셈은 배타적 논리합Exclusive OR 연산과 동일한 결과를 얻는다.
수신 호스트는 전송 오류가 발생했는지를 판단하기 위해 수신한 m+n비트의 데이터를 생성 다항식 G(x)로 나누는 연산을 수행한다.
연결 결과로 얻은 나머지가 0이면 전송 오류가 없다고 판단하고, 0이 아니면 오류가 발생했다고 판단한다.
체크섬의 예
예를 들어, 생성 다항식 $ G(x) = x^5 + x^2 + 1 $이 주어지고, 전송 데이터가 101101001인 경우의 체크섬 계산 과정은 다음과 같다.
계산을 통해 얻은 나머지는 00010이므로, 송신 데이터는 10110100100010이 된다.
수신 호스트는 수신 데이터 10110100100010을 생성 다항식 100101로 나누기 연산을 수행한다.
이때 나머지가 0이면 전송 오류가 없고, 0이 아니면 오류가 발생한 것으로 판단할 수 있다.
