osp.chungbuk.ac.kr/2012년 강의자료

Presentation on theme: "osp.chungbuk.ac.kr/2012년 강의자료"— Presentation transcript:

1 osp.chungbuk.ac.kr/2012년 강의자료
정보 및 부호 이론 ’12-1 학기 담당교수 : 이봉운 osp.chungbuk.ac.kr/2012년 강의자료 ID: guest, PW: lee

2 강의 구성 1장 확률과 랜덤변수 2장 정보공학과 통신 시스템 3장 채널코딩 4장 가변길이 코드 5장 상관관계와 자료압축
1장 확률과 랜덤변수 2장 정보공학과 통신 시스템 3장 채널코딩 4장 가변길이 코드 5장 상관관계와 자료압축 6장 정보의 특성과 엔트로피 7장 소스코딩의 한계 8장 채널의 특성과 상호정보 9장 채널용량 10장 Shannon의 정리 2

3 제3장 채널코딩 3.1 채널코딩의 필요성 3.2 패리티검사 3.3 독립오류와 백색잡음 3.4 메시지의 재전송
제3장 채널코딩 3.1 채널코딩의 필요성 3.2 패리티검사 3.3 독립오류와 백색잡음 3.4 메시지의 재전송 3.5 다발오류 검출 코드 3.6 가중치 코드 3.7 간단한 오류정정코드 3.8 Hamming 오류정정코드 3.9 채널코딩의 기하학적 접근 3

4 3.1 채널코딩의 필요성-1 채널에서의 잡음 채널코딩 모든 채널은 신호 전송 시 잡음의 영향을 받음: 오류 유발
오류 보상을 위한 특별한 코드체계가 수신측에서 필요 채널코딩 채널 잡음에 의한 오류를 제어할 수 있는 코드체계의 조작 오류검출코드 (error-detection code) 오류의 발생 여부만을 판단  재전송(retransmission) 요구 반복의 횟수가 한정 : 초과 시에 해당 메시지를 포기 재전송 요구가 불합리한 경우가 발생 위성통신 : 전송시간이 신호처리 속도에 비해 매우 김 오류를 검출하여 재전송을 요구하는 것은 매우 비효율적 오류정정코드 (error-correction code) 오류의 발생 여부 판단 및 발생된 오류를 독립적으로 수정 오류의 발생위치를 정확히 알아내는 것이 핵심

5 3.1 채널코딩의 필요성-2 오류제어 체계의 중요성 시스템의 신뢰성 유지 및 성능의 향상에 필요
신뢰성이 떨어지는 시스템에서 오류가 발생되는 단점을 보상 오류의 검출 또는 정정으로 신뢰성을 제고 H/W : 고속으로 동작하나 고비용 S/W : 저속으로 동작하나, 저렴하고 융통성을 제공 시스템의 유지보수(maintenance)에 필수적 오류검출 체계를 갖추지 않은 대형 디지털 시스템 유지보수가 거의 불가능 오류검출 체계를 갖춘 대형 디지털 시스템 시스템의 입력에 일정한 형태의 2진열을 인가 각 블록별로 오류의 발생 여부를 검사: 오류의 발생 부위를 진단 대형 디지털 시스템의 고장 부분을 용이하게 발견

6 3.2 패리티검사-1 가장 간단한 오류검출 방법 단순 패리티검사를 위한 블록의 형성
전체 2진 메시지를 일정한 길이로 구분 : 블록(block)을 형성 각 블록이 짝수 개의 ‘1’을 포함하도록 패리티 비트를 부여 짝수 패리티(even parity) 수신 측에서 짝수 패리티 비트를 검출 패리티검사(parity check) 단순 패리티검사를 위한 블록의 형성 전체 메시지를 길이가 (n-1) 비트인 블록으로 구분 각 블록의 n 번째 비트에 패리티검사 비트를 추가

7 3.2 패리티검사-2 오류발생 확률 단순 패리티검사 : 홀수 개의 오류만을 검출
짝수 개의 오류 검출 불가 블록 내의 각 비트에서 오류가 발생할 확률 : p 단일 비트의 오류가 발생할 확률 : 각 비트는 서로 독립적 2개 비트의 오류가 발생할 확률 단일오류발생확률이 매우 작을 때 : 2개 비트 오류확률은 거의 무시 단일오류만 검출해도 상당히 의미 있는 오류제어 수행 가능

8 3.2 패리티검사-3 리던던시(redundancy) 정의: 전체 비트 수와 순수한 정보 비트 수의 비
단순 패리티검사의 리던던시 리던던시를 줄이기 위해 블록의 길이 n을 증가 오류검출 능력 향상을 위해 가능한 한 짧은 블록의 길이가 필요 블록 내에서 2비트 이상의 오류 검출 패리티검사 비트 증가  리던던시가 증가

9 3.2 패리티검사-4 리던던시(계속) 다중 패리티검사를 위한 블록의 형성 리던던시의 증가 리던던시의 감소
전송된 블록에서 순수한 정보의 비율이 저하 오류검출 능력은 향상 : 시스템의 신뢰성이 개선 리던던시의 감소 시스템의 신뢰성이 감소 블록 내의 정보율이 증가 오류검출코드의 리던던시 결정: 공학적 상보성(trade-off) 다중 패리티검사를 위한 블록의 형성

10 3.3 독립오류와 백색잡음-1 채널잡음에 의한 디지털 정보의 오류 특성 유색잡음(colored noise)
블록 내의 각 비트는 동일한 오류확률 p 를 가짐 블록 내의 각 비트 사이에는 독립성이 유지 이러한 오류 특성을 유발하는 잡음 : 백색잡음(white noise) 유색잡음(colored noise) 각 비트의 오류확률이 상이 각 비트는 유관하여 독립이 아님 다발성 오류(burst error)를 유발 각 비트에서 백색잡음의 오류확률

11 3.3 독립오류와 백색잡음-2 비트의 오류 확률 하나의 블록(n 비트)이 오류 없이 전송될 확률 :
단일 오류(1 bit error)가 발생할 확률 n비트 중 k비트에서 오류가 발생할 확률 : 짝수 개(0, 2, 4, …)의 오류가 발생할 확률 홀수 개(1, 3, 5, …)의 오류가 발생할 확률

12 3.3 독립오류와 백색잡음-3 비트의 오류 확률(계속) 예제1 : n=8, p=0.01
단일 패리티검사에 의해 검출되지 않는 오류가 발생할 확률 홀수 개의 모든 오류는 검출 가능 짝수 개의 모든 오류는 검출 불가 : 무 오류 발생 확률 제외 예제1 : n=8, p=0.01 무 오류 전송확률 : 단일오류 발생확률 검출되지 않은 오류의 발생확률 오류의 발생확률을 주도

13 3.3 독립오류와 백색잡음-4 예제2 : 검출되지 않은 오류의 발생확률 확률 식의 처음 두 항에 의해 지배
확률 값이 10-3 보다 작게 하기 위해 필요한 블록의 길이는?

14 3.4 메시지의 재전송 재전송(retransmission), 재처리(reprocessing)
3.4 메시지의 재전송 재전송(retransmission), 재처리(reprocessing) 오류검출코드를 사용하는 시스템에서 전송 중 오류가 발생할 때 요구 예 : 자기테이프 판독장치 판독 중 패리티검사에서 오류가 검출되면 재판독을 요청 오류모델(error model)에 의해 재판독의 수가 결정 예 : 자기드럼(magnetic drum) 과거에 컴퓨터 기억장치로 흔히 사용 블록의 모든 비트를 포함하는 레지스터의 논리합을 계산 드럼 상의 최종 블록에 저장 저장이 끝나면 곧바로 드럼을 판독하여 모든 정보의 기억을 검사 차후에 드럼이 판독될 때 다시 모든 블록의 패리티를 검사 논리합이 ‘0’이 되는가를 확인 : ‘0’이 되지 않으면 재판독을 요청 예 : 유선 데이터통신이나 이동통신 시스템 일종의 오류검출코드를 사용 수신기는 오류 발생여부를 검사 : 송신기에 재전송을 요구 재전송 횟수를 계수기로 계수 : 반복 횟수가 초과되면 해당 블록을 포기

15 3.5 다발오류 검출 코드-1 다발성 오류(burst error) 워드(word) 단위 패리티검사
3.5 다발오류 검출 코드-1 다발성 오류(burst error) 비트오류가 독립적이지 않고 서로 유관하게 발생 다발성 오류의 발생 원인 천둥 및 번개와 같은 전파환경의 변화 전원공급기의 성능 변화에 의한 통신시스템의 이상 저장시스템의 자성체 표면에 형성된 흠(flake) 워드(word) 단위 패리티검사 다발오류 검출에 사용 다발오류의 최대길이 : L 비트(레지스터 길이와 일치) 전송할 메시지를 L 비트의 길이로 구분 구분된 각 블록을 워드(word)로 취급 : 패리티 워드를 부여 수신측에서의 패리티검사 비트 단위 패리티검사 : 독립오류가 검출 워드 단위 패리티검사 : 다발오류가 검출

16 3.5 다발오류 검출 코드-2 다발오류 검출을 위한 워드 단위 패리티검사 각 워드를 차례로 전개 행 단위 패리티검사
3.5 다발오류 검출 코드-2 다발오류 검출을 위한 워드 단위 패리티검사 각 워드를 차례로 전개 행(row) 단위 패리티검사와 열(column) 단위 패리티검사 수행 행 단위 패리티검사 독립오류 검출을 위해 수행되는 비트 단위 검사 열 단위 패리티검사 다발오류 검출을 위해 수행되는 워드 단위의 검사

17 3.5 다발오류 검출 코드-3 다발오류 검출을 위한 워드 단위 패리티검사(계속)
3.5 다발오류 검출 코드-3 다발오류 검출을 위한 워드 단위 패리티검사(계속) 오류가 워드의 끝부분에서 다음 워드 첫 부분까지 존재할 때 다발오류의 길이 : 0  k  L 다발오류는 워드 단위의 패리티검사에 의해 검출 다발오류가 검출되면 수신측은 재전송을 요구 독립오류와 마찬가지로 오류가 발생된 워드의 위치판단 불가 단지 다발오류의 발생여부만을 검출 패리티검사에 참여한 모든 워드에 대해 재전송을 요구 예제3 : 전송할 메시지 “Information Eng. 1966” 패리티검사 비트와 패리티검사 워드에 대한 코딩과정을 수행 5번째 워드 뒷부분과 6번째 워드 앞부분에서 다발오류 발생 검출과정을 설명 메시지는 8진 ASCII 코드로의 전송을 가정

18 예제3 메시지의 부호화-1 (1) 짝수 패리티검사 코딩

19 예제3 메시지의 부호화-2 (2) 메시지의 패리티검사 다발오류 발생

20 예제3 메시지의 부호화-3 (3) 8진 ASCII 코드로 전송되는 메시지 더미 문자(dummy characters)

21 3.6 가중치 코드(weighted codes)-1
운용자의 조작 실수로 발생되는 오류의 경우 심벌을 빠뜨리거나, 불필요한 심벌을 삽입 심벌을 거꾸로 입력 메시지의 왜곡 및 시스템의 동기에도 치명적인 손상을 유발 예 : 67 → 76, 667 → 677 문자‘O’와 숫자 ‘0’, 문자‘I’와 숫자 ‘1’, 문자‘B’와 숫자 ‘8’ 영문자와 숫자만을 사용하는 시스템 소스 알파벳을 사용 26개의 영문자, 1개의 공백(space), 10개의 10진 숫자들로 구성 심볼의 수 : = 37  37 : 소수(prime number)

22 3.6 가중치 코드(weighted codes)-2
영문자와 숫자만을 사용하는 시스템에서의 오류검출 체계 가중치 코드의 생성 37이 소수인 특성을 이용 메시지를 일정한 길이의 문자열(character string)로 구분 각 문자열의 최하위에 검사문자(check character) 를 부여 각 문자는 주어진 소스알파벳 순서에 따라 코딩 문자의 가중치 부여(1,2, …, n) : 문자열의 최하위로부터 시작 하나의 문자열에 대하여 가중합(weighted sum)을 산출 가중합이 ‘모듈로(modulo)-37’이 되도록 검사문자 를추가 모듈로-37 : 37로 나누어 떨어지는 것을 의미

23 3.6 가중치 코드(weighted codes)-3
영문자/숫자만을 사용하는 시스템에서 오류검출 체계(계속) 가중치 코드의 생성(계속) 검사문자가 공백(SP)인 경우 검사문자가 없는 것이 아니라 코드 ’10’을 갖는 검사문자로 취급 수신된 가중치 코드의 복구 문자열 별로 다시 가중합을 구하여 검사 모듈로-37이 성립되는가를 확인 성립되지 않으면 오류가 발생하였다고 판단 재전송/재처리 요구

24 그림3.5 가중치 코드의 생성 문자의 코딩

25 3.6 가중치 코드-4 예제4 : 문자열 NO 557에 대한 가중치 코드 적용 1 2 7 3 5 4 10 6 25 24 v O
3.6 가중치 코드-4 예제4 : 문자열 NO 557에 대한 가중치 코드 적용 가중합과 검사문자를 구하고 전송되는 메시지를 작성하라. 문자열의 길이 : n = 7 = 6 + 1(검사문자) 검사문자를 n 로 지정 전송되는 메시지 : ‘NO 557Q’ 1 2 7 3 5 4 10 6 25 24 v O N

26 3.6 가중치 코드-5 예제4: 문자열 NO 557에 대한 가중치 코드 적용(계속)
3.6 가중치 코드-5 예제4: 문자열 NO 557에 대한 가중치 코드 적용(계속) 문자열이 ‘NO 577Q’ 로 잘못 전송된 경우의 오류검출 과정 수신된 메시지는 오류를 포함

27 3.6 가중치 코드-6 문자열의 k번째 문자와 (k+1)문자가 서로 바뀐 경우 원래의 가중합 : 뒤바뀐 문자열의 가중합
3.6 가중치 코드-6 문자열의 k번째 문자와 (k+1)문자가 서로 바뀐 경우 원래의 가중합 : 뒤바뀐 문자열의 가중합 동일문자의 경우(sk = sk+1) 가중합의 차는 0 (mod-37)이므로 오류 미 발생 문자열이 길어지면 가중합을 구하는 것이 용이하지 않음 다수의 곱셈 수행으로 긴 연산시간이 필요 ‘Progressive digiting’ 알고리즘 사용 문자열의 가중합을 구하는 쉽고도 간단한 방법

28 3.6 가중치 코드-7 Progressive digiting’ 알고리즘 문자열 합 합의 합
3.6 가중치 코드-7 Progressive digiting’ 알고리즘 문자열의 최상위 문자로부터 차례로 나열 : 첫 번째 열을 구성 차 하위의 문자를 차례로 더하여 두 번째 열(합)을 형성 차차 하위의 문자를 차례로 더하여 세 번째 열(합)을 형성 장점 : 모든 과정이 덧셈이며 알고리즘이 체계적인 순환과정 기계적인 처리에 매우 유리 예 : 문자열 ‘wxyz’에 대한 progressive digiting 과정 문자열 합 합의 합 W W W X W+X W+X Y W+X+Y W+2X+Y Z W+X+Y+Z W+3X+2Y+Z

29 3.6 가중치 코드-8 Progressive digiting’ 알고리즘(계속) 문자열 합 합의 합
3.6 가중치 코드-8 Progressive digiting’ 알고리즘(계속) 예제4에 적용 : NO 557Q 마지막 원소인 ‘444’는 전송 메시지 ‘NO 557Q’의 가중합 Modulo-37을 만족 : 전송 중에 오류가 없음을 표시 문자열 합 합의 합 N= O= SP= 5= 5= 7= Q=

30 전송되는 메시지 : ‘WEIGHTED CODEY’
3.6 가중치 코드-9 예제5:“WEIGHTED CODE’에 대한 progressive digiting 알고리즘 문자열 합 합의 합 W= E= I= G= H= T= E= D= SP= C= O= D= E= n=? 238+n n 전송되는 메시지 : ‘WEIGHTED CODEY’

31 3.6 가중치 코드-10 ISBN(Internation Standard Book Number)
3.6 가중치 코드-10 ISBN(Internation Standard Book Number) 국제표준 도서번호 운용자의 작업과 결부되어 사용하는 또 다른 가중치 코드 운용자의 실수로 발생되는 오류를 검출하기 위한 코드체계 10자리 숫자코드로써 출판사에서 부여 ‘-’은 다른 위치에 표시 가능 : 위치는 중요하지 않음 모듈로-11을 사용 : S = {0, 1, 2, …, 9, X}  11개의 원소 예 : ISBN 발행국(미국) 검사번호 (mod-11) 출판사 (Prentice-Hall) 도서번호

32 3.6 가중치 코드-11 ISBN(계속) 숫자열 합 합의 합 예 : ISBN 89-353-0154-X의 오류 유무 판별
3.6 가중치 코드-11 ISBN(계속) 예 : ISBN X의 오류 유무 판별 마지막 원소인 ‘275’는 Modulo-11을 만족 : 275/11 = 25 오류가 없는 올바른 ISBN 숫자열 합 합의 합 X=

33 3.6 가중치 코드-12 예제6 : ISBN 0-07-041468-v에서 검사번호를 부여하라. 숫자열 합 합의 합 0 0 0
3.6 가중치 코드-12 예제6 : ISBN v에서 검사번호를 부여하라. ISBN 숫자열 합 합의 합 v =? v v+135

34 3장 과제-1 연습문제 3.1 연습문제 3.3 연습문제 3.7 (a) 연습문제 3.10 (a) 연습문제 3.14 (a)

35 3.7 간단한 오류정정코드-1 오류정정코드 수신된 메시지로부터 직접 오류를 수정/복원하는 코드체계
3.7 간단한 오류정정코드-1 오류정정코드 수신된 메시지로부터 직접 오류를 수정/복원하는 코드체계 재전송을 요구하거나, 확인신호(ACK)의 전송이 불필요 장거리 전송이나 고속 실시간 처리 시스템에서 널리 사용 삼중코드(triplication code) 가장 간단한 오류정정코드 모든 메시지를 3번씩 반복하여 전송 수신된 메시지 중 다수인 것을 선택 리던던시 : 매우 비효율적인 정보율을 제공

36 3.7 간단한 오류정정코드-2 사각형코드(rectangular code) 정보는 (m-1)  (n-1)의 배열을 형성
3.7 간단한 오류정정코드-2 사각형코드(rectangular code) 정보는 (m-1)  (n-1)의 배열을 형성 실제로 일렬로 늘어선 정보 비트를 차례로 배열 각 행(row) 별로 하나의 패리티검사 비트를 첨가 : m 비트 각 열(column) 별로 하나의 패리티검사 비트 첨가 : n 비트 최하단 우측의 패리티 비트는 배열의 형태유지에 사용 오류정정 과정에서는 불필요 • • • • m-1 n-1 : 정보 bits : 패리티 bits

37 3.7 간단한 오류정정코드-3 사각형코드(계속) 각 행과 열에서의 패리티검사는 독립적으로 수행
3.7 간단한 오류정정코드-3 사각형코드(계속) 각 행과 열에서의 패리티검사는 독립적으로 수행 단일오류가 발생되면 하나의 행과 하나의 열에서 실패로 표시 패리티검사에서 홀수 패리티를 검출 패리티검사가 실패한 열과 행이 만나는 위치에서 오류 발생 해당 위치의 비트를 교환하여 정정 : 0→1, 1→0 리던던시 블록이 정사각형에 가까울수록 리던던시는 작아짐 정사각형(square) 코드 : 최소의 리던던시 제공

38 3.7 간단한 오류정정코드-4 삼각형코드(triangular code) 사각형에서 대각선으로 패리티검사 비트를 배열
3.7 간단한 오류정정코드-4 삼각형코드(triangular code) 사각형에서 대각선으로 패리티검사 비트를 배열 정보 비트들이 하나씩 감소 : n-1, n-2, …, 2, 1 n개의 패리티검사 비트가 사용 단일 오류가 발생한 경우 패리티검사 비트 중 2개가 패리티검사에 실패 실패한 열과 행이 만나는 위치에서 오류 발생 : 해당 비트를 정정 • • • • n-1

39 3.7 간단한 오류정정코드-5 삼각형코드(계속) 리던던시 삼각형코드가 사각형코드보다 더 낮은 리던던시를 제공

40 3.7 간단한 오류정정코드-6 정육면체(cubic) 코드 3차원 코드 : 리던던시 감소 관점에서 2차원 코드보다 효율적
3.7 간단한 오류정정코드-6 정육면체(cubic) 코드 3차원 코드 : 리던던시 감소 관점에서 2차원 코드보다 효율적 정육면체 내부에 정보 비트가 차례로 배열 하나의 꼭지점에서 만나는 3 변 상에 패리티검사 비트를 배열 각 패리티 비트는 절단면 상의 모든 비트를 검사 단일 오류가 발생한 경우 3개의 절단면에 대해 3개의 패리티검사가 실패 실패한 3개의 절단면이 만나는 위치의 비트를 수정

41 표3.1 단일오류 정정코드의 효율성 비교 n이 증가함에 따라 육면체코드의 효율이 더욱 증가
표3.1 단일오류 정정코드의 효율성 비교 n이 증가함에 따라 육면체코드의 효율이 더욱 증가 육면체코드의 개념을 4차원으로 확장 가능 초과 리던던시 : 약 4/n3

42 3.7 간단한 오류정정코드-7 패리티검사 비트들의 배열 신드롬(징후: syndrome)
3.7 간단한 오류정정코드-7 패리티검사 비트들의 배열 일정한 규칙에 따라 배열되면 패리티검사는 신드롬을 발생 신드롬(징후: syndrome) 한 블록 내에서 오류의 발생위치를 표시하도록 설계된 2진수 성공: ‘0’, 실패: ‘1’ 을 부여 오류의 위치가 10진 표현에 의해 표시

43 Hamming (7, 4) 코드-1 부호화 과정 4개의 데이터 비트를 7개 비트의 코드로 전환 : 송신 코드어
패리티검사 비트 : c1, c2, c3 , 정보 비트 : w1, w2, w3 , w4 예제 : W = ( )을 부호화

44 Hamming (7, 4) 코드-2 패리티검사 방정식

45 Hamming (7, 4) 코드-3 패리티검사 행렬의 특성 신드롬(syndrome) : S R : 수신된 7비트 2진 코드어
C = R 이면 오류 없이 전송 : S = 0 C≠R 이면 오류가 전송 : S ≠0

46 Hamming (7, 4) 코드-4 복호화 과정 전송 오류가 없는 경우
R에 있는 3개의 패리티검사 비트를 제거하면 전송 비트를 복원 예 : R=( )

47 Hamming (7, 4) 코드-5 복호화 과정(계속) 전송 오류가 있는 경우 예 : R=( )

48 Hamming (7, 4) 코드-6 신드롬에 의한 오류 비트의 검출 E =(e1 e2 e3 e4 e5 e6 e7)
전송 중에 송신 코드어 C 에 추가된 단일 오류 잡음 코드어 ei → 1 : 잡음이 i 번째 비트를 바꿀 때 ei → 0 : 잡음이 i 번째 비트를 바꾸지 않을 때

49 Hamming (7, 4) 코드-7 신드롬에 의한 오류 비트의 검출(계속)
예: R=( )의 신드롬은 ST=(0 1 1) 3번째 비트에서 오류가 발생하므로 전송 코드어 C는

50 해밍 오류정정코드의 발생-1 패리티 검사 비트 수의 공식 비트들의 위치와 표기 송신 코드어의 순서 패리티 검사 비트
p : 패리티검사 비트의 수, d : 데이터 비트의 수 비트들의 위치와 표기 패리티 검사 비트 1, 2, 4, 8, 16, 32, …  P1, P2, P4, P8, P16 , P32 , … 로 표시 데이터 비트 3, 5, 6, 7, 9, 10, 11, …  D3, D5, D6, D7, D10, D11, … 로 표시 송신 코드어의 순서

51 해밍 오류정정코드의 발생-2 패리티 비트의 위치와 패리티 생성 영역 비트위치 1 2 3 4 5 6 7 8 9 10 11 12
기호 P1 P2 D3 P4 D5 D6 D7 P8 D9 D10 D11 D12 P1 영역  P2 영역 P4 영역 P8 영역

52 3.8 Hamming 오류정정코드-1 오류정정코드의 설계를 위한 대수학적 접근방법을 제공
단일오류를 정정할 수 있는 최적의 오류정정코드 백색잡음을 가정한 경우 한 블록에 대해 m개의 독립적인 패리티검사 수행의 경우 독립적 : 각각의 패리티검사가 완전히 중복되지 않도록 수행 종속적(dependent) 임의의 패리티검사를 결합하여 다른 패리티검사를 대신하는 경우 오류정정코드의 패리티검사위치 설정은 독립적 수행이 필요 예 : 검사1과 검사2를 결합하여 검사3를 대신  종속적 검사1 : 1, 2, 5, 7 검사2 : , 7, 8, 9 검사3 : 1, 2, , 9

53 3.8 Hamming 오류정정코드-2 Hamming 오류정정코드에서 m-비트 신드롬
각각의 패리티검사에 대해 성공이면 ‘0’, 실패이면 ‘1’을 부여 2m 개의 서로 다른 상태를 표시 n-비트 블록에서 발생된 단일오류를 정정하는 경우 (n+1) 개의 서로 다른 상태의 표시가 필요 오류 발생이 가능한 n개의 위치와 1개의 무 오류 상태를 포함 신드롬의 기본 조건 : Hamming 오류정정코드 기본조건을 정확히 만족하는 특수해로서의 코드체계 신드롬이 표현하는 10진수가 오류 발생의 위치를 표시 신드롬의 모든 비트가 ‘0’ 이면 무 오류 발생

54 표3.2 검사위치와 신드롬의 2진수 표현 제1의 패리티검사 제2의 패리티검사 제3의 패리티검사 제4의 패리티검사

55 3.8 Hamming 오류정정코드-3 7-비트 Hamming 코드의 예 : 메시지 블록 - - 1 - 0 1 1
메시지 블록 제1패리티: 1,3,5, 제2패리티: 2,3,6, 제3패리티: 4,5,6, 패리티비트 삽입 채널오류 발생 3비트 패리티 검사 오류 정정

56 3.8 Hamming 오류정정코드-4 Hamming 코드의 특성 인코딩 과정이나 디코딩 과정이 간단한 논리적 산술로 수행
H/W 구성이 모두 간단한 논리회로에 의해 실현 단일오류 정정을 위한 코드체계로 가장 널리 사용 신드롬은 오류 발생 위치를 직접 표시 전송된 메시지의 내용과는 무관 신드롬이 가르치는 위치에 무조건 ‘1’을 가산하여 정정

57 3.8 Hamming 오류정정코드-5 Hamming 코드의 리던던시 7-비트 Hamming 코드
3개의 패리티 검사 비트를 사용 리던던시는 7/4  비교적 큰 리던던시 패리티검사 비트 수를 조금만 증가해도 전체 비트 수는 크게 증가 패리티검사 비트의 증가로 리던던시를 현저히 감소 예 : 하나의 블록에 10개의 패리티검사를 사용하는 경우(m=10) n-비트 Hamming 코드의 리던던시

58 3.8 Hamming 오류정정코드-6 예제7 : 15-비트 Hamming 코드 메시지 블록: - -1-101-0110011
제1패리티: 1,3,5,7,9,11,13,  제2패리티: 2,3,6,7,10,11,14,  제3패리티: 4,5,6,7,12,13,14,  제4패리티: 8,9,10,11,12,13,14,15 

59 3.8 Hamming 오류정정코드-7 예제7: 15-비트 Hamming 코드(계속) 1+1=0

60 3.8 Hamming 오류정정코드-8 Hamming 코드의 등가코드(equivalent code)
비트 위치 교환에 의한 등가코드 블록 내의 각 비트의 위치를 서로 교환 완전히 다른 코드체계를 형성 단일오류를 정정하는 능력은 그대로 유지 변환관계는 다소 복잡 : 약간의 알고리즘과 메모리 필요 보수(complement)에 의한 등가코드 블록 내의 모든 비트에 0 ↔ 1을 교환 Hamming 코드체계와 거의 차별성이 없음 변환관계도 간단히 수행 꼬리검사코드(tail-check code) 가장 널리 사용되고 있는 Hamming 등가코드 블록 내 모든 패리티검사 비트를 최하위로 변경 상위에 정보 비트들이 놓이도록 위치를 교환

61 그림3.9 Hamming 코드의 위치교환 : 꼬리검사코드

62 3.8 Hamming 오류정정코드-9 꼬리검사코드(계속) 교환순열(interchange permutation)
코드화된 블록은 교환순열을 거쳐 꼬리검사코드로 변환 수신된 꼬리검사코드 블록을 교환순열을 통해 원 코드로 복원 장점 하나의 블록 내에 정보와 패리티 구분이 명확 각 블록의 앞 부분을 취함으로 정보를 추출 코드화된 메시지를 블록 별로 정렬(sorting)할 때 순수 정보 정렬과 일치 단점 : 추가적인 처리 부담이 발생 교환표(look-up table)를 위한 기억장치와 교환과정이 추가

63 3.9 채널코딩의 기하학적 접근-1 Hamming 오류정정코드 기하학적 접근(geometric approach) 방법
3.9 채널코딩의 기하학적 접근-1 Hamming 오류정정코드 대수학적 접근(algebraic approach) 방법 기하학적 접근(geometric approach) 방법 채널코딩의 개념을 n-차원 이진공간을 이용하여 표현 대수학적 접근에 의한 결과와 정확하게 일치 접근과정에서 채널코딩에 대한 새롭고 유용한 개념이 도입 정보이론을 다룰 때 필수적인 개념으로 사용 채널코딩의 기하학적 모델 n-비트 코드체계는 n-차원 이진공간(binary space)에 대응 2진 n-비트 코드는 n-차원의 한 점으로 표현 n-차원 2진 공간은 2n개의 꼭지점만을 보유 꼭지점들은 n-비트 코드체계에 존재하는 2n 개의 코드에 대응

64 3.9 채널코딩의 기하학적 접근-2 n-차원 2진공간과 n-비트 코드체계의 대응관계 n = 1 n = 2 n = 3
3.9 채널코딩의 기하학적 접근-2 n-차원 2진공간과 n-비트 코드체계의 대응관계 2진공간 내의 모든 정점(point)은 변(edge)에 의해 연결 변에 의해 연결된 두 정점: 1 비트 차이 1 비트의 오류 : 한 변의 이동을 의미 코드점(code point) n-차원 공간의 정점들 중 채널코드 체계에서 실제로 사용하는 정점 n = n = n = 3 001 000 111 011 010 00 100 110 01 11 10 1 101

65 3.9 채널코딩의 기하학적 접근-3 거리함수 (distance function) : Hamming 거리
3.9 채널코딩의 기하학적 접근-3 거리함수 (distance function) : Hamming 거리 채널코딩의 기하학적 접근에 매우 중요한 개념 거리함수는 2개의 코드점(code point) 사이에서 정의 2개의 코드점 사이를 천이할 때 지나게 되는 변의 최소수를 표시 두 코드점의 2진수 사이에 서로 다른 비트 수와 동일 두 2진수를 논리적으로 더했을 때 나타나는 ‘1’의 개수와 동일 동일한 코드점 사이의 거리함수는 0 x로부터 y까지의 거리함수 = y로부터 x까지의 거리함수 거리함수는 삼각부등식(triangle inequality)을 만족

66 3.9 채널코딩의 기하학적 접근-4 시스템의 최소거리 (minimum distance of a system)
3.9 채널코딩의 기하학적 접근-4 시스템의 최소거리 (minimum distance of a system) 시스템 내의 코드점 사이에 존재하는 최소의 Hamming 거리 시스템 : 채널코드에 사용되는 모든 코드점들의 집합 오류제어 능력의 척도로 사용 최소거리와 오류제어 능력의 관계 최소거리가 1 이상인 코드체계 각 코드점이 유일코드(unique code)를 표현 코드체계 내의 모든 코드점들이 최소 1 비트 이상 상이 각 코드점을 유일하게 구별 가능 최소거리가 2인 코드체계 : 단일오류검출 능력을 부여 최소거리가 3인 코드체계 : 단일오류정정 능력을 부여 이중오류검출에도 사용 최소거리가 4인 코드체계 : 단일오류정정 및 이중오류검출 최소거리가 5인 코드체계 : 이중오류정정 코드로 사용

67 표3.4 최소거리와 오류제어 능력

68 3.9 채널코딩의 기하학적 접근-5 구의 표면 (surface of a sphere)
3.9 채널코딩의 기하학적 접근-5 구의 표면 (surface of a sphere) 한 코드점으로부터 동일한 거리를 갖는 정점들의 집합 구의 중심 : 구의 표면에서 중심이 되는 코드점 구의 반경 : 구의 중심에서 설정된 동일한 거리 예: n-차원 코드점(0, 0, …, 0)을 중심으로 반경이 1인 구의 표면 원점으로부터 1개 만큼 변 떨어져 있는 모든 꼭지점들의 집합 2진열 내에 오직 하나의 ‘1’을 포함 구의 표면은 n 개의 원소로 구성 구의 체적 (volume of a sphere) 하나의 구에 포함되어 있는 모든 정점의 수 반경이 r 인 구 : 1개 중심 + (r -1) 개의 구각(shells) + 구의 표면 구의 체적 : 구의 중심, 구각 및 표면에 포함된 모든 정점의 수 공간의 체적 (volume of a space) 2진공간에 포함된 모든 정점의 수 : Vn = 2n

69 3.9 채널코딩의 기하학적 접근-6 예제8 : 3차원 2진공간 원점 (0,0,0)을 중심으로 한 반경이 1인 구의 표면은?
3.9 채널코딩의 기하학적 접근-6 예제8 : 3차원 2진공간 원점 (0,0,0)을 중심으로 한 반경이 1인 구의 표면은? 원점으로부터 한 변 떨어진 정점들의 집합 : 정점 (1,1,1)을 중심으로 반경이 1과 2인 구의 체적은? 반경이 1인 구의 체적 : (1,1,1)과 1 비트 다른 모든 정점의 수 반경이 2인 구의 체적 : 중심 + 반경이 1인 구각 + 구의 표면 3차원 공간의 체적은?

70 3.9 채널코딩의 기하학적 접근-7 예제9 : n차원 2진공간 원점을 중심으로 한 반경이 1인 구의 표면과 원소의 수
3.9 채널코딩의 기하학적 접근-7 예제9 : n차원 2진공간 원점을 중심으로 한 반경이 1인 구의 표면과 원소의 수 원점으로부터 한 변 떨어진 정점들의 집합 원점을 중심으로 반경이 1과 2인 구의 체적은? 반경이 1인 구의 체적 반경이 2인 구의 체적: 중심 + 반경이 1인 구각 + 구의 표면 임의의 정점을 중심으로 하고 반경이 k인 구의 체적: 단 k  n

71 3.9 채널코딩의 기하학적 접근-8 기하학적 접근방법에 의한 Hamming 코드 Hamming 코드 : 단일오류 정정코드
3.9 채널코딩의 기하학적 접근-8 기하학적 접근방법에 의한 Hamming 코드 Hamming 코드 : 단일오류 정정코드 시스템 내의 모든 코드점들은 최소거리 3을 유지 각 코드점을 중심으로 하는 반경 1인 구가 중첩되지 않아야 함 비 중첩 구들은 서로 다른 코드점들의 수만큼 존재 : 2k 블록 전체의 비트 수 : 단일오류 정정코드의 설계를 위한 기본관계식

72 3.9 채널코딩의 기하학적 접근-9 다중오류 정정코드체계 2중오류 정정코드 완전코드(perfect code)
3.9 채널코딩의 기하학적 접근-9 다중오류 정정코드체계 2중오류 정정코드 시스템 내의 모든 코드점들이 최소거리 5를 유지 각 코드점을 중심으로 하는 반경 2인 구가 중첩되지 않아야 함 n-비트 블록 내에 설정할 수 있는 정보 비트 수인 k의 상한값 제공 완전코드(perfect code) 코드점을 중심으로 각 구들이 n -차원 공간의 모든 정점(2n)을 포함 대칭성이 강하며, 효율적이고, 이론이 매우 간단 오류정정 능력이 커질수록 완전코드는 매우 희소 완전코드가 되기 위해서는 기본관계식의 등식부분을 만족 Hamming 코드는 완전코드의 한 예

73 3.9 채널코딩의 기하학적 접근-10 다중오류 정정코드체계(계속) 단일오류정정/이중오류검출을 동시에 실현하는 코드체계 설계
3.9 채널코딩의 기하학적 접근-10 다중오류 정정코드체계(계속) 단일오류정정/이중오류검출을 동시에 실현하는 코드체계 설계 최소거리 3인 코드체계를 사용하는 경우 단일오류 정정코드로 사용한다면 이중오류 제어는 전혀 불가능 이중오류가 발생할 경우 신드롬은 ‘0’이 아닌 수로 나타남 디코더는 해당 위치를 찾아 비트교환을 수행 디코딩을 거친 블록에는 최대 3비트의 오류가 존재 가능 최소거리 4인 코드체계를 사용하는 경우 단일오류정정과 이중오류검출을 동시에 실현하는 코드체계 전송시스템의 신뢰성을 크게 향상 단일오류 발생시 신드롬에 의해 수신 측에서 직접 정정 이중오류 발생 시에는 이를 검출하여 재전송을 요구 최소거리 3인 단일오류 정정코드를 조작하여 최소거리 1를 증가 단일오류 정정코드의 각 블록마다 전체 블록에 대한 한 개의 패리티검사 비트를 첨가

74 표3.5 단일오류정정 및 이중오류검출

75 3장 과제-2 연습문제 3.19 연습문제 3.24 (a) 연습문제 3.29 연습문제 3.30 QR 코드에 대해 설명하라.