Ver la fonte de Deteición y correición d'errores

[[Ficheru:Reed–Solomon error correction Mona Lisa LroLrLasercomFig4.jpg|miniaturadeimagen]]
En [[matemátiques]], [[computación]] y [[teoría de la información]], la '''detección y correición d'errores''' ye una importante práutica pal caltenimientu ya integridá de los datos al traviés de distintos procedimientos y dispositivos como medios d'almacenamientu confiables.<ref name="simmons">G. J. Simmons, "A survey of Information Authentication". Contemporary Cryptology, The science of information integrity, ed. GJ Simmons, IEEE Press, New York, (1992)</ref>Considérase como precursor d'esti tipu de teunoloxíes el [[Acme Comodity and Phrase Code]] usáu nos [[telégrafo|telegrames]]

== Introducción ==
La [[comunicación]] ente delles [[Ordenador electrónica|ordenador]]s produz de cutio un movimientu de datos, xeneralmente por [[Canal de comunicaciones|canales]] non diseñaos pa esti propósitu (llinia telefónica), y qu'introducen un [[ruiu]] esternu que produz errores na tresmisión.

Poro, tenemos d'aseguranos que si dichu movimientu causa errores, éstos puedan ser detectaos.
El métodu pa detectar y correxir errores ye incluyir nos bloques de datos tresmitíos [[bit]]s adicionales denominaos [[redundancia]].
 
Desenvolviéronse dos estrategia básiques pa remanar los errores: 

* Incluyir abonda información redundante en cada bloque de datos por que puedan detectase y correxir los bits erróneos. Utilícense '''códigos de correición d'errores'''. 

* Incluyir namái la información redundante necesaria en cada bloque de datos pa detectar los errores. Nesti casu'l númberu de bits de redundancia ye menor. Utilícense '''códigos de detección d'errores'''. 

Si consideramos un bloque de datos formáu por '''m''' bits de datos y '''r''' de redundancia, el llargor final del bloque va ser '''n''', onde '''n''' = '''m''' + '''r'''.

== Tipu de códigos detectores ==

=== Paridá simple (paridá horizontal) ===

Consiste n'añader un bit de más a la cadena que queremos unviar, y que nos indicará si'l númberu de ''unos'' (bits puestos a 1) ye par o ye impar. Si ye par vamos incluyir esti bit col valor = 0, y si nun ye asina, vamos incluyir con valor = 1.

 Exemplu de xeneración d'un bit de paridá simple:
 
 Queremos unviar la cadena “1110100”:
 1º Cuntamos la cantidá de ''unos'' qu'hai: 4 ''unos''
 2º El númberu de ''unos'' ye par por tanto añadimos un bit con valor = 0
 3º La cadena unviada ye 11101000

El receptor agora, repite la operación de cuntar la cantidá de “unos” qu'hai (menos el postreru bit) y si coincide, ye que nun hubo error.

'''Problemes d'esti métodu:'''

Hai una alta probabilidá de que se ''colen'' casos nos qu'hubo error, y que l'error nun seya detectáu, como asocede si camuden dos númberos na tresmisión en cuenta de unu.



Un exemplu de polinomiu xenerador usáu de normal nes redes [[WAN]] ye: <math>g(x) = x^{16}+x^{12}+x^5+1</math>

Los cálculos que realiza l'equipu tresmisor pa calcular el so CRC son:

# Añade tantos ceros pela derecha al mensaxe orixinal como'l grau del polinomiu xenerador
# Estrema'l mensaxe colos ceros incluyíos ente'l polinomiu xenerador
# El restu que se llogra de la división sumir al mensaxe colos ceros incluyíos
# Únviase la resultancia llograda

Estes operaciones xeneralmente son incorporaes nel [[hardware]] por que pueda ser calculáu con mayor rapidez, pero na teoría utilicen los polinomios pa facilitar los cálculos.

 Exemplu de llogru del CRC:
 
 Datos:
 Mensaxe codificado en binariu: 1101001
 Polinomiu xenerador: <math>x^4+x+1</math>
 
 Operaciones:
 
 1º Llograr el polinomiu equivalente al mensaxe: <math>x^6+x^5+x^3+1</math>
 
 2º Multiplicar el mensaxe por <math>x^4</math> (añader 4 ceros pela derecha): <math>x^{10}+x^9+x^7+x^4</math>
 
 3º Estremar en binariu'l mensaxe pol polinomiu xenerador y sacar el restu: <math>x^2+1</math>
 
 4º Concatenar el mensaxe col restu (en módulu 2 tamién): <math>x^{10}+x^9+x^7+x^4+x^2+1</math>
 
 5º Tresmitir el mensaxe

L'equipu receptor tien de comprobar el códigu CRC pa detectar si produciéronse o non errores.

 Exemplu de los cálculos del receptor:
 
 1º Por aciu el protocolu correspondiente alcuerden el polinomiu xenerador
 2º Estrema'l códigu recibíu ente'l polinomiu xenerador
 3º Comprueba'l restu de dicha operación
 
 3.1 Si'l restu ye cero, nun se producieron errores
 3.2 Procesar el mensaxe 3.1
 
 Si'l restu ye distintu de cero, significa que se producieron errores
 3.2 Reenviar el mensaxe 3.2
 
 Intentar correxir los errores por aciu los códigos correutores

En resume, esti métodu rique d'un polinomiu xenerador que, escoyíu correutamente, puede llegar a detectar gran cantidá d'errores:

* Errores simples: toos Errores dobles: toos Errores nes posiciones impares de los bits: toos Errores en rabaseres con un llargor menor que'l grau del polinomiu xenerador: toos
* Otres rabaseres: un porcentaxe elevao y cercano al 100%

=== Suma de comprobación ===
{{main|suma de verificación}}

Ye un métodu senciello pero eficiente namái con cadenes de pallabres d'un llargor pequeñu, ye por esto que se suel utilizar en [[Cabecera (informática)|cabeceres]] de trames importantes o otres cadenes importantes y en combinación con otros métodos.

Funcionalidad: consiste n'arrexuntar el mensaxe a tresmitir en cadenes d'un llargor determináu L non bien grande, de por casu 16 bits. Considerando a cada cadena como un númberu enteru numberáu según el sistema de numberación <math>2^L-1</math>.
De siguío súmase'l valor de toles pallabres nes que s'estrema'l mensaxe, y añader la resultancia al mensaxe a tresmitir, pero camudáu de signu.

Con esto, el receptor lo único que tien que faer ye sumar toles cadenes, y si la resultancia ye 0 nun hai errores.

 Exemplu:
 
 Mensaxe 101001110101
 
 1º Alcordar el llargor de cada cadena: 3
 
 2º Alcordar el sistema de numberación: <math>2^3-1 = 7</math>
 
 3º Estremar el mensaxe: 101 001 110 101
 
 4º Acomuñar cada cadena con un enteru: 5 1 6 5
 
 5º Sumar tolos valores y añader el númberu camudáu de signu: -17
 
 6º Unviar 5 1 6 5 -17 codificado en [[binariu]]

 El receptor:
 
 1º Suma tolos valores; si la suma ye 0, procesa'l mensaxe; si non, producióse un error.

Esti métodu al ser más senciellu ye óptimo pa ser implementáu en [[software]] yá que puede algamar velocidaes de cálculu similares a la implementación en hardware

=== Distancia de Hamming basada en comprobación ===

[[Ficheru:Hamming distance 4 bit binary example.svg|right|thumb|300px|[[Hipercubo]] binariu de dimensión cuatro.]]
Si queremos detectar d bit erróneos nuna pallabra de n bits, podemos añader a cada pallabra de n bits d+1 bits predeterminados a la fin, de forma que quede una pallabra de n+d+1 bits con una [[Distancia de Hamming|distancia mínima de Hamming]] de d+1. D'esta manera, si unu recibe una pallabra de n+d+1 bits que nun encaxar con nenguna pallabra del códigu (con una distancia de Hamming x <= d+1 la pallabra nun pertenez al códigu) detecta correutamente si ye una pallabra errónea. Entá ye más, d o menos errores nunca se van convertir nuna pallabra válida por cuenta de que la distancia de Hamming ente cada pallabra válida ye de siquier d+1, y tales errores conducen solamente a les pallabres inválides que se detecten correutamente. Dau un conxuntu de m*n bits, podemos detectar x <= d bits errores correutamente usando'l mesmu métodu en toles pallabres de n bits. Ello ye que podemos detectar un máximu de m*d error si toles pallabres de n bits son tresmitíes con un máximu de d errores.

; Exemplu:
 
Pallabres a unviar:
 
# 000001
# 000001
# 000010
 
==== Codificadas con distancia mínima de Hamming = 2 ====
 
:000001 0000
:000001 0011
:000010 1100
 
Si les pallabres recibíes tienen una distancia de Hamming < 2, son pallabres incorreutes.

== Llista de los [[Códigos detectores y correutores d'error|método de correición]] y detección d'errores ==

* [[Díxitu verificador]]
* [[FEC|FEC (Forward Error Correction)]]
* [[Códigu Binariu de Golay]]
* [[Códigu Hamming]]
* [[Bit de paridá]]
* [[Reed-Solomon]]

== Ver tamién ==
* [[Correición d'errores cuántica]]
* [[Recuperación de datos]]
* [[Corrupción de datos]]
* [[Automatic Repeat Request]]

== Referencies ==
{{llistaref}}

== Enllaces esternos ==

* Otros códigos utilizaos



{{Tradubot|Detección y corrección de errores}}

{{control d'autoridaes}}
[[Categoría:Detección y correición d'errores]]
[[Categoría:Protocolos]]