[Data Communications] Chapter 6.2 - Error Detection and Correction

이한량·2024년 5월 26일

Data Communications

목록 보기

7/13

1. Error Detection - Cyclic Code

Cyclic Code : Linear Block Codes (선형 블록 코드)의 한 특별한 형태로, 순환 코드가 갖는 특성을 통해 오류를 감지 및 수정하는 기법이다.
- 순환 특성 : Codeword를 Cyclic Shift한 결과는 또 다른 코드가 된다. 예를 들어, 10110001이라는 코드를 Left Shift한 결과는 01100011로, 완전히 다른 코드이다.
- 두 선형 코드의 xor 연산 결과로 다른 코드를 만들어낼 수 있다.
CRC 예제 : 송신측
- Dataword : 1001
- Divisor : 1011
- 진행 과정
  
  1). Dataword 변형 : 1001000 (Divisor의 최고 차수만큼 여분 데이터 추가)
  
  2). 변형된 데이터와 Divisor의 xor 연산
  
  3). Dataword + Remainder = Codeword : 1001110
CRC 예제 : 수신측
- Codeword : 1001110
- Divisor : 1011 (송신측과 동일)
- 오류가 발생 안한 경우
  
  1). Codeword(1001110) 수신
  
  2). Divisor와 Codeword의 xor 연산
  
  3). 나머지(Syndrome)가 0이므로, 오류가 발생하지 않았다고 판단.
  
  4). Remainder를 제거 후 Dataword 추출
- 오류가 발생한 경우
  
  1). Codeword(1000110) 수신
  
  2). Divisor와 Codeword의 xor 연산
  
  3). 나머지(Syndrome)이 0이 아니므로 오류가 발생했다고 판단.
  
  4). 수신한 코드 폐기.
Generator Polynomial : CRC 코드를 생성하기 위해 Divisor의 역할을 하는 것.
Polynomial 예제
- Generator Polynomial, (1011) : $g(x) = x^3 + x + 1$
- Information, (1100) : $i(x) = x^3 + x^2$
- Encoding (데이터 변형, 1100000) : $x^3i(x) = x^6 + x^5$
- 진행 과정
- 위 과정은 아래와 동일한 과정이다.
- Codeword (1100010) = $x^6 + x^5 + x$
Generator Polynomial 선택시 주의사항
- Single bits 검출 : 생성 다항식 $g(x)$ 가 2개 이상의 항을 갖고, 상수항 계수가 1이어야 한다. 즉, $g(x) = g^{\prime}(x) + 1$
- Multi bits 검출 : 생성 다항식 $g(x)$ 가 $x^t + 1$ 을 인수로 갖지 않아야 한다.
위 두 가지 조건을 충족시키는 Polynomial 예시 : $g(x) = x^2 + x + 1$
CRC의 장점
- 싱글 비트, 이중 비트, 홀수 비트, Bursty 에러를 검출하는 성능이 매우 우수.
- 나누기 연산만 하면 되므로 구현이 매우 간단하다. 따라서 하드웨어 및 소프트웨어로 쉽게 구현 가능.

2. Error Detection - Checksum

Checksum : 체크섬은 메시지의 길이와 상관 없이 적용할 수 있는 오류 검출 기법이다. 주로 네트워크 계층과 전송 계층에서 사용한다.
- 특징
  - 메시지 길이에 상관없이 적용 가능
  - 데이터 링크 계층보다 상위 계층(주로 네트워크 계층과 전송 계층)에서 사용

2-1. Tranditional Checksum

Tranditional Checksum : 전통적인 체크섬은 매우 간단하지만, 괜찮은 오류 검출 방식이다. 아래 4비트 숫자로 이루어진 Data set의 통신 예제를 통해 알아보자.
- 송신측
  - Data Set : $(7(0111)_2, 11(1011)_2, 12(1100)_2, 0(0000)_2, 6(0110)_2)$
  - 데이터 셋 전체 합계 : $(100100)_2 = 36_{10}$
  - 오버플로우 처리 : $(0110)_2 = (6)_{10}$
  - $(0110)_2$ 의 1의 보수 = $(1001)_2 = (9)_{10}$
  - 보낼 패킷 : (7, 11, 12, 0, 6, 9)
- 수신측
  - 수신한 데이터 셋에 1의 보수를 취한 뒤 전체 합계 : $8 + 4 + 3 + 15 + 9 + 6 = 45 = (101101)_2$
  - 오버플로우 처리 : $(1111)_2 = (15)_{10}$
  - 따라서 오류가 발생하지 않았음을 알 수 있다.
- 체크섬 방식은 싱글 비트 에러는 감지할 수 있지만, 멀티 비트 에러는 감지하지 못할 수 있다. 예를 들어, 한 숫자는 증가, 한 숫자는 동일한 양으로 감소하는 경우 체크섬으로 감지할 수 없지만 오류가 발생한 경우이다.

2-2. Upgraded Checksum

Improved Checksum : 각 자리 숫자마다 체크섬을 첨가하는 방식. 기존 방식보다 오류 감지 능력이 향상되었다. 하지만 이를 위해 추가적인 bit가 많이 필요하다.
Enhanced Checksum : 전통적 체크섬 방식을 개선한 것으로, 오류 검출 능력이 더 높다. 데이터 블록을 두 개의 블록으로 나누고, 각 블록의 누적합을 계산하여 비교하는 방식이다.

3. Forward Error Correction

Forward Error Correction (FEC, 정방향 오류 정정) : Error Correction Code를 데이터에 포함시켜 수신자가 오류를 직접 감지 및 수정하도록 하는 방식이다. 이 방식은 주로 재전송이 어려운 경우에 유효하다. 예를 들어, 비디오 혹은 오디오 스트리밍 등과 같은 실시간 서비스같은 경우에 주로 사용된다.

3-1. Hamming Code

Hamming Code : 전송 데이터에 패리티 비트(Parity Bit)을 추가하여 1비트 오류를 검출 및 수정할 수 있도록 하는 오류 검출 방식이다. 1비트 이상 발생하는 오류에 대한 검출 성능은 떨어진다.
(7,4) Hamming Code
(15, 11) Hamming Code

3-2. Interleaving

Interleaving : 에러를 전체적으로 분산시켜 오류의 영향을 줄이는 기법이다. 이는 영상 데이터와 같이 사소한 오류에 덜 민감한 경우 효과적이다.
- 동작 방식
  
  1). 각 패킷을 세로로 읽으며 각 패킷 당 1개 비트씩 추출
  
  2). 총 5비트로 이루어진 1개의 새로운 패킷을 구성해 데이터를 전송
  
  3). 역캡슐화 과정에서 패킷 원본으로 복구
  
  4). 만약 1개 패킷에 오류가 발생 시, 전체 패킷의 1개 비트에 오류가 발생하는 것으로 오류가 분산되는 효과
- 장점
  - 한 패킷에 대한 에러를 더 작은 오류로 분산시켜 오류의 영향력을 줄인다.
  - 데이터 복구율을 높여 전송 품질을 향상시킨다.
- 단점
  - 추가적인 지연이 발생할 수 있다.
  - 메모리 및 계산 자원이 더 많이 필요하다.

3-3. Compound

Compound : 각 패킷의 저해상도 복사본을 생성하고 이 복사본을 다음 패킷과 결합하여 전송하는 방식으로, 치명적인 오류를 덜 치명적인 오류로 바꿔 데이터 복구 가능성을 높이는 효과를 기대할 수 있다.
- 동작 방식
  
  1). 중복 패킷 생성 : 원본 고해상도 패킷의 저해상도 복사본을 생성한다.
  
  2). 결합 전송 : 생성된 저해상도 복사본을 다음 고해상도 패킷과 결합하여 전송한다.
  
  3). 결론적으로 하나의 패킷이 손실되면, 앞에 붙어있는 저해상도 패킷을 불러와 오류에 대처한다.
- 장점
  - 특정 패킷이 손실되는 오류가 발생했을 때 저해상도 중복본을 통한 대처가 가능하다.
  - 데이터 복구 가능성을 높인다.
- 단점
  - 전송량이 증가하여 네트워크 대역폭을 더 많이 사용해야 한다.
  - 추가적인 복제 및 결합 과정으로 인해 처리 시간이 늘어날 수 있다.

4. Backward Error Correction

Backward Error Correction (역방향 오류 정정) : Automatic Repeat request (ARQ)라고도 불리운다. 이 방식은 수신자가 데이터 블록을 제대로 수신하였는지 여부를 송신자에게 전송한다. 수신된 데이터에 오류가 있는 경우, 송신자 측에서 해당 데이터를 다시 전송하도록 한다. 이 방식은 지연 발생 등으로 인해 실시간 서비스에 적합한 방식은 아니다.
- 해당하는 예시는 SaW, GBN 프로토콜 등이 여기에 해당한다.