Arithmetic Coding

H.264 Video Coding에 대한 논문을 읽다보니 Arithmetic coding에 대한 이야기가 계속 나와 그냥 넘어갈 수가 없었다. Arithmetic coding이란 무손실 압축 방법의 하나로, 다양한 길이를 가지는 부호로 압축하는 방법(Variable-length entropy encoding)이다.

우리가 사용하는 컴퓨터에서는 ABC라는 글자를 표현하기 위해 알파벳 하나 당 8bit 씩을 할당하여 ABC를 표현하는데 이러한 방법을 주로 Block encoding이라고 한다. (A B C는 01100001 01100010 01100011이 된다.) 범위를 줄여서 {A,B,C}만 있다고 해보자. 이 때, A, B, C의 조합으로 나타나는 다양한 신호들을 0과 1의 digital signal로 나타내려면 A=00, B=01, C=10 등으로 표현할 수 있다. 이 때, 11에 대한 정의는 이루어져있지 않다. 즉, 낭비되는 코드(11)가 있다는 단점이 존재한다.

그렇다면 A,B,C를 각각 동일한 길이(2bit)로 표현할 게 아니라, 다양한 길이를 가지도록 할당하면 어떨까? 게다가 자주 쓰는 글자는 더 적은 길이로, 자주 쓰지 않는 글자는 더 긴 길이로 표현한다면? 훨씬 경제적으로 표현할 수 있을 것이다. 이런 아이디어로 시작하는 무손실압축방법으로 Huffman coding과 Arithmetic coding이 있다.

공통점으로는 둘다 가변길이를 가지는 부호를 사용한다는 점이다. 부호 간 사용 빈도에 차이가 있다는 점에 기반하여 가변 길이를 이용해서 압축을 가능하게 하므로, 무손실 압축이 가능하다. 물론 사용 빈도의 차이가 적다면 압축률은 형편없을 것이다.

차이점은 그 최종 표현 방법에 있다. Huffman encoding은 단순히 기호들의 나열을 통해 표현한다. 한 편, Arithmetic encoding은 부호화하고자 하는 메시지 전체가 하나의 숫자 n, ( a fraction n, 0.0 ≤ n ＜ 1.0 )로 나타난다는 점이다.

Wikipedia에서 나오는 예제를 들어 표현해보자. 우리가 압축하고자하는 신호는 아래와 같이 총 4가지로 나타나고, 신호 간 빈도가 차이난다고 하자.

{NEUTRAL, POSITIVE, NEGATIVE, END-OF-DATA}

• 60%의 확률로 NEUTRAL
• 20%의 확률로 POSITIVE
• 10%의 확률로 NEGATIVE
• 10%의 확률로 END-OF-DATA

Huffman Coding에서는 가장 많이 나타나는 Symbol을 작은 수의 Bit로, 자주 나타나지 않는 Symbol을 긴 Bit로 나타낸다. 따라서, 아래와 같이 나타낼 수 있다.

• NEUTRAL = 1
• POSITIVE = 01
• NEGATIVE = 001
• END-OF-DATA = 0001

예를 들어, {NEUTRAL, NEUTRAL, NEUTRAL, POSITIVE, NEGATIVE, POSITIVE, END-OF-DATA}의 신호가 입력된다면 이는 Huffman Coding에 의해 11101001010001 이 된다.

Arithmetic Coding에서는 이를 소수로 표현한다. 예를 들어 0.538이라는 encoding된 신호를 받았다고 하자. 이를 decoding하는 과정은 아래와 같다.

http://en.wikipedia.org/wiki/Arithmetic_coding

각 Symbol의 빈도에 따라, 60%, 20%, 10%, 10%로 0.0 ~ 1.0 구간을 할당한 후, 0.538을 이 구간 내에서 비교한다. 첫번째로 보다시피, 0.538은 [0.0, 0.6) 에 위치하므로 NEUTRAL, 두번째로 이러한 0 ~ 0.6 구간을 다시 빈도에 따라 구간을 분리한 후, 해석해보면 10%를 차지하는 [0.48, 0.54)에 위치하므로 NEGATIVE, 다음 단계에서도 똑같이 이를 반복하여 END-OF-DATA에 도달하여 decoding 과정이 끝났다. 즉, 0.538은 {NEUTRAL, NEGATIVE, END-OF-DATA}의 신호라는 뜻이다.

신호 전체를 하나의 소수로 표현한다는 점에서 Huffman coding보다 훌륭하게 압축이 가능해보인다. 하지만 그만큼 계산해야할 양이 많아질 것이다. 코덱이 발전하면서 더 좋은 화질을 더 적은 용량으로 압축이 가능해지지만, 더 높은 계산 성능을 필요로 하는 데에는 이러한 것들이 이유가 된다.