정보이론-5(3)W

• Lossless Compression

- Symbol(기호) 단위로 하나씩 데이터 입력 받는다.
- 고유한 bianry 문자열 인코딩하여 압축
EX)

 

• Symbol Codes

 

 

---

 

• Good Symbol Codes

[조건]

EX)

 

1. 하나의 부호열이 오직 하나의 symbol 시퀸스로만 해석되어야 한다.
2. 각 코드워드의 끝을 쉽게 식별할 수 있어야 한다.
3. 어떤 코드워드도 다른 코드워드의 prefix가 되지 않는다.

---

• Kracft Inequality

- Unique Decodable 한 부호를 만들기 위한 필수 조건
- 이 부등식을 성립해야만 고유 디코딩 가능한 코드가 존재한다.

 

Q) 최대 얼마나 압축할 수 있는가? 
A) Entropy H(X)

 

---

• Huffman Coding

- 가장 빈도가 낮은 두 기호를 선택해 0, 1 을 할당하고, 두 기호를 결합하여 트리를 반복적으로 구축하는 방식

EX)

Q) No Better Code?
A) Yes 
=> Huffman code가 최적의 코드이다!