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



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

Códigos BCH

Os códigos de Bose, Chaudhuri e Hocquenghem (BCH) formam uma vasta classe de poderosos códigos cíclicos corretores de erro. Essa classe é uma generalização dos códigos de Hamming para correção de múltiplos erros. Os códigos BCH binários foram descobertos por Hocquenghem em 1959 e independentemente por Bose e Chaudhuri, em 1960. Entre os códigos BCH não-binários, a subclasse mais importante é a classe dos códigos Reed-Solomon (RS). Os códigos RS foram introduzidos em 1960 por Reed-Solomon, independentemente dos trabalhos de Bose, Chaudhuri e Hocquenghem.

O primeiro algoritmo de decodificação para códigos binários BCH foi desenvolvido por Peterson em 1960. Desde então, esse algoritmo foi sendo generalizado e refinado por Gorenstein e Zierler, Chien, Forney, Berlekamp, Massey e Burton. Entre todos os algoritmos decodificadores dos códigos BCH, o algoritmo iterativo de Berlekamp e o de busca de Chien são os mais eficientes.

    1. Descrição do Código

Para qualquer inteiro positivo m (m 3) e t (t < 2m-1), existe um código BCH binário com os seguintes parâmetros:




  • Comprimento do bloco: n = 2m –1

  • Número de dígitos de paridade: n-k mt

  • Distância mínima: dmin 2t +1

Esse código é capaz de corrigir qualquer combinação de t ou menos erros em um bloco de n dígitos. Portanto, esse código é chamado de um código BCH corretor de t erros. O polinômio gerador do código é especificado em termos das raízes a partir do campo de Galois GF(2m). Seja um elemento primitivo em GF(2m). O polinômio gerador g(x) de um código BCH corretor de t erros e comprimento n é o polinômio de menor grau sobre GF(2) que possui , 2, 3, ..., 2t e seus conjugados como raízes. Seja i o polinômio mínimo de i. Então, g(x) deve ser o mínimo múltiplo comum de 1(x), 2(x), ..., 2t(x), ou seja:


(20)
Se i for um número par, ele pode ser expresso como produto da seguinte forma: , onde i’ é um número ímpar e l  1. Então, é o conjugado de i e, dessa forma, i e i’ possuem o mesmo polinômio de grau mínimo, ou seja, i(x) = i’(x). Como resultado, o polinômio gerador g(x) torna-se:
(21)
Pode-se definir um código BCH corretor de t erros da seguinte maneira: uma n-tupla binária v = (v0, v1, v2, ..., vn-1) é uma palavra do código se e somente se o polinômio v(X)=v0+ v1X+...+ vn-1Xn-1 possuir , 2, 3, ..., 2t como raízes.

Seja v(X)= v0+ v1X+...+ vn-1Xn-1 um polinômio do código em um código BCH corretor de t erros de comprimento n = 2m –1. Uma vez que i é uma raiz de v(X) para 1  i 2t, então


(22)
A equação (22) pode ser escrita como um produto de matrizes:
(23)
Pode-se formar a seguinte matriz:
(24)
Como v = (v0, v1, v2, ..., vn-1) é uma palavra do código BCH corretor de t erros, então
(25)
Se para algum i e j, j é conjugado de i, então v(j) = 0 se e somente se v(i)=0. Dessa forma, se o produto interno de v = (v0, v1, v2, ..., vn-1) com a i-ésima linha de H for nulo, o produto interno da j-ésima linha de H é também nulo. Por essa razão, a j-ésima linha de H pode ser omitida. Como resultado, a matriz H pode ser reduzida para a seguinte forma:
(26)
É importante observar que as entradas da matriz H são elementos em GF(2m). Cada elemento pode ser representado por uma m-tupla sobre GF(2). Se cada entrada de H é substituída por sua correspondente m-tupla sobre GF(2), pode-se obter uma matriz binária de checagem de paridade para o código.

    1. Decodificação dos Códigos BCH

Sabendo-se que a palavra código v(X) = v0+ v1X+...+ vn-1Xn-1 é transmitida e que devido aos erros de transmissão, o vetor recebido é .

Seja e(X) o padrão de erro. Então:
(27)
O primeiro passo da decodificação é computar a síndrome a partir do vetor recebido r(X). Para decodificar um código BCH corretor de t erros, a síndrome é uma 2t-tupla.
(28)
A partir de (24) e (28), pode-se encontrar a i-ésima componente da síndrome para 1i2t.


(29)
Deve-se notar que os componentes da síndrome são elementos no campo GF(2m). Esses componentes podem ser computados a partir de r(X). Dividindo r(X) pelo polinômio mínimo i(X) de i, obtém-se
(30)
Na equação (30), bi(X) é o resto da divisão com grau menor que i(X). Como i(i)=0, tem-se que
(31)
Dessa forma, a componente da síndrome Si pode ser obtida através do cálculo de bi(X) com X=i.

Uma vez que 1, 2, ..., 2t são raízes de cada polinômio do código, v(i) = 0 para 1 i 2t. A partir das equações (27) e (29), pode-se obter a seguinte relação entre os componentes da síndrome e o padrão de erro.


(32)
Com a equação (32) acima, observa-se que a síndrome depende somente do padrão de erro e. Supondo que o padrão de erro e(X) possui v erros nas localizações Xj1, Xj2, ..., Xjv, ou seja:
(33)
Onde 0 j1 < j2 < ... < jv < n. A partir de (32) e (33), obtém-se o seguinte conjunto de equações:
(34)
Onde j1, j2, ..., jv são desconhecidos. Qualquer método de resolução dessas equações é um algoritmo de decodificação dos códigos BCH. Uma vez encontrados j1, j2, ..., jv, as potências j1, j2, ..., jv mostram as localizações dos erros em e(X).

Na seqüência, será descrito um eficiente procedimento para a determinar jl, para l = 1, 2, ..., v a partir dos componentes da síndrome Si’s.

Por conveniência, seja l = jl, para 1  lv. Esses elementos são chamados números de localização de erro, uma vez que eles informam a localização dos erros.

As equações (34) podem ser expressas da seguinte forma:


(35)
Essas 2t equações são as funções simétricas em 1, 2, ..., v, as quais são conhecidas como funções simétricas das somas de potências. Pode-se agora definir o seguinte polinômio:

(36)
As raízes de (X) são 1-1, 2-1, ..., v-1, que são o inverso dos números de localização de erro. Por essa razão, (X) é chamado de polinômio de localização de erro. É interessante lembrar que (X) é um polinômio desconhecido cujos coeficientes devem ser determinados. Os coeficientes e os números de localização de erro são relacionados pelas seguintes equações:
(37)
Os i’s são conhecidos como funções simétricas elementares dos i’s. A partir das equações (35) e (37), pode-se relacionar os i’s com as componentes da síndrome Sl’s. De fato, eles se relacionam através das identidades de Newton:
(38)
Para o caso binário, como 1+1=2=0, tem-se que
(39)
É possível determinar as funções elementares 1, 2, ..., v a partir das equações (38). Os números de localização de erro podem ser encontrados determinando-se as raízes do polinômio de localização de erro (X).

Faz-se necessário resumir o procedimento de correção de erro dos códigos BCH em três passos principais:




  • Computar a síndrome S a partir do polinômio recebido r(X);

  • Determinar o polinômio de localização de erro (X) a partir dos componentes da síndrome;

  • Determinar os números de localização de erro encontrando as raízes de (X) e corrigindo os erros em r(X).

O primeiro algoritmo que utiliza esses três passos para a decodificação dos códigos BCH foi desenvolvido por Peterson. Contudo, o algoritmo mais eficiente para tanto é o algoritmo iterativo de Berlekamp para obtenção do polinômio de localização de erro (X).




    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