일라이어스 델타 부호

1. 개요

엘리아스 델타 부호는 양의 정수를 가변 길이로 표현하는 엔트로피 부호화 방식 중 하나이다. 숫자를 2의 거듭제곱과 나머지 이진 숫자로 나누어 부호화하며, 엘리아스 감마 부호보다 큰 정수를 효율적으로 표현할 수 있다. 부호화는 N, L 값을 계산하고, L개의 0, N+1의 이진 표현, X의 최상위 비트를 제외한 나머지 N 비트를 쓰는 방식으로 진행된다. 디코딩은 0의 개수를 세고, L과 N을 계산하여 원래 숫자를 복원하는 과정으로 이루어진다. C++ 코드를 통해 인코딩 및 디코딩을 구현할 수 있으며, 0 또는 음의 정수를 부호화하기 위한 확장 방법도 존재한다.

2. 부호화 원리

숫자 X ≥ 1을 인코딩하는 단계는 다음과 같다.

# N = ⌊log₂ X⌋를 계산한다. 즉, X에서 2의 가장 높은 거듭제곱을 구한다 (2^N ≤ X < 2^N+1).
# L = ⌊log₂(N+1)⌋를 계산한다. 즉, N+1에서 2의 가장 높은 거듭제곱을 구한다 (2^L ≤ N+1 < 2^L+1).
# L개의 0을 쓴다.
# N+1의 이진 표현(L+1 비트)을 쓴다.
# X의 최상위 비트(MSB)를 제외한 나머지 N 비트를 쓴다.

다른 표현 방법:

# X를 2의 거듭제곱(2^N)과 나머지 N개의 이진 숫자로 나눈다.
# 엘리아스 감마 코딩을 사용하여 N+1을 인코딩한다.
# N+1의 표현에 N개의 나머지 이진 숫자를 추가한다.

엘리아스 델타(δ)는 숫자 $x$를 나타내기 위해 $\backslash lfloor\; \backslash log\_2(x)\; \backslash rfloor\; +\; 2\; \backslash lfloor\; \backslash log\_2\; (\backslash lfloor\; \backslash log\_2(x)\; \backslash rfloor\; +1)\; \backslash rfloor\; +\; 1$ 비트를 사용한다. 이는 엘리아스 감마 코딩보다 적은 비트를 사용하여 매우 큰 정수를 표현할 때 유용하다.

2.1. 단계별 부호화 방법

숫자 X ≥ 1을 인코딩하는 단계는 다음과 같다.

# N = ⌊log₂ X⌋를 계산한다. 즉, X에서 2의 가장 높은 거듭제곱을 구한다 (2^N ≤ X < 2^N+1).
# L = ⌊log₂(N+1)⌋를 계산한다. 즉, N+1에서 2의 가장 높은 거듭제곱을 구한다 (2^L ≤ N+1 < 2^L+1).
# L개의 0을 쓴다.
# N+1의 이진 표현(L+1 비트)을 쓴다.
# X의 최상위 비트(MSB)를 제외한 나머지 N 비트를 쓴다.

다른 표현 방법:

# X를 2의 거듭제곱(2^N)과 나머지 N개의 이진 숫자로 나눈다.
# 엘리아스 감마 코딩을 사용하여 N+1을 인코딩한다.
# N+1의 표현에 N개의 나머지 이진 숫자를 추가한다.

엘리아스 델타(δ)는 숫자 $x$를 나타내기 위해 $\backslash lfloor\; \backslash log\_2(x)\; \backslash rfloor\; +\; 2\; \backslash lfloor\; \backslash log\_2\; (\backslash lfloor\; \backslash log\_2(x)\; \backslash rfloor\; +1)\; \backslash rfloor\; +\; 1$ 비트를 사용한다. 이는 엘리아스 감마 코딩보다 적은 비트를 사용하여 매우 큰 정수를 표현할 때 유용하다.

2.2. 간략화된 부호화 방법

숫자 X ≥ 1을 인코딩하는 방법은 다음과 같다.

# N = ⌊log₂ X⌋ 즉, X에서 2의 가장 높은 거듭제곱을 구한다. (2^N ≤ X < 2^N+1)
# L = ⌊log₂(N+1)⌋ 즉, N+1에서 2의 가장 높은 거듭제곱을 구한다. (2^L ≤ N+1 < 2^L+1)
# L개의 0을 쓴다.
# N+1의 이진 표현(L+1 비트)을 쓴다.
# X의 최상위 비트를 제외한 나머지 비트(N 비트)를 쓴다.

다른 표현 방법은 다음과 같다.

# X를 2의 거듭제곱(2^N)과 나머지 N개의 이진 숫자로 나눈다.
# 엘리아스 감마 코딩으로 N+1을 인코딩한다.
# N개의 나머지 이진 숫자를 N+1 표현에 추가한다.

엘리아스 델타(δ)는 숫자 $x$를 나타내기 위해 $\backslash lfloor\; \backslash log\_2(x)\; \backslash rfloor\; +\; 2\; \backslash lfloor\; \backslash log\_2\; (\backslash lfloor\; \backslash log\_2(x)\; \backslash rfloor\; +1)\; \backslash rfloor\; +\; 1$ 비트를 사용한다. 이는 엘리아스 감마 코딩을 사용할 때보다 큰 정수에 유용하다.

엘리아스 델타 인코딩된 정수를 디코딩하는 방법은 다음과 같다.

# 스트림에서 첫 번째 1이 나올 때까지 0을 읽고 개수를 센다. 이 0의 개수를 L이라고 한다.
# 1을 정수의 첫 번째 숫자로 간주하고, 값은 2^L이다. 정수의 나머지 L 비트를 읽는다. 이 정수를 N+1이라 하고, 1을 빼서 N을 구한다.
# 최종 출력의 첫 번째 자리에 1을 넣고, 값은 2^N이다.
# 다음 N 비트를 읽고 추가한다.

예시: 001010011

1. 선행 0이 001에 2개
2. 2개의 비트를 더 읽는다. (00101)
3. N+1 = 00101 = 5
4. N = 5 - 1 = 4, 전체 코드에 대한 나머지 비트는 '0011'
5. 인코딩된 숫자 = 2⁴ + 3 = 19

3. 디코딩

엘리아스 델타 부호화된 정수를 디코딩하는 과정은 다음과 같다.

1. 처음 0 비트의 개수(lengthOfLen)를 센다.
2. lengthOfLen개의 비트를 읽어 len을 계산한다. (len은 초기값 1에서 시작하여, 비트를 읽을 때마다 왼쪽으로 시프트하고, 읽은 비트가 1이면 1을 더한다.)
3. len - 1개의 비트를 읽어 num을 계산한다. (num은 초기값 1에서 시작하여, 비트를 읽을 때마다 왼쪽으로 시프트하고, 읽은 비트가 1이면 1을 더한다.)
4. 최종적으로 계산된 num이 디코딩된 정수 값이다.

이 과정을 반복하여 모든 정수를 디코딩한다.

4. 부호화 예시

5. 일반화

일라이어스 델타 부호는 기본적으로 양의 정수만을 부호화할 수 있다. 하지만, 다음과 같은 방법을 통해 0 또는 음의 정수도 부호화할 수 있도록 확장할 수 있다.

일라이어스 델타 부호는 0 또는 음의 정수를 부호화하지 않는다. 모든 음이 아닌 정수를 부호화하는 한 가지 방법은 부호화 전에 1을 더하고 디코딩 후에 1을 빼는 것이다. 모든 정수를 부호화하는 한 가지 방법은 모든 정수(0, 1, −1, 2, −2, 3, −3, ...)를 부호화 전에 엄격하게 양의 정수(1, 2, 3, 4, 5, 6, 7, ...)에 매핑하는 전단사 함수를 설정하는 것이다. 이 전단사 함수는 프로토콜 버퍼의 "지그재그" 부호화를 사용하여 수행할 수 있다. (지그재그 부호 또는 JPEG 지그재그 엔트로피 부호화와 혼동하지 않도록 한다.)

5.1. 0 또는 음의 정수 부호화

일라이어스 델타 부호는 0 또는 음의 정수를 부호화하지 않는다. 모든 음이 아닌 정수를 부호화하는 한 가지 방법은 부호화 전에 1을 더하고 디코딩 후에 1을 빼는 것이다. 모든 정수를 부호화하는 한 가지 방법은 모든 정수(0, 1, −1, 2, −2, 3, −3, ...)를 부호화 전에 엄격하게 양의 정수(1, 2, 3, 4, 5, 6, 7, ...)에 매핑하는 전단사 함수를 설정하는 것이다. 이 전단사 함수는 프로토콜 버퍼의 "지그재그" 부호화를 사용하여 수행할 수 있다. (지그재그 부호 또는 JPEG 지그재그 엔트로피 부호화와 혼동하지 않도록 한다.)

6. C++ 코드 예시

6.1. 인코딩

일라이어스 델타 부호 인코딩은 다음과 같이 진행된다.

1. 숫자를 N이라고 한다.
2. N의 이진 표현의 비트수(길이)를 L이라고 한다.
3. L의 이진 표현의 비트수(길이)를 M이라고 한다.
4. M-1개의 0을 출력한다.
5. L을 이진수로 출력한다.
6. N의 이진 표현에서 최상위 비트(MSB)를 제외한 나머지 비트들을 출력한다.

C++를 사용한 일라이어스 델타 부호 인코딩 예제 코드는 다음과 같다.

```cpp
void eliasDeltaEncode(char* source, char* dest)
{
IntReader intreader(source);
BitWriter bitwriter(dest);
while (intreader.hasLeft())
{
int num = intreader.getInt();
int len = 0;
int lengthOfLen = 0;

len = 1 + floor(log2(num)); // calculate 1+floor(log2(num))
lengthOfLen = floor(log2(len)); // calculate floor(log2(len))

for (int i = lengthOfLen; i > 0; --i)
bitwriter.outputBit(0);
for (int i = lengthOfLen; i >= 0; --i)
bitwriter.outputBit((len >> i) & 1);
for (int i = len-2; i >= 0; i--)
bitwriter.outputBit((num >> i) & 1);
}
bitwriter.close();
intreader.close();
}

6.2. 디코딩

일라이어스 델타 부호의 디코딩은 C++ 코드로 구현할 수 있다.

```cpp
void eliasDeltaDecode(char* source, char* dest)
{
BitReader bitreader(source);
IntWriter intwriter(dest);
while (bitreader.hasLeft())
{
int num = 1;
int len = 1;
int lengthOfLen = 0;
while (!bitreader.inputBit()) // 잘못된 파일의 경우 잠재적으로 위험함.
lengthOfLen++;
for (int i = 0; i < lengthOfLen; i++)
{
len <<= 1;
if (bitreader.inputBit())
len |= 1;
}
for (int i = 0; i < len - 1; i++)
{
num <<= 1;
if (bitreader.inputBit())
num |= 1;
}
intwriter.putInt(num); // 값을 기록
}
bitreader.close();
intwriter.close();
}

7. 활용 분야

8. 추가 정보