Page 30 - Telebrasil - Janeiro/Fevereiro 1979
P. 30
V 3 (Ct C2 li C3 I2 I3 I4 C4 I5 lg I7 I3 |g possíveis do código BCH podem dimento para correção de erros e m
ser expressas por:
•10I11). três etapas:
S i = r(a') = r0 ® r, a 1 © r2 ( a 1) * ® . . . © r „ . ,
sendo Cj 0 i-ésimo bit de paridade (a')"-M = 1,2,... 2t 1) a partir de 7 ( x ) , calcular _as
e lj o j-ésimo bit de informação. Os sindromes (S) = XSi, §2 , .... St),
bits de paridade podem ser deter ou S , = v(a') © v(a‘) © r(a') = v(a') g usando a equação S, = 7(a');
minados pela equação Hvt = 0 : e(a'), ondea1, a2, ...a2’
2) calcular as sindromes e achar 0
são raízes de qualquer polinómio polinómio localizador de erros p
{ C| + It + i* + 1« + I5 + I7 + i9 + it1 = 0
c2 + 1 , + i3 + i4 + i6 + i7 + |10 + |1t = 0 associado a um vetor-código. As (x), através dos ai*, ou de algum al
C3 + l2 + l3 + l4 + l8 + l9 + I10 + |„ =0 sim, goritmo simplificador;
c < + *5 + 1« + *7 + Is + I9 + *10 + *11 = 0
v (a1) = 0 e S, = e (a'); supondo que 3) determinar os números localiza-
Por exemplo, para transmitir a in e(x) = xi1 © xJ2 © ... © xiu, então: dores de erros bj, achando as
formação 1 0 1 0 1 0 1 0 1 0 1, raízes de p (x) — caso não se tenha
verifica-se que C1 = 1, C2 = 0 , C3 S, = a*1©ai2© ...© aju obtjdo diretamente os ai* — e corri-
= 1 , C4 = 0 , sendo transmitido 0 S2 = (aj1)2© (aj2)2 ©... © (a»“)2 gir7(x) a seguir.
código 101101001010101.
Através de um exemplo, o proces
Para ilustrar a decodificação, S2, = (a*1)21 © (a*2)21 © ... © (ai“)21 so ficará mais claro. Seja x*m
suponha-se que 0 vetor recebido código BCH (1 5 ,9), com t = 3 e r =
tenha sido 1 0 0 1 0 1 0 0 1 0 1 0 1 0 1 . A O método de correção será portan (000101000000100) s x3© x 12
síndrome resúltará to achar as síndromas, 0 que impli
ca em resolver o sistema de 1) Cálculo das sindromes:
equações anterior, o que é
possível (pois u £ t). A seguir, S, = 7(a) = a3 © a 5 0 a12
encontra-se o “erro” ai* (I = 1,2,..., Usando os valores de ai do CG
u) para cada bit na posição jl. Há, (24), conforme atrás, vem:
cujo equivalente decimal é 1 .2 ° + entretanto, maneiras mais simples
1 .2* + 0 . 2 2 + 0 . 2 3 = 3, indican para se determinar as sindromes, S, = f 30 ji20 ^ © ^ © ^ 0 ^ 0 1 =1
do que o erro está no 3.° digito da como se verá a seguir. Analogamente,
sequência recebida. Pelo critério
da m í n i m a d i s t â n c i a (equivalente Primeiramente, simplifiquemos a s2 = r (a2) = a6 0 a10 0 a24 = 1
ao de máxima probabilidade), 0 ve notação fazendo b| = ai*, e que
tor transmitido t e r á sido será adequadamente denominado S3 = r*(a3)= a90 a150 a36 = a 10
101101001010101, como de fato ti "número localizador de erro":
S4 = r (a4) = a12 « a20© a48 = 1
nha sido suposto.
S, s b, © b2© ... © bu
S5 = r (a5) = a15 © a25 © a60 = a 10
Oberve-se que os códigos de Ham
ming usam uma técnica denomina S6 = 7(a6) = a18© a20© a72 = a6
da "entrelaçamento", consistindo S2, = b2S © b2,2® ... ® b2,u
na mistura entre bits de paridade e 2 ) Algoritmo para cálculo do poli
informação, o que os torna mais O “ polinómio localizador de erros" nómio localizador de erros:
eficientes para detectar erupções será definido como:
de erros. Um algaritmo possível para códi
P (X) = (1 © b,x) (1 © b2x)... (1 © bux) = Po gos BCH binários recomenda a
P i x ® p2x2©...©pux“, construção da seguinte tabela:
9 . Correção de Erros em Códigos
BCH onde
i P|M dj ') 2 i - * i
Sejam v(x) e r(x), respectivamente, Po = 1 - 1 / 2 1 1 0 - 1
os vetores transmitido e recebido b-j + b2... + bu 0 1 s , 0 0
dentro de um código BCH:
1
P2 = b1b2 + b2b3 + ... + bu _ 1 bu i %
V (x) = v 0 © v t x © v 2 x 2 I I I • •
t
Mx) = fo® r i x ® r 2 x 2 ® . . . ® r n -
Pu = t>ib2... bu Preenchendo-se a j-ésima linha, a
O vetor-erro será então (j + 1)-ésima linha será preenchida
Obviamente, as raízes de p (x) são de acordo com as seguintes re
e ( x ) = v ( x ) b - 1i, b - 12 , •••, b - 1u, que podem gras:
ser achadas por substituição em — se dj = 0, então Pj + n(x) = p;(x)
Sendo H a matriz de paridade, a p(x), devendo resultar p (x) = 0.
sindrome será_o vetor com n - k — se d j * 0 , procura-se uma linha
componentes s = 7. H* (pois v . H* Com as considerações preceden anterior j’, tal que 2j’ - lj seja o
= 0). Todas as sindromes tes, pode-se esquematizar o proce maior possível e dr * 0; então,
