11 Codigos Corretores de Erro2

Prévia do material em texto

Códigos Corretores de Erro
Introdução
• A necessidade de se garantir a integridade de uma grande quantidade de 
informação transmitida pelos mais variáveis meios exige o uso de 
sofisticados sistemas de códigos corretores de erros.
• Dois importantes tipos de códigos:
– Códigos de bloco: um bloco de k dígitos de dados é codificado por 
uma palavra de código de n dígitos (n>k). Para cada seqüência 
de k dígitos de dados, existe uma palavra de código distinta de n 
dígitos.
– Códigos convolucionais ou recorrentes: a seqüência codificada de n 
dígitos depende não apenas dos k dígitos de dados, mas também dos 
 dados digitais N-1 anteriores (N>1). Assim, a seqüência codificada 
para um conjunto de k dígitos de dados não é única, mas depende 
dos N-1 dígitos de dados
Introdução
• Se k dígitos de dados são transmitidos por uma palavra de código de n dígitos, o 
número de dígitos de verificação é m=n-k. . 
• A eficiência de código (ou taxa de código) é k/n
• Este código é representado por (n,k)
• Os dígitos de dados formam um vetor k-dimensional d=(d1,d2,...dk) e a palavra de 
código é um vetor n-dimensional c=(c1,c2,...,cn)
Limite de Hamming
• Se considerarmos que a distancias entre duas 
palavras de código é o numero de posições 
em que estas palavras diferem. Exemplo, as 
palavras,
estão a uma distancia (de Hamming) d=2 
Limite de Hamming
• Um esquema é capaz de corrigir até t erros, a 
distancia mínima entre duas palavras de código 
valido 
• Para encontrar a relação entre n e k, nota-se que 2n 
palavras estão disponíveis para 2k palavras de dados 
e o restantes, 2n-2k são palavras redundantes. Então, 
quantas palavras cabem em uma esfera de raio t?
Limite de Hamming
• A expressão anterior pode ser escrita como
onde m=n-k
• Essa expressão é denominada limite de 
Hamming. Vale ressaltar que, em geral. O 
limite de Hamming é uma condição 
necessária, mas não suficiente
Limite de Hamming
• A Tabela mostra alguns exemplos de códigos de correção de erros e suas 
eficiências.
Limite de Hamming
• Os códigos para o qual a desigualdade anterior tornar-se uma 
igualdade são conhecidos como códigos perfeitos.
• Códigos perfeitos com t=1 são conhecidos como códigos de 
Hamming.
• Para esses códigos
• Assim
• Exercícios
• 1. (LATHI; 1998, p. 758) Os códigos de Golay (23,12) 
permitem a correção de até 3 erros. Verifique que n=23 
 e k=12 satisfazem o limite de Hamming exatamente 
para t=3
• 2. (LATHI; 1998, p. 758) Confirme a possibilidade de um 
código binário (18,7) corrigir até 3 erros. Este código 
consegue corrigir 4 erros?
Códigos de blocos lineares
• Uma palavra de código consiste de n dígitos 
c1, c2, ...,cn e uma palavra de dados consiste 
de k dígitos d1,d2,...,dk. Estas palavras são 
representadas pelos vetores-linhas
Códigos de bloco lineares
(LATHI; 1998, p. 732) Para um código (6,3), a matriz geradora (LATHI; 1998, p. 732) Para um código (6,3), a matriz geradora GG é: é: 
Para todas as possíveis oito palavras de dados, encontre as Para todas as possíveis oito palavras de dados, encontre as 
correspondentes palavras de códigos e verifique que este código é um correspondentes palavras de códigos e verifique que este código é um 
código corretor de 1 erro.código corretor de 1 erro.
Decodificação
• A soma módulo-2 de qualquer seqüência consigo 
mesma é zero, obtém-se: 
 em que Im é a matriz identidade de ordem mXn 
(m=n-k). Assim, 
Matriz verificadora de paridade
Decodificação
• Toda palavra de código deve satisfazer a 
equação da matriz de paridade. Essa é a base 
para a decodificação.
• Considere uma palavra recebida. Devido a possíveis 
erros causados pelo ruído do canal, r em geral difere 
da palavra transmitida
 em que a palavra de erro (ou vetor de erro) e é 
também um vetor linha de n elementos
Decodificação
Decodificação
• Exemplo, se a palavra de dado 100 é 
transmitida pela palavra de código 100101 e o 
ruído no canal causa erro de detecção no 
terceiro digito, então
Decodificação
• Suponha que a palavra de código transmitido Suponha que a palavra de código transmitido 
seja cseja c ii e o ruído no canal cause um erro e e o ruído no canal cause um erro e ii, , 
tornando a palavra recebidatornando a palavra recebida
• Se não há erros, isto é se ei=000000, então
Decodificação
• Porém, devido a possíveis erros causados pelo 
canal, rHT é, em geral, um vetor linha não-nulo 
s, chamado de síndrome,
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18