골롬 부호화

Golomb coding

골롬 부호화는 1960년대에 Solomon W. Golomb에 의해 발명된 데이터 압축 코드 패밀리를 사용하는 무손실 데이터 압축 방법입니다.기하학적 분포에 이은 알파벳은 최적의 프리픽스 [1]코드로서 골롬 코드를 가지기 때문에 골롬 부호화는 큰 값보다 입력 스트림에서 작은 값이 발생할 가능성이 큰 상황에 매우 적합합니다.

쌀 코딩

코딩(Robert F. 발명) 라이스)는 골롬 코드 패밀리의 서브셋을 사용하여 보다 단순하지만 최적이 아닌 프레픽스 코드를 생성하는 것을 의미한다.Rice는 적응 부호화 체계에서 이 코드 집합을 사용했다. "Rice coding"은 적응 체계 또는 골롬 부호의 하위 집합을 사용할 수 있다.Golomb 코드에는 임의의 양의 정수 값을 지정할 수 있는 조정 가능한 파라미터가 있는 반면 Rice 코드는 조정 가능한 파라미터가 2의 거듭제곱인 파라미터입니다.이것은 2진수 산술에서 곱셈과 2로 나누기를 보다 효율적으로 구현할 수 있기 때문에 라이스 코드를 컴퓨터에서 사용하기 편리합니다.

Rice는 기하학적 분포가 시간에 따라 종종 정확하게 알려지지 않거나 둘 다에 따라 변하기 때문에 이 단순한 하위 집합을 제안하도록 동기를 부여받았다. 따라서 겉으로 보기에 최적의 코드를 선택하는 것은 그다지 유리하지 않을 수 있다.

부호화는 다수의 무손실 화상 압축오디오 데이터 압축 방법에서 엔트로피 부호화 단계로서 사용된다.

개요

M = 3인 골롬 코드를 사용하여 모수 p(0) = 0.2인 기하 분포의 소스 x에 대한 골롬 부호화 예제입니다.2비트 코드 00은 20%, 3비트 코드 010, 011 및 100은 38% 이상 사용됩니다.소수의 경우 4비트 이상이 필요합니다.이 소스의 경우 엔트로피 = 3.610 비트, 이 소스를 사용하는 이 코드의 경우 속도 = 3.639 비트입니다. 따라서 이중화 = 0.030 비트 또는 효율성 = 0.992 비트/비트입니다.

코드의 구축

골롬 부호화는 조정 가능한 파라미터 M을 사용하여 입력값 x를 M으로 나눈 결과 q와 나머지 r의 두 부분으로 나눈다.몫은 단항 부호화로 전송되고 나머지는 잘린 이진 부호화로 전송됩니다.M {\ M일 때 골롬 부호화는 단항 부호화와 동일합니다.

골롬-쌀 코드는 (q)의 위치와 빈(r) 내의 오프셋으로 숫자를 나타내는 코드라고 할 수 있습니다.그림 예시는 골롬-라이스 매개변수 M = 3을 사용하여 정수 x의 부호화에 대한 위치 q와 오프셋 r을 나타내며, 소스 확률은 p(0) = 0.2의 기하 분포를 따른다.

형식적으로 두 부분은 다음 식에 의해 지정됩니다.여기서 x는 부호화되는 음이 아닌 정수입니다.

그리고.

- M({ r
이 이미지는 1 - p(0) 0 0.45에 대해 M이 최적으로 선택되었을 때 골롬 코드의 용장성을 비트 단위로 나타내고 있습니다.

만약 r< 둘 다 q, r라이스 코드에 대해서는 b비트, 또는 b와 b+1비트 사이에 골룸 부호(2의 i.e. M이 아닌 것은 힘)에 대한 선택에 의해 비트 변수 번호:단항 코드에서 q, r을 사용하여, b)⌊ 로그 2⁡(M)⌋{\displaystyle b=\lfloor \log_{2}(M)\rfloor}.;2b+1− M{\displaystyle r<, 2^{b+1}-M}, 인코딩될 것이다.사용 bbits to encode r, b+1 bits to encode r. M이 2의 거듭제곱이고 r의 모든 값을 b 비트로 인코딩할 수 있는 경우 = 2 ( M) { b _ {2} (M ) 。

Golomb에 의해 처리된 정수 x는 0부터 시작하는 기하학적 분포를 갖는 Bernouli 공정의 런 길이입니다.매개 변수 M의 최선의 선택은 해당 베르누이 프로세스의 함수이며, 이는 주어진 베르누이 시행에서 성공 확률을 p ( ) { p= 매개 변수화됩니다.M은 분포의 중위수 또는 중위수 ±1입니다.이는 다음과 같은 부등식에 의해 결정될 수 있다.

에 의해 해결된다.

"- " ( - ) "( - )"" { \ M = \ \ { \ \( 2 - p ) } { \ log ( 1 - p ) } \ \ }

p(0) = 0.2인 예제의 경우:

" - log ( . ) 6 ( . ) 2 . 3 { \ M = \\ { \ { \ . 8 ) } { \ \ .6 \

소스 값의 무한 집합에 대한 허프만 코드를 계산할 수 있는 경우, 이 분포의 골롬 코드는 동일한 확률에 대한 허프만 코드와 동일합니다.

부호 있는 정수와 함께 사용

골롬의 계획은 음수가 아닌 숫자의 시퀀스를 인코딩하도록 설계되었다.단, 오버랩 및 인터리브 방식을 사용하여 음수가 포함된 시퀀스를 받아들이도록 쉽게 확장할 수 있습니다.이 방식에서는 모든 값이 고유하고 가역적인 방법으로 어떤 양의 번호로 재할당됩니다.시퀀스 시작: 0, -1, 1, -2, 2, -3, 3, -4, 4...n개의 음수 값( - n -th n개th 홀수( - 1에 매핑되고 mth 양수 값은 mth 짝수(\에 매핑됩니다.이는 수학적으로 다음과 같이 표현될 수 있습니다. 양의 값 x는 ( x , 0 ( \ ^ { \ } = 2 \ 0 )에 매핑되고 의 값 y는( - y -1 ,1 )에 이러한 코드는, 최적이 아닌 경우라도, 심플화를 위해서 사용할 수 있습니다.양면 기하 분포에 대한 진정한 최적 코드에는 분포 모수에 따라 이 코드를 [2]포함한 여러 변형 골롬 코드가 포함됩니다.

단순 알고리즘

아래는 라이스-골롬 부호화입니다.여기서 나머지 코드는 "Rice coding"이라고도 불리는 단순 잘린 이진 부호화를 사용합니다(산술이나 허프만 부호화와 같은 다른 가변 길이 이진 부호화는 나머지 코드에 대해 가능합니다). 나머지 코드의 통계 분포가 평평하지 않은 경우, 특히 모든 것이 가능하지 않은 경우,분할 사용 후 잔여물).이 알고리즘에서는 M 파라미터가 2의 거듭제곱일 경우 단순한 Rice 부호화와 동등해집니다.

  1. 파라미터 M을 정수값으로 고정한다.
  2. N의 경우 부호화할 번호를 찾습니다.
    1. 몫 = q = 바닥(N/M)
    2. 나머지 = r = N 모듈로 M
  3. 코드워드 생성
    1. 코드 형식: <쿼티언트 코드><리머 코드>, 여기서
    2. 몫 코드(단항 부호화)
      1. 1비트의 q-length 문자열을 씁니다(또는 0비트).
      2. 0비트 쓰기(각각 1비트)
    3. 나머지 코드(잘린 이진 인코딩)
      1. b 2 { b = \ \ _ { ) \ .
        1. < b + - { r < ^ { + } - }코드 r 이 b 비트를 사용한 바이너리 표현일 경우.
        2. r b + - r 2 코드일 경우 + b + -M(\ r b + 1비트를 사용하여 이진 표현됩니다.

M = 10으로 설정합니다. b 2 { b = \ \ _ } ( ) \ 컷오프는 2 + - - ({ 2 입니다.

몫 부품의 부호화
q 출력 비트
0 0
1 10
2 110
3 1110
4 11110
5 111110
6 1111110
N
나머지 부분의 인코딩
r 오프셋 바이너리 출력 비트
0 0 0000 000
1 1 0001 001
2 2 0010 010
3 3 0011 011
4 4 0100 100
5 5 0101 101
6 12 1100 1100
7 13 1101 1101
8 14 1110 1110
9 15 1111 1111

예를 들어 파라미터 M = 10을 사용하는 Rice-Golomb 부호화의 경우 10진수 42는 처음에 q = 4 r = 2로 분할되어 qcode(q), rcode(r) = qcode(4), rcode(2) = 11110,010으로 부호화됩니다(q 스트림의 출력의 에서 구분 콤마를 부호화할 필요가 없습니다).ins; qcode와 rcode는 모두 자기 인증됩니다).


런타임 인코딩에 사용

p와 1 p는 이전 섹션의 사용법과 비교하여 이 섹션에서는 반대입니다.

P와 (1 - p)의 확률이 각각 p와 (1 - p)인 2개의 심볼의 알파벳 또는 2개의 이벤트 세트(p ≤ 1/2)가 주어지면 골롬 부호화는 단일 Q로 구분된 0개 이상의 P'의 실행을 부호화하기 위해 사용할 수 있습니다.이 응용 프로그램에서는 파라미터 M의 최적 설정은 2{\{\ _에 가장 가까운 정수입니다.p = 1/2, M = 1일 때 골롬 코드는 단수(n0 P s 뒤에 0 P s가 이어 0)로 부호화됩니다.보다 단순한 코드가 필요한 경우 Golomb-Rice 파라미터 b(즉, Golomb M (\M = 를 로그2에가장 가까운 정수 - p에 할당할 수 있습니다.다만, 통상 최적인 파라미터는 아닙니다.폼은 최적의 골롬 코드에 매우 가깝습니다.(Rice 자신이 동일한 데이터에 대해 다양한 코드를 사용하여 어떤 것이 가장 좋은지 결정할 것을 제안했습니다.이후 JPL 연구자는 코드 매개변수를 최적화하거나 추정하는 다양한 방법을 제안했다.)[3]

b비트를 가진 바이너리 부분에 Rice 코드를 사용하여 P의 확률p인 런렝스 부호화 시퀀스를 실행하는 것을 검토합니다.P[ -run의 of 경우 비트가 k비트 실행( \k -1 Ps and 1 Q ) 및( -run의 {\style 의 일부입니다.예상되는 압축비는 다음과 같습니다.

압축은 압축된비율인 [ ratio로 표현되는 경우가 많다.p1 { p \ 1}의 경우 런렝스 부호화 접근법에 의해 압축비가 엔트로피에 가깝습니다.예를 들어 쌀 b b을 p =.({ p= 사용하면 91.89%의 압축률이 나오지만 엔트로피 한계는 91.92%입니다.

적응형 런렝스 Golomb-Rice 부호화

정수의 확률 분포를 알 수 없는 경우 Golomb-Rice 인코더의 최적 파라미터를 결정할 수 없습니다.따라서 많은 애플리케이션에서 2패스 방식을 사용합니다. 첫째, 데이터 블록을 스캔하여 데이터의 확률 밀도 함수(PDF)를 추정합니다.그런 다음 Golomb-Rice 매개변수는 추정된 PDF에서 결정된다.이 접근방식의 단순한 변형은 PDF가 모수화된 계열에 속한다고 가정하고 데이터에서 PDF 매개변수를 추정하여 최적의 골롬-라이스 매개변수를 계산하는 것이다.이는 아래에서 설명하는 대부분의 애플리케이션에서 사용되는 접근법입니다.

PDF가 불분명한 정수 데이터를 효율적으로 부호화하기 위한 대체 접근법은 역적응형 인코더를 사용하는 것입니다.Run-length Golomb-Rice(RLGR) 코드는 마지막 부호화 심볼에 따라 Golomb-Rice 파라미터를 업 또는 다운으로 조정하는 매우 단순한 알고리즘을 사용하여 이를 실현합니다.디코더는 부호화 파라미터의 변동을 추적하기 위해 동일한 규칙을 따를 수 있으므로 부호화 데이터만 전송하면 된다.멀티미디어 코덱의 예측 오류 또는 변환 계수 등 데이터에서 볼 수 있는 광범위한 통계 정보를 포함하는 일반화된 가우스 PDF를 가정하면 RLGR 인코딩 알고리즘은 이러한 애플리케이션에서 매우 잘 수행할 수 있습니다.

적용들

골롬 코드 쌀 알고리즘 실험 압축비

많은 신호 코덱이 예측 잔류물에 라이스 코드를 사용합니다.예측 알고리즘에서, 그러한 잔류물은 큰 잔류물보다 더 빈번하게 발생하는 양면 기하학적 분포로 떨어지는 경향이 있으며, 라이스 코드는 허프만 테이블을 전송해야 하는 오버헤드 없이 그러한 분포에 대한 허프만 코드에 근접한다.기하 분포와 일치하지 않는 신호는 사인파입니다. 왜냐하면 차분 잔류물은 값이 기하 분포를 생성하지 않는 사인파 신호를 생성하기 때문입니다(최고 잔류 값과 최저 잔류 값은 유사한 높은 발생 빈도를 가지며 중앙값의 양의 잔류물과 음의 잔류물만 더 자주 발생합니다).

Shorten,[4] FLAC,[5] Apple Lossless, MPEG-4 ALS 의 몇 가지 무손실 오디오코덱에서는 선형 예측 단계 후에 라이스 코드가 사용됩니다(Apple Lossless에서는 「adaptive FIR filter」라고 불립니다).쌀 코딩은 FELICS 무손실 이미지 코덱에서도 사용됩니다.

Golomb-Rice 코더는 Rice 알고리즘 기반의 무손실 이미지 코덱의 엔트로피 코딩 단계에서 사용됩니다.이러한 실험 중 하나는 표시된 압축비 그래프를 산출합니다.

JPEG-LS 방식에서는 Rice-Golomb을 사용하여 예측 잔차를 인코딩합니다.

위에서 설명한 RLGR(Run-length Golomb-Rice) 적응형 버전의 Golomb-Rice 코딩은 Microsoft Remote Desktop Protocol의 RemoteFX 구성 요소에서 가상 시스템의 화면 콘텐츠를 인코딩하는 데 사용됩니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Gallager, R. G.; van Voorhis, D. C. (1975). "Optimal source codes for geometrically distributed integer alphabets". IEEE Transactions on Information Theory. 21 (2): 228–230. doi:10.1109/tit.1975.1055357.
  2. ^ Merhav, N.; Seroussi, G.; Weinberger, M. J. (2000). "Coding of sources with two-sided geometric distributions and unknown parameters". IEEE Transactions on Information Theory. 46 (1): 229–236. doi:10.1109/18.817520.
  3. ^ Kiely, A. (2004). Selecting the Golomb Parameter in Rice Coding (Technical report). Jet Propulsion Laboratory. 42-159.
  4. ^ "man shorten". Archived from the original on 2014-01-30. Retrieved 2008-12-07.
  5. ^ FLAC 매뉴얼: 포맷의 개요

추가 정보