[정보통신공학] CH 6 Error Detection and Correction

 Timing

 

*clock synch를 맞추는 것 -  bit arrival time, bit interval을 맞추는 것

 

1. Asynchronous Serial Transmission

-TX와 RX가 처음만 synch를 맞추고 그 후에는 맞추지 않은 것(L1에서 싱크 안맞춤)

 (1) data stream은 synchronization 정보를 가지고 있음

  - start bit =0, stop bit = 1

 (2) TX와 RX 사이의 약속

  - data bit의 수와 순서

  - stop bit의 길이

  - parity bit의 존재 여부와 odd/even parity

  - bit 간격

 (3) 데이터는 한번에 한 문자씩 전송됨

 [Frame]  

  ① start bit

  ② 각 문자는 5~8 bit 길이

  ③ parity bit(optional)

  ④ stop bit 1~2bit

 (4) RX는 각 문자의 시작(start bit)에서 새롭게 synch를 다시 맞출 수 있는 기회를 가짐

 (5) 장점: 간단 & 쌈, 큰 gap을 가진 data는 좋음 (keyboard, teletypewriter)

      단점: 한 문자마다 최소 2~3bit overhead, 큰 block은 timing error남

 (6) point to point

 

2. Synchronous Serial Transmission

-TX와 RX가 계속적으로 synch를 맞춰주는 것

 (1) receive clock을 계속해서 transmitter clock과 맞춰줌

   - 방법1) TX와 RX 사이에 별도의 clock을 이용 : 짧은 거리에는 좋지만 장거리로 가면 손상 발생

   - 방법2) data 신호 안에 clocking 정보 넣기:  맨체스터 인코딩 -> clock 정보를 주기 위해 1bit당 2bit를 보내야함

   - 방법3) 앞과 뒤에 bit pattern을 넣어줌 -> frame

 (2) multi point

 

2-1.  Synchronous Serial Transmission - Efficiency

 (1) 데이터 블록은 start,stop bit 없이 안정적 흐름으로 전달됨

   - HDLC : bit단위로 하나씩

   - LAN: 8bit 단위로 읽음

 (2) 데이터의 큰 block에서 asynchronous보다 높은 효율성과 낮은 overhead를 가짐

 

 

3. Types of Errors

 (1) 에러는 TX에서 RX 사이에서 bit가 바뀔 때 발생 

 (2) Single bit error

  - 한 비트만 바뀜

  - 인접한 비트는 영향 받지 않음

  - white noise에 의해 발생

 (3) Burst error

  - 연속적인 bit에서 error 발생

  - 높은 데이터 전송 속도에서 더 많이 발생

  - impulse noise와 무선 환경의 fading에 의해 발생

 

4. Burst Bit Errors

 - 두 개의 연속적인 오류 비트가 항상 x보다 작은 올바른 비트 수로 구분되는 비트. 따라서 버스트의 마지막 오류 비트와 다음 버스트의 첫 번째 오류 비트는 x개 이상의 올바른 비트로 구분됨. error가 안난 간격이 x보단 작아야함

 

 

 

 Error Detection

 

1. Error Detectoin at layer 2

 (1) frames: data는 하나 또는 그 이상의 연속된 bit로 전달

 (2) 에러가 안날 확률 = (1-single bit error가 날 확률)^n(frame size) 

 (3) frame의 길이 늘리면 에러가 나지 않을 확률이 줄어듦

  - frame의 길이가 더 길면, 더 많은 bit를 가지고 error가 날 확률이 높아짐

 * No error frame을 늘리는 것이 목표

L2 Error Detection Process

 - error를 detection/correction 하려고 넣는 redundancy 자체도 error의 frame을 늘리면서 error 확률을 높임

 

2. 3 Error detection techniques

 (1) Parity Check (L2)

 (2) Internet checksum (L3, L4)

 (3) Cyclic Redundancy Check (CRC) (L2)

* 1,3 additional bits 사용. TX에 의해. error detection 목적. payload data 추가

 

3. Single (odd or even) Parity Check

 (1) 가장 단순한 에러 탐지법. 데이터 블록의 끝에 parity bit 추가

 (2) RX에 의해 코드는 다시 계산되고 체크됨

 (3) parity의 값은 한 문자가 1을 몇개 가지고 있느냐에 따라 결정 - 1의 개수가 odd면 1, even이면 0

 (4) exclusive - or을 사용

 + error bit가 짝수개이면 parity bit로 error을 탐지하지 못한다. parity bit는 1의 홀수, 짝수로 결정하기 때문.

 

4. 2-dimensional parity check

 

5. Internet Checksum

 (1) 인터넷 표준 프로토콜(IPv4, TCP, and UDP)에서 사용되는 error 탐지

 (2) 3 steps

  ① 16bit 크기로 줄세우기

  ② 두 숫자씩 더하기(한 숫자당 16 bit). 만약 MSB를 넘어가는 것이 있다면 더한 결과에 1을 더하기 

  ③ 다시 숫자를 뒤집기 

 (3) Internet Checksum의 한계

  - 완벽하게 뒤집어진(서로 교환된 것 같은 형태의) bit error가 생기면 error를 검출하지 못함

  - 16 bit block 2개가 서로 교환된 것 같은 형태의 error가 나면 검출 X 

 

6. Cyclic Redundancy Check (CRC)

 (1) Burst error는 거의 parity check에서 error 탐지 X

 (2) TX가 FCS라고 하는 redundant bit를 붙여주는 것

  - FCS는 RX가 에러를 탐지할 때 사용됨

 (3) HOW?

  ① k = number of original data, D(k)

  ② n = frame을 구성하는 bit의 수, frame size, T(n)

  ③ TX는 n-k개의 bit를 만듦. 이것이 F(n-k). 

   - T(n)을 P로 나눠줌. P는 n-k+1 bits

   - T(n)을 P값으로 나눴을 때 딱 나눠떨어지게 하는 F값을 만들어 보내야함

  ④ RX가 P로 frame을 나눔

   - 만약 나머지가 0이라면, 에러가 없다고 판단

   - 많은 에러난 비트가 P로 새로운 정확한 나누기를 초래하지 않는다면, 에러가 탐지 되지 않음. 

 

 

7. CRC Generation

 (1) TX에서 CRC 생성은 주어진 data와 divisor로 FCS를 찾는 것

 (2) CRC 코드를 만드는 방법

  ① modulo 2 arithmetic

  ② polynomial

  ③ digital logic

 

 8. CRC - modulo 2 arithmetic method

 (1) carry 없이 binary addition

 (2) XOR 방식 사용

 (3) data의 맨 뒤에 n-k개의 0을 추가해놓고 계산 시작

 (4) at TX

  ① 2^(n-k) x D (왼쪽으로 shift 연산자 역할)

  ② ①/P -> 나머지: R(n-k)

  ③  기존 데이터에 FCS인 R(n-k)값 더하기 

  ④ T(n) = (D(n)+R(n-k)) 값을 RX로 보내기

 (5) 

  ① T(n) 값 받기

  ② T(n) / P 

  ③ 나눈 것의 나머지가 0이면 에러가 없다고 판단

 

9. CRC - Polynomial method

 (1) D(k)가 다항식으로 표현돼 있을 때, D(x)는 (k-1)차항

 (2) x^4를 곱하는 것은 D의 맨 뒤에 0을 4번 붙여주는 것과 같음

 (3) Divisor P should have following properties

  ① 최소 2bit (11)

  ② 상수항은 무조건 1

 

10. CRC - Digital Logic method **

 (1) shift register, XOR 사용 

  - FCS의 길이(n-k)만큼 이동

 (2) bit 값이 1인 register 뒤에 XOR gate 넣기

 (3) RX에도 같은 logic

 

 

 

 Error Correction

 

1. Error Correction at layer 2 - two alternatives

 (1) BEC(Backward Error Correction) method

  ① RX는 에러가 난 frame에 retransmission을 요청할 수 있음

  ② data link protocol - HDLC, transport protocol - TCP

  ③ 아래에의 것들에는 적절하지 않음

   - 무선

   - frame transmission time에 비해 propagation delay가 큰 곳

   - real-time application

  (2) FEC(Forward Error Correction) method

   ① TX는 RX가 error correct 하게 하기 위해서 block coding을 사용 (보낼 때 block으로 나눠 encoding하여 보냄)

 

2. (FEC) Error Correction Process Diagram

 

3. (FEC) Block code principles - Hamming distance

 (1) Hamming distance d(v1,v2)

  - d(011011, 110001) 서로 다른 bit 수 몇개인지 -> 3개

 (2) Hamming distance를 사용하여 error correction이 작동하는 방법

  ① data를 k-bit block으로 쪼개기

  ② k-bit block을 n-bit codeword로 map (n>k)

  ③ k-bit block 대신 n-bit codeword를 보냄