Códigos Unicamp

Prof.
Eric Fagotto
1
O que um Cdigo?
Um cdigo simplesmente um conjunto de elementos. Por exemplo, A={0,1}
um cdigo composto pelas palavras 0 e 1. A motivao para a utilizao de cdigos
pode ser a mais variada, mas, estar normalmente associada a pelo menos uma das
seguintes necessidades:
1) Criptografia (SSL, etc).
2) Compresso de informao (zip, JPG, MPEG, etc).
3) Evitar a deteriorao de informao (Hamming, etc).
Cdigos BCD
No sistema de codificao de decimal em binrio (BCD - binary coded decimal)
cada digito decimal expresso atravs de um conjunto de 4 bits (1 nibble).
Portanto, existiro 16!/6! codificaes possveis. Contudo, a maior parte no
utilizada devido s dificuldades com as operaes aritmticas. Apresentamos na
tabela abaixo alguns deles:
Dec 8 4 2 1 8 4 -2 -1 2 4 2 1 3 em excesso
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
1 0 0 0 1 0 1 1 1 0 0 0 1 0 1 0 0
2 0 0 1 0 0 1 1 0 0 0 1 0 0 1 0 1
3 0 0 1 1 0 1 0 1 0 0 1 1 0 1 1 0
4 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1
5 0 1 0 1 1 0 1 1 1 0 1 1 1 0 0 0
6 0 1 1 0 1 0 1 0 1 1 0 0 1 0 0 1
7 0 1 1 1 1 0 0 1 1 1 0 1 1 0 1 0
8 1 0 0 0 1 0 0 0 1 1 1 0 1 0 1 1
9 1 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0
Estes cdigos so ditos ponderados, ou seja, um peso determinado atribudo para
cada posio de bit. Os cdigos (8,4,-2,-1) e o (3 em excesso) so complementares,
i.e., a complementao individual dos bits de uma palavra gera outra palavra
vlida, p.ex.: 00111100 e 0011+1100=1111. O BCD8421 tem como seu
principal atrativo a facilidade de converso para o sistema decimal. No se deve
confundi-lo com o binrio simples, onde
(00011001)
2
= 25, enquanto no BCD8421, (00011001)
BCD
= 19.
Prof. Eric Fagotto
2
Cdigo Gray
O cdigo Gray faz parte de uma classe de codificao onde as palavras sucessivas
diferem por apenas um bit. Conforme podemos observar pela tabela abaixo, ele
gerado mediante a reflexo sucessiva das palavras. Este cdigo encontra aplicaes
tecnolgicas importantes, como p.ex., na converso A/D, ou ainda na codificao
de ngulos (shaft enconder). Note que no se trata de um cdigo ponderado. O
algoritmo para gerao do cdigo Gray a partir do cdigo binrio :
g
i
= b
i
b
i+1
Regras Prticas de Converso
(i) binrio para Gray
1 + 0 + 1 + 1 +
0
Binrio Gray
b
3
b
2
b
1
b
0
g
3
g
2
g
1
g
0
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1
0 0 1 0 0 0 1 1
0 0 1 1 0 0 1 0
0 1 0 0 0 1 1 0
0 1 0 1 0 1 1 1
0 1 1 0 0 1 0 1
0 1 1 1 0 1 0 0
1 0 0 0 1 1 0 0
1 0 0 1 1 1 0 1
1 0 1 0 1 1 1 1
1 0 1 1 1 1 1 0
1 1 0 0 1 0 1 0
1 1 0 1 1 0 1 1
1 1 1 0 1 0 0 1
1 1 1 1 1 0 0 0
Prof. Eric Fagotto
3
Cdigos Dectetores e Corretores de Erros
Os cdigos apresentados at o momento, a exceo do Cdigo Gray, so pouco
robustos a erros que podem ocorrer devido a rudos durante uma transmisso.
Embora no apresentemos a prova nestas notas, a probabilidade da ocorrncia de 2
ou mais erros em uma palavra muito pequena.
Cdigos Detectores de Erros
Um cdigo dito detector de erro sempre que a ocorrncia de um erro simples
resultar em uma palavra de cdigo invlida. Definimos a distncia entre duas
palavras de cdigo como sendo o nmero de bits que necessitam ser
complementados em uma delas para que se tornem iguais. Portanto, cdigos
detectores de erro simples tero uma distncia mnima de 2. A seguir so
apresentados alguns desses cdigos
Note que para transformarmos (00011)
2 em 5
numa outra palavra vlida, como
(10001)
2 em 5
, sero necessrias duas complementaes [(00011)
2 em 5
].
Cdigos Corretores de Erros
Considere um cdigo de trs bits, formado unicamente pelas palavras 000 e
111 (palavras vlidas). Supondo que um erro simples ocorra na primeira
palavra, ela poder ser alterada para: 001, 010 ou 100. No caso da segunda
palavra teremos: 110, 101 ou 011. Assim, como a distncia mnima do
cdigo 3, qualquer erro simples resultar numa palavra invlida, cuja distncia
da palavra original 1, e 2 da outra palavra vlida. Desta forma, qualquer erro
simples poder ser corrigido, ou qualquer erro duplo detectado.
D 2 em 5 Biquinrio
( 5; MSB=1)
0 1 2 4 7 5 0 4 3 2 1 0
0 0 0 0 1 1 0 1 0 0 0 0 1
1 1 1 0 0 0 0 1 0 0 0 1 0
2 1 0 1 0 0 0 1 0 0 1 0 0
3 0 1 1 0 0 0 1 0 1 0 0 0
4 1 0 0 1 0 0 1 1 0 0 0 0
5 0 1 0 1 0 1 0 0 0 0 0 1
6 0 0 1 1 0 1 0 0 0 0 1 0
7 1 0 0 0 1 1 0 0 0 1 0 0
8 0 1 0 0 1 1 0 0 1 0 0 0
9 0 0 1 0 1 1 0 1 0 0 0 0
BCD
Paridade Par (Even)
P B
8
B
4
B
2
B
1
0 0 0 0 0
1 0 0 0 1
1 0 0 1 0
0 0 0 1 1
1 0 1 0 0
0 0 1 0 1
0 0 1 1 0
1 0 1 1 1
1 1 0 0 0
0 1 0 0 1
BCD
Paridade mpar (Odd)
P B
8
B
4
B
2
B
1
1 0 0 0 0
0 0 0 0 1
0 0 0 1 0
1 0 0 1 1
0 0 1 0 0
1 0 1 0 1
1 0 1 1 0
0 0 1 1 1
0 1 0 0 0
1 1 0 0 1
Prof. Eric Fagotto
4
Cdigo de Hamming (CH)
Um CH (n,m) de k bits constitui uma classe especial de cdigo corretor de erro
simples, que utiliza m bits de paridade para certificar/corrigir n bits informao,
onde
Portanto, para 4 bits de informao sero necessrios pelo menos 3 bits de
paridade, ou seja, um cdigo com palavras de 7 bits.
A codificao de Hamming pode ser colocada nos seguintes termos:
1. Todas as m posies de bit que so potncias de 2 so os bits de paridade (1, 2,
4, etc.)
2. As demais n posies sero utilizadas pelos bits de informao (3, 5, 6, 7, etc.)
3. A posio de cada bit de paridade determina os bits a serem verificados, isto :
Posio 1: verifica os bits 1, 3, 5, 7, ... ; i.e. XXX1
Posio 2: verifica os bits 2, 3, 6, 7, 10, 11; i.e. XXX10
Posio 4: verifica os bits 4, 5, 6, 7, 12, 13, 14, 15, 20; i.e. XX010
4. Faa o j-simo bit de paridade igual ao XOR entre os bits checados, exceto com
o prprio bit de paridade (isto assegura paridade par), ou simplesmente
verifique o nmero de 1s necessrios p/ manter a paridade.
Exemplo: Utilize o algoritmo de Hamming para codificar
1010 (X
7
=1, X
6
=0, X
5
=1, X
1
=0)
Escrevendo a palavra com os bits de paridade:
1 0 1 P
4
0 P
2
P
1
Posio 1 verifica os bits 1,3,5,7: P
1
= X
3
X
5
X
7
= 0 1 0 1 P
4
0 P
2
0
2
= X
3
X
6
X
7
= 1 1 0 1 P
4
0 1 0
4
= X
5
X
6
X
7
= 1 1 0 1 0 0 1 0
Portanto a codificao resulta em : 1 0 1 0 0 1 0
2
m
n+1 k=n+m
e
Prof. Eric Fagotto
5
A gerao e a verificao dos cdigos executada de modo mais eficiente atravs de
equaes matriciais. No caso da verificao, usual se utilizar uma equao de sndrome:
[S]=[H] [v],
onde [H] uma matriz de 2
k-m
1 colunas e k m linhas e [v] um vetor coluna de
2
k-m
1 linhas. As colunas da matriz [H] so formadas por todas as possveis palavras de
k m bits, exceto a palavra nula. Se a palavra for vlida, [S]=[0] e, caso contrrio, a
sndrome [S] indicar em qual bit est o erro.
Exemplo: Verifique se v = [011100101010] um CH vlido.
Como a palavra tem 12 bits (k=12), decorre que existem 4 bits de paridade (m = 4) e a
equao de sndrome escrita como
[ ]
( ) ( ) ( ) ( ) ( ) ( )
1
0
0 0 0 1 1 1 1 0
0 1 1 0 0 1 1 1
1 0 1 0 1 0 1 1
0
1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 [1 1 1]
S

= =

= =

[ ]
( ) ( ) ( ) ( ) ( ) ( )
1
0
0 0 0 1 1 1 1 0
0 1 1 0 0 1 1 1
1 0 1 0 1 0 1 1
0
1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 [1 1 1]
S

= =

= =

Códigos Unicamp

Enviado por

Direitos autorais:

Formatos disponíveis

Códigos Unicamp

Enviado por

Dados do documento

Descrição original:

Título original

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Códigos Unicamp

Enviado por

Direitos autorais:

Formatos disponíveis

Prof.

Você também pode gostar