<소스코딩(Source Coding)> 제5장 상관관계와 자료압축

Presentation on theme: "<소스코딩(Source Coding)> 제5장 상관관계와 자료압축"— Presentation transcript:

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

2 심볼간 상관관계와 소스코딩 <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) 정보공학

3 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 정보공학

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

5 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) 정보공학

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

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

8 예측형 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’ 정보공학

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

10 예측형 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) k (2k-1)~2(2k-1) k 2(2k-1)~3(2k-1) k 3(2k-1)~4(2k-1) k • • • • • • • • • 예) 4-bit block code ‘0’ run-length blocks · · · · 15 16 17 1110 1111 0001 0000 0010 정보공학

11 예측형 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 ···· 해당갯수 Run-length = 2k-1 인 경우  {En} : 00 ···· 0 2k-1개 정보공학

12 Run-length Coding의 자료압축 효과
<최적 블록의 길이 k> <자료압축 효과> : 평균 전송 bit 수 (run-length coder) : run-length+1 의 평균(보통 전송) : 블록의 예측기의 성능 (p) 길이 k : 압축률(%) 예측기 최적 압축률 성능 블록길이 p k LRL LP (%) 정보공학

13 변조방식에서의 상관관계 이용  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’의 크기를 변화시킴 정보공학

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

15 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) 정보공학

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

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

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

19 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 n bits 변화 n-1 bits 변화 정보공학