Presentation on theme: "Young-Tae Han {} 오류 검출과 오류 정정 Young-Tae Han {}"— Presentation transcript: 1 Young-Tae Han {}
2 개요 데이터는 전송중에 변경 될 수 있으며 신뢰성 있는 시스템은 이러한 오류들을 검출하고 정정 할 수 있는 수단을 제공해야 함
3 검출 대 정정 검출 - 오류를 찾는것 정정 - 오류를 수정하는 것 전향 오류 정정 재전송 중복 비트를 이용하여 메시지를 추측
4 중복 (Redundancy) 목적지에서 오류를 검출하고 정정 하기 위해 비 트를 추가한 것 부화화 방법을 통해 달성 5 부호화기와 복호화기의 구조
6 해밍코드 (Hamming code) 오류 검출 및
정정이 가능한 코드 오류 제어를 위해 해밍 거리 이용
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) 11
패리티 검사 패리티 검사(Parity check) 단순 패리티 검사 오류 검출에 가장 널리 사용
12 패리티 검사 13 짝수 패리티 비트(even parity bit)
14 짝수 패리티 비트(even parity bit)
15 패리티 검사 예제 1 송신자가 ‘world’라는 단어를 보내고자 한다. ASCII(부록 A 참조)를 사용하면 다섯 글자는 다음처럼 코드화 된다. 다음은 실제 전송되는 비트를 보여주고 있다.
16 패리티 검사 예제 2 예제 1에서 ‘world’라는 단어가 전송시 변환되지 않고 수신자에 의 해 수신되었다고 가정하자.
17 패리티 검사 예제 3 예제 1에서 ‘world’라는 단어가 전송 중 변환되었고, 이를 수신자가 수신했다고 가정하자. 수신자는 각 글자에서 1의 수를 세고 짝수와 홀수(7, 6, 5, 4, 4)임을 알아낸다. 수신자는 데이터가 변환되었음 을 알고 그 단어를 버리고 재전송을 요청한다.
18 패리티 검사 단순 패리티 검사는 모든 단일 비트 오류를 검출할 수 있다. 각 데이터 단위상의 오류의 전체 개수가 홀수인 경우라면 폭주 오류도도 검출할 수 있다.
19 2차원 패리티 검사 2차원 패리티 검사 모든 바이트의 짝수 패리티를 모아서 데이터 단위로 만들어서 데 이터 블록의 맨 뒤에 추가
20 해밍 코드
R.W. Hamming에 의해 개발 중복비트의 위치를 분산함 Hamming 코드에서 중복 비트의 위치 21 해밍코드 부호화기와 복호화기의 구조
22 해밍코드 n : 코드 워드 크기, k:데이터 워드 크기, m:확인 비트수
23 해밍 코드(계속) 각 비트는 데이터 비트의 조합을 위한
패러티 비트 중복 비트 계산
24 해밍 코드(계속) 25 해밍
코드(계속) 값 계산(짝수 사용) 26 해밍 코드(계속) 오류 발견과 정정
27 순환중복검사(CRC; Cyclic Redundancy Check)
28 순환중복검사 CRC 발생기 모듈러-2 나눗셈을 이용 2진 나눗셈
29 순환중복검사 CRC 검사기
30 순환중복검사 다항식 CRC 발생기는 1과 0의 스트링
보다는 대수다항식으로 표현 31 순환중복검사 하나의 다항식은 하나의 젯수를 표현
32 순환중복검사 표준 다항식 Name Polynomial Application CRC-8 x8 + x2 + x + 1 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) 상위 계층 프로토콜에서 사용 전체 숫자의 합도 전송 37 검사합(Checksum) 발생기
38 검사합(Checksum) 데이터 단위와 검사합
39 검사합(Checksum) 검사합을 생성하기 위해 송신기는 다음을 수행한다 40
검사합(Checksum) 검사합을 생성하기 위해 수신기는 다음을 수행한다
41 검사합(Checksum) 검사합(Checksum) 검사기 수신기는 데이터 단위를 나눈다 42 검사합(Checksum) 예제 7 10101001 00111001 10101001 00111001 ---------
43 검사합(Checksum) 예제 8 이제 수신자가 예제 7에서 보낸 비트 형식을 받았고 오류는 없다고 가정하자. 수신자가 3개의 섹션 모두를 더한 후, 모두 1의 결과를 얻을 것이다. 보수화하면 모두 0이고 오류가 없음을 보여준다. Sum Complement
44 검사합(Checksum) 예제 9 이제 4비트에 영향을 주는 길이 5의 폭주 오류가 있다고 가정하자 수신자가 3개의 섹션을 모두 더하면 다음을 얻게 된다. Result Carry Sum Complement (이 비트 형식은 변환되었음을 의미)
45 검사합(Checksum) 성능 짝수/홀수 개의 비트 오류를 검출 |