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

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

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) 감소 정보공학 2001-1

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

가중치(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 문자열 검사문자      5 4 3 2 1  “weights” 가중합(Weighted sum) = 5W + 4X + 3Y + 2Z + p 정보공학 2001-1

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

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

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

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

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

Hamming 코드 (Syndrome과 검사위치 ) 검사위치 이진수 표현 1 0 0 0 1 2 0 0 1 0 3 0 0 1 1 4 0 1 0 0 5 0 1 0 1 6 0 1 1 0 7 0 1 1 1 8 1 0 0 0 9 1 0 0 1 10 1 0 1 0 11 1 0 1 1 12 . . . 1 1 0 0 . . . 정보공학 2001-1

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

채널코딩의 기하학적 접근 n-bit code system n-dimensional binary space n = 1 n = 2 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 순으로 표시 정보공학 2001-1

기본 개념 거리함수(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) 정보공학 2001-1

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