Chapter 10
오류검출과 오류정정
10장 오류검출과 오류정정
10.1 소개
10.2 블록 코딩
10.3 순환 코드
10.4 검사합
10.5 순방향 오류 정정
10.1 소개
오류의 종류
단일비트 오류(single-bit error): 주어진 데이터 단위중 오직 하나의 비트만 이 1에서 0 또는 0에서 1로 변경되는 오류
폭주 오류(burst error): 데이터 단위에서 2개 이상의 연속적인 비트들이 1 에서 0 또는 0에서 1로 바뀌는 오류
단일비트 오류와 폭주 오류
중복
중복(redundancy)
1) 오류를 검출하거나 정정하는 것의 중심 개념
2) 오류를 검출하거나 정정하기 위해서는 데이터 이외에 추가 비트들을 보내 야 하는데, 이 중복 비트는 송신자에 의해 첨가되며 수신자가 제거함 3) 중복 비트들로 인해 수신자는 오류를 찾아내거나 정정할 수 있음
검출 대 정정
오류 검출
1) 오류가 생겼는지 알아내는 것
2) 간단히 오류가 있느냐 없느냐만 확인 3) 오류가 몇 개인지 조차 알 필요가 없음
오류 정정
1) 정확하게 몇 비트가 잘못 되었는지, 어디가 잘못 되었는지를 알아내는 것
부호화
송신자는 중복 비트와 실제 데이터 비트들 사이에 어떤 관련 을 짓게 하는 과정을 통해 중복 비트들을 보냄
수신자는 이 두 종류의 비트들 사이의 관계를 확인하여 오류
를 검출하거나 정정함
10.2 블록 코딩
블록 코딩
1) 데이터워드(dataword)라고 불리는 k 비트의 블록으로 메시지를 나눔 2) 각 블록에 r개의 중복 비트들을 더하여 길이 n= k + r이 되도록 함 3) 결과로 얻는 n비트 블록들은 코드워드(codeword)라고 불림
블록 코딩의 오류 검색 과정
예제
k = 2이고 n = 3인 경우, 오류 검출을 위한 데이터워드와 코드워드의 예
송신자가 데이터워드 01을 011로 코딩하여 수신자에게 보
낸 경우
예제 (계속):
1) 수신자가 011을 수신. 이는 유효 코드이므로 수신자는 이로부터 데이터워 드 01을 추출한다.
2) 코드워드가 전송 도중 손상되어 111이 수신. 이는 유효 코드가 아니므로 버려진다.
3) 코드워드가 전송 도중 손상되어 000이 수신. 이는 유효 코드이다. 수신자 는 이로부터 부정확한 데이터워드인 00을 추출한다. 두 개 비트가 손상되 어 오류를 찾지 못한다.
해밍 거리
해밍 거리(Hamming distance)
1) 두 개의 같은 크기의 워드간에 차이가 나는 비트의 개수 2) 두 워드에 XOR 연산을 해서 얻은 결과 값의 1의 개수
예제 : 두 워드들 사이의 해밍 거리
1) 000 ⊕ 011 = 011(두 개의 1)이기 때문에, d(000, 011) = 2
2) 10101 ⊕ 11110 = 01011(3개의 1)이기 때문에, d(10101, 11110) = 3
최소 해밍 거리
최소 해밍 거리(minimum Hamming distance)
1) 모든 가능한 코드워드 쌍들 사이의 가장 작은 해밍 거리
2) 앞 코드워드 표의 최소 해밍 거리는 2. 따라서 단일 비트 오류만 검출할 수 있다.
3) 해밍거리
d
min= 4인 코드인 경우, 세 개까지의 오류(d = s + 1 or s =선형 블록 코드
선형 블록 코드(Linear block code): 두 유효한 코드워드 를 XOR 연산을 하면 다른 유효한 코드워드를 생성하는 코 드
패리티 검사 코드
1) 선형 블록 코드
2) k비트 데이터워드를 n=k+1이 되도록 n비트 코드워드로 바꾸는 것
3) 추가된 비트는 패리티 비트라고 불리며 전체 코드워드의 1의 개수가 짝수 가 되도록 선정
4) 최소 해밍 거리 dmin=2이며, 이는 코드가 단일비트 오류 검출코드라는 것 을 의미
단순 패리티 검사 코드 C(5,4)
단순 패리티 검사 코드의 부호화기와 복호기
10.3 순환 코드
순환코드(cyclic code)
1) 하나의 특별한 성질이 있는 선형 블록 코드 2) 코드워드를 순환시켜 다른 코드워드를 얻음
3) 예를 들어, 1011000이 코드워드이면 1개의 비트를 왼쪽으로 이동시켜 얻 는 코드워드 0110001도 코드워드
4) 맨 오른쪽 등식에서는 첫 번째 워드의 마지막 비트가 두 번째 워드의 첫 번째 비트가 됨
순환 중복 검사
순환 중복 검사(CRC, cyclic redundancy check):
LAN이나 WAN에서 널리 사용
CRC 코드 C(7,4)
CRC 부호화기와 복호화기
CRC 부호화기의 나눗셈
두 가지 경우의 CRC 복호기의 나눗셈
다항식
다항식(polynomial)
1) 0과 1의 패턴은 계수 0과 1의 다항식으로 나타낼 수 있음 2) 각 항의 지수가 각 비트의 자리수를 나타냄
3) 계수는 비트의 값
2진 워드를 표시하는 다항식
다항식을 사용하는 순환 코드 부호화기
표준 다항식
순환 코드의 이점
순환 코드의 이점
1) 단일 비트, 두 비트, 홀수 개의 비트 및 폭주 오류를 검출하는데 우수 2) 하드웨어나 소프트웨어로 쉽게 구현
3) 하드웨어로 구현하면 특히 빠름
4) 이로 인해 많은 네트워크에서 순환 코드가 사용
10.4 검사합
검사합
1) 어떠한 길이의 메시지에도 적용시킬 수 있는 오류 검출 기법
2) 인터넷에서 검사합 기술은 대부분 네트워크 계층과 전송 계층에서 사용됨
검사합 계산 절차
검사합 계산 알고리즘
10.5 순방향 오류 정정
오류 발생으로 인한 재전송과 패킷 손실은 실시간 멀티미디 어 전송에서는 유용하지 않음
실시간 응용 경우, 오류 발생한 패킷은 즉시 정정되어야 함
순방향 오류 정정(FEC, forward error correction) 기
술이 이러한 상황에 사용됨
10.5 순방향 오류 정정 (계속)`
단일 비트 오류 정정
패리티 비트 이용
오류 정정은 잘못된 비트의 위치를 알아내는 것
7 비트의 ASCII 코드는 잘못된 비트 위치를 찾기 위해서 3-비트 중복비트 가 필요하다(000-111)?
10.5 순방향 오류 정정 (계속)`
중복 비트
주어진 데이터 비트(m 비트) 중에서 한 비트를 정정하기 위해 요구되는 중 복비트 수(r) 를 알아야 한다
10.5 순방향 오류 정정 (계속)`
전송할 수 있는 비트의 전체 수가 m + r이면 r은 적어도 다 음 조건을 만족해야 한다
2
r m + r + 1
예) 7 비트(ASCII) m에 대해 가장 적은 r의 값은 4이다
2
4 7 + 4 + 1
10.5 순방향 오류 정정 (계속)`
해밍 코드
R.W. Hamming에 의해 개발
Hamming 코드에서 중복 비트의 위치
2 1 4
8
10.5 순방향 오류 정정 (계속)`
코드의 구성
연산방법
1의 값을 가진 비트의 위치값을 이진수로 Exclusive-OR한다.
1
10.5 순방향 오류 정정`(계속)
수신측 오류 검출 및 정정 방법
오류가 없는 경우
수신한 데이터내의 1의 값을 갖는 비트의 위치값을 계산
10.5 순방향 오류 정정 (계속)`
오류가 발생한 경우
1
