Warum ist dieser Code eindeutig dekodierbar?

Quellalphabet: $\{a, b, c, d, e, f\}$

Code-Alphabet: $\{0, 1\}$

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

Ich dachte, dass ein Code, um eindeutig dekodierbar zu sein, Präfix-frei sein muss. In diesem Code ist das Codewort jedoch beispielsweise das Präfix von Codewort , sodass es nicht präfixfrei ist. Mein Lehrbuch sagt mir jedoch, dass seine Rückseite frei von Präfixen ist (ich verstehe das nicht) und daher eindeutig dekodierbar ist. Kann jemand erklären, was dies bedeutet oder warum es eindeutig dekodierbar ist? Ich weiß, dass es die Ungleichung von Kraft befriedigt, aber das ist nur eine notwendige Bedingung, keine ausreichende Bedingung. $c$ $f$

encoding-scheme 2000mroliver
quelle

Präfix-frei impliziert eindeutig dekodierbar, dass es sich jedoch nicht um eine "if and only if" -Anweisung handelt. Siehe zum Beispiel hier .

Dkaeae

Okay, ich verstehe, aber in meinem Lehrbuch steht: Code A ist eindeutig dekodierbar, da seine Rückseite vorwahlfrei und somit eindeutig dekodierbar ist. Verstehst du, was sie unter seiner Rückseite verstehen?

Wahrscheinlich einfach der Code, der durch Umkehren aller Codewörter erhalten wurde.

Dkaeae

und warum impliziert das eindeutig decodierbar, ich verstehe es nicht

2000mroliver

ckann ein Präfix von bund sein f, aber die verbleibenden Suffixe sind im Code nicht vorhanden. Wenn Sie den Code umkehren, werden Suffixe zu Präfixen und anschließend zu Präfixen.

Barmar

Antworten:

Ihr Code hat die Eigenschaft, dass Sie einen Präfixcode erhalten, wenn Sie alle Codewörter umkehren. Dies impliziert, dass Ihr Code eindeutig dekodierbar ist.

Betrachten Sie in der Tat jeden Code dessen Umkehrung eindeutig decodierbar ist. Ich behaupte, dass auch eindeutig dekodierbar ist. Dies liegt daran, dass In Worten, Zersetzungen von in Codewörter von sind in einer Eins-zu-Eins - Entsprechung mit Zerlegungen von in Codewörter von . Da letztere einzigartig sind, sind auch die ersteren einzigartig. $C = x_1,\ldots,x_n$ $C^R := x_1^R,\ldots,x_n^R$ $C$

w = x_{{ich}_{1}} \dots x_{{ich}_{m}} dann und nur dann, wenn w^{R} = x_{{ich}_{m}}^{R} \dots x_{{ich}_{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$

Da Präfixcodes eindeutig decodierbar sind, folgt, dass die Umkehrung eines Präfixcodes ebenfalls eindeutig decodierbar ist. Dies ist in Ihrem Beispiel der Fall.

Die McMillan-Ungleichung besagt, dass, wenn eindeutig dekodierbar ist, Mit anderen Worten, ein eindeutig dekodierbarer Code erfüllt Krafts Ungleichung. Wenn Sie also nur die erwartete Codewortlänge minimieren möchten, gibt es keinen Grund, über Präfixcodes hinauszuschauen. $C$

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

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

Sam Roweis gibt in seinen Folien ein schönes Beispiel für einen eindeutig dekodierbaren Code, der weder ein Präfixcode noch die Umkehrung eines Präfixcodes ist: Um zu zeigen, dass dieser Code eindeutig decodierbar ist, genügt es zu zeigen, wie das erste Codewort eines Wortes decodiert wird. Beginnt das Wort mit einer , ist das erste Codewort . Wenn es die Form , muss es entweder oder . Andernfalls muss ein Präfix der Form . Wir unterscheiden nun mehrere Fälle:

0, 01, 110.

$0,01,110.$

1

$1$

110

$110$

01^{*}

$01^*$

0

$0$

01

$01$

01^{*} 0

$01^*0$

\begin{array}{ccccc} Präfix & 00 & 010 & 0110 & 01110 \\ Codewort & 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}$ Längere Läufe von sind nicht möglich überhaupt dekodiert werden.

1

$1$

Yuval Filmus
quelle

Anscheinend können wir im Beispiel des OP das erste Codewort nach einer festgelegten Anzahl von Ziffern nicht decodieren. Es gibt unendlich viele Fälle: 1001010101010101…kann entweder fcccccc…oder sein caaa…, und wir müssen möglicherweise bis zum Ende der Eingabe warten, um zu entscheiden.

Bergi

Dies gilt auch für .

1, 10, 00

$1,10,00$

Yuval Filmus

@Bergi Es ist immer für eine endliche Anzahl von Ziffern decodierbar. Es gibt immer nur eine Möglichkeit, die Kodierung ohne Rest zu dekodieren. Jeder andere Versuch führt zu einer 1 oder einer 0. Dies liegt daran, dass der Code eindeutig dekodierbar ist, wenn wir ihn zuerst lesen. Wenn etwas in einer Richtung eindeutig dekodierbar ist, macht es theoretisch keinen Sinn, dass es in der anderen Richtung mehr als eine Lösung geben kann

slebetman

@slebetman Ich bezog mich auf ein endliches Präfix (mit möglichen Resten). Ja, wenn wir den gesamten Eingang nehmen, ist er immer dekodierbar.

Bergi

Wenn ich Ihnen eine Nachricht gebe, die Sie entschlüsseln sollen, können Sie Folgendes tun: Kehren Sie die Nachricht um, indem Sie mit dem letzten anstelle des ersten Bits beginnen. Kehren Sie die Codewörter um. Dekodiere die Nachricht. Kehre die dekodierte Zeichenfolge um.

Dies ist möglich, da Sie nach dem Umkehren der sechs Codewörter einen vorwahlfreien Code erhalten: 1010, 1001, 01, 000, 11, 001 ist vorwahlfrei.

gnasher729
quelle

Wenn Präfix-frei bedeutet, was ich denke, beginnt die Umkehrung von 'a' mit 1, 10 oder 101, von denen keiner ein anderer ganzer gültiger Code ist.

Wenn eine Nachricht mit 0101 endet, kann es sich daher nur um ein 'a' handeln, und Sie können ähnliche Logik auf die vorhergehenden Bits anwenden.

Was aber, wenn es kein Ende gibt, von dem man ausgehen kann? Wenn das erste Bit 1 ist, wissen Sie, dass es nicht 'a' oder 'd' ist. Das zweite Bit eliminiert 'e' oder {'b', 'c', 'f'}. Das dritte Bit könnte es auf eine Auswahl bringen, aber wenn nicht, ist es durch das vierte Bit eindeutig.

Sobald Sie zu einer eindeutigen Sequenz gelangen, starten Sie den Algorithmus beim nächsten Bit neu.

WGroleau
quelle