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


História dos Códigos Controladores de Erro



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

História dos Códigos Controladores de Erro

A história dos códigos controladores de erro teve início em 1948, com a publicação do artigo de Claude Shannon. Em seu estudo, Shannon mostrou que existe um número C, chamado capacidade do canal e medido em bits por segundo, que está associado a cada canal e que possui o seguinte significado: sempre que a taxa de transmissão R em bits por segundo de um sistema de comunicação for menor que C, então é possível projetar para esse canal um sistema de comunicação com códigos controladores de erros, cuja probabilidade de erro na saída do sistema é tão pequena quanto se queira. Shannon não disse, porém como encontrar esses códigos.

Em 1950, foi concentrado muito esforço para encontrar uma regra de formação de classes de códigos que produzissem a prometida probabilidade de erro. A primeira tentativa veio com os códigos de bloco com uma forte estrutura algébrica.

O primeiro código de bloco foi introduzido por Hamming, em 1950, com a correção de apenas um erro.

Desde então, muitos tipos de códigos de blocos foram descobertos, sendo que os maiores progressos foram quando, em 1960, Bose e Ray-Chaudhuri e, em 1959, Hocquenghem encontraram uma classe de códigos corretores de múltiplos erros, os códigos BCH. Enquanto isso, também em 1960, Reed e Solomon encontraram a mesma classe de códigos para canais não binários.

Uma segunda tentativa veio com os códigos convolucionais. Em 1967, foi desenvolvido o algoritmo de Viterbi, ótimo para a decodificação desses códigos. Esse algoritmo ganhou popularidade por sua baixa complexidade. Antes disso, os códigos convolucionais eram decodificados por algoritmos seqüenciais.

Em 1993, com o artigo “Near Shannon Limit Error Correcting Coding and Decoding: Turbo Codes”, Berrou, Glavieux e Thitimajshima introduziram a nova técnica de codificação, os Turbo Codes que produziam resultados muito eficientes e próximos ao limite de Shannon.

  1. Linhas Atuais e Futuras de Desenvolvimento de Códigos Controladores de Erro

Atualmente, os códigos controladores de erro são empregados em praticamente todos os sistemas de transmissão e/ou armazenamento de dados onde se deseja atingir uma determinada confiabilidade. Pode-se citar:




  • Comunicação via satélite;

  • Redes locais de Computadores;

  • Sistemas de telessupervisão e telecontrole;

  • Sistemas de automação bancária, ferroviária, industrial;

  • Sistemas de gravação magnética e em discos ópticos;

  • Modems de alta velocidade (modulação codificada);



  1. Códigos de Blocos Lineares

Na maioria dos computadores digitais e dos sistemas de comunicação de dados, a informação é codificada em dígitos binários (0 e 1). Assim, serão descritos brevemente somente os códigos de blocos lineares com símbolos a partir do campo de Galois GF(2).

Primeiramente, os códigos lineares de bloco são definidos e descritos em termos das matrizes geradoras e de checagem de paridade. Será mostrada a codificação dos códigos lineares de bloco e a utilização da síndrome para a detecção e a correção de erros.

Nos códigos de bloco, cada bloco codificado de n elementos depende somente dos k bits de informação. Ao contrário dos códigos convolucionais, os códigos de bloco não possuem memória. Pelo fato da palavra-código não depender do histórico das informações. Dessa forma, cada palavra código depende unicamente do código utilizado e dos bits de informação na entrada do codificador.

Para k bits de informação e n bits de codificação, existem (n-k) dígitos de verificação de paridade (dígitos de redundância).

    1. Introdução aos Códigos de Bloco Lineares


Assume-se que a saída de uma fonte de informação é uma seqüência de dígitos binários “0” ou ”1”. Na codificação de bloco, esta seqüência é segmentada em blocos de mensagem de comprimento fixo. Cada bloco de mensagem de comprimento u consiste de k dígitos de informação. Existe um total de 2k mensagens distintas. O codificador, de acordo com uma certa regra, transforma cada mensagem de entrada u em uma n-tupla binária v, onde n > k. Essa n-tupla v é chamada palavra-código ou vetor código da mensagem u. O conjunto de 2k palavras código é chamado de código de bloco.

Por definição, um código de bloco de comprimento n e 2k palavras-código é um código linear C(n,k) se e somente se suas 2k palavras códigos formam um subespaço de k dimensões de um espaço vetorial de todas as n-tuplas sobre o campo GF(2).

De fato, um código de bloco binário é linear se e somente se a soma módulo 2 de duas palavras código é também uma palavra código.

Uma vez que um código linear C(n,k) é um subespaço de k dimensões de um espaço vetorial Vn de todas as n-tuplas binárias, é possível encontrar k palavras-código linearmente independentes g0, g1, ..., gk-1 em C tal que toda palavra-código v em C é uma combinação linear dessas k palavras-código, ou seja
(1)
Na equação (1), ui = 0 ou 1 para 0  i < k. Pode-se arranjar estas k palavras-código linearmente independente como as linhas de uma matriz k x n, como na equação (2) abaixo.
(2)
Na equação (2), gi = (gi0, gi1, ... , gi,n-1) para 0  i < k. Se u = (u0, u1, ..., uk-1) é a mensagem codificada, a palavra código é dada pela equação (3).


(3)
Observa-se que as linhas de G geram o código linear C(n,k). Por essa razão, a matriz G é chamada matriz geradora do código C.

O código C(7, 4) mostrado na tabela 1 é um código de bloco sistemático linear, pois os quatro primeiros dígitos de cada palavra código são idênticos aos dígitos de informação.


Tabela 1: Código em bloco linear com k=4 e n=7 (Código de Hamming)

Mensagem

Palavra-código

(0 0 0 0)

(0 0 0 0 0 0 0)

(1 0 0 0)

(1 1 0 1 0 0 0)

(0 1 0 0)

(0 1 1 0 1 0 0)

(1 1 0 0)

(1 0 1 1 1 0 0)

(0 0 1 0)

(1 1 1 0 0 1 0)

(1 0 1 0)

(0 0 1 1 0 1 0)

(0 1 1 0)

(1 0 0 0 1 1 0)

(1 1 1 0)

(0 1 0 1 1 1 0)

(0 0 0 1)

(1 0 1 0 0 0 1)

(1 0 0 1)

(0 1 1 1 0 0 1)

(0 1 0 1)

(1 1 0 0 1 0 1)

(1 1 0 1)

(0 0 0 1 1 0 1)

(0 0 1 1)

(0 1 0 0 0 1 1)

(1 0 1 1)

(1 0 0 1 0 1 1)

(0 1 1 1)

(0 0 1 0 1 1 1)

(1 1 1 1)

(1 1 1 1 1 1 1)

Um código (n,k) linear e sistemático é completamente especificado por uma matriz Gk x n da forma mostrada na equação (4).


(4)

Na equação (4) acima, pij = 0 ou 1. Seja Ik a matriz identidade kxk. Então, G =[PIk].

Existe uma outra matriz associada com os códigos lineares de bloco. Para qualquer matriz Gn x k com k linhas linearmente independentes, existe uma matriz Hn-k x n com n-k linhas linearmente independentes. Todavia, pode-se descrever um código linear (n,k) gerado por G se e somente v . HT = 0. Essa matriz H é chamada de matriz de checagem de paridade do código.

Se a matriz geradora de um código linear (n,k) está na forma sistemática, a matriz de checagem de paridade deve tomar a seguinte forma da equação (5).




(5)
Onde PT é a transposta da matriz P.


    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