10 장 오류 검출 및 수정 10.1 오류 종류 10.2 검출 10.3 오류 정정 10.4 요약

데이터는 전송 중에 변경될 수 있다. 신뢰성 있는 통신을 위해 오류들은 검출·정정되어야 한다. 오류 검출 및 수정 데이터는 전송 중에 변경될 수 있다. 신뢰성 있는 통신을 위해 오류들은 검출·정정되어야 한다.

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

단일 비트 오류는 데이터 단위 중 하나의 비트만이 변경되었을 때를 일컫는다. 오류의 종류(계속) 단일 비트 오류는 데이터 단위 중 하나의 비트만이 변경되었을 때를 일컫는다.

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

폭주 오류는 데이터 단위에서 2개 이상의 연속적인 비트들이 변경되는 경우를 일컫는다. 오류의 종류(계속) 폭주 오류는 데이터 단위에서 2개 이상의 연속적인 비트들이 변경되는 경우를 일컫는다.

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

검출(계속) 중복(redundancy)

오류 검출은 목적지에서 오류를 검출하기 위해 여분의 비트들을 추가하는 중복의 개념을 사용한다. 검출(계속) 오류 검출은 목적지에서 오류를 검출하기 위해 여분의 비트들을 추가하는 중복의 개념을 사용한다.

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

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

검출(계속) 짝수 패리티 비트(even parity bit)

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

검출(계속) 예제 1 송신자가 ‘world’라는 단어를 보내고자 한다. ASCII(부록 A 참조)를 사용하면 다섯 글자는 다음처럼 코드화 된다. 1110111 1101111 1110010 1101100 1100100 다음은 실제 전송되는 비트를 보여주고 있다. 11101110 11011110 11100100 11011000 11001001

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

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

검출(계속) 성능 VRC(vertical redundancy check) 검사기는 모든 단일 비트 오류를 검출할 수 있음.

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

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

검출(계속) 예제 4 다음의 블록을 전송한다고 가정하자. 10101001 00111001 11011101 11100111 10101010 그런데 폭주길이 8의 폭주잡음을 만나 일부 비트가 변환되었다. 10100011 10001001 11011101 11100111 10101010 수신자가 LRC(logitudinal redundancy check)를 검사할 때, 일부 비트가 짝수 패리티 규칙을 따르지 않고 전체 블록은 버려지게 된다.(적합하지 않은 비트는 굵은 글씨로 보인다.)

2차원 패리티 검사에서는 비트의 블록은 행으로 나뉘고 비트의 나머지 행은 전체 블록에 추가된다. 검출(계속) 2차원 패리티 검사에서는 비트의 블록은 행으로 나뉘고 비트의 나머지 행은 전체 블록에 추가된다.

검출(계속) 성능 폭주 오류의 검출 가능성 증가 n 비트의 중복 비트는 n 비트의 폭주 오류를 쉽게 검출 하나의 데이터 단위 내에서 두 비트가 손상되고 다른 데이터 단위 내에서 정확히 같은 위치의 두 비트가 손상되었을 경우 오류를 검출하지 못함 11110000과 11000011 → 01110001과 01000010

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

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

검출(계속) CRC 검사기

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

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

검출(계속) 표준 다항식 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

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

검출(계속) 성능 CRC는 홀수 비트에 영향을 주는 모든 폭주 오류를 검출

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

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

검출(계속) 검사합(Checksum) 발생기

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

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

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

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

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

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

검출(계속) 예제 9 이제 4비트에 영향을 주는 길이 5의 폭주 오류가 있다고 가정하자 10101111 11111001 00011101 수신자가 3개의 섹션을 모두 더하면 다음을 얻게 된다. 10101111 11111001 00011101 --------- Result 1 11000101 Carry 1 Sum 11000110 Complement 00111001 (이 비트 형식은 변환되었음을 의미)

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

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

오류 정정(계속) 재전송에 의한 오류 정정 오류가 발견될 경우 전체 데이터를 다시 송신 흐름제어와 오류제어에서 논의

오류 정정(계속) 전향 오류 정정(forward error correction) 패리티 비트 오류 정정의 비밀은 잘못된 비트의 위치를 알아내는 것 ASCII 코드는 3-비트 잉여코드가 필요하다(000-111)

오류 정정(계속) 중복 비트 주어진 데이터 비트의 수(m)를 정정하기 위해 요구되는 중복비트 수(r)을 계산하기 위해 m과 r의 관계를 알아야 한다 전송할 수 있는 비트의 전체 수가 m+r이면 r은 적어도 2r  m + r + 1을 만족해야 한다 7 비트(ASCII) m에 대해 가장 적은 r의 값은 4이다 24  7 + 4 + 1

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

오류 정정(계속) 해밍 코드(Hamming code) R.W. Hamming에 의해 개발

오류 정정(계속) 각 r 비트는 데이터 비트의 조합에 대하 패리티 비트이다 r1 = bits 1, 3, 5, 7, 9, 11

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

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

오류 정정(계속) 해밍 코드를 이용한 오류 검출

오류 정정(계속) 폭주 오류 정정 데이터 단위의 비트 전송 순서를 바꾸어서 해밍코드를 사용하여 폭주 오류를 정정할 수 있다

10.4 요약