9 장 오류 검출 및 오류 정정 9.1 오류 종류 9.2 검출 9.3 오류 정정 9.4 요약.

Presentation on theme: "9 장 오류 검출 및 오류 정정 9.1 오류 종류 9.2 검출 9.3 오류 정정 9.4 요약."— Presentation transcript:

1 9 장 오류 검출 및 오류 정정 9.1 오류 종류 9.2 검출 9.3 오류 정정 9.4 요약

2 오류 검출 및 오류 정정 데이터는 전송 중에 손상될 수 있다. 신뢰할 수 있는 통신을 위해서 오류를 검출, 수정해야 한다
OSI 모델의 데이터 링크 층 또는 전송 층에서 수행

3 9.1 오류의 종류

4 오류의 종류(계속) 단일-비트 에러(Single-Bit Error) 데이터 부분의 한 비트만 변경
(예 : ASCII STX - ASCII LF)

5 오류의 종류(계속) 다중-비트 에러(Multiple-Bit Error)
데이터 부분의 2개 또는 그 이상의 비연속적인 비트가 변경(예 : ASCII B - ASCII LF)

6 오류의 종류(계속) 집단 오류(Burst Error) 데이터 부분의 2개 또는 그 이상의 연속적인 비트가 변경

7 9.2 검출 오류 검출은 목적지에서 오류를 검출하기 위해서 여분의 비트를 추가하는 중복(잉여) 개념을 이용

8 검출(계속) 중복(redundancy)

9 검출(계속) 검출 방법 VRC(Vertical Redundancy Check)
LRC(Longitudinal Redundancy) CRC(Cyclical redundancy Check) Checksum

10 검출(계속) VRC(Vertical Redundancy Check)
각 데이터 단위에 패리티 비트가 추가되는데, 이 패리티 비트는 전체 데이터 단위에서 1의 개수가 홀수 또는 짝수가 되게 한다

11 검출(계속) 짝수 패리티 VRC(Vertical Redundancy Check)

12 검출(계속) LRC(Longitudinal Redundancy)
모든 바이트의 짝수 패리티를 모아서 데이터 단위로 만들어서 데이터 블럭의 맨 뒤에 추가

13 검출(계속) 순환 중복 검사(CRC: Cyclic Redundancy Check) 2진 나눗셈을 이용

14 검출(계속) CRC 발생기 모듈러-2 나눗셈을 이용 2진 나눗셈

15 검출(계속) 다항식 CRC 발생기는 1과 0의 스트링 보다는 대수식으로 표현

16 검출(계속) 하나의 다항식은 하나의 젯수를 표현

17 검출(계속) 표준 다항식

18 검출(계속) 검사합(Checksum) 상위 계층 프로토콜에서 사용 중복(VRC, LRC, CRC ….) 개념을 기반으로 한다

19 검출(계속) 검사합(Checksum) 생성기

20 검출(계속) 검사합을 생성하기 위해 송신자는 다음을 수행한다 단위를 길이가 n 비트인 K 섹션으로 나눈다
섹션 1과 2를 1의 보수를 이용하여 더한다 앞의 결과를 섹션 3과 더한다 앞의 결과를 섹션 4와 더한다 이 과정을 섹션 K까지 반복한다 최종 결과는 검사합을 만들기 위해 보수를 취한다

21 검출(계속) 데이터 단위와 검사합

22 9.3 오류 정정 두 가지 방법으로 처리한다 수신자가 송신자에게 전체 데이터 재전송 요구
수신자가 오류 교정 코드를 이용하여 자동으로 수행

23 오류 정정(계속) 단일 비트 오류 교정 패리티 비트 오류 교정의 비밀은 잘못된 비트의 위치를 알아내는 것
ASCII 코드는 3-비트 잉여코드가 필요하다( ) 7비트-8가지 경우

24 오류 정정(계속) 중복 비트 주어진 데이터 비트의 수(m)를 정정하기 위해 요구되는 중복비트 수(r)을 계산하기 위해 m과 r의 관계를 알아야 한다

25 오류 정정(계속) 전송할 수 있는 비트의 전체 수가 m + r이면 r은 적어도 다음 조건을 만족해야 한다 2r  m + r + 1 예) 7 비트(ASCII) m에 대해 가장 적은 r의 값은 4이다24 

26 Number of Redundancy Bits
오류 정정(계속) 데이터와 중복 비트간의 관계 Number of Data Bits (m) Number of Redundancy Bits (r) Total Bits (m+r) 1 2 3 4 5 6 7 2 3 4 3 5 6 7 9 10 11

27 오류 정정(계속) 해밍 코드 R.W. Hamming에 의해 개발 Hamming 코드에서 중복 비트의 위치

28 오류 정정(계속) 각 비트는 데이터 비트의 조합을 위한 VRC 비트이다 r1 = bits 1, 3, 5, 7, 9, 11

29 오류 정정(계속) 중복 비트 계산

30 오류 정정(계속) 값 계산 1이 들어간 비트 11번째 비트:1011 7번째 비트: 0111 6번째 비트: 0110
7번째 비트: 0111 6번째 비트: 0110 3번째 비트: 0011 1001

31 오류 정정(계속) 오류 발견과 교정

32 오류 정정(계속) Hamming 코드를 이용한 오류발견

33 오류 정정(계속) 다중-비트 오류 교정 데이터 비트의 집합을 중복하여 계산되는 중복 비트는 다중 비트 오류를 정정하는 데로 사용할 수 있다

34 9.4 요약