일라이어스 감마 부호

3. 복호화 (Decoding)

일라이어스 감마 부호로 인코딩된 정수를 복호화하는 과정은 다음과 같다.

# 스트림에서 0을 읽어 첫 번째 1이 나올 때까지 0의 개수를 센다. 이 0의 개수를 ''N''이라고 한다.

# 첫 번째 1을 정수의 첫 번째 숫자, 즉 2^''N''의 값을 가진 숫자로 간주하고, 나머지 ''N''개의 정수 자릿수를 읽는다.

4. 활용 (Uses)

일라이어스 감마 부호는 작은 값의 발생 빈도가 높고 큰 값의 발생 빈도가 낮은 데이터에 대해 효율적이며, 데이터 압축 등에 활용된다. 감마 코딩은 가장 큰 인코딩된 값을 미리 알 수 없거나, 작은 값이 큰 값보다 훨씬 더 빈번한 데이터를 압축하는 데 사용된다. 예를 들어, 5와 같은 작은 숫자를 고정된 8비트 크기로 저장하면 00000101이 되지만, γ-인코딩 가변 비트 버전은 00 1 01이 되어 3비트가 덜 필요하다. 반대로, 254와 같은 큰 값을 고정 8비트 크기로 저장하면 11111110이 되지만, γ-인코딩 가변 비트 버전은 0000000 1 1111110이 되어 7비트가 더 필요하다.

X가 큰 값 (6비트 이상)이라면, 델타 부호가 더 짧은 부호를 출력할 수 있다. 감마 부호는 엘리아스 델타 부호의 구성 요소로 사용된다.

5. 일반화 (Generalizations)

엘리아스 감마 부호는 0 또는 음의 정수를 직접 표현할 수 없다. 0을 처리하는 한 가지 방법은 코딩 전에 1을 더하고 디코딩 후에 1을 빼는 것이다. 또 다른 방법은 각 0이 아닌 코드 앞에 1을 붙이고 0을 단일 0으로 코딩하는 것이다.

모든 정수를 코딩하는 한 가지 방법은 전단사를 설정하는 것이다. 예를 들어 정수(0, −1, 1, −2, 2, −3, 3, ...)를 (1, 2, 3, 4, 5, 6, 7, ...)에 매핑한다. 소프트웨어에서 이는 음이 아닌 입력을 홀수 출력에, 음의 입력을 짝수 출력에 매핑하여 가장 낮은 비트가 반전된 부호 비트가 되도록 함으로써 가장 쉽게 수행된다.

수식으로 표현하면 다음과 같다.

:$\backslash begin\{cases\}$

x \mapsto 2x+1 & \mathrm{when~} x \geq 0 \\

x \mapsto -2x & \mathrm{when~} x < 0 \\

\end{cases}

지수 골롬 부호화는 감마 코드를 "더 평평한" 멱법칙 분포를 가진 정수로 일반화하며, 이는 골롬 부호화가 단항 코드를 일반화하는 것과 같다. 이것은 숫자를 2의 거듭제곱과 같은 양의 제수로 나누고, 몫보다 1 더 큰 값에 대한 감마 코드를 쓰고, 일반적인 이진 코드로 나머지를 쓰는 것을 포함한다. 대상 정수 X의 2진수 표현을 대상으로 할때, 우선, X의 자릿수보다 1 작은 수만큼 "0"을 출력한다. 다음으로, X를 그대로 출력한다. 그 결과가 감마 부호이다.

5. 1. 0 또는 음수 표현

5. 2. 지수 골롬 부호화 (Exponential-Golomb coding)

대상 정수 X의 2진수 표현을 대상으로 할때, 우선 X의 자릿수보다 1 작은 수만큼 "0"을 출력하고, 다음으로 X를 그대로 출력하면 그 결과가 감마 부호가 된다. X가 큰 값 (6비트 이상)이라면, 델타 부호가 더 짧은 부호를 출력할 수 있다.