맨위로가기

일라이어스 델타 부호

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

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

더 읽어볼만한 페이지

  • 무손실 압축 알고리즘 - VP9
    VP9는 구글이 개발한 오픈 소스 비디오 코덱으로, VP8보다 압축 효율을 높이고 HEVC보다 나은 성능을 목표로 개발되었으며, WebM 형식으로 사용되고 주요 웹 브라우저와 넷플릭스, 유튜브 등에서 지원했으나 AV1의 등장으로 개발이 중단되었다.
  • 무손실 압축 알고리즘 - FLAC
    FLAC은 조시 콜슨이 개발한 무손실 오디오 코덱으로, 원본 음질을 유지하면서 파일 크기를 줄이기 위해 오디오 데이터를 압축하며, 4~32비트 샘플 크기, 최대 8 채널을 지원하고, 미국 국립 문서 기록 관리청에서 디지털 오디오에 선호되는 형식으로 지정되었다.
  • 기수법 - 이진법
    이진법은 0과 1 두 개의 숫자를 사용하는 밑이 2인 위치 기수법으로, 컴퓨터 과학의 기초가 되었으며 현대 컴퓨터에서 데이터를 저장하고 처리하는 데 사용된다.
  • 기수법 - 구진법
    구진법은 9를 밑으로 하는 위치 기수법으로 0부터 8까지의 숫자를 사용하여 수를 나타내며, 3의 배수 표현이 간결하고 3의 역수는 유한소수로 표현되는 특징이 있다.
일라이어스 델타 부호
개요
유형무손실 데이터 압축
개발자피터 이라이어스
발표1975년
속성
엔트로피 코딩유니버설 부호화
가족일라이어스 부호
선행 부호예
세부 정보
사용처정수 부호화

2. 부호화 원리

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

# ''N'' = ⌊log2 ''X''⌋를 계산한다. 즉, ''X''에서 2의 가장 높은 거듭제곱을 구한다 (2''N'' ≤ ''X'' < 2''N''+1).

# ''L'' = ⌊log2(''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를 나타내기 위해 \lfloor \log_2(x) \rfloor + 2 \lfloor \log_2 (\lfloor \log_2(x) \rfloor +1) \rfloor + 1 비트를 사용한다. 이는 엘리아스 감마 코딩보다 적은 비트를 사용하여 매우 큰 정수를 표현할 때 유용하다.

숫자NN+1δ 인코딩암시된 확률
1 = 200111/2
colspan=5|
2 = 21 + 0120 1 0 01/16
3 = 21 + 1120 1 0 11/16
colspan=5|
4 = 22 + 0230 1 1 001/32
5 = 22 + 1230 1 1 011/32
6 = 22 + 2230 1 1 101/32
7 = 22 + 3230 1 1 111/32
colspan=5|
8 = 23 + 03400 1 00 0001/256
9 = 23 + 13400 1 00 0011/256
10 = 23 + 23400 1 00 0101/256
11 = 23 + 33400 1 00 0111/256
12 = 23 + 43400 1 00 1001/256
13 = 23 + 53400 1 00 1011/256
14 = 23 + 63400 1 00 1101/256
15 = 23 + 73400 1 00 1111/256
colspan=5|
16 = 24 + 04500 1 01 00001/512
17 = 24 + 14500 1 01 00011/512


2. 1. 단계별 부호화 방법

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

# ''N'' = ⌊log2 ''X''⌋를 계산한다. 즉, ''X''에서 2의 가장 높은 거듭제곱을 구한다 (2''N'' ≤ ''X'' < 2''N''+1).

# ''L'' = ⌊log2(''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를 나타내기 위해 \lfloor \log_2(x) \rfloor + 2 \lfloor \log_2 (\lfloor \log_2(x) \rfloor +1) \rfloor + 1 비트를 사용한다. 이는 엘리아스 감마 코딩보다 적은 비트를 사용하여 매우 큰 정수를 표현할 때 유용하다.

숫자NN+1δ 인코딩암시된 확률
1 = 200111/2
colspan=5|
2 = 21 + 0120 1 0 01/16
3 = 21 + 1120 1 0 11/16
colspan=5|
4 = 22 + 0230 1 1 001/32
5 = 22 + 1230 1 1 011/32
6 = 22 + 2230 1 1 101/32
7 = 22 + 3230 1 1 111/32
colspan=5|
8 = 23 + 03400 1 00 0001/256
9 = 23 + 13400 1 00 0011/256
10 = 23 + 23400 1 00 0101/256
11 = 23 + 33400 1 00 0111/256
12 = 23 + 43400 1 00 1001/256
13 = 23 + 53400 1 00 1011/256
14 = 23 + 63400 1 00 1101/256
15 = 23 + 73400 1 00 1111/256
colspan=5|
16 = 24 + 04500 1 01 00001/512
17 = 24 + 14500 1 01 00011/512


2. 2. 간략화된 부호화 방법

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

# ''N'' = ⌊log2 ''X''⌋ 즉, ''X''에서 2의 가장 높은 거듭제곱을 구한다. (2''N'' ≤ ''X'' < 2''N''+1)

# ''L'' = ⌊log2(''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를 나타내기 위해 \lfloor \log_2(x) \rfloor + 2 \lfloor \log_2 (\lfloor \log_2(x) \rfloor +1) \rfloor + 1 비트를 사용한다. 이는 엘리아스 감마 코딩을 사용할 때보다 큰 정수에 유용하다.

숫자NN+1δ 인코딩암시된 확률
1 = 200111/2
colspan=5|
2 = 21 + 0120 10 01/16
3 = 21 + 1120 10 11/16
colspan=5|
4 = 22 + 0230 11 001/32
5 = 22 + 1230 11 011/32
6 = 22 + 2230 11 101/32
7 = 22 + 3230 11 111/32
colspan=5|
8 = 23 + 03400 100 0001/256
9 = 23 + 13400 100 0011/256
10 = 23 + 23400 100 0101/256
11 = 23 + 33400 100 0111/256
12 = 23 + 43400 100 1001/256
13 = 23 + 53400 100 1011/256
14 = 23 + 63400 100 1101/256
15 = 23 + 73400 100 1111/256
colspan=5|
16 = 24 + 04500 101 00001/512
17 = 24 + 14500 101 00011/512



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

# 스트림에서 첫 번째 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. 인코딩된 숫자 = 24 + 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. 추가 정보


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com