C언어를 이용한 Arithmetic Coding

소개글

디지털영상처리 과제입니다.
최대한 알기 쉽게 작성하였습니다.
이론과 소스, 분석으로 이루어져있습니다.

목차

1. 이론
(1) Entrophy 부호화
(2) Arithmetic coding

2. 내용
(1) Encoding
(2) Decoding

3. 결과 분석
(1) Encoding
(2) Decoding

본문내용

(1) Entrophy 부호화
이번 실습은 Entrophy 부호화 방식 중에 하나인 Arithmetic coding 방식에 대하여 알아보았다. 저번 시간에 실습한 허프만 코딩 방식 또한 Entrophy 부호화 방식이다. 이 개념의 특징은 일단은 무손실 압축 기법 알고리즘 이며, 모든 데이터를 가변길이나 혹은 고정길이의 부호들로 부호화 한다. 이 부호화 방식의 특징은 데이터 고유의 특징과 형태를 무시하고 모두 비트 열이나 바이트 열로 간주하여 처리한다.
어떠한 데이터들의 빈도수 값이 있을 때 Entrophy는 이들 데이터들이 나타내는 빈도수에 따라 자신들이 표현 하는 정보량을 평균적으로 산출한 값이다. 이 값은 최적의 값이며 이 값을 기준으로 압축 알고리즘의 효율성을 판단하게 된다. 예를 들어 어떠한 데이터들을 표현하는데 필요한 Entrophy 값이 3bit 라면 3bit 는 최적 값이기 때문에 동일 데이터를 표현하는데 있어 3bit보다 낮은 bit수로는 절대 표현이 불가능 하다. 따라서 우리는 이 최적의 Entrophy 값에 최대한 근접하는 결과를 가져오는 알고리즘을 설계하는 것이 주된 목적이다. 이론상으로 이 Entrophy 와 동일한 알고리즘을 설계 하는 것이 가능하지만 좀처럼 간단한 방법으론 이를 구현하기가 쉽지 않고 여러가지 물리적, 구조적 제약 조건들 때문에 달성해야 하는 기준 값으로 놓고 설계하는 경우가 많다.

(2) Arithmetic coding
Arithmetic coding은 Entrophy 부호화 방식 중 에서도 원래의 데이터를 손상시키지 않는 무손실 데이터 압축 방법이다. 그래서 이번 실험에서는 그 특징을 알아 볼 수 있게 TEXT를 가지고 부호화를 해보았다. Arithmetic coding 기법은 이름에서도 알 수 있듯이 많은 연산량을 기초로 하기 때문에 허프만 코딩 방식 보다는 조금 복잡하다. 그리고 허프만 코딩 방식이 최적의 코딩길이를 기반으로 문자 하나당 코드워드를 생성하는 알고리즘 이었던 반면에 Arithmetic coding 방식은 연속적인 전체의 데이터를 가지고 이 전체에 대한 실수로 표현하여 부호화 하는 방식이다.
압축률은 허프만 코딩 방식보다 뛰어나며 역시 통계적인 확률 값을 이용하여 구현한다. 만약에 예를 들어 알파벳 A, B, C에 대한 통계 값이 있고 이들 3문자가 ABC라는 단어를 만든다고 할 때 Arithmetic coding 알고리즘이 고려하는 사항은 다음과 같다.

참고 자료

없음