엘리아스 감마 부호화

Elias δ 코드 또는 Elias 감마 코드는 Peter Elias에 ^[1]^{: 197, 199}의해 개발된 양의 정수를 부호화하는 범용 코드입니다.상한을 미리 결정할 수 없는 정수를 코드화할 때 가장 일반적으로 사용됩니다.

부호화

숫자 x 11을 코드화하려면:

N $N=\lfloor \log _{2}x\rfloor$ $N=\lfloor \log _{2}x\rfloor$ $N=\lfloor \log _{2}x\rfloor$ 2 $N=\lfloor \log _{2}x\rfloor$ $N=\lfloor \log _{2}x\rfloor$ $⌋$ display （ { $displaystyle$ N = \ $lfloor$ \ $log$ _ ${2}x$ \ $loor$ } ）가 $N=\lfloor \log _{2}x\rfloor$ 포함된 2의 최대 전력이므로^N 2µ x < 2라고^N+1 $N=\lfloor \log _{2}x\rfloor$ .
N개의 0비트를 기입합니다.
N+1비트 이진수인 x의 이진 형식을 추가합니다.

동일한 프로세스를 표현하는 동등한 방법:

N을 단항으로 인코딩합니다.즉, N 뒤에 0이 1이 계속됩니다.
나머지 N자리 숫자 x를 이 N자리 표현에 추가합니다.

$숫자$ x(\ $displaystyle$ x $x$ 를 나타내기 위해 Elias 감마(')는 2 $2\lfloor \log _{2}(x)\rfloor +1$ 2 $2\lfloor \log _{2}(x)\rfloor +1$ ( $2\lfloor \log _{2}(x)\rfloor +1$ ) $2\lfloor \log _{2}(x)\rfloor +1$ + $2\lfloor \log _{2}(x)\rfloor +1$ ( \ $displaystyle$ 2 \ $lfloor$ \ $log$ _ ${ 2$ (x $2\lfloor \log _{2}(x)\rfloor +1$ ) \ $rfloor + 1$ ^[1]^{: 199})비트를 $2\lfloor \log _{2}(x)\rfloor +1$ 합니다.

코드가 시작됩니다(명확성을 위해 코드에 대한 묵시적 확률 분포가 추가됨).

번호	바이너리	§ 부호화	암묵적
1 = 2⁰ + 0	`1`	`1`	1/2

2 = 2¹ + 0	`1 0`	`0 1 0`	1/8
3 = 2¹ + 1	`1 1`	`0 1 1`	1/8

4 = 2² + 0	`1 00`	`00 1 00`	1/32
5 = 2² + 1	`1 01`	`00 1 01`	1/32
6 = 2² + 2	`1 10`	`00 1 10`	1/32
7 = 2² + 3	`1 11`	`00 1 11`	1/32

8 = 2³ + 0	`1 000`	`000 1 000`	1/128
9 = 2³ + 1	`1 001`	`000 1 001`	1/128
10 = 2³ + 2	`1 010`	`000 1 010`	1/128
11 = 2³ + 3	`1 011`	`000 1 011`	1/128
12 = 2³ + 4	`1 100`	`000 1 100`	1/128
13 = 2³ + 5	`1 101`	`000 1 101`	1/128
14 = 2³ + 6	`1 110`	`000 1 110`	1/128
15 = 2³ + 7	`1 111`	`000 1 111`	1/128

16 = 2⁴ + 0	`1 0000`	`0000 1 0000`	1/512
17 = 2⁴ + 1	`1 0001`	`0000 1 0001`	1/512

디코딩

Elias 감마 코드화된 정수를 디코딩하려면:

스트림에서 0을 읽고 첫 번째 1에 도달할 때까지 세어 보십시오. 이 0을 N이라고 합니다.
도달한 숫자가 정수의 첫 번째 자리라고 생각하고 값이 2인^N 경우 나머지 N자리 정수를 읽습니다.

사용하다

감마 부호화는 가장 큰 부호화 값을 사전에 알 수 없는 애플리케이션 또는 작은 값이 큰 값보다 훨씬 더 빈번한 데이터를 압축하는 데 사용됩니다.

감마 부호화는 Elias 델타 코드의 구성 요소입니다.

일반화

감마 부호화는 0 또는 음의 정수를 코드화하지 않습니다.0을 처리하는 한 가지 방법은 부호화 전에 1을 더하고 복호화 후에 1을 빼는 것입니다.다른 방법은 0이 아닌 각 코드에 1을 프리픽스로 붙이고 코드0을 단일0으로 붙이는 것입니다.

모든 정수를 코드화하는 한 가지 방법은 부호화하기 전에 정수(0, -1, 1, -2, -3, 3, ...)를 (1, 2, 3, 4, 5, 6, 7, ...)에 매핑하는 바이젝션을 설정하는 것입니다.소프트웨어에서는 음이 아닌 입력을 홀수 출력에 매핑하고 음의 입력을 짝수 출력에 매핑함으로써 가장 쉽게 실행할 수 있으므로 최하위 비트는 반전 부호 비트가 됩니다.
${\displaystyle}x\mapto 2x+1&\mathrm {when~}x\geq 0\x\mapsto -2x&\mathrm {when~}x<0\end{cases}}$

지수-골롬 부호화는 골롬 부호화가 단항 코드를 일반화하듯이 감마 코드를 "더 평평한" 멱함수 분포를 가진 정수로 일반화합니다.이는 숫자를 양수(일반적으로 2의 거듭제곱)로 나누고, 몫보다 하나 더 많은 감마 코드를 쓰고, 나머지를 일반 이진 코드로 쓰는 것을 포함한다.

「」를 참조해 주세요.

레퍼런스

^ ^a ^b Elias, Peter (March 1975). "Universal codeword sets and representations of the integers". IEEE Transactions on Information Theory. 21 (2): 194–203. doi:10.1109/tit.1975.1055349.

추가 정보

Sayood, Khalid (2003). "Levenstein and Elias Gamma Codes". Lossless Compression Handbook. Elsevier. ISBN 978-0-12-620861-0.

[Elias-1] Elias, Peter (March 1975). "Universal codeword sets and representations of the integers". IEEE Transactions on Information Theory. 21 (2): 194–203. doi:10.1109/tit.1975.1055349.

[1]

Search

엘리아스 감마 부호화

네임스페이스

더

목차

부호화

디코딩

사용하다

일반화

「」를 참조해 주세요.

레퍼런스

추가 정보

Search

엘리아스 감마 부호화

부호화

디코딩

사용하다

일반화

「 」를 참조해 주세요.

레퍼런스

추가 정보

「」를 참조해 주세요.