Page 29 - Telebrasil - Janeiro/Fevereiro 1979

Para a codificação, no lado da
transmissão, a chave A está fecha­
da, a B aberta. Os 26 bits de infor­
mação passam pelos registrado­
res FF1, ...FF5, até que, em segui­
da, os bits de paridade P1, P2, ...,
P5 estejam armazenados nas
saídas dos biestáveis. A chave A
se abre e B se fecha, de modo que
os bits de paridade, resultantes da
divisão da informação por G (x),
são acrescentados á mensagem. A
figura 5 ilustra a divisão, como
exemplo, da palavra (1111 ... 11)
p o r G (x).
F i g u r a 5 — D e t e c ç ã o d e
d i v i s ã o d e p o l i n ó m i o s .
Na decodificação, usa-se o mesmo
circuito com A fechada e B aberta.
Após a passagem pelos biestáveis
dos 31 bits da mensagem, os no­
vos valores de P1,..., P5 devem ser
iguais a zero. Com isto, a saída da
porta “ NE” , denominada “ ERRO” ,
é nula, o que não aconteceria caso
um dos novos bits de paridade fos­
se “ 1” . Para mplhor interrelacionar
as figuras 4 e 5, note-se que o se­
gundo “ OU” exclusivo do circuito
de detecção compara o bit P4 num
instante de relógio t - 1 com o bit
P5 num instante “ t” . No instante
26, os bits de paridade conterão o
resto da divisão de 1 © x © x2 © ... tanto, para que um código corrija
© x25 por 1 © x2 © x5, e após o ins­ qualquer vetor com “ e” erros, cada
tante 31, o resto da divisão de 1 © vetor-erro deve dar origem a uma
X © X2 © ... © x24 © X25 © X26 © síndrome diferente. Dito de outra
X2? © X29 por 1 © X2 © X5j isto é, 0. forma, nenhum par de conjun­
tos com “ e” colunas de H pode ter
a mesma soma em módulo-2, isto
8. Matriz de Paridade e Código de é, cada conjunto de 2e colunas de
Hamming H deve ser linearmente indepen­
dente.
Antes de considerar com mais de­
talhe o processo de correção de er­ Com b a s e n e s s e s f a t o s ,
ros nos códigos BCH, é ne­ compreende-se melhor o código
cessário introduzir mais alguns inventado por Hamming em 1950.
conceitos e exem plificá-los Desejando-se corrigir t o d o s o s e r ­
através de uma outra classe de r o s i n d i v i d u a i s que possam ocor­
códigos.
rer numa sequência de “ n” dígitos,
basta arranjar H de forma que suas
Um código de paridade pode ser “ n” colunas sejam não-nulas e dis­
definido univocamente em termos tintas. O código corretor equiva­
de sua “ matriz de cheque de pari­ lente pode ser construído se conti­
dade", ou simplesmente matriz de ver "m ” dígitos de paridade, onde
paridade H, que é aquela tal que "m ” é o menor inteiro a satisfazer
uma palavra-código (v) = (v,,V2..... a desigualdade 2m > n + 1, pois
vn) obedeça à equação matricial
2m é o número de síndromes distin­
tas. Para chegar agora ao “ código
H (v)' = (0).
de Hamming” , basta arrumar a ma­
Se a característica de H for “ m” triz H, de forma que o conteúdo
(isto é, “ m” linhas de H são linear­ binário de cada coluna (convertido
mente independentes), n-m dos em seu decimal equivalente) indi­
elementos de (v) podem ser esco­ que a posição da coluna na matriz,
lhidos arbitrariamente — os dígi­ e que a s p o s i ç õ e s d o s d í g i t o s d e
tos de informação — enquanto p a r i d a d e n a p a l a v r a - c ó d i g o c o i n c i ­
que os “ m” dígitos restantes são d a m c o m a s c o l u n a s d a m a t r i z q u e
determinados como soluções da c o n t e n h a m u m ú n i c o “ 1 ” Esse ar­
equação matricial dada acima — ranjo permite as seguintes vanta­
os dígitos de paridade. gens:
A “ síndrome” de um vetor-código a) cada dígito de paridade pode
(v’) recebido será definida por: ser determinado diretamente dos
dígitos de informação, indepen­
¦
c = H (v')< dentemente dos demais dígitos de
paridade;
Se o vetor transmitido fora (v) e
ocorreu um vetor-erro (x), a b) a posição de um erro pode ser
síndrome será: determinada simplesmente con­
e r r o s p o r vertendo a síndrome resultante em
c = H(v + x)> = Hv< + Hx' = Hx< seu decimal equivalente, já sendo
este a localização do erro.
No exemplo anterior da figura 5, a
síndrome resultante do código Como exemplo, considere-se um
BCH foi “ zero” , pois foi decodifi­ código de Hamming para palavras
cado um vetor pertencente ao de comprimento n = 15, 2m > 15
código — Hv< = 0 — isto é, sem er­ + 1 = 16, e os vetores-códigos
ro detectável. Caso a síndrome conterão 11 bits de informação,
fosse diferente de “ zero” , tratar- contra m = 4 de paridade. Pode-se
se-ia de um vetor não-pertencente mostrar que a matriz de paridade
ao código, ou seja, com erro. será:
Na formulação dos códigos O f l O O O O O l 1 1 1 1 1 1 l \
I
através de matrizes de paridade, 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 /
verifica-se que a síndrome é igual 0 1 1 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 /
à adição, módulo 2, das colunas de
H cujas posições correspondem A estrutua da palavra, conforme
aos dígitos “ 1” do vetor-erro. Por- explicado, será