10장 오류 검출과 오류 정정 (Error Detection and Correction)

10장 : 개요 10.1 소개 10.2 블록 코딩 10.3 순환 코드 10.4 검사합 10.5 전향 오류 정정 10.6 요약

10.1.1 오류의 종류 단일비트 오류(single-bit error): 주어진 데이터 단위(예를 들어 한 바이트의 문자, 또는 패킷)중 오직 하나의 비트만이 1에서 0 또는 0에서 1로 변경되는 오류 폭주 오류(burst error): 데이터 단위에서 2개 이상의 연속적인 비트들이 1에서 0 또는 0에서 1로 바뀌는 오류

10.1.1 오류의 종류 그림 10.1 : 단일비트 오류와 폭주 오류

10.1.2 중복 중복(redundancy) 오류를 검출하거나 정정하는 것의 중심 개념 오류를 검출하거나 정정할 수 있기 위해서는 데이터 이외에 추가 비트들을 보내야 하는데, 이 중복 비트는 송신자에 의해 첨가되며 수신자가 제거함 중복 비트들로 인해 수신자는 오류를 찾아내거나 정정할 수 있음

10.1.3 검출 대 정정 오류 검출 오류가 생겼는지 알아내는 것 간단히 오류가 있느냐 없느냐만 확인 오류가 몇 개인지 조차 알 필요가 없음 오류 정정 정확하게 몇 비트가 잘못 되었는지, 어디가 잘못 되었는지를 알아내는 것

10.1.4 코딩 송신자는 중복 비트와 실제 데이터 비트들 사이에 어떤 관련을 짓게 하는 과정을 통해 중복 비트들을 보냄 수신자는 이 두 종류의 비트들 사이의 관계를 확인하여 오류를 검출하거나 정정함 코딩 방법은 블록 코딩(block coding)과 컨볼루션 코딩(convolution coding)으로 나뉨 1.#

10.2 블록 코딩 블록 코딩 데이터워드(dataword)라고 불리는 k 비트의 블록으로 메시지를 나눔 각 블록에 r개의 중복 비트들을 더하여 길이 n= k + r이 되도록 함 결과로 얻는 n비트 블록들은 코드워드(codeword)라고 불림 1.#

10.2.1 오류 검출 다음 두 조건으로 수신자는 원래 코드워드가 바뀐 것을 확인 수신자는 유효 코드워드들을 찾아내거나 그 리스트를 가지고 있다. 원래의 코드워드가 무효 코드워드로 바뀌었다. 1.#

10.2.1 오류 검출 그림 10.2: 블록 코딩의 오류 검색 과정 1.#

10.2.1 오류 검출 예제 10.1: k = 2이고 n = 3이라고 하자. 표 10.1에 데이터워드와 코드워드가 있다. 나중에 데이터워드로부터 어떻게 코드워드를 만들어 내는지 논의한다. 표 10.1 : 오류 검색(예제 10.1)을 위한 한 가지 코드 송신자가 데이터워드 01을 011로 코딩하여 수신자에게 보낸다고 하자. 다음 경우를 생각하라. 1.#

10.2.1 오류 검출 예제 10.1(계속): 수신자가 011을 수신한다. 이는 유효 코드이다. 수신자는 이로부터 데이터워드 01을 추출한다. 코드워드가 전송 도중 손상되어 111이 수신되었다(맨 왼쪽 비트가 깨졌다). 이는 유효 코드가 아니므로 버려진다. 코드워드가 전송 도중 손상되어 000이 수신되었다(오른 쪽 두 비트가 깨졌다). 이는 유효 코드이다. 수신자는 이로부터 부정확한 데이터워드인 00을 추출한다. 두 개 비트가 손상되어 오류를 찾지 못한다. 1.#

10.2.1 오류 검출 해밍 거리(Hamming distance) 두 개의 같은 크기의 워드간에 차이가 나는 비트의 개수 두 워드에 XOR 연산을 해서 얻은 결과 값의 1의 개수 최소 해밍 거리(minimum Hamming distance) 모든 가능한 코드워드 쌍들 사이의 가장 작은 해밍 거리 1.#

10.2.1 오류 검출 예제 10.2 :두 워드들 사이의 해밍 거리를 알아보자. d(000, 011)은 2인데 이는 000 ⊕ 011은 011(두 개의 1)이기 때문이다. d(10101, 11110)은 3인데 10101 ⊕ 11110은 01011(3개의 1)이기 때문이다. 1.#

10.2.1 오류 검출 그림 10.3 :오류 검색에서 dmin을 구하기 위한 기하학적 개념 1.#

10.2.1 오류 검출 예제 10.3 :우리의 첫 번째 코드 기법(표 10.1)의 최소 해밍 거리는 2이다. 이 코드는 오직 단일 비트 오류를 검출할 수 있다. 예를 들면 세 번째 코드(101)가 전송되었는데 하나의 비트 오류가 발생했다면 수신된 코드는 그 어떤 유효 코드가 일치하지 않는다. 그러나 두 개의 오류가 발생했다면 수신된 코드워드는 다른 유효 코드와 일치할 수 있으므로 오류를 알아 낼 수 없다. 1.#

10.2.1 오류 검출 예제 10.4 :코드 기법 해밍거리 dmin= 4이다. 이 코드는 세 개까지의 오류(d = s + 1 or s = 3)를 검출 할 수 있다. 1.#

10.2.1 오류 검출 선형 블록 코드(Linear block code): 두 유효한 코드워드에 대해 XOR 연산을 가해 다른 유효한 코드워드를 생성하는 코드 패리티 검사 코드 선형 블록 코드 k비트 데이터워드를 n=k+1이 되도록 n비트 코드워드로 바꾸는 것 추가된 비트는 패리티 비트라고 불리며 전체 코드워드의 1의 개수가 짝수가 되도록 선정 최소 해밍 거리 dmin=2이며 이는 코드가 단일비트 오류 검출코드라는 것을 의미 1.#

10.2.1 오류 검출 예제 10.5 :표 10.1에 사용된 방식은 임의의 코드워드를 다른 코드워드와 XOR 연산을 시키면 다른 유효 코드워드가 나오기 때문에 선형 블록 코드이다. 예를 들면, 두 번째 코드워드와 세 번째 코드워드를 XOR하면 네 번째 코드워드가 나온다. 1.#

10.2.1 오류 검출 예제 10.6 :첫 번째 코드(표 10.1)에서는 0이 아닌 코드워드의 1의 개수는 각각 2, 2 및 2이다. 그러므로 최소 해밍 거리 dmin= 2이다. 1.#

10.2.1 오류 검출 표 10.2: 단순 패리티 검사 코드 C(5,4) 1.#

10.2.1 오류 검출 그림 10.4: 단순 패리티 검사 코드의 부호화기와 복호기 1.#

10.2.1 오류 검출 예제 10.7: 어떤 전송 시나리오를 생각해보자. 송신자는 1011의 데이터워드를 보낸다고 하자. 이 데이터워드로부터 생성된 코드워드는 10111이며 이것이 수신자에게 보내진다. 다섯 가지 경우에 대해 조사해 보자. 오류가 발생하지 않았다. 수신된 코드워드는 10111이다. 신드롬은 0이다. 데이터워드 1011이 만들어진다. a1 비트에 손상이 생겨 한 개의 비트가 바뀌었다. 수신된 코드워드는 10011이다. 신드롬은 1이다. 데이터워드는 만들어지지 않았다. 1.#

10.2.1 오류 검출 예제 10.7(계속): 3) r0 비트에 손상이 생겨 한 개의 비트가 바뀌었다. 수신된 코드워드는 10110이다. 신드롬은 1이다. 데이터워드는 만들어지지 않았다. 데이터비트는 손상되지 않았지만 코드가 어디가 손상되었는지 알려주지 못하므로 데이터워드를 만들지 못했다. 4) r0와 a3비트에 오류가 생겨 해당 비트를 바꾸었다. 수신된 코드워드는 00110이다. 신드롬은 0이다. 데이터워드 0011이 수신자에 의해 만들어졌다. 잘못된 신드롬 값 때문에 잘못된 데이터워드가 만들어졌다는 것에 유의하라. 단순 패리티 확인 코드는 짝수 개의 오류가 발생하면 검출해 내지 못한다. 오류가 서로를 상쇄해서 신드롬 값이 0이 된다. 5) a3, a2, a1의 세 비트가 오류가 발생하여 값이 바뀌었다. 수신된 코드워드는 01011이다. 신드롬은 1이다. 데이터워드는 생성되지 않았다. 이는 단일 비트 오류를 검출토록 보장된 단순 패리티 확인 코드는 홀수 개의 오류도 검출해 내는 것을 보여준다. 1.#

10.3 순환 코드 순환코드(cyclic code) 하나의 특별한 성질이 있는 선형 블록 코드 코드워드를 순환시켜 다른 코드워드를 얻음 예를 들어, 1011000이 코드워드이면 1개의 비트를 왼쪽으로 이동시켜 얻는 코드워드 0110001도 코드워드 맨 오른쪽 등식에서는 첫 번째 워드의 마지막 비트가 두 번째 워드의 첫 번째 비트가 됨 1.#

10.3.1 순환 중복 검사 순환 중복 검사(CRC, cyclic redundancy check): LAN이나 WAN에서 널리 사용 표 10.3: CRC 코드 C(7,4) 1.#

10.3.1 순환 중복 검사 그림 10.5: CRC 부호화기와 복호화기 1.#

10.3.1 순환 중복 검사 그림 10.6: CRC 부호화기의 나눗셈 1.#

10.3.1 순환 중복 검사 그림 10.7: 두 가지 경우의 CRC 복호기의 나눗셈 1.#

10.3.2 다항식 다항식(polynomial) 0과 1의 패턴은 계수 0과 1의 다항식으로 나타낼 수 있음 각 항의 지수가 각 비트의 자리수를 나타냄 계수는 비트의 값 그림 10.8: 2진 워드를 표시하는 다항식 1.#

10.3.3 다항식을 사용하는 순환 코드 부호화기 그림 10.9: 다항식을 사용하는 CRC 나눗셈 1.#

10.3.4 순환 코드 분석 1.#

10.3.4 순환 코드 분석 예제 10.8: 다음 중 단일 비트 오류를 검출하는 것을 보장하는 g(x)는? 각 경우 검출할 수 없는 오류는? x +1 X3 1 1.#

10.3.4 순환 코드 분석 예제 10.8(계속): 해답 어떤 xi도 x + 1로 나누어 떨어지지 않는다. 다시 말하면 xi/(x + 1)은 항상 나머지가 있다. 그러므로 증상은 0이 아니다. 임의의 단일 비트 오류를 검출할 수 있다. 만일 i가 3 이상이면 xi는 g(x)로 나누어 떨어진다. xi/x3의 나머지는 0이며 수신자는 오류가 있음에도 불구하고 잘못되어 오류가 없다고 믿게 된다. 이 경우에 손상된 비트는 4 또는 그 이상의 위치이어야 한다. 1부터 3까지의 위치에 발생한 단일 비트 오류는 모두 검출할 수 있다. 모든 i의 값에 대해 xi는 g(x)로 나누어 떨어진다. 단일 비트 오류를 검출할 수 없다. 더욱이 이 g(x)는 데이터워드에 n－k개의 0을 더하여 코드워드를 만든 것이기 때문에 쓸모가 없다. 1.#

10.3.4 순환 코드 분석 그림 10.10: 다항식을 사용한 두 분리된 단일 비트 오류의 표시 1.#

10.3.4 순환 코드 분석 예제 10.9: 다음 생성기의 단일 비트 오류와 분리된 두 개의 오류에 대한 관계를 확인하라. a. x + 1 b. x4 + 1 c. x7 + x6 + 1 d. x15 + x14 + 1 해답 생성기로서는 매우 적절치 못하다. 서로 이웃하는 두 개의 오류를 검출할 수 없다. 이 생성기는 4개의 비트만큼 떨어진 두 개의 오류를 검출할 수 없다. 두 개의 오류는 어디든지 생길 수 있는데 그 거리가 4라면 검출할 수 없다 이 생성기는 이런 목적에 적절하다. 이 다항식은 t가 32,768보다 작은 xt + 1 형식의 오류를 나누어 떨어지게 하지 못한다. 이는 서로 이웃하거나 최대 32,768비트만큼 떨어진 두 개의 오류는 생성기에 의해 검출된다는 것을 말한다. 1.#

10.3.4 순환 코드 분석 1.#

10.3.4 순환 코드 분석 예제 10.10: 다음 생성기가 다양한 길이의 폭주 오류를 검출하는 안정도를 찾으라. 해답 a. x6 + 1 b. x18 + x7 + x + 1 c. x32 + x23 + x7 + 1 해답 이 생성기는 길이가 6비트 이하의 모든 폭주 오류를 찾아낸다. 길이 7인 폭주 오류는 100개 중 3개가 검출되지 않을 것이며 길이가 8 이상인 폭주 오류는 1000개 중 16개가 검출되지 않을 것이다. 이 생성기는 길이가 18비트 이하의 모든 폭주 오류를 찾아낸다. 길이 18인 폭주 오류는 100 만 개 중 8개가 검출되지 않을 것이며 길이가 19 이상인 폭주 오류는 100만 개 중 4개가 검출되지 않을 것이다. 이 생성기는 길이가 32비트 이하의 모든 폭주 오류를 찾아낸다. 길이 33인 폭주 오류는 100억 개 중 5개가 검출되지 않을 것이며 길이가 33 이상인 폭주 오류는 100억 개 중 3개가 검출되지 않을 것이다. 1.#

10.3.4 순환 코드 분석 1.#

10.3.4 순환 코드 분석 표 10.4: 표준 다항식 1.#

10.3.5 순환 코드의 이점 순환 코드의 이점 단일 비트, 두 비트, 홀수 개의 비트 및 폭주 오류를 검출하는 데 우수 하드웨어나 소프트웨어로 쉽게 구현 하드웨어로 구현하면 특히 빠름 이로 인해 많은 네트워크에서 순환 코드가 사용 1.#

10.3.7 하드웨어 구현 그림 10.11: CRC 나눗셈을 위한 하드웨어 설계 1.#

10.3.7 하드웨어 구현 그림 10.12: CRC 부호화기의 나눗셈에 대한 시뮬레이션 1.#

10.3.7 하드웨어 구현 그림 10.13: 이동 레지스터를 사용한 CRC 부호화기 설계 1.#

10.3.7 하드웨어 구현 그림 10.14: CRC 코드의 부호화기와 복호기의 일반적 설계 1.#

10.4 검사합 검사합 어떠한 길이의 메시지에도 적용시킬 수 있는 오류 검출 기법 인터넷에서 검사합 기술은 대부분 데이터 링크 계층 보다는 네트워크와 전송 계층에서 사용됨 1.#

10.4 검사합 그림 10.15: 검사합 1.#

10.4.1 개념 예제 10.11: 우리 데이터가 5개의 4비트 수라고 하자. 이 숫자들을 전송하는 것 이외에 전체 숫자의 합도 전송한다. 예를 들면 숫자들이 (7, 11, 12, 0, 6)이라면 우리는 (7, 11, 12, 0, 6, 36)을 전송하는 데 36은 원래 숫자들의 합이다. 수신자는 5개의 숫자를 합하여 그 결과를 합과 비교한다. 두 값이 같으면 수신자는 오류가 없는 것으로 가정하여 5개의 숫자를 받아들이고 합은 버린다. 그렇지 않으면 오류가 있는 것이어서 데이터를 받아들이지 않는다. 1.#

10.4.1 개념 1의 보수 0 부터 2n-1 사이의 부호 없는 수를 n 비트만 사용하여 나타냄 1.#

10.4.1 개념 예제 10.12: 이전의 예에서, 십진수 36은 2진수로 (100100)2 이다. 아래와 같이 오른쪽 4비트와 나머지 왼쪽 비트를 더해서 4비트의 숫자로 변환한다. 해답: 합으로 36을 전송하는 대신에 6을 전송할 수 있다. (7, 11, 12, 0, 6, 6) 수신자는 처음 5개의 숫자에 1의 보수 연산을 추가할 수 있다. 만약 결과가 6이라면, 숫자들은 받아들여지고, 그렇지 않으면, 거부된다. 1.#

10.4.1 개념 예제 10.13: 예제 10.12에서의 검사합의 개념을 사용해보자. 송신자는 다섯 개의 모든 숫자를 더한 수에 1의 보수화를 해서 6이라는 값을 얻는다. 송신자는 그다음 결과 값에 1의 보수화를 해서 검사합 9를 얻는다. 이는 15 - 6이다. 참고로 6 = (0110)2 이고 9 = (1001)2 이다. 이 둘은 서로의 보수 관계이다. 송신자는 5개의 숫자와 검사합 값을 전송 한다.(7, 11, 12, 0, 6, 9) 만약 전송 시 데이터의 변형이 없다면, 수신자는 (7, 11, 12, 0, 6, 9)을 전송 받고, 이 수 들의 1의 보수인 15를 얻게 된다. 송신자는 0을 얻기 위해 보수화 한다. 이를 통해 데이터에 오류가 발생되지 않았다는 것을 알 수 있다. 그림 10.16에서 이에 대한 과정을 보여주고 있다. 1.#

10.4.1 개념 그림 10.16: 예제 10.13 1.#

10.4.1 개념 표 10.5: 통상적인 검사합 계산 절차 1.#

10.4.1 개념 그림 10.17: 통상적인 검사합 계산 알고리즘 1.#

10.4.2 검사합에 대한 다른 접근법 그림 10.18: 8 비트 플래처 검사합 계산 알고리즘 1.#

10.4.2 검사합에 대한 다른 접근법 그림 10.19: 애들러 검사합 계산 알고리즘 1.#

10.5 전향 오류 정정 오류 발생으로 인한 재전송과 패킷 손실은 실시간 멀티미디어 전송에서는 유용하지 않음 오류나 복사 패킷을 즉시 정정하여야 함 전향 오류 정정(FEC, forward error correction) 기술이라 불리는 몇몇의 방식은 이러한 상황에 맞게 설계되고 사용됨 1.#

10.5.1 해밍 거리 이용 t개의 오류를 검출하기 위해서는 dmin = 2t + 1이 필요 그림 10.20: 오류 수정을 위한 해밍 거리 1.#

10.5.2 XOR 이용 배타적 논리합(XOR)의 특성을 사용하는 방법 1.#

10.5.3 청크 끼워넣기 그림 10.21: 끼워넣기 1.#

10.5.4 해밍 거리와 끼워 넣기 결합 해밍 거리와 끼워 넣기는 결합 t 비트의 오류를 수정한 n 비트의 패킷을 생성 m 행에 끼워 넣고, 열×열로 비트를 전송 이 방법으로 폭주오류와 m×t 비트 오류까지 자동으로 수정할 수 있음 1.#

10.5.5 고해상도와 저해상도 패킷의 복합 그림 10.22: 고해상도와 저해상도 패킷의 복합 1.#

10.6 요약 Q & A

연습문제 풀이해서 Report로 다음 주까지(일주일 후) 제출해 주세요! 알림