Page 26 - Telebrasil - Janeiro/Fevereiro 1979

— comprimento do bloco: n = 2m so, a16). Desta forma, m-j(x) terá co­ Os códigos BCH são construídos

- 1 mo raízes a, a2, a4, a8; portanto, com distância mínima dmfn s 2t +

1. Daí decorrem as propriedades

— número de bits de paridade: n mi(x) = (x 0 a )(x © a 2)(x 0 a 4)(x 0 a 8) = seguintes, que caracterizam seu

- k < mt < n = (x2 © a3 0 a2 xXx2 © a12 0 a4x 0 a®x) = desempenho:

= x4 © x2(a3 0 a2) 0 x2 a12 0 x3(a2 0 a) 0

x2 (a4 © a2 © 2a3) 0 x(a14 0 a13) 0
O polinómio gerador desse código © a ¥ ® x ( a 5© a 4) 0 a 15 1) Um código BCH é capaz de cor­

será rigir até “ t” erros.

Após simplificações evidentes, re­

G(x> = MMC (m,(x), mj|x),.... m2, . ,(x)) sulta: Seja Vo vetor-código transmitido,?

o recebido e ui qualquer outro

sendo mj(x) o polinómio minimo de irH(x) = x 4 © x 0 1 vetor-código. Se o máximo número

a'. Por exemplo, seja descobrir o de erros for “ t” ,

polinómio gerador para um código De maneira análoga, para achar

BCH (15,7), com m = 4, t = 2. Nes­ m3 (x), faz-se b = a3: d ( 7 , 7 ) < d ( ü , 7 ) < d ( v , u ) , e vale a d e s ig u a l­

se caso, d a d e : '

b20 ss a3, b21 = a®> b2* = a12» b23 = a24 =

a9, etc.

G(x) = MMC(m,(x),m3(x)) . . d ( v t 7 ) + . d ( u , r ) 2* . d(v,u) ,

Logo, m^x) = (x 0 atyx 0 a®Xx © atyx 0 *" mâx Z t " T u l i d m t n z
m^x) é o polinómio minimo do ele­ a12) = x 4 © x 3 0 x 2 0 x © 1 .

mento “ a” do CG (24). Inicialmente,

deve-se encontrar um polinómio (a3) é ou seja,

de grau “ m" irredutível. Usando a Verifica-se facilmente que m3 d ( u , r ) ^ d ( v , 7 )

notação de adição módulo — 2, vê- o polinómio mínimo para a3, d m i n 1 t ‘ < t

se que x4 © x3 © x2 © 1, por exem­ substituindo-se seu valor em m3 (x):

plo, é fatorável por x © 1, e por x - Logo, se ocorrerem “ t” ou menos

1 (pois x © 1 = x - 1), e não serve. a ' 2 f f i a 9 © a 8 © a 3 © 1 = 0 . erros, v estará mais próximo de 7

Pode-se demonstrar que p(x) = x4 Como polinómios minimos são ir do que qualquer outro vetor-código

© x © 1 é irredutível, e os 16 redutíveis, u. De acordo com o p r i n c i p i o d a

símbolos do CG (24) serão expres­ m á x i m a p r o b a b i l i d a d e ( m a x i m u m

sos em função de 0,1, a, a2, a 3 co­ l i k e l i h o o d ) , P (r/v) será um máximo,

mo se segue: MMC (m,(x), m3(x)) = m,(x)m3<x) = G(x) =

( X 4 ® x © 1 ) ( x 4 © x 3 © x 2 ® x © 1 ) . e 7 = v, sendo corrigidos os "t" er­

.o Portanto, G(x) = x3 © x? © x^ © x4 ros.

1

a ® 1, que é de grau 8, como deseja­ 2) Um código BCH é capaz de de­

a2 do.

a3 tectar dmin - 1 = 2t erros.

P(a) ® 0 — a4 © a © 1 = 0 e a4 = a © 1 (se Visto o procedimento para encon­

y© z = 0, y = z) trar G(x), ó necessário acrescentar Isso ocorre porque nenhum vetor-

a5 : = a . a 4 = a(a © 1) : a 2 © a código com dmin - J ou menos er­

a6 s : a . a5 = a(a2© a) a 3 © a 2 algumas definições para melhor ros alterará V para u. Por outro la­

a7 = : a . a6 = a(a30 a2) : a40 a3© a3© a entender o desempenho dos

© 1 códigos BCH. do, se o número de erros fo rj &

a8 = : a.a7 = a(a3© a © 1) « a2© 1 dmin, pode acontecer que d (u, ví =

a 9 = : a . a8 = a(a2© 1) = a3© a L e com um vetor-código e^= u ©

a 1 0 = a . a 9 : = a(a3© a) = a2© a © 1 — A “ Distância de Hamming” , ou v, u será transformado em v, e vice-

a 1 1 = a.a10 = a ( a 2 © a © 1) = a 3 © a 2 © a simplesmente "distância” , entre

a 1 2 = a . a h = a(a3 © a2 © a) = a3 © a2 © duas palavras-códigos representa­ versa.

a © 1 das por u e v , é igual ao número de

a 1 3 = a . a 1 2 = a(a3© a2© a © 1) = a3 © a 2 3) Um código BCH pode detectar
componentes_em que diferem._Por

© 1 toda erupção de erros de compri­

a ’ 4 = a . a13 = a(a3© a2© 1) = a3© 1 exemplo, se u = (10011011) e v = mento menor ou igual a n-k.

(01110101), a distância entre u e v

Daí por diante, os símbolos se re­ será:

petem ciclicamente, caracterizan­ 4) A fração não-detectada de eru­

do o código, como se verifica, por d ( u , v ) = 6 pção de erros de comprimento n -

exemplo, para a18 = a . a14 = 1, e # k + 1 de um código BCH é 2- (" - *

de maneira geral, aP = aP - i5q. — Dado um código, a menor dis­ + D.

tância entre todos os possíveis pa­

Com estes símbolos, pode-se res de vetores-códigos (palavras- 5) A fração não-detectável de e-

achar os polinómios mínimos. Pa­ códigos em forma vetorial) é cha­ 'rupções de erros de comprimentos

ra mi(x) forma-se a seguinte se­ mada “ distância mínima” do maiores do que n - k + 1 de um

quência: * código. código BCH é 2- (n ~ k).

b2° = a, b2' = a2, b2* = a4, b2Í = a8 b2“1 — Sendo v o vetor código transmi­ Como exemplo das três últimas

= a16 tido, e7o recebido, o vetor erro e é propriedades, cuja prova é mais

a diferença entreTe v, ou seja, elaborada, um código BCH muito

até que comece a repetição cícli­ usado, o (31,26) — isto é, com n =

ca, o que se dará para b2rn (no ca- e = 7 © v 31 e k = 26, e eficiência de 83,9%