Young-Tae Han {han0tae@gmail.com} 오류 검출과 오류 정정 Young-Tae Han {han0tae@gmail.com}

Presentation on theme: "Young-Tae Han {han0tae@gmail.com} 오류 검출과 오류 정정 Young-Tae Han {han0tae@gmail.com}"— Presentation transcript:

1 Young-Tae Han {han0tae@gmail.com}
오류 검출과 오류 정정 Young-Tae Han

2 개요 데이터는 전송중에 변경 될 수 있으며 신뢰성 있는 시스템은 이러한 오류들을 검출하고 정정 할 수 있는 수단을 제공해야 함
데이터는 전송중에 변경 될 수 있으며 신뢰성 있는 시스템은 이러한 오류들을 검출하고 정정 할 수 있는 수단을 제공해야 함 오류의 종류 단일비트 오류 (Single-bit error) 하나의 비트가 변경 된 경우 폭주 오류 (Burst error) 2개 이상의 비트가 변경 된 경우

3 검출 대 정정 검출 - 오류를 찾는것 정정 - 오류를 수정하는 것 전향 오류 정정 재전송 중복 비트를 이용하여 메시지를 추측
오류가 검출되면 송신자에게 재전송을 요청

4 중복 (Redundancy) 목적지에서 오류를 검출하고 정정 하기 위해 비 트를 추가한 것 부화화 방법을 통해 달성
블록 부호화 콘볼루션 부호화

5 부호화기와 복호화기의 구조

6 해밍코드 (Hamming code) 오류 검출 및 정정이 가능한 코드 오류 제어를 위해 해밍 거리 이용
Parity digit라고 불리는 여분의 코드를 가지고 있음 해밍 거리 (Hamming distance) 두 같은 크기의 워드에서 서로 차이가 나는 해당 비 트들의 개수 d(x,y)로 표시 최소 해밍 거리 모든 가능한 워드 조합 중 가장 작은 해밍 거리

7 예제 d(000, 011) =2 d(00000,01011), d(00000,10101), d(00000,11110)에서 dmin(x,y)=3

8 오류 검출을 위한 최소 해밍 거리 S개까지의 오류가 발생해도 오류가 생긴 것을 알아내 는 것을 보장하기 위해서는 블록 코드의 최소 해밍 거 리는 dmin=s+1 이어야 함

9 오류 정정을 위한 최소 거리 모든 경우에 있어서 t오류까지 교정을 보장하기 위하 여 블록 코드에서의 초소 해밍 거리는 dmin=2t+1 이어 야 함

10 검출 검출 방법 패리티 검사(Parity check) 순환중복검사(CRC; Cyclical redundancy Check)
검사합(Checksum)

11 패리티 검사 패리티 검사(Parity check) 단순 패리티 검사 오류 검출에 가장 널리 사용
단순 패리티 검사와 2차원 패리티 검사 단순 패리티 검사 패리티 비트(parity bit)라 불리는 중복 비트를 데이터 단위에 덧붙임 패리티 비트(parity bit)를 포함한 데이터 단위 내의 1의 전체 개수가 짝수(또는 홀수)가 되도록 함 짝수 패리티(even parity) 1의 전체 개수가 짝수가 되도록 함 홀수 패리티(odd parity) 1의 전체 개수가 홀수가 되도록 함

12 패리티 검사

13 짝수 패리티 비트(even parity bit)

14 짝수 패리티 비트(even parity bit)
패리티 검사에서 패리티 비트는 모든 데이터 단위에 덧붙여져서 1의 전체 개수가 짝수가 되도록 한다.(홀 수 패리티의 경우에는 홀수)

15 패리티 검사 예제 1 송신자가 ‘world’라는 단어를 보내고자 한다. ASCII(부록 A 참조)를 사용하면 다섯 글자는 다음처럼 코드화 된다. 다음은 실제 전송되는 비트를 보여주고 있다.

16 패리티 검사 예제 2 예제 1에서 ‘world’라는 단어가 전송시 변환되지 않고 수신자에 의 해 수신되었다고 가정하자.
수신자는 각 글자에서 1의 수를 세고 짝수 (6, 6, 4, 4, 4)임을 알아 낸다. 그 단어는 받아들여진다.

17 패리티 검사 예제 3 예제 1에서 ‘world’라는 단어가 전송 중 변환되었고, 이를 수신자가 수신했다고 가정하자. 수신자는 각 글자에서 1의 수를 세고 짝수와 홀수(7, 6, 5, 4, 4)임을 알아낸다. 수신자는 데이터가 변환되었음 을 알고 그 단어를 버리고 재전송을 요청한다.

18 패리티 검사 단순 패리티 검사는 모든 단일 비트 오류를 검출할 수 있다. 각 데이터 단위상의 오류의 전체 개수가 홀수인 경우라면 폭주 오류도도 검출할 수 있다.

19 2차원 패리티 검사 2차원 패리티 검사 모든 바이트의 짝수 패리티를 모아서 데이터 단위로 만들어서 데 이터 블록의 맨 뒤에 추가

20 해밍 코드 R.W. Hamming에 의해 개발 중복비트의 위치를 분산함 Hamming 코드에서 중복 비트의 위치

21 해밍코드 부호화기와 복호화기의 구조

22 해밍코드 n : 코드 워드 크기, k:데이터 워드 크기, m:확인 비트수
m ≥ dmin n ≥ 2m-1 k=n-m 최소 데이터워드가 7비트를 필요로 할경우 해 밍코드의 k값과 n값을 구하라 2m-1-m≥7 , m=4 n=24-1=15, k=15-4=11 C(15,11)

23 해밍 코드(계속) 각 비트는 데이터 비트의 조합을 위한 패러티 비트 중복 비트 계산
r1 = bits 1, 3, 5, 7, 9, 11 r2 = bits 2, 3, 6, 7, 10, 11 r4 = bits 4, 5, 6, 7 r8 = bits 8, 9, 10, 11 중복 비트 계산 r1 – 최하위의 위치에 1을 포함하는 모든 비트들 r2 – 두 번째 위치에 1을 포함하는 모든 비트들 r3 – 세 번째 위치에 “ r4 – 네 번째 위치에 “

24 해밍 코드(계속)

25 해밍 코드(계속) 값 계산(짝수 사용)

26 해밍 코드(계속) 오류 발견과 정정

27 순환중복검사(CRC; Cyclic Redundancy Check)
2진 나눗셈을 이용

28 순환중복검사 CRC 발생기 모듈러-2 나눗셈을 이용 2진 나눗셈

29 순환중복검사 CRC 검사기

30 순환중복검사 다항식 CRC 발생기는 1과 0의 스트링 보다는 대수다항식으로 표현

31 순환중복검사 하나의 다항식은 하나의 젯수를 표현

32 순환중복검사 표준 다항식 Name Polynomial Application CRC-8 x8 + x2 + x + 1
ATM header CRC-10 x10 + x9 + x5 + x4 + x 2 + 1 ATM AAL ITU-16 x16 + x12 + x5 + 1 HDLC ITU-32 x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1 LANs

33 순환중복검사 예제 5 x(2진수 10) 또는 x2+x(2진수 110)는 x로 나누어지 므로 다항식으로 선택될 수 없는 것이 분명하다. 그 렇지만 (x+1)(2진수 11)은 x로 나누어지지 않고 (x+1) 로 나뉘므로 선택할 수 있다. 또한 x2+x(2진수 101) 도 (x+1)(2진 나눗셈)로 나누어지므로 선택할 수 있 다.

34 순환중복검사 성능 CRC는 홀수 비트에 영향을 주는 모든 폭주 오류를 검출

35 순환중복검사 예제 6 차수가 12인 CRC-12(x12+x11+x3+x+1)는 홀수 비 트에 영향을 주는 모든 폭주 오류를 검출할 수 있고, 12이하의 길이를 가진 모든 폭주 오류를 검출할 수 있으며, 12이상의 길이를 갖는 99.97퍼센트의 폭주 오류를 검출할 수 있다.

36 검사합(Checksum) 상위 계층 프로토콜에서 사용 전체 숫자의 합도 전송
중복(VRC, LRC, CRC ….) 개념을 기반으로 한다

37 검사합(Checksum) 발생기

38 검사합(Checksum) 데이터 단위와 검사합

39 검사합(Checksum) 검사합을 생성하기 위해 송신기는 다음을 수행한다
데이터 단위는 각각 n 비트인 k 개의 섹션으로 나뉜다 모든 섹션은 합을 만들기 위해 1의 보수를 사용하여 서로 더해진 다. 합은 보수화되고 검사합으로 된다 검사합은 데이터와 함께 보내진다

40 검사합(Checksum) 검사합을 생성하기 위해 수신기는 다음을 수행한다
데이터 단위는 각각 n 비트인 k 개의 섹션으로 나뉜다 모든 섹션은 합을 만들기 위해 1의 보수를 사용하여 서로 더해 진다 합은 보수화된다 결과가 0이면 데이터는 받아들여지고, 그렇지 않으면 거부된다

41 검사합(Checksum) 검사합(Checksum) 검사기 수신기는 데이터 단위를 나눈다
모든 세그먼트들을 더하고 결과를 보수화 한다 데이터 세그먼트와 검사합을 더한 전체 값이 0이면 데이터가 손상 되지 않았다는 의미 0이 아니라면 수신기는 이를 거부

42 검사합(Checksum) 예제 7 10101001 00111001 10101001 00111001 ---------
다음과 같은 16비트 블록이 8비트의 검사합을 사용하여 보내진다고 가정 하자. 1의 보수연산을 사용해서 수를 더한다 Sum Checksum

43 검사합(Checksum) 예제 8 이제 수신자가 예제 7에서 보낸 비트 형식을 받았고 오류는 없다고 가정하자. 수신자가 3개의 섹션 모두를 더한 후, 모두 1의 결과를 얻을 것이다. 보수화하면 모두 0이고 오류가 없음을 보여준다. Sum Complement

44 검사합(Checksum) 예제 9 이제 4비트에 영향을 주는 길이 5의 폭주 오류가 있다고 가정하자 수신자가 3개의 섹션을 모두 더하면 다음을 얻게 된다. Result Carry Sum Complement (이 비트 형식은 변환되었음을 의미)

45 검사합(Checksum) 성능 짝수/홀수 개의 비트 오류를 검출
하나 이상의 세그먼트가 손상되고 두 번째 세그먼트에 대응하는 비트들 또한 손상될 경우 오류를 검출하지 못함