Na teoria de códigos, os códigos concatenados formam uma classe de códigos de correção de erros que são derivados combinando um código interno e um código externo. Eles foram concebidos em 1966 por Dave Forney como uma solução para o problema de encontrar um código que tenha simultaneamente uma probabilidade de erro decrescente exponencialmente com o aumento do comprimento do bloco e uma complexidade de decodificação em tempo polinomial. Os códigos concatenados tornaram-se amplamente utilizados em comunicações espaciais na década de 1970.
Contexto teórico O campo da codificação de canal preocupa-se em enviar um fluxo de dados na maior taxa possível através de um dado canal de comunicações e, em seguida, decodificar os dados originais de forma confiável no receptor, usando algoritmos de codificação e decodificação que sejam viáveis de implementar em uma determinada tecnologia.
O teorema de codificação de canal de Shannon mostra que, em muitos canais comuns, existem esquemas de codificação de canal capazes de transmitir dados de forma confiável em todas as taxas menores que um certo limiar , chamado de capacidade de canal do dado canal. De fato, a probabilidade de erro de decodificação pode ser feita decrescer exponencialmente à medida que o comprimento do bloco do esquema de codificação tende ao infinito. No entanto, a complexidade de um esquema de decodificação ótimo ingênuo, que simplesmente calcula a verossimilhança de cada palavra-código transmitida possível, aumenta exponencialmente com , de modo que tal decodificador ótimo torna-se rapidamente inviável.
Em sua tese de doutorado, Dave Forney mostrou que os códigos concatenados poderiam ser usados para alcançar probabilidades de erro que diminuem exponencialmente em todas as taxas de dados inferiores à capacidade, com uma complexidade de decodificação que aumenta apenas polinomialmente com o comprimento do bloco do código.
Descrição miniaturadaimagem|Representação esquemática de um código concatenado construído sobre um código interno e um código externo. miniaturadaimagem|400x400px|Esta é uma representação pictórica de uma concatenação de código e, em particular, o código de Reed-Solomon com e é usado como código externo e o código de Hadamard com e é usado como código interno. De forma geral, o código concatenado é um código . Seja um código , ou seja, um código de bloco de comprimento , dimensão , distância de Hamming mínima e taxa , sobre um alfabeto :
Seja um código sobre um alfabeto com símbolos:
O código interno recebe uma das entradas possíveis, codifica em uma -upla sobre , transmite e decodifica em uma das saídas possíveis. Consideramos isso como um (super) canal que pode transmitir um símbolo do alfabeto . Utilizamos este canal vezes para transmitir cada um dos símbolos em uma palavra-código de . A concatenação de (como código externo) com (como código interno), denotada por , é portanto um código de comprimento sobre o alfabeto :
Ele mapeia cada mensagem de entrada para uma palavra-código , onde .
A ideia-chave nesta abordagem é que se for decodificado usando uma abordagem de máxima verossimilhança (mostrando, assim, uma probabilidade de erro decrescente exponencialmente com o aumento do comprimento), e for um código com comprimento que pode ser decodificado em tempo polinomial de , então o código concatenado pode ser decodificado em tempo polinomial de seu comprimento combinado e apresenta uma probabilidade de erro que decresce exponencialmente, mesmo que tenha uma complexidade de decodificação exponencial. Isso é discutido em mais detalhes na seção Decodificação de códigos concatenados.
Em uma generalização da concatenação acima, existem possíveis códigos internos e o -ésimo símbolo em uma palavra-código de é transmitido pelo canal interno usando o -ésimo código interno. Os códigos de Justesen são exemplos de códigos concatenados generalizados, onde o código externo é um código de Reed-Solomon.
Propriedades 1. A distância do código concatenado é de pelo menos , isto é, é um código com .
Demonstração: Considere duas mensagens diferentes . Seja a distância entre duas palavras-código. Então
Assim, existem pelo menos posições nas quais a sequência de símbolos das palavras-código e diferem. Para essas posições, denotadas por , temos
Consequentemente, existem pelo menos posições na sequência de símbolos retirados do alfabeto nas quais as duas palavras-código diferem e, portanto,
2. Se e são códigos de bloco lineares, então também é um código de bloco linear.
Esta propriedade pode ser facilmente demonstrada com base na ideia de definir uma matriz geradora para o código concatenado em termos das matrizes geradoras de e .
Decodificação de códigos concatenados Um conceito natural para um algoritmo de decodificação para códigos concatenados é decodificar primeiramente o código interno e, em seguida, o código externo. Para que o algoritmo seja prático, ele deve operar em tempo polinomial em relação ao comprimento do bloco final. Considere que existe um algoritmo de decodificação única em tempo polinomial para o código externo. Agora, temos que encontrar um algoritmo de decodificação em tempo polinomial para o código interno. Entende-se que tempo de execução polinomial aqui significa que o tempo de execução é polinomial no comprimento do bloco final. A ideia principal é que, se o comprimento do bloco interno for selecionado para ser logarítmico em relação ao tamanho do código externo, o algoritmo de decodificação para o código interno poderá ser executado em tempo exponencial do comprimento do bloco interno e, assim, podemos usar um decodificador de máxima verossimilhança (MLD) ótimo, embora de tempo exponencial, para o código interno.
Detalhadamente, seja a entrada do decodificador o vetor . Então o algoritmo de decodificação é um processo de duas etapas:
Use o MLD do código interno para reconstruir um conjunto de palavras-código internas , com , . Execute o algoritmo de decodificação única para sobre .
A complexidade de tempo da primeira etapa é , onde é o comprimento do bloco interno. Em outras palavras, é (isto é, tempo polinomial) em termos do comprimento do bloco externo . Como se assume que o algoritmo de decodificação externo na etapa dois seja executado em tempo polinomial, a complexidade do algoritmo de decodificação como um todo também é de tempo polinomial.
Observações O algoritmo de decodificação descrito acima pode ser usado para corrigir todos os erros até um número inferior a . Usando a decodificação de distância mínima, o decodificador externo pode corrigir todas as entradas com menos de símbolos incorretos. Da mesma forma, o código interno pode corrigir com confiabilidade uma entrada se menos de símbolos internos estiverem errados. Assim, para que um símbolo externo esteja incorreto após a decodificação interna, pelo menos símbolos internos devem ter sofrido erro, e para que o código externo falhe, isso deve ter ocorrido em pelo menos símbolos externos. Consequentemente, o número total de símbolos internos que devem ser recebidos incorretamente para que o código concatenado falhe deve ser de pelo menos .
O algoritmo também funciona se os códigos internos forem diferentes, por exemplo, nos códigos de Justesen. O algoritmo de decodificação de distância mínima generalizada, desenvolvido por Forney, pode ser usado para corrigir até erros. Ele usa informações de apagamento (erasure) do código interno para melhorar o desempenho do código externo, e foi o primeiro exemplo de um algoritmo usando decodificação de decisão suave.
Aplicações Embora um esquema de concatenação simples já tenha sido implementado para a missão do orbitador marciano Mariner em 1971, os códigos concatenados começaram a ser usados regularmente para comunicação no espaço profundo com o Programa Voyager, que lançou duas sondas espaciais em 1977.K. Andrews et al., The Development of Turbo and LDPC Codes for Deep-Space Applications, Proceedings of the IEEE, Vol. 95, No. 11, Nov. 2007. Desde então, os códigos concatenados se tornaram o pilar para uma codificação eficiente de correção de erros, e assim permaneceram pelo menos até a invenção dos turbo códigos e códigos LDPC.
Normalmente, o código interno não é um código de bloco, mas um código convolucional decodificado por Viterbi de decisão suave com um curto comprimento de restrição. Para o código externo, utiliza-se um código de bloco mais longo de decisão rígida, frequentemente um código de Reed-Solomon com símbolos de oito bits. O tamanho de símbolo maior torna o código externo mais robusto a rajadas de erros que podem ocorrer devido a deficiências do canal, e também porque a própria saída errônea do código convolucional ocorre em rajadas. Uma camada de entrelaçamento é geralmente adicionada entre os dois códigos para espalhar rajadas de erros por um intervalo mais amplo.
A combinação de um código convolucional de Viterbi interno com um código de Reed-Solomon externo (conhecida como código RSV) foi usada pela primeira vez na Voyager 2,R. Ludwig, J. Taylor, Voyager Telecommunications Manual, JPL DESCANSO (Design and Performance Summary Series), March 2002. e tornou-se uma construção popular dentro e fora do setor espacial. Ainda é notavelmente usada hoje para comunicações via satélite, como no padrão de transmissão de televisão digital DVB-S.Digital Video Broadcasting (DVB); Framing structure, channel coding and modulation for 11/12 GHz satellite services, ETSI EN 300 421, V1.1.2, August 1997.
Em um sentido mais amplo, qualquer combinação (serial) de dois ou mais códigos pode ser referida como um código concatenado. Por exemplo, no padrão DVB-S2, um código LDPC altamente eficiente é combinado com um código externo algébrico a fim de remover quaisquer erros residuais deixados pelo código LDPC interno devido ao seu patamar de erro inerente.Digital Video Broadcasting (DVB); Second generation framing structure, channel coding and modulation systems for Broadcasting, Interactive Services, News Gathering and other broadband satellite applications (DVB-S2), ETSI EN 302 307, V1.2.1, April 2009.
Um esquema de concatenação simples também é usado no compact disc (CD), onde uma camada de entrelaçamento entre dois códigos de Reed-Solomon de tamanhos diferentes espalha erros por vários blocos.
Turbo códigos: Uma abordagem de concatenação paralela A descrição acima é dada para o que hoje é chamado de código concatenado serialmente. Os turbo códigos, conforme descritos pela primeira vez em 1993, implementaram uma concatenação paralela de dois códigos convolucionais, com um entrelaçador entre os dois códigos e um decodificador iterativo que passa informações para frente e para trás entre os códigos. Esse design tem um desempenho melhor do que quaisquer códigos concatenados concebidos anteriormente.
No entanto, um aspecto chave dos turbo códigos é a sua abordagem de decodificação iterada. A decodificação iterada agora também é aplicada a concatenações seriais a fim de alcançar maiores ganhos de codificação, como nos códigos convolucionais concatenados serialmente (SCCCs). Uma forma inicial de decodificação iterada foi implementada com duas a cinco iterações no "código Galileo" da sonda espacial Galileo.
Ver também
Limite de Gilbert-Varshamov Código de Justesen Limite de Singleton Limite de Zyablov
Referências
Leitura adicional
Ligações externas
Notas de Aula de Teoria de Códigos da Universidade de Buffalo – Dr. Atri Rudra