Obcięte kodowanie binarne
Obcięte kodowanie binarne to kodowanie entropijne, zwykle używane do jednolitych rozkładów prawdopodobieństwa ze skończonym alfabetem. Jest sparametryzowany alfabetem o łącznej wielkości liczby n . Jest to nieco bardziej ogólna forma kodowania binarnego , gdy n nie jest potęgą dwójki .
Jeśli n jest potęgą dwójki, to zakodowana wartość dla 0 ≤ x < n jest prostym kodem binarnym dla x o długości log 2 ( n ). W przeciwnym razie niech k = podłoga(log 2 ( n )), tak że 2 k < n < 2 k +1 i niech u = 2 k +1 − n .
Skrócone kodowanie binarne przypisuje pierwszym symbolom u słów kodowych o długości k , a następnie przypisuje pozostałym symbolom n - u ostatnie słowa kodowe n - u o długości k + 1. Ponieważ wszystkie słowa kodowe o długości k + 1 składają się z nieprzypisanego słowa kodowego o długości k z dodaną cyfrą „0” lub „1” wynikowy kod jest kodem prefiksu .
Historia
Używane od co najmniej 1984 r. kody fazowe , znane również jako kody ekonomiczne , są również znane jako obcięte kodowanie binarne.
Przykład z n = 5
Na przykład dla alfabetu {0, 1, 2, 3, 4} n = 5 i 2 2 ≤ n < 2 3 , stąd k = 2 i u = 2 3 − 5 = 3. Skrócone kodowanie binarne przypisuje pierwsze u symbolizuje słowa kodowe 00, 01 i 10, wszystkie o długości 2, a następnie przypisuje ostatnie n - symbole u symboli słów kodowych 110 i 111, dwa ostatnie słowa kodowe o długości 3.
Na przykład, jeśli n wynosi 5, zwykłe kodowanie binarne i obcięte kodowanie binarne przydziela następujące słowa kodowe . Cyfry pokazane jako przekreślone nie są przesyłane w obciętym formacie binarnym.
|
Obcięty plik binarny |
Kodowanie |
Standardowy plik binarny |
||
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | |
| 1 | 0 | 1 | 1 | |
| 2 | 1 | 0 | 2 | |
| NIE UŻYWANY | 3 | |||
| NIE UŻYWANY | 4 | |||
| NIE UŻYWANY | 5/NIEUŻYWANE | |||
| 3 | 1 | 1 | 0 | 6/NIEUŻYWANE |
| 4 | 1 | 1 | 1 | 7/NIEUŻYWANE |
Zakodowanie n przy użyciu prostego kodowania binarnego zajmuje 3 bity, stąd 2 3 − n = 8 − 5 = 3 są nieużywane.
W kategoriach liczbowych, aby wysłać wartość x , gdzie 0 ≤ x < n , i gdzie jest 2 k ≤ n < 2 k +1 symboli, istnieje u = 2 k +1 − n niewykorzystanych wpisów, gdy rozmiar alfabetu jest zaokrąglony do najbliższej potęgi dwójki. Proces kodowania liczby x w obciętym systemie binarnym jest następujący: jeśli x jest mniejsze niż u , zakoduj ją w k bitach binarnych; jeśli x jest większe lub równe u , zakoduj wartość x + u w k + 1 bitach binarnych.
Przykład z n = 10
Inny przykład, kodowanie alfabetu o rozmiarze 10 (między 0 a 9) wymaga 4 bitów, ale jest 2 4 - 10 = 6 niewykorzystanych kodów, więc wartości wejściowe mniejsze niż 6 mają pierwszy bit odrzucony, podczas gdy wartości wejściowe większe lub równe do 6 są przesunięte o 6 do końca przestrzeni binarnej. (Niewykorzystane wzory nie są pokazane w tej tabeli).
|
Wprowadź wartość |
Zrównoważyć | Wartość przesunięcia |
Standardowy plik binarny |
Obcięty plik binarny |
|---|---|---|---|---|
| 0 | 0 | 0 |
|
000 |
| 1 | 0 | 1 |
|
001 |
| 2 | 0 | 2 |
|
010 |
| 3 | 0 | 3 |
|
011 |
| 4 | 0 | 4 |
|
100 |
| 5 | 0 | 5 |
|
101 |
| 6 | 6 | 12 | 0110 | 1100 |
| 7 | 6 | 13 | 0111 | 1101 |
| 8 | 6 | 14 | 1000 | 1110 |
| 9 | 6 | 15 | 1001 | 1111 |
Aby zdekodować, przeczytaj pierwsze k bitów. Jeśli zakodują wartość mniejszą niż u , dekodowanie jest zakończone. W przeciwnym razie przeczytaj dodatkowy bit i odejmij u od wyniku.
Przykład z n = 7
Oto bardziej ekstremalny przypadek: przy n = 7 następną potęgą 2 jest 8, więc k = 2 i u = 2 · 3 - 7 = 1:
|
Wprowadź wartość |
Zrównoważyć | Wartość przesunięcia |
Standardowy plik binarny |
Obcięty plik binarny |
|---|---|---|---|---|
| 0 | 0 | 0 |
|
00 |
| 1 | 1 | 2 | 001 | 010 |
| 2 | 1 | 3 | 010 | 011 |
| 3 | 1 | 4 | 011 | 100 |
| 4 | 1 | 5 | 100 | 101 |
| 5 | 1 | 6 | 101 | 110 |
| 6 | 1 | 7 | 110 | 111 |
Ten ostatni przykład pokazuje, że wiodący bit zerowy nie zawsze oznacza krótki kod; jeśli u < 2 k , niektóre długie kody będą zaczynać się od bitu zerowego.
Prosty algorytm
Wygeneruj skrócone kodowanie binarne dla wartości x , 0 ≤ x < n , gdzie n > 0 to rozmiar alfabetu zawierającego x . n nie musi być potęgą dwójki.
0
string TruncatedBinary ( int x , int n ) { // Ustaw k = floor(log2(n)), tj. k takie, że 2^k <= n < 2^(k+1). int k = , t = n ; podczas gdy ( t > 1 ) { k ++ ; t >>= 1 ; } // Ustaw u na liczbę nieużywanych słów kodowych = 2^(k+1) - n. int u = ( 1
<< k + 1 ) - n ; if ( x < u ) powrót Binarny ( x , k ); w przeciwnym razie zwróć Binarny ( x + u , k + 1 )); }
Rutynowy plik binarny ma charakter ekspozycyjny; zwykle pożądane są tylko skrajne prawe bity długości zmiennej x . Tutaj po prostu wyprowadzamy kod binarny dla x za pomocą len bitów, dopełniając zerami wysokiego rzędu, jeśli to konieczne.
0
string Binarny ( int x , int len ) { string s = "" ; podczas gdy ( x ! = ) { jeśli ( parzyste ( x )) s = '0' + s ; inaczej s = '1' + s ; x >>= 1 ; } podczas (
s . Długość < długość ) s = '0' + s ; zwróć s ; }
O wydajności
Jeśli n nie jest potęgą dwójki, a symbole k -bitowe są obserwowane z prawdopodobieństwem p , to symbole ( k + 1)-bitowe są obserwowane z prawdopodobieństwem 1 − p . Możemy obliczyć oczekiwaną liczbę bitów na symbol
Surowe kodowanie symbolu ma bity Wtedy względna oszczędność miejsca s (patrz Współczynnik kompresji danych ) kodowania może być zdefiniowana jako
W uproszczeniu to wyrażenie prowadzi do
że względna wydajność obciętego kodowania binarnego wzrasta wraz ze wzrostem prawdopodobieństwa p k -bitowych symboli , a symbolu kodowania surowego maleje.
