Michelle Foltran Miranda CÓdigos corretores de erro e turbo code curitiba


Propriedades Estruturais dos Códigos Convolucionais



Baixar 248.2 Kb.
Página7/10
Encontro29.07.2016
Tamanho248.2 Kb.
1   2   3   4   5   6   7   8   9   10

Propriedades Estruturais dos Códigos Convolucionais

Como um codificador convolucional é um circuito seqüencial, sua operação pode ser descrita por um diagrama de estado. O estado do codificador é definido por seus registradores de deslocamento. Para um código (n,k,m) com k > 1, o i-ésimo registrador contém Ki bits de informações anteriores.

Definindo a memória total do codificador como na equação (65) abaixo, o estado do codificador na unidade de tempo l á a K-tupla binária de entradas (ul-1(1) ul-2(1)... ulk1(1) ul-1(2) ul-2(2)... ul-k1(2) ... ul-1(k) ul-2(k)... ul-k1(k)) e existe um total de 2k diferentes estados possíveis. Deve-se notar a diferença entre o total de memória do codificador K e a ordem de memória m. K é a soma de todos os comprimentos dos registradores de deslocamento, enquanto que m é o comprimento máximo de qualquer registrador de deslocamento.
(65)
Cada novo bloco de k entradas causa uma transição para um novo estado. Dessa forma, existem 2k blocos de saída em cada estado, cada um correspondendo a cada bloco de entrada. Cada tronco é nomeado com k entradas causando transições e seqüências de saída. O diagrama de estados para o código (2,1,3) está mostrado na figura 3.


Figura 3: Diagrama de estados do código (2,1,3)

    1. Decodificação de Máxima Verossimilhança dos Códigos Convolucionais

Em 1967, Viterbi introduziu um algoritmo de decodificação para códigos convolucionais que desde então tornou-se conhecido como algoritmo de Viterbi. Mais tarde, Omura mostrou que o algortmo de Viterbi era equivalente a uma solução dinâmica programável para o problema de descobrir o caminho mais curto através de um gráfico ponderado. Finalmente, Forney, reconheceu que esse algoritmo era, de fato, um algoritmo de decodificação de máxima verossimilhança para os códigos convolucionais, ou seja, a saída selecionada pelo decodificador é sempre a palavra-código que fornece o maior valor da função log de verossimilhança.



      1. O algoritmo de Viterbi

A fim de se entender o algoritmo de Viterbi, deve-se expandir o diagrama de estados de codificador no tempo, ou seja, representar cada unidade de tempo como um diagrama de estado separado. A estrutura resultante é chamada diagrama em treliça.

O diagrama em treliça contém L + m + 1 unidades de tempo ou níveis e eles são nomeados de 0 a L+m. Assumindo que o codificador sempre inicia no estado S0 e retorna ao estado S0, a primeira unidade de tempo m corresponde à saída do codificador do estado S0, e as últimas m unidades de tempo correspondentes ao codificador retornam ao estado S0. Nem todos os estados podem ser alcançados podem ser alcançados nas primeiras m ou últimas m unidades de tempo. Todavia, em uma porção central da treliça, todos os estados são possíveis e cada unidade do tempo contém uma réplica do diagrama de estados. Existem dois troncos saindo e entrado em cada estágio. O tronco superior saindo de cada estado na unidade de tempo i representa a entrada ui=1, enquanto que o tronco inferior representa ui=0. Cada tronco é nomeado com as n saídas vi correspondentes e cada uma das 2L palavras-código de comprimento N = n(L+m) é representada por um único caminho através da treliça.

Para o caso geral de um código (n,k,m) e uma seqüência de informação de comprimento kL, haverá 2k troncos saindo e entrando em cada estado e 2kL caminhos distintos ao longo da treliça correspondendo às 2kL palavras do código.

Assume-se agora que uma seqüência de informação u de comprimento kL é codificada em uma palavra código v de comprimento N = n(L + m) e que uma seqüência Q-nária r é recebida como uma entrada binária, saída Q-nária de um canal discreto sem memória (DMC).

O decodificador deve produzir uma estimativa da palavra código v baseada na seqüência recebida r. Um decodificador de máxima verossimilhança (MLD) para um DMC escolhe como a palavra-código v a qual maximiza a função log de verossimilhança log P(r | v). Portanto, para um DMC:


(66)
Dessa forma:
(67)
Nas equações (66) e (67), P(ri | vi) é a probabilidade de transição de canal.

A função log de verossimilhança log P(r | v) é chamada métrica associada ao caminho v e é denotada por M(r | v). Os termos log P(ri | vi) no somatório da equação (67) são chamados métricas dos troncos e são denotados por M(ri | vi), onde os termos log P(ri | vi) são as métricas dos bits e são denotadas por M(ri | vi). Portanto, a métrica do caminho M(r | v) pode ser escrita como na equação (68):


(68)
O seguinte algoritmo, quando aplicado à seqüência receptora r de um DMC encontra o caminho através da treliça com a maior métrica, ou seja, o caminho da máxima verossimilhança. Esse algoritmo processa r de maneira iterativa. A cada passo, ele compara as métricas de todos os caminhos entrando em cada estado e armazena o caminho com a maior métrica, chamado de sobrevivente, juntamente com sua métrica.

Pode-se resumir o algoritmo de Viterbi em três passos:



  • Passo 1: Começando na unidade de tempo j = m, computar a métrica parcial para o único caminho entrando em cada estado. Armazer o caminho (o sobrevivente) e sua métrica para cada estado.

  • Passo 2: Incrementar j de 1 unidade. Computar a métrica parcial para todos os caminhos entrando em um estado adicionando a métrica do tronco que entra nesse estado à métrica do sobrevivente na unidade de tempo precedente. Para cada estado, armazenar o caminho com a maior métrica (o sobrevivente), junto com sua métrica e eliminar todos os demais caminhos.

  • Passo 3: Se j< L + m, repetir o passo 2. Caso contrário, parar o processo.

Existem 2k sobreviventes da unidade de tempo m através da unidade de tempo L, um para cada um dos 2k estados. Após a unidade de tempo L, existem poucos sobreviventes, uma vez que existem poucos estados enquanto o codificador está retornando ao estado completamente nulo. Finalmente, na unidade de tempo L + m, existe somente um estado, o estado completamente nulo e, portanto, somente um sobrevivente e o algoritmo termina. O sobrevivente final é o caminho de máxima verossimilhança.




  1. Catálogo: edu
    edu -> Advocacia Previdenciária Dra. Mª Cecília Melo Trópia Dra. Marcella Souza França
    edu -> Fundamentos neurolingüÍsticos: contribuições à Fonoaudiologia
    edu -> A música na educaçÃo infantil e sua contribuiçÃo para o desenvolvimento infantil
    edu -> EducaçÃO À distância: uma contribuição na formação pessoal e profissional dos usuários
    edu -> Universidade federal do estado do rio de janeiro unirio maria clara ligiero chehin
    edu -> Norma Silvia Trindade de Lima educaçÃo e psicodrama: possíveis práticas de singularizaçÃO?
    edu -> Projeto a inclusão do ensino da história africana
    edu -> Modelo de resumo de projeto
    edu -> Poder judiciário tribunal regional federal da 1ª regiãO
    edu -> Fitorremediação por Miscanthus X giganteus de solos contaminados com lamas residuais urbanas (lru’s) ricas em metais pesados


    Compartilhe com seus amigos:
1   2   3   4   5   6   7   8   9   10


©principo.org 2019
enviar mensagem

    Página principal