Fundamentos dos Códigos Convolucionais e Algoritmo de Viterbi

CODIGOS CONVOLUCIONAIS Além dos Codigos de Blocos Lineares os Codigos Convolucionais compdem outra grande familia de cédigos corretores de erros Este capitulo descreve os fundamentos dos cdédigos convolucionais sendo que os principais topicos abordados nessas notas de aulas sao Ocodificador convolucional e suas representagées Decodificagao de Codigos Convolucionais com o algoritmo de Viterbi Capacidade de correcao de erros dos Codigos Convolucionais Cédigos Convolucionais Catastroficos Céddigos Convolucionais sistematicos e Melhores Codigos Convolucionais Conhecidos 51 INTRODUGAO Considere 0 bloco de codificagéo apresentado na Figura 51 que representa um codificador convolucional A mensagem m a ser codificada é representada pela seqiiéncia m mo mj onde cada m representa um bit e 7 o indice correspondente ao tempo Seaiiéncia d d Seqiiéncia codificada equencia de entrada Codificador Gm m NM Mi Convolucional C CI Coy oer y Cy oe Onde Ci Cliy 006 5 Cji yg 00 5 Cni Figura 51 Bloco de codificagao convolucional Suponha que massuma os valores zero ou um de forma equiprovavel e que a presenca de um ou outro seja estatisticamente independente ou seja o bit presente nao depende de seu predecessor nem influencia seu sucessor O codificador transforma cada seqiiéncia m em uma unica seqiiéncia codigo ec Gm A seqiiéncia U pode ser segmentada em uma seqiiéncia de palavras ramos C1 C2 5 Cis Cada palavra ramo c um simbolo codigo binario freqiientemente chamado de simbolo do canal bits do canal ou bits codigos Ao contrario dos bits da mensagem de entrada os bits dos simbolos codigos nao sao independentes Isto significa que embora uma seqtiéncia m defina uma Unica seqiiéncia uma caracteristica chave dos cédigos convolucionais é que um elemento m de uma seqiiéncia de entrada m nao suficiente para definir seu simbolo cédigo associado c em U uma vez que a codificagao de cada elemento m nao apenas funao do proprio m mas é também do elemento m que o precedeu 51 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 52 Um codificador convolucional genérico mostrado na Figura 22 é constituído de um registrador de deslocamento de kK estágios e somadores módulo2 onde K determina a extensão de influência ou profundidade do código A profundidade influência de um código convolucional é definida como sendo o máximo número de bits codificados que podem ser afetados por um único bit de entrada A cada unidade de tempo k bits são deslocados para os primeiros k estágios do registrador todos os bits no registrador são deslocados k bits para a direita e as saídas dos n somadores são seqüencialmente amostradas para a obtenção do símbolo código ou bits códigos Uma vez que n bits códigos são obtidos na saída para cada grupo de k bits de mensagem a taxa do código é kn bits de mensagem por bits códigos onde k n Figura 52 Codificador convolucional 52 REPRESENTAÇÕES E CARACTERÍSTICAS BÁSICAS DO CODIFICADOR 1 2 3 Para descrever um código convolucional é necessário caracterizar a função de codificação Gm de tal forma que dada uma seqüência de entrada m seja possível determinar a saída codificada c Uma abordagem muito comum para apresentar o processo da codificação convolucional é por meio de um exemplo Assim sendo os tópicos apresentados a seguir mostram as formas de representação mais comuns bem como as características básicas de um codificador convolucional e seu princípio de operação 1 2 3 kK Seqüência de entrada m kK estágios registradores de deslocamento n somadores módulo2 Seqüência código c 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 53 521 REPRESENTAÇÃO PICTORIAL A representação pictorial nada mais é do que o desenho do codificador Considere por exemplo o codificador convolucional apresentado na Figura 53 onde a cada instante de tempo um bit de entrada ocupa a posição mais a esquerda do registrador de deslocamento k 1 Como o codificador possui dois somadores módulo2 para cada bit que entra no codificador dois bits códigos são gerados na saída pela amostragem dos resultados dos dois somadores Logo este codificador gera um código de taxa kn 12 com profundidade K 3 Figura 53 Codificador convolucional taxa 12 K 3 A escolha entre das conexões entre os somadores e os estágios dos registradores determinam as características do código Qualquer mudança na escolha das conexões resulta em um código diferente As conexões não são escolhidas arbitrariamente entretanto elas afetam as características de distância do código ou seja seu desempenho Esta escolha é complicada e não existe até o momento uma regra geral que de escolha de conexões que maximize a distância de um código Bons códigos com profundidade menor que 20 têm sido obtidos através de busca computacional Ao contrário dos códigos de bloco que possuem palavras com comprimento fixo um código convolucional não possui um tamanho de bloco particular No entanto códigos convolucionais são freqüentemente forçados para uma estrutura de bloco através de um truncamento periódico Isso requer um número de bits zeros adicionados ao final de uma seqüência com o propósito de esvaziar o conteúdo dos registradores de deslocamento Como os zeros adicionados não transportam informação a taxa efetiva de codificação cai abaixo de kn Para manter a taxa de codificação próxima de kn o período de truncamento deve ser feito tão longo quanto prático Bit de entrada m c1 c2 Saída 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 54 522 PRINCÍPIO DE OPERAÇÃO Suponha agora que a mensagem mX 1 X X 3 deve ser codificada pelo codificador da Figura 53 O processo de codificação é mostrado passo a passo na Figura 54 e as entradas registro de todos os estados dos registradores e saída à cada deslocamento são apresentados na Tabela 51 Figura 54 Codificação da mensagem m 1101 através da máquina de estados obtida passo a passo 1 0 0 Deslocamento 1 c1 c2 c1 c2 1 1 0 1 0 Deslocamento 2 c1 c2 c1 c2 1 0 1 0 1 Deslocamento 3 c1 c2 c1 c2 0 0 1 1 0 Deslocamento 4 c1 c2 c1 c2 0 1 0 1 1 Deslocamento 5 c1 c2 c1 c2 0 1 0 0 1 Deslocamento 6 c1 c2 c1 c2 1 1 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 55 Tabela 51 Codificação da mensagem mX 1 X X 3 para o codificador da Figura 53 DESLOCAMENTO ENTRADA CONTEÚDO DOS REGISTRADORES SAÍDA c1 c2 0 1 0 0 0 1 0 1 0 0 11 2 1 0 1 0 10 3 1 1 0 1 00 4 0 1 1 0 01 5 0 0 1 1 01 6 0 0 0 1 11 7 0 0 0 00 Saída 11 10 00 01 01 11 Observe na Tabela 51 que foi necessário acrescentar dois zeros para a obtenção da seqüência codificada de saída e três zeros para esvaziar totalmente o registrador de deslocamento Independentemente do tamanho da seqüência a ser codificada é necessário acrescentar kK 1 zeros para a obtenção da seqüência código de saída Conseqüentemente o zero do sétimo deslocamento é desnecessário e o primeiro bit de um novo bloco de entrada poderia estar no primeiro estágio do registrador de deslocamento A Figura 53 mostra um codificador em sua forma pictorial Outra forma de representar o codificador é através da especificação de um conjunto de n vetores conexão um para cada somador módulo2 Cada vetor tem a dimensão kK e descreve as conexões entre os estágios do registrador de deslocamento e os somadores módulo2 Um um na iésima posição do vetor indica que o estágio correspondente do registrador de deslocamento está conectado ao somador representado pelo vetor e um zero em uma dada posição indica que aquela posição não é conectada ao somador Para o codificador da Figura 23 podese escrever os vetores conexão g1 e g2 para os dois somadores como 101 111 2 1 g g 523 RESPOSTA AO IMPULSO DO CODIFICADOR Podese determinar a resposta ao impulso de um codificador convolucional fazendo um único 1 atravessálo desde o primeiro estágio do registrador de deslocamento até o último Para o codificador da Figura 53 a resposta ao impulso pode ser obtida de acordo com a Tabela 52 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 56 Tabela 52 Resposta ao impulso do Codificador Convolucional apresentado na Figura 53 DESLOCAMENTO CONTEÚDO DOS REGISTRADORES SAÍDA 1 1 0 0 11 2 0 1 0 10 3 0 0 1 11 Resposta ao impulso 11 10 11 Note que a resposta ao impulso pode ser obtida diretamente dos vetores conexão conforme mostrado a seguir g1 g2 1 1 1 0 1 1 11 10 11 A resposta ao impulso permite a determinação da saída do codificador para uma dada entrada m pela superposição ou adição linear das respostas ao impulso deslocadas no tempo ou ainda pela convolução da seqüência de entrada com a resposta ao impulso do codificador Para a mensagem m 1 1 0 1 a saída do codificador obtida a partir da resposta ao impulso é obtida da forma como se segue Entrada m Saída 1 1 1 1 0 1 1 0 0 0 0 0 0 0 1 1 1 1 0 1 1 1 1 1 1 0 1 1 Soma módulo2 1 1 1 0 0 0 0 1 0 1 1 1 A resposta ao impulso deslocada pode ser representada também na forma matricial e a seqüência código c pode ser obtida da forma c mG da mesma forma que para códigos de blocos lineares 10 00 01 0111 11 11 10 11 11 10 11 11 10 11 11 10 11 1 011 m G c Note que as dimensões da matriz dependem da resposta ao impulso e do comprimento da mensagem É interessante notar ainda que apesar da taxa de codificação do codificador em questão ser igual a ½ uma mensagem de 4 bits produziu uma seqüência codificada de 12 bits ou seja uma taxa igual a 412 13 Isso se deve aos kK 1 zeros necessários para o esvaziamento do registrador de deslocamento que neste caso são 2 e produz dois pares de bits adicionais à seqüência código Conseqüentemente a taxa de codificação deve ser entendida como a taxa 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 57 quando a mensagem possui comprimento infinito Por exemplo para esse mesmo codificador uma mensagem com 1000 bits produz uma seqüência código com 2000 4 bits Neste caso a taxa é 10002004 ½ 524 REPRESENTAÇÃO POLINOMIAL Um codificador convolucional pode ser representado por um conjunto de n polinômios geradores correspondentes aos n somadores módulo2 que compõem o codificador Cada polinômio possui grau igual ou menor que K 1 e descreve as conexões entre os estágios do registrador de deslocamento e seu respectivo somador da mesma forma que os vetores conexão Os coeficientes de cada termo de cada polinômio assumem valores 1 ou 0 dependendo da existência ou não de conexão entre uma posição específica do registrador de deslocamento e o seu respectivo somador Para o codificador da Figura 53 os polinômios geradores em termos de operador D operador delay são g1D 1 D D 2 g2D 1 D 2 onde o termo de mais baixa ordem corresponde ao estágio de entrada do codificador A seqüência de saída do codificador pode ser obtida conforme indicado a seguir cD mDg1D intercalado com mDg2D Note que a mensagem também deve ser escrita em termos de operador atraso ou seja mD pois da mesma forma que em uma transformação de Fourier a convolução no domínio do tempo tornase multiplicação no domínio do atraso Na convenção adotada até agora o termo de mX mais cedo é o termo de mais alta ordem ou seja é aquele que corresponde ao primeiro bit a entrar no codificador Em termos de operador D o primeiro bit a entrar no codificador é aquele que corresponde ao termo de menor ordem que corresponde ao termo mais cedo Desta forma mX 1 X X 3 mD D3 D2 1 Por exemplo para a mensagem mD 1 D2 D 3 obtémse mDg1D 1 D2 D31 D D2 1 D D 5 mDg2D 1 D2 D31 D 2 1 D3 D4 D 5 mDg1D 1 1 D 0 D 2 0 D 3 0 D 4 D 5 mDg2D 1 0 D 0 D 2 D 3 D 4 D 5 c 11 10 00 01 01 11 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 58 525 DIAGRAMA DE ESTADOS Um codificador convolucional pertence a uma classe de dispositivos conhecidos como máquinas de estado finito que é o nome genérico para maquinas que tem memória dos sinais passados O termo finito referese ao fato de que existe apenas um número de estados único e finito que a máquina pode gerar Em um sentido amplo um estado consiste de uma pequena quantidade de informação que junto com a informação presente na entrada da máquina é capaz de determinar a saída Os estados fornecem algum conhecimento de eventos passados e o restrito conjunto de possíveis saídas no futuro Um estado futuro fica restringido por um estado passado Para um codificador convolucional com taxa 1n o estado atual representado pelo tampo ti é representado pelo conteúdo dos K 1 estágios mais a direita conforme mostrado na Figura 55 O estado representado pelo tempo ti 1 é o estado futuro O conhecimento do estado e da próxima entrada é necessário e suficiente para determinar a próxima saída Um codificador convolucional pode ser representado por seu diagrama de estados Como um exemplo o diagrama de estados apresentado na Figura 56 descreve o comportamento do codificador da Figura 55 O diagrama de estados do codificador pode ser obtido a partir da verificação de todas as possibilidades de transição entre os estados do codificador conforme mostrado na Tabela 55 Figura 55 Definição do estado atual ti e estado futuro ti 1 para um codificador com K 3 De acordo com a Figura 56a o estado 00 é representado por um círculo do qual partem duas transições Uma transição parte de um estado no tempo ti e alcança um estado no tempo ti 1 e é representada por uma seta Para que isso aconteça é necessário que esteja presente na entrada um bit mi que provoca uma saída c1c2 representado pela notação mic1c2 próximo a cada transição Conforme mostrado na Tabela 55 a partir do estado 00 podese permanecer nele se a entrada for 0 ou migrar para o estado 10 se a entrada for 1 Bit de entrada m c1 c2 Saída ti ti 1 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 59 Tabela 55 Construção do diagrama de estados para o codificador da Figura 55 Entrada mi Conteúdos dos registradores Estado em ti Estado em ti 1 Saída em ti c1 c2 Figura 0 000 00 00 00 1 100 00 10 11 56a 0 010 10 01 10 1 110 10 11 01 56b 0 011 11 01 01 1 111 11 11 10 56c 0 001 01 00 11 1 101 01 10 00 56d Figura 56 a b e c Construção do diagrama de estados de acordo com a Tabela 55 00 10 111 000 a 00 10 11 01 111 101 010 000 b 00 10 11 01 111 101 001 010 110 000 c 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 510 A Figura 56b apresenta as transições que partem do estado 10 De acordo com a Tabela 55 a partir do estado 10 podese migrar para o estado 01 se a entrada for 0 ou migrar para o estado 11 se a entrada for 1 Da mesma forma a Figuras 56c apresenta as transições que partem do estado 11 De acordo com a Tabela 55 se a entrada for 1 o próximo estado é o próprio estado 11 e se entrada for 0 ocorre uma transição para o estado 01 Finalmente na Figura 56d são apresentadas as transições que partem do estado 01 e alcançam os estados 10 e 00 se as entradas forem 1 e 0 respectivamente A Figura 56e apresenta o diagrama de estados completo Figura 56 d e e Construção do diagrama de estados de acordo com a Tabela 55 00 10 11 01 111 101 001 100 010 011 110 000 00 10 11 01 111 101 001 100 010 011 110 000 d e 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 511 526 DIAGRAMA DE ÁRVORE O diagrama de árvore acrescenta a dimensão de tempo ao diagrama de estado Ao contrário do diagrama de estado que não permite representar a história do tempo no diagrama de árvore a evolução das mudanças de estado e a resultado na saída é visível conforme mostrado na Figura 57 Figura 57 Diagrama de árvore para o codificador convolucional da Figura 55 00 11 10 01 11 00 01 10 11 00 01 10 00 11 10 01 11 00 01 10 11 00 01 10 11 00 01 10 11 00 0 1 00 00 00 00 10 10 00 10 01 11 01 11 01 11 10 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 512 No diagrama de árvore apresentado pela Figura 57 cada ramo vertical representa uma entrada Um ramo para cima representa uma entrada zero enquanto um ramo para baixo representa uma entrada um As saídas do codificador são as palavras binárias colocadas sobre os ramos horizontais Cada derivação da árvore ou nó representa um estado identificado pela palavra binária colocada na caixa de cada nó Assim para a mensagem m 1101 pode se verificar pelo trajeto representado pela linha mais espessa na Figura 57 que a seqüência de estados correspondentes aos quatro bits da mensagem é 00 10 01 10 As saídas correspondentes a esta trajetória são 11 10 10 01 Note que cada nó representa o instante de tempo em que um estado é atingido Por isso este diagrama permite a obtenção de um histórico de transições ao longo do tempo 527 DIAGRAMA DE TRELIÇA Uma observação da Figura 57 permite concluir que a partir de um determinado instante de tempo a estrutura do diagrama tornase repetitivo Além disso para uma observação muitos intervalos de tempo o diagrama de árvore tornase pouco prático em função do grande número de ramos do diagrama Uma alternativa mais prática ao diagrama de árvore é o diagrama de treliça No diagrama de treliça temse um histórico de entradas transições e saídas sem que o diagrama cresça demasiadamente A Figura 58 apresenta o diagrama de treliça para o codificador da Figura 55 Neste diagrama os estados são representados pelos níveis horizontais e as entradas e saídas são representadas pela mesma convenção utilizada no diagrama de estados ou seja miu1u2 que são colocados sobre cada braço da treliça que por sua vez representa uma transição A mensagem m 1101 estabelece no diagrama de treliça a trajetória mostrada na Figura 59 resultando como era de se esperar nas saídas 11 10 10 01 Note que para esvaziar os registradores do codificador mais dois zeros na entrada são necessários resultando em uma saída complementar igual a 01 11 Assim a seqüência de saída completa para a mensagem m 1101 tornase 11 10 00 01 01 11 Este resultado é rigorosamente igual aos resultados apresentados anteriormente Figura 58 Diagrama de treliça para o codificador convolucional da Figura 55 00 10 01 11 000 111 010 110 101 001 011 100 101 010 010 010 011 011 011 110 110 110 001 101 001 101 001 101 100 100 100 111 111 111 111 111 000 000 000 000 000 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 513 Figura 59 Trajetória para a mensagem m 1101 53 DECODIFICAÇÃO DE CÓDIGOS CONVOLUCIONAIS PELO ALGORITMO DE VITERBI 1 2 3 O algoritmo de Viterbi é um algoritmo de máxima verossimilhança com baixa carga computacional em função da utilização da estrutura dos diagramas de treliça dos códigos convolucionais A vantagem da decodificação de Viterbi comparado com a decodificação por força bruta é que a complexidade de um decodificador não é função do número de símbolos da seqüência código mas função de uma medida de similaridade ou distância entre o sinal recebido em um tempo ti e todos os braços da treliça que entram em cada estado no tempo ti Quando dois braços entram no mesmo estado em um tempo ti o que possuir melhor métrica ou maior semelhança com o sinal recebido é escolhido e chamado de caminho sobrevivente Existem basicamente duas distâncias que podem ser utilizadas no algoritmo de Viterbi para a medida de similaridade entre a seqüência recebida pelo decodificador e as seqüências possíveis sobre a treliça a distância de Hamming e a distância Euclidiana A distância de Hamming é utilizada em um processo de decisão chamado de decisão abrupta hard decision enquanto a distância Euclidiana ou um parâmetro derivado dela é utilizado em um processo de decisão chamado de decisão suave soft decision A decisão abrupta destacase pela simplicidade e baixa carga computacional enquanto que a decisão suave requer uma carga computacional maior em troca de melhor desempenho em termos de capacidade de correção de erros As subseções apresentadas a seguir descrevem os dois processos de decodificação 531 DECODIFICAÇÃO ABRUPTA PELO ALGORITMO DE VITERBI Para facilitar o entendimento do algoritmo de Viterbi considere a seqüência recebida 11 10 10 01 01 11 codificada pelo codificador da Figura 55 cujo diagrama de treliça está apresentado na Figura 58 Note que foi introduzido um erro no terceiro par de bits 00 10 01 11 111 010 100 011 101 001 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 514 Passo 1 Partindo do estado 00 comparase a distância de Hamming do primeiro par de bits da seqüência código 11 com as distâncias de Hamming das duas transições possíveis a partir do estado 00 As distâncias de Hamming obtidas são armazenadas valores entre parênteses conforme apresentado na Figura 510a Passo 2 A distância de Hamming do próximo par de bits da seqüência código 10 é comparada com as distâncias de Hamming das transições possíveis a partir dos estados alcançados após o passo anterior As distâncias de Hamming encontradas são somadas àquelas obtidas nas transições anteriores Veja Figura 510b Figura 510a Situação após o passo 1 do exemplo de decodificação Figura 510b Situação após o Passo 2 do exemplo de decodificação 00 10 01 11 000 111 2 0 recebidos 11 00 10 01 11 000 111 2 0 3 000 111 3 010 101 0 2 recebidos 11 10 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 515 Passo 3 O mesmo procedimento apresentado no Passo 2 é repetido para o próximo par da seqüência código 10 Note que neste terceiro passo alguns dos estados são alcançados por dois caminhos diferentes O caminho sobrevivente deve ser aquele que apresenta a menor distância de Hamming acumulada Na Figura 510c os caminhos sobreviventes estão representados por uma linha mais espessa Figura 510c Situação após o Passo 3 do exemplo de decodificação Passo 4 O mesmo procedimento é repetido até o final da seqüência Para cada par do sinal recebido devese inspecionar a treliça e eleger o caminho sobrevivente As Figuras 510d e e f apresentam a evolução da treliça mostrando apenas os caminhos sobreviventes Note que ao final da seqüência código recebida apenas um caminho é o caminho sobrevivente final 00 10 01 11 000 111 2 0 3 000 111 3 010 101 0 2 4 000 111 1 010 101 3 5 011 4 001 110 100 1 4 2 recebidos 11 10 10 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 516 Figura 510d Situação após a análise do 4o par de bits recebidos do exemplo de decodificação Figura 510e Situação após a análise do 5o par de bits recebidos do exemplo de decodificação 00 10 01 11 111 0 010 101 0 2 1 011 110 2 000 2 1 111 101 1 2 recebidos 11 10 10 01 100 2 001 00 10 01 11 111 0 010 101 0 2 1 011 110 2 000 2 1 111 101 1 2 recebidos 11 10 10 01 01 100 2 001 000 3 3 111 100 011 3 3 101 2 001 1 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 517 Figura 510f Situação após a análise do 6o par de bits recebidos do exemplo de decodificação Conclusão Após a análise do último par de bits recebidos o caminho sobrevivente aponta uma distância de Hamming acumulada igual a 1 Este resultado mostra que a seqüência decodificada com maior probabilidade de ter sido a seqüência transmitida é a seqüência 11 10 00 01 01 11 correspondente a mensagem m 101100 Neste caso a seqüência recebida apresenta um erro em relação à seqüência decodificada correspondente à distância de Hamming acumulada igual a 1 Note que no exemplo apresentado a seqüência analisada é curta e o resultado da decodificação tornase óbvio Entretanto quando a seqüência recebida é extremamente longa o uso do algoritmo de Viterbi requer a utilização de uma quantidade de memória muito alta A abordagem usualmente usada é truncar a seqüência decodificada conforme os passos descritos a seguir 1 Uma janela de decodificação de comprimento l é especificada 2 O algoritmo opera sobre um quadro correspondente ao comprimento l parando sempre após l intervalos de tempo 3 A decisão é tomada sobre o melhor caminho e o símbolo associado com o primeiro ramo do caminho é liberado para o usuário 4 O símbolo associado com o último ramo do caminho é desconsiderado 5 A janela de decodificação é movida um intervalo de tempo para frente e a decisão sobre o melhor caminho sobre o novo quadro é feita e assim por diante A decisão de decodificação feita dessa maneira não é verdadeiramente máxima verossimilhança mas ela pode ser feita quase tão boa desde que a janela de decodificação seja suficientemente grande Experiência e análises têm demonstrado que resultados satisfatórios são obtidos se a janela de decodificação tem comprimento l da ordem de cinco vezes ou mais do que a extensão de influência K do código convolucional 00 10 01 11 111 0 010 0 1 101 1 recebidos 11 10 10 01 01 11 100 001 1 011 1 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 518 532 DECODIFICAÇÃO SUAVE PELO ALGORITMO DE VITERBI A decodificação com o algoritmo de Viterbi apresentada anteriormente tem por finalidade encontrar a seqüência código ou seqüência válida que mais se assemelha à seqüência binária recebida Isso é feito por meio do cálculo da distância de Hamming acumulada em todos os caminhos possíveis da treliça de forma que através da eleição dos caminhos sobreviventes seja possível a determinação do caminho sobrevivente final que é aquele que apresenta maior verossimilhança com a seqüência recebida Portanto o parâmetro utilizado para a eleição dos caminhos sobreviventes é a distância de Hamming Isso pressupõe que os símbolos recebidos foram determinados previamente por um processo de decisão de máxima verossimilhança onde os símbolos recebidos no espaço de sinais são aproximados para os símbolos mais próximos ou seja o parâmetro utilizado neste processo de decisão é a distância Euclidiana Neste caso verificase que o processo de decisão e o processo de decodificação são dois processos realizados independentemente Esta decodificação é chamada de decodificação abrupta harddecision A seguir será apresentado o processo de decodificação suave onde a decisão dos símbolos recebidos leva em conta simultaneamente a distância Euclidiana e o código corretor de erro utilizado ou seja o processo de decisão por meio de distâncias Euclidianas e a decodificação com o algoritmo de Viterbi são fundidos em um único processo Para isso considere o esquema de codificação e modulação apresentado na Figura 511 Figura 511 Exemplo de um esquema de modulação e codificação a decodificação suave Admita que a constelação recebida na ausência de ruído tenha seus simbolos posicionados no espaço de sinais de acordo com as coordenadas apresentadas na Figura 512 Figura 512 Coordenadas dos símbolos de modulação no espaço de sinais Codificador Convolucional Rc ½ g1 111 g2 101 00 01 11 10 Modulador QPSK Símbolos da modulação Seqüência binária 1 1 1 1 00 01 11 10 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 519 Na decisão por máxima verossimilhança um ponto recebido contaminado por ruído é decidido como sendo o símbolo mais próximo do espaço de sinais Ou seja decidese pelo símbolo que apresenta a menor distância Euclidiana para o ponto recebido A distância Euclidiana Ei de um ponto recebido para um símbolo Si de uma constelação pode ser calculada em função de suas coordenadas ortogonais pela expressão 2 2 q q i i E i i i 51 onde ii é a coordenada do símbolo i no eixo I i é a coordenada do ponto recebido no eixo I qi é a coordenada do símbolo i no eixo Q e q é a coordenada do ponto recebido no eixo Q conforme mostrado na Figura 513 Figura 513 Distância Euclidiana E0 de um ponto recebido para o símbolo S0 Para a modulação em questão os símbolos seus valores binários e suas coordenadas são mostrados na Tabela 56 Tabela 56 Símbolos seus valores binários e suas coordenadas Símbolo Valor binário Coordenadas ii qi S0 00 1 1 S1 01 1 1 S3 11 1 1 S2 10 1 1 1 1 1 1 S0 S1 S3 S2 i q I Q i0 q0 E0 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 520 Suponha agora que seis pontos tenham sido transmitidos através de um canal ruidoso de acordo com o esquema de codificação e modulação apresentado na Figura 511 Admita que no receptor tenham chegado seis pontos com as seguintes coordenadas r1 093 003 r2 055 011 r3 035 113 r4 097 002 r5 020 042 r6 041 025 Em um processo de decisão abrupta os pontos recebidos são aproximados para o símbolo da constelação mais próximo resultando na seqüência S3 S0 S0 S3 S0 S3 que correspondem aos valores binários 11 00 00 11 00 11 Esta seqüência binária quando decodificada de acordo com o algoritmo de Viterbi resulta na treliça mostrada na Figura 4 Figura 514 Caminhos sobreviventes correspondentes à decodificação abrupta da seqüência de pontos r1 r2 r6 De acordo com o resultado apresentado na Figura 514 observase que existem duas possibilidades para o caminho sobrevivente final que são 00 00 00 11 10 11 ou 11 10 00 01 01 11 Desde que a capacidade de correção de erros do código não tenha sido excedida pelo número de erros introduzido pelo canal então uma das duas seqüências é a seqüência transmitida Note que neste caso a chance de se eleger a seqüência de máxima verossimilhança é de 50 00 10 01 11 000 111 010 110 101 001 011 100 101 010 010 010 011 011 011 110 110 110 001 101 001 101 001 101 100 100 100 111 111 111 111 111 000 000 000 000 000 2 0 2 4 1 1 2 3 4 1 5 2 5 2 2 2 2 4 4 3 2 3 6 4 4 2 3 3 3 3 010 8 3 6 5 3 4 3 4 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 521 O algoritmo de Viterbi para a decodificação suave é o mesmo utilizado para a decodificação abrupta Entretanto no processo de decodificação suave as distâncias acumuladas ao longo da treliça não são as distâncias de Hamming e sim as distâncias Euclidianas dos pontos recebidos em relação aos símbolos representados por cada braço da treliça Desta forma na decodificação suave cada braço da treliça deve ser identificado com o par de coordenadas do símbolo obtido na saída do codificador de acordo com as correspondências entre coordenadas e valores binários apresentados na Tabela 56 A partir do exposto acima podese redesenhar a treliça para a decodificação suave da forma como mostrada na Figura 515 Figura 515 Treliça para a decodificação suave O início da decodificação suave consiste na determinação da distância do ponto recebido para os símbolos das transições que saem do estado 00 ou seja os ramos cujos símbolos estão nas coordenadas 1 1 e 1 1 A partir dos estados alcançados calculamse novamente as distâncias para os estados seguintes acumulandoas com as anteriores e assim por diante conforme mostrado a seguir De r1 093 003 para S0 1 1 2 2 0 0 03 1 0 93 1 E E0 2188 S3 1 1 2 2 3 0 03 1 0 93 1 E E3 0973 00 00 2188 2188 0 00 10 0 973 0 973 0 00 10 01 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 522 De r2 055 011 para S0 1 1 2 2 0 011 1 0 55 1 E E0 0997 S3 1 1 2 2 3 011 1 0 55 1 E E3 1906 S2 1 1 2 2 2 011 1 0 55 1 E E2 1198 S1 1 1 2 2 1 011 1 0 55 1 E E1 1787 00 00 3185 0 997 2188 00 10 4 094 1906 2188 10 01 2171 1198 0 973 2 760 1 787 0 973 10 11 00 10 01 11 1 1 1 1 2188 0973 3185 4094 2171 2760 1 1 1 1 1 1 1 1 00 10 01 11 1 1 1 1 2188 0973 0 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 523 De r3 035 113 para S0 1 1 2 2 0 113 1 0 35 1 E E0 0663 S3 1 1 2 2 3 113 1 0 35 1 E E3 2522 S2 1 1 2 2 2 113 1 0 35 1 E E2 2227 S1 1 1 2 2 1 113 1 0 35 1 E E1 1356 00 00 3 848 0 663 3185 01 10 2 834 0 663 2171 00 10 5 707 2 522 3185 01 00 4 693 2 522 2171 10 01 6 321 2 227 4 094 11 11 4 987 2 227 2 760 10 11 5 450 1356 4 094 11 01 4116 1356 2 760 A partir desta etapa devese eleger os caminhos sobreviventes para a etapa seguinte De r4 097 002 para S0 1 1 2 2 0 0 02 1 0 97 1 E E0 2218 S3 1 1 2 2 3 0 02 1 0 97 1 E E3 0980 S2 1 1 2 2 2 0 02 1 0 97 1 E E2 2200 S1 1 1 2 2 1 0 02 1 0 97 1 E E1 1020 00 10 01 11 1 1 1 1 2188 0973 3185 4094 2171 2760 1 1 1 1 1 1 1 1 3848 5707 6321 5450 2834 4693 4987 4116 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 524 00 00 6 066 2 218 3 848 01 10 6 334 2 218 4116 00 10 4 828 0 980 3 848 01 00 5 096 0 980 4116 10 01 5 034 2 200 2 834 11 11 7 187 2 200 4 987 10 11 3 854 1 020 2 834 11 01 6 007 1 020 4 987 De r5 020 042 para S0 1 1 2 2 0 0 42 1 0 20 1 E E0 0988 S3 1 1 2 2 3 0 42 1 0 20 1 E E3 1859 S2 1 1 2 2 2 0 42 1 0 20 1 E E2 1630 S1 1 1 2 2 1 0 42 1 0 20 1 E E1 1333 00 00 6 084 0 988 5 096 01 10 6 022 0 988 5 034 00 10 6 955 1859 5 096 01 00 6 893 1859 5 034 10 01 6 458 1 630 4 828 11 11 5 484 1 630 3 854 10 11 6161 1333 4 828 11 01 5187 1333 3 854 00 10 01 11 1 1 1 1 2188 0973 3185 2171 2760 1 1 1 1 1 1 3848 2834 4987 4116 1 1 1 1 1 1 1 1 1 1 1 1 6066 1 1 1 1 1 1 1 1 1 1 1 1 4828 5034 3854 6334 5096 6007 7187 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 525 De r6 041 025 para S0 1 1 2 2 0 0 25 1 0 41 1 E E0 1884 S3 1 1 2 2 3 0 25 1 0 41 1 E E3 0954 S2 1 1 2 2 2 0 25 1 0 41 1 E E2 1597 S1 1 1 2 2 1 0 25 1 0 41 1 E E1 1382 00 00 7 968 1884 6 084 01 10 7 071 1884 5187 00 10 7 038 0 954 6 084 01 00 6141 0 954 5187 10 01 7 619 1597 6 022 11 11 7 081 1597 5 484 10 11 7 404 1382 6 022 11 01 6 866 1382 5 484 00 10 01 11 1 1 1 1 2188 0973 3185 2171 2760 1 1 1 1 1 1 3848 2834 4116 1 1 1 1 1 1 1 1 1 1 1 1 1 1 4828 5034 3854 5096 1 1 6084 1 1 6955 1 1 6458 6161 1 1 1 1 6893 6022 1 1 5187 1 1 5484 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 526 Que resulta nos seguintes caminhos sobreviventes Como não há mais pontos a serem decodificados e existe um dos caminhos sobreviventes que retorna ao estado 00 com a menor distância Euclidiana acumulada podese concluir que este é o caminho de máxima verossimilhança entre os sobreviventes conforme mostrado a seguir 00 10 01 11 1 1 0973 2171 2760 1 1 1 1 2834 4116 1 1 1 1 1 1 1 1 3854 5096 1 1 6084 1 1 5187 1 1 5484 7038 1 1 1 1 6141 6866 1 1 7081 1 1 00 10 01 11 1 1 0973 2171 2760 1 1 1 1 2834 4116 1 1 1 1 1 1 1 1 1 1 5034 3854 5096 1 1 6084 1 1 6022 1 1 5187 1 1 5484 1 1 7968 7038 1 1 7619 7404 1 1 1 1 1 1 6141 7071 6866 1 1 1 1 7081 1 1 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 527 As coordenadas do caminho de máxima verossimilhança indicam os seguintes pares binários decodificados 11 10 00 01 01 11 É importante salientar que a distância Euclidiana não é o único parâmetro utilizado na decodificação suave O exemplo apresentado é apenas uma das forma de decodificação suave Qualquer parâmetro que mantenha a proporcionalidade entre as distâncias do símbolo recebido para os símbolos da constelação pode ser utilizado na decodificação suave 54 CAPACIDADE DE CORREÇÃO DE ERROS DOS CÓDIGOS CONVOLUCIONAIS 1 2 O desempenho de um código convolucional depende do algoritmo de decodificação e das propriedades de distância do código Neste aspecto a principal característica de um código convolucional é a distância livre denotada por dfree A distância livre de um código convolucional é definida como a distância de Hamming entre duas palavras códigos A distância livre pode ser obtida de forma bastante simples a partir do diagrama de estados do codificador convolucional Considere o diagrama de estados da Figura 56 Qualquer seqüência código não zero corresponde a um caminho que começa e termina no estado 00 Podese dividir o estado 00 em dois de modo a permitir que o diagrama de estado possa ser transformado em um grafo de fluxo de sinal com uma única entrada e uma única saída conforme mostrado na Figura 516 Um grafo de fluxo de sinal consiste de nós e ramos e opera segundo as seguintes regras 1 Um ramo multiplica o sinal em seu nó de entrada pela função que caracteriza cada ramo 2 Um nó com ramos de chegada somam os sinais produzidos por todos aqueles ramos 3 O sinal em cada nó é aplicado igualmente à todos os ramos de saída daquele nó 4 A função de transferência do grafo é a relação entre o sinal de saída e o sinal de entrada 00 10 01 11 1 1 0973 2171 1 1 2834 1 1 1 1 3854 1 1 5187 6141 1 1 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 528 Figura 516 Diagrama de estado modificado Retornando à Figura 516 note que o expoente de D sobre cada ramo do grafo corresponde ao peso de Hamming da saída correspondente ao ramo O expoente de L é sempre igual a um uma vez que o comprimento de cada ramo é igual a um Considere que TD L representa a função de transferência do grafo de fluxo de sinal com D e L fazendo o papel de variável fantasma Segundo as regras 1 2 e 3 apresentadas acima para o grafo da Figura 516 podese obter as seguintes relações entradasaída D Lc a DLd DLb d DLd DLb c Lc D La b 2 1 0 2 52 onde a0 b c d e a1 são os sinais do nó do grafo Resolvendo o conjunto de Equações 52 para a relação a1a0 encontrase a função de transferência do grafo dada por 1 1 3 5 L DL D L T d L 53 Usando a expansão binomial 53 tornase 0 5 3 1 i L i DL D L T d L 54 Fazendo L 1 obtémse a função de transferência da distância na forma de uma série de potência como a1 b d c L DL a0 D2L D2L DL DL DL 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 529 L 7 6 5 4 2 D D D T d L 55 Uma vez que a distância livre é a mínima distância de Hamming entre duas palavras código quaisquer e a função de transferência TD 1 enumera o número de palavras códigos que possuem uma dada distância umas da outras concluise que o expoente do primeiro termo na expansão de TD 1 define a distância livre Conseqüentemente o código convolucional correspondente ao diagrama de estados apresentado na Figura 26 tem distância livre dfree 5 Um código convolucional com distância livre igual a dfree pode corrigir t erros de acordo com a relação 2 1 d free t 56 Podese concluir que a capacidade de correção de um código cuja dfree 5 é igual a dois ou talvez três erros Essa conclusão entretanto leva a uma questão importante para que comprimento da seqüência recebida podese corrigir dois ou talvez três erros Infelizmente não existe uma resposta exata para essa questão já que a capacidade de correção está associada à forma como os erros estão distribuídos na seqüência mais próximos ou mais afastados uns dos outros Mais uma vez podese dizer que observações permitem concluir que a capacidade de correção de t erros ocorre geralmente dentro de algumas extensões de influência K onde algumas aqui significa 3 a 5 Logo voltando ao código em questão em que k 3 podese dizer então que 2 ou 3 erros podem ser corrigidos em uma seqüência recebida cujo comprimento pode variar de 9 a 15 bits dependendo da distribuição dos erros na seqüência 55 CÓDIGOS CONVOLUCIONAIS CATASTRÓFICOS 1 2 Quando se usa a função de transferência TD 1 para a determinação da distância livre fica implícito que a série de potência que a representa é convergente ie a soma possui um valor finito No caso do exemplo apresentado podese demonstrar que para o codificador em questão a série é de fato convergente Entretanto para outros codificadores convolucionais não existe nenhuma garantia de que TD 1 é sempre convergente Quando TD 1 é não convergente um número finito de erros introduzidos na transmissão provoca uma seqüência infinita de erros de decodificação Isso significa uma propagação catastrófica de erros e neste caso o código é chamado de um código catastrófico A condição para a propagação catastrófica de erros está nos codificadores em que os polinômios geradores possuem um polinômio fator comum de grau 1 pelo menos Como exemplo considere o codificador apresentado na Figura 517 cujo diagrama de estados modificado é apresentado na Figura 518 Este codificador apresenta os seguintes polinômios geradores g1D 1 D g2D 1 D2 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 530 Ambos os polinômios possuem um polinômio fator comum que é 1 D pois 1 D2 1 D1 D Figura 517 Codificador convolucional catastrófico Figura 518 Diagrama de estado modificado para o codificador da Figura 517 Em termos de diagrama de estados para códigos com qualquer taxa erros catastróficos podem ocorrer se e somente se todos os laços fechados do diagrama possuem peso zero Bit de entrada m c1 c2 Saída a1 b d c DL DL a0 D2L DL L DL D2L 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 531 56 CÓDIGOS CONVOLUCIONAIS SISTEMÁTICOS 12 Uma garantia de que um código convolucional é nãocatastrófico se dá quando o codificador gera um código convolucional sistemático Um exemplo de codificador sistemático está mostrado na Figura 519 Figura 519 Codificador convolucional sistemático Infelizmente para códigos com a mesma extensão de influência K e mesma taxa os valores de distância livre obtidos são geralmente menores do que aqueles obtidos pelos códigos convolucionais nãosistemáticos como mostra a Tabela 57 Tabela 57 Máximas distâncias livres obtidas com códigos convolucionais sistemáticos e nãosistemáticos de taxa 12 Extensão de influência K Sistemático Nãosistemático 2 3 3 3 4 5 4 4 6 5 5 7 6 6 8 7 6 10 8 7 10 Entretanto é importante ressaltar que apenas uma pequena fração dos códigos não sistemáticos excluindo aqueles onde todos os somadores possuem um número par de conexões são catastróficos c1 c2 Saída Bit de entrada m 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 532 57 MELHORES CÓDIGOS CONVOLUCIONAIS CONHECIDOS 1 Conforme apresentado códigos convolucionais devem apresentar boas características de distância livre para uma dada taxa de codificação e extensão de influência K Uma lista dos melhores códigos convolucionais de taxa 12 K 3 até 9 e taxa 13 K 3 até 8 são apresentados na Tabela 58 e 59 respectivamente Tabela 58 Códigos convolucionais de taxa 12 K 3 até 9 Taxa Extensão de influência K Distância livre Vetores conexão 3 5 111 101 4 6 1111 1011 5 7 10111 11001 6 8 101111 110101 7 10 1001111 1101101 8 10 10011111 11100101 12 9 12 110101111 100011101 Tabela 59 Códigos convolucionais de taxa 13 K 3 até 9 Taxa Extensão de influência K Distância livre Vetores conexão 3 8 111 111 101 4 10 1111 1011 1101 5 12 11111 11011 10101 6 13 101110 110101 111001 7 15 1001111 1010111 1101101 13 8 16 11101111 10011011 10101001 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 533 00 10 11 01 1111 1010 0010 1000 0101 0111 1101 0000 57 EXERCÍCIOS 1 Considere o codificador convolucional representado pelos vetores conexão 1101 e 1111 Pedese a Codificar a mensagem 10101 b Determinar o seu diagrama de estados c Determinar a capacidade de correção de erros deste código 2 Considere o diagrama de estados de um codificador convolucional apresentado abaixo a Desenhe o codificador b Determine a capacidade de correção de erros deste código c Codifique a mensagem 10101 d Decodifique a seqüência recebida 101001000110101010101 utilizando o algoritmo de Viterbi 3 Considere o esquema de codificação e de modulação apresentado na Figura 511 Admita que os seguintes pares de coordenadas tenham sido recebidos 092 089 071 012 013 002 001 011 095 085 e 088 099 Admita ainda que o processo de codificação foi iniciado no estado 00 e terminou no estado 00 Fazendo uso do algoritmo de Viterbi pedese a A decisão e decodificação abrupta da seqüência recebida b A decodificação suave da seqüência recebida c Comparar os dois resultados escolher a seqüência decodificada e justificar a escolha 5 Códigos Convolucionais 5ConvolucionalV2011 Geraldo Gil R Gomes 534 58 REFERÊNCIAS BIBLIOGRÁFICAS 1 SKLAR Bernard Channel coding In Digital communications fundamentals and applications 2 ed Upper Saddle River New Jersey Prentice Hall 2001 p 304429 ISBN 0130847887 2 HAYKIN Simon Error control coding In Systems communications 4 ed New York John Wiley Sons 2001 p 626696 ISBN 0471178691 3 LIN S COSTELLO D J Error control coding fundamentals and applications Englewood Cliffs New Jersey Prentice Hall 1983 ISBN 013283796X