3주차. 산술 부호화

산술 부호화 이론

1. 엔트로피 부호화를 설명할 수 있다.
   1. 정보가 갖고 있는 엔트로피에 최대한 가깝게 데이터를 압축하는 것
2. 산술 부호화를 예제를 통해 확인하고, 산술 부호화 알고리즘을 설명할 수 있다.
   1. 산술 부호화: 정보 전체의 확률을 부호화한다.
   2. 각 심볼마다의 최대-최소 확률을 가중한 결과의 값 범위를 통해 압축하는 기법
3. 확률을 이진수로 표현할 수 있다.

무손실 데이터: “원 데이터 - 복호된 데이터의 == 0”

엔트로피 부호화

Shannon의 엔트로피 이론을 기반하는 무손실 부호화, Huffman 부호화와 Arithmetic 부호화

⇒ 정보가 갖고 있는 엔트로피에 최대한 가깝게 데이터를 압축하는 것

허프만 코딩의 핵심 한 문장

💡 확률이 적은 심볼은 많은 수의 비트로, 확률이 큰 심볼은 적은 수의 비트로 부호화해서 엔트로피에 근접하게 부호화

⚠️ 심볼마다 비트를 할당 판별, 부정확성 발생, 압축 성능이 떨어짐

Arithmetic(산술) 부호화

정보 전체의 확률을 부호화한다.

✅ 허프만 부호화 방법보다 더 정보의 엔트로피에 가깝게 많이 압축 가능

기본 아이디어 알고리즘

기초 조건

💡 복호화 하기 위해 해당 정보 전체를 표현하기 위한 비트의 수를 미리 알고 있어야 한다.

확률 이진수 표현

산술 부호화의 문제와 해결

1. 산술 부호화를 이용해 데이터를 압축할 수 있다.
2. 확률 곱하기의 Underflow 문제를 설명할 수 있다.
3. Renormalization을 기반으로 한 산술부호화로 데이터를 압축할 수 있다.

확률 곱하기의 언더플로우

컴퓨터에서 소수점 자리를 한정해서 데이터를 저장하는 경우, 하위 소수점 자리가 사라지는 문제가 발생함

✅ 확률 곱하기 언더플로우 방지하기

1. 소수점 자리가 첫째 자리가 0인 경우 곱하기 10 with cnt += 1
2. 10^cnt한 만큼 최종 결과에서 나누기

Renormalization 산술부호화

모든 정보의 확률 구간을 얻은 후 산술 부호화 하는 것이 아닌, 심볼을 읽어 가며 산술 부호화를 하는 방법

💡 ⇒ 갱신된 Interval 조건에 따라 비트를 바로 출력하고 구간을 2배로 확대함

Renormalization 알고리즘

이진 산술 부호화

정보를 구성하는 심볼이 두 개인 산술 부호화

✅ 2개로 심볼의 의미를 나눔

1. MPS(Most Probable Symbol)
2. LPS(Least Probable Symbol) → Low Probability: 심볼에 대한 확률 기록

💡 모든 심볼에 대하여 전처리과정 후에 이진화를 적용 할 수 있다.
⇒ 압축분야에서 이진 산술 부호과정은 변경하지 않고, 이진화 과정만 설계 구현하여 압축할 수 있다.

적응 이진 산술 부호화 방법

LPS의 확률을 부호화를 위해 입력되는 심볼들의 통계에 따라 적응적으로 갱신하여 압축 성능을 높이는 방법

💡 MPS의 확률을 높이면 높일수록 압축 성능을 높일 수 있음

콘텍스트 적응 이진 산술 부호(CABAC)

입력된 이진정보를 부호화하기 위해서 다양한 콘텍스트(맥락)에 대해서 각각 LPS 심볼의 확률을 독립적으로 적응적으로 변화시키는 것

⇒ 모든 미디어 내용을 전부 읽고 부호화 하는 것이 아닌 읽어가면서 부호화하는 기법

🚨 264, HEVC, VVC 동영상 압축 등 다양한 분야의 압축에서 사용됨

---

학습 자료

K-MOOC - 멀티미디어

K-MOOC 자료실