ESCUELA POLITCNICA DEL EJRCITO EXTENSIN LATACUNGA.CDIGOS DE
DETECCIN DE ERROR HAMMING Y CRC.Geovani VicenteDaz CuichnCarrera
Ingeniera Mecatrnica, Sexto Nivel, Escuela Politcnica del Ejrcito
Extensin Latacunga,Mrquede MaenaS!N Latacunga,
Ecuador"e-mail:[email protected] de preentaci!n:
"#$"9$#"1%.RESUMEN:El error es la alteracin del
valorcorrectoenunoo#s$itsdein%or#acin&roducidadurante su
al#acena#iento, trans#isin o#ani&ulacin, no existe ning'n
siste#a deco#unicacin de datos que &ueda i#&edir que
ocurranerroresdurantelatrans#isin, aunquela#a(oradeestos &ueden
detectarse #ediante dise)os a&ro&iadosque &er#iten
sa$er si la in%or#acin reci$ida es la#is#a que se trans#iti
original#ente"*n cdigo +a##inges un cdigode $loque ca&a
deidenti%icar (corregir cualquier error de$it si#&lequeocurra
dentro de l"El #todo de redundancia cclica ,C-C
C(clic-edundanc(C.ec/0 esotratcnica#u(usada&aradeteccin de
errores, son ca&aces de detectar la&resencia de errores en
una secuencia de $its #s no&ueden corregirlos"PALABRAS CLAVE:
C!digo de detecci!n de error&C!digo 'amming& C!digo de
detecci!n de error C(C.1. INTRODUCCIN)acomunicaci!nentre
variacomputadoraproduce continuamente un movimiento de
dato&generalmente porcanaleno die*ado para
eteprop!ito+lneatele,!nica-& ./ueintroducenunruidoe0terno /ue
produce errore en la tranmii!n.1or lo tanto& de2emo aegurarno
/ue i dichomovimiento caua errore& 3to puedan er detectado.4l
m3todo para detectar . corregir errore e incluir enlo 2lo/ue de
dato tranmitido2itadicionaledenominado redundancia.2. CDIGOS DE
DETECCIN YCORRECCIN DE ERRORES4nmatemtica&computaci!n.teora de
lain,ormaci!n& la detecci!n . correcci!n de errore e
unaimportanteprctica para elmantenimiento e
integridaddelodatoatrav3dedi,erenteprocedimiento.dipoitivo como
medio de almacenamientocon,ia2le.5o e0ite ning6n itema de
comunicaci!n de dato/ue pueda impedir /ue ocurran errore durante
latranmii!n& aun/ue la ma.ora de eto
puedendetectaremediantedie*oapropiado/uepermitena2er i
lain,ormaci!nreci2idaelamima/ueetranmiti! originalmente.2.1 TIPOS
DE ERRORES7nter,erencia& calor& magnetimo& etc&
in,lu.enenuna e*al electromagn3tica& eo ,actore puedenalterar
la ,orma o temporalidad de una e*al. 8i la e*altranporta dato
digitale& lo cam2io pueden modi,icarel igni,icado de lo dato.
)o errore poi2le on:2.1.1 ERROR DE BIT9nicamente un 2it de una
unidad de dato determinada cam2ia de 1 a " o vicevera.Figura 1:
4rror de 2it.:n error de 2it altera el igni,icado del dato. 8on
eltipodeerror menopro2a2leenunatranmii!ndedato erie& pueto /ue
el intervalo de 2it e mu. 2reve+1$,recuencia- el ruido tiene /ue
tener una duraci!n mu.2reve. 8in em2argo i puede ocurrir en una
tranmii!nparalela& en /ue un ca2le puede u,rir una
pertur2aci!n. alterar un 2it de cada 2.te. 2.1.2 ERROR DE RFAGA.4l
error de r,aga igni,ica /ue do o m 2it de
launidaddedatohancam2iado. )oerroreder,agano igni,ica neceariamente
/ue lo errore eproduzcan en 2it conecutivo. )a longitud de la
r,agaemidededeel primerohatael 6ltimo2it correcto&alguno 2it
intermedio pueden etar 2ien.Figura #: 4rror de r,aga.1ESCUELA
POLITCNICA DEL EJRCITO EXTENSIN LATACUNGA.)o errore de r,aga e m
pro2a2le en tranmiioneerie& donde la duraci!n del ruido e
normalmentema.or /ue la duraci!n de un 2it& por lo /ue a,ectara
a uncon;unto de 2it. 4l n6mero donde 2it a,ectadodepende de la taa
de dato . de la duraci!n del ruido.3. MTODO DE PARIDAD PARA
LADETECCIN DE ERROES:n 2it de paridad e un dgito 2inario /ue indica
iel n6merode2it conun valor de1 enuncon;untode2ite par o impar.
)o2itdeparidadcon,ormanelm3todo de detecci!n m imple.)o c!digo de
paridad e uan en.4te 2it de paridad e determina de ,orma /ue
eln6merototal de2it1atranmitireapar+c!digodeparidad par- o impar
+c!digo de paridad impar-.3.1 CDIGO DE PARIDAD PAR4l 2it de paridad
er un " i el n6mero total de 1 atranmitir e par.3.2 CDIGO DE
PARIDAD IMPAR4l 2it de paridad er un 1 i el n6mero total de 1e
impar.5ormalmente el 2it de paridad e a*ade a laiz/uierda del
carcter original.
1aracual/uierenteropoitivomBC%& e0iteunc!digo'amming con lo
iguiente parmetro:)ongitud del C!digo: nC#m-1 56mero de m2olo de
in,ormaci!n: DC#m-m-156mero de m2olo de compro2aci!n de
paridad:n-DCmCapacidad de correcci!n de errore:
tC1+dminC%-4;emplo:Eena;e 1"1""111"1"11F @cordar la longitud de
cada cadena: %#F @cordar el itema de numeraci!n: %F Dividir el
mena;e: 1"1 ""1 11" 1"1?F @ociar cada cadena con un entero: A 1 G
A2ESCUELA POLITCNICA DEL EJRCITO EXTENSIN LATACUNGA.AF 8umar todo
lo valore . a*adir el n6mero cam2iadode igno: -1HGF 4nviar A 1 G A
-1H codi,icado en 2inario4l receptor:1F 8uma todo lo valoreI i la
uma e "& procea el mena;eI i no& e ha producido un error.4l
c!digo de 'amming agrega tre 2it adicionale de compro2aci!n por
cada cuatro 2it de dato del mena;e. 4l algoritmo de 'amming puede
corregir cual/uier errorde un olo 2it& . detecta todo lo errore
de do 2it.1araunam2ienteenel /ueel ruidopuedacam2iarcomo m0imo #
2it de H& el c!digo 'amming egeneralmenteel dep3rdidamnima. 4l
mediotendra/ueermu.ruidoo para /ueeperdieran mde#2it de cada H +cai
el ?AJ de lo 2it tranmitido-& .ha2ra/ueconiderar
eriamentecam2iar a un mediode tranmii!n m ,ia2le.4l algoritmo e
imple: 1..1 LA INTEGRIDAD DE LOS DATOS FRENTE A LA CODIFICACIN4
6til paradetecci!n de errore& pero& encondicione de
eguridad& no podemo con,iar en /ue elC(C puede veri,icar
plenamente /ue lo dato on locorrecto en cao de /ue e ha.an
producido cam2iodeli2erado . no aleatorio.@menudo e piena /ue &
cuando llega unmena;e& 3te . u C(C coinciden& /uiere decir
/ue elmena;e no ha podido er alterado durante utranmii!n&
aun/ueeha.atranmitidoporuncanala2ierto.Cuando un C(C e calcula&
el mena;e e conerva+noci,rado- .lacontantedetama*oC(Ceit6ahaciael
,inal +edecir&el mena;epuedeertan,cilcomo leer ante de la
poici!n /ue ocupa el C(C-.@dem& lalongituddel C(Ce por
logeneralmuchompe/ue*a/uelalongituddel mena;e&
eimpoi2leparaunarelaci!nde1:1entrelaC(C.elmena;e.)aC(Cirveparaveri,icarlaintegridad&
peronopara a2er i el mena;e e correcto.1or el contrario& un
medio e,icaz para proteger a
lomena;econtralamanipulaci!nintencional eel uode unc!digo de
autenticaci!n de mena;ecomo'[email protected] CLCULO DE CRC4l
C(Cconiteenconiderar alo 2it
aertranmitidocomounpolinomioen0+paran2itelorden e n-1- tal /ue la
preencia de un t3rmino igni,icaun P1P& . la auencia& un
P"PI e decir: ean 1"1"1"1 lo2it a tranmitir& entonce el mena;e
podr erconiderado como un polinomio G+0- tal /ue: G+0- C 0H L0A L
0% L 1. :n mena;e de c!digo cclico conite enun n6mero de 2it de
dato . el QCC. 8ea n el n6merototal de 2it . D el n6mero de 2it de
dato& por lo tanto&el n6merode2it del QCCen- D. 4l
c!digodelmena;e +QCC- e o2tiene de # polinomio: 1olinomio generador
1+0- Eena;e 1olinomial G+0- +2it de dato-.Dado: 1+0-: polinomio
generador G+0-: polinomio de mena;e de dato8edeeahallar F+0-&
c!digodel mena;e1olinomial&como igue: Eultiplicarel
mena;eG+0-por 0& iendon-Deln6merode2it del QCCparadar lugar al
QCC+multiplicar por 0& elomimo/uedeplazar elmena;e polinomial
de dato n-D lugarecompletando con cero a la derecha-.G+0- R 0n-D
Dividir el productoreultante G+0- R 0n-D por elpolinomio generador
1+0-.G+0- R 0n-D C S+0- 1+0- L C+0- Depreciarel
cociente.umarleaG+0-R0n-Delreto C+0- de la divii!n para producir el
c!digo demena;e polinomial F+0-. F+0- C G+0- R 0n-D L C+0-I Eena;e
1olinomial a
)o clculo /ue realiza el e/uipo tranmior paracalcular u C(C
on:1. @*ade tanto cero por la derecha al mena;eoriginal como el
grado del polinomio generador2. Divide el mena;e con lo cero
incluido entreel polinomio generador3. 4l reto /ue e o2tiene de la
divii!n e umaal mena;e con lo cero incluido4. 8e enva el reultado
o2tenidoC"#"$%'(%)$"( *+( (),-).)$"%)/"( 0&1 CRC2
Detectatodoloerrorede1.#2it+erroreimple . do2le-. Detecta todo lo
errore de un MQurtN menor /ueel grado de 1+0- Detecta el 99 J de lo
errore de un MQurtN ma.or/ue el grado de 1+0-.3 MATEMTICAS DEL
CRC4te apartado e re,iere al anlii matemtico
deeteproceodedivii!n& comoponedemani,ietolamanera de elegir un
divior /ue garantiza la detecci!n4ESCUELA POLITCNICA DEL EJRCITO
EXTENSIN LATACUNGA.deerrore2uenapropiedade. 4neteanlii& lodgito
de la cadena de 2it on coniderado
comolocoe,icientedeunpolinomioenalgunovaria2le0$coe,iciente&
/ue on elemento del campo ,inito2inarioen lugar de lo n6mero
decimale. 4teTpolinomioU,ormaunacadenade2it/uepuedeno2ervare como
elemento de un anillo. :nanilloe&
ha2landoent3rminogenerale& uncon;unto de elemento& e decir
como lo n6mero /uepueden er operado por una operaci!n eme;ante
peronoid3nticaaladelauma. adem algunaotraoperaci!n eme;ante a la
multiplicaci!n&
etaoperacionepoeenmuchadelapropiedadedelaaritm3tica
conmutatividad& aociativa& . ditri2utiva..4 APLICACIONES DE
UN CRC4l C(C e utiliza como una detecci!n de errore dec!digo&
el cual tiene una erie de aplicacione uada cuando e implementa
mediante norma& convirti3ndolo a en un itema prctico.4ta on
alguna de la aplicacione: 8e ua un patr!n de pre,i;o de 2it para
compro2ar u autenticidad. 4to e 6til cuando la trama podra tener
errore en lo 2it de delante de un mena;e& una alteraci!n
/ue& de otro modo de;ara in cam2io al C(C. @ vece un envo
agrega n 2it +n e el tama*o de la C(C- al mena;e /ue e de2e
controlar .a /ue e cogera un polinomio /ue no era el correcto para
la divii!n. 4to tiene la conveniencia de /ue el C(C del mena;e
original con el C(C ad;unto e e0actamente cero& por lo /ue el
C(C e puede compro2ar implemente por la divii!n polin!mica .
comparando con el reto cero. @ vece e realiza una implementaci!n
del C(C con V( e0cluivo en el reto de la divii!n polin!mica.
O#0&- 0& 13( 4)%(: en ocaione& el orden en el /uee
envan la trama de dato no correponden e0actamente con la poici!n
/ue tendrn lo 2it enla divii!n polin!micaI e decir& /ue puede
/ue el primer 2it enviado ea el de m peo o vicevera. 4te convenio
tiene entido cuando la trama a enviar e envan por puerto erie .a
/ue el C(C e compro2ado por el .ard2are de cada m/uina& .cada
uno tendr un convenio con;unto de lectura . poicionamiento de
pa/uete para el envi! a la capa iguiente. O*)()5- 0&1 3#0&-
0&1 4)% 0& *+( 6&(3 0&1 631)-3*)3 0)/)(3#: alguno
ecritore proponen omitir eto& pueto /ue el 2it ma.or peo e
iempre 1& . .a /ue el 2it C(C de2e er de,inido por un +n L 1-
2it del divior& e inneceario mencionar el divior ma.or peo en
el mena;e . en el C(C.7. CONCLUSIONES
C!digoderedundanciacclicaelat3cnicamu. uada para detecci!n de
errore . cuandoe emplea elm3todo delc!digo polin!mico& elemior
. elreceptor de2ern etar de acuerdorepecto a un polinomio
generador. 4l C!digo 'amming& e un itema de detecci!n.
correcci!n automtica de errore enin,ormaci!n electr!nica& el
cual aocia una eriede2itdevalidaci!noparidadalo2itdedato. 1ara la
aplicaci!n del c!digo 'amming eneceita conocer o2re lo m3todo de
paridadpar e impar.8. REFERENCIAS=1> Gonzle 8ainz. 19KH.
Diponi2le en:
http:$$codigohammingud.WiDipace.com$,ile$vieW$CJC%J9%D7GVLD4L'@EE75GL#"1#.pd,$%?AK9%9K?$CJC%J9%D7GVJ#"D4J#"'@EE75GJ#"#"1#.pd,[2]
XiDipedia.=online>. @lgoritmo de C!digo de(edundancia Cclica.
Diponi2leen:http:$$e.WiDipedia.org$WiDi$@lgoritmoYdeYloYCJC%JQ%digoYdeY(edundanciaYCJC%J@Dclica=%>
D. Ga;Di&3Princi&ios de dise)o digital3& #nd. ed.&
1rentice'all& 5Z& pp. %"-?H& 199G.[4]4chaiz +#"1%&
@2ril #?- 5etWorD +#nd
ed.-Diponi2leen:http:$$c.un.edu.ar$[;echaiz$organizacion$clae$clae$1H-Codigo#J#"QX.pd,5
