Por que esse código é decodificado exclusivamente?

Alfabeto de origem:$\{a, b, c, d, e, f\}$

Alfabeto do código:$\{0, 1\}$

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

Eu pensei que, para um código ser decodificado de forma única, ele precisava ser livre de prefixos. Mas neste código, a palavra de código é o prefixo da palavra de código por exemplo, portanto, não é livre de prefixo. No entanto, meu livro me diz que seu reverso é livre de prefixo (eu não entendo isso) e, portanto, é exclusivamente decodível. Alguém pode explicar o que isso significa, ou por que é exclusivamente decodificável? Sei que satisfaz a desigualdade da Kraft, mas isso é apenas uma condição necessária, não suficiente.$c$$f$

Seu código possui a propriedade de que, se você reverter todas as palavras de código, obterá um código de prefixo. Isso implica que seu código é decodificável exclusivamente.

Com efeito, considerar qualquer código $C = x_1,\ldots,x_n$ cujo reverso $C^R := x_1^R,\ldots,x_n^R$ é exclusivamente decodificável. Afirmo que $C$ também é exclusivamente decodificável. Isso ocorre porque

$$w = x_{i_1} \ldots x_{i_m} \text{ if and only if } w^R = x_{i_m}^R \ldots x_{i_1}^R.$$ Em palavras, decomposições de $w$ em palavras de código de $C$ estão em correspondência de um-para-um com decomposições de $w^R$ em palavras de código de $C^R$ . Como os últimos são únicos, o mesmo acontece com os primeiros.

Como os códigos de prefixo são decodificados exclusivamente, segue-se que o reverso de um código de prefixo também é decodificado exclusivamente. Este é o caso no seu exemplo.

A desigualdade de McMillan afirma que se $C$ é decodificável de forma única, então

$$\sum_{i=1}^n 2^{-|x_i|} \leq 1.$$ Em outras palavras, um código exclusivamente decodificável satisfaz a desigualdade da Kraft. Portanto, se tudo o que você está interessado é minimizar o comprimento esperado da palavra de código, não há motivo para procurar além dos códigos de prefixo.

Sam Roweis fornece em seus slides um bom exemplo de um código decodificável único que não é nem um código prefixo nem o inverso de um código prefixo:

$$0,01,110.$$ Para mostrar que esse código é decodificável exclusivamente, basta mostrar como para decodificar a primeira palavra de código de uma palavra. Se a palavra começar com $1$ , a primeira palavra de código é $110$ . Se tiver o formato $01^*$ , deverá ser $0$ ou $01$ . Caso contrário, deve haver um prefixo no formato $01^*0$ . Agora, distinguimos vários casos:

$$\begin{array}{c|cccc} \text{prefix} & 00 & 010 & 0110 & 01110 \\\hline \text{codeword} & 0 & 01 & 0 & 01 \end{array}$$ Execuções mais longas de$1$não podem ser decodificadas.

Se eu lhe der uma mensagem que você deve decodificar, faça o seguinte: Inverta a mensagem, começando com o último bit em vez do primeiro. Inverta as palavras de código. Decodifique a mensagem. Inverta a string decodificada.

Você pode fazer isso porque, depois de reverter as seis palavras de código, você obtém um código sem prefixo: 1010, 1001, 01, 000, 11, 001 é sem prefixo.

Se livre de prefixo significa o que penso, o reverso de 'a' começa com 1, 10 ou 101, nenhum dos quais é outro código válido.

Portanto, se uma mensagem terminar com 0101, ela poderá ser apenas um 'a' e você poderá aplicar uma lógica semelhante aos bits anteriores.

No entanto, e se não houver fim para começar? Bem, se o primeiro bit é 1, você sabe que não é 'a' ou 'd'. O segundo bit eliminará 'e' ou {'b', 'c', 'f'}. O terceiro bit pode reduzi-lo a uma opção, mas, se não, é exclusivo do quarto bit.

Assim que você chegar a uma sequência única, reinicie o algoritmo no próximo bit.