2주차. 정보이론 및 데이터 압축(허프만 부호화)

1. 정보이론(엔트로피)

학습 목표

1. 데이터 압축의 필요성을 설명할 수 있다.
   ⇒ 정보를 그대로 표현하기는 용량이 굉장히 크다.
2. 정보이론을 설명할 수 있다.
   ⇒ 정보의 크기를 계산할 수 있도록 해주는 이론
3. 정보의 엔트로피를 계산할 수 있다.
   ⇒ 심볼의 확률 비트 수에 심볼의 확률 가중치를 곱한 것을 모두 더한 것

데이터 압축의 필요성

24프레임 8K 비디오 녹화 1시간 시

• 하나의 프레임의 byte = 3byte(색상을 표현하는데 필요한 바이트) * 7680 * 4320
  ⇒ 99,532,800 bytes / frame
• 99,532,800 bytes / frame * 24 frames / sec = 2.4 GB / sec
• 2.4 GB / sec * 3600 secs / hour = 8.64 TB / h

정보 이론이란?

✅ 정보의 크기를 계산할 수 있도록 해 주는 이론

정보의 크기를 알아야 압축을 한다!

League of Legends ⇒ LoL

확률과 정보량은 반비례한다.

예시)

• 내일 태양이 뜬다 ⇒ 확률: 1 - 정보량: 0
• 집에 초인종이 울린다. ⇒ 확률: 적음 - 정보량: 많음

확률을 비트로 표현하기

⚠️ Entropy ⇒ 정보량의 기댓값

특정 심볼의 확률을 비트로 나타내는 식

⚠️ n개의 심볼로 구성된 정보 I의 엔트로피 E(I) ⇒ 심볼 당 평균 비트 수

심볼의 확률 비트 수에 심볼의 확률 가중치를 곱한 것을 모두 더한 것

✅ 엔트로피 이론

Cross Entropy란? + Loss

⚠️ 정보 i의 원래 확률이 아닌 특정 확률로 비트를 배당했을 때의 심볼 당 평균 비트 수

허프만 코딩 (허프만 부호화)

1. 데이터의 중복성과 부호화에 대해 설명할 수 있다.
2. Run-Length 방법으로 데이터를 압축할 수 있다.
3. 예측 부호화 방법으로 데이터를 압축할 수 있다.
4. 허프만 부호화 방법으로 데이터를 압축할 수 있다.

데이터 중복성과 부호화

- 정보의 중복성: 확률이 높다는 것은 중복성이 높다는 것

- 데이터 압축: 여러 번 반복되는 중복성을 줄이는 것

---

데이터의 손실과 손실 부호화

❓ 데이터 손실이란? => 원 데이터와 복호된 데이터 간의 손실이 발생한 것

엔트로피 부호화

💡 엔트로피 이론을 기반으로 하는 무손실 부호화 대표적으로 Huffman 부호화, Arithmetic 부호화가 있음

간단한 무손실 부호화

1. Run-Length Coding ⇒ 심볼과 그 심볼이 연속으로 나오는 갯수로 부호화 함

2. 예측 부호화 ⇒ 부호화 할 데이터에서 예측 데이터를 뺀 잔차값을 부호화 함

허프만 부호화

허프만 부호화 알고리즘

1. 주어진 정보를 구성하는 심볼들의 확률을 계산

2. 심볼들의 확률로부터 허프만 이진 트리 구성허프만 이진트리의 핵심 아이디어 → 확률이 가장 낮은 두 개의 단일 혹은 최상위 노드들 끼리 연결한다.

3. 허프만 이진 트리 기반 허프만 테이블 구성

4. 허프만 테이블에 따라 정보의 각 심볼 부호화

---

학습 자료

K-MOOC - 멀티미디어

K-MOOC 자료실