<소스코딩(Source Coding)> 제5장 상관관계와 자료압축 Markov 과정과 Huffman Coding 예측형 Run-length Coding System DPCM, ADPCM, DM, ADM Gray Code & Anti-Gray Code

심볼간 상관관계와 소스코딩 <Huffman Code>  정보원 심볼들의 독립적 발생확률만을 이용하여 코딩  심볼 사이의 상관관계 무시 <심볼간 상관관계의 적용>  Markov chain을 이용한 Huffman Coding - 문자의 전후관계 고려 (예: ‘q’ 다음에 오는 문자는 대부분 ‘u’ 이다.)  Run-length Coding System - ‘0’ run-length를 코딩하여 전송하는 체계 - 화상(image)정보의 전송에 주로 응용  Sample의 전후관계를 고려한 펄스변조방식 - DPCM(differential pulse code modulation) - ADPCM(adaptive DPCM) - DM(delta modulation) - ADM(adaptive DM) <A/D, D/A 변환, 메모리 주소 등에 적용되는 코드체계>  Gray Code : 수의 진행에 따라 오직 1-bit 씩 변화 (A/D, D/A 변환)  Anti-Gray Code : 수의 진행에 따라 될수록 많은 bits 변화 (memory addressing) 정보공학 2001-1

Markov 과정과 Huffman Code jth order Markov process (j-memory source) P(si | si1, si2, …., sij), for all i = 1, 2, …, q & i1, i2, …, ij  j-memory 필요  소스알파벳 S = {s1, s2, …, sq}에 대하여 1st 2nd 3rd 4th • • • • • jth q × q × q × q × · · · · · ×  # of states (j-memory) = q j 정보공학 2001-1

Markov 과정을 이용한 Huffman Coding(예) 표현방법 1 표현방법 2 : 천이행렬(transition matrix) 표현방법 3 : 천이도(transition graph) c b a 1/2 1/4 1/3 a b c 정보공학 2001-1

Markov 과정을 이용한 Huffman Coding(예) 현상태(present state)의 표시 차기상태(next state)의 표시 차차기상태(the state after next state)의 표시 Sequence of Matrix <성질> 1. 차수 n이 증가할수록 원소 사이의 변화량은 감소함 2. 임의의 행(row)을 더하면 1 3. 모두 qq matrix (1-memory source) 정보공학 2001-1

평형상태(equilibrium state)의 분포 현상태와 차기상태의 분포가 같아지는 조건 Matrix equation으로부터 얻는 3개의 방정식은 선형종속 Matrix equation으로부터 2개의 방정식을 임의로 선택하고, 나머지 1개의 방정식은 Pa + Pb + Pc = 1을 사용 3원 1차 연립방정식을 풀어 평형상태 분포를 산출함 정보공학 2001-1

Markov 과정을 이용한 Huffman Coding(예) Si Pi a 1/3 b 1/3 c 1/3 2/3 1/3 01 00 1 2) 전상태가 ‘b’인 경우 Si Pi b 1/2 a 1/4 c 1/4 1/2 01 00 1 3) 전상태가 ‘c’인 경우 Si Pi c 1/2 a 1/4 b 1/4 1/2 01 00 1  평형상태에서 순수한 Huffman 코딩 Si Pi b 4/11 c 4/11 a 3/11 1 7/11 00 4/11 1 01  평균코드길이(Markov)  평균코드길이(Huffman) 정보공학 2001-1

예측형 Run-length Coding 시스템 {Sn’} 예측형 인코더 채널 Run-length 디코더 예측형 디코더 Run-length 인코더 Noise     {En’} {En} {Sn} “블록코드 전송”  예측형 인코더(predictive encoder) {Sn} 예측기 (predictor) {Pn} {En} 예측기가 우수할수록 {En}의 0-run이 길어짐 {Sn} : random sequence {En} : 주로 ‘0’, 가끔 ‘1’ 정보공학 2001-1

예측형 Run-length Coding 시스템(계속)  예측형 디코더(predictive decoder) {En’} 예측기 (predictor) {Pn’} {Sn’} 예측기는 ‘예측형 인코더’에서와 동일한 장치임 만일 채널상에서 오류가 발생하지 않는다면 {En}은 그대로 전송된다. 예측형 디코더의 출력에서는 입력 sequence를 복원함 정보공학 2001-1

예측형 Run-length Coding 시스템(계속) {En}의 ‘0’-run length만을 k-bit 블록코드로 인코딩 ‘0’-run Counter k-bit block coder {En} Run-length k-bit block code ‘0’ run-length # of blocks # of bits 0~(2k-1)-1 1 k (2k-1)~2(2k-1)-1 2 2k 2(2k-1)~3(2k-1)-1 3 3k 3(2k-1)~4(2k-1)-1 4 4k • • • • • • • • • 예) 4-bit block code ‘0’ run-length blocks · · · · 14 15 16 17 1110 1111 0001 0000 0010 정보공학 2001-1

예측형 Run-length Coding 시스템(계속) 채널을 통해 전달된 k-bit 블록코드로부터 {En}을 재생 k-bit block decoder {En’} k-bit block code Run-length Binary gen. <Algorithm> Run-length = 0 인 경우  {En} : 1 Run-length = 1 ~ 2k-2 인 경우  {En} : 00 ···· 01 해당갯수 Run-length = 2k-1 인 경우  {En} : 00 ···· 0 2k-1개 정보공학 2001-1

Run-length Coding의 자료압축 효과 <최적 블록의 길이 k> <자료압축 효과> : 평균 전송 bit 수 (run-length coder) : run-length+1 의 평균(보통 전송) : 블록의 예측기의 성능 (p) 길이 k 0.5 0.6 0.7 0.8 0.9 0.95 0.98 0.99 2 2.29 2.55 3.04 4.10 7.38 14.02 34.0 67.3 3 3.02 3.09 3.27 3.80 5.75 9.94 22.7 44.2 4 4.00 4.00 4.02 4.15 5.04 7.45 15.3 28.6 5 5.00 5.00 5.20 6.28 10.7 18.7 6 6.00 6.00 6.25 8.33 12.8 7 7.01 7.58 9.71 8 8.00 8.05 8.67 9 9.00 9.05 10 10.0 : 압축률(%) 예측기 최적 압축률 성능 블록길이 p k LRL LP (%) 0.7 2 3.04 3.33 91.3 0.8 3 3.80 5.00 76.0 0.9 4 5.04 10.00 50.4 0.95 6 6.25 20.00 31.3 0.98 7 7.58 50.00 15.2 0.99 8 8.67 100.00 8.7 정보공학 2001-1

변조방식에서의 상관관계 이용  PCM (pulse code modulation) - 표본화(sampling), 양자화(quantizing), 부호화(coding) - 각각의 표본을 독립적으로 양자화  DPCM (differential pulse code modulation) - 예측기 이용, 실제의 표본과의 차이(difference)만을 양자화  ADPCM (adaptive differential pulse code modulation) - DPCM 방식에서 ‘양자화 step’을 적응적으로 변화시킴  DM (delta modulation) - 비교기를 사용하여 1-bit 양자화기 사용 (1-bit DPCM) ADM (adaptive delta modulation) - DM 방식에서 신호의 변화율에 따라 ‘양자화 step’의 크기를 변화시킴 정보공학 2001-1

DPCM(differential PCM) {xn} Quantizer Linear Adaptive Predictor  {yn} {en} {xn’} 입력표본 출력표본 예측표본 + - ※ PCM에 대한 DPCM의 효율 정보공학 2001-1

DM(delta modulation) x(t) 극성 Quantizer 적분기 y(t) - + Pulse gen. x(t)’ 입력신호 출력신호 - + Pulse gen. x(t)’ A B 1 -1 A: x(t) x(t)’ 1 B: 1 -1 y(t) 정보공학 2001-1

<계단의 크기를 조절하는ADM> DM의 잡음과 ADM Granular Noise : 입력신호의 완만한 변화에 비하여 계단의 크기가 큰 경 우에 발생하는 잡음 Overload Noise : 입력신호의 급격한 변화에 비하여 계단의 크기가 작은 경우에 발생하는 잡음 x(t) x(t)’ x(t) x(t)’ <계단의 크기를 조절하는ADM> x(t)’ x(t) 정보공학 2001-1

Gray Code 수의 진행에 따라 오로지 1-bit씩 변화하도록 설정된 Code 체계 - Magnetic disk의 구역번호(sector #) 설정 - Linear quantization 1-bit gray 2-bit gray 3-bit gray 4-bit gray 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 1 1 0 1 1 0 0 1 1 1 0 0 1 0 0 0 1 0 1 1 0 0 1 1 0 1 1 1 0 1 1 1 1 0 1 0 1 0 1 1 0 0 0 1 0 0 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 0 0 1 1 0 0 0 정보공학 2001-1

(Gray  Pure Binary) 코드 변환 4-bit pure binary  4-bit gray 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1 0 0 1 1 0 0 1 0 0 1 0 0 0 1 1 0 0 1 0 1 0 1 1 1 0 1 1 0 0 1 0 1 0 1 1 1 0 1 0 0 1 0 0 0 1 1 0 0 1 0 0 1 1 1 0 1 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 0 0 1 0 1 0 1 1 0 1 1 0 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 0 0 0 b1 b2 b3 b4 B1 B2 B3 B4 Binary-to-Gray Gray-to-Binary 변환기는 간단한 논리회로로 실현된다. 정보공학 2001-1

Anti-Gray Code 수의 진행에 따라 될수록 많은 bit가 변하도록 설정된 Code 체계 - 기억장치의 주소 코드(address code) 설정 <n-bit Anti-Gray Code의 구성> 1) (n-1)-bit Gray Code 2) Attaching leading ‘0’ 3) Interpolations of the complement codes 3-bit gray Attaching ‘0’ Interpolations 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 0 1 1 0 0 1 1 0 0 0 1 0 1 0 0 0 1 0 1 1 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 0 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0 0 1 0 0 1 1 0 1 0 1 1 0 1 0 0 1 0 1 1 1 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 1 0 1 1 n bits 변화 n-1 bits 변화 정보공학 2001-1