1º seminário - Codificação Turbo - Primeira parte da apresentação

Instituto Nacional de Telecomunicações

Códigos Turbo

Seminário 1

Introdução aos códigos Turbo e Codificação Turbo

Guilherme V. Barbosa

2012

Instituto Nacional de Telecomunicações

Introdução

Tópicos:

1 Codificação de Canal.

2 Histórico.

3 Surgimento dos Códigos Turbo.

4 A estrutura da Codificação Turbo.

5 Aplicação dos códigos Turbo.

6 Avanço.

Instituto Nacional de Telecomunicações

Introdução

1. Codificação de Canal:

• O objetivo consiste em transmitir uma mensagem qualquer por umcanal ruidoso de maneira que o receptor possa decodificar essamensagem corretamente.

• Para viabilizar esse processo, um código C com taxa Rc deve serdimensionado corretamente.

Transmissor(codificador)

Receptor(Descodificador)

Canal( ruído)

Figura IIII: Representação em blocos de um sistema de transmissão.

Instituto Nacional de Telecomunicações

Introdução

1. Codificação de Canal:

• Parâmetros de referência:

• Tamanho do código – n;

• Taxa de codificação Rc; (Rc = k/n)

• Probabilidade de erro de bit – Pe;

• Complexidade na codificação e decodificação.

Instituto Nacional de Telecomunicações

Introdução

1. Codificação de Canal:

• Principal referência:

• Claude Shannon estabeleceu os limites teóricos (Limite de Shannon

1948) para uma comunicação confiável através de um canal

ruidoso.

• Ele dizia que: adicionando redundância controlada à informação,poder-se-ia reduzir a quantidade de erros na recepção a umpatamar tão pequeno quanto se desejasse, desde que a taxa de

transmissão R fosse inferior a capacidade do canal C e (n ∞).

Instituto Nacional de Telecomunicações

Introdução

1. Codificação de Canal:

• Principal referência:

• Em um canal AWGN (Aditive White Gaussian Noise):

- C é a capacidade do canal em (bps);- P é a potência em Watts do sinal enviado;- N é a potência em Watts do ruído;- B é a largura de faixa disponível em Hertz.

R≤

Instituto Nacional de Telecomunicações

Introdução

2. Histórico:

• Hamming, com um estudo paralelo, usou (FEC)

Correção de erro antecipada e também disseque redundâncias poderiam ser adicionadas à

informação, surgindo assim um dos primeiros sistemas práticos de

código de bloco, conhecido como código de Hamming;

• Por várias décadas pesquisadores tentaram uma aproximação ao limite

de Shannon usando novos códigos e técnicas.

Instituto Nacional de Telecomunicações

Introdução

2. Histórico:

• Uma Importante descoberta foi a concatenação

de códigos (Forney 1966):

- Consiste na combinação de dois ou mais códigos;(não sistemáticos nem recursivos)

- Códigos esses, com a capacidade de correção de erro maior que deum extenso código isolado;

- Permitindo uma nova alternativa para se atingir altos ganhos de

codificação, além de conservar o processo de decodificação em umnível de complexidade moderadamente contornável (“melhor”).

Instituto Nacional de Telecomunicações

Introdução

2. Histórico:

• O mais difundido esquema de concatenação de códigos utilizava:

- Um código Reed-Solomon “código externo”;

- Um código convolucional “código interno”.

• Tal configuração permitiu, por muitos anos, desempenhos distantes 4 dB do

limite teórico em aplicações reais (sistemas utilizados por sondas espaciais) [6].

• Embora a combinação utilizada resulte em uma palavra código com grande

distância mínima, o que garante elevado ganho assintótico, o processo dedecodificação interna é isolada e não é explorada a redundância do código

externo. Como consequência, a convergência fica distante do limite teórico [3].

Instituto Nacional de Telecomunicações

Introdução aos códigos Turbo

3. Surgimento dos Códigos Turbo:

• Inventores: (Apresentados em 1993)

• Até que surgiram os códigos Turbo, no início da década de 90 na França,apresentados na IEEE (International Conference on Communications),que deixaram valores de Eb/N0 muito próximos desse limite.

Claude Berrou(1951 - *)

Alain Glavieux(1949 - 2004 )

Punya Thitimajshima(1955 - 2006 )

Instituto Nacional de Telecomunicações

Introdução aos códigos Turbo

3. Surgimento dos Códigos Turbo:

• Os códigos turbo podem ser vistos como um aprimoramento da técnica

de concatenação;

• Utilizando codificadores Convolucionais Recursivos e Sistemáticos

(RSC); (comprimento de restrição curto parece códigos de bloco comum comprimento de bloco de grandes dimensões);

• E emprega iterativamente resultados parciais e complementares dosestágios de decodificação SISO no refinamento da confiabilidade dadecisão das etapas seguintes. (diferente da forma de decodificaçãototalmente isolada dos códigos componentes).

Instituto Nacional de Telecomunicações

Introdução aos códigos Turbo

3. Surgimento dos Códigos Turbo:

Figura IIIIIIII: Adaptado de Berrou [Ber03]. Três possíveis comportamentos para um esquema FEC em um canal AWGN commodulação BPSK ou QPSK, taxa de código 1/2 e blocos de 188 bytes. (1) Limite teórico. (2) Código turbo. (3) Concatenaçãoclássica entre um código Reed-Solomon e um código convolucional. FONTE: GASPAR I. S. [9]

Instituto Nacional de Telecomunicações

Codificação Turbo

4. Estrutura da codificação Turbo:

a) Possui concatenação paralela ou serial de dois ou mais

codificadores componentes, que podem ou não serem iguais;

b) Um entrelaçador de K bits de comprimento;

c) Um sistema de puncionamento (opcional);

d) Alimentações com arranjos diferentemente entrelaçados damesma sequência de informação;

e) E um processo iterativo de decodificação baseada em um algoritmo

de entrada e saída suaves SISO (Soft-Input Soft-Output).

Instituto Nacional de Telecomunicações

Codificação Turbo

4. A estrutura da codificação Turbo:

a1) Concatenação Serial:

Taxa = k/p Taxa = p/n Rc = k/n

Algébrico (RS)ou

Convolucional

Algébrico (RS)ou

ConvolucionalConvolucionalConvolucionalinterleaverinterleaver

Encoder 2 (outer)

Encoder 1 (inner)π

Dados (k bits)Dados + paridades 1 e 2

(n bits)

p bitsk bits p-k

p bits n bits

p bits n-pk

4. A estrutura da codificação Turbo:

a2) Concatenação Paralela:

• Para a codificação Turbo Sistemática em paralelo são usados dois

codificadores separados (normalmente idênticos).

• É usado um entrelaçador para assegurar códigos diferentes entre as saídas dos codificadores.

• Os bits de paridade são puncionados para aumentar a taxa do código (não é necessário).

Instituto Nacional de Telecomunicações

Codificação Turbo

Instituto Nacional de Telecomunicações

Codificação Turbo

a2) Concatenação Paralela:

Figura IVIVIVIV: Representação de um sistema de concatenação paralela. FONTE: MOHAMMAD, S. A. [10]

Figura VVVV: Esquema de Código turbo Convolucional Sistemático e Recursivo (RSC). FONTE: GLAVIEUX, A. [4]

Instituto Nacional de Telecomunicações

Codificação Turbo

4. A estrutura da codificação Turbo:

a2) Exemplo de Código turbo Convolucional Sistemático

e Recursivo (RSC):

• Polinómios geradores 15

(para a recursividade);• E 13 (para a construção da

redundância).

Instituto Nacional de Telecomunicações

Codificação Turbo

4. A estrutura da codificação Turbo:

b) Entrelaçamento (interleaving π):

• Exemplos de Interleaver:

• Entrelaçador de Bloco;

• Entrelaçador convolucional;

• Entrelaçador Pseudoaleatório...

Instituto Nacional de Telecomunicações

Codificação Turbo

b) Entrelaçamento (interleaving π):

Sequência Permutada (y)Sequência Permutada (y)

Sequência original (x)Sequência original (x)

Padrão de permutaçãoP = [ 2 0 4 1 3 ]

Padrão de permutaçãoP = [ 2 0 4 1 3 ]

m0 m1 m2 m3 m4min:min:

m1 m3 m0 m4 m2mout:mout:

P0P0 P1P1 P2P2 P3P3 P4P4

• O principal objetivo doentrelaçador π é aumentar adistância mínima do códigoturbo, eliminando ascorrelaçõesentre oscodificadores.

(x) (y)π

min:min: mout:mout:

Interleaver

Instituto Nacional de Telecomunicações

Codificação Turbo

b) Entrelaçamento (interleaving π):

• Exemplo numérico e computacional (Mathcad)

“ “

• Outro objetivo do entrelaçador π éespalhar erros em rajada emdiferentes palavras códigospermitindo assim acorreção damaioria deles.

Figura VVVV: Ilustração da estratégia de codificação turbo com puncionamento.

Instituto Nacional de Telecomunicações

Codificação Turbo

4. A estrutura da codificação Turbo:

c) Puncionamento:

• O puncionamento é usado para obteruma maior taxa de codificação.

• Ele é aplicado às saídas de paridade,das quais, alternadamente, bits são

transmitidos (t = par e t = ímpar).A taxa de 1/3 vai para 1/2.

Taxa = k/n

Instituto Nacional de Telecomunicações

Códigos Turbo

5. Aplicação dos códigos Turbo:• Telemóveis 3G• UMTS, WCDMA (3GPP/evolução de GSM)• CDMA2000 (3GPP2/evolução de IS-95)• Televisão digital• Norma DVB-RCS (“Return Channel via Satellite”)• Redes locais e metropolitanas sem fios• Norma IEEE 802.16a (“Fixed Broadband Wireless Access Systems”)• Comunicações espaciais• NASA: Messenger (‘04), Mars Reconnaissance Orbiter & Rover (’05),

STEREO (’05), Pluto (’06), Kepler (’07), etc.• ESA: SMART-1 (‘03), Rosetta• Sistemas militares• Gravação magnética

Instituto Nacional de Telecomunicações

Códigos Turbo

6. Avanço:

• A invenção dos códigos turbo levou ao ressurgimento

de um outro código que também se aproxima da

capacidade dos códigos turbos:

LDPC(Low-Density Parity-Check Code)

Gallager

IEEE- LDPC 1962-63

Instituto Nacional de Telecomunicações

Códigos Turbo

7. Referências bibliográficas:

[1] BERROU, C., GLAVIEUX, A., THITIMAJSHIMA, P.; “Near Shannon Limit

Error-Correcting Coding and Decoding : Turbo Codes”, IEEE, 1993.

[2] FORNEY, G. D., Jr., Concatenated codes, MIT Press, 1966.

[3] BERROU C., Codes and turbo codes, pp. 213 a 266, 2010.

[4] GLAVIEUX A., Channel Coding in Communication Networks, From

Theory to Turbocodes, 2007.

[5] ANDERSEN J. D.; A Turbo Tutorial, Department of TelecommunicationTechnical University of Denmark, http:\\www.tele.dtu.dk\~jda\

Instituto Nacional de Telecomunicações

Códigos Turbo

[6] SKLAR B.,” Fundamentals of Turbo Codes”,

[7] SKLAR B., Digital Communications, Fundamentals and Applications,

Second Edition (Prentice-Hall, 2001, ISBN 0-13-084788-7).

[8] HANZO, L., LIEW, T. H., YEAP, B. L.;“Turbo Coding, Turbo Equalisation and

Space-Time Coding, for Transmission over Fading Channels”, 2003.

[9] GASPAR, I. S.; Implementação de uma Classe de Códigos Produto com

Decodificação Turbo em FPGA,2006.

[10] MOHAMMAD, S. A.; Turbo Codes.

[11] DAYAN A. Guimarães, GERALDO G. R. G., BARTOLOMEU F. U.; A Coded

Cooperation Scheme With Single Parity-Check Turbo-Product Codes.

Instituto Nacional de Telecomunicações

Códigos Turbo

FIM