Sind alle Präfixcodes eindeutig decodierbar?

Question

Ich kann mir keine Gegenexample vorstellen, aber ich kann keine solche Erklärung im Internet oder mein Lehrbuch finden.Ich weiß, dass es für jeden einzigartig decodierbaren Code einen Präfixcode mit derselben durchschnittlichen Länge gibt.

Answer 1

Sie können sich durch Induktion über die Länge der Kodierung beweisen, dass eine beliebige Zeichenfolge eindeutig decodierbar ist.

lass $ s= s_1 ... s_n $ Seien Sie mit einem mit einem Präfix freien Code codiert.Da unser Code präfixfrei ist, gibt es ein einzigartiges Präfix von $ s $ , $ s_1 ... s_j $ Welches ist ein Codewort. $ s_ {j + 1} ... s_n $ ist auch eine gültige Kodierung (wir haben ein einzelnes Codewort aus einer Verkettung von Codewords entfernt), also durch unsere induktive Hypothese, $ s_ {j + 1} ... s_n $ ist eindeutig decodierbar, was den Beweis abschließt.