Código de comprimento variável - Variable-length code

Na teoria da codificação, um código de comprimento variável é um código que mapeia símbolos de origem para um número variável de bits.

Os códigos de comprimento variável podem permitir que as fontes sejam compactadas e descompactadas com erro zero ( compactação de dados sem perdas ) e ainda assim sejam lidas símbolo por símbolo. Com a estratégia de codificação correta, uma fonte independente e distribuída de forma idêntica pode ser comprimida quase que arbitrariamente perto de sua entropia . Isso está em contraste com os métodos de codificação de comprimento fixo, para os quais a compactação de dados só é possível para grandes blocos de dados, e qualquer compactação além do logaritmo do número total de possibilidades vem com uma probabilidade finita (embora talvez arbitrariamente pequena) de falha.

Alguns exemplos de estratégias de codificação de comprimento variável bem conhecidas são a codificação de Huffman , a codificação de Lempel-Ziv , a codificação aritmética e a codificação de comprimento variável adaptável ao contexto .

Códigos e suas extensões

A extensão de um código é o mapeamento de sequências de origem de comprimento finito para sequências de bits de comprimento finito, que é obtido concatenando para cada símbolo da sequência de origem a palavra-código correspondente produzida pelo código original.

Usando termos da teoria da linguagem formal , a definição matemática precisa é a seguinte: sejam e sejam dois conjuntos finitos, chamados de alfabetos de origem e de destino , respectivamente. Um código é uma função total de mapeamento de cada símbolo de uma sequência de símbolos mais , e a extensão de um homomorphism de dentro , o que naturalmente mapeia cada sequência de símbolos de código para uma sequência de símbolos de alvo, é referido como a sua extensão . ${\ displaystyle S}$${\ displaystyle T}$ ${\ displaystyle C: S \ to T ^ {*}}$${\ displaystyle S}$${\ displaystyle T}$${\ displaystyle C}$${\ displaystyle S ^ {*}}$${\ displaystyle T ^ {*}}$

Classes de códigos de comprimento variável

Os códigos de comprimento variável podem ser estritamente aninhados em ordem decrescente de generalidade como códigos não singulares, códigos decodificáveis ​​de maneira única e códigos de prefixo. Os códigos de prefixo são sempre decodificáveis ​​de forma única e, por sua vez, são sempre não singulares:

Códigos não singulares

Um código é não singular se cada símbolo de origem é mapeado para uma sequência de bits não vazia diferente, ou seja, o mapeamento dos símbolos de origem para sequências de bits é injetivo .

• Por exemplo, o mapeamento não é não singular porque "a" e "b" são mapeados para a mesma string de bits "0"; qualquer extensão deste mapeamento irá gerar uma codificação com perdas (sem perdas). Tal codificação singular pode ainda ser útil quando alguma perda de informação é aceitável (por exemplo, quando tal código é usado na compressão de áudio ou vídeo, onde uma codificação com perdas torna-se equivalente à quantização da fonte ).${\ displaystyle M_ {1} = \ {\, a \ mapsto 0, b \ mapsto 0, c \ mapsto 1 \, \}}$
• No entanto, o mapeamento não é singular; sua extensão irá gerar uma codificação sem perdas, que será útil para a transmissão geral de dados (mas esse recurso nem sempre é necessário). Observe que não é necessário que o código não singular seja mais compacto do que a fonte (e em muitas aplicações, um código maior é útil, por exemplo, como uma forma de detectar e / ou recuperar de erros de codificação ou transmissão, ou em aplicativos de segurança para proteger uma fonte de adulteração indetectável).${\ displaystyle M_ {2} = \ {\, a \ mapsto 1, b \ mapsto 011, c \ mapsto 01110, d \ mapsto 1110, e \ mapsto 10011, f \ mapsto 0 \}}$

Códigos decodificáveis ​​exclusivamente

Um código é decodificável exclusivamente se sua extensão não for singular (veja acima). Se um determinado código é exclusivamente decodificável, pode ser decidido com o algoritmo Sardinas-Patterson .

• O mapeamento é exclusivamente decodificável (isso pode ser demonstrado observando o conjunto de seguimento após cada sequência de bits de destino no mapa, porque cada sequência de bits é encerrada assim que vemos um bit 0 que não pode seguir qualquer código existente para criar um código mais válido código no mapa, mas inicia de forma inequívoca um novo código).${\ displaystyle M_ {3} = \ {\, a \ mapsto 0, b \ mapsto 01, c \ mapsto 011 \, \}}$
• Considere novamente o código da seção anterior. Este código não é decodificável exclusivamente, uma vez que a sequência 011101110011 pode ser interpretada como a sequência de palavras-código 01110 - 1110 - 011 , mas também como a sequência de palavras-código 011 - 1 - 011 - 10011 . Duas decodificações possíveis dessa string codificada são, portanto, fornecidas por cdb e babe . No entanto, esse código é útil quando o conjunto de todos os símbolos de origem possíveis é completamente conhecido e finito ou quando há restrições (por exemplo, uma sintaxe formal) que determinam se os elementos de origem desta extensão são aceitáveis. Tais restrições permitem a decodificação da mensagem original, verificando quais dos possíveis símbolos de origem mapeados para o mesmo símbolo são válidos sob essas restrições.${\ displaystyle M_ {2}}$

Códigos de prefixo

Um código é um código de prefixo se nenhuma sequência de bits de destino no mapeamento for um prefixo da sequência de bits de destino de um símbolo de origem diferente no mesmo mapeamento. Isso significa que os símbolos podem ser decodificados instantaneamente depois que sua palavra-código inteira for recebida. Outros nomes comumente usados ​​para este conceito são código sem prefixo , código instantâneo ou código livre de contexto .

• O exemplo de mapeamento no parágrafo anterior não é um código de prefixo porque não sabemos depois de ler a string de bits "0" se ele codifica um símbolo de origem "a" ou se é o prefixo das codificações de "b" ou símbolos "c".${\ displaystyle M_ {3}}$
• Um exemplo de um código de prefixo é mostrado abaixo.

Exemplo de codificação e decodificação:

aabacdab → 00100110111010 → | 0 | 0 | 10 | 0 | 110 | 111 | 0 | 10 | → aabacdab

Um caso especial de códigos de prefixo são códigos de bloco . Aqui, todas as palavras-código devem ter o mesmo comprimento. Os últimos não são muito úteis no contexto da codificação de origem , mas geralmente servem como códigos de correção de erros no contexto da codificação de canal .

Outro caso especial de códigos de prefixo são os códigos de quantidade de comprimento variável , que codificam inteiros arbitrariamente grandes como uma sequência de octetos - ou seja, cada palavra-código é um múltiplo de 8 bits.

Vantagens

A vantagem de um código de comprimento variável é que símbolos de fonte improváveis ​​podem ser atribuídos a palavras de código mais longas e símbolos de origem prováveis ​​podem receber palavras de código mais curtas, dando assim um comprimento de palavra de código esperado baixo . Para o exemplo acima, se as probabilidades de (a, b, c, d) fossem , o número esperado de bits usados ​​para representar um símbolo de origem usando o código acima seria: ${\ displaystyle \ textstyle \ left ({\ frac {1} {2}}, {\ frac {1} {4}}, {\ frac {1} {8}}, {\ frac {1} {8} }\direito)}$

${\ displaystyle 1 \ times {\ frac {1} {2}} + 2 \ times {\ frac {1} {4}} + 3 \ times {\ frac {1} {8}} + 3 \ times {\ frac {1} {8}} = {\ frac {7} {4}}}$.

Como a entropia desta fonte é de 1,7500 bits por símbolo, este código comprime a fonte o máximo possível para que a fonte possa ser recuperada com erro zero .

Notas

Referências

• Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). Códigos e autômatos . Enciclopédia de Matemática e suas Aplicações. 129 . Cambridge: Cambridge University Press . ISBN 978-0-521-88831-8. Zbl  1187.94001 . Rascunho disponível online