Introduction

• 데이터는 전송 중에 변경될 수 있다.
• 몇몇 기능들은 에러가 검출되거나 정정되도록 요구한다

에러 검출 및 정정에 직/간접적으로 관련된 사항들에 대해 먼저 살펴보자!

Types of Errors

• Single bit error
  -한 비트만 변경되었다
  -근접 비트는 영향을 미치지 않는다
  
• Burst error
  -데이터 부분의 2개 또는 그 이상의 비트가 변경
  

Detection vs Correction

• detection은 어떤 에러가 일어났을때 검출하는 것이 가능하다
• correction은에서는, 우리는 일어난 비트의 정확한 수와 위치를 알아야한다

Forward Error Correction vs Retransmission

• Forward error correction: 수신자가 메시지의 중복비트를 이용하여 메시지를 추측해가는 과정
• Retransmission: 오류발생을 검출하여 송신자에게 다시 보내줄 것을 요청하는 과정

Basic principle of Error Detection

• transmitter
  -bit stream M이 주어졌을때, additional bits는 M의 함수로써 계산된다 그리고 M의 끝에 추가된다
• receiver
  -각각의 들어오는 프레임에 대해 같은 계산을 수행하고 두 결과를 비교한다. 감지된 에러는 불일치 했을때 일어난다.
  

Parity Checks

Single Bit Parity Check

• bit수가 even or odd이도록 맞춰준다
  
• single-bit parity는 erro가 홀수 개일때만 탐지한다
  

Two Dimensional Parity Check

• Horizontal and vertical parity확인
• 짝수 개수의 오류가 단일 행일 경우에 열(column) parity검사를 통해 감지할 수 있다
  
• but 같은 행, 같은 열끼리 오류가 있는 경우 감지할 수 없다.
  

Cyclic Redundancy Check

• 강력한 도구이지만, 쉽게 하드웨어 상으로 구현가능하다
• 이론: k bit 메시지가 주어졌을때 , n-bit sequence를 생산한다. 그래서 resulting frame(T)가 정확하게 s나눠진다 (n+1)-bit number (G)로
• modulo-2 연산을 쓴다
  

=> 나머지 없이 떨어져 버리면 erro detection이 안된다

검출 가능한 에러

• all single-bit errors
• all double-bit erros, 최소 3차항
• any odd number of erros, factor(X+1)을 가져야함
• any burst error 길이가 n bit거나 보다 작거나, n= degree of the polynomial G(X)
  

Checksum

• 헤더에있는 에러 찾기위해 인터넷 프로토콜에서 널라사용된다

• IP protocol에서, checksum는 헤더정보가 계산되고, special field에 포함된다

• Checksum은 매 router마다 재계산된다, 그래서 소프트웨어상 구현이 쉬운 알고리즘을 선택한다
  
  

• 0 이면 ERROR 없는 거임!

• 송신자 쪽

  1. 메시지를 16비트 워드로 나눈다.
  2. 검사합 워드의 값은 0으로 둔다.
  3. 검사합을 포함한 모든 워드는 1의 보수연산을 하여 더한다.
  4. 그 합을 보수를 취하여 그 최종 값을 검사합으로 한다.
  5. 검사합을 데이터와 함께 보낸다.

• 수신자 쪽
  1. 메시지(검사합을 포함)를 16비트 워드로 나눈다.
  2. 모든 워드를 1의 보수 연산을 하여 더한다.
  3. 그 합을 보수를 취하여 그 최종 값을 새로운 검사합으로 한다.
  4. 검사합의 값이 0이면 메시지를 받고 아니면 거부한다
  

Error Correction

• 재전송 요구한다
• 무선방식에는 적합하지않음
• 수신받는 bits의 기본으로 에러를 수정하기 위해 필요하다