Código convolucional - Convolutional code

Em telecomunicações , um código convolucional é um tipo de código de correção de erros que gera símbolos de paridade por meio da aplicação deslizante de uma função polinomial booleana a um fluxo de dados. O aplicativo 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 da treliça usando uma treliça invariante no tempo. A decodificação de treliça invariante no tempo permite que os códigos convolucionais sejam decodificados por decisão suave de máxima verossimilhança com complexidade razoável.

A capacidade de realizar a decodificação de decisão suave de máxima verossimilhança econômica é um dos principais benefícios dos códigos convolucionais. Isso está em contraste com os códigos de bloco clássicos, que geralmente são representados por uma treliça de variação no tempo e, portanto, são normalmente decodificados por decisão difícil. 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 é normalmente fornecida como , onde n é a taxa de dados de entrada bruta ek é a taxa de dados do fluxo codificado do canal de saída. n é menor que k porque a codificação do 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 entradas anteriores . A profundidade também pode ser fornecida 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 (normalmente:) .

Os códigos convolucionais são freqüentemente descritos como contínuos. No entanto, também pode ser dito que os códigos convolucionais têm comprimento de bloco arbitrário, em vez de serem contínuos, uma vez que a maior parte da codificação convolucional do mundo real é realizada em blocos de dados. Os códigos de bloco codificados convolucionalmente geralmente empregam terminação. O comprimento de bloco arbitrário de códigos convolucionais também pode ser contrastado com os códigos de bloco clássicos , que geralmente têm comprimentos de bloco fixos que são determinados por propriedades algébricas.

A taxa de código de um código convolucional é comumente modificada por meio de punção de símbolo . 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 por não transmitir 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 de decisão suave em códigos convolucionais, bem como o comprimento do bloco e a flexibilidade da 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 . Pensou-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 de probabilidade máxima 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 .

Os códigos convolucionais sistemáticos recursivos foram inventados por Claude Berrou por volta de 1991. Esses códigos se mostraram especialmente úteis para processamento iterativo, incluindo o processamento de códigos concatenados, como códigos turbo .

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

Onde códigos convolucionais são usados

Estágios de codificação de canal em GSM. Codificador de bloco e verificação de paridade - parte de detecção de erro. Codificador convolucional e decodificador Viterbi - parte de correção de erros. Intercalação e desintercalação - separação de palavras de código aumentando no domínio do tempo e para evitar distorções em rajadas.

Os códigos convolucionais são usados ​​extensivamente para obter transferência confiável de dados em várias aplicações, como vídeo digital , rádio, comunicações móveis (por exemplo, em redes GSM, GPRS, EDGE e 3G (até o 3GPP Versão 7)) e comunicações por satélite . Esses códigos são frequentemente implementados em concatenação com um código de decisão difícil, particularmente Reed – Solomon . Antes dos códigos turbo, essas 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 contendo um bit de entrada. A menos que especificado de outra forma, todos os registros 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 adicionador (ver figura abaixo). Um bit de entrada m 1 é alimentado no registro mais à esquerda. Usando os polinômios geradores e os valores existentes nos registros restantes, o codificador emite n símbolos. Esses símbolos podem ser transmitidos ou perfurados dependendo da taxa de código desejada. Agora o bit desloca todos os valores de registro para a direita ( m 1 move-se para m 0 , m 0 move-se para m -1 ) e espera pelo próximo bit de entrada. Se não houver bits de entrada restantes, o codificador continua deslocando até que todos os registros tenham retornado ao estado zero (terminação do bit de limpeza).

Img.1. Taxa 1/3 codificador convolucional não recursivo e não sistemático com comprimento de restrição 3

A figura abaixo é um codificador de taxa 13 ( mn ) com comprimento de restrição ( k ) de 3. Os polinômios do gerador são G 1 = (1,1,1), G 2 = (0,1,1) e G 3 = (1,0,1) . Portanto, os bits de saída são calculados (módulo 2) da seguinte forma:

n 1 = m 1 + m 0 + m −1
n 2 = m 0 + m −1
n 3 = m 1 + m −1 .

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

  • sistemática repete a estrutura da mensagem antes da codificação
  • mudanças não sistemáticas da estrutura inicial

Os códigos convolucionais não sistemáticos são mais populares devido à melhor imunidade a ruídos. Refere-se à distância livre do código convolucional.

Códigos recursivos e não recursivos

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

Img.2. Taxa 1/2 codificador convolucional sistemático recursivo de 8 estados. Usado como código constituinte no 3GPP 25.212 Turbo Code.

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). Os códigos com símbolos de saída que não incluem os dados de entrada são chamados de não sistemáticos.

Os códigos recursivos são tipicamente sistemáticos e, ao contrário, os 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 em Img. 2. é um codificador de 8 estados porque os 3 registros criarão 8 estados de codificador possíveis (2 3 ). Uma treliça de decodificador correspondente normalmente usará 8 estados também.

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

Outros códigos RSC e aplicativos de exemplo incluem:

Img. 3. Código convolucional sistemático recursivo de dois estados (RSC). Também chamado de 'acumulador'.

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

Img. 4. Código convolucional sistemático recursivo de quatro estados (RSC).

Útil para SCCC e códigos turbo multidimensionais.

Img. 5. Código convolucional sistemático recursivo de dezesseis estados (RSC).

Útil como código constituinte em códigos turbo de baixa taxa de erro para aplicativos como links de 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 de impulso do codificador :

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 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 de impulso é conectado com uma função de transferência através de Z-transform .

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

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

Definir m por

onde, para qualquer função racional ,

.

Então m é o máximo dos graus polinomiais de , e o comprimento da restrição é definido como . Por exemplo, no primeiro exemplo, o comprimento da restrição é 3 e, no segundo, o comprimento da 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á 2 n estados.

Imagine que o codificador (mostrado na Figura 1, acima) tenha '1' na célula de memória esquerda ( m 0 ) e '0' na direita ( m -1 ). ( m 1 não é realmente uma célula de memória porque representa um valor atual). Iremos designar esse estado como "10". De acordo com um bit de entrada, o codificador na próxima volta pode ser convertido para o estado "01" ou para o estado "11". Pode-se ver que nem todas as transições são possíveis para (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 como abaixo:

Img.6. Um diagrama de treliça para o codificador em Img.1. Um caminho através da treliça é mostrado como uma linha vermelha. As linhas sólidas indicam as 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 a decodificação : se uma seqüência recebida não se encaixa neste gráfico, então ela foi recebida com erros, e devemos escolher a seqüência correta mais próxima (ajustando-se ao gráfico). Os verdadeiros algoritmos de decodificação exploram essa ideia.

Distância livre e distribuição de erros

Curvas de taxa de erro de bit teóricas de QPSK codificado (recursivo e não recursivo, decisão suave), canal de ruído gaussiano branco aditivo. As curvas são pequenas distintas devido a aproximadamente as mesmas distâncias livres e pesos.

A distância livre ( 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. Pode ser calculado como

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

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

Decodificando códigos convolucionais

Curvas de razão de erro de bit para códigos convolucionais com diferentes opções de modulações digitais ( QPSK, 8-PSK , 16-QAM, 64-QAM ) e Algoritmos LLR . (Exato e Aproximado) sobre o canal de ruído gaussiano branco aditivo.

Existem vários algoritmos para decodificar códigos convolucionais. Para valores relativamente pequenos de k , o algoritmo de Viterbi é usado universalmente, pois fornece desempenho de máxima verossimilhança e é altamente paralelizável. Os 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 de restrição mais longos são decodificados de forma mais prática 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 probabilidade máxima, mas sua complexidade aumenta apenas ligeiramente com o comprimento da restrição, permitindo o uso de códigos de comprimento de restrição fortes e longos. Esses 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 erro Reed-Solomon que aumentam a curva geral da taxa de erro de bits e produzem taxas de erro residuais não detectadas extremamente baixas.

Ambos os algoritmos de decodificação sequencial e Viterbi retornam decisões difíceis: 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 de saída suave . As decisões suaves de Maximum a posteriori (MAP) para cada bit podem ser obtidas pelo uso do algoritmo BCJR .

Códigos convolucionais populares

Registro de deslocamento para o polinômio do código convolucional (7, [171, 133]). Ramos: , . Todas as operações matemáticas devem ser feitas pelo módulo 2.
Curvas de taxa de erro de bit teóricas de QPSK codificado (decisão suave), canal de ruído gaussiano branco aditivo. Comprimentos de restrição mais longos produzem códigos mais poderosos, mas a complexidade do algoritmo de Viterbi aumenta exponencialmente com os comprimentos de restrição, limitando esses códigos mais poderosos a missões no espaço profundo onde o desempenho extra facilmente compensa o aumento da complexidade do decodificador.

Na verdade, estruturas de códigos convolucionais pré-definidas obtidas durante pesquisas científicas são utilizadas na indústria. Isso está relacionado à possibilidade de selecionar códigos convolucionais catastróficos (causa 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.

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 um desempenho cerca de 2 dB melhor do que o código mais simples a um custo de 256 × na complexidade de decodificação (em comparação com os códigos de missão da Voyager).

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

Códigos convolucionais puncionados

Códigos convolucionais com taxas de código 1/2 e 3/4 (e comprimento de restrição 7, decisão suave, 4-QAM / QPSK / OQPSK).

O código convolucional com qualquer taxa de código pode ser projetado com base na seleção polinomial; entretanto, na prática, um procedimento de puncionamento é freqüentemente usado para atingir a taxa de código necessária. A punção é uma técnica usada para fazer um código de taxa m / n a partir de um código "básico" de taxa baixa (por exemplo, 1 / n ). Isso é obtido pela exclusão de alguns bits na saída do codificador. Os bits são excluídos de acordo com uma matriz de punção . As seguintes matrizes de punção são as mais frequentemente utilizadas:

Taxa de código Matriz de punção Distância livre (para o padrão da NASA K = 7 código convolucional)
1/2
(sem perf.)
1
1
10
2/3
1 0
1 1
6
3/4
1 0 1
1 1 0
5
5/6
1 0 1 0 1
1 1 0 1 0
4
7/8
1 0 0 0 1 0 1
1 1 1 1 0 1 0
3

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

Os códigos convolucionais puncionados são amplamente utilizados nas comunicações por satélite , por exemplo, em sistemas INTELSAT e Digital Video Broadcasting .

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

Códigos turbo: substituindo códigos convolucionais

Um código turbo com códigos de componente 13, 15. Os códigos turbo recebem esse nome porque o decodificador usa feedback, como um motor turbo. Permutação significa o mesmo que intercalação. C1 e C2 são códigos convolucionais recursivos. Os códigos convolucionais recursivos e não recursivos não são muito diferentes no desempenho do BER, no entanto, o tipo recursivo de é implementado nos códigos convolucionais Turbo devido às melhores propriedades de intercalação.

Códigos convolucionais simples decodificados por Viterbi estão agora dando lugar aos turbo códigos , uma nova classe de códigos convolucionais curtos iterados que se aproximam dos limites teóricos impostos pelo teorema de Shannon com muito menos complexidade de decodificação do que o algoritmo de Viterbi nos códigos convolucionais longos 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 de pisos de erro inerentes aos projetos de código turbo.

Veja também

Referências

  • Domínio público Este artigo incorpora  material de domínio público do documento General Services Administration : "Federal Standard 1037C" .

links externos

Leitura adicional

Publicações

  • Francis, Michael. "Viterbi Decoder Block Decoding-Trellis Termination and Tail Biting." Xilinx XAPP551 v2. 0, DD (2005): 1-21.
  • Chen, Qingchun, Wai Ho Mow e Pingzhi Fan. "Alguns novos resultados sobre códigos convolucionais recursivos e suas aplicações." Workshop de Teoria da Informação, 2006. ITW'06 Chengdu. IEEE. IEEE, 2006.
  • Fiebig, UC. E Patrick Robertson. "Decodificação de decisão suave e eliminação em sistemas de salto de frequência rápido com códigos convolucionais, turbo e Reed-Solomon." IEEE Transactions on Communications 47.11 (1999): 1646-1654.
  • Bhaskar, Vidhyacharan e Laurie L. Joiner. "Desempenho de códigos convolucionais perfurados em comunicações CDMA assíncronas sob condições perfeitas de rastreamento de fase." Computadores e Engenharia Elétrica 30.8 (2004): 573-592.
  • Modestino, J. e Shou Mui. "Desempenho de código convolucional no canal de desvanecimento riciano." IEEE Transactions on Communications 24.6 (1976): 592-606.
  • Chen, Yuh-Long e Che-Ho Wei. "Avaliação de desempenho de códigos convolucionais com MPSK em canais de desvanecimento Rician." Procedimentos IEE F-Communications, Radar and Signal Processing. Vol. 134. No. 2. IET, 1987.