Código Turbo 📖 Wikipedia

Na teoria da informação, os turbo códigos (em inglês: turbo codes) são uma classe de códigos de correção antecipada de erros (FEC) de alto desempenho desenvolvidos por volta de 1990–91, mas publicados pela primeira vez em 1993. Eles foram os primeiros códigos práticos a se aproximarem intimamente da capacidade máxima do canal ou do limite de Shannon, um máximo teórico para a taxa de código na qual a comunicação confiável ainda é possível, dado um nível de ruído específico. Os turbo códigos são usados em comunicações móveis 3G/4G (por exemplo, em UMTS e LTE) e em comunicações por satélite (espaço profundo), bem como em outras aplicações onde os projetistas buscam alcançar uma transferência de informações confiável em links de comunicação com restrição de largura de banda ou latência na presença de ruído que corrompe os dados. Os turbo códigos concorrem com os códigos de verificação de paridade de baixa densidade (LDPC), que fornecem um desempenho semelhante. Até que a patente dos turbo códigos expirasse,^[1] o status livre de patentes dos códigos LDPC foi um fator importante para a relevância contínua do LDPC.^[2]

O nome "turbo código" surgiu do loop de retroalimentação (feedback) usado durante a decodificação normal do turbo código, que foi comparado à retroalimentação de exaustão usada para o turbocompressor de motores. Joachim Hagenauer argumentou que o termo turbo código é um nome impróprio, uma vez que não há retroalimentação envolvida no processo de codificação.^[3]

O pedido de patente fundamental para os turbo códigos foi depositado em 23 de abril de 1991. O pedido de patente lista Claude Berrou como o único inventor dos turbo códigos. O depósito da patente resultou em várias patentes, incluindo a Patente dos EUA 5.446.747, que expirou em 29 de agosto de 2013.

O primeiro artigo público sobre turbo códigos foi "Near Shannon Limit Error-correcting Coding and Decoding: Turbo-codes".^[4] Este artigo foi publicado em 1993 nos Anais da IEEE International Communications Conference. O artigo de 1993 foi formado a partir de três submissões separadas que foram combinadas devido a restrições de espaço. A fusão fez com que o artigo listasse três autores: Berrou, Glavieux e Thitimajshima (da Télécom Bretagne, antiga ENST Bretagne, França). No entanto, fica claro a partir do depósito original da patente que Berrou é o único inventor dos turbo códigos e que os outros autores do artigo contribuíram com material diferente dos conceitos centrais.

Os turbo códigos foram tão revolucionários na época de sua introdução que muitos especialistas no campo da codificação não acreditaram nos resultados relatados. Quando o desempenho foi confirmado, ocorreu uma pequena revolução no mundo da codificação que levou à investigação de muitos outros tipos de processamento iterativo de sinais.^[5]

A primeira classe de turbo código foi o código convolucional concatenado paralelo (PCCC). Desde a introdução dos turbo códigos paralelos originais em 1993, muitas outras classes de turbo códigos foram descobertas, incluindo os códigos convolucionais concatenados serialmente e os códigos de repetição-acumulação. Métodos iterativos de decodificação turbo também foram aplicados a sistemas FEC mais convencionais, incluindo códigos convolucionais corrigidos por Reed-Solomon, embora esses sistemas sejam muito complexos para implementações práticas de decodificadores iterativos. A equalização turbo também fluiu do conceito de turbo codificação.

Além dos turbo códigos, Berrou também inventou os códigos convolucionais sistemáticos recursivos (RSC), que são usados na implementação de exemplo dos turbo códigos descritos na patente. Os turbo códigos que usam códigos RSC parecem ter um desempenho melhor do que os turbo códigos que não usam códigos RSC.

Antes dos turbo códigos, as melhores construções eram os códigos concatenados em série baseados em um código de correção de erros Reed-Solomon externo combinado com um código convolucional interno de comprimento de restrição curto decodificado pelo algoritmo de Viterbi, também conhecidos como códigos RSV.

Num artigo posterior, Berrou deu o crédito à intuição de "G. Battail, J. Hagenauer e P. Hoeher, que, no final dos anos 80, destacaram o interesse do processamento probabilístico". Ele acrescenta que "R. Gallager e M. Tanner já haviam imaginado técnicas de codificação e decodificação cujos princípios gerais estão intimamente relacionados", embora os cálculos necessários fossem impraticáveis naquela época.^[6]

Existem muitas instâncias diferentes de turbo códigos, usando diferentes codificadores componentes, relações de entrada/saída, entrelaçadores e padrões de perfuração (puncturing). Esta implementação de exemplo de codificador descreve um turbo codificador clássico e demonstra o design geral dos turbo códigos paralelos.

Esta implementação do codificador envia três sub-blocos de bits. O primeiro sub-bloco é o bloco de ${\displaystyle m}$ bits de dados de carga útil (payload). O segundo sub-bloco consiste em ${\displaystyle n/2}$ bits de paridade para os dados da carga útil, calculados usando um código convolucional sistemático recursivo (código RSC). O terceiro sub-bloco consiste em ${\displaystyle n/2}$ bits de paridade para uma permutação conhecida dos dados da carga útil, novamente calculados usando um código RSC. Assim, dois sub-blocos redundantes, mas diferentes, de bits de paridade são enviados junto com a carga útil. O bloco completo tem ${\displaystyle m+n}$ bits de dados com uma taxa de código de ${\displaystyle m/(m+n)}$. A permutação dos dados da carga útil é realizada por um dispositivo chamado entrelaçador (interleaver).

Em termos de hardware, este codificador de turbo código consiste em dois codificadores RSC idênticos, ${\displaystyle C_{1}}$ e ${\displaystyle C_{2}}$, conforme ilustrado na figura, que são conectados um ao outro usando um esquema de concatenação, chamado concatenação paralela:

Na figura, ${\displaystyle M}$ é um registrador de memória. A linha de atraso e o entrelaçador forçam os bits de entrada ${\displaystyle d_{k}}$ a aparecerem em sequências diferentes. Na primeira iteração, a sequência de entrada ${\displaystyle d_{k}}$ aparece em ambas as saídas do codificador, ${\displaystyle x_{k}}$ e ${\displaystyle y_{1k}}$ ou ${\displaystyle y_{2k}}$ devido à natureza sistemática do codificador. Se os codificadores ${\displaystyle C_{1}}$ e ${\displaystyle C_{2}}$ são usados em ${\displaystyle n_{1}}$ e ${\displaystyle n_{2}}$ iterações, suas taxas são respectivamente iguais a:

${\displaystyle {\begin{aligned}~R_{1}&={\frac {n_{1}+n_{2}}{2n_{1}+n_{2}}}\\~R_{2}&={\frac {n_{1}+n_{2}}{n_{1}+2n_{2}}}\end{aligned}}}$

O decodificador é construído de maneira semelhante ao codificador acima. Dois decodificadores elementares são interconectados um ao outro, mas em série, não em paralelo. O decodificador ${\displaystyle {\text{DEC}}_{1}}$ opera em velocidade menor (ou seja, ${\displaystyle R_{1}}$), portanto, destina-se ao codificador ${\displaystyle C_{1}}$, e ${\displaystyle {\text{DEC}}_{2}}$ serve correspondentemente para ${\displaystyle C_{2}}$. ${\displaystyle {\text{DEC}}_{1}}$ produz uma decisão suave que causa um atraso ${\displaystyle L_{1}}$. O mesmo atraso é causado pela linha de atraso no codificador. A operação de ${\displaystyle {\text{DEC}}_{2}}$ causa um atraso ${\displaystyle L_{2}}$.

Um entrelaçador instalado entre os dois decodificadores é usado aqui para dispersar as rajadas de erro vindas da saída de ${\displaystyle {\text{DEC}}_{1}}$. O bloco DI é um módulo de demultiplexação e inserção. Ele funciona como um interruptor, redirecionando os bits de entrada para ${\displaystyle {\text{DEC}}_{1}}$ em um momento e para ${\displaystyle {\text{DEC}}_{2}}$ em outro. No estado OFF, ele alimenta ambas as entradas ${\displaystyle y_{1k}}$ e ${\displaystyle y_{2k}}$ com bits de preenchimento (zeros).

Considere um canal AWGN (ruído gaussiano branco aditivo) sem memória, e suponha que na ${\displaystyle k}$-ésima iteração, o decodificador recebe um par de variáveis aleatórias:

${\displaystyle {\begin{aligned}~x_{k}&=(2d_{k}-1)+a_{k}\\~y_{k}&=2(Y_{k}-1)+b_{k}\end{aligned}}}$

onde ${\displaystyle a_{k}}$ e ${\displaystyle b_{k}}$ são componentes de ruído independentes com a mesma variância ${\displaystyle \sigma ^{2}}$. ${\displaystyle Y_{k}}$ é o ${\displaystyle k}$-ésimo bit da saída do codificador ${\displaystyle y_{k}}$.

A informação redundante é demultiplexada e enviada através de DI para ${\displaystyle {\text{DEC}}_{1}}$ (quando ${\displaystyle y_{k}=y_{1k}}$) e para ${\displaystyle {\text{DEC}}_{2}}$ (quando ${\displaystyle y_{k}=y_{2k}}$).

${\displaystyle {\text{DEC}}_{1}}$ produz uma decisão suave; ou seja:

${\displaystyle \Lambda (d_{k})=\log {\frac {p(d_{k}=1)}{p(d_{k}=0)}}}$

e a entrega a ${\displaystyle {\text{DEC}}_{2}}$. ${\displaystyle \Lambda (d_{k})}$ é chamado de logaritmo da razão de verossimilhança (LLR, do inglês log-likelihood ratio). ${\displaystyle p(d_{k}=i),\,i\in \{0,1\}}$ é a probabilidade a posteriori (APP) do bit de dados ${\displaystyle d_{k}}$ que mostra a probabilidade de interpretar um bit ${\displaystyle d_{k}}$ recebido como ${\displaystyle i}$. Levando o LLR em conta, ${\displaystyle {\text{DEC}}_{2}}$ produz uma decisão rígida (hard decision); ou seja, um bit decodificado.

Sabe-se que o algoritmo de Viterbi é incapaz de calcular a APP, portanto, não pode ser usado em ${\displaystyle {\text{DEC}}_{1}}$. Em vez disso, um algoritmo BCJR modificado é usado. Para ${\displaystyle {\text{DEC}}_{2}}$, o algoritmo de Viterbi é o apropriado.

No entanto, a estrutura retratada não é ótima, porque ${\displaystyle {\text{DEC}}_{1}}$ usa apenas uma fração adequada da informação redundante disponível. Para melhorar a estrutura, um loop de retroalimentação é usado (veja a linha pontilhada na figura).

O front-end do decodificador produz um número inteiro para cada bit no fluxo de dados. Este inteiro é uma medida do quão provável é que o bit seja um 0 ou 1 e também é chamado de soft bit. O inteiro pode ser extraído do intervalo [-127, 127], onde:

• -127 significa "certamente 0"
• -100 significa "muito provavelmente 0"
• 0 significa "pode ser tanto 0 quanto 1"
• 100 significa "muito provavelmente 1"
• 127 significa "certamente 1"

Isto introduz um aspecto probabilístico ao fluxo de dados do front-end, mas transmite mais informações sobre cada bit do que apenas 0 ou 1.

Por exemplo, para cada bit, o front-end de um receptor sem fio tradicional tem que decidir se uma tensão analógica interna está acima ou abaixo de um determinado nível de limite de tensão. Para um decodificador de turbo código, o front-end forneceria uma medida inteira de quão longe a tensão interna está do limite fornecido.

Para decodificar o bloco de dados de ${\displaystyle m+n}$ bits, o front-end do decodificador cria um bloco de medidas de verossimilhança, com uma medida de verossimilhança para cada bit no fluxo de dados. Existem dois decodificadores paralelos, um para cada um dos sub-blocos de paridade de ${\displaystyle n/2}$ bits. Ambos os decodificadores usam o sub-bloco de ${\displaystyle m}$ verossimilhanças para os dados da carga útil. O decodificador que trabalha no segundo sub-bloco de paridade conhece a permutação que o codificador usou para este sub-bloco.

A principal inovação dos turbo códigos é como eles usam os dados de verossimilhança para reconciliar as diferenças entre os dois decodificadores. Cada um dos dois decodificadores convolucionais gera uma hipótese (com verossimilhanças derivadas) para o padrão de ${\displaystyle m}$ bits no sub-bloco da carga útil. Os padrões de bits das hipóteses são comparados e, se forem diferentes, os decodificadores trocam as verossimilhanças derivadas que têm para cada bit nas hipóteses. Cada decodificador incorpora as estimativas de verossimilhança derivadas do outro decodificador para gerar uma nova hipótese para os bits na carga útil. Em seguida, eles comparam essas novas hipóteses. Esse processo iterativo continua até que os dois decodificadores cheguem à mesma hipótese para o padrão de ${\displaystyle m}$ bits da carga útil, o que normalmente ocorre de 15 a 18 ciclos.

Uma analogia pode ser traçada entre esse processo e a resolução de quebra-cabeças de referência cruzada, como palavras cruzadas ou sudoku. Considere um jogo de palavras cruzadas parcialmente preenchido e possivelmente confuso. Dois solucionadores de quebra-cabeças (decodificadores) estão tentando resolvê-lo: um possuindo apenas as pistas "verticais" (bits de paridade) e o outro possuindo apenas as pistas "horizontais". Para começar, ambos os solucionadores adivinham as respostas (hipóteses) para suas próprias pistas, anotando o quão confiantes estão em cada letra (bit de carga útil). Em seguida, eles comparam suas anotações, trocando respostas e classificações de confiança entre si, percebendo onde e como eles diferem. Com base nesse novo conhecimento, ambos apresentam respostas atualizadas e classificações de confiança, repetindo todo o processo até convergirem para a mesma solução.

Os turbo códigos apresentam um bom desempenho devido à combinação atraente da aparência aleatória do código no canal, aliada à estrutura de decodificação fisicamente realizável. Os turbo códigos são afetados por um patamar de erro (error floor).

Telecomunicações:

• Os turbo códigos são amplamente usados nos padrões de telefonia móvel 3G e 4G; por exemplo, em HSPA, EV-DO e LTE.
• MediaFLO, sistema de televisão móvel terrestre da Qualcomm.
• O canal de interação de sistemas de comunicação via satélite, como o DVB-RCS^[7] e o DVB-RCS2.
• Missões recentes da NASA, como a Mars Reconnaissance Orbiter, usam turbo códigos como alternativa à combinação de correção de erros Reed-Solomon com códigos do decodificador de Viterbi.
• O IEEE 802.16 (WiMAX), um padrão de rede metropolitana sem fio, usa codificação turbo de bloco e codificação turbo convolucional.

Do ponto de vista da inteligência artificial, os turbo códigos podem ser considerados como uma instância de propagação de crença com loops em redes Bayesianas.^[8]

• Algoritmo BCJR
• Código convolucional
• Correção antecipada de erros
• Entrelaçador
• Código de verificação de paridade de baixa densidade (LDPC)
• Código convolucional concatenado serialmente
• Decodificação de decisão suave
• Equalizador turbo
• Algoritmo de Viterbi

• Battail, Gérard (1998). «A conceptual framework for understanding turbo codes». IEEE Journal on Selected Areas in Communications. 916 (2): 245–254. doi:10.1109/49.661112 
• Brejza, M.F.; Li, L.; Maunder, R.G.; Al-Hashimi, B.M.; Berrou, C.; Hanzo, L. (2016). «20 years of turbo coding and energy-aware design guidelines for energy-constrained wireless applications» (PDF). IEEE Communications Surveys & Tutorials. 918 (1): 8–28. doi:10.1109/COMST.2015.2448692 
• Garzón-Bohórquez, Ronald; Nour, Charbel Abdel; Douillard, Catherine (2016). Improving Turbo codes for 5G with parity puncture-constrained interleavers (PDF). 9th International Symposium on Turbo Codes and Iterative Information Processing (ISTC). pp. 151–5. doi:10.1109/ISTC.2016.7593095 

• Guizzo, Erico (março de 2004). «Closing In On The Perfect Code». IEEE Spectrum. 41 (3): 36–42. doi:10.1109/MSPEC.2004.1270546. Cópia arquivada em 11 de outubro de 2009  Verifique o valor de |url-access=subscription (ajuda)
• "The UMTS Turbo Code and an Efficient Decoder Implementation Suitable for Software-Defined Radios" Arquivado em 2016-10-20 no Wayback Machine (International Journal of Wireless Information Networks)
• Mackenzie, Dana (2005). «Take it to the limit». New Scientist. 187 (2507): 38–41 
• "Pushing the Limit", um artigo da Science News sobre o desenvolvimento e a gênese dos turbo códigos
• International Symposium On Turbo Codes
• Coded Modulation Library, uma biblioteca de código aberto para simulação de turbo códigos no MATLAB
• "Turbo Equalization: Principles and New Results" Arquivado em 2009-02-27 no Wayback Machine, um artigo da IEEE Transactions on Communications sobre o uso de códigos convolucionais em conjunto com a equalização de canal.
• IT++ Home Page A biblioteca IT++ é uma poderosa biblioteca C++ que, em particular, suporta turbo códigos.
• Publicações sobre turbo códigos por David MacKay
• AFF3CT Home Page (Uma Caixa de Ferramentas de Correção Antecipada de Erros Rápida) para simulações de turbo códigos de alta velocidade em software
• Kerouédan, Sylvie; Berrou, Claude (2010). «Turbo code». scholarpedia.org. Scholarpedia. 5 (4): 6496. Bibcode:2010SchpJ...5.6496K. doi:10.4249/scholarpedia.6496 
• 3GPP LTE Turbo Reference Design.
• Estimate Turbo Code BER Performance in AWGN Arquivado em 2019-02-01 no Wayback Machine (MATLAB).
• Parallel Concatenated Convolutional Coding: Turbo Codes (MatLab Simulink)

Predefinição:CCSDS

Predefinição:ORDENAR:Turbo Codigos