Dlaczego ten kod jest unikalnie dekodowalny?

Alfabet źródłowy: $\{a, b, c, d, e, f\}$

Alfabet kodu: $\{0, 1\}$

$a\colon 0101$
$b\colon 1001$
$c\colon 10$
$d\colon 000$
$e\colon 11$
$f\colon 100$

Pomyślałem, że aby kod był unikalnie dekodowalny, musiał być bez prefiksów. Ale w tym kodzie słowo kodowe jest na przykład prefiksem słowa kodowego , więc nie jest wolne od prefiksu. Jednak mój podręcznik mówi mi, że jego odwrotność jest wolna od prefiksu (nie rozumiem tego), a zatem jest wyjątkowo dekodowalna. Czy ktoś może wyjaśnić, co to znaczy lub dlaczego jest wyjątkowo dekodowalne? Wiem, że zaspokaja nierówność Krafta, ale jest to tylko warunek konieczny, a nie wystarczający. $c$ $f$

encoding-scheme 2000moliver
źródło

Bez prefiksu oznacza jednoznacznie dekodowalne, ale że nie jest to instrukcja „jeśli i tylko jeśli”. Zobacz na przykład tutaj .

dkaeae

Okay, rozumiem, ale moja książka tekstowa mówi: Kod A jest wyjątkowo dekodowalny, ponieważ jego rewers jest prefiksowy, a więc wyjątkowo dekodowalny Czy rozumiesz, co rozumieją przez jego odwrotność?

2000moliver

Prawdopodobnie po prostu kod uzyskany przez odwrócenie wszystkich słów kodowych.

dkaeae

i dlaczego to oznacza jednoznacznie dekodowalne, nie rozumiem

2000mroliver

cmoże być prefiksem bi f, ale pozostałe przyrostki nie istnieją w kodzie. Po odwróceniu kodu sufiksy stają się prefiksami, a następnie stają się wolne od prefiksów.

Barmar

Odpowiedzi:

Twój kod ma właściwość polegającą na tym, że jeśli odwrócisz wszystkie słowa kodowe, otrzymasz kod prefiksu. Oznacza to, że Twój kod jest jednoznacznie dekodowalny.

Rzeczywiście, rozważ dowolny kod którego odwrotne jest jednoznacznie dekodowalne. Twierdzę, że jest również wyjątkowo dekodowalny. Wynika to z tego, że Słowami, dekompozycje język słów kodowych są odpowiednio jeden do jednego z dekompozycje na słowa kodowe o . Ponieważ te ostatnie są wyjątkowe, tak samo są te pierwsze. $C = x_1,\ldots,x_n$ $C^R := x_1^R,\ldots,x_n^R$ $C$

w = x_{i_{1}} \dots x_{i_{m}} if and only if w^{R} = x_{i_{m}}^{R} \dots x_{i_{1}}^{R} .

$w = x_{i_1} \ldots x_{i_m} \text{ if and only if } w^R = x_{i_m}^R \ldots x_{i_1}^R.$

w

$w$

C

$C$

w^{R}

$w^R$

C^{R}

$C^R$

Ponieważ kody prefiksów są jednoznacznie dekodowane, wynika z tego, że rewers kodu prefiksu jest również jednoznacznie dekodowalny. Tak jest w twoim przykładzie.

Nierówność McMillana stwierdza, że jeśli można jednoznacznie zdekodować, to Innymi słowy, unikalnie dekodowalny kod spełnia nierówność Krafta. Dlatego jeśli wszystko, co Cię interesuje, to zminimalizowanie oczekiwanej długości słowa kodowego, nie ma powodu, aby szukać poza kodami prefiksów. $C$

\sum_{i = 1}^{n} 2^{- | x_{i} |} \leq 1.

$\sum_{i=1}^n 2^{-|x_i|} \leq 1.$

Sam Roweis podaje w swoich slajdach dobry przykład unikalnie dekodowalnego kodu, który nie jest ani kodem prefiksu, ani odwrotnością kodu prefiksu: Aby pokazać, że ten kod jest jednoznacznie dekodowalny, wystarczy pokazać, jak zdekodować pierwsze słowo kodowe słowa. Jeśli słowo zaczyna się od , to pierwsze słowo kodowe to . Jeśli ma postać , musi mieć wartość lub . W przeciwnym razie musi istnieć prefiks formularza . Rozróżniamy teraz kilka przypadków:

0, 01, 110.

$0,01,110.$

1

$1$

110

$110$

01^{*}

$01^*$

0

$0$

01

$01$

01^{*} 0

$01^*0$

\begin{array}{ccccc} prefix & 00 & 010 & 0110 & 01110 \\ codeword & 0 & 01 & 0 & 01 \end{array}

$\begin{array}{c|cccc} \text{prefix} & 00 & 010 & 0110 & 01110 \\\hline \text{codeword} & 0 & 01 & 0 & 01 \end{array}$ Dłuższe nie mogą być w ogóle dekodowanym.

1

$1$

Yuval Filmus
źródło

Na przykład wydaje się, że w PO jest, nie możemy rozszyfrować pierwszego słowa kodowego po ustalonej ilości cyfr, istnieje nieskończenie wiele przypadków: 1001010101010101…może być fcccccc…albo caaa…i może musimy poczekać do końca wejścia na decyzję.

Bergi

Dzieje się tak również w przypadku .

1, 10, 00

$1,10,00$

Yuval Filmus

@ Bergi Jest zawsze dekodowalny dla dowolnej skończonej liczby cyfr. Zawsze jest tylko jeden sposób na dekodowanie kodowania bez żadnych pozostałości. Każda inna próba zakończy się zapasowymi 1 lub 0. Wynika to z faktu, że kod jest unikalnie dekodowalny, jeśli najpierw go przeczytamy Teoretycznie, jeśli coś jest jednoznacznie dekodowalne w jednym kierunku, nie ma sensu, że może być więcej niż jedno rozwiązanie w drugim kierunku

Slebetman

@slebetman Miałem na myśli skończony przedrostek (z możliwymi pozostałymi częściami). Tak, jeśli weźmiemy cały wkład, zawsze można go rozszyfrować.

Bergi

Jeśli dam ci jakąś wiadomość, którą chcesz zdekodować, możesz wykonać następujące czynności: Odwróć wiadomość, zaczynając od ostatniego bitu zamiast pierwszego bitu. Odwróć słowa kodowe. Dekoduj wiadomość. Odwróć dekodowany ciąg.

Możesz to zrobić, ponieważ po odwróceniu sześciu słów kodowych otrzymasz kod bez prefiksu: 1010, 1001, 01, 000, 11, 001 jest wolny od prefiksów.

gnasher729
źródło

Jeśli bez prefiksu oznacza to, co myślę, odwrotność „a” zaczyna się od 1, 10 lub 101, z których żaden nie jest żadnym innym poprawnym kodem.

Dlatego jeśli komunikat kończy się na 0101, może być tylko „a” i można zastosować podobną logikę do poprzednich bitów.

Co jednak, jeśli nie ma końca, aby zacząć? Cóż, jeśli pierwszy bit to 1, wiesz, że to nie jest „a” ani „d”. Drugi bit wyeliminuje „e” lub {„b”, „c”, „f”}. Trzeci bit może sprowadzić go do jednego wyboru, ale jeśli nie, jest unikalny pod czwartym bitem.

Gdy tylko dojdziesz do unikalnej sekwencji, ponownie uruchom algorytm na następnym bicie.

WGroleau
źródło