Chapter10 Error Detection and Correction

Introduction

오류 감지 및 수정에 직간접적으로 관련된 몇가지 문제에 대해서 먼저 다루겠다.

 

오류유형

오류

• 간섭으로 인해 발생하는 예측할 수 없는 신호 변경

에러 유형

• 단일 비트 오류(Single-bit-error): 주어진 데이터 단위의 1비트만 변경됨
• 버스트 오류(Burst error): 데이터 단위에서 2비트 이상 변경됨

 

중복성

• 오류 감지 또는 수정의 중심 개념은 중복이다. 
• 오류를 감지하거나 수정하려면 일부 추가 비트를 데이터와 함께 전송해야 한다.
• 수진자가 손상된 비트를 감지하거나 수정할 수 있다.
• 에러 감지 기술

 

감지 VS 수정 (Detection versus Correction)

• 검출보다 오류 수정이 더 어렵다.
• 오류 감지에서는 오류가 발생했는지 여부만 확인한다. 감지응답은 손상된 비트의 수에 관계없이 간단하게 "예" 또는 "아니오"이다.
• 오류 수정에서는 손상된 비트의 정확한 수와 더 중요하게는 메시지에서 해당 비트의 위치를 찾아야 한다.

 

 

코딩(Coding)

• 다양한 코딩 방식을 통해 이중화를 구현한다. 중복 비트와 데이터 비트의 비율 및 견고성(redundant)은 모든 코딩 체계에서 중요한 요소이다.
• 두가지 종류
  • 블록코딩
  • Convolution Coding
   

 

 

블록 코딩(Block Coding)

블록 코딩에서 우리는 메시지를 데이터워드(datawords)라고 하는 각 비트의 블록으로 나눈다. 각 블록에 여분의 비트를 추가하여 길이를 n = k + r로 만든다. 결과 비트 블록을 코드워드(codewords)라고 한다. 추가 비트를 선택하거나 계산하는 방법은 나중 단원에서 나온다.

 

오류 감지

• 메시지는 데이터 워드(datawords)라고 하는 k-bit 블록으로 분할된다.
• 각 데이터 워드는 n-bit 코드워드(codeword)에 매핑된다. (n>k)
• 2^n -2^k 코드워드가 사용되지 않는다. -> 오류 감지 및 수정을 위한 이중화(Redunddancy)

 

예제

k=2, n=3이라고 하자. 아래 테이블은 데이터 워드 및 코드 워드 목록을 보여준다.

• 수신자가 수신하는 경우
  • 011: valid ->dataword 01
  • 111: invalid -> 폐기(오류감지)
  • 000: valid -> dataword 00

해밍거리

• 해밍 거리(Hamming distance): 두 워드(동일한 크기)의 비트간의 차이수
• d(x,y): 두 워드x,y간의 해밍거리 
  d(00000,01101) = 3
• 해밍거리는 아래의 방법으로 쉽게 구할 수 있다.
  1. 두 단어에 XOR연산(⊕) 적용
  2. XOR연산 결과에서 1의 개수 세기
• 예제
  • d(000,011) = 3
  • d(10101,11110) = 3
• 최소 해밍거리 dmin: 가능한 모든 코드워드쌍 사이의 최소 해밍거리
• 오류를 검출하려면 손상된 비트의 수가 dmin보다 작아야 한다.
• 모든 경우에 최대 s-비트 오류 감지를 보장하려면 블록 코드의 최소 해밍 거리(dmin)은 s+1이어야 한다.
  • dmin = s + 1
• 오류 감지에서 최소해밍거리를 설명하는 기하학적 개념

• 예제) 아래 코드체계에 대한 최소 해밍거리는 2이다. 이코드는 단 하나의 오류 검출을 보장한다. 예를 들어 101코드워드가 전송되고 하나의 오류가 발생하면 수신된 코드워드는 유효한 코드워드와 일치하지 않는다. 그러나 두개의 오류가 발생하면 수신된 코드워드가 유효한 코드워드와 일치할 수 있으므로 오류가 감지되지 않는다.

• 예제) 코드 체계는  최소 해밍거리가 4이다. 이 것은 최대 3개의 오류를 보장한다. d=s+1, s=3

parity check code

 

 

코드워드에서 1의 개수를 짝수(짝수패리티) 또는 홀수(홀수패리티)로 만들기 위해 패리티 비트라고 하는 추가 비트가 추가된다.

• 짝수 패리티(even parity)

• simple parity-check code 용 인코더 및 디코더

• 예시) 보낸 사람이 데이터워드 1011을 보낸다고 가정하자. 이 데이터워드에서 생성된 코드워드는 10111(짝수 패리티)이다.
  • 수신자가 수신할 때
  • 10111: 오류가 발생하지 않는다.
  • 10011: 단일 비트 오류가 감지. 폐기된다.
  • 10110: 손상된 데이터워드가 없어도 폐기된다. (홀수이기때문에)
  • 00110: 짝수 비트 오류가 발생되었지만 감지 되지 않는다.
  • 01011: 홀수 비트 오류가 발생되고 감지 된다.

---

 

순환 코드(Cyclic Codes)

순환 코드는 하나의 추가 속성이 있는 특수한 선형 블록 코드이다. 순환 코드에서 코드워드가 순환적으로 이동(회전)하면 결과는 다른 코드워드이다. 예를 들어 1011000이 코드워드이고 주기적으로 왼쪽으로 이동하면 0110001도 코드워드이다.

 

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

• n-bit CRC의 경우, divisor는 n+1 비트여야 한다.
• divisor는 발신자와 수신자가 공유해야 한다.

• CRC 인코더 및 디코더

• CRC 인코더에서의 나누기

• DRC 디코더에서의 나누기 두가지 케이스 

 

 

Polynomails(다항식)

• 0과 1의 패턴은 계수(coefficient)가 0과 1인 다항식으로 나타낼 수 있다.
  
  • 각 용어의 거듭 제곱은 비트의 위치를 나타낸다. 계수는 비트의 값을 보여준다.
   

 

다항식을 사용하는 인코더

• dataword: 1001
• divisor: 1011

 

 

순환코드 분석(Cyclic Code Analysis)

좋은 다항식 생성기는 

• 적어도 두개의 용어(terms)가 있어야 한다.
• x^0(상수항)의 계수가 1이어야 한다.
• 2<t<n-1에서 x^t+1로 나누지 않는다.
• 요소(factor) x+1을 가진다.

 

표준다항식

 

순환 코드의 장점

• 단일 비트 오류, 이중 오류, 홀수 오류 및 버스트 오류 감지에 매우 우수한 성능
• 하드웨어 및 소프트웨어로 쉽게 구현 가능
• 하드웨어로 구현될 때 특히 빠름

 

기타 순환코드

여기서 다룬 순환 코드는 매우 간단하다. 체크 비트와 신드롭은 간단한 대수로 계산할 수 있다..

Reed Solomon 코드와 같은 더 강력한 다항식도 있다.

 

---

체크섬(Checksum)

체크섬은 모든 길이의 메시지에 적용할 수 있는 오류 감지 기술이다.

인터넷에서 체크섬 기술은 데이터 링크 계층보다는 네트워크 및 전송 계층에서 주로 사용된다.

그러나 오류 감지 기술에 대한 논의를 완료하기 위해 이 장에서 체크섬에 대해 논의 한다.

 

• 체크섬: 원본 메시지의 일부인 m-bit 단위로 생성된 추가 m-bit 단위

예시1) 메시지가 목적지로 보내려는 5개의 4비트 숫자 목록이라고 가정하자. 이러한 숫자는 보내는 것 외에도 숫자의 합계를 보낸다. 예를 들어 숫자 집합이 (7,11,12,0,6)인 경우(7,11,12,0,6,36)을 보낸다. 여기서 36은 원래 숫자의 합이다. 수신자는 5개의 숫자를 더하고 결과를 합계와 비교한다. 둘이 같으면 수신자는 오류가 없다고 가정하고 5개의 숫자를 수락하고 합계를 버린다. 그렇지 않으면 어딘가에 오류가 있고 메시지가 수락되지 않는다.

 

예시2) 이전 예에서 10진수 36은 2진수로 (100100)2이다. 이를 4비트 숫자로 변경하려면 아래와 같이 오른쪽 4비트에 추가 맨 왼쪽 비트를 더한다.

합계로 36을 보내는 대신 합계로 6을 보낼 수 있다. 

(7,11,12,0,6,6). 수신자는 1의 보수 산술에서 처음 5개의 숫자를 더할 수 있다. 결과가 6이면 숫자가 허용된다. 그렇지 않으면 거부된다.

발신자는 결과를 보관하여 체크섬 9(15-6)을 얻는다. (6=0110, 9=1001; 이 둘은 보수관계)

발신자는 5개의 데이터 번호와 체크섬 (7,11,12,0,6,9)을 보낸다. 전송에 손상이 없으면 수신자는 (7,11,12,0,6,9)를 수신하고 1의 보수에 더하여 15을 얻는다.

(1의 보수: 1->0, 0->1)

 

위 그림은 더하는 과정을 보여준 것이다. 수신자에서 전체 합이 15(1111)가 된다. 이를 1의보수를 구하면 0이 된다.

 

인터넷 체크섬 계산 절차

Sender

1. 메시지가 16비트 단어로 쪼개진다.
2. 체크섬워드의 값이 0으로 초기세팅된다.
3. 체크섬을 포함하여 모든 값을 1의보수를 이용하여 더한다.
4. 합의 보수가 체크섬이 된다.
5. 체크섬이 데이터와 전송된다.

Receiver

1. 메시지와 체크섬을 수신한다.
2. 메시지가 16비트 단어로 쪼개진다.
3. 모든 단어를 1의보수를 이용하여 더한다.
4. 합은 의 보수가 체크섬이 된다.
5. 체크섬의 값이 0이면 수용되고. 아니라면 폐기된다.

 

---

Forward Error Correction( 전방 오류 수정)

이전 섹션에서 오류 감지 및 재전송에 대해 다루었다. 그러나 손상되거나 손실된 패킷의 재전송은 실시간 멀티미디어 전송에 유용하지 않다. 오류를 수정하거나 즉시 패킷을 재생해야 한다. 이경우 FEC(Forward Error Correction) 기술 이라고 총칭하는 여러 방식이 설계되고 사용되었다.

 

해밍거리 사용

• 최대 s-bit 오류 감지에 필요한 최소 해밍거리 dmin = s+1
• 최대 s-bit 오류 수정에 필요한 최소 해밍거리 dmin = 2s+1 

XOR 사용

• 패킷을 N개의 청크로 나눈 후 다음과 같은 XOR 연산을 적용한다.

• 청크가 손실되거나 손상된 경우

 

Chunk Interleaving

• 멀티미디어 응용 프로그램에서는 각 패킷에서 하나의 청크가 누락되도록 허용할 수 있다. 그러나 동일한 패킷에 속하는 모든 청크가 누락되도록 할 수는 없다.
• -> 여러 연속 패킷에 속하는 청크는 인터리브된다.

 

Combining(결합)

• 해밍거리와 인터리빙을 결합할 수 있다. 먼저 t-bit 오류를 수정할 수 있는 n-bit 패킷을 만든다.
• 그런 다음 m행을 인터리브하고 열별로 비트를 열별로(column by column) 비트를 보낸다.
• 이러한 방식으로 최대 m X t 비트의 오류까지 버스트오류를 자동으로 수정할 수 있다.

 

Compounding(합성)

• 또 다른 해결법은 저해상도 중복으로 각 패킷의 복제본을 생성하고 중복 버전을 다음 패킷과 결합하는 것이다.