Teoria da codificação

Uma visualização bidimensional da distância de Hamming, uma medida crítica na teoria da codificação.

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

Existem quatro tipos de codificação:

Compactação de dados (ou codificação de origem)
Controle de erros (ou codificação de canal)
Codificação criptográfica
Codificação de linha

A compactação de dados tenta remover a redundância indesejada dos dados de uma fonte, a fim de transmiti-los de forma mais eficiente. Por exemplo, a compactação de dados ZIP torna os arquivos de dados menores, para fins como 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 erro adiciona redundância útil aos dados de uma fonte para tornar a transmissão mais robusta aos distúrbios presentes no canal de transmissão. O usuário comum pode não estar ciente de muitos aplicativos usando correção de erro. Um disco compacto de música típico (CD) usa o código Reed-Solomon para corrigir arranhões e poeira. Neste aplicativo o canal de transmissão é o próprio CD. Os celulares também usam técnicas de codificação para corrigir o desbotamento e ruído da transmissão de rádio de alta frequência. Modems de dados, transmissões telefônicas e a NASA Deep Space Network empregam técnicas de codificação de canais para obter os bits, por exemplo, o código turbo e 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 se concentra no problema da melhor forma de codificar as informações que um remetente quer transmitir. Neste trabalho fundamental ele usou ferramentas na teoria da probabilidade, desenvolvidas por Norbert Wiener, que estavam em seus estágios nascentes de serem aplicadas à teoria da comunicação naquela é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 detetar um quarto.

Richard Hamming ganhou o Prêmio Turing em 1968 por seu trabalho no Bell Labs em métodos numéricos, sistemas de codificação automática e códigos de deteção de erros e correção de erros. Ele inventou os conceitos conhecidos como códigos Hamming, janelas hamming, números de Hamming, e distância hamming.

Em 1972, Nasir Ahmed propôs a discreta transformação cossina (DCT), que ele desenvolveu com T. Natarajan e K. R. Rao em 1973. O DCT é o algoritmo de compressão lossy mais utilizado, a base para formatos multimídia como JPEG, MPEG e MP3.

Codificação de origem

Artigo principal: Compressão de dados
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 $X:\Omega \para {\mathcal {X}}$ onde $x\in {\mathcal {X}}$ aparece com probabilidade $\mathbb {P} [X=x]$ .
Os dados são codificados por strings (palavras) sobre um alfabeto $\Sigma$ .
Um código é uma função
$C:{\mathcal {X}}\para \Sigma ^{*}$ (ou $\Sigma ^{+}$ se a corda vazia não faz parte do alfabeto).
$C(x)$ é a palavra de código associada com $x$ .
O comprimento da palavra de código é escrito como
$l(C(x)).$
O comprimento esperado de um código é
$l(C)=\sum _{x\in {\mathcal {X}}}l(C(x)\mathbb {P} [X=x].$
A concatenação das palavras de código $C(x_{1},\ldots ,x_{k})=C(x_{1})C(x_{2})\cdots C(x_{k})$ .
A palavra de código da sequência vazia é a própria corda vazia:
$C(\epsilon =\epsilon$

Propriedades

$C:{\mathcal {X}}\para \Sigma ^{}$ não-singular se injetável.
$C:{\mathcal {X}}^{}\para \Sigma ^{}$ é exclusivamente decodável se injetável.
$C:{\mathcal {X}}\para \Sigma ^{}$ é instantâneo se $C (x_{1})$ não é um prefixo de $C (x_{2})$ (e vice-versa).

Princípio

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 carregam 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 presumida é chamada de codificação de entropia.
Várias técnicas utilizadas por esquemas de codificação de origem tentam alcançar o limite de entropia da fonte. C(x) ≥ H(x), onde H(x) é entropia de fonte (bitrate), e C(x) é a bitrate após a compressão. Em particular, nenhum esquema de codificação de origem pode ser melhor do que a entropia da fonte.

Exemplo

A transmissão fac-símile usa um código de comprimento de execução simples. A codificação de origem remove todos os dados supérfluos à necessidade do transmissor, diminuindo a largura de banda necessária para a transmissão.

Codificação de canais

O objetivo da teoria da codificação de canais é encontrar códigos que transmitam rapidamente, contêm muitas palavras de código válidas e podem corrigir ou pelo menos detetar muitos erros. Embora não seja mutuamente exclusivo, o desempenho nessas áreas é uma compensação. Assim, códigos diferentes são ideais para diferentes aplicações. As propriedades necessárias deste código dependem principalmente da probabilidade de erros acontecerem durante a transmissão. Em um CD típico, o prejuízo é 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 simples código de repetição pode servir como um exemplo compreensível. Suponha que peguemos um bloco de bits de dados (representando o som) e enviemos três vezes. No recetor vamos examinar as três repetições pouco a pouco e tomar um voto majoritário. A reviravolta nisso é que não apenas enviamos os pedaços em ordem. Nós os entrelaçamos. O bloco de bits de dados é primeiro dividido em 4 blocos menores. Então nós pedalamos através do bloco e enviamos um pouco do primeiro, depois o segundo, etc. Isso é feito três vezes para espalhar os dados sobre a 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 "estouro" de um arranhão ou uma mancha de poeira quando esta técnica de interleaving é usada.

Outros códigos são mais apropriados para diferentes aplicativos. As comunicações do espaço profundo são limitadas pelo ruído térmico do recetor que é mais de natureza contínua do que uma natureza estourada. Da mesma forma, os modems de banda estreita são limitados pelo ruído, presentes na rede telefônica e também modelados melhor como uma perturbação contínua. ^{[citação necessária]} Os celulares estão sujeitos a desvanecimento rápido. As altas frequências utilizadas podem causar desbotamento rápido do sinal mesmo que o recetor seja movido alguns centímetros. Novamente há uma classe de códigos de canal que são projetados para combater o desbotamento. ^{[citação necessária]}

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. ^{[citação necessária]}

A teoria da codificação algébrica é basicamente dividida em dois tipos principais de códigos:^{[citação necessária]}

Códigos de bloco lineares
Códigos convulsionais

Ele analisa as três propriedades a seguir de um código – principalmente:^{[citação necessária]}

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 lineares

Os códigos de bloco lineares têm a propriedade da linearidade, ou seja, a soma de qualquer duas palavras-código também é uma palavra-código, e são aplicadas aos bits de origem em blocos, daí os códigos de bloco lineares do nome. Existem códigos de bloco que não são lineares, mas é difícil provar que um código é um bom sem essa propriedade.

Os códigos de bloco linear são resumidos por seus alfabetos símbolo (por exemplo, binário ou ternário) e parâmetros (n,m,d _min) onde

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

Existem muitos tipos de códigos de blocos lineares, como

Códigos cíclicos (por exemplo, códigos de hamming)
Códigos de repetição
Códigos de paridade
Códigos polinômricos (por exemplo, códigos BCH)
Códigos reed-salomão
Códigos geométricos algébricos
Códigos Reed-Muller
Códigos perfeitos

Os códigos de bloco estão ligados ao problema de embalagem da esfera, que tem recebido alguma atenção ao longo dos anos. Em duas dimensões, é fácil de visualizar. Pegue um monte de centavos na mesa e empurre-os juntos. O resultado é um padrão hexágono 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 (24,12) código Golay usado em comunicações de espaço profundo usa 24 dimensões. Se usado como um código binário (que geralmente é) as dimensões referem-se ao comprimento da palavra-código como definido acima.

A teoria da codificação usa o modelo de esfera n-dimensional. Por exemplo, quantos centavos podem ser embalados em um círculo em uma mesa, ou em 3 dimensões, quantas bolinhas de gude podem ser embaladas em um globo. Outras considerações insusem a escolha de um código. Por exemplo, a embalagem hexágona na restrição de uma caixa retangular deixará espaço vazio nos cantos. À medida que as dimensões ficam maiores, a percentagem de espaço vazio fica menor. Mas em certas dimensões, a embalagem usa todo o espaço e esses códigos são os chamados códigos "perfeitos". Os únicos códigos perfeitos não trivial e úteis são os códigos de Hamming de distância-3 com parâmetros satisfatórios (2^r – 1, 2^r – 1 – r, 3), e os códigos binários [23,12,7] binários e [11,6,5] ternários golay.

Outra propriedade de código é o número de vizinhos que uma única palavra de código pode ter. Mais uma vez, considere centavos como um exemplo. Primeiro embalamos os centavos em uma grade retangular. Cada centavo terá 4 vizinhos próximos (e 4 nas esquinas que estão mais distantes). Em um hexágono, cada centavo terá 6 perto dos vizinhos. Quando aumentamos as dimensões, o número de vizinhos próximos aumenta muito rapidamente. O resultado é que o número de maneiras de ruído fazer o recetor escolher um vizinho (portanto um erro) também cresce. Esta é uma limitação fundamental dos códigos de bloco, e de fato todos os códigos. Pode ser mais difícil causar um erro a um único vizinho, mas o número de vizinhos pode ser grande o suficiente para que a probabilidade de erro total realmente sofra.

Propriedades de códigos de blocos lineares são usadas em muitas aplicações. Por exemplo, a propriedade de singularidade de síndrome-coset de códigos de bloco lineares é usada na modelagem de ^{treliças,[7]} 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. Isso é como convolução usada em sistemas LTI para encontrar a saída de um sistema, quando você conhece a resposta de entrada e impulso.

Então, geralmente encontramos a saída do codificador convolucional do sistema, que é a convolução da broca de entrada, contra os estados do codificador de convolução, registra.

Fundamentalmente, os códigos convulsionais 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 tem memória de estado e alguma lógica de feedback, normalmente portões XOR. O decodificador pode ser implementado em software ou firmware.

O algoritmo Viterbi é o algoritmo ideal usado para decodificar códigos convulsionais. Há simplificações para reduzir a carga computacional. Eles dependem apenas de procurar apenas os caminhos mais prováveis. Embora não sejam ótimos, eles geralmente têm sido encontrados para dar bons resultados em ambientes com baixo ruído.

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

Codificação criptográfica

Criptografia ou codificação criptográfica é a prática e o estudo de técnicas de comunicação segura na presença de terceiros (chamados adversários). De forma mais geral, trata-se de construir e analisar protocolos que bloqueiam adversários; Vários aspetos na segurança da informação, como confidencialidade de dados, integridade de dados, autenticação e não repúdio^[10] são centrais para a criptografia moderna. A criptografia moderna existe na intersecção das disciplinas de matemática, ciência da computação e engenharia elétrica. Os aplicativos 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 para um absurdo aparente. O criador 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 que pessoas indesejadas fizessem o mesmo. Desde a Primeira Guerra Mundial e o advento do computador, os métodos usados para realizar a criptografia 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 tais 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; os avanços teóricos, por exemplo, melhorias nos algoritmos de faturação de inteiros e a tecnologia de computação mais rápida exigem que essas soluções sejam continuamente adaptadas. Existem esquemas teoricamente seguros de informação que comprovadamente 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 com base em segurança.

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 dentro de um sistema de comunicação para fins de transmissão de banda base. A codificação de linha é frequentemente usada para o transporte digital de dados.

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

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 para que uma mudança de fase possa ser facilmente detetada e corrigida e que vários sinais possam ser enviados no mesmo canal. ^{[citação necessária]}

Outra aplicação de códigos, usado em alguns sistemas de telefonia móvel, é o CDMA (Code-Division Multiple Access). Cada telefone recebe uma sequência de código que é aproximadamente não corrigida com os códigos de outros telefones. ^{[citação necessária]} Ao transmitir, a palavra código é usada para modular os bits de dados que representam a mensagem de voz. No recetor, é realizado um processo de desmodulação 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 recetor, os sinais de outros usuários aparecerão para o demodulador apenas como um ruído de baixo nível. ^{[citação necessária]}

Outra classe geral de códigos são os códigos arq (automatic repeat-request). 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 recetor pedirá ao remetente que retransmita a mensagem. Todos, exceto os protocolos de rede de área ampla mais simples, usam ARQ. Protocolos comuns incluem SDLC (IBM), TCP (Internet), X.25 (Internacional) e muitos outros. Há um extenso campo de pesquisa sobre este tema devido ao problema de combinar um pacote rejeitado com um novo pacote. É novo ou é uma retransmissão? Normalmente, esquemas de numeração são usados, como no TCP. "RFC793". RFCs. Força-Tarefa de Engenharia da Internet (IETF). Setembro de 1981.

Testes emgrupo

O teste em grupo usa códigos de uma maneira diferente. Considere um grande grupo de itens em que poucos são diferentes de uma forma particular (por exemplo, produtos defeituosos ou sujeitos de teste infetados). A ideia do teste em grupo é determinar quais itens são "diferentes" usando o menor número possível de testes. A origem do problema tem suas raízes na Segunda Guerra Mundial, quando as Forças Aéreas do Exército dos Estados Unidos precisavam testar seus soldados para sífilis.

Codificação analógica

A informação é codificada analogamente nas redes neurais do cérebro, no processamento de sinais analógicos e na eletrônica analógica. Os aspetos da codificação analógica incluem correção de erro analógico^, compressão de dados analógico e criptografia analógica.

Codificação neural

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

treliças,[7]

[10]

,

Teoria da codificação

Conteúdo

História da teoria da codificação

Codificação de origem