Codificação convolucional com o decodificador Viterbi

Alunos

Introdução
 
 

A proposta deste trabalho é introduzir ao leitor uma técnica de correção de erros conhecida como codificação convolucional com decodificação Viterbi. Mais particularmente, este trabalho vai focar primordialmente no algoritmo de decodificação Viterbi.
 
 

Seguindo esta introdução, vai ser demonstrada uma descrição detalhada dos algoritmos para a geração de números binários aleatórios, codificação com convolução dos dados, passar os dados codificados por um canal ruidoso, quantizar os símbolos do sinal recebido, e aplicar a decodificação Viterbi nos símbolos do canal quantizado para descobrir os dados binários originais. Também vão ser incluídos alguns resultados de um exemplo da simulação do código. Na descrição dos algoritmos são feitos comentários para um melhor entendimento dos algoritmos.
 
 

A proposta da correção de erros posterior (FEC) é de melhorar a capacidade de um canal adicionando informações redundantes cuidadosamente elaboradas aos dados que estão sendo transmitidos pelo canal. O processo de adicionar estas informações redundantes é conhecido como codificação de canal. Codificação convolucional e codificação de blocos são as duas melhores formas de se codificar um canal.
 
 

Códigos de convolução operam em dados seriais, um ou vários bits por vez. Blocos de códigos operam em blocos de mensagens relativamente grandes (tipicamente, acima de duzentos bytes). Existe uma variedade de códigos de convolução e de blocos utilizáveis, e uma variedade de algoritmos para a decodificação das seqüências de informações do sinal codificado recebido para descobrir os dados originais.
 
 

Codificação convolucional com decodificação Viterbi é uma técnica FEC que é particularmente utilizada para um canal em que o sinal transmitido é corrompido principalmente por um ruído branco gaussiano aditivo (AWGN). Deve-se pensar em um AWGN como um ruído cuja distribuição de tensão no tempo tem características que podem ser descritas usando-se um distribuição estatística, normal ou Gaussiana, por exemplo, uma curva em forma de sino. Esta distribuição de tensão tem um significado zero e um desvio padrão que é uma função da relação sinal ruído (SNR) do sinal recebido. Vamos assumir neste momento que o nível de sinal recebido é fixo. Então a relação sinal ruído é alta, o desvio padrão do ruído é pequeno, e vice-versa. Muitos canais de rádio são canais AWGN, mas muitos, particularmente canais de rádios terrestres tem outras disparidades, como multipath, atenuação seletiva, interferências, e ruídos atmosféricos. Transmissores e receptores podem adicionar sinais espúrios e ruídos de fase no canal designado. Embora a codificação convolucional com decodificação Viterbi possa ser útil em lidar com estes outros problemas, ela pode não ser a melhor técnica.
 
 

Códigos de convolução podem ser usualmente descritos usando-se dois parâmetros: a taxa de codificação e o tamanho de confinamento. A taxa de código, k/n, é expressa como uma relação entre o número de bits do decodificador convolucional (k) e o número de símbolos de canais da saída pelo codificador convolucional (n) em um dado ciclo do codificador. O parâmetro de tamanho de confinamento, K, denota o "comprimento" do codificador convolucional, por exemplo quantos estágios de k-bit são necessários para completar a lógica combinacional que produz os símbolos de saída. Relacionada com K está o parâmetro m, que indica quantos ciclos do codificador um bit de entrada é retido e usado para a codificação após a sua primeira aparição na entrada do codificador convolucional. O parâmetro m pode ser comparado ao tamanho da memória do codificador. Neste trabalho, e no exemplo do código fonte, será focado na taxa 1/2 para o código convolucional.
 
 

A decodificação Viterbi foi desenvolvida por Andrew J. Viterbi, o fundador da Qualcomm Corporation Sua tese foi em "Limites de Erro para Códigos Convolucionais e um Algoritmo de decodificação assintóticamente ótimo", publicado no IEEE Transactions of Information Theory, Volume IT-13, páginas 260-269, em abril de 1967. Desde então, outros pesquisadores têm expandido esta pesquisa encontrando bons códigos de convolução, explorando os limites de performance da técnica, e variando parâmetros de projeto do decodificador para otimizar a implementação da técnica em hardware e em software.
 
 

A decodificação Viterbi é um dos dois tipos de algoritmos de decodificação usados com codificação convolucional, o outro tipo é a codificação seqüencial. Codificação seqüencial tem a vantagem de poder atuar muito bem com códigos convolucionais de grande tamanho de confinamento, mas tem um tempo de codificação variável. Uma discussão sobre algoritmos de decodificação seqüencial vai além dos objetivos deste trabalho.
 
 

A decodificação de Viterbi tem a vantagem de ter um tempo de decodificação fixo. Ela se encaixa bem para implementação de decodificador com hardware, mas os seus requisitos computacionais crescem exponencialmente em função do seu tamanho de confinamento, então a sua prática é usualmente limitada para tamanhos de confinamento de K=9 ou menores. A empresa Stanford Telecom produz um decodificador Viterbi de K=9 que opera a taxas de até 96 Kbps e um decodificador Viterbi de K=7 que opera até 45 Mbps. Tecnologias de Wireless avançadas oferecem um decodificador Viterbi de K =9 que opera a taxas de até 2 Mbps. A NTT anunciou um decodificador Viterbi que opera a 60 Mbps mas não se conhece a sua viabilidade comercial.
 
 

Por alguns anos a codificação convolucional com decodificação Viterbi foi a técnica FEC predominantemente utilizada em comunicações espaciais, particularmente em redes de comunicação de satélites geoestacionários, como na rede VSAT (very small aperture terminal). Acredita-se que a variante mais utilizada nas redes VSAT é a codificação convolucional de taxa 1/2 usando um código com um tamanho de confinamento de K=7. Com este código, é possível transmitir sinais chaveados por fase binários ou quaternários (BPSK ou QPSK) com uma potência de no mínimo 5dB menor que a potência necessária para transmitir o mesmo sinal sem essa técnica de codificação. Esta é uma redução em watts com um fator maior que três muito útil para reduzir o custo de antenas e transmissores ou permitir o aumento das taxas de dados utilizando-se a mesma potência de transmissão e tamanhos de antenas.
 
 

A codificação convolucional utilizando a taxa 1/2 ocupa o dobro da banda do mesmo sinal sem a codificação, dado que a técnica de modulação é a mesma. Isto acontece porque com a taxa de codificação 1/2 , dois símbolos do canal são transmitidos para cada bit de dados. Para expandir a banda de freqüência seria necessário um acréscimo de potência de 3dB. Tendo em vista que o sinal poderia ser transmitido com uma redução de no mínimo 5dB, pode-se notar que o uso desta técnica de codificação é viável.
 
 

Nos últimos anos a codificação Viterbi tem sido concatenada juntamente com a codificação Reed-Solomon para comunicação de satélites geoestacionários, Essa é a técnica que tem sido utilizada em quase todos os sistemas de direct-broadcast satellite (DBS) e também nos produtos VSAT. Esse tipo de técnica tem sido divulgada como codificação turbo por utilizar implementações de codificação e decodificação em hardware.
 
 

Descrição dos algoritmos
 
 

Os passos envolvidos na simulação de um canal de comunicação utilizando comunicação convolucional e decodificação Viterbi são as seguintes:
 
 

• Geração de dados a serem transmitidos pelo canal de dados binários
• Codificação de forma convolucional do canal de dados binários em um canal de símbolos.
• Mapeamento dos símbolos do canal de uns/zeros em um sinal antipodal baseband produzindo um canal de símbolos a serem transmitidos.
• Adição de ruído aos símbolos transmitidos no canal para a simulação dos símbolos que chegam no receptor (com ruído).
• Quantização dos níveis de bit 1 do canal de recepção chamada quantização de difícil decisão(Hard Decision), e de dois a n bits que é chamada de fácil decisão (Soft Decision) (n é usualmente três ou quatro).
• Aplicação da decodificação Viterbi nos símbolos resultantes do canal recebido quantizado fazendo com que este seja novamente um canal de dados binários.
• Comparação dos dados binários decodificados com os dados binários transmitidos e contagem do número de erros.

Geração de dados
 
 

A geração dos dados a serem transmitidos pelo canal pode ser realizada de forma simples quando usado um gerador aleatório de números. Um que produza uma distribuição uniforme dos números no intervalo de 0 a um valor máximo dado no comando em C rand( ). Usando esta função, pode-se dizer que qualquer valor menor que a metade do valor máximo é um zero; qualquer valor maior ou igual que a metade do valor máximo é um 1.
 Uma implementação que está sendo estudada é a leitura de um arquivo .WAV ao invés da geração aleatória de dados.
 

Codificação convolucional dos dados
 
 

A codificação de forma convolucional dos dados é realizada usando-se um registrador de deslocamento e uma lógica combinacional associada que faz a adição de módulo dois (um registrador por deslocamento é meramente uma associação de flip-flops sendo que a saída do n-ésimo flip-flop é amarrado a entrada do flip-flop (n+1). Sempre que a borda ativa do clock ocorrer, a entrada do flip-flop é comutada na saída , e então os dados são deslocados para o próximo estágio). Freqüentemente a lógica combinacional é implementada na forma de portas ou-exclusivo cascateadas. Como uma forma de representação, as portas ou-exclusivo são portas com duas entradas, uma saída e representadas pelo símbolo lógico abaixo:
 

A sua tabela verdade é :

A porta ou-exclusivo faz a adição de módulo dois com suas entradas. Quando cascateada q portas ou-exclusivo de duas entradas com a saída do primeiro conectada à uma das entradas do segundo. A saída do segundo conecta à uma das entradas do terceiro, etc., a saída do último da cascata é a soma módulo dois da entrada q+1.

Outro método de ilustrar a adição módulo dois que é mais usada nos livros texto é como um círculo com um sinal + dentro, como abaixo:
 

Agora que tem-se dois componentes básicos da codificação convolucional (flip-flops compreendendo os registradores de deslocamento e as portas ou-exclusivo compreendendo os somadores de módulo dois associados) definidos pode-se analisar a figura de um codificador convolucional para uma taxa de código 1/2 , k=3, m=2.
 

Nesse codificador, os bits são fornecidos a uma taxa de k bits por segundo. Os símbolos do canal são colocados na saída a uma taxa de n=2k símbolos por segundo. O bit de entrada é estabilizado durante o ciclo de codificação. O ciclo de codificação começa quando ocorre uma borda de clock da entrada. Quando a borda de clock da entrada ocorrer, a saída do flip-flop do lado esquerdo é disponibilizada no flip-flop do lado direito, o bit de entrada anterior é disponibilizado no flip-flop da esquerda, e o novo bit de entrada torna-se disponível. Então a saída dos somadores de cima e de baixo tornam-se estáveis. Os ciclos do seletor de saída (bloco SEL A/B) passa por dois estados para cada estado de entrada, ele seleciona e põe na saída a saída do somador de módulo 2 de cima; no segundo estado ele seleciona e põe na saída a saída do somador de módulo 2 de baixo.
 
 

O codificador mostrado acima codifica o código convolucional k=3, (7,5). Os número octais 7 e 5 representam o gerador de código polinomial, o qual corresponde a (111b e 101b), quando lido em binário, as conexões do registrador de deslocamento dos somadores de módulo 2 de cima e de baixo, respectivamente. Este código foi determinado para ser o "melhor" código k=3 para taxa 1/2.. Este código será usado para discussões e exemplos posteriores por razões claras quando entrarmos no mérito do algoritmo de decodificação Viterbi.

Segue um exemplo de uma sequência de dados de entrada e a sequência correspondente de saída:
 
 

Dada a sequência de entrada 010111001010001.
 
 

Assume-se que as saídas de ambos os flip-flops no registrador de deslocamento sejam inicialmente zeros. O primeiro ciclo de clock habilita o primeiro bit de entrada, um zero, disponível ao codificador. As saídas dos flip-flops são ambas zero. As entradas dos somadores de módulo 2 são todas zeros, portanto a saída do codificador é 00b.
 
 

O segundo ciclo de clock faz com que o segundo bit de entrada esteja disponível ao codificador. O flip-flop da esquerda desloca o bit anterior, que era um zero, e o flip-flop da direita desloca a saída zero do flip-flop da esquerda. As entradas do somador de módulo 2 superior são 100b, portanto a saída é um 1b. As entradas do somador de módulo 2 inferior são 10b, portanto a saída também é um 1b. Então a saída do codificador é 11b.

O terceiro ciclo de clock faz com que o terceiro bit de entrada esteja disponível ao codificador. O flip-flop da esquerda desloca o bit anterior, que era um 1b, e o flip-flop da direita desloca o zero de dois tempos de bit atrás. As entradas do somador de módulo 2 superior são 010b, portanto a saída é um 1b. As entradas do somador de módulo 2 inferior são 00b, portanto a saída é um 0b. Então a saída do codificador é 10b.

E assim por diante. O diagrama de tempos mostrado abaixo ilustra o processo.
 
 

Depois de todas as entradas terem sido codificadas, a sequência de saída será:
 
 

00 11 10 00 01 10 01 11 11 10 00 10 11 00 11
 
 

Para cada par de bit representado acima o primeiro bit deles é a saída do somador de módulo 2 superior e o segundo é a saída do somador de módulo 2 inferior.
 
 

Pode se observar na estrutura do codificador convolucional de taxa 1/2 com k=3 e do exemplo dado acima que cada bit de entrada tem um efeito em três sucessivos pares de símbolos de saída. Este é um ponto extremamente importante que da ao código convolucional o seu poder de correção de erros. A razão para isso tornar-se-á evidente quando o algoritmo decodificador Viterbi for analisado.
 
 

Agora se forem mandados os 15 bits de dados mostrados anteriormente, de modo com que o último bit afete 3 pares dos símbolos de saída, faz-se necessário que mais dois pares de símbolos sejam colocados na saída, isto é realizado no nosso exemplo deixando com que mais dois pulsos de clock atuem no codificador convolucional enquanto a saída continua em zero. Esse efeito é chamado "nivelamento" do codificador e resulta em dois pares adicionais nos símbolos de saída, resultando:
 
 

00 11 10 00 01 10 01 11 11 10 00 10 11 00 11 10 11
 
 

Se não for feita a operação de nivelamento, o último bit da mensagem tem menos capacidade de correção de erros que os anteriores. Essa é uma característica muito importante a ser lembrada quando a técnica FEC for usada em uma aplicação onde o número de clocks seja previamente definido. Também deve ser lembrado que o registrador de deslocamento deve ser zerado no início de cada nova seqüência de bits. O codificador deve ser iniciado em um estado conhecido e terminar em um estado conhecido para que o decodificador seja capaz de reconstruir a seqüência de entrada de dados apropriadamente.
 
 

Agora o codificador pode ser visto por outra perspectiva. O codificador pode ser visto como uma simples máquina de estados. O codificador exemplificado tem dois bits de memória, portanto há 4 estados possíveis. Ao flip-flop da esquerda vai ser dado um peso binário de 2¹, e ao flip-flop da direita vai ser dado um peso binário de 2⁰. Inicialmente, o codificador esta no estado de "todos-zero" se o primeiro bit de entrada for um zero, o codificador continua no estado de "todos-zero" na próxima transição de clock. Mas se o bit de entrada for um 1 o codificador comuta para o estado 10 na próxima transição de clock. No entanto, se o próximo bit de entrada for um zero, o codificador comuta para o estado 01b, caso contrário, ele comuta para o estado 11b. A tabela seguinte ilustra o estado futuro dado o estado presente na entrada:
 
 

A tabela acima vai ser referida como a tabela de próximo estado. Agora será ilustrada uma tabela que lista os símbolos de saída do canal
 
 

Agora pode-se ver que, com essas duas tabelas, pode-se descrever completamente o comportamento do codificador convolucional de taxa 1/2 e k=3. Nota-se que ambas as tabelas tem 2^(K-1) linhas, e 2^k colunas, onde K é o tamanho de confinamento e o k é o número de bits que entram no codificador a cada ciclo.
 
 

Mapeamento dos símbolos de canais em níveis de sinal
 
 

Mapear a saída um/zero do codificador convolucional em esquema de sinalização antipodal basehand é simplesmente um problema de transladar zeros para +1 e uns para -1, isso pode ser feito a partir da operação y = 1-2x para cada símbolo de saída do codificador convolucional.
 
 

Adicionar ruído aos símbolos transmitidos
 
 

Adicionar ruído aos símbolos transmitidos do canal produzido pelo codificador convolucional envolve a geração Gaussiana de números aleatórios, escalar os números de acordo com a energia requerida por símbolo em relação a taxa de densidade de ruído, E_S/N₀, e adicionar os números aleatórios Gaussianos aos valores dos símbolos do canal.

O gerador aleatório Gaussiano de números é a única parte interessante desta tarefa. O C fornece somente um gerador uniforme de números aleatórios, rand(). De forma a obter números aleatórios Gaussianos pode-se tirar vantagem das relações entre distribuições uniforme, Rayleigh e Gaussiana:

Dada uma variável aleatória uniforme U, uma variável R aleatória de Rayleigh pode ser obtida por
 

Onde é a variância da variável aleatória de Rayleigh, e sendo dados R e uma segunda variável aleatória uniforme V, duas variáveis aleatórias Gaussianas G e H podem ser obtidas por
 

                    G = R cos U e H = R sen V.
 

No canal AWGN, o sinal é corrompido por ruído adicional, n(t), que tem o espectro de potência No/2 watts/Hz. A variância desse ruído é igual a No/2. Se a energia por símbolo Es for igual a 1, então
 

Quantização dos símbolos do canal de recepção

Um decodificador Viterbi ideal trabalharia com precisão infinita, ou pelo menos números de ponto flutuante. Em sistemas práticos os símbolos do canal de recepção são quantizados com um ou alguns bits de precisão de forma a reduzir a complexidade do decodificador Viterbi. Se os símbolos no canal de recepção são quantizados com precisão de um bit (< 0V=1, > 0V=0), o resultado é chamado dado de difícil decisão(Hard Decision). Se os símbolos do canal de recepção são quantizados com mais que um bit de precisão, o resultado é chamado de dado de fácil decisão(Soft Decision). Um decodificador Viterbi com entrada de dados de fácil decisão quantizados em três ou quatro bits de precisão pode atuar aproximadamente 2dB melhor que um decodificador trabalhando com entradas de difícil decisão. A precisão de quantização usual é 3 bits.
 
 

A seleção dos níveis de quantização é uma decisão importante porque pode ter um efeito significante na performance da conexão. Segue uma breve explicação de uma maneira de se escolher esses níveis. Assume-se que os níveis de sinais ausência de ruído são -1V=1, +1V=0. Com ruído o sinal recebido tem significado +/- 1 e desvio padrão . Assumindo um quantizador uniforme de três bits com a relação entrada/saída ilustrada na figura abaixo, onde D é o nível de decisão que será calculado brevemente:

O nível de decisão D pode ser calculado de acordo com a fórmula , onde ES/N0 é a energia por símbolo da taxa de densidade de ruído.
 
 

Execução da decodificação Viterbi
 
 

O decodificador Viterbi é o principal foco desse trabalho, talvez o conceito mais importante para auxiliar no entendimento do algoritmo Viterbi seja o diagrama de treliças. A figura abaixo mostra o diagrama de treliças para o codificador convolucional de taxa 1/2 , K=3, para uma mensagem de 15 bits
 
 

Os quatro estados possíveis do codificador são descritos como quatro linhas de pontos horizontais. Há uma coluna de quatro pontos para o estado inicial do codificador e um para cada instante de tempo durante a mensagem. Para uma mensagem de 15 bits com dois bits de nivelamento do codificador, existem 17 instantes de tempo em adição ao t = 0, que representa a condição inicial do codificador. As linhas sólidas conectando os pontos no diagrama representam transições de estado quando o bit de entrada for 1, as linhas pontilhadas representam transições de estado quando o bit de entrada for 0. Nota-se a correspondência entre as setas no diagrama de treliças e a tabela de estados discutida anteriormente. Nota-se também que, desde que a condição inicial do codificador é estado 00, e os dois bits de nivelamento são zeros, as setas saem do estado 00 e chegam no mesmo estado.

O diagrama abaixo mostra os estados das treliças que são utilizados durante a codificação do exemplo da mensagem de 15 bits.
 
 

Os bits de entrada do codificador e os símbolos de saída são mostrados na parte inferior do diagrama. Nota-se a correspondência entre os símbolos de saída codificados e a tabela de saída discutida anteriormente. Logo abaixo será visto em detalhes o uso da versão expandida da transição entre um instante a outro:
 

Os números de dois bits distribuídos nas linhas são os símbolos de saída do canal do codificador convolucional correspondente. Lembra-se que as linhas pontilhadas representam casos onde a entrada codificada é um zero, e as linhas sólidas representam casos em que a entrada codificada é 1. Na figura acima, os números de dois bits distribuídos nas linhas pontilhadas estão na esquerda, e os número de dois bits distribuídos nas linhas sólidas estão na direita .

Agora será visto como o algoritmo de decodificação Viterbi trabalha. Por exemplo: será usado símbolo de entrada de difícil decisão para simplificar. O código fonte exemplo usa entradas de fácil decisão para atingir uma melhor performance. Supõe-se que seja recebida a mensagem codificada baixo com um par de bits errados:
 

A cada instante é recebido um par de símbolos do canal, será computado uma medida para "distância" entre o que foi recebido e todos os pares de símbolos do canal possíveis de serem recebidos. Indo de t=0 a t=1, existe somente dois pares de símbolos de canal possíveis de serem recebidos: 00b e 11b. Isso porque sabe-se que o codificador convolucional foi inicializado com estados "todos-zero" e teve um bit igual a um ou zero de entrada, existem somente dois estados nos quais a transição poderia ocorrer e duas saídas possíveis do codificador. Estas saídas possíveis do codificador são 00b e 11b.
 
 

A medida que será usada agora é a distância Hamming entre o par de símbolos do canal recebido e o possível par de símbolos do canal. A distância Hamming é computada pela contagem simples de quantos bits são diferentes entre o par de símbolos do canal recebido e o possível par de símbolos do canal.
 
 

Os resultados podem ser somente zero, um ou dois. Os valores da distância Hamming computados a cada instante de tempo para os caminhos entre os estados do instante de tempo anterior e os estados do instante de tempo atual são chamados de medida de ramo. Para o primeiro instante de tempo os resultados serão salvos como valores de "erro de medida acumulado", associados com estados. Para o segundo instante de tempo , o erro de medida acumulado será computado adicionando-se o erro de medida acumulado anterior a medida ramificada atual.
 
 

Em t=1, foi recebido 00b. Os únicos pares de símbolos possíveis do canal a serem recebidos são 00b e 11b. A distância Hamming entre 00b e 00b é zero. A distância Hamming entre 00b e 11b é dois. Entretanto, a medida do ramo do estado 00b para o estado 00b é zero, e para o ramo do estado 00b para o estado 10b é dois. Desde que os valores anteriores da medida de erro acumulada são iguais a zero, os valores métricos acumulados para o estado 00b e para o estado 10b são iguais aos valores das medidas de ramo. O valor da medida de erro acumulada para os outros dois estados é indefinida. A figura abaixo ilustra os resultados em t=1:
 

Nota-se que as linhas sólidas entre os estados em t=1 e o estado em t=0 ilustra o relacionamento antecessor-sucessor entre os estados em t=1 e o estado em t=0, respectivamente. Essa informação é mostrada graficamente na figura, mas é armazenada numericamente na implementação atual, ou seja, a cada instante de tempo t será armazenado o número do estado antecessor que resultou em cada estado atual em t.
 
 

Agora vai ser visto o que acontece em t=2. Foi recebido um par de símbolos do canal 11b. Os pares de símbolos de canais possíveis de serem recebidos na ida de t=1 para t=2 são 00b indo do estado 00b para o estado 00b, 11b indo do estado 00b para o estado 10b, 10b indo do estado 10b para o estado 01b, e 01b indo do estado 10b para o estado 11b. A distância Hamming entre 00b e 11b é dois, entre 11b e 11b é zero, e entre 10b ou 01b e 11b é um. Foram adicionados esses valores de medidas de ramo aos valores de medida de erro acumulados anteriormente associados com cada estado originário para atingir o estado atual. Em t=1,pode-se estar somente em estado 00b ou estado 10b. Os valores de medida de erro acumulados associados com estes estados eram 0 e 2, respectivamente. A figura abaixo mostra o cálculo da medida de erro acumulado associado com cada estado, em t=2.
 

Estes são todos os dados computados para t = 2. O que será reservado para t = 3 será o erro de medida acumulado para cada estado, e os estados antecessores para cada um dos quatro estados em t = 2, correspondente às relações dos estados mostrado pelas linhas sólidas na ilustração das treliças.

Agora vai ser analisada a figura para t = 3. As coisas tornam-se mais complicadas aqui, sendo que agora existem dois caminhos diferentes que poderiam ser tomados para cada um dos quatro estados que eram válidos em t = 2, para os quatro estados que são válidos em t = 3. Que caminhos devem ser tomados? A resposta é, devem ser comparadas as medidas de erro acumuladas associadas a cada ramo, e descartada a maior de cada par de ramos que levam a um determinado estado. Se os membros de um par de medidas de erro acumuladas que vão até um estado particular são iguais, os valores devem ser salvos. Outra coisa que é afetada é o histórico antecessor-sucessor que estava sendo mantido. Para cada estado, o antecessor que se mantém é aquele da medida de ramo mais baixo. Se as duas medidas de erro acumulado forem iguais, algumas pessoas usam o ‘lance justo da moeda’ para escolher qual estado antecessor que se mantém. Outros simplesmente escolhem sempre a mesma decisão, por exemplo o ramo superior ou o ramo inferior. O método usado provavelmente não importa. A operação de adicionar a medida de erro acumulada anterior na medida do novo ramo, comparando os resultados, e selecionando a menor medida de erro acumulada a ser retida para o novo instante de tempo é chamada operação adicionar-comparar-selecionar. A figura abaixo ilustra os resultados de processamento em t=3:
 

Nota-se que o terceiro par de símbolos recebido tinha um erro de símbolo. A menor medida de erro acumulada é um 1, e existem dois destes.

Será visto agora o que acontece em t=4. O processamento é o mesmo utilizado para t=3. Os resultados são mostrados na figura:
 
 

Nota-se que para t=4, o caminho na treliça da mensagem atualmente transmitida, mostrada em negrito, é normalmente associada à menor medida de erro acumulada. Tem-se para t=5:
 

Para t=5, o caminho pela treliça correspondente a mensagem atual, mostrada em negrito, ainda está associada à menor medida de erro acumulada. Esse ponto que o decodificador Viterbi explora para descobrir a mensagem original.
 
 

Em t=17, a treliça tem este formato, com o histórico dos estados intermediários removido:
 

O processo de decodificação começa com a construção da medida de erro acumulada para alguns números dos pares de símbolos do canal de recepção, e o histórico de quais estados que antecediam os estados de cada instante de tempo t com a menor medida de erro acumulada. Assim que essa informação tenha sido construída, o decodificador Viterbi esta pronto para recriar a seqüência de bits da entrada do codificador convolucional quando a entrada foi codificada para a transmissão. Ela é resultante dos seguintes passos:
 
 

Primeiramente, selecionar o estado tendo a menor medida de erro acumulada e salvar o número deste estado.
 
 

Interativamente, executar os passos abaixo até que o começo da treliça seja alcançada: Trabalhar retrocedendo com a tabela de histórico anterior para o estado selecionado, selecionar um novo estado que é listado na tabela de histórico de estados como sendo o antecessor para aquele estado. Salvar o número de cada estado selecionado. Esse passo é chamado trace-back

Agora trabalhar avançando na lista do estado selecionado salva nos passos anteriores. Encontrar qual o bit de entrada corresponde a uma transição de cada estado antecessor para seu estado sucessor. Este é o bit que deve ser codificado pelo codificador convolucional.
 
 

A tabela abaixo mostra a medida acumulada para todos os 15 bits (mais dois bits de nivelamento) da mensagem usada como exemplo em cada tempo t:
 
 

É interessante notar que para o exemplo de decodificador de entrada de difícil decisão, a menor medida de erro acumulado no estado final indica quantos erros de símbolo de canal ocorreram:
 
 

A tabela seguinte mostra os estados selecionados que traçam o caminho de volta pela tabela mantida mostrada abaixo:

Usando a tabela que mapeia os estados de transição em relação as entradas que os causaram, pode-se recriar a mensagem original. Aqui está esta tabela que parece com o exemplo de taxa 1/2 e K=3 do código convolucional:

Nota-se na tabela acima, x denota uma transição impossível de um estado para o outro estado.
 

Agora tem-se todas as ferramentas requeridas para recriar a mensagem do sinal original da mensagem que foi recebida:
 
 

Os dois bits de nivelamento são descartados.
 

Aqui tem-se uma visão geral de como o algoritmo traceback eventualmente encontra seu caminho na direção certa. Mesmo que este tenha iniciado escolhendo o estado inicial errado. Isso pode acontecer se mais de um estado tiver a menor medida de erro acumulado, por exemplo. A figura da treliça em t =3 será novamente usada para ilustrar este ponto:
 

Pode-se ver como em t=3, ambos os estados 01b e 00b tem uma medida de erro acumulada igual a um. O caminho correto vai para o estado 01b, nota-se que a linha em negrito mostra o caminho da mensagem atual que vai para a este estado. Mas supostamente foi escolhido o estado 11b para começar o traceback. O estado antecessor para o estado 11b, estado 10b, é o mesmo que o estado antecessor para o estado 01b ! Isto porque em t = 2, o estado 10b tem a menor medida de erro acumulada. Mas depois de um falso início, está quase imediatamente de volta ao caminho correto.
 
 

Para o exemplo da mensagem de 15 bits, construiu-se as treliças para a mensagem inteira antes de começar o traceback. Para mensagens maiores, ou dados contínuos, isto não é prático e nem desejável, devido a memórias de confinamento e atraso na decodificação. Pesquisas tem mostrado que um tamanho de traceback de K x 5 é suficiente para a decodificação Viterbi com o tipo de códigos que foram discutidos. Qualquer profundidade de traceback decrementa o atraso de decodificação e os requisitos de memória de decodificação, entretanto, não melhorando significativamente a performance do decodificador. A exceção são códigos puncionados, os quais serão descritos mais tarde. Eles requerem um traceback mais profundo para alcançar seus limites finais de performance.
 

Para implementar um decodificador Viterbi em software, o primeiro passo é construir algumas estruturas de dados com as quais o algoritmo do decodificador será implementado. Essas estruturas de dados são melhor implementadas como matrizes. As seis primeiras matrizes necessárias para o decodificador Viterbi são as seguintes:
 

• Uma cópia da tabela próximo estado do codificador convolucional, a tabela transição de estado do codificador. As dimensões desta tabela (linhas x colunas) são 2(K -1) x 2k. Esta matriz tem que ser inicializada antes do início do processo de decodificação.
• Uma cópia da tabela saída do codificador convolucional. As dimensões desta tabela (linhas x colunas) são 2(K -1) x 2k. Esta matriz tem que ser inicializada antes do início do processo de decodificação.
• Uma matriz (tabela) mostrando para cada estado atual e próximo estado do codificador convolucional, que o valor de entrada (zero ou um) produziria o próximo estado, resultando no estado atual. Esta matriz será chamada de tabela entrada. Suas dimensões são 2( K-1 ) x 2( K-1 ) .Esta matriz tem que ser inicializada antes do início do processo de decodificação.
• Uma matriz para armazenar a medida de erro acumulada para cada estado computado usando a operação adicionar-comparar-selecionar. Esta matriz será chamada medida de erro acumulada. A dimensão desta matriz é 2( K-1 ) x 2. Esta matriz não necessita ser inicializada antes do início do processo de decodificação.
• Uma matriz para armazenar uma lista de estados determinados durante o traceback (termo a ser explicado abaixo). Ela é chamada de matriz sequencia estado. A dimensão desta matriz é ( K x 5) +1. Esta matriz não necessita ser inicializada antes do início do processo de decodificação.

voltar para a introdução

Exemplos de códigos fonte para simulação
 
 

A simulação de códigos de fonte que incluem uma rotina de teste e muitas funções que serão descritas abaixo. Este código simula uma conexão entre o canal AWGN desde a fonte de dados até a saída do decodificador Viterbi.
 
 

A rotina de teste primeiro aloca dinamicamente várias matrizes para armazenar os dados fonte, os dados fonte codificados de forma convolucional, a saída do canal AWGN e a saída de dados pelo decodificador Viterbi. Na seqüência, ela chama o gerador de dados, codificador convolucional, simulação de canal e funções necessárias ao decodificador Viterbi. Este então compara a saída fonte de dados do gerador de dados para a saída de dados do codificador Viterbi e conta o número de erros. Uma vez que 100 erros são acumulados, então a rotina de teste mostra a Taxa de erro de Bits (BER) para um dado Es/No. Os parâmetros de teste são controlados pelas definições no arquivo vdsim.h.
 
 

A rotina de teste inclui uma opção compile-time para também medir o BER para um canal não codificado, por exemplo um canal sem correção de erro adiante. Esta opção foi usada para validar o gerador de ruídos Gaussiano, comparando o BER não codificado simulado com o BER não codificado teórico codificado dado por:

onde Eb/No é expressa como uma taxa, não em dB.
 
 

O função gerador de dados simula os dados fonte. Ela aceita como argumentos um ponteiro para uma matriz de entrada e o número de bits a serem gerados, e completa a matriz com zeros e uns aleatóriamente escolhidos.
 
 

A função codificador convolucional aceita como argumentos os ponteiros das matrizes de entrada e saída. Ela executa então a codificação convolucional especificada e completa a matriz de saída com símbolos de canal um/zero. Os parâmetros do código convolucional estão no cabeçalho do arquivo vdsim.h.
 
 

A função simulação de canal aceita como argumentos o Es/No designado, o número de símbolos do canal na matriz de entrada, e ponteiros para as matrizes de entrada e saída. Ela adiciona variáveis aleatórias Gaussianas aos símbolos mapeados e completa a matriz de saída. Os dados de saída são números de ponto flutuante.
 
 

Os argumentos para a função decodificador Viterbi são os Es/No esperados, o número de símbolos de canal na matriz de entrada, e os ponteiros para suas matrizes de entrada e saída. Primeiramente a função de decodificação configura sua estrutura de dados, as matrizes descritas no na seção de descrição do algoritmo . Então, ele executa uma quantização fácil de três bits sobre símbolos de canal recebidos de ponto flutuante, utilizando o Es/No esperado, produzindo inteiros. Isto completa o processamento preliminar.
 
 

O próximo passo para iniciar a decodificação dos símbolos de canal de fácil decisão. O decodificador constrói uma treliça de dimensão K x 5 e traça do final para o começo da treliça e coloca um bit na saída. Então o decodificador desloca a treliça esquerda em um instante de tempo, descartando o dado antigo, continuando, ele computa a medida de erro acumulada para o próximo instante de tempo, traceback, e põe um bit na saída. O decodificador continua por este caminho até alcançar os bits de nivelamento. Os bits de nivelamento fazem com que o codificador causem no codificador uma convergência de volta ao estado zero, e o decodificador explora este fato. Uma vez que o decodificador constrói a treliça para o próximo bit, ele nivela a treliça, decodificando e colocando na saída todos os bits na treliça até o bit de nivelamento, exclusive.
 
 

O código fonte de simulação foi compilado e testado usando Borland C++ Builder V.3. Os resultados da simulação são representados a seguir.

voltar para a introdução

Conclusão - Resultados do exemplo de simulação
 

Os resultados obtidos mostrados neste gráfico usando o código exemplo de simulação, com a dimensão das treliças configuradas para K x 5, usando o quantizador adaptativo com a quantização de símbolo de canal de 3 bits. Para cada ponto de dados, foi executada a simulação até ocorrerem 100 erros ou mais. Com este número de erros tem-se a confiabilidade de 95% que o verdadeiro número de erros está entre 80 e 120.
 
 

Pode-se notar como os resultados da simulação para o BER em um canal não codificado aproxima-se do BER teórico para um canal não codificado. Isso valida o algoritmo BER não codificado e o gerador de ruído Gaussiano. Os resultados do BER codificado aparecem para combinar bem com aqueles obtidos pelos outros.
 
 

O próximo passo é obviamente iniciar variando alguns dos parâmetros. Por exemplo, pode-se tentar diferentes áreas de treliças, um quantizador fixo no lugar de um quantizador adaptativo, mais ou menos bits no quantizador e assim por diante.

voltar para a introdução

 Bibliografia
 

4i2i  C++, VHDL e código Verilog para codificador convolucional /decodificadores Viterbi.

Advanced Hardware Architectures  codificadores/decodificadores turbo, codificadores/decodificadores Reed-Solomon, e um decodificador concatenado Viterbi/Reed-Solomon.

Advanced Wireless Technologies decodificadores Viterbi, decodificadores Reed-Solomon e decodificadores concatenados.

Efficient Channel Coding, Inc. desenvolveu técnicas de codificação turbo implementadas por Advanced Hardware Architectures em seu componente AHA4501.

Istari Design, Inc.decodificadores Reed-Solomon .Encotra-se também Simuladores de decodificadores de Viterbi e desenvolvimento de decodificadores Viterbi .

Qualcomm decodificador  Viterbi/Treliça.

Stanford Telecom inúmeros chips de decodificadores Viterbi.