Diferencies ente revisiones de «Deteición y correición d'errores»

← Edición más antigua Edición más nueva →

Contenido eliminado Contenido añadido

En renglón

Revisión a fecha de 19:47 7 pay 2018

En matemátiques, computación y teoría de la información, la detección y corrección d'erros 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.^[1]Considérase como precursor d'esti tipu de tecnoloxíes el Acme Comodity and Phrase Code usáu nos telegrames

Introducción

La comunicación ente delles computadoras produz de cutio un movimientu de datos, xeneralmente por canales non diseñaos pa esti propósitu (llinia telefónica), y qu'introducen un ruiu esternu que produz erros na tresmisión.

Poro, tenemos d'aseguranos que si dichu movimientu causa erros, éstos puedan ser detectaos. El métodu pa detectar y correxir erros ye incluyir nos bloques de datos tresmitíos bits adicionales denominaos redundancia.

Desenvolviéronse dos estrategia básiques pa remanar los erros:

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 corrección d'erros.

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

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ñedir 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 tantu añedimos 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 erru.

Problemes d'esti métodu:

Hai una alta probabilidá de que se colen casos nos qu'hubo erru, y que l'erru nun sía 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: $g(x)=x^{16}+x^{12}+x^{5}+1$

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

Añede tantos ceros pola 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:  $x^{4}+x+1$ 

Operaciones:

1º Llograr el polinomiu equivalente al mensaxe:  $x^{6}+x^{5}+x^{3}+1$ 

2º Multiplicar el mensaxe por  $x^{4}$  (añedir 4 ceros pola derecha):  $x^{10}+x^{9}+x^{7}+x^{4}$ 

3º Estremar en binariu'l mensaxe pol polinomiu xenerador y sacar el restu:  $x^{2}+1$ 

4º Concatenar el mensaxe col restu (en módulu 2 tamién):  $x^{10}+x^{9}+x^{7}+x^{4}+x^{2}+1$ 

5º Tresmitir el mensaxe

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

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 erros
3.2 Procesar el mensaxe 3.1

Si'l restu ye distintu de cero, significa que se producieron erros
3.2 Reenviar el mensaxe 3.2

Intentar correxir los erros por aciu los códigos correctores

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

Erros simples: toos Erros dobles: toos Erros nes posiciones impares de los bits: toos Erros 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

Ye un métodu senciello pero eficiente namái con cadenes de pallabres d'un llargor pequenu, ye por esto que se suel utilizar en 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 $2^{L}-1$ . De siguío súmase'l valor de toles pallabres nes que s'estrema'l mensaxe, y añedir 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 erros.

Exemplu:

Mensaxe 101001110101

1º Alcordar el llargor de cada cadena: 3

2º Alcordar el sistema de numberación:  $2^{3}-1=7$ 

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ñedir 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 erru.

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

Si queremos detectar d bit erróneos nuna palabra de n bits, podemos añedir a cada palabra de n bits d+1 bits predeterminados a la fin, de forma que quede una palabra de n+d+1 bits con una distancia mínima de Hamming de d+1. D'esta manera, si unu recibe una palabra de n+d+1 bits que nun encaxar con nenguna palabra del códigu (con una distancia de Hamming x <= d+1 la palabra nun pertenez al códigu) detecta correchamente si ye una palabra errónea. Entá ye más, d o menos erros nunca se van convertir nuna palabra válida por cuenta de que la distancia de Hamming ente cada palabra válida ye de siquier d+1, y tales erros conducen solamente a les pallabres inválides que se detecten correchamente. Dáu un conxuntu de m*n bits, podemos detectar x <= d bits erros correchamente 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 erros.

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 incorrectes.

Llista de los método de corrección y detección d'erros

Ver tamién

Referencies

↑ G. J. Simmons, "A survey of Information Authentication". Contemporary Cryptology, The science of information integrity, ed. GJ Simmons, IEEE Press, New York, (1992)

Enllaces esternos

Otros códigos utilizaos

[simmons-1] G. J. Simmons, "A survey of Information Authentication". Contemporary Cryptology, The science of information integrity, ed. GJ Simmons, IEEE Press, New York, (1992)

[1]

@@ Llinia 73: / Llinia 73: @@
 º Comprueba'l restu de dicha operación
 .1 Si'l restu ye cero, nun se producieron erros
 .2 Procesar el mensaxe 3.1
-  Si'l restu ye distintu de cero, significa que se producieron erros
+ Si'l restu ye distintu de cero, significa que se producieron erros
 .2 Reenviar el mensaxe 3.2
-  Intentar correxir los erros por aciu los códigos correctores
+ Intentar correxir los erros por aciu los códigos correctores
 En resume, esti métodu rique d'un polinomiu xenerador que, escoyíu correchamente, puede llegar a detectar gran cantidá d'erros:
@@ Llinia 89: / Llinia 89: @@
 {{main|suma de verificación}}
-Ye un métodu senciello pero eficiente namái con cadenes de palabres d'un llargor pequenu, 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.
+Ye un métodu senciello pero eficiente namái con cadenes de pallabres d'un llargor pequenu, 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 palabres nes que s'estrema'l mensaxe, y añedir la resultancia al mensaxe a tresmitir, pero camudáu de signu.
+De siguío súmase'l valor de toles pallabres nes que s'estrema'l mensaxe, y añedir 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 erros.
@@ Llinia 121: / Llinia 121: @@
 [[Archivu:Hamming distance 4 bit binary example.svg|rigth|thumb|300px|[[Hipercubo]] binariu de dimensión cuatro.]]
-Si queremos detectar d bit erróneos nuna palabra de n bits, podemos añedir a cada palabra de n bits d+1 bits predeterminados a la fin, de forma que quede una palabra 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 palabra de n+d+1 bits que nun encaxar con nenguna palabra del códigu (con una distancia de Hamming x <= d+1 la palabra nun pertenez al códigu) detecta correchamente si ye una palabra errónea. Entá ye más, d o menos erros nunca se van convertir nuna palabra válida por cuenta de que la distancia de Hamming ente cada palabra válida ye de siquier d+1, y tales erros conducen solamente a les palabres inválides que se detecten correchamente. Dáu un conxuntu de m*n bits, podemos detectar x <= d bits erros correchamente usando'l mesmu métodu en toles palabres de n bits. Ello ye que podemos detectar un máximu de m*d error si toles palabres de n bits son tresmitíes con un máximu de d erros.
+Si queremos detectar d bit erróneos nuna palabra de n bits, podemos añedir a cada palabra de n bits d+1 bits predeterminados a la fin, de forma que quede una palabra 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 palabra de n+d+1 bits que nun encaxar con nenguna palabra del códigu (con una distancia de Hamming x <= d+1 la palabra nun pertenez al códigu) detecta correchamente si ye una palabra errónea. Entá ye más, d o menos erros nunca se van convertir nuna palabra válida por cuenta de que la distancia de Hamming ente cada palabra válida ye de siquier d+1, y tales erros conducen solamente a les pallabres inválides que se detecten correchamente. Dáu un conxuntu de m*n bits, podemos detectar x <= d bits erros correchamente 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 erros.
 ; Exemplu:
-Palabres a unviar:
+Pallabres a unviar:
 # 000001
@@ Llinia 137: / Llinia 137: @@
 :000010 1100
-Si les palabres recibíes tienen una distancia de Hamming < 2, son palabres incorrectes.
+Si les pallabres recibíes tienen una distancia de Hamming < 2, son pallabres incorrectes.
 == Llista de los [[Códigos detectores y correctores d'error|método de corrección]] y detección d'erros ==