TCMb

XX SIMPÓSIO BRASILEIRO DE TELECOMUNICAÇÕES-SBT’03, 05-08 DE OUTUBRO DE 2003, RIO DE JANEIRO, RJ

Quantização Codificada por Treliças Utilizando oPrincípio Turbo

José F. L. de Oliveira, Gelson V. Mendonça e Eduardo A. B. da Silva

Resumo— A modulação codificada por treliças (TCM –Trellis-Coded Modulation) aumentou expressivamente o desempenho desistemas de transmissão de dados. A quantização codificada portreliças (TCQ – Trellis-Coded Quantisation), cujo desempenhoem termos de taxa distorção é excelente para diversas fontes, foiproposta com base na TCM. Recentemente, a turbo modulaçãocodificada por treliças (TTCM – Turbo TCM) aumentou signi-ficativamente o desempenho da TCM. Este artigo investiga umesquema de turbo quantização baseado na TTCM. A principalmotivação para tal investigação é o excelente desempenho daTCQ. A turbo quantização é desenvolvida, seu desempenho éanalisado e são apresentadas as conclusões.

Palavras-Chave— Modulação Codificada, Quantização Codifi-cada, Códigos Turbo, Turbo Quantização.

Abstract— Trellis-coded modulation (TCM) has expressivelyimproved the performance of data transmission systems. Trellis-coded quantisation (TCQ), whose performance in terms of ratedistortion is excellent for several sources, was proposed basedon TCM. Recently, turbo trellis-coded modulation (TTCM) hassignificantly improved the performance of TCM. This paperinvestigates a turbo quantisation scheme based on TTCM. Themain motivation for such investigation is the excellent performan-ce of TCQ. Turbo quantisation is developed, its performance isanalysed and the conclusions are presented.

Keywords— Coded Modulation, Coded Quantisation, TurboCodes, Turbo Quantisation.

I. I NTRODUÇÃO

Em 1993, Berrou et al. [1] apresentaram os códigos tur-bo, um nova e prática técnica de codificação de canal quepermitiu, pela primeira vez, obter uma taxa de transmissãonum canal ruidoso próxima do limite de Shannon. Logo,esta impressionante característica inspirou o desenvolvimentode outros esquemas que tinham por objetivo aumentar aeficiência espectral dos códigos turbo. Nesta classe de códigos,encontra-se a TTCM, proposta por Robertson et al. [2], [3].Eles empregaram dois codificadores de Ungerboeck [4], numaestrutura similar àquela dos códigos turbo resultando numcódigo mais eficiente.

Como a TCM [4] foi utilizada na elaboração de um esque-ma de quantização eficiente como a TCQ [5], seria naturalconstruir um turbo quantizador codificado por treliças, TTCQ(Turbo TCQ), a partir da estrutura do turbo modulador propos-ta por Robertson et al. [2], [3]. Visto que a TTCM produziuresultados notadamente superiores aos da TCM, conjeturou-seque a TTCQ poderia produzir resultados melhores que os daTCQ.

José F. L. de Oliveira, Gelson V. Mendonça e Eduardo A. B. da Silva,COPPE, Universidade Federal do Rio de Janeiro, Caixa Postal 68504, CEP:21945-970, Rio de Janeiro, RJ - Brasil. E-mail: [email protected].

Neste artigo, será investigado se, de fato, a TTCQ, propostacom base na TTCM, terá um desempenho superior ao daTCQ. Para tanto, na seção 2, são apresentados os conceitosbásicos relativos à TTCM e as estruturas do codificador e dodecodificador são descritas. Na seção 3, descreve-se o esquemada TTCQ. Na seção 4, são mostrados os resultados obtidospela TTCQ que são, na sua maioria, de natureza experimental.Finalmente, na seção 5, apresentam-se as conclusões.

II. T URBO TCM

Uma importante característica dos códigos turbo é a uti-lização simples de códigos convolucionais sistemáticos e re-cursivos num esquema de concatenação paralela, sendo que autilização de um permutador pseudo-aleatório assegura umabaixa probabilidade de erro [3]. Porém, o mais importante é ofato de que os códigos turbo podem ser decodificados iterativae eficientemente. Por outro lado, os códigos de Ungerboeckcombinam codificação e modulação maximizando a distânciaEuclidiana mínima entre as palavras código acarretando umaalta eficiência espectral. A TTCM procura reunir num únicoesquema de codificação as características dos códigos deUngerboeck e dos códigos turbo. Basicamente, Robertson etal. [3] substituem os dois codificadores convolucionais doscódigos turbo por dois codificadores de Ungerboeck idênticos.

A. O Codificador

Na figura 1a, tem-se o diagrama de blocos do codificador daTTCM. Ele é composto por dois codificadores convolucionaissistemáticos recursivos seguidos por mapeadores que seleci-onam o sinal modulado a ser transmitido pelo canal. Cadacodificador convolucional produz umbit de paridade para cadagrupo de� bits de entrada, gerando localmente um código detaxa �� de forma análoga à TCM. No caso particular,que será de interesse para a TTCQ, em que se empregaum modulador ASK (Amplitude Shift Keying), somente umdos � bits de cada símbolo do vetor�� será codificado. Ou seja, sendo�! " � �!# �� $��%� � � � umdos símbolos composto por� bits do vetor de entrada� ,somente obit � � será codificado, da mesma forma como éfeito na TCM. Isto é ilustrado na figura 1b, onde o polinômio& � �(') corresponde à parte recursiva do código convolucional epolinômio & � �*'+ , à parte não recursiva. Há, porém, algumasdiferenças em relação aos codificadores dos códigos turbo,dentre as quais pode-se destacar:

1) o emprego da permutação por grupo debits, onde cadagrupo contém� bits. Os bits dentro de cada grupo não


, - . / 0 / 1 2 . - 3, - 4 5 - 6 7 1 / - 4 2 6 8

, - . / 0 / 1 2 . - 3, - 4 5 - 6 7 1 / - 4 2 6 9 : 2 ; < 2 . - 3= > ?

: 2 ; < 2 . - 3=

@ A BC D E F

@ A BC D E F

G H IJ KG LG K

M N = MO G LOJ LO@ C D E F

@ C D E F

P < 6 < Q - 3

P R S T - 6 - U . < , 2 4 2 6

: 2 Q 3 / V . < W < 3 S 7 Q 2 X Y -M

Z [ ? \[]^^^] [_Z [_ ` ?

D D D

a bc a bd a bb a bea e ba edca e = B

Z [ f ?[]f[]

^^^^^^

^ ^ ^^ ^ ^

^ ^ ^ g T h

g 2 h

Fig. 1. (a) O codificador da TTCM. (b) Detalhe do codificador convolucional.

são permutados, sendo cada um destes grupos chamadode símbolo de canal;

2) a maior complexidade da operação de perfuração dainformação de paridade para obter a eficiência espectraldesejada;

3) a necessidade de restrições específicas na estrutura dospermutadores.

Com o auxílio da figura 2, onde é apresentado um exemplode codificação empregando TTCM, será possível compreendermelhor estas diferenças. Na figura 2a, tem-se um codificadorcom eficiência espectral de 2bits/s/Hz, ou seja, cada símbolode canal representa 2bits da mensagem� . A figura 2b ilustracomo o conjunto de símbolos de canal é particionado nossubconjuntosi � kjml�n �porqs�t�u�voxw , i � yjzl|{ �vo�qs�~}��po�w ,i�� jml }��porqs� { �voxw e i�� jzl �u�porqs� n �poxw . A figura 2btambém ilustra como osbits produzidos pelos codificadoresconvolucionais selecionam o subconjunto e os elementos emcada subconjunto. Na verdade, este é o mesmo mapeamentoadotado na TCM-ASK [4]. Assim sendo, a seqüência deentrada� � 00, 01, 11, 10, 00, 11 é injetada no codificadorconvolucional superior, produzindo a saída�� 00:0, 01:1,11:0, 10:1, 00:1, 11:1 . A mesma seqüência� é permutada,obtendo-se �� 11, 11, 00, 01, 00, 10 . Observeque o permutador do exemplo foi construído de tal forma quesomente são permutadas posições pares com pares e ímparescom ímpares. Isto será justificado a seguir. A seqüência�� éinjetada no codificador convolucional inferior, produzindo a

=

� � � � � � � �

� � � � � � � �

\ � � ? f �f ? \ � � �

� � � � � � � � ¡ � ¢ £ ¢ ¡ � � �¡ � ¤ ¥ ¦ ¡ ¢ � � ¥ §¨ b b © b b © e e © e b © e e © b e ª«¬ ¦¦ ® « ¯ ¯ ¯ ¯ ¯ ¯° ± ² ³ ´ µ ¨ b b ¶ b © b b ¶ e © e e ¶ b © e b ¶ e © e e ¶ b © b e ¶ b ª·¤® « ¨ e e ¶ b © e b ¶ e © b b ¶ b © b e ¶ b © e e ¶ b © b b ¶ e ª«·¤ ¸ � ¹ � � � ¡ � ¢ £ ¢ ¡ � � �¡ � ¤ ¥ ¦ ¡ ¢ � � ¥ §

º ·® « ¨ » ¼ © ½ ¼ © b ¼ © d ¼ © b ¼ © ¾ ¼ ª

¨ b ¼ © d ¼ © » ¼ © ¾ ¼ © b ¼ © ½ ¼ ª«º ·º « ¨ e © d ¼ © ½ © ¾ ¼ © b © ½ ¼ ª

¤ ¿ « ¨ e e ¶ e © e b ¶ b © b b ¶ e © b e ¶ b © e e ¶ b © b b ¶ b ª¨ e e © e b © b b © b e © e e © b b ª¦ «« ¯ ´ ¯ ³ ¯ ¯ ¯ ¯ ±²µ° « ¨ e © À © ½ © ¾ © b © » ªº ¿

= > ? ¸ ¹ Á Â ¥ Ã � Ä ¡ � � � ¥

: 2 ; < 2 . - 3

¬ Ä � Á ¦ � � Å Æ Ç > È É Ê

Ç > È É Ê

D D

Ë H I[

Ë H I[

] f[] ?[] \[

Z f[Z ?[

] f[] ?[] \[ Ì Ì Ì Ì Ì B Ì B Ì Ì B B B Ì Ì B Ì B B B Ì B B BÍ f Í ? Í \ Í � Í f Í ? Í \ Í �

Î Ï Ð Ñ Ï Ò Ó Ô Õ Ï Ð Ö Ò ×Î Ï Ø Õ Ù Õ Ô Ö Ø Ï Ú

Î Ï Ø Õ Ù Õ Ô Ö Ø Ï ÚÎ Ï Ð Ñ Ï Ò Ó Ô Õ Ï Ð Ö Ò Û

Ü Ý Þ P ß

P < 6 < 1 / - 4 2 U R S T - 6 - . < 4 Q 3 - . < 7 S U 7 T 1 - 4 à 7 4 Q - ^

N Ì B á â ã ä å æN

g T h

g 2 h

P < 6 < 1 / - 4 2 U 7 T 1 - 4 à 7 4 Q - ^Ý B ç ÜÝ â ç ÜÝ ä ç ÜÝ æ ç Ü A B ç Ü A â ç Ü A ä ç Ü A æ ç Ü

Fig. 2. (a) Exemplo de codificação com TTCM. (b) Detalhe do conjuntocodificador-mapeador/modulador.

saída ��èé � 11:1, 11:0, 00:1, 01:0, 00:1, 10:1 . Os símbolosdesta seqüência são permutados, por meio da permutaçãoinversa, obtendo-se��èê ë� �� èì � 00:1, 01:0, 11:1,10:1, 00:1, 11:0 . Visto que o permutador mapeia posiçõespares em pares e ímpares em ímpares e que os codificadoresconvolucionais atuam em grupos de� îí bits por vez, aseqüência debits sistemáticos de�� e � è são iguais. Destaforma, a perfuração dosbits de paridade é feita selecionando-se alternadamente as componentes dos vetores de símbolosde canalï�� e ï è . O sobrescritoðòñ do vetor ïôózõ tem porfinalidade indicar que cada um de seus símbolos transmitesimultaneamentebits sistemáticos e de paridade.

B. O Decodificador

O decodificador da TTCM é muito semelhante àqueleutilizado na decodificação dos códigos turbo, como se podever na figura 3. Entretanto, há uma diferença em relação aotipo de informação que os decodificadores trocam entre si e nomodo como a primeira iteração deve ser iniciada. Outra carac-terística, que é particular a este processo de decodificação, é ofato de cada um dos decodificadores receber alternadamente osímbolo corrompido por ruído do codificador correspondentee o símbolo corrompido pelo ruído do outro codificador. Osímbolo correspondente ao outro codificador é ignorado e odecodificador corrente utiliza somente a informaçãoa priori


ö

ö

ö ÷ øö ÷ ø

ù ú û ü ý þ ÿ þ û � ý ü ��

ù ú û ü ý þ ÿ þ û � ý ü �� ÷ ø

� � � � �ø �

� � �� ø

� ø

� ��

� � ø

�

Fig. 3. O decodificador da TTCM.

fornecida pelo outro decodificador que não ignorou este sím-bolo. E é por isto que a iniciação do processo de decodificaçãoda turbo modulação é um pouco diferente daquele dos códigosturbo. Na primeira parte da primeira iteração, a informaçãoa priori do símbolo ignorado deve ser estimada, conformedescrito em [3].

A saída de cada decodificador componente dos códigosturbo pode ser dividida em três partes:

1) a informaçãoa priori,2) a informação sistemática e3) a informação extrínseca

que são afetadas por ruído independente [6]. Na turbo mo-dulação, ver figura 3, a componente sistemática não pode serseparada da componente extrínseca, pois o mesmo símbolo decanal transporta a informação sistemática e de paridade emcontraste com os códigos turbo. Na figura 3, estas compo-nentes de informação mista correspondem às matrizes

�� e�� , onde o sobrescritoes significa informação extrínseca esistemática não separáveis. Desta forma, no esquema da turbomodulação a saída de cada decodificador pode ser dividida emduas partes:

1) a informaçãoa priori e2) a informação extrínseca e sistemática.

Como a informação extrínseca e sistemática produzida por umdecodificador é utilizada pelo outro como informaçãoa priori,correspondendo às matrizes

�� e�� na figura 3, cada um

dos decodificadores que compõe o esquema de decodificaçãoda TTCM utiliza o algoritmo BCRJ-MAP [7] que produzsaídas contínuas (Soft Output), o que é adequado para umdecodificador iterativo como este.

III. T URBO TCQ

A utilização da turbo modulação como código taxa distorçãoé feita de forma direta como no caso da quantização codificadapor treliças de Marcellin [5]. Na figura 4, é mostrado odiagrama de blocos do quantizador proposto. A fonte produzum sinal � que é visto pelo decodificador da turbo modulaçãocomo se fosse a saída de um canal ruidoso. Este decodificador,que está atuando como codificador do ponto de vista da

� � ! "#

$ � % ! " � % ! " ! "� #

& ' ( ) * + * , ' - . / 0 *1 2 3 * , 4 5 4 3 . , * ( , .6 * 7 & 2 #

8 9 : ;! . "

< * , 4 5 4 3 . , * ( , .& ' ( ) * + * , ' - . / 0 *

�8 9 : ;

! ) "Fig. 4. Turbo TCQ. Em (a), o codificador e em (b), o decodificador.

quantização, procura encontrar a seqüência debits � >= � � que melhor aproxima a seqüência� . A seqüência debits �aplicada ao codificador da turbo modulação, que atua comodecodificador para a quantização, produz uma saídaï� &�� = � � % que é a representação quantizada de� .

IV. RESULTADOS

Nesta seção, serão apresentados os resultados obtidos pelaTTCQ na quantização de fonte Gaussiana? �A@rq�� sem memó-ria com B bits, para B �mq í q }�qDC . Na tabela I, são mostradosos resultados obtidos pela TCQ de Marcellin [5] utilizando osníveis de reconstrução do quantizador de Lloyd-Max [8] detaxa B � � . Na tabela II, são apresentados os resultados da TCQde Marcellin utilizando níveis de reconstrução otimizados, ouseja, os níveis de recosntrução são obtidos por procedimentonumérico para minimizar o valor esperado do erro médioquadrático,' FE �HG �|��IKJ � �AL I lNM I � �KO � , entre os vetoresï e� definidos na seção 3. Estas duas tabelas serão utilizadas paracomparação com os resultados obtidos pela TTCQ. Cada valorexperimental listado nas tabelas referentes à TCQ e à TTCQ éo resultado do cálculo da média oriunda da simulação de 100seqüências de comprimentoO igual a 1000 de realizaçõesindependentes de um gerador de distribuição Gaussiana. Osvalores de SNR (Signal to Noise Ratio) contidos nestas tabelasestão listados em dB (�P@RQTSVU � � �%�u�v' ). Os intervalos de confian-ça de 95% também foram incluídos. As últimas duas linhas dastabelas I, II, IV e V correspondem aos resultados obtidos peloquantizador de Lloyd-Max e ao limite superior teórico quepode ser obtido para uma fonte Gaussiana, respectivamente.

A primeira experiência foi feita utilizando o algoritmoBCJR (TTCQ-BCJR), os códigos de Ungerboeck [9], listadosna coluna “códigos da TCQ” da tabela III, e os níveis dereconstrução do quantizador de Lloyd-Max de taxaB � � . Comesta configuração, o desempenho do quantizador proposto ébastante inferior até mesmo ao de Lloyd-Max em cerca de3 a 4 dB e, independente do número de iterações utilizado.Verificou-se, posteriormente, que o algoritmo BCJR quandoutilizado no quantizador de Marcellin também não produziaresultados satisfatórios. Então, decidiu-se substituir o algorit-mo BCJR pelo SOVA (Soft Output Viterbi Algorithm). Estealgoritmo corresponde a versão SISO (Soft Input Soft Output)do algoritmo de Viterbi utilizado tradicionalmente na TCQ e osresultados produzidos pelo esquema TCQ-SOVA são idênticosaos listados nas tabelas I e II. O SOVA pode ser empregado


TABELA I

TCQ COM PONTOS DE RECONSTRUÇÃO DELLOYD-MAX DE TAXA WYXNZ .FONTE GAUSSIANA SEM MEMÓRIA. SNREM DB.

Número de Taxa (bits)Estados 1 2 3 4

4 4,65 10,19 15,83 21,618 4,79 10,31 15,93 21,7216 4,87 10,35 15,99 21,7932 4,94 10,41 16,07 21,8664 5,00 10,49 16,12 21,91128 5,05 10,54 16,18 21,96256 5,09 10,58 16,21 22,00

Confiança de 95% 0,03 0,03 0,04 0,05

Lloyd-Max 4,40 9,30 14,62 20,22Limite 6,02 12,04 18,06 24,08

TABELA II

TCQ OTIMIZADA . FONTE GAUSSIANA SEM MEMÓRIA. SNREM DB.


4 5,03 10,56 16,18 21,958 5,22 10,69 16,33 22,0616 5,29 10,77 16,39 22,1332 5,35 10,84 16,46 22,1664 5,44 10,92 16,53 22,28128 5,51 10,96 16,58 22,35256 5,54 11,01 16,63 22,40

Confiança de 95% 0,05 0,05 0,07 0,09

Lloyd-Max 4,40 9,30 14,62 20,22Limite 6,02 12,04 18,06 24,08

diretamente num esquema que utiliza o princípio turbo [6]como a TTCQ visto que é um algoritmo do tipo SISO. Osresultados, com esta alteração na configuração inicial, foramum pouco melhores, mas ainda inferiores aos do quantizadorde Lloyd-Max. Notou-se, também, que a utilização de maisde uma iteração foi prejudicial para esta configuração.

Fazendo experiências com TTCM-SOVA, verificou-se queos códigos de Ungerboeck não produziam os melhores resul-tados quando utilizados no codificador de canal empregandoturbo modulação, e conjeturou-se que isto poderia estar cau-sando os péssimos resultados obtidos com a TTCQ. Através deuma procura exaustiva pelos melhores códigos convolucionaisde quatro estados, constatou-se que a transferência1

[ �('+ ]\ � ^�`_ ^ _ ^badc (1)

produzia melhores resultados que a transferência de Ungerbo-eck

[ �*'+ ]\ � ^��_ ^ aec (2)

quando utilizada com o turbo modulador. A diferença dedesempenho entre estas duas transferências é mostrada nafigura 5. Entretanto, esta mudança produziu resultados tãoruins quanto os anteriores para a TTCQ, independentementedo algoritmo utilizado (BCRJ ou SOVA) e do número de

1Seria mais adequado utilizar a expressãomatriz geradora na formapolinomial. Porém, por brevidade, foi utilizado o termotransferência.

4 6 8 10 1210

−5

10−4

10−3

10−2

10−1

100

BE

R

SNR (dB)

Fig. 5. Comparação entre os códigos convolucionais correspondentes àsequações (f ) 1 e (g ) 2 empregados na TTCM-SOVA.

iterações. Desta forma, a conjetura não se mostrou válida comoera esperado.

Efetuando uma análise de convergência, Richardson [10]prova que os códigos turbo sempre possuem pontos fixos,fornecendo condições teóricas suficientes para a unicidade domesmo. Ele comenta que a unicidade do ponto fixo deve, pro-vavelmente, ocorrer com regularidade. Entretanto, Richardsonobserva que a baixa relação sinal ruído é um fator limitante nodesempenho dos códigos turbo, sendo este um problema aindanão resolvido. A medida que o desempenho do decodificadorturbo se degrada nesta região de baixa relação sinal ruído, aestabilidade do ponto fixo diminui. Desta forma, a quebra nodesempenho dos códigos turbo é, provavelmente, uma falhana convergência. Embora o decodificador tenha pontos fixosestáveis, o algoritmo pode iniciar fora da região de conver-gência e não conseguir atingi-la mesmo após várias iterações.Outro fator que também poderia afetar o desempenho do turbodecodificador seria a existência de pontos fixos múltiplos. Nocaso da multiplicidade de pontos fixos, haveria a possibilidadede poder distingui-los e encontrar aquele que produzisse omelhor desempenho. Então, duas hipóteses foram formuladaspara tentar explicar os péssimos resultados da TTCQ:

1) o algoritmo da TTCQ está convergindo com uma iteração,mas para um ponto fixo que produz péssimos resultados;

2) o algoritmo de decodificação não está convergindo.Testes experimentais revelaram que o algoritmo não estava

convergindo. Quando ocorre a convergência, ver figura 3,�ih _��̀ j� k � �lh _ ��j� e�� h _��̀ j k �� h j , para alguma iteraçãom @�q$� q í q �$�� , visto que

�� h _��̀ j �� h j � �nh _ ��j� l� �lh _ ��j� , e isto não é verificado, mesmo após centenas deiterações. Observando-se a figura 5, nota-se que a TTCM-SOVA para o código da equação 1 possui uma região re-


lativamente plana, onde a BER (Bit Error Rate) se alterapouco com o aumento da SNR, e uma região onde a BER sealtera acentuadamente com o aumento da SNR. É nesta últimaregião que o algoritimo iterativo da TTCM-SOVA converge.Infelizmente, esta região está além da SNR teórica máxima queum quantizador para fonte Gaussiana pode atingir. Portanto,por um problema de convergência, que é inerente ao algoritmode decodificação turbo, o melhor código para TTCM, ou seja,para codificação de canal, não produz resultados satisfatórioscomo código taxa distorção.

Entretanto, o problema da quantização está relacionado aoproblema da cobertura doo � com esferas e o problema dacodificação de canal está relacionado ao empacotamento deesferas noo � [11], [12]. As soluções ótimas para estes doisproblemas não são, em geral, iguais para uma dada dimensãoO . Como mencionando na seção 1, a TTCM é mais eficientena codificação de canal que a TCM. Portanto, a TTCM (comos códigos adequados) deve produzir um empacotamento doo � bem melhor que o da TCM. Porém, isto não implica que acobertura produzida pela TTCM para oo � seja melhor que ada TCM para uma dada dimensãoO . De fato, as experiênciasdescritas anteriormente indicam justamente o oposto. Comoconseqüência, a TCQ tem-se mostrado bem mais eficienteque a TTCQ. Coincidentemente, as soluções que a TCMdá aos problemas de cobertura e empacotamento utilizam osmesmos códigos convolucionais, bastando ajustar os níveisde reconstrução (símbolos de canal) para obter o melhor de-sempenho. Contudo, dada a, já mencionada, natureza distintadestes dois problemas, pode-se conjeturar que os códigosconvolucionais que produzem o melhor desempenho para aTTCM não serão, necessariamente, aqueles que produzirão omelhor desempenho para a TTCQ. Desta forma, uma busca poroutros códigos para a TTCQ poderia acarretar uma melhoranos resultados até então obtidos.

TABELA III

CÓDIGOS PARATCQ E TTCQ-SOVAEM OCTAL.

Número de Códigos da TCQ Códigos da TTCQEstados prqtsupwvixzy{q}|~p�vixAx prqtsupwvixzy�q�|Kp�vixAx

4 (005, 002) (005, 004)8 (013, 004) (017, 014)16 (023, 004) (025, 004)32 (045, 010) (077, 014)64 (103, 024) (125, 004)128 (235, 126) (377, 014)256 (515, 362) (405, 124)

Realizando, então, uma busca exaustiva foi constatadoque os melhores códigos convolucionais para TTCQ são osmostrados na tabela III. Os coeficientes foram agrupados eexpressos em octal, de modo que� �P@m}m̀ � ��@V@r��@V@�@�@��m�� corresponde ao polinômio& � �('+ '�� ' � � . Utilizandoos novos códigos e os níveis de reconstrução de Lloyd-Maxforam obtidos os resultados da tabela IV que superam os deLloyd-Max, exceto pelos dois primeiros valores da colunade 1 bit/amostra. Entretanto, a utilização de mais de umaiteração não altera os resultados. De fato, verificou-se queo algoritmo da TTCQ-SOVA se estabiliza após uma iteração

com estes novos códigos. Curiosamente, observa-se que osresultados das linhas de 16, 64 e 256 estados da tabela IVsão idênticos aos obtidos para TCQ na tabela I nas linhasde 4, 8 e 16 estados. Ou seja, parece que a TTCQ-SOVAnecessita do quadrado do número de estados utilizados naTCQ para produzir um desempenho semelhante ao desta. Autilização dos novos códigos com a TTCQ-BCJR foi testadamas produziu péssimos resultados novamente.

TABELA IV

TTCQ-SOVACOM OS PONTOS DE RECONSTRUÇÃO DELLOYD-MAX DE

TAXA WYX�Z E COM OS CÓDIGOSTTCQ DA TABELA III. F ONTE

GAUSSIANA SEM MEMÓRIA. SNRDB.


4 4,06 9,51 15,13 20,938 4,06 9,51 15,13 20,9316 4,67 10,18 15,82 21,6132 4,67 10,18 15,82 21,6164 4,79 10,30 15,93 21,71128 4,79 10,30 15,93 21,71256 4,86 10,36 15,99 21,79

Confiança de 95% 0,03 0,03 0,03 0,05

Lloyd-Max 4,40 9,30 14,62 20,22Limite 6,02 12,04 18,06 24,08

TABELA V

TTCQ-SOVAOTIMIZADA COM CÓDIGOS TTCQ DA TABELA III. F ONTE

GAUSSIANA SEM MEMÓRIA. SNREM DB.


4 4,71 9,99 15,63 21,408 4,71 9,99 15,63 21,4016 5,08 10,55 16,18 21,9432 5,08 10,55 16,18 21,9464 5,19 10,69 16,31 22,07128 5,19 10,69 16,31 22,07256 5,29 10,79 16,41 22,14

Confiança de 95% 0,05 0,05 0,07 0,09

Lloyd-Max 4,40 9,30 14,62 20,22Limite 6,02 12,04 18,06 24,08

Porém, ainda é possível otimizar os níveis de reconstruçãoutilizados na TTCQ-SOVA. Efetuando-se mais este passo foiobtida a tabela V. Comparando com a tabela II, onde seencontram os resultados da TCQ com níveis de reconstruçãotambém otimizados, constata-se, novamente, que a TTCQ-SOVA necessita do quadrado do número de estados da TCQpara produzir um desempenho correspondente ao desta última.Quando se tenta otimizar os níveis de reconstrução da TTCQ-BCJR, utilizando os códigos TTCQ da tabela III, observa-se,claramente, que a TTCQ-BCJR se degenera num quantizadorde Lloyd-Max. Observando as tabelas IV e V, nota-se que osresultados para 4 e 8, 16 e 32, assim como para 64 e 128 esta-dos são extremamente semelhantes. A explicação para este fatoé dada a seguir. Analisando o caso de 4 e 8 estados, verificou-se que o melhor código de 8 estados,� � n q$�tCz , contém omelhor código de 4 estados,� { q`C� , como é ilustrado na figura6. Na figura 6a, tem-se a treliça do código� { qDCz e na figura 6b,


, � . / � - g B æ � B ã h

æåäãâáBÌ

æåäãâáBÌ

g T hg 2 h

, � . / � - g ä � ã h

� � � �

� � � ��

� � � �� ÌBáâ â

áBÌ

B

äåâÌÌ

âåä g 1 h

� � � �

� � � �� ãæáB

áæã� � � �

� � � ��

� � � ��

� � � ��

� � � �

� � � �

� � � �

� � � �

Fig. 6. Os códigospT�uy{�tx em (a) e pAZD Py`Z��tx em (b) produzem os mesmosresultados quando utilizados na TTCQ porque a treliça do códigopAZD Py`Z��txpode ser dividida como mostrado em (c).

a treliça do código�%� n q$�tC� . A figura 6c mostra que a treliçado código �%� n q$�tC� pode ser separada em duas outras disjuntas.A treliça da esquerda na figura 6c é idêntica à da figura 6a.Como o algoritmo da TTCQ é iniciado no estado zero osresultados obtidos por estes dois códigos devem ser necessari-amente iguais. Conjectura-se que os outros dois casos possamser explicados do mesmo modo. Desta forma, na prática, aTTCQ possui códigos efetivos para 4, 16, 64 e 256 estados.Possivelmente, os melhores códigos de 512 estados produzirãoresultados semelhantes aos melhores códigos de 256 estados,seguindo o padrão observado. Outro fato observado é quea TTCQ utilizando o algoritmo BCJR-LogMAP produz osmesmos resultados da TTCQ-SOVA somente quando se faz oparâmetro correspondente a variância do ruído do canal tendera zero. Na verdade, quando isto é feito o algoritmo BCJR-LogMAP se “transforma” no SOVA e, portanto, é natural queos resultados coincidam. Isto indica, experimentalmente, queo melhor algoritmo, entre os utilizados, para a TTCQ seria oSOVA.

V. CONCLUSÕES

Neste artigo, foi investigado um novo esquema de quan-tização, a turbo quantização codificada por treliças, TTCQ,derivado do esquema de codificação de canal de Robertsonet al. [2], [3], a TTCM. Os algoritmos de codificação BCJR(TTCQ-BCJR) e SOVA (TTCQ-SOVA) foram analisados. Aimplementação do turbo quantizador (TTCQ-SOVA) foi feita

com sucesso, mas necessita do quadrado do número de estadospara produzir resultados semelhantes aos da TCQ de Marcellin[5] e com uma complexidade muito maior. Portanto, apesarde a TTCM ser um esquema de modulação codificada de altodesempenho, a TTCQ derivada diretamente da TTCM não éuma alternativa viável para quantizadores de alto desempenho.

REFERÊNCIAS

[1] BERROU, C., GLAVIEUX, A., THITIMAJSHIMA, P., “Near ShannonLimit Error-Correcting Coding and Decoding: Turbo-Codes”. In:ICC1993, pp. 1064–1070, Geneva, Suíça, Maio 1993.

[2] ROBERTSON, P., WÖRZ, T., “Coded Modulation Scheme EmployingTurbo Codes”,Electronics Letters, v. 31, n. 18, pp. 1546–1547, Agosto1995.

[3] ROBERTSON, P., WÖRZ, T., “Bandwidth-Efficient Turbo Trellis-CodedModulation Using Punctured Component Codes”,IEEE Journal onSelected Areas in Communications, v. 16, n. 2, pp. 206–218, Fevereiro1998.

[4] UNGERBOECK, G., “Channel Coding with Multilevel/Phase Signals”,IEEE Transactions on Information Theory, v. IT-28, n. 1, pp. 55–67,Janeiro 1982.

[5] MARCELLIN, M. W., Trellis Coded Quantization: An Efficient Techni-que for Data Compression. Ph.D. dissertation, Texas A&M University,Texas, EUA, 1987.

[6] VUCETIC, B., YUAN, J., Turbo Codes: Principles and Applications. 1ed. Norwell, MA, EUA, Kluwer Academic Publishers, 2001.

[7] BAHL, L. R., COCKE, J., JELINEK, F.,et al., “Optimal Decoding ofLinear Codes for Minimizing Symbol Error Rate”,IEEE Transactionson Information Theory, v. IT-20, n. 2, pp. 248–287, Março 1974.

[8] JAIN, A. K., Fundamentals of Digital Image Processing. 1 ed. Englewo-od Cliffs, NJ, EUA, Prentice-Hall, Inc., 1989.

[9] UNGERBOECK, G., “Trellis-Coded Modulation with Redundant SignalSets: Part II - State of Art”,IEEE Communications Magazine, v. 25, n. 2,pp. 12–21, Fevereiro 1987.

[10] RICHARDSON, T., “The Geometry of Turbo-Decoding Dynamics”,IEEE Transactions on Information Theory, v. 46, n. 1, pp. 9–23, Janeiro2000.

[11] COVER, T. M., THOMAS, J. A.,Elements of Information Theory. 1ed. New York, EUA, John Wiley & Sons, Inc., 1991.

[12] CONWAY, J. H., SLOANE, N. J. A.,Sphere Packings, Lattices andGroups. New York, EUA, Springer Verlag, 1988.

Documents

TCMb