Código convolucional 📖 Wikipedia

Em telecomunicação, um código convolucional é um tipo de código corretor de erros que gera símbolos de paridade através da aplicação deslizante de uma função polinomial booleana a um fluxo de dados. A aplicação deslizante representa a 'convolução' do codificador sobre os dados, o que dá origem ao termo 'codificação convolucional'. A natureza deslizante dos códigos convolucionais facilita a decodificação em treliça usando uma treliça invariante no tempo. A decodificação em treliça invariante no tempo permite que códigos convolucionais sejam decodificados por máxima verossimilhança com decisão branda e com complexidade razoável.

A capacidade de realizar decodificação econômica por máxima verossimilhança com decisão branda é um dos principais benefícios dos códigos convolucionais. Isso contrasta com os códigos de bloco clássicos, que geralmente são representados por uma treliça variante no tempo e, portanto, são tipicamente decodificados com decisão firme. Os códigos convolucionais são frequentemente caracterizados pela taxa de código base e pela profundidade (ou memória) do codificador ${\displaystyle [n,k,K]}$. A taxa de código base é tipicamente dada como ${\displaystyle k/n}$, onde k é a taxa de dados de entrada bruta e n é a taxa de dados do fluxo codificado do canal de saída. k é menor que n porque a codificação de canal insere redundância nos bits de entrada. A memória é frequentemente chamada de "comprimento de restrição" K, onde a saída é uma função da entrada atual bem como das ${\displaystyle K-1}$ entradas anteriores.^[1] A profundidade também pode ser dada como o número de elementos de memória v no polinômio ou o número máximo possível de estados do codificador (tipicamente: ${\displaystyle 2^{v}}$).

Os códigos convolucionais são frequentemente descritos como contínuos. No entanto, também se pode dizer que os códigos convolucionais têm comprimento de bloco arbitrário, em vez de serem contínuos, uma vez que a maioria das codificações convolucionais do mundo real é realizada em blocos de dados. Códigos de bloco codificados convolucionalmente tipicamente empregam terminação. O comprimento de bloco arbitrário dos códigos convolucionais também pode ser contrastado com os códigos de bloco clássicos, que geralmente têm comprimentos de bloco fixos determinados por propriedades algébricas.

A taxa de código de um código convolucional é comumente modificada via perfuração de símbolos. Por exemplo, um código convolucional com uma taxa de código 'mãe' ${\displaystyle n/k=1/2}$ pode ser perfurado para uma taxa mais alta de, por exemplo, ${\displaystyle 7/8}$ simplesmente não transmitindo uma parte dos símbolos de código. O desempenho de um código convolucional perfurado geralmente escala bem com a quantidade de paridade transmitida. A capacidade de realizar decodificação econômica com decisão branda em códigos convolucionais, bem como a flexibilidade de comprimento de bloco e taxa de código dos códigos convolucionais, os torna muito populares para comunicações digitais.

Os códigos convolucionais foram introduzidos em 1955 por Peter Elias. Pensava-se que os códigos convolucionais poderiam ser decodificados com qualidade arbitrária às custas de computação e atraso. Em 1967, Andrew Viterbi determinou que os códigos convolucionais poderiam ser decodificados por máxima verossimilhança com complexidade razoável usando decodificadores baseados em treliça invariante no tempo — o algoritmo de Viterbi. Outros algoritmos de decodificação baseados em treliça foram desenvolvidos posteriormente, incluindo o algoritmo de decodificação BCJR.

Códigos convolucionais sistemáticos recursivos foram inventados por Claude Berrou por volta de 1991. Esses códigos provaram ser especialmente úteis para processamento iterativo, incluindo o processamento de códigos concatenados, como códigos turbo.^[2]

Usando a terminologia "convolucional", um código convolucional clássico poderia ser considerado um filtro de resposta ao impulso finita (FIR), enquanto um código convolucional recursivo poderia ser considerado um filtro de resposta ao impulso infinita (IIR).

Os códigos convolucionais são extensivamente usados para alcançar transferência confiável de dados em inúmeras aplicações, como vídeo digital, rádio, comunicações móveis (por exemplo, em redes GSM, GPRS, EDGE e 3G (até 3GPP Release 7)^[4][5]) e comunicações via satélite.^[6] Esses códigos são frequentemente implementados em concatenação com um código de decisão firme, particularmente Reed–Solomon. Antes dos códigos turbo, tais construções eram as mais eficientes, chegando mais perto do limite de Shannon.

Para codificar dados convolucionalmente, comece com k registradores de memória, cada um armazenando um bit de entrada. Salvo especificação em contrário, todos os registradores de memória começam com um valor de 0. O codificador tem n somadores módulo-2 (um somador módulo 2 pode ser implementado com uma única porta booleana XOR, onde a lógica é: 0+0 = 0, 0+1 = 1, 1+0 = 1, 1+1 = 0), e n polinômios geradores — um para cada somador (veja a figura abaixo). Um bit de entrada m₁ é alimentado no registrador mais à esquerda. Usando os polinômios geradores e os valores existentes nos registradores restantes, o codificador produz n símbolos. Esses símbolos podem ser transmitidos ou perfurados dependendo da taxa de código desejada. Agora, desloque todos os valores dos registradores para a direita (m₁ move para m₀, m₀ move para m₋₁) e aguarde o próximo bit de entrada. Se não houver mais bits de entrada, o codificador continua deslocando até que todos os registradores tenham retornado ao estado zero (terminação com bits de descarga).

A figura abaixo é um codificador de taxa 1⁄3 (m⁄n) com comprimento de restrição (k) de 3. Os polinômios geradores são G₁ = (1,1,1), G₂ = (0,1,1), e G₃ = (1,0,1). Portanto, os bits de saída são calculados (módulo 2) como segue:

n₁ = m₁ + m₀ + m₋₁

n₂ = m₀ + m₋₁

n₃ = m₁ + m₋₁.

Os códigos convolucionais podem ser sistemáticos e não sistemáticos:

• sistemático repete a estrutura da mensagem antes da codificação
• não sistemático altera a estrutura inicial

Os códigos convolucionais não sistemáticos são mais populares devido à melhor imunidade a ruído. Isso está relacionado à distância livre do código convolucional.^[7]

• 
  Uma breve ilustração de código convolucional não sistemático.
• 
  Uma breve ilustração de código convolucional sistemático.

O codificador na figura acima é um codificador não recursivo. Aqui está um exemplo de um codificador recursivo e, como tal, admite uma estrutura de realimentação:

O codificador de exemplo é sistemático porque os dados de entrada também são usados nos símbolos de saída (Saída 2). Códigos com símbolos de saída que não incluem os dados de entrada são chamados de não sistemáticos.

Códigos recursivos são tipicamente sistemáticos e, inversamente, códigos não recursivos são tipicamente não sistemáticos. Não é um requisito estrito, mas uma prática comum.

O codificador de exemplo na Img. 2 é um codificador de 8 estados porque os 3 registradores criarão 8 possíveis estados do codificador (2³). Uma treliça de decodificador correspondente tipicamente usará também 8 estados.

Códigos convolucionais sistemáticos recursivos (RSC) tornaram-se mais populares devido ao seu uso em Códigos Turbo. Códigos sistemáticos recursivos também são chamados de códigos pseudo-sistemáticos.

Outros códigos RSC e exemplos de aplicações incluem:

Útil para implementação de códigos LDPC e como código constituinte interno para códigos convolucionais concatenados seriais (SCCC's).

Útil para SCCC's e códigos turbo multidimensionais.

Útil como código constituinte em códigos turbo de baixa taxa de erro para aplicações como links via satélite. Também adequado como código externo SCCC.

Um codificador convolucional é chamado assim porque realiza uma convolução do fluxo de entrada com as respostas ao impulso do codificador:

${\displaystyle y_{i}^{j}=\sum _{k=0}^{\infty }h_{k}^{j}x_{i-k}=(x*h^{j})[i],}$

onde x é uma sequência de entrada, y^j é uma sequência da saída j, h^j é uma resposta ao impulso para a saída j e ${\displaystyle {*}}$ denota convolução.

Um codificador convolucional é um sistema linear invariante no tempo discreto. Cada saída de um codificador pode ser descrita por sua própria função de transferência, que está intimamente relacionada ao polinômio gerador. Uma resposta ao impulso está conectada com uma função de transferência através da transformada Z.

Funções de transferência para o primeiro codificador (não recursivo) são:

• ${\displaystyle H_{1}(z)=1+z^{-1}+z^{-2},\,}$
• ${\displaystyle H_{2}(z)=z^{-1}+z^{-2},\,}$
• ${\displaystyle H_{3}(z)=1+z^{-2}.\,}$

Funções de transferência para o segundo codificador (recursivo) são:

• ${\displaystyle H_{1}(z)={\frac {1+z^{-1}+z^{-3}}{1-z^{-2}-z^{-3}}},\,}$
• ${\displaystyle H_{2}(z)=1.\,}$

Defina m por

${\displaystyle m=\max _{i}\operatorname {polydeg} (H_{i}(1/z))\,}$

onde, para qualquer função racional ${\displaystyle f(z)=P(z)/Q(z)\,}$,

${\displaystyle \operatorname {polydeg} (f)=\max(\deg(P),\deg(Q))\,}$.

Então m é o máximo dos graus polinomiais dos

${\displaystyle H_{i}(1/z)\,}$, e o comprimento de restrição é definido como ${\displaystyle K=m+1\,}$. Por exemplo, no primeiro exemplo o comprimento de restrição é 3, e no segundo o comprimento de restrição é 4.

Um codificador convolucional é uma máquina de estados finitos. Um codificador com n células binárias terá 2ⁿ estados.

Imagine que o codificador (mostrado na Img.1, acima) tem '1' na célula de memória esquerda (m₀) e '0' na direita (m₋₁). (m₁ não é realmente uma célula de memória porque representa um valor atual). Vamos designar tal estado como "10". De acordo com um bit de entrada, o codificador na próxima vez pode converter para o estado "01" ou para o estado "11". Pode-se ver que nem todas as transições são possíveis (por exemplo, um decodificador não pode converter do estado "10" para "00" ou mesmo permanecer no estado "10").

Todas as transições possíveis podem ser mostradas abaixo:

Uma sequência codificada real pode ser representada como um caminho neste gráfico. Um caminho válido é mostrado em vermelho como exemplo.

Este diagrama nos dá uma ideia sobre decodificação: se uma sequência recebida não se encaixa neste gráfico, então ela foi recebida com erros, e devemos escolher a sequência correta mais próxima (que se encaixa no gráfico). Os algoritmos de decodificação reais exploram esta ideia.

A distância livre^[8] (d) é a distância de Hamming mínima entre diferentes sequências codificadas. A capacidade de correção (t) de um código convolucional é o número de erros que podem ser corrigidos pelo código. Ela pode ser calculada como

${\displaystyle t=\left\lfloor {\frac {d-1}{2}}\right\rfloor .}$

Como um código convolucional não usa blocos, processando em vez disso um fluxo contínuo de bits, o valor de t se aplica a uma quantidade de erros localizados relativamente próximos uns dos outros. Ou seja, múltiplos grupos de t erros geralmente podem ser corrigidos quando estão relativamente distantes entre si.

A distância livre pode ser interpretada como o comprimento mínimo de uma "rajada" errônea na saída de um decodificador convolucional. O fato de que os erros aparecem como "rajadas" deve ser levado em conta ao projetar um código concatenado com um código convolucional interno. A solução popular para este problema é intercalar dados antes da codificação convolucional, para que o código de bloco externo (geralmente Reed–Solomon) possa corrigir a maioria dos erros.

Vários algoritmos existem para decodificar códigos convolucionais. Para valores relativamente pequenos de k, o algoritmo de Viterbi é universalmente usado, pois fornece desempenho de máxima verossimilhança e é altamente paralelizável. Decodificadores Viterbi são, portanto, fáceis de implementar em hardware VLSI e em software em CPUs com conjuntos de instruções SIMD.

Códigos com comprimento de restrição mais longo são mais praticamente decodificados com qualquer um dos vários algoritmos de decodificação sequencial, dos quais o algoritmo de Fano é o mais conhecido. Ao contrário da decodificação de Viterbi, a decodificação sequencial não é de máxima verossimilhança, mas sua complexidade aumenta apenas ligeiramente com o comprimento de restrição, permitindo o uso de códigos fortes de longo comprimento de restrição. Tais códigos foram usados no Programa Pioneer do início dos anos 1970 para Júpiter e Saturno, mas deram lugar a códigos mais curtos, decodificados por Viterbi, geralmente concatenados com grandes códigos de correção de erros Reed–Solomon que acentuam a curva geral da taxa de erro de bit e produzem taxas de erro residual não detectado extremamente baixas.

Tanto os algoritmos de decodificação de Viterbi quanto os sequenciais retornam decisões firmes: os bits que formam a palavra-código mais provável. Uma medida de confiança aproximada pode ser adicionada a cada bit usando o algoritmo de Viterbi com saída branda. Decisões brandas de máxima probabilidade a posteriori (MAP) para cada bit podem ser obtidas usando o algoritmo BCJR.

Na verdade, estruturas de códigos convolucionais predefinidas obtidas durante pesquisas científicas são usadas na indústria. Isso se relaciona com a possibilidade de selecionar códigos convolucionais catastróficos (causam maior número de erros).

Um código convolucional decodificado por Viterbi especialmente popular, usado pelo menos desde o Programa Voyager, tem um comprimento de restrição K de 7 e uma taxa r de 1/2.^[13]

Mars Pathfinder, Mars Exploration Rover e a sonda Cassini para Saturno usam um K de 15 e uma taxa de 1/6; este código tem desempenho cerca de 2 dB melhor que o código ${\displaystyle K=7}$ mais simples ao custo de 256× na complexidade de decodificação (comparado aos códigos da missão Voyager).

O código convolucional com comprimento de restrição 2 e taxa de 1/2 é usado no GSM como uma técnica de correção de erros.^[14]

Um código convolucional com qualquer taxa de código pode ser projetado com base na seleção de polinômios;^[16] no entanto, na prática, um procedimento de perfuração é frequentemente usado para alcançar a taxa de código desejada. A perfuração é uma técnica usada para fazer um código de taxa m/n a partir de um código "básico" de baixa taxa (por exemplo, 1/n). É alcançada pela exclusão de alguns bits na saída do codificador. Os bits são excluídos de acordo com uma matriz de perfuração. As seguintes matrizes de perfuração são as mais frequentemente usadas:

Por exemplo, se quisermos fazer um código com taxa 2/3 usando a matriz apropriada da tabela acima, devemos tomar uma saída de codificador básica e transmitir cada primeiro bit do primeiro ramo e cada bit do segundo. A ordem específica de transmissão é definida pelo padrão de comunicação respectivo.

Códigos convolucionais perfurados são amplamente usados em comunicações via satélite, por exemplo, em sistemas Intelsat e Radiodifusão de Vídeo Digital.

Códigos convolucionais perfurados também são chamados de "perfurados".

Códigos convolucionais simples decodificados por Viterbi estão agora dando lugar aos códigos turbo, uma nova classe de códigos convolucionais curtos iterados que se aproximam estreitamente dos limites teóricos impostos pelo teorema de Shannon com muito menos complexidade de decodificação do que o algoritmo de Viterbi nos longos códigos convolucionais que seriam necessários para o mesmo desempenho. A concatenação com um código algébrico externo (por exemplo, Reed–Solomon) aborda a questão dos pisos de erro inerentes aos projetos de códigos turbo.

• Código convolucional quântico

• O livro-texto online: Information Theory, Inference, and Learning Algorithms, de David J.C. MacKay, discute códigos convolucionais no Capítulo 48.
• A página de Códigos Corretores de Erros (ECC)
• Explicações Matlab
• Fundamentos de Decodificadores Convolucionais para Melhores Comunicações Digitais
• Códigos convolucionais (MIT)
• Information Theory and Coding (TU Ilmenau) Arquivado em 2017-08-30 no Wayback Machine, discute códigos convolucionais na página 48.