Tous les codes préfixaux sont-ils uniquement décodables?

Question

Je ne peux penser à aucun contre-exemple, mais je ne trouve aucune déclaration de ce type sur Internet ou mon manuel non plus.Je sais que pour chaque code unique décodable, il existe un code de préfixe avec la même longueur moyenne.

Answer 1

Vous pouvez prouver par induction sur la longueur du codage que toute chaîne est unique décodable.

let $ s= s_1 ... S_n $ Soyez une chaîne codée avec un code GRATUIT PREFIX.Puisque notre code est gratuit gratuit, il existe un préfixe unique de $ s $ , $ s_1 ... S_J $ qui est un mot de code. $ s_ {j + 1} ... S_n $ est également un codage valide (nous avons supprimé un seul code de code d'une concaténation de mots de codewords), donc par notre hypothèse inductive, $ s_ {j + 1} ... S_N $ est unique décodable, qui termine la preuve.