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


Códigos BCH Não-binários e de Reed-Solomon



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

Códigos BCH Não-binários e de Reed-Solomon

Em complementação aos códigos binários, existem os não-binários. De fato, se p é um número primo e q é qualquer potência de p, existem códigos com símbolos a partir do campo de Galois GF(q). Esses códigos são chamados código q-nários. Os conceitos e propriedades desenvolvidos para os códigos binários, como vistos anteriormente, aplicam-se aos códigos q-nários com poucas modificações. Um código linear (n,k) com símbolos a partir de GF(q) é um subespaço k-dimensional do espaço vetorial de todas as n-tuplas sobre GF(q). A codificação e a decodificação dos códigos q-nários são similares às dos códigos binários.

Os códigos BCH definidos anteriormente podem ser generalizados a códigos não-binários da seguinte maneira. Para qualquer escolha de inteiros positivos s e t, existe um código BCH q-nário de comprimento n = qs – 1, o qual é capaz de corrigir qualquer combinação de t ou menos erros e não requer mais do que 2st dígitos de checagem de paridade.

Seja um elemento primitivo no campo de Galois GF(qs). O polinômio gerador g(X) de um BCH q-nário corretor de t erros é o polinômio de menor grau com coeficientes de GF(q) onde , 2, ..., 2t são raízes. Seja i(X) o polinômio mínimo de i. Então .

O grau de cada polinômio mínimo é s ou menor. Portanto, o grau de g(X) é no máximo 2st. Para q = 2, têm-se os códigos binários BCH. Nesse item, será analisada somente uma subclasse especial de códigos BCH q-nários.

A subclasse especial de códigos BCH q-nários para a qual s = 1 constitui a subclasse mais importante. Os códigos dessa subclasse são usualmente chamados de Reed-Solomon, em homenagem aos seus descobridores. Um código Reed-Solomon corretor de t-erros com símbolos em GF(q) possuirá os seguintes parâmetros:


Comprimento do bloco: n = q -1

Número de dígitos de paridade: n - k = 2t

Distância mínima: dmin = 2t +1
Na seqüência, considera-se o código de Reed-Solomon um código corretor de t erros com símbolos-códigos do campo de Galois GF(2m). Seja  um elemento primitivo em GF(2m). O polinômio gerador de um código Reed-Solomon corretor de t-erros de comprimento 2m-1 é
(40)
Claramente, a equação acima possui , 2, ..., 2t como suas raízes e possui coeficientes no campo de Galois GF(2m).

A codificação desse código é similar ao caso binário. Seja a(X) a mensagem codificada mostrada na equação abaixo.


(41)
A decodificação de um código Reed-Solomon (ou qualquer código BCH q-nário), os mesmos três passos para a decodificação dos códigos BCH binários são requeridos e ainda um quarto envolvendo o cálculo dos valores de erro. Dessa forma, as síndromes são obtidas substituindo i no polinômio recebido r(X) para i = 1, 2,..., 2t. Em seguida, encontra-se o polinômio de localização de erro (X) resolvendo as equações de Newton, conforme mostrado anteriormente com o método iterativo de Berlekamp. Uma vez encontrado (X), pode-se determinar os valores de erro.
(42)
Dessa forma, o valor de erro na localização l = jv é dado por
(43)

  1. Códigos Convolucionais

Os códigos convolucionais diferem dos códigos de bloco porque o codificador contém memória e suas n saídas em uma certa unidade de tempo não depende somente das k entradas naquele tempo, mas também dos m blocos de entrada anteriores. Um código convolucional (n,k,m) pode ser implementado através de um circuito linear seqüencial com k entradas, n saídas e memória de entrada m. Tipicamente, n e k são pequenos números inteiros com k < n, mas a ordem de memória pode ser aumentada para se obter uma baixa probabilidade de erro.

Esses códigos foram primeiramente introduzidos por Elias em 1955 como alternativa para os códigos de bloco. Logo após, Wozencraft propôs uma decodificação seqüencial como um esquema eficiente de decodificação dos códigos convolucionais.

Em 1963, Massey propôs um método de decodificação menos eficiente, mas de simples implementação chamado decodificação por threshold.

Em 1967, Viterbi propôs um esquema de decodificação de máxima verossimilhança, relativamente fácil de se implementar para códigos com pequenas ordens de memória. Esse esquema de decodificação conduziu a aplicações espaciais e em comunicação via satélite no começo dos anos 70.

    1. Codificação dos Códigos Convolucionais

O codificador para um código binário (2,1,3) está mostrado na figura. Deve-se notar que ele consiste de m = 3 registradores de deslocamento, n = 2 somadores módulo-2 e um multiplexador na saída. Os somadores podem ser implementados como portas ou-exclusivo.




Figura 2: Codificador para código convolucional binário (2,1,3)
A seqüência de informação u=(u0, u1, u2,...) entra no codificador bit a bit a cada instante de tempo. Uma vez que o codificador é um sistema linear, as duas seqüências de saída v(1) = (v0(1), v1(1), v2(1),...) e v(2) = (v0(2), v1(2), v2(2),...) pode ser obtido pela convolução da seqüência de entrada u com as duas respostas ao impulso do codificador. Uma vez que o codificador possui uma memória de unidade m-tempos, a resposta ao impulso pode durar até m+1 unidades de tempo e são escritas como g(1) = (g0(1), g1(1), ..., gm(1)) e g(2) = (g0(2), g1(2), ..., gm(2)). Para o codificador da figura, g(1) e g(1) são g(1) = (1 0 1 1) e g(2) = (1 1 1 1).

As respostas ao impulso g(1) e g(2) são chamadas seqüências geradoras do código.

As equações de codificação (44a) e (44b) podem ser escritas como mostrado nas equações abaixo, onde * denota convolução discreta e todas as operações são módulo-2.

(44a)

(44b)
A operação de convolução implica que para todo l 0, vi(1) é dado pela equação (45) abaixo.
(45)
Para o codificador da figura, vl(1) e vl(2) são resumidos na equação (46) abaixo.
(46)
Após codificação, as duas seqüências de saídas são multiplexadas em uma única seqüência, chamada palavra-código a fim de ser transmitida pelo canal. A palavra código é dada por:
(47)

As seqüências geradoras podem ser entrelaçadas e arranjadas em uma matriz G, chamada matriz geradora do código como mostra a equação (48).


(48)
Dessa forma, as equações de codificação podem ser reescritas como na equação (49), onde todas as operações são módulo-2.
(49)
Se o codificador contiver k registradores de deslocamento, nem todos possuirão o mesmo comprimento. Se Ki é o comprimento do i-ésimo registrador de deslocamento, então a ordem de memória m é definida como o comprimento máximo de todos os registradores de deslocamento e é dada pela equação (50).
(50)
Define-se ainda constraint lenght na equação (51) abaixo, uma vez que cada bit de informação permanece no codificador por m + 1 unidades de tempo e durante cada unidade de tempo pode afetar qualquer uma das n saídas do codificador.
(51)
Dessa forma, nA pode ser interpretada como o número máximo de saídas do codificador que podem ser afetadas por um único bit de informação.

Para o caso geral de um código (n,k,m), a matriz geradora é dada pela equação (52).


(52)
Nessa equação, cada Gl é uma submatriz cujas entradas estão mostradas na equação (53).
(53)
Um codificador convolucional gera n bits codificados para cada k bits de informação e R=k/n é chamada taxa do código. É importante observar que para uma seqüência de informação de comprimento finito kL, a palavra código correspondente terá comprimento n(L + m), onde as nm saídas finais são geradas após os últimos blocos de informação não-nulos entrarem no codificador. Observando um código convolucional como um código de bloco linear com uma matriz geradora G, a taxa do código é dada por kL/n(L + m), ou seja, a relação entre o número de bits de informação o comprimento da palavra-código. Se L >> m, então L/(L+m)1 e a taxa do código de bloco e a do código convolucional são aproximadamente iguais. Isso representa o modo normal de operação do código convolucional e, portanto, não haverá diferença entre a taxa do código convolucioanl e sua taxa quando observado como um código de bloco. Se L for mantido muito pequeno, a relação kL/n(L + m), que é a taxa efetiva da transmissão da informação será reduzida abaixo da taxa real do código por um fator dado pela equação abaixo, chamada fração de perda da taxa.
(54)
Em qualquer sistema linear, as operações no domínio do tempo podem ser substituídas operações mais convenientes de transformada do domínio que envolvem multiplicação polinomial. Como o codificador convolucional é um sistema linear, cada seqüência nas equações de codificação pode ser substituída por multiplicação polinomial. Na representação polinomial de uma seqüência binária, a seqüência é representada por coeficientes do polinômio.

Para um código (2,1,m), as equações de codificação tornam-se as (55).


(55)
Nessas euqações, a seqüência de informação, as seqüências codificadas e os polinômios geradores do código são dados pelas equações (56), (57) e (58) abaixo.
(56)

(57)

(58)
Após multiplexação, a palavra código torna-se:
(59)
D pode ser interpretado como um operador de atraso, a potência do operador D pode ser determinada como o número de unidades de tempo que um bit é atrasado em relação ao bit inicial da seqüência.

Como o codificador é um sistema linear, u(i)(D) representa a i-ésima seqüência de entrada e v(j)(D) é a j-ésima seqüência de saída, o polinômio gerador gi(j)(D) pode ser interpretado como a função de transferência do codificador em relação a entrada i e saída j. A matriz G(D) pode ser representada então pela matriz de função de transferência k x n.


(60)
Utilizando a matriz função de transferência, as equações de codificação para um código (n,k,m) pode ser expressa por:
(61)
Na equação acima, U(D) é a k-tupla das seqüências de entrada e V(D) é a n-tupla das seqüências de saída. Após a multiplexação, a palavra-código torna-se:
(62)
As equações (60), (61) e (62) podem ser reescritas para que se possa representar v(D) diretamente em termos das seqüências de entrada. Com algumas manipulações algébricas, pode-se encontrar a equação (63).
(63)
Nessa equação gi(D) é o polinômio composto gerador do código e é dado pela equação (64).
(64)


    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