제3장 채널코딩(Channel Coding)

Presentation on theme: "제3장 채널코딩(Channel Coding)"— Presentation transcript:

1 제3장 채널코딩(Channel Coding)
Parity Check (error-detecting/correcting) Weighted code Hamming code Channel coding의 기하학적 접근 방법

2 채널코딩(Channel Coding) 채널상에서 발생하는 오류(error)를 제어하기 위하여 송수신 간에 약속된 코드 조작방식
오류검출코드(error-detecting code) 오류정정코드(error-correcting code) <필요성>  시스템의 신뢰성 및 성능의 유지 및 향상  시스템의 유지보수  round-trip delay가 큰 경우 : error-correcting <구현의 형태>  H/W : 고속으로 동작, High cost  S/W : 저속으로 동작, Low cost (융통성) 정보공학

3 Parity Check 1. Simple Parity Check nth n-1st       3rd 2nd 1st
Parity bit Information bits : One Block 홀수 개의 오류 검출 2. Multiple Parity Check nth n-1st    (k+1) kth    2nd 1st : One Block Parity bits : n-k개 Information bits : k개 Redundancy : R  n / k Excess Redundancy = R-1 Redundancy가 증가할수록 오류제어능력 향상, 시스템 신뢰성 향상 정보율(information rate) 감소 정보공학

4 독립오류(백색잡음) 다발오류(burst error)의 검출 Block 내의 각 bit는 서로 독립이다.
bn bn-1 bn b b1 p 다발오류(burst error)의 검출 원인 전파환경의 급격한 변화 - 전력공급의 성능 변화 자성체 기억장치의 흠 등 오류검출코드의 설계 실험에 의하여 burst-error의 최대길이 L(bits)을 추적 Word 단위/Bit 단위 parity 검사를 동시에 적용 정보공학

5 가중치(Weighted) 코드 시스템 운용자의 실수에 의한 오류를 검출
1. Alphanumeric Weighted Code(mod-37) S={0, 1, 2, …, 9, space, A, B, C, …, Z} : 총 37개 원소 1) 문자블록의 최후에 “check character” 첨가 2) 문자블록의 가중합(weighted sum)이 mod-37을 만족하도록 W X Y Z p 문자열 검사문자       “weights” 가중합(Weighted sum) = 5W + 4X + 3Y + 2Z + p 정보공학

6 Progressive Digiting : 문자블록의 가중합을 구하는 방법
W X Y Z p 문자열 검사문자       “weights” 문자열 합 합의 합 W W W X W+X W+X Y W+X+Y W+2X+Y Z W+X+Y+Z W+3X+2Y+Z p W+X+Y+Z+p W+4X+3Y+2Z+p 정보공학

7 가중합(weighted sum)이 mod-11을 만족하도록 검사번호 설정
2. ISBN(international standard book number) : 국제표준 도서번호 S={0, 1, 2, …, 9, X} : 총 11개 원소 (mod-11 weighted code) ISBN 검사번호 (mod-11) 국적(미국) 출판사 (Prentice-Hall) 도서번호 번호 사이의 하이픈(‘-’)은 임의로 삽입 가중합(weighted sum)이 mod-11을 만족하도록 검사번호 설정 검사번호가 ‘10’인 경우 ‘X’를 사용 정보공학

8 오류정정코드(error-correcting code)
삼중코드(triplication code) - 한 블록을 3회씩 전송하는 방식 - RT = 3k/k = 3 (redundancy가 매우 크다.) 사각형코드(rectangular code) • • • • m-1 n-1 : 정보 bits : 패리티 bits 정보공학

9 3. 삼각형코드(triangular code)
• • • • • • n-1 • • • • • • 4. 육면체코드(cubic code) n n • • • • • • n • 정보공학

10 Hamming 코드 (기본지식) Syndrome : 한 블록 내에서 오류의 발생위치를 표시하도록 설 계된 이진수 (그 십진 표현이 오류의 위치를 표시함) Syndrome bits Parity check의 결과에 따라, even  ‘0’, odd  ‘1’ m 번의 Parity check  m-bit syndrome 기본 관계식(fundamental relationship) Redundancy of n-bit Hamming Code 정보공학

11 Hamming 코드 (Syndrome과 검사위치 )
검사위치 이진수 표현 정보공학

12 7-bit Hamming 코드 (예) 1 2 3 4 5 6 7 <Encoding> 위치 정보 1 0 1 1
<Encoding> 위치 정보 Encoded 정보 <전송중 오류발생>  Encoded 정보 <Decoding> 1st 2nd 3rd  fail  fail  success Syndrome = 3 (세 번째 위치에서 오류) 정보공학

13 채널코딩의 기하학적 접근 n-bit code system n-dimensional binary space
n = n = n = 3 001 000 111 011 010 00 100 110 01 11 10 1 101 # of points = 2n 1-bit error = 1-edge transfer point(정점) vs. code-point(코드점) vertex = code edge = 1-bit difference gray code 순으로 표시 정보공학

14 기본 개념 거리함수(distance function or Hamming distance) : 두 코드점 사이의 최소 edge 수 - 서로 다른 bit의 수  연산하여 나타나는 ‘1’의 수 최소거리(minimum distance of a system) : 코드체계(code system) 내의 각 코드점 사이의 거리함수 중 최 소값 - 오류제어능력의 척도로 사용됨 구의 표면(surface of a sphere) : 한 코드점으로부터 동일한 거리를 갖는 정점들의 집합 - 중심(origin) 반경(radius) 원소(element) 구의 체적(volume of a sphere) : 한 구에 포함되는 모든 정점의 수(중심+구각+구의 표면) 공간의 체적(volume of a space) : 한 Binary space에 포함되는 모든 정점의 수 (2n) 정보공학

15 최소거리에 따르는 오류제어 능력 최소거리 오류제어 능력 (min. distance) (error-control capability) 유일코드(unique code) 단일오류 검출 3 단일오류 정정 혹은 이중오류 검출 4 단일오류 정정 및 이중오류 검출 5 이중오류 정정 7 삼중오류 정정 정보공학