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



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

Síndrome e Detecção de Erro

Considerando um código linear com matriz geradora G e matriz de checagem de paridade H. Seja v = (v0, v1, ..., vn-1) uma palavra-código que foi transmitida por um canal ruidoso. Seja r = (r0, r1, ..., rn-1) um vetor recebido na saída do canal. Devido ao ruído do canal, r pode ser diferente de v. O vetor soma e é uma n-tupla onde ei=1 para ri vi e ei = 0 para ri = vi. Essa n-tupla é chamada de vetor erro ou padrão de erro e está mostrada na equação (6).




(6)
Os bits 1 no vetor e são os erros de transmissão causados pelo ruído do canal. O vetor recebido r é a soma da palavra código transmitida e o vetor erro, ou seja, .

Recebendo a palavra r, o decodificador deve primeiramente determinar se o vetor r contém erros de transmissão ou não. Se a presença de erros for detectada, o decodificador deverá realizar ações para localizar e corrigir esses erros.

Quando o vetor r é recebido, o decodificador computa a seguinte (n-k)-tupla, a qual é chamada síndrome do vetor r. A síndrome é dada pela equação (7).


(7)
Dessa forma, s = 0 se e somente se r é uma palavra do código e s 0 se e somente se r não é palavra do código. Portanto, quando s 0, sabe-se que r não é uma palavra do código e a presença de erros pode ser detectada. Quando s =0, r é uma palavra código e o receptor aceita r como a palavra código transmitida. É possível que os erros em certos vetores de erro não sejam detectáveis, ou seja, r contém erros, mas s = 0. Isso ocorre quando o padrão de erro é idêntico a uma palavra do código. Padrões de erro desse tipo são chamados padrões de erro não-detectáveis.

    1. Arranjo Padrão e Decodificação por Síndrome

Será apresentado um esquema para decodificação de códigos de blocos lineares. Seja C um código linear (n,k). Sejam v1, v2, ..., v2k vetores códigos de C. Não importa qual vetor código é transmitido por um canal ruidoso, o vetor receptor r deve ser qualquer uma das 2n n-tuplas sobre GF(2).



Um método para particionar 2n vetores recebidos possíveis em 2k subconjuntos distintos tal que cada subconjunto contém um e somente um vetor código é descrito aqui. A partição é baseada na estrutura linear do código. Primeiramente, os 2k vetores códigos de C são substituídos em uma linha com o vetor código nulo v1 = (0, 0, ..., 0) como primeiro elemento. Para as demais 2n – 2k n-tuplas, uma n-tupla e2 é escolhida e inserida abaixo do vetor v1. Em seguida, forma-se uma segunda linha adicionando-se e2 à cada vetor código vi. Com a segunda linha completa, é escolhida uma n-tupla e3 entre as n-tuplas restantes. Então, uma terceira linha é formada adicionando-se e3 a cada vetor código vi na primeira linha. Esse processo é realizado até que todas as n-tuplas são usadas. Assim, tem-se um arranjo de linhas e colunas como mostrado na figura 2. Esse arranjo é chamado de arranjo padrão de um determinado código linear C.



v1 = 0

v2

...

vi

...

v2k

e2

e2 + v2



e2 + vi



e2 + v2k

e3

e3 + v2

...

e3 + vi

...

e3 + v2k

:













:

ei

ei + v2

...

ei + vi

...

ei + v2k

:













:

E2n-k

e2n-k + v2

...

e2n-k + vi

...

e2n-k + v2k

Figura 2: Arranjo padrão para um código linear (n,k)
Dessa forma, o arranjo padrão nada mais é do que uma tabela organizada com 2k colunas e 2n-k linhas. As palavras-código ocupam o topo das 2k colunas da tabela. A primeira coluna é encabeçada pela palavra-código zero (no caso dela existir). Essa coluna é chamada líder da classe lateral. As demais palavras (não pertencentes ao código) ocupam as demais posições da tabela obedecendo a seguinte regra: cada palavra deve estar o mais próxima possível (em termos de distância de Hamming) da palavra-código do topo da coluna onde se encontra a palavra em questão.

A síndrome de uma n-tupla é uma (n-k)-tupla e existem 2n-k diferentes (n-k)-tuplas. Existe uma correspondência um-a-um entre um componente do arranjo-padrão e uma (n-k)-tupla síndrome. Ou seja, existe uma correspondência um-a-um entre um líder da classe lateral (um padrão de erro corrigível) e uma síndrome. Utilizando essa correspondência, pode-se formar uma tabela de decodificação, a qual é muito mais simples do que usar o arranjo-padrão. Essa tabela consiste de 2n-k líderes da classe lateral (os padrões de erro corrigíveis) e suas correspondentes síndromes. Essa tabela deve estar armazenada no receptor. Assim, a decodificação de um vetor recebido r segue três passos.



  • Cálculo da síndrome de r:;

  • Localizar o líder da classe lateral cuja síndrome é igual a . Assim, é o padrão de erro causado pelo canal.

  • Decodificar o vetor recebido r, que consiste em somar (operação ou-exclusivo) a palavra recebida e o padrão de erro obtido: v = r + ei.

Um exemplo da tabela de decodificação por síndrome está mostrado na tabela 2 abaixo para o código de Hamming C(7,4).


Tabela 2: Tabela de decodificação para C(7,4)

Síndrome

Líderes da Classe Lateral

(1 0 0)

(1 0 0 0 0 0 0)

(0 1 0)

(0 1 0 0 0 0 0)

(0 0 1)

(0 0 1 0 0 0 0)

(1 1 0)

(0 0 0 1 0 0 0)

(0 1 1)

(0 0 0 0 1 0 0)

(1 1 1)

(0 0 0 0 0 1 0)

(1 0 1)

(0 0 0 0 0 0 1)

O esquema de decodificação descrito acima é chamado de decodificação por síndrome. Esse tipo de decodificação pode ser aplicado a qualquer código linear (n,k). Ele resulta em um atraso de decodificação mínimo e em uma probabilidade mínima de erro.




    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