일라이어스 오메가 부호

일라이어스 오메가 부호(Elias omega code)는 양의 정수를 대응시키는 범용 부호이다. 피터 일라이어스가 1975년 논문에서 소개했으며, 일라이어스 감마 부호와 일라이어스 델타 부호와 같이 숫자의 크기(자릿수)를 부호화해서 앞에 덧붙이는 방식을 쓴다. 하지만 감마 및 델타 부호와는 달리 오메가 부호는 이 과정에서 자기 자신을 재귀적으로 사용한다. 따라서 종종 재귀 일라이어스 부호라고 불리기도 한다.

오메가 부호로 부호화하는 과정은 다음과 같다.

1. 부호화될 숫자가 1이 아니면 숫자를 이진법으로 표현해서 적는다.
2. 위의 과정을 부호화될 숫자가 1이 될 때까지 반복한다. 새 숫자는 이전에 부호화된 숫자의 자릿수 - 1이 된다.
3. 마지막에 0을 덧붙인다.

오메가 부호를 복호화하는 과정은 다음과 같다.

1. 변수 N을 1으로 놓는다.
2. 읽은 비트가 0이면 중단하고, 아니면 그 뒤의 N자리를 읽어서 맨 처음의 1과 함께 이진법으로 해석한 값을 새 N으로 한다.
3. 이 과정을 0을 읽을 때까지 반복해서 나온 N이 복호화된 숫자이다.

오메가 부호로 표현된 첫 몇 개의 정수는 다음과 같다.

 1 = 0
 2 = 10 0
 3 = 11 0
 4 = 10 100 0
 5 = 10 101 0
 6 = 10 110 0
 7 = 10 111 0
 8 = 11 1000 0
 9 = 11 1001 0
10 = 11 1010 0
11 = 11 1011 0
12 = 11 1100 0
13 = 11 1101 0
14 = 11 1110 0
15 = 11 1111 0
16 = 10 100 10000 0
17 = 10 100 10001 0

참고 자료

• Elias, P. (1975). Universal code length sets and representations of integers. IEEE Trans. Inform. Theory, 21, 194--203.

같이 보기

• 일라이어스 감마 부호
• 일라이어스 델타 부호