miniaturadaimagem|Um gráfico do peso de Hamming para os números 0 a 256. O peso é a quantidade de bits 1 na representação binária do número.
thumb|Visualização bidimensional da distância de Hamming, uma medida crítica na teoria da codificação
Teoria da codificação é o estudo das propriedades dos códigos e sua respectiva adequação para aplicações específicas. Códigos são usados para compressão de dados, criptografia, detecção e correção de erros, transmissão de dados e armazenamento de dados. Os códigos são estudados por várias disciplinas científicas — como teoria da informação, engenharia elétrica, matemática, linguística e ciência da computação — com o objetivo de projetar métodos de transmissão de dados eficientes e confiáveis. Isso normalmente envolve a remoção de redundância e a correção ou detecção de erros nos dados transmitidos.
Existem quatro tipos de codificação:
Compressão de dados (ou codificação de fonte) Controle de erros (ou codificação de canal) Codificação criptográfica Codificação de linha
A compressão de dados tenta remover a redundância indesejada dos dados de uma fonte para transmiti-los de forma mais eficiente. Por exemplo, a compressão de dados DEFLATE torna os arquivos menores para fins como reduzir o tráfego na Internet. A compressão de dados e a correção de erros podem ser estudadas em conjunto.
A correção de erros adiciona redundância útil aos dados de uma fonte para tornar a transmissão mais robusta a distúrbios presentes no canal de transmissão. O usuário comum pode não estar ciente de muitas aplicações que usam correção de erros. Um CD de música típico usa o código de Reed–Solomon para corrigir arranhões e poeira. Nesta aplicação, o canal de transmissão é o próprio CD. Os telefones celulares também usam técnicas de codificação para corrigir o desvanecimento e o ruído da transmissão por rádio de alta frequência. Modems de dados, transmissões telefônicas e a Deep Space Network da NASA empregam técnicas de codificação de canal para transmitir os bits, por exemplo, o código turbo e os códigos LDPC.
História da teoria da codificação
O artigo de Shannon foca no problema de como codificar da melhor forma a informação que um remetente deseja transmitir. Neste trabalho fundamental, ele usou ferramentas da teoria da probabilidade, desenvolvidas por Norbert Wiener, que estavam em estágios iniciais de aplicação à teoria da comunicação naquela época. Shannon desenvolveu a entropia da informação como uma medida para a incerteza em uma mensagem, essencialmente inventando o campo da teoria da informação.
O código de Golay binário foi desenvolvido em 1949. É um código de correção de erros capaz de corrigir até três erros em cada palavra de 24 bits e detectar um quarto.
Richard Hamming ganhou o Prêmio Turing em 1968 por seu trabalho nos Bell Labs em métodos numéricos, sistemas de codificação automática e códigos de detecção e correção de erros. Ele inventou os conceitos conhecidos como códigos de Hamming, janela de Hamming, números de Hamming e distância de Hamming.
Em 1972, Nasir Ahmed propôs a transformada discreta de cosseno (DCT), que ele desenvolveu com T. Natarajan e K. R. Rao em 1973. A DCT é o algoritmo de compressão com perdas mais amplamente utilizado, a base para formatos multimídia como JPEG, MPEG e MP3.
Codificação de fonte
O objetivo da codificação de fonte é pegar os dados da fonte e torná-los menores.
Definição Os dados podem ser vistos como uma variável aleatória , onde aparece com probabilidade .
Os dados são codificados por cadeias (palavras) sobre um alfabeto .
Um código é uma função
(ou se a cadeia vazia não fizer parte do alfabeto).
é a palavra-código associada a .
O comprimento da palavra-código é escrito como
O comprimento esperado de um código é
A concatenação de palavras-código .
A palavra-código da cadeia vazia é a própria cadeia vazia:
Propriedades é não singular se injetora. é unicamente decodificável se injetora. é instantâneo se não é um prefixo próprio de (e vice-versa).
Princípio A entropia de uma fonte é a medida da informação. Basicamente, os códigos de fonte tentam reduzir a redundância presente na fonte e representar a fonte com menos bits que carregam mais informação.
A compressão de dados que tenta explicitamente minimizar o comprimento médio das mensagens de acordo com um determinado modelo de probabilidade assumido é chamada de codificação entrópica.
Várias técnicas usadas por esquemas de codificação de fonte tentam atingir o limite da entropia da fonte. C(x) ≥ H(x), onde H(x) é a entropia da fonte (taxa de bits), e C(x) é a taxa de bits após a compressão. Em particular, nenhum esquema de codificação de fonte pode ser melhor do que a entropia da fonte.
Exemplo A transmissão por fac-símile usa um simples código de comprimento de execução. A codificação de fonte remove todos os dados supérfluos à necessidade do transmissor, diminuindo a largura de banda necessária para a transmissão.
Codificação de canal
O objetivo da teoria da codificação de canal é encontrar códigos que transmitam rapidamente, contenham muitas palavras-código válidas e possam corrigir ou pelo menos detectar muitos erros. Embora não sejam mutuamente exclusivos, o desempenho nessas áreas é uma troca. Portanto, diferentes códigos são ótimos para diferentes aplicações. As propriedades necessárias desse código dependem principalmente da probabilidade de erros durante a transmissão. Em um CD típico, a deficiência é principalmente poeira ou arranhões.
Os CDs usam a codificação Reed–Solomon entrecruzada para espalhar os dados pelo disco.Todd Campbell. "Answer Geek: Error Correction Rule CDs".
Embora não seja um código muito bom, um simples código de repetição pode servir como um exemplo compreensível. Suponha que pegamos um bloco de bits de dados (representando som) e o enviamos três vezes. No receptor, examinaremos as três repetições bit a bit e faremos uma votação majoritária. O detalhe é que não simplesmente enviamos os bits em ordem. Nós os entrelaçamos. O bloco de bits de dados é primeiro dividido em 4 blocos menores. Em seguida, percorremos o bloco e enviamos um bit do primeiro, depois do segundo, etc. Isso é feito três vezes para espalhar os dados pela superfície do disco. No contexto do código de repetição simples, isso pode não parecer eficaz. No entanto, existem códigos mais poderosos conhecidos que são muito eficazes na correção do erro "em rajada" de um arranhão ou uma mancha de poeira quando esta técnica de entrelaçamento é usada.
Outros códigos são mais apropriados para diferentes aplicações. As comunicações no espaço profundo são limitadas pelo ruído térmico do receptor, que é mais de natureza contínua do que em rajadas. Da mesma forma, modems de banda estreita são limitados pelo ruído presente na rede telefônica, também modelado melhor como uma perturbação contínua. Os telefones celulares estão sujeitos a desvanecimento rápido. As altas frequências usadas podem causar desvanecimento rápido do sinal mesmo que o receptor seja movido alguns centímetros. Novamente, há uma classe de códigos de canal projetados para combater o desvanecimento.
Códigos lineares
O termo teoria da codificação algébrica denota o subcampo da teoria da codificação onde as propriedades dos códigos são expressas em termos algébricos e depois pesquisadas.
A teoria da codificação algébrica é basicamente dividida em dois tipos principais de códigos:
Códigos de bloco lineares Códigos convolucionais
Ela analisa as seguintes três propriedades de um código – principalmente:
Comprimento da palavra-código Número total de palavras-código válidas A distância mínima entre duas palavras-código válidas, usando principalmente a distância de Hamming, às vezes também outras distâncias como a distância de Lee
Códigos de bloco lineares
Os códigos de bloco lineares têm a propriedade de linearidade, ou seja, a soma de quaisquer duas palavras-código também é uma palavra-código, e eles são aplicados aos bits de fonte em blocos, daí o nome códigos de bloco lineares. Existem códigos de bloco que não são lineares, mas é difícil provar que um código é bom sem essa propriedade.
Os códigos de bloco lineares são resumidos por seus alfabetos de símbolos (por exemplo, binário ou ternário) e parâmetros (n,m,dmin) onde
n é o comprimento da palavra-código, em símbolos, m é o número de símbolos de fonte que serão usados para codificação de uma só vez, dmin é a distância mínima de Hamming para o código.
Existem muitos tipos de códigos de bloco lineares, como
Códigos cíclicos (por exemplo, códigos de Hamming) Códigos de repetição Códigos de paridade Códigos polinomiais (por exemplo, códigos BCH) Códigos de Reed–Solomon Códigos algébricos geométricos Códigos de Reed–Muller Códigos perfeitos Códigos localmente recuperáveis
Os códigos de bloco estão ligados ao problema do empacotamento de esferas, que tem recebido alguma atenção ao longo dos anos. Em duas dimensões, é fácil visualizar. Pegue um monte de moedas sobre a mesa e junte-as. O resultado é um padrão hexagonal como um ninho de abelhas. Mas os códigos de bloco dependem de mais dimensões que não podem ser facilmente visualizadas. O poderoso código de Golay (24,12) usado em comunicações espaciais usa 24 dimensões. Se usado como código binário (como geralmente é), as dimensões se referem ao comprimento da palavra-código conforme definido acima.
A teoria da codificação usa o modelo de esfera N-dimensional. Por exemplo, quantas moedas podem ser empacotadas em um círculo sobre uma mesa ou, em 3 dimensões, quantas bolinhas de gude podem ser empacotadas em um globo. Outras considerações entram na escolha de um código. Por exemplo, o empacotamento hexagonal dentro da restrição de uma caixa retangular deixará espaço vazio nos cantos. À medida que as dimensões aumentam, a porcentagem de espaço vazio diminui. Mas em certas dimensões, o empacotamento usa todo o espaço e esses códigos são os chamados códigos "perfeitos". Os únicos códigos perfeitos não triviais e úteis são os códigos de Hamming de distância 3 com parâmetros satisfazendo (2r – 1, 2r – 1 – r, 3), e os códigos de Golay binário [23,12,7] e ternário [11,6,5].
Outra propriedade do código é o número de vizinhos que uma única palavra-código pode ter. Novamente, considere as moedas como exemplo. Primeiro, empacotamos as moedas em uma grade retangular. Cada moeda terá 4 vizinhos próximos (e 4 nos cantos que estão mais distantes). Em um hexágono, cada moeda terá 6 vizinhos próximos. Quando aumentamos as dimensões, o número de vizinhos próximos aumenta muito rapidamente. O resultado é que o número de maneiras pelas quais o ruído pode fazer o receptor escolher um vizinho (daí um erro) também cresce. Esta é uma limitação fundamental dos códigos de bloco, e de fato de todos os códigos. Pode ser mais difícil causar um erro em um único vizinho, mas o número de vizinhos pode ser grande o suficiente para que a probabilidade total de erro realmente sofra.
As propriedades dos códigos de bloco lineares são usadas em muitas aplicações. Por exemplo, a propriedade de unicidade síndrome-coclasses dos códigos de bloco lineares é usada na modelagem de treliça, um dos códigos de modelagem mais conhecidos.
Códigos convolucionais
A ideia por trás de um código convolutional é fazer com que cada símbolo da palavra-código seja a soma ponderada dos vários símbolos da mensagem de entrada. Isso é como a convolução usada em sistemas LTI para encontrar a saída de um sistema quando se conhece a entrada e a resposta ao impulso.
Assim, geralmente encontramos a saída do codificador convolutional do sistema, que é a convolução do bit de entrada contra os estados do codificador convolutional, registradores.