잘린 이진 인코딩

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "Trunced binary incoding" – 뉴스 · 신문 · 책 · 학자 · JSTOR (2009년 12월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

잘린 이진 인코딩은 일반적으로 유한한 알파벳을 가진 균일한 확률 분포에 사용되는 엔트로피 인코딩이다.총 크기가 n인 알파벳으로 매개변수화된다.n이 2의 힘이 아닐 때는 약간 더 일반적인 형태의 이진 부호화다.

n이 2의 검정력인 경우, 0 ≤ x < n에 대한 코드화된 값은 x of length log₂(n)에 대한 단순한 이진법 코드다.그렇지 않으면 k = 바닥(log(n₂))을 2^k < 2로^k+1 하고 u = 2 - n으로^k+1 한다.

잘린 이진 인코딩은 길이 k의 첫 번째 u 기호 코드 워드를 할당하고 나머지 n - u 기호를 길이 k + 1의 마지막 n - u 코드 워드를 할당한다. 길이 k + 1의 모든 코드 워드는 "0" 또는 "1"이 추가된 길이 k의 미지정 코드 워드로 구성되기 때문에 결과 코드는 접두사 코드다.

역사

적어도 1984년 이후 사용된 단계별 코드(이코노미 코드라고도 함)^[1]는 잘린 이진 부호화라고도 한다.

n = 5인 예제

예를 들어, 알파벳 {0, 1, 2, 3, 4}, n = 5 및² 2 ≤ n < 2이므로³ k = 2 및 u³ = 2 - 5 = 3이다.잘린 이진 인코딩은 첫 번째 u 기호를 길이 2의 코드 워드 00, 01 및 10으로 지정한 후 마지막 n - u 기호를 코드 워드 110과 111로 지정하고, 마지막 두 개의 코드 워드는 길이 3으로 지정한다.

예를 들어, n이 5인 경우 일반 이진 인코딩과 잘린 이진 인코딩은 다음과 같은 코드 단어를 할당한다.적중된 자릿수는 잘린 이진수로 전송되지 않는다.

잘림 이진의	인코딩			표준 이진의
0	0	0	0	0
1	0	0	1	1
2	0	1	0	2
사용되지 않음	0	1	1	3
사용되지 않음	1	0	0	4
사용되지 않음	1	0	1	5/사용되지 않음
3	1	1	0	6/사용되지 않음
4	1	1	1	7/사용되지 않음

간단한 이진 인코딩을 사용하여 n을 인코딩하는 데 3비트가 필요하므로 2³ - n = 8 - 5 = 3은 사용되지 않는다.

수치로 환산하면 값 x를 0 ≤ x < n으로 보내고, 기호가^k 2 ≤ n < 2인^k+1 경우에는 알파벳 크기를 2의 가장 가까운 검정력으로 반올림할 때 u = 2^{k + 1} - n 미사용 항목이 있다.잘린 이진수로 숫자 x를 인코딩하는 프로세스는 다음과 같다: x가 u보다 작으면 k 이진 비트 단위로 인코딩한다.x가 u보다 크거나 같으면 x + u 값을 k + 1 이진 비트 단위로 인코딩하십시오.

n = 10인 예제

또 다른 예로는 크기 10(0과 9 사이)의 알파벳을 인코딩하려면 4비트가 필요하지만 2~10⁴ = 6개의 사용되지 않는 코드가 있으므로 6 미만의 입력값은 첫 번째 비트가 폐기되는 반면, 6보다 크거나 같은 입력값은 이진 공간의 끝에서 6으로 오프셋된다.(사용되지 않은 패턴은 이 표에 나와 있지 않음)

입력 가치를 매기다	오프셋	오프셋 가치를 매기다	표준 이진수	잘림 이진수
0	0	0	0000	000
1	0	1	0001	001
2	0	2	0010	010
3	0	3	0011	011
4	0	4	0100	100
5	0	5	0101	101
6	6	12	0110	1100
7	6	13	0111	1101
8	6	14	1000	1110
9	6	15	1001	1111

디코딩하려면 첫 번째 k비트를 읽으십시오.u보다 작은 값을 인코딩하면 디코딩이 완료된다.그렇지 않으면 추가 비트를 읽고 결과에서 u를 뺀다.

n = 7인 예제

여기서 더 극단적인 경우를 들 수 있다: n = 7을 사용하면 2의 다음 검정력은 8이므로 k = 2와 u = 2³ - 7 = 1:

입력 가치를 매기다	오프셋	오프셋 가치를 매기다	표준 이진수	잘림 이진수
0	0	0	000	00
1	1	2	001	010
2	1	3	010	011
3	1	4	011	100
4	1	5	100	101
5	1	6	101	110
6	1	7	110	111

이 마지막 예는 선행 0비트가 항상 짧은 코드를 나타내지는 않는다는 것을 보여준다; 만약 u < 2가^k 있다면, 어떤 긴 코드는 0비트로 시작할 것이다.

단순 알고리즘

값 x, 0 <= x < n에 대해 잘린 이진 인코딩을 생성하십시오. 여기서 n > 0은 x. n을 포함하는 알파벳의 크기입니다 2의 검정력이 될 필요는 없음.

문자열 잘림Binary(int x, int n) {/ k = 바닥(log2(n)을 설정), 즉 2^k <= n < 2^(k+1)과 같은 k.int k = 0, t = n; while (t > 1) { k++; t >= 1; } // u를 사용하지 않는 코드 워드 수로 설정 = 2^(k+1) - n. int u = (1< k+1) - n; 만약 (x < u)가 바이너리(x, k+1)를 반환할 경우, 다른 바이너리(x+u, k+1); }; }; }; }

루틴 바이너리는 설명서로, 일반적으로 변수 x의 가장 오른쪽의 렌 비트만 원하는 것이다.여기서는 렌비트를 사용하여 x에 대한 이진 코드를 출력하고, 필요할 경우 고차 0의 패딩을 출력한다.

문자열 이진수(int x, int len) { 문자열 s = ""," 반면 (x != 0) { 만약 (짝수) s = '0' + s, 그 외 s = '1' + s; x >= 1; }, s.길이 < len) s = '0' + s; 리턴 s; }

효율성에 관하여

n이 2의 검정력이 아니고 k 비트 기호가 확률 p로 관측되면 k + 1 비트 기호는 확률 1 - p로 관측된다.기호 $b{\displaystyle {}_{}}$ ${\displaystyle e_{}}$ ${\$당 예상되는 비트 수를 다음과 같이$$ 계산할 수 있다.

${\displaystyle b_{}}$ ${\displaystyle e_{}}$= ${\displaystyle p}$ ${\displaystyle \ast k}$+${\displaystyle }$( ${\displaystyle 1}$- p${\displaystyle }$) ${\displaystyle \ast }$( k${\displaystyle }$+ ${\displaystyle 1}$) ${\displaystyle b_{e}=p*k+(1-p)*(k+1$

기호의 원시 인코딩은 $b{\displaystyle {}_{}}$ ${\displaystyle u_{}}$= ${\displaystyle \mathrm{k}}$+ 1 ${\displaystyle b_{u}=k+1}$비트$$ 입니다.그런 다음 인코딩의 상대적 공간 절약 s(데이터 압축 비율 참조)를 다음과 같이 정의할 수 있다.

${\displaystyle \mathrm{s}}$= 1${\displaystyle }$- ${\displaystyle b\frac{{}_{}}{}}$ ${\displaystyle \frac{{}_{}}{{}_{}}}$ ${\displaystyle \frac{b_{}}{}}$ ${\displaystyle \frac{u}{}\frac{{}_{}}{}}$= ${\displaystyle 1}$- ${\displaystyle p\frac{}{}}$ ${\displaystyle \frac{\ast }{}}$ k${\displaystyle \frac{}{}}$+${\displaystyle \frac{}{}}$( ${\displaystyle \frac{1}{}}$- p${\displaystyle \frac{}{}}$)${\displaystyle \frac{\ast }{}}$( ${\displaystyle \frac{\mathrm{k}}{}}$+ 1) ${\displaystyle \frac{}{}}$+ 1 k + ${\displaystyle \frac{1}{}}$ ${\$$1}.$

단순화되면 이 표현은 다음과 같은 결과를 초래한다.

${\displaystyle s}$= ${\displaystyle \frac{\mathrm{p}}{}}$ ${\displaystyle \frac{k}{}}$+ 1${\displaystyle \frac{}{}}$= ${\displaystyle p\frac{}{}}$ ${\displaystyle \frac{{}_{}}{}}$ ${\displaystyle \frac{u_{}}{}}$ ${\$u$\}\}\}\}\}\}\}\}\}.$

이는 k비트 기호의 확률 p가 증가할수록 잘린 이진 인코딩의 상대적 효율성이 증가하며 기호 $b{\displaystyle {}_{}}$ ${\displaystyle u_{}}$ ${\$당 원시 인코딩 비트가 감소한다는$$ 것을 나타낸다.

참고 항목

• 벤포드의 법칙
• 골롬 부호화

참조