Pourquoi ce code est-il uniquement décodable?

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

Alphabet de code: $\{0, 1\}$

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

Je pensais que pour qu'un code soit uniquement décodable, il devait être sans préfixe. Mais dans ce code, le mot de code $c$ est le préfixe du mot de code $f$ par exemple, il n'est donc pas sans préfixe. Cependant, mon manuel me dit que son revers est sans préfixe (je ne comprends pas cela), et qu'il est donc uniquement décodable. Quelqu'un peut-il expliquer ce que cela signifie ou pourquoi il est uniquement décodable? Je sais que cela satisfait l'inégalité de Kraft, mais ce n'est qu'une condition nécessaire, pas une condition suffisante.

encoding-scheme 2000mroliver
la source

Sans préfixe implique un décodage unique, mais qu'il ne s'agit pas d'une instruction "si et seulement si". Voir, par exemple, ici .

dkaeae

D'accord, je vois, mais mon manuel dit ceci: le code A est uniquement décodable car son revers est sans préfixe, donc uniquement décodable Comprenez-vous ce qu'ils entendent par son revers?

2000mroliver

Probablement simplement le code obtenu en inversant tous les mots de code.

dkaeae

et pourquoi cela implique-t-il un

décodage

cpeut être un préfixe de bet f, mais les suffixes qui restent n'existent pas dans le code. Lorsque vous inversez le code, les suffixes deviennent des préfixes, puis il devient sans préfixe.

Barmar

Réponses:

Votre code a la propriété que si vous inversez tous les mots de code, vous obtenez un code de préfixe. Cela implique que votre code est uniquement décodable.

En effet, considérons tout code dont l'inverse est uniquement décodable. Je prétends que est également uniquement décodable. En effet, En d'autres termes, les décompositions de en mots de code de sont dans une correspondance univoque avec des décompositions de dans les mots de code de . Étant donné que ces derniers sont uniques, les premiers le sont également. $C = x_1,\ldots,x_n$ $C^R := x_1^R,\ldots,x_n^R$ $C$

w = X_{{je}_{1}} \dots X_{{je}_{m}} si et seulement si w^{R} = X_{{je}_{m}}^{R} \dots X_{{je}_{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$

Étant donné que les codes de préfixe sont uniquement décodables, il s'ensuit que l'inverse d'un code de préfixe est également uniquement décodable. C'est le cas dans votre exemple.

L'inégalité de McMillan indique que si est uniquement décodable, alors En d'autres termes, un code uniquement décodable satisfait l'inégalité de Kraft. Par conséquent, si tout ce qui vous intéresse est de minimiser la longueur de mot de code attendue, il n'y a aucune raison de regarder au-delà des codes de préfixe. $C$

\sum_{je = 1}^{n} 2^{- | X_{je} |} \leq 1.

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

Sam Roweis donne dans ses diapositives un bel exemple d'un code décodable unique qui n'est ni un code préfixe ni l'inverse d'un code préfixe: Afin de montrer que ce code est uniquement décodable, il suffit de montrer comment décoder le premier mot de code d'un mot. Si le mot commence par , le premier mot de code est . Si elle est de la forme , elle doit être ou . Sinon, il doit y avoir un préfixe de la forme . On distingue maintenant plusieurs cas:

0, 01, 110.

$0,01,110.$

1

$1$

110

$110$

01^{*}

$01^*$

0

$0$

01

$01$

01^{*} 0

$01^*0$

\begin{array}{ccccc} préfixe & 00 & 010 & 0110 & 01110 \\ mot de code & 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}$ Des séries plus longues de ne peuvent pas être décodé du tout.

1

$1$

Yuval Filmus
la source

Il semble que dans l'exemple de l'OP, nous ne pouvons pas décoder le premier mot de code après un nombre fixe de chiffres, il existe une infinité de cas: 1001010101010101…peut être soit fcccccc…ou caaa…, et nous pourrions avoir besoin d'attendre la fin de l'entrée pour décider.

Bergi

Cela se produit également pour .

1, 10, 00

$1,10,00$

Yuval Filmus

@Bergi Il est toujours décodable pour n'importe quelle quantité finie de chiffres. Il n'y a toujours qu'une seule façon de décoder l'encodage sans aucun reste. Toute autre tentative se terminera par des 1 ou 0 de rechange. C'est parce que le code est uniquement décodable si nous le lisons en premier. En théorie, si quelque chose est uniquement décodable dans une direction, cela n'a aucun sens qu'il puisse y avoir plus d'une solution dans l'autre direction

slebetman

@slebetman Je faisais référence à un préfixe fini (avec des restes possibles). Oui, si nous prenons la totalité de l'entrée, elle est toujours décodable.

Bergi

Si je vous donne un message que vous êtes censé décoder, vous pouvez faire ce qui suit: Inversez le message, en commençant par le dernier bit au lieu du premier bit. Inversez les mots de code. Décodez le message. Inverse la chaîne décodée.

Vous pouvez le faire car après avoir inversé les six mots de code, vous obtenez un code sans préfixe: 1010, 1001, 01, 000, 11, 001 est sans préfixe.

gnasher729
la source

Si sans préfixe signifie ce que je pense, l'inverse de 'a' commence par 1, ou 10 ou 101, dont aucun n'est un autre code valide.

Par conséquent, si un message se termine par 0101, il ne peut s'agir que d'un «a» et vous pouvez appliquer une logique similaire aux bits précédents.

Mais que faire s'il n'y a pas de fin pour commencer? Eh bien, si le premier bit est 1, vous savez que ce n'est pas «a» ou «d». Le deuxième bit éliminera 'e' ou {'b', 'c', 'f'}. Le troisième bit peut le ramener à un choix, mais sinon, il est unique par le quatrième bit.

Dès que vous arrivez à une séquence unique, vous redémarrez l'algorithme sur le bit suivant.

WGroleau
la source