Error Detection and Correction

Presentation on theme: "Error Detection and Correction"— Presentation transcript:

1 Error Detection and Correction
Chapter 10 Error Detection and Correction

2 오류 제어(error control) 오류 검출(error detection) 오류 정정(error correction)
블록 코드 단순 패리티 코드(parity code) 순환 중복 확인(Cyclic Redundancy Check) 검사합(checksum) 오류 정정(error correction) 전향 오류 정정(forward error correction) 재전송(retransmission)

3 에러 종류: single bit error

4 에러 종류: burst error

5 에러 검출/정정 코드 에러 검출 혹은 정정을 위해서 여분의 비트들(redundancy)을 데이터에 덧붙여서 전송한다.

6 에러 검출 코드 패러티 비트(parity bit) 순환 중복 확인(Cyclic Redundancy Check)
검사합(checksum)

7 Even parity bit 비트 1의 수가 짝수(even)가 되도록 데이터 비트에 패리티 비트를 추가한다.

8 2-dimensional parity

9 순환 중복 확인(CRC) 가장 널리 사용되는 에러 검출 방법 하드웨어로 쉽게 구현할 수 있다.

10 에러검출 코드 생성(CRC encoder)
데이터워드: k 비트 Divisor 혹은 generator: m 비트 에러 검출 코드: m-1 비트 데이터워드를 생성기로 (모듈로-2) 나누어서 구한다. 코드워드: n = k + (m-1) 비트 데이터워드에 에러 검출 코드를 덧붙인다. 송신장치는 코드워드를 전송한다.

11 CRC encoder and decoder

12 CRC encoder 예 Dataword: 1001 Divisor : 1011 Error detection code: 110
Codeword:

13 에러 검출(CRC decoder) 수신한 Codeword를 divisor로 나눈다.
만약 나머지가 0이면 에러가 없거나 에러 발견 실패 만약 나머지가 0이 아니면 에러 발생

14 CRC decoder 예 에러 발생

15 CRC 다항식 divisor(혹은 generator)는 다항식으로 표현하기도 한다.

16 표준 CRC 다항식

17 CRC는 얼마나 잘 에러를 검출한는가? Divisor가 어떤 것인가에 따라 다르다. 좋은 divisor는 그렇다면,
두 개 이상의 항으로 되어 있어야 한다. X0항의 계수는 1이어야 한다. 0부터 n-1 사이의 t값에 대해서 xt+1을 나누어 떨어지지 않도록 해야 한다. X+1을 인자로 갖고 있어야 한다. 그렇다면, 단일 비트, 두 비트, 홀수개의 비트 에러, 그리고 대부분의 burst error를 검출할 수 있다.

18 검사합(checksum) CRC가 하드웨어로 구현하기 편리한 반면에 소프트웨어로 구현해야 하는 경우 checksum을 사용한다. 인터넷의 IP와 TCP에서 사용

19 1의 보수 연산으로 checksum 계산

20 송신 1. 데이터(프레임)를 16 비트 길이의 워드로 나눈다. 2. Checksum 워드의 자리에는 0을 대입한다.
4. 합한 결과를 1의 보수로 만든다. 5. 이것을 checksum 워드 자리에 대입하여 데이터를 전송한다.

21 수신 1. 수신한 데이터(프레임)를 16 비트 길이의 워드로 나눈다.
2. Checksum을 포함한 모든 워드들을 1의 보수 연산으로 더한다. 3. 합한 결과를 1의 보수로 만든다. 4. 이 값이 0이면 에러가 없는 것이고 0이 아니면 에러가 발생한 것이다.

22 예제 10.23 F F F F