Por que esse código é decodificado exclusivamente?

21

Alfabeto de origem:{uma,b,c,d,e,f}

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

  • uma:0101
  • b:1001
  • c:10
  • d:000
  • e:11
  • f: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.cf

2000mroliver
fonte
10
Sem prefixo implica decodificação exclusiva, mas que não é uma declaração "se e somente se". Veja, por exemplo, aqui .
dkaeae 3/03
Tudo bem, entendo, mas meu livro de texto diz o seguinte: O código A é decodificável de forma única, pois seu reverso é prefixfree, tão decodificável de forma singular Você entende o que eles querem dizer com seu inverso?
2000mroliver 3/03
1
Provavelmente, simplesmente o código obtido revertendo todas as palavras de código.
dkaeae 3/03
e por que isso implica uma decodificação única, eu não entendo
2000mroliver 03/03
1
cpode ser um prefixo de be f, mas os sufixos restantes não existem no código. Quando você inverte o código, os sufixos se tornam prefixos e, em seguida, ficam sem prefixos.
Barmar 04/03

Respostas:

26

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=x1,,xn cujo reverso CR: =x1R,...,xnR é exclusivamente decodificável. Afirmo que C também é exclusivamente decodificável. Isso ocorre porque

W=xEu1...xEum se e apenas se WR=xEumR...xEu1R.
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 WR em palavras de código de CR . 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

Eu=1n2-|xEu|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 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 0 ou 01 . Caso contrário, deve haver um prefixo no formato 010 0 . Agora, distinguimos vários casos:

prefixo00010011001110palavra de código0 0010 001
Execuções mais longas de1não podem ser decodificadas.

Yuval Filmus
fonte
2
Parece que, no exemplo do OP, não podemos decodificar a primeira palavra de código após uma quantidade fixa de dígitos, existem infinitos casos: 1001010101010101…pode ser um fcccccc…ou ou caaa…, e talvez precisemos esperar até o final da entrada para decidir.
Bergi 03/03
1
1,10,00
4
@ Bergi É sempre decodificável para qualquer quantidade finita de dígitos. Sempre há apenas uma maneira de decodificar a codificação sem restos. Qualquer outra tentativa terá 1 ou 0 de reposição. Isso ocorre porque o código é decodificável exclusivamente se o lermos primeiro. Em teoria, se algo é exclusivamente decodificável em uma direção, não faz sentido que possa haver mais de uma solução na outra direção
slebetman
@slebetman eu estava me referindo a um prefixo finito (com possíveis restos). Sim, se pegarmos toda a entrada, ela sempre será decodificada.
Bergi 04/03
5

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.

gnasher729
fonte
0

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.

WGroleau
fonte