데이터 전송 - 오류 검출 기법

프레임 전송 과정의 오류를 극복하는 2가지 방법

1) 전송 프레임에 오류 검출 코드를 넣어 호스트가 전송 과정의 오류를 검출

주로 재전송으로 이루어짐. ex) 패리티 비트, 다항 코드 방식

네트워크에서는 일반적으로 재전송 방식을 이용해 오류를 복구하는 역방향 오류 복구(BEC, Backward Error Correction), ARQ(Automatic Repeat reQuest)방식을 이용한다.

 

2) 전송 프레임에 오류 복구 코드를 넣어 수신 호스트가 오류 검출과 복구 기능을 모두 수행

오류 복구 코드를 사용해 수신 호스트가 오류 복구 기능을 수행하는 방식을 순방향 오류 복구(FEC, Forward Error Correction)라 함

ex) 해밍 코드(Hamming Code)에는 1 비트 오류를 검출하고 복구하는 기능이 있음

 

오류 검출

네트워크에서 일반적으로 이용하는 역방향 오류 복구 기능을 수행하려면 수신한 프레임에 오류가 있는지 판단할 수 있어야 한다.

이를 위해서 송신 호스트는 오류를 검출하기 위한 코드를 전송 데이터와 함께 송신해야 한다.

오류 검출 코드는 패리티 비트, 블록 검사, 다항 코드 등을 이용해 생성 가능하다.

 

패리티 비트(Parity bit)

1바이트 구조에서 패리티 비트는 7비트의 ASCII 코드를 제외한 나머지 1 비트이다. 패리티 비트는 전송 과정에서 1비트 오류를 검출하기 위한 것으로 패리티 비트를 포함해 1의 개수가 짝수나 홀수 개가 되도록 한다.

ex) 1101001 이라는 데이터를 짝수 패리티(even parity)방식을 사용해 전송하려면 11010010의 형태로 만들어 전송한다. 즉, 짝수 패리티 방식에서는 데이터 끝에 패리티 비트를 추가해 전체 1의 개수를 짝수로 만든다. 수신 호스트는 1의 개수를 판단하여 홀수일 경우 전송 오류로 판단하여 송신 호스트에게 재전송을 요구한다.

홀수 패리티(odd parity) 방식은 1의 개수를 홀수로 만드는 것이고 수신 호스트는 1이 홀수 개인지 판단한다. 

송신호스트와 수신호스트는 짝수 패리티나 홀수 패리티 중 동일한 한가지 방식을 사용해야 한다.

 

패리티 방식은 1 비트 오류에 간단히 적용할 수 있는 장점이 있지만, 짝수개의 비트에서 오류가 발생한 경우 오류가 검출되지 않는다는 문제가 있다. 

 

 

블록 검사(Block Sum Check)

다수의 비트에서 오류가 발생할 때 오류를 검출하는 방법

이 방식에서는 위의 그림과 같이 여러 개의 바이트를 하나의 블록으로 구성한 후 교차 검사를 한다. 즉, 블록 데이터의 수평과 수직 방향에 모두 패리티 비트를 둠으로써 짝수 개의 오류 검출이 가능해진다.

위의 그림에서 오른쪽에 표시한 패리티 비트는 수평 방향으로 짝수 패리티를, 아래쪽에 블록 검사 비트로 표시한 데이터는 수직 방향으로 짝수 패리티 비트를 적용한 것이다. 따라서 수평 방향으로 짝수 개의 비트가 깨지면 수직 방향의 블록 검사 비트로 오류를 검출하고, 수직 방향으로 짝수 개의 비트가 깨지면 수평 방향의 패리티 비트로 오류를 검출이 가능하다.

 

블록 검사의 문제점은 전송되는 데이터의 양과 비교해 오류 검출을 위한 오버헤드가 크다는 것이다.

또한, 아래의 그림과 같이 수평 수직 방향에서 모두 사각형 형태로 짝수 개의 데이터 오류가 발생하면 오류를 검출하지 못한다.

블록 검사의 한계

 

다항 코드(Polynomial Code),(CRC, Cyclic Redundancy Code) 

네트워크 프로토콜에서 가장 많이 사용하는 오류 검출 기법으로 네트워크에서 발생하는 오류는 특정 위치에서 집중적으로 발생하는 버스트 에러(Burst Error) 형태인 경우가 많은데, 다항 코드 방식은 이런 오류를 검출할 확률이 높다.

 

생성 다항식

다항 코드 방식은 계수가 0과 1인 다항식 형태를 기반으로 함

 

• 이진수 데이터를 다항식으로 표현하여 연산을 수행
• 예: 101101 → x⁵ + x³ + x² + 1 (각 1이 있는 위치를 지수로 표현)

주요 구성 요소

• M(x): m비트 길이의 원래 데이터
• G(x): n+1비트 길이의 생성 다항식
• 체크섬: n비트 길이의 오류 검출 코드

체크섬 계산 과정 (송신 측)

Step 1) 데이터 준비

- 원본 데이터 M(x) 뒤에 n비트의 0을 추가

- n은 생성 다항식의 차수

 

Step 2) 모듈로-2 나눗셈 수행

- 확장된 데이터를 G(x)로 나눔

- 나머지가 체크섬이 됨

 

Step 3) 전송 데이터 생성

- 원본 데이터 + 체크섬

 

모듈로-2 연산의 특징

• 덧셈/뺄셈 시 자리올림/자리빌림 없음
• XOR 연산과 동일한 결과
  • 1 ⊕ 1 = 0
  • 1 ⊕ 0 = 1
  • 0 ⊕ 1 = 1
  • 0 ⊕ 0 = 0

예)

생성 다항식 G(x) = x⁵ + x² + 1 (100101) => 6비트 생성 다항식 

원래 데이터 = 101101001

 

계산 과정

1) 원본 데이터에 0 추가 (5비트) 101101001 00000

2) 모듈로-2 나눗셈 수행 101101001 00000 ÷ 100101 => XOR 연산과 동일

3) 나머지(체크섬) = 00010

4) 최종 전송 데이터 101101001 00010

 

수신 측 검증 과정

Step 1) 수신 데이터 검증
- 전체 데이터를 G(x)로 나눔

Step 2) 결과 판단
- 나머지 = 0 → 오류 없음
- 나머지 ≠ 0 → 오류 발생

Step 3-A) 오류가 없는 경우
- 체크섬 제거
- 원본 데이터를 상위 계층으로 전달

Step 3-B) 오류가 있는 경우
- 부정 응답(NAK) 전송
- 재전송 요청

 

체크섬은 오류 검출만 가능 (오류 수정은 불가)

 

 

 

참고 자료 :

쉽게 배우는 데이터 통신과 컴퓨터 네트워크 3판 - 박기현 지음