Teoria da codificação - Coding theory

A teoria da codificação é o estudo das propriedades dos códigos e sua respectiva adequação a aplicações específicas. Os códigos são usados ​​para compressão de dados , criptografia , detecção e correção de erros , transmissão 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 propósito de projetar métodos de transmissão de dados eficientes e confiáveis . Isso normalmente envolve a remoção da redundância e a correção ou detecção de erros nos dados transmitidos.

Existem quatro tipos de codificação:

1. Compressão de dados (ou codificação de origem )
2. Controle de erro (ou codificação de canal )
3. Codificação criptográfica
4. Codificação de linha

A compactação de dados tenta remover a redundância dos dados de uma fonte para transmiti-los com mais eficiência. Por exemplo, a compactação de dados ZIP torna os arquivos de dados menores, com o objetivo de reduzir o tráfego da Internet. A compressão de dados e a correção de erros podem ser estudadas em combinação .

A correção de erros adiciona bits de dados extras para tornar a transmissão de dados mais robusta a distúrbios presentes no canal de transmissão. O usuário comum pode não estar ciente de muitos aplicativos que usam correção de erros. Um disco compacto (CD) de música típico usa o código 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 desbotamento e o ruído da transmissão de rádio de alta freqüência. Modems de dados, transmissões de telefone e a NASA Deep Space Network, todos empregam técnicas de codificação de canal para passar os bits, por exemplo, o código turbo e os códigos LDPC .

História da teoria da codificação

Em 1948, Claude Shannon publicou " A Mathematical Theory of Communication ", um artigo em duas partes nas edições de julho e outubro do Bell System Technical Journal . Este trabalho enfoca o problema de como codificar melhor as informações que um remetente deseja transmitir. Nesse trabalho fundamental ele utilizou ferramentas da teoria da probabilidade, desenvolvidas por Norbert Wiener , que estavam em seus estágios iniciais de aplicação à teoria da comunicação na época. Shannon desenvolveu a entropia da informação como uma medida para a incerteza em uma mensagem enquanto, essencialmente, inventava o campo da teoria da informação .

O código binário de Golay 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 na 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 , janelas de Hamming , números de Hamming , e Hamming distância .

Em 1972, Nasir Ahmed propôs a transformada discreta de cosseno (DCT), que ele desenvolveu com T. Natarajan e KR Rao em 1973. O DCT é o algoritmo de compressão com perdas mais amplamente usado , a base para formatos de multimídia como JPEG , MPEG e MP3 .

Codificação fonte

O objetivo da codificação de origem é pegar os dados de origem e torná-los menores.

Definição

Os dados podem ser vistos como uma variável aleatória , onde aparece com probabilidade . ${\ displaystyle X: \ Omega \ to {\ mathcal {X}}}$${\ displaystyle x \ in {\ mathcal {X}}}$${\ displaystyle \ mathbb {P} [X = x]}$

Os dados são codificados por strings (palavras) sobre um alfabeto . ${\ displaystyle \ Sigma}$

Um código é uma função

${\ displaystyle C: {\ mathcal {X}} \ to \ Sigma ^ {*}}$(ou se a string vazia não fizer parte do alfabeto).${\ displaystyle \ Sigma ^ {+}}$

${\ displaystyle C (x)}$é a palavra de código associada a . ${\ displaystyle x}$

O comprimento da palavra de código é escrito como

${\ displaystyle l (C (x)).}$

O comprimento esperado de um código é

${\ displaystyle l (C) = \ sum _ {x \ in {\ mathcal {X}}} l (C (x)) \ mathbb {P} [X = x].}$

A concatenação de palavras de código . ${\ displaystyle C (x_ {1}, \ ldots, x_ {k}) = C (x_ {1}) C (x_ {2}) \ cdots C (x_ {k})}$

A palavra de código da string vazia é a própria string vazia:

${\ displaystyle C (\ epsilon) = \ epsilon}$

Propriedades

1. ${\ displaystyle C: {\ mathcal {X}} \ to \ Sigma ^ {*}}$é não singular se injetivo .
2. ${\ displaystyle C: {\ mathcal {X}} ^ {*} \ to \ Sigma ^ {*}}$é unicamente decodificável se injetivo.
3. ${\ displaystyle C: {\ mathcal {X}} \ to \ Sigma ^ {*}}$é instantâneo se não for um prefixo de (e vice-versa).${\ displaystyle C (x_ {1})}$${\ displaystyle C (x_ {2})}$

Princípio

A entropia de uma fonte é a medida da informação. Basicamente, os códigos-fonte tentam reduzir a redundância presente na fonte e representam a fonte com menos bits que transportam mais informações.

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 de entropia .

Várias técnicas usadas por esquemas de codificação de fonte tentam atingir o limite de 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 de fac-símile usa um código de comprimento de execução simples . A codificação da 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 transmitem rapidamente, contêm muitas palavras de código válidas e podem corrigir ou pelo menos detectar muitos erros. Embora não seja mutuamente exclusivo, o desempenho nessas áreas é uma troca. Portanto, códigos diferentes são ideais para diferentes aplicações. As propriedades necessárias desse código dependem principalmente da probabilidade de erros ocorridos durante a transmissão. Em um CD típico, a deficiência é principalmente poeira ou arranhões.

Os CDs usam codificação Reed – Solomon intercalada para espalhar os dados pelo disco.

Embora não seja um código muito bom, um código de repetição simples pode servir como um exemplo compreensível. Suponha que pegemos um bloco de bits de dados (representando o som) e o enviemos três vezes. No receptor, examinaremos as três repetições, pouco a pouco, e faremos uma votação majoritária. A diferença é que não apenas enviamos os bits em ordem. Nós os intercalamos. O bloco de bits de dados é primeiro dividido em 4 blocos menores. Em seguida, percorremos o bloco e enviamos um bit do primeiro, depois o 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 de "explosão" de um arranhão ou uma mancha de poeira quando esta técnica de intercalação é 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 de rajadas. Da mesma forma, modems de banda estreita são limitados pelo ruído, presente na rede telefônica e também modelado melhor como uma perturbação contínua. Os telefones celulares estão sujeitos a desbotamento rápido . As altas frequências usadas podem causar desvanecimento rápido do sinal, mesmo se o receptor for movido alguns centímetros. Novamente, há uma classe de códigos de canal que são projetados para combater o desbotamento.

Códigos Lineares

O termo teoria algébrica da codificação denota o subcampo da teoria da codificação, onde as propriedades dos códigos são expressas em termos algébricos e posteriormente pesquisadas.

A teoria da codificação algébrica é basicamente dividida em dois tipos principais de códigos:

• Códigos de bloco linear
• Códigos convolucionais

Ele analisa as três propriedades a seguir de um código - principalmente:

• Comprimento da palavra de código
• Número total de palavras de código válidas
• A distância mínima entre duas palavras de 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 linear

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 são aplicados aos bits de origem 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 , d _min ) onde

1. n é o comprimento da palavra-código, em símbolos,
2. m é o número de símbolos de origem que serão usados ​​para codificação de uma vez,
3. d _min é a distância mínima de hamming para o código.

Existem muitos tipos de códigos de bloco linear, como

1. Códigos cíclicos (por exemplo, códigos de Hamming )
2. Códigos de repetição
3. Códigos de paridade
4. Códigos polinomiais (por exemplo, códigos BCH )
5. Códigos Reed-Solomon
6. Códigos geométricos algébricos
7. Códigos Reed-Muller
8. Códigos perfeitos

Os códigos de bloco estão ligados ao problema de empacotamento de esferas , que tem recebido alguma atenção ao longo dos anos. Em duas dimensões, é fácil de visualizar. Pegue um monte de moedas sobre a mesa e empurre-as juntas. O resultado é um padrão hexagonal como o ninho de uma abelha. 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 nas comunicações do espaço profundo usa 24 dimensões. Se usado como um código binário (o que geralmente é), as dimensões referem-se 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 de um centavo podem ser colocadas em um círculo em uma mesa, ou em 3 dimensões, quantas bolas de gude podem ser colocadas em um globo. Outras considerações entram na escolha de um código. Por exemplo, a embalagem hexagonal na restrição de uma caixa retangular deixará um espaço vazio nos cantos. Conforme as dimensões aumentam, a porcentagem de espaço vazio diminui. Mas, em certas dimensões, a embalagem ocupa 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 que satisfazem (2 ^r - 1, 2 ^r - 1 - r , 3), e os [23,12,7] binários e [11,6,5 ] códigos de Golay ternários.

Outra propriedade do código é o número de vizinhos que uma única palavra-código pode ter. Novamente, considere os centavos como exemplo. Primeiro, empacotamos os centavos em uma grade retangular. Cada centavo terá 4 vizinhos próximos (e 4 nos cantos mais distantes). Em um hexágono, cada centavo terá 6 vizinhos próximos. Quando aumentamos as dimensões, o número de vizinhos próximos aumenta muito rapidamente. O resultado é o número de maneiras de o ruído fazer o receptor escolher um vizinho (portanto, um erro) também aumenta. Esta é uma limitação fundamental dos códigos de bloco e, na verdade, 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 seja realmente reduzida.

As propriedades dos códigos de bloco linear são usadas em muitas aplicações. Por exemplo, a propriedade de unicidade do coset da síndrome dos códigos de bloco linear é 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 convolucional é fazer com que cada símbolo de palavra-código seja a soma ponderada dos vários símbolos de mensagem de entrada. É como a convolução usada em sistemas LTI para encontrar a saída de um sistema, quando você conhece a entrada e a resposta ao impulso.

Portanto, geralmente encontramos a saída do codificador de convolução do sistema, que é a convolução do bit de entrada, em relação aos registros do codificador de convolução.

Fundamentalmente, os códigos convolucionais não oferecem mais proteção contra ruído do que um código de bloco equivalente. Em muitos casos, eles geralmente oferecem maior simplicidade de implementação sobre um código de bloco de igual poder. O codificador é geralmente um circuito simples que possui memória de estado e alguma lógica de feedback, normalmente portas XOR . O decodificador pode ser implementado em software ou firmware.

O algoritmo de Viterbi é o algoritmo ideal usado para decodificar códigos convolucionais. Existem simplificações para reduzir a carga computacional. Eles dependem de pesquisar apenas os caminhos mais prováveis. Embora não sejam ótimos, eles geralmente fornecem bons resultados em ambientes de baixo ruído.

Os códigos convolucionais são usados ​​em modems de banda de voz (V.32, V.17, V.34) e em telefones celulares GSM, bem como em dispositivos de comunicação militar e por satélite.

Codificação criptográfica

Criptografia ou codificação criptográfica é a prática e o estudo de técnicas para comunicação segura na presença de terceiros (chamados de adversários ). De maneira mais geral, trata-se de construir e analisar protocolos que bloqueiam adversários; vários aspectos da segurança da informação , como confidencialidade de dados , integridade de dados , autenticação e não repúdio, são fundamentais para a criptografia moderna. A criptografia moderna existe na interseção das disciplinas de matemática , ciência da computação e engenharia elétrica . As aplicações de criptografia incluem cartões ATM , senhas de computador e comércio eletrônico .

A criptografia antes da era moderna era efetivamente sinônimo de criptografia , a conversão de informações de um estado legível em um aparente absurdo . O originador de uma mensagem criptografada compartilhou a técnica de decodificação necessária para recuperar as informações originais apenas com os destinatários pretendidos, impedindo assim pessoas indesejadas de fazerem o mesmo. Desde a Primeira Guerra Mundial e o advento do computador , os métodos usados ​​para realizar a criptologia tornaram-se cada vez mais complexos e sua aplicação mais difundida.

A criptografia moderna é fortemente baseada na teoria matemática e na prática da ciência da computação; algoritmos criptográficos são projetados em torno de suposições de dureza computacional , tornando esses algoritmos difíceis de quebrar na prática por qualquer adversário. É teoricamente possível quebrar tal sistema, mas é inviável fazê-lo por qualquer meio prático conhecido. Esses esquemas são, portanto, denominados computacionalmente seguros; avanços teóricos, por exemplo, melhorias em algoritmos de fatoração de inteiros e tecnologia de computação mais rápida exigem que essas soluções sejam continuamente adaptadas. Existem esquemas de informação teoricamente seguros que provavelmente não podem ser quebrados, mesmo com poder de computação ilimitado - um exemplo é o bloco único -, mas esses esquemas são mais difíceis de implementar do que os melhores mecanismos teoricamente quebráveis, mas computacionalmente seguros.

Codificação de linha

Um código de linha (também chamado de modulação de banda base digital ou método de transmissão de banda base digital) é um código escolhido para uso em um sistema de comunicações para fins de transmissão de banda base . A codificação de linha é freqüentemente usada para transporte digital de dados.

A codificação de linha consiste em representar o sinal digital a ser transportado por um sinal discreto em amplitude e tempo que é otimizado para as propriedades específicas do canal físico (e do equipamento receptor). O padrão de forma de onda de tensão ou corrente usado para representar os 1s e 0s de dados digitais em um link de transmissão é chamado de codificação de linha . Os tipos comuns de codificação de linha são codificação unipolar , polar , bipolar e Manchester .

Outras aplicações da teoria da codificação

Outra preocupação da teoria da codificação é projetar códigos que ajudem na sincronização . Um código pode ser projetado de forma que uma mudança de fase possa ser facilmente detectada e corrigida e que vários sinais possam ser enviados no mesmo canal.

Outra aplicação de códigos, usada em alguns sistemas de telefonia móvel, é o acesso múltiplo por divisão de código (CDMA). Cada telefone é atribuído a uma sequência de código que é aproximadamente não correlacionada com os códigos de outros telefones. Ao transmitir, a palavra de código é usada para modular os bits de dados que representam a mensagem de voz. No receptor, um processo de desmodulação é executado para recuperar os dados. As propriedades desta classe de códigos permitem que muitos usuários (com códigos diferentes) usem o mesmo canal de rádio ao mesmo tempo. Para o receptor, os sinais de outros usuários aparecerão para o demodulador apenas como um ruído de baixo nível.

Outra classe geral de códigos são os códigos de solicitação de repetição automática (ARQ). Nesses códigos, o remetente adiciona redundância a cada mensagem para verificação de erros, geralmente adicionando bits de verificação. Se os bits de verificação não forem consistentes com o resto da mensagem quando ela chegar, o receptor pedirá ao remetente para retransmitir a mensagem. Todos, exceto os protocolos de rede de longa distância mais simples , usam ARQ. Os protocolos comuns incluem SDLC (IBM), TCP (Internet), X.25 (Internacional) e muitos outros. Existe um extenso campo de pesquisa neste tópico devido ao problema de combinar um pacote rejeitado com um novo pacote. É um novo ou é uma retransmissão? Normalmente são usados ​​esquemas de numeração, como no TCP. "RFC793" . RFCs . Força-Tarefa de Engenharia da Internet (IETF). Setembro de 1981.

Teste de grupo

O teste de grupo usa códigos de uma maneira diferente. Considere um grande grupo de itens em que muito poucos são diferentes de uma maneira particular (por exemplo, produtos defeituosos ou cobaias infectadas). A ideia do teste de grupo é determinar quais itens são "diferentes" usando o mínimo de testes possível. A origem do problema está na Segunda Guerra Mundial, quando as Forças Aéreas do Exército dos Estados Unidos precisaram testar seus soldados para detectar sífilis .

Codificação analógica

A informação é codificada de forma análoga nas redes neurais do cérebro , no processamento de sinal analógico e na eletrônica analógica . Aspectos da codificação analógica incluem correção analógica de erros, compressão analógica de dados e criptografia analógica.

Codificação neural

A codificação neural é um campo relacionado à neurociência , preocupado em como as informações sensoriais e outras são representadas no cérebro por redes de neurônios . O objetivo principal do estudo da codificação neural é caracterizar a relação entre o estímulo e as respostas neuronais individuais ou em conjunto e a relação entre a atividade elétrica dos neurônios no conjunto. Pensa-se que os neurônios podem codificar informações digitais e analógicas e que seguem os princípios da teoria da informação e comprimem as informações, e detectam e corrigem erros nos sinais que são enviados por todo o cérebro e sistema nervoso mais amplo.

Veja também

• Ganho de codificação
• Código de cobertura
• Código de correção de erro
• Código Reed-Solomon dobrado
• Teste de grupo
• Distância de Hamming , peso de Hamming
• Distância de Lee
• Lista de tópicos da teoria da codificação algébrica
• Codificação espacial e MIMO na pesquisa de múltiplas antenas
  • A codificação de diversidade espacial é a codificação espacial que transmite réplicas do sinal de informação ao longo de diferentes caminhos espaciais, de modo a aumentar a confiabilidade da transmissão de dados.
  • Codificação de cancelamento de interferência espacial
  • Codificação multiplex espacial
• Linha do tempo da teoria da informação, compressão de dados e códigos de correção de erros

Notas

Referências

• Elwyn R. Berlekamp (2014), Algebraic Coding Theory , World Scientific Publishing (edição revisada), ISBN  978-9-81463-589-9 .
• MacKay, David JC . Teoria da informação, inferência e algoritmos de aprendizagem Cambridge: Cambridge University Press, 2003. ISBN  0-521-64298-1
• Vera Pless (1982), Introdução à Teoria dos Códigos de Correção de Erros , John Wiley & Sons, Inc., ISBN  0-471-08684-3 .
• Randy Yates, A Coding Theory Tutorial .