골롬-라이스 부호 계산기

값 n을 매개변수 m으로 나눠 몫은 단항으로, 나머지는 이진으로 적습니다. 몫이 q라면 1을 q개 늘어놓고 0으로 끊은 뒤, 나머지를 이진으로 붙입니다. 예를 들어 m=4일 때 9는 몫 2, 나머지 1이므로 「110」 + 「01」이 됩니다.

라이스 부호는 m이 2의 거듭제곱인 골롬 부호입니다. 그때 나머지가 언제나 k = log₂m 비트라 나눗셈이 시프트로 끝나서, 하드웨어와 코덱이 이 경우만 쓰는 일이 많습니다. m이 2의 거듭제곱이 아니면 나머지를 절단 이진 부호로 적어 앞쪽 몇 개를 한 비트 짧게 씁니다.

값이 기하분포를 따를 때 θ = 1−p라 하면 m = ⌈−log(1+θ)/log θ⌉가 정확한 답입니다(갤러거–반부리스, 1975). 값의 평균 μ만 알고 있다면 p = 1/(μ+1)로 바꿔 넣으면 됩니다. 흔히 인용되는 m ≈ −1/log₂(1−p)는 이것의 근사인데, 대부분 같은 값을 주지만 p=0.4처럼 갈리는 자리가 있고 그때는 근사식 쪽이 최적이 아닙니다.

크게 손해입니다. m이 너무 작으면 몫이 커져 단항 부분이 길어지고, 너무 크면 나머지 비트가 낭비됩니다. 평균이 20쯤인 값에 m=1을 쓰면 값당 20비트를 넘고, m=512를 쓰면 나머지에만 9비트를 쓰게 됩니다. 최적 m 근처에 골짜기가 하나 있고, 이 계산기의 「m을 바꿔 가며」 표에서 그 모양을 볼 수 있습니다.

허프만은 어떤 분포에도 최적이지만 부호표가 필요하고, 골롬-라이스는 분포를 하나 가정하는 대신 표가 없습니다. 매개변수 m 하나만 주고받으면 되므로 값이 기하분포에 가까운 자료에서는 표를 실어 보내는 비용까지 따지면 골롬-라이스가 이깁니다. FLAC 같은 무손실 오디오와 이미지 예측 잔차가 그런 자료입니다.

그대로는 안 됩니다. 이 부호는 0 이상의 정수를 위한 것입니다. 실제 코덱은 음수를 지그재그로 옮겨(0, −1, 1, −2, 2 …를 0, 1, 2, 3, 4 …로) 0 이상으로 바꾼 뒤 넣습니다. 예측 잔차는 부호가 반씩 섞이므로 이 단계가 반드시 앞에 붙습니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.