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 . A taxa de código base é tipicamente dada como , onde é a taxa de dados de entrada bruta e é a taxa de dados do fluxo codificado do canal de saída. é menor que porque a codificação de canal insere redundância nos bits de entrada. A memória é frequentemente chamada de "comprimento de restrição" , onde a saída é uma função da entrada atual bem como das entradas anteriores. A profundidade também pode ser dada como o número de elementos de memória no polinômio ou o número máximo possível de estados do codificador (tipicamente: ).
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' pode ser perfurado para uma taxa mais alta de, por exemplo, 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.
História 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.Benedetto, Sergio, and Guido Montorsi. "Role of recursive convolutional codes in turbo codes." Electronics Letters 31.11 (1995): 858-859.
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).
Onde os códigos convolucionais são usados thumb|right|400px|Estágios da codificação de canal no GSM.Eberspächer J. et al. GSM-architecture, protocols and services. John Wiley & Sons, 2008. p.97 Codificador de bloco e verificação de paridade – parte de detecção de erros. Codificador convolucional e decodificador Viterbi – parte de correção de erros. Intercalamento e desintercalamento – separação de palavras-código aumentando no domínio do tempo e para evitar distorções em rajada.
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)3rd Generation Partnership Project (September 2012). "3GGP TS45.001: Technical Specification Group GSM/EDGE Radio Access Network; Physical layer on the radio path; General description". Retrieved 2013-07-20.Halonen, Timo, Javier Romero, and Juan Melero, eds. GSM, GPRS and EDGE performance: evolution towards 3G/UMTS. John Wiley & Sons, 2004. p. 430) e comunicações via satélite.Butman, S. A., L. J. Deutsch, and R. L. Miller. "Performance of concatenated codes for deep space missions." The Telecommunications and Data Acquisition Progress Report 42-63, March–April 1981 (1981): 33-39. 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.
Codificação convolucional 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 é: , , , ), e n polinômios geradores — um para cada somador (veja a figura abaixo). Um bit de entrada m1 é 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 (m1 move para m0, m0 move para m−1) 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). frame|Img.1. Codificador convolucional não recursivo, não sistemático, taxa 1/3, com comprimento de restrição 3 A figura abaixo é um codificador de taxa () com comprimento de restrição (k) de 3. Os polinômios geradores são , e . Portanto, os bits de saída são calculados (módulo 2) como segue: n1 = m1 + m0 + m−1 n2 = m0 + m−1 n3 = m1 + m−1.
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.Moon, Todd K. "Error correction coding." Mathematical Methods and Algorithms. John Wiley and Son (2005). p. 508
Códigos recursivos e não recursivos 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:
thumb|340px|none|Img.2. Codificador convolucional sistemático recursivo de taxa 1/2 com 8 estados. Usado como código constituinte no Código Turbo 3GPP 25.212.
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 (23). 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:
thumb|340px|none|Img. 3. Código convolucional sistemático recursivo (RSC) de dois estados. Também chamado de 'acumulador'.
Útil para implementação de códigos LDPC e como código constituinte interno para códigos convolucionais concatenados seriais (SCCC's).
thumb|340px|none|Img. 4. Código convolucional sistemático recursivo (RSC) de quatro estados.
Útil para SCCC's e códigos turbo multidimensionais.
thumb|340px|none|Img. 5. Código convolucional sistemático recursivo (RSC) de dezesseis estados.
Ú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.
Resposta ao impulso, função de transferência e comprimento de restrição Um codificador convolucional é chamado assim porque realiza uma convolução do fluxo de entrada com as respostas ao impulso do codificador:
onde é uma sequência de entrada, é uma sequência da saída , é uma resposta ao impulso para a saída e 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:
Funções de transferência para o segundo codificador (recursivo) são:
Defina por
onde, para qualquer função racional , .
Então é o máximo dos graus polinomiais dos
, e o comprimento de restrição é definido como . Por exemplo, no primeiro exemplo o comprimento de restrição é 3, e no segundo o comprimento de restrição é 4.
Diagrama de treliça
Um codificador convolucional é uma máquina de estados finitos. Um codificador com n células binárias terá 2n estados.
Imagine que o codificador (mostrado na Img.1, acima) tem '1' na célula de memória esquerda (m0) e '0' na direita (m−1). (m1 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:
left|thumb|340px|Img.6. Um diagrama de treliça para o codificador na Img.1. Um caminho através da treliça é mostrado como uma linha vermelha. As linhas sólidas indicam transições onde um "0" é inserido e as linhas tracejadas onde um "1" é inserido.
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.
Distância livre e distribuição de erros