<소스코딩(Source Coding)> 제4장 가변길이 코드 고정/가변길이 코드(variable-length code) 유일디코딩과 동시디코딩 최적 동시코드와 Huffman Code Huffman Code의 응용

소스코딩(Source Coding) 정보원 심볼들에 대하여 Binary Code를 부여하는 방법 • 평균코드길이(avg. code-length)의 최소화 지향 • 고정길이코드 vs. 가변길이코드 <고정길이코드(fixed-length code)> 예) ASCII code  모든 정보원 심볼에 대하여 동일한 길이의 코드 부여  정보원 심볼의 수를 M이라 하고, 코드의 고정길이를 n이라 하면 <가변길이코드(variable-length code)> 예) Morse code  정보원 심볼의 발생확률에 따라 서로 다른 길이의 코드 부여 - 발생빈도가 높은 심볼 : short code - 발생빈도가 낮은 심볼 : long code  유일성, 동시성, 동기 등의 문제를 해결해야 한다. 정보공학 2001-1

유일성 / 동시성 코드체계 1 s1 = 0 s2 = 01 s3 = 11 s4 = 00 코드체계 2 s1 = 0 s2 = 01 s3 = 011 s4 = 111 코드체계 3 s1 = 0 s2 = 10 s3 = 110 s4 = 111 코드체계 4 s1 = 0 s2 = 10 s3 = 110 s4 = 1110 s5 = 1111 코드체계 5 s1 = 00 s2 = 01 s3 = 10 s4 = 110 s5 = 111 정보공학 2001-1

UI-Code(unique & instantaneous code) Unique Code  모든 extension이 서로 다르다 UI-Code  코드체계 내에 prefix가 없다  디코딩트리 존재 코드체계 2 s1 = 0 s2 = 01 s3 = 011 s4 = 111 코드체계 3 s1 = 0 s2 = 10 s3 = 110 s4 = 111 s2 s3 s4 s1 1 s1 s4 s3 s2 1 정보공학 2001-1

Kraft Inequality 최대 코드길이에 대한 수학적 귀납법으로 증명 Basis step 2) Induction step (최대길이=1 인 경우) (최대길이=n 일때 성립함을 가정하여 최대길이=n+1일때 성립함을 보임) K’ K K’’ 최대길이= n 정보공학 2001-1

최적 UI-Code의 특성 Source Alphabet S = {s1, s2, …, sq}, Code Alphabet C = {0, 1} & pi = Pr{si occurs}, i = 1, 2, …, q & li : code-length for si , i = 1, 2, …, q 평균 코드길이 최적 UI-Code의 특성 (“평균 코드길이”의 관점에서 최적) 정보공학 2001-1

Binary Huffman Coding Step 1. 축소과정(reduction process) 1) 최하위(최소 확률)의 두 심볼을 결합, 합의 확률을 갖는 하나 의 심볼을 형성 2) 새로 형성된 심볼을 확률순서에 따라 천이 3) 오직 두 개의 심볼만 남을 때까지 1), 2) 과정을 반복 Step 2. 확장과정(splitting & expansion process) 1) 남은 두 심볼에 대하여 각각 ‘0’, ‘1’을 할당 (split) 2) 축소과정을 통하여 결합되었던 심볼을 다시 분리하면서 각각 ‘0’, ‘1’을 첨가 (expand) 3) 원래의 q개 심볼이 될 때까지 2) 과정을 반복 정보공학 2001-1

Huffman Coding (예) 예제1) 예제2) 예제3) Zipf’s Distribution (language problem simulation) q = 4 일 때 2. q = 8 일 때 3. q = 16 일 때 각각 Huffman 방식으로 Coding 하라. 정보공학 2001-1

Zipf 분포에 대한 Huffman coding의 이득 N LB LH (Average) G 2 1 1.0 0 4 2 1.8 10 8 3 2.68 10.7 16 4 3.43 14.3 32 5 4.17 16.6 64 6 4.89 18.5 128 7 5.60 20 256 8 6.26 21.8 512 9 6.90 23.3 1024 10 7.54 24.6 정보공학 2001-1

Huffman Code의 특수한 경우 1. 모든 심볼들이 동일한 발생확률을 갖는 경우, • Huffman code = m-bit block code 2. • Huffman code = m-bit block code 심볼들의 발생확률이 대동소이한 경우 3. • Huffman code = Comma code 심볼들의 발생확률이 서로 크게 다른 경우 정보공학 2001-1

코드의 확장 1-차 확장 (원래의 Alphabet) 2-차 확장 (2nd extension) Si Pi S1 2/3 0 S2 1/3 1 2-차 확장 (2nd extension) Sij Pij S1S1 4/9 S1S2 2/9 S2S1 2/9 S2S2 1/9 1 4/9 5/9 01 00 3/9 4/9 1 000 2/9 01 001 3-차 확장 (3rd extension) 4-차 확장 (4th extension) 정보공학 2001-1

코드의 확장과 Entropy Entropy ‖ 0.944444 4 3 2 0.938270 1.000000 Ln 평균코드길이 1 0.918296 1 0.98 0.96 0.94 ‖ Ln 평균코드길이 n 코드확장의 차수 0.944444 4 3 2 0.938270 1.000000 정보공학 2001-1

Radix-r Huffman Coding Step 1. 전처리과정(pre-processing) 1) 소스알파벳의 심볼 수를 개가 되도록, 필요한 경우 dummy Symbol들을 추가한다. Step 2. 축소과정(reduction process) 1) 최하위(최소 확률) r 개 심볼을 결합, 합의 확률을 갖는 하나의 심볼을 형성 2) 새로 형성된 심볼을 확률순서에 따라 천이 3) 오직 r 개의 심볼만 남을 때까지 1), 2) 과정을 반복 Step 3. 확장과정(splitting & expansion process) 1) 남은 r 개의 심볼에 대하여 각각 ‘0’, ‘1’, …, ‘r-1’을 할당 (split) 2) 축소과정을 통하여 결합되었던 심볼을 다시 분리하면서 각각 ‘0’, ‘1’, …, ‘r-1’을 첨가 (expand) 3) 원래의 q개 심볼이 될 때까지 2) 과정을 반복 정보공학 2001-1