Page 25 - Telebrasil - Janeiro/Fevereiro 1979

4. Avaliação de um Código
Os parâmetros geralmente usados
para se avaliar o desempenho de
um código são os seguintes:
a) C a p a c i d a d e d e d e t e c ç ã o
r o — É dada na forma da probabili­
dade de que um erro não seja de­
tectado através do código. Note-se
que os erros
“ aleatórios” (quando cada bit tem
a mesma probabilidade de estar er­
rado), ou "em erupções” (em in­
glês, "bursts” ) de dois ou mais
bits, com uma probabilidade que
pode depender inclusive da ocor­
rência anterior de erros. Assim, a
capacidade de detecção deve ser
especificada tanto para erros
aleatórios como para erupções de
erros (menores ou iguais a "m "
bits errados consecutivos). Na ver­
dade, há códigos que se revelam
melhores para erros aleatórios do
que para erupões de erros, ou vice-
versa; uma classe reduzida de
códigos tem bom desempenho pa­
ra ambos.
b) C a p a c i d a d e d e c o r r e ç ã o
— É expressa na forma de quantos
erros são corrigíveis num certo
número de bits (formando ou não
um-bloco). Analogamente à detec­
ção de erros, existem as capaci­
dades para correção de erros
aleatórios e de erupção de erros.
c) E f i c i ê n c i a — É definida em for­
ma de porcentagem, indicando
quanto uma dada mensagem con­
terá de informação em relação a
seu total (informação mais redun­
dância do código). Deve-se tomar
cuidado para não atribuir impor­
tância excessiva a esse parâme­
tro, pois a eficiência em si pode
não ser um condicionante em uma
determinada aplicação. Por exem­
plo, um sistema de transmissão de
dados para controle automático de
tráfego numa ferrovia não necessi­
ta uma atualização muito rápida
das informações aplicáveis, o que
pode levar à escolha de um código
pouco eficiente, mas bastante se­
guro, e concomitantemente lento.
A seguir, serão vistas com mais
detalhes as peculiaridades e limi­
tações de alguns códigos, dando-
se atenção especial para os códi­
gos cíclicos. Finalmente, uma
classe especial desses, os códi­
gos BCH, será analisada com res­
peito à correção de erros.
5. Códigos de Taxa Constante
A figura 1 ilustra um exemplo de
d e e r ­ código de taxa constante. Ao invés
de se usar o código BCD (b i n a r y
c o d e d d e c i m a l ) 8-4-2-1, cada bloco
é codificado com os “ pesos” 7-4-2-
podem ser 1-0. Essa pequena modificação
permite a codificação de qualquer
dígito decimal empregando sem­
pre dois bits “ 1” , com o artifício
adicional de uma coluna para "0” ,
e com a exceção de que os pesos
não valem para o decimal "0” , co­
dificado como 7 + 4; esta é a úni­
ca combinação de dois bits “ 1"
que resta para um código de 5 bits.
A taxa constante é, no exemplo da­
do, igual a dois "1” por palavra.
Deci­ Código
mal BCD
Equiva*
lente 842 1
9 1 0 0 1
8 1 0 0 0
7 0 1 1 1
6 0 1 1 0
d e e r r o 5 0 1 0 1
4 0 1 0 0
3 0 0 1 1 0 0 1
2 ’ 0 0 1 0
J ? 0 0 0 1
0 0 0 0 0
F i g u r a 1 — E x e m p l o d e c ó d i g o
t a x a c o n s t a n t e .
O código exemplificado detectará
todos os erros simples, triplos e
quíntuplos. Um erro duplo do tipo
11000 / 10100 naturalmenle não
poderá ser detectado, mas um erro
duplo tal como 11000 - 00000 será
detectado, pois não existe a
palavra-código 00000. É fácil con­
cluir que, no total, serão detecta­
dos 40% de todos os erros duplos
e quádruplos, tendo este código
uma capacidade para detectar
71% de todos os erros, com uma
eficiência de 80%.
6. Códigos Cíclicos BCH
Os códigos BCH (inventados inde­
pendentemente por Bose, Chaudh-
huri e Hocquenghem entre 1959-
t
1960) são um tipo de código cíclico
bastante atraente pelas suas pro­
priedades, e por serem de fácil im­
plementação. A idéia por detrás
deles consiste, a grosso modo, em
encarar as palavras de dados co­
mo a representação binária de um
polinómio. Como exemplo, a men­
sagem 100101 pode ser descrita
pelo polinómio 1 . x° + 0 . x 1 + 0 .
¦ x2 + 1 . x3 + 0 . x4 + 1 . x3, ou 1 +
x3 + x5. Para uma mensagem de
“ n” bits, os n-k bits redundantes
do código constituem o resto da
divisão do polinómio da infor­
mação por um "polinómio gera­
dor” G (x), de grau “ k” , após o que
são transmitidos os “ n” bits da
mensagem.
Caso se deseje apenas detectar er­
ros na recepção, efetua-se a mes­
ma operação de divisão sobre a
mensagem. Divide-se então o resto
assim obtido pelo polinómio gera­
dor e na ausência de erros o novo
resto deverá ser zero.
Para se entender como encontrar
Código de G(x) para um dado código BCH, se­
Taxa rão necessárias algumas defi­
Constante
nições preliminares extraídas da
7 4 2 1 0
álgebra dos corpos:
1 0 1 0 0
1 0 1 0 0
a) “ Corpo de Galois” de dois
1 0 0 0 1
0 1 1 0 0 símbolos (“ 0” e “ 1” ) é aquele defi­
0 1 0 1 0 nido através das operaões boolea-
0 1 0 0 1 nas de adição módulo-2 (OU exclu­
1 0 sivo) e multiplicação; sua repre­
0 0 1 0 1
sentação é CG (2). Analogamente,
0 0 0 1 1
' 1 1 0 0 0 define-se um corpo de Galois de
2m símbolos, CG (2m), com os
d e símbolos “ 0” , “ 1” , e 2™ - 2 quais­
quer outros.
b) Sendo “ a” um elemento de CG
(2m), o polinómio m(x), com coefi­
cientes binários, de menor grau tal
que m(a) = 0, é o “ polinómio
mínimo” , ou primitivo, de “ a” . Poli­
nómios mínimos são irredutíveis,
isto é, não fatoráveis; caso
contrário, seria
m(x) = m ^x). m^x)
m(a) = m ^a). m^a) = 0
e dai m^a) = 0 ou m^a) = 0, o que
é absurdo, pois m(a) é o polinómio
de menor grau tal que m(a) = 0.
c) Os 2m símbolos de CG (2m) são
gerados por um polinómio mínimo
m(x), a partir de símbolos a, a2, a3,
..., a', em que “ i” é igual ao grau de
m(x) menos 1, e tal que m(a) = 0.
Com esses conceitos, pode-se de­
finir um código BCH (n, k) para
quaisquer m, t positivos (t > 2m -
1), tais que: