decodificação seqüencial - Sequential decoding

Decodificação seqüencial é uma técnica de memória limitada para decodificar códigos de árvores . Descodificação sequencial é utilizado principalmente como é um algoritmo de descodificação para aproximado longo restrição de comprimento códigos convolucionais . Esta abordagem pode não ser tão preciso quanto o algoritmo Viterbi , mas pode salvar uma quantidade substancial de memória do computador.

decodificação Sequential explora o código árvore de tal maneira para tentar minimizar os custos e requisitos de memória computacional para armazenar a árvore.

Há uma variedade de abordagens de decodificação sequenciais com base na escolha de métrica e algoritmo. Métricas incluem:

• Fano métrica
• Zigangirov métrica
• Gallager métrica

Algoritmos incluem:

• algoritmo de pilha
• algoritmo de Fano
• algoritmo Creeper

Fano métrica

Dada uma árvore parcialmente explorado (representado por um conjunto de nós que são limite de exploração), gostaríamos de saber a melhor nó para explorar ainda mais. A métrica Fano (em homenagem a Robert Fano ) permite calcular a partir do qual é o melhor nó para explorar mais. Esta métrica é o ideal dada há outras restrições (por exemplo, memória).

Para um canal simétrico binário (com probabilidade de erro ) a métrica Fano pode ser derivada através teorema de Bayes . Estamos interessados em seguir o caminho mais provável dado um estado explorado da árvore e uma sequência recebida . Usando a linguagem da probabilidade e teorema de Bayes queremos escolher o máximo sobre de: ${\ Displaystyle p}$${\ Displaystyle P_ {i}}$${\ Displaystyle X}$${\ Displaystyle {\ mathbf {r}}}$${\ Displaystyle i}$

${\ Displaystyle \ Pr (P_ {i} | X, {\ mathbf {r}}) \ propto \ Pr ({\ mathbf {r}} | P_ {i}, X) \ Pr (P_ {i} | X )}$

Vamos agora introduzir a seguinte notação:

• ${\ N} displaystyle$ para representar o comprimento máximo de transmissão em ramos
• ${\ Displaystyle b}$para representar o número de bits em uma filial do código (o denominador da taxa de código , ).${\ Displaystyle R}$
• ${\ Displaystyle d_ {i}}$para representar o número de erros de bit no caminho (a distância de Hamming entre as etiquetas de agências e a sequência recebida)${\ Displaystyle P_ {i}}$
• ${\ Displaystyle n_ {i}}$para ser o comprimento de ramos.${\ Displaystyle P_ {i}}$

Nós expressar a probabilidade como (usando a probabilidade canal simétrico binário para os primeiros bits de seguidos por um uniforme antes sobre os restantes bits). ${\ Displaystyle \ Pr ({\ mathbf {r}} | P_ {i}, X)}$${\ Displaystyle p ^ {d_ {i}} (1-p) ^ n_ {{i} b-d_ {i}} 2 ^ {- (N-n_ {i}) b}}$${\ Displaystyle n_ {i} b}$

Expressamos o anterior em termos do número de escolhas Ramo Um fez, e o número de agências de cada nó, . ${\ Displaystyle \ Pr (P_ {i} | X)}$${\ Displaystyle n_ {i}}$${\ Displaystyle 2 ^ {Rb}}$

Assim sendo:

${\ Displaystyle {\ begin {alinhados} \ Pr (P_ {i} | X, {\ mathbf {r}}) & \ propto p ^ {d_ {i}} (1-p) ^ {n_ {i} b -d_ {i}} 2 ^ {- (N-n_ {i}) b} 2 ^ - ^ Rb} \\ & \ propto p ^ {d_ {i}} (1-p) {{n_ {i} N_ {i} b-d_ {i}} 2 ^ n_ {{i} b} 2 ^ {- N_ {i} Rb} \ final {alinhados}}}$

Nós podemos equivalentemente maximizar o log dessa probabilidade, ou seja,

${\ Displaystyle {\ begin {alinhados} & d_ {i} \ log _ {2} p + (n_ {i} b-d_ {i}) \ log _ {2} (1-p) + n_ {i} b- N_ {i} Rb \\ = & d_ {i} (\ log _ {2} p + 1-R) + (n_ {i} b-d_ {i}) (\ log _ {2} (1-p) + 1-R) \ final {alinhados}}}$

Esta última expressão é a métrica Fano. O ponto importante para ver é que temos dois termos aqui: um baseado no número de bits errados e um com base no número de bits certas. Podemos, portanto, atualizar a métrica Fano simplesmente adicionando para cada bit de não-casamento e para cada bit correspondente. ${\ Displaystyle \ log _ {2} p + 1-R}$${\ Displaystyle \ log _ {2} (1-p) + 1-R}$

taxa de corte computacional

Para a descodificação sequencial a uma boa escolha de algoritmo de descodificação, o número de estados explorado quer permanecem pequenas (de outro modo um algoritmo que deliberadamente explora todos os estados, por exemplo, o algoritmo de Viterbi , pode ser mais adequado). Para um nível de ruído particular, existe uma taxa máxima de codificação chamada de taxa de corte computacional onde há um limite finito retrocesso. Para o canal simétrico binário: ${\ Displaystyle R_ {0}}$

${\ Displaystyle R_ {0} = 1- \ log _ {2} (1 + 2 {\ sqrt {p (1-p)}})}$

algoritmos

algoritmo de pilha

O algoritmo mais simples de descrever é o "algoritmo de pilha", na qual os melhores caminhos encontrados até agora são armazenados. Descodificação sequencial pode introduzir um erro adicional acima de Viterbi descodificação quando o caminho correcto tem ou mais altamente caminhos de pontuação acima dela; Neste ponto, o melhor caminho vai cair fora da pilha e ser deixou de ser considerado. ${\ N} displaystyle$${\ N} displaystyle$

algoritmo de Fano

O algoritmo Fano famoso (em homenagem a Robert Fano ) tem uma exigência de memória muito baixa e, portanto, é adequado para implementações de hardware. Este algoritmo explora para trás e para a frente a partir de um único ponto na árvore.

1. O algoritmo de Fano é um algoritmo de decodificação seqüencial que não requer uma pilha.
2. O algoritmo Fano só pode operar sobre uma árvore de código, pois não pode examinar caminho fusão.
3. Em cada fase de descodificação, o algoritmo de Fano retém a informação relativa três caminhos: o caminho da corrente, o seu caminho antecessor imediato, e um dos seus caminhos de sucessores.
4. Com base nesta informação, o algoritmo Fano pode mover-se do caminho atual, quer seu caminho antecessor imediato ou o caminho sucessor selecionada; Assim, não é necessário para a pilha filas todos os caminhos examinados.
5. O movimento do algoritmo Fano é guiado por um limiar T dinâmico que é um múltiplo inteiro de um ¢ tamanho de passo fixo.
6. Apenas o caminho cujo métrica caminho é nada menos do que T pode ser o próximo visitado. De acordo com o algoritmo, o processo de busca palavra-chave continua a avançar ao longo de um caminho de código, enquanto a métrica Fano ao longo do caminho de código permanece não-decrescente.
7. Uma vez que todas as métricas de caminho sucessor são menores do que T, o algoritmo se move para trás, para o caminho predecessor se a métrica caminho predecessor bate T; depois disso, o exame limite será posteriormente realizada em outro caminho sucessor deste predecessor revisitado.
8. No caso do caminho métrica antecessor é também a menos de T, o limiar T é um passo reduzidos, para que o algoritmo não está preso no caminho atual.
9. Para o algoritmo Fano, se um caminho é revisitado, o limiar dinâmica presentemente examinado é sempre inferior ao limiar dinâmica momentânea na visita anterior, garantindo que looping no algoritmo não ocorrer, e que o algoritmo pode finalmente chegar a um nó terminal a árvore de código, e stop.

Referências

• John Wozencraft e B. Reiffen, decodificação Sequential , ISBN  0-262-23006-2
• Rolf Johannesson e Kamil Sh. Zigangirov, Fundamentos da codificação convolucional (capítulo 6), ISBN  0-470-27683-5

links externos

• " Árvores de correção " - simulador de processo de correção usando fila de prioridade para escolher nó métrica máxima (chamado de peso)