Error detection and correction

De Departamento de Informatica
Saltar a: navegación, buscar

Las redes deben ser capaces de transferir datos de un dispositivo a otro con total exactitud para así mantener la consistencia, pues en caso contrario, si estos datos recibidos no son idénticos a los emitidos podemos decir que el sistema de comunicación es ineficaz e inútil, es por esto que cada vez que se transmite información o datos desde de un origen a un destino debemos tener presente que pueden corromperse en el camino. Es por esto, que los sistemas de comunicación deben poseer mecanismos para detectar y corregir estos errores que alteren o modifiquen los datos recibidos debido a los múltiples factores que pueden existir en la transmisión.

La detección y correción de errores o control de errores corresponde a un conjunto de técnicas las cuales permiten el mantenimiento e integridad de los datos a través de canales de comunicación poco confiables. La idea básica detrás de las ténicas de detección de errores en redes es agregar información redundante al paquete, para así determinar si un error ha sido introducido mientras se llevaba de un nodo a otro, mientras que la correción nos permitirá la reconstrucción de los datos originales.

Contenido

Introducción

La detección y corrección de errores de nivel bit son dos servicios ofrecidos a menudo por la capa de enlace. En esta wiki se mostrarán algunas de las técnicas más simples que pueden utilizarse para detectar, y en algunos casos, corregir estos errores de bit. Se revisará como funcionan algunas técnicas simples de detección y corrección de errores.

Figura 1: esquema de detección de errores de datos.

En la figura 1 de muestra un esquema de los elementos para el análisis a realizar. En el nodo emisor (a la izquierda), están los datos que hay que proteger frente a los errores de bit, D, que se complementan con una serie de bits de detección y corrección de errores (EDC, siglas para Error Detection Correction). Normalmente, los datos que hay que proteger incluyen un datagrama, los números de secuencia y otros campos. Tanto D como EDC se envían hacia el nodo receptor en una trama de la capa de enlace. Por otro lado, en el nodo receptor se recibe una secuencia de bits formada por D y EDC, pero esta secuencia puede diferir de las secuencias D y EDC originales, ya que las secuencias pueden haber sufrido alteraciones de los bits sufridas durante el tránsito.

En este contexto, el desafío es para el receptor y consiste en determinar si el D que recibió coincide con la secuencia D original, considerando que lo único que ha recibido son las secuencias D y EDC. Un importante hecho es mencionado en la figura 1, que muestra un símbolo de decisión en el que se pregunta si se ha detectado un error, no si se ha producido un error. En este sentido, es importante mencionar que las técnicas de detección y corrección de errores permiten al receptor detectar en ocasiones, pero no siempre, si se han producido errores en los bits. Incluso si se utilizan bits de detección de errores pueden seguir existiendo errores de bit no detectados, por lo que el receptor podría no estar consciente de que la información recibida tiene errores en los bits. La consecuencia es que el receptor podría entregar datos incorrectos a la capa de red. Entonces, se intentará elegir un esquema de detección de errores que tenga asociada una probabilidad pequeña de que se entreguen datos hayan sido corrompidos. En general, las mejores técnicas de detección de corrección de errores, esto es, aquellas con menor probabilidad de que se produzcan errores de bit no detectados, requieren más recursos en términos de cálculos y transmisión de datos.

Técnicas de detección

Paridad Simple

Este se basa en agregar a la palabra que se enviará un dígito cuyo valor dependerá de los valores de los dígitos que la conforman. Para esto existen dos métodos de control de paridad simple:

  • Paridad Par: Consiste en añadir un "1" si la palabra original contiene un número impar de unos, y un "0" en caso contrario. En todos los casos el emisor enviará palabras con un numero par de unos.
  • Paridad Impar: Consiste en añadir un "1" si la palabra original contiene un número par de unos, y un "0" en caso contrario. En todos los casos el emisor enviará palabras con un numero impar de unos.

De esta forma, si se produce un error en un bit, éste será detectado. Sin embargo, aunque este sistema es capaz de detectar un número impar de errores, no es capaz de detectar un número par de errores. A modo de ejemplo:

Se desea enviar la palabra 1001011 utilizando para esto la paridad impar. Luego el emisor envía la siguiente palabra codificada: 10010111
Sin embargo, se produce un error en el dígito número 2, con lo que llega: 10010101
El receptor sabrá que se ha producido un error porque la paridad de la palabra recibida es par.
Sin embargo, si se hubieran producido dos errores recibiendo la palabra "11010011", el receptor no detectaría ningún error.

Paridad Cruzada

Este método se basa en agrupar los bits en una matriz de N filas y K columnas, para luego realizar todas las paridades horizontales por el método anteriormente mencionado, y por último, realizar la misma operación de calcular el número de unos, pero ahora para las columnas. Una vez creada esta matriz, podemos enviarla por filas, o bien por columnas. Si enviamos las palabras por columnas aumentaremos la posibilidad de corregir una palabra que haya sufrido un error de rafága (errores que afectan a varios bits consecutivos, debidos a causas generalmente electrónicas, como chispazos, y que harían que se perdiera toda una palabra completa). A modo de ejemplo:

Debemos transmitir la palabra(con paridad par explicado anteriormente): 0010101111010100011011011010
Formamos la matriz de la siguiente forma:
0010101
1110101
0001101
1011010

Ahora añadimos los bits de forma horizonal:
0010101 1
1110101 1
0001101 1
1011010 0

Finalmente añadimos los bits de forma vertical:
0010101 1
1110101 1
0001101 1
1011010 0

0110111 1

Checksum de Internet

El algoritmo Checksum(suma de chequeo) de Internet se basa en la suma de todas las palabras de 16 bits que conforman el mensaje para luego transmitir, junto con el mensaje, el resultado de dicha suma (este resultado recibe el nombre de Checksum). Al llegar el mensaje a su destino, el receptor realiza el mismo cálculo sobre los datos recibidos, para luego comparar el resultado con el checksum recibido. Si cualquiera de los datos transmitidos (incluyendo el mismo Checksum) esta corrupto, entonces el resultado no concordará y el receptor sabrá que ha ocurrido un error.

Para poder aplicar este algoritmo en primer lugar debemos tomar los datos que serán procesados (es decir el mensaje) para luego acomodarlos como una secuencia de enteros de 16 bit, luegos estos enteros se suman utilizando aritmética complemento a uno para 16 bits y, para generar el Checksum, se toma el complemento a uno para 16 bits del resultado. Para revisar el checksum, la suma es calculada sobre la misma secuencia, incluyendo el campo de Checksum. Si el resultado es 16 bits con valor 1 (-0 en aritmética complemento a uno), el chequeo es correcto.

Para poder visualizar de mejor manera el algoritmo veamos el siguiente ejemplo:

Tenemos las siguientes secuencias:
0110011001100110
0101010101010101
0000111100001111

La suma de las dos primeras secuencias sería:
0110011001100110
0101010101010101
----------------
1011101110111011

Sumando la tercera secuencia con la anterior obtenemos:
1011101110111011
0000111100001111
----------------
1100101011001010

La suma complemento a uno de 1100101011001010 será 0011010100110101 (Checksum).
Finalmente el receptor recive estas 4 secuencias de 16 bits, estos deben ser sumados (las 3 secuencias y el Checksum) y el resultado debe ser 1111111111111111.
En caso que alguno de los bits sea cero, un error ha sido detectado

Códigos de redundancia cíclica (CRC)

Descripción

Es una técnica mas para la detección de errores, esta es usada ampliamente en las redes de computadores de hoy, los códigos CRC también se conocen como códigos polinómicos, dado que el string de bits que se transmite se puede ver como un polinomio donde los bits representan los coeficientes del polinomio y las operaciones aritméticas sobre este corresponderían a las operaciones tradicionales con polinomios (suma resta divicion), esta aritmética se realiza modulo 2.

Funcionamiento (codificación, detección de errores y decodificación)

Primero que todo tanto el emisor como el receptor deben acordar un string común de bits G, de r + 1 bits, este string se conoce como generador. Como condición adicional se pide que el bits mas significativo del string G sea 1 (el bits de mas a la izquierda). Por lo tanto, la codificación funciona así: el emisor toma una cadena D de d bits que desea transmitir y le adhiere a la cola un string R de r bits (por ende tenemos un string DR de d + r bits) los r bits se escogen de tal manera que el nuevo string DR sea divisible por G (en aritmética modulo 2) es decir que el resto sea 0. por tanto el receptor para verificar si la cadena recibida posee errores solo debe dividir el string recibido por G, si el resto es cero el receptor asume que la cadena no posee errores, y si el resto es distinto de cero el receptor descarta el string ya que este posee errores), para decodificar la cadena recibida solo se debe cortar del string DR de d + r bits sus ultimo r bits (que fueron los que se adhirieron para codificar) y de esa forma recuperamos el string D.

Determinación del string R

Entiéndase los string D, R y G como polinomios (donde el bit de mas a la izquierda es coeficiente del termino de mayor grado), y las operaciones siguientes conforme a las reglas aritméticas modulo 2.

Ejemplo: Supongamos D = 1101, entonces el polinomio que representa a D es x3 + x2 + 0x + 1, que es lo mismo como x3 + x2 + 1.

por lo tanto lo que se quiere es tener D * xr + R sea divisible por el polinomio G, lo que es lo mismo que:

D * xr + R = KG, para algún polinomio K.

lo que implica, D * xr = KG + R (recordemos que estamos en aritmética modulo dos y la suma y resta coinciden), Ahora si dividimos D * xr por G nos da que el resto es justamente R, por lo tanto para determinar la cadena R, solo debemos calcular el resto de dividir D * xr / G.


Tecnicas de correción

Las técnicas de corrección hacen referencia la la capacidad que tiene el receptor de un mensaje para reconstruir éste una vez detectado que el mensaje contiene errores. Estos métodos son de suma importancia en internet ya que mejoran de forma considerable el rendimiento de las redes al no tener que pedir la retransmisión de un mensaje cuando está corrupto. Algunos ejemplos de códigos importantes con capacidad de corregir errores son los códigos, códigos Hamming, paridad bidimensional, entre otros.

A modo de ejemplo ilustraremos como funcionan los códigos de paridad bidimensional. Estos códigos son una extensión de los códigos que implementan un bit de paridad simple, la ventaja de los códigos de paridad bidimensional es que estos puede corregir el error detectado (solo cuando existe error en 1 bit), sin embargo estos código de igual manera pueden detectar cuando hay mas de un error, no así con los códigos de paridad simple.

Códigos de paridad bidimensional

Uno ejemplo de técnicas de corrección es código de paridad bidimensional. El funcionamiento es el siguiente: se toma un string que se desee codificar, éste se divide en i filas y j columnas (análogo a cuando se construye una matriz bidimensional a partir de un array unidimensional). Luego, por cada columna y fila se agrega un bit, por tanto se tiene i + j + 1 bit (ver figura para aclarar). Entonces cuando se transmita ese string, el receptor solo tendrá que verificar si los bit de paridad concuerdan (recordamos que los bit de paridad son 1 cuando la cantidad de 1's es par y cero en otro caso). Luego, si existe un error, el bit de paridad asociado a la columna y fila correspondientes no concordará, y de esta forma se sabe que hubo un error y en que lugar, y se proceder a corregir. Ahora bien, si hemos detectado que existe mas de un error, perdemos la capacidad de corregir. Es fácil darse cuenta porque sucede lo anterior, aun así es útil tener la capacidad de detectar mas de un error en un mensaje aunque no se pueda corregir, lo que indica la robustez que puede tener determinado código a la hora de detectar errores.

Paridad.png


Algunas implementaciones

  • Comprobación de redundancia cíclica en lenguaje C.
#include <stdlib.h>
#include <stdio.h>
void main()
{
   int i,j,n,g,a,arr[20],gen[20],b[20],q[20],x[20],check,s;
   check=0;
   printf("\n\n\t ****** CYCLIC REDUNDANCY CHECK ****** ");
   printf("\n\t Transmitter side:");
   printf("\n\t Enter no. of data bits: ");
   scanf("%d",&n);
   printf("\n\t Enter the data to be sent: \n");
   for(i=0;i<n;i++)
      scanf("%d",&arr[i]);
   printf("\n\t Enter no. of divisor bits: ");
   scanf("%d",&g);
   do
   {
      printf("\n\t Enter the generator data: \n");
      for(j=0;j<g;j++)
      scanf("%d",&gen[j]);
   }
   while(gen[0]!=1);
   printf("\n\t The divisor is:");
   for(j=0;j<g;j++)
      printf("%d",gen[j]);
   a=n+(g-1);
   printf("\n\t The transmitter side data is:");
   for(i=0;i<j;++i)
      arr[n+i]=0;
   for(i=0;i<a;++i)
      printf("%d",arr[i]);
   for(i=0;i<n;++i)
      q[i]= arr[i];
   for(i=0;i<n;++i)
   {
      if(arr[i]==0)
      {
         for(j=i;j<g+i;++j)
         arr[j] = arr[j]^0;
      }
      else
      {
         arr[i] = arr[i]^gen[0];
         arr[i+1]=arr[i+1]^gen[1];
         arr[i+2]=arr[i+2]^gen[2];
         arr[i+3]=arr[i+3]^gen[3];
      }
   }
   printf("\n\t The CRC is :");
   for(i=n;i<a;++i)
      printf("%d",arr[i]);
   for(i=0;i<g-1;++i)
      x[i]=arr[i];
   s=n+a;
   for(i=n;i<s;i++)
      q[i]=arr[i];
   printf("\n");
   for(i=0;i<a;i++)
      printf("%d",q[i]);
   printf("\n\t Receiver side:");
   printf("\n\t Enter no. of data bits received: ");
   scanf("%d",&n);
   printf("\n\t Enter the data received: \n");
   for(i=0;i<n;i++)
      scanf("%d",&arr[i]);
   for(i=n,j=g-1;i<a,j<0;i++,j--)
      arr[i]=q[j];
   printf("\n\t The receiver side data is:");
   for(i=0;i<a;++i)
      printf("%d",arr[i]);
   for(i=0;i<n;++i)
      q[i]=arr[i];
   for(i=0;i<n;++i)
   {
      if(arr[i]==0)
      {
         for(j=i;j<g+i;++j)
         arr[j] = arr[j]^0;
      }
      else
      {
         arr[i] = arr[i]^gen[0];
         arr[i+1]=arr[i+1]^gen[1];
         arr[i+2]=arr[i+2]^gen[2];
         arr[i+3]=arr[i+3]^gen[3];
      }
   }
   printf("\n\t The CRC at the receiver is:");
   for(i=n;i<a;++i)
      printf("%d",arr[i]);
   s=n+a;
   for(i=n;i<s;i++)
      q[i]=arr[i];
   printf("\n");
   i=0;
   while(i<a)
   {
      if(q[i]==0)
         check=0;
      else
         check=1;
      i++;
   }
   printf("\n\n Result of CRC Error detection is: ");
   if(check==0)
      printf("\n\t Data is accepted successfully!");
   else
      printf("\n Resend the data again!");
}

Ejemplo de Entrada/Salida para el ejemplo anterior:

****** CYCLIC REDUNDANCY CHECK ******
Transmitter side:
Enter no. of data bits: 6
Enter the data to be sent:
1 0 0 1 0 0
Enter no. of divisor bits: 4
Enter the generator data:
1 1 0 1
The divisor is: 1101
The transmitter side data is:100100000
The CRC is: 001
100100001
Receiver side:
Enter no. of data bits received: 6

Enter the data received:
1 0 0 1 0 0
The receiver side data is:100100001
The CRC at the receiver is:000
100100000
Result of CRC Error detection is:
Data is accepted successfully!
  • Comprobación de paridad simple en lenguaje Java.

Reciever.java

/*
simple parity programm
this is reciever
reciver get the packet
extract the parity bit and message
recalculate parity bit and compare it
*/
import java.io.*;
import java.net.*;
public class Reciever{
   ServerSocket RecieverSocket;
   Socket connection = null;
   ObjectOutputStream out;
   ObjectInputStream in;
   String message,parity1,parity2;
   Reciever(){}
   void run()
   {
       try{
           BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
           //1. creating a server socket
           RecieverSocket = new ServerSocket(2004, 10);
           //2. Wait for connection
           System.out.println("Waiting for connection");
           connection = RecieverSocket.accept();
           System.out.println("Connection received from " + connection.getInetAddress().getHostName());
           //3. get Input and Output streams
           out = new ObjectOutputStream(connection.getOutputStream());
           out.flush();
           in = new ObjectInputStream(connection.getInputStream());
           sendMessage("Connection successful ...");
           //4. The two parts communicate via the input and output streams
           //do{
               try{
                   message = (String)in.readObject();
                   System.out.println("client>" + message);
                   parity1=message.substring(0,1);
                   parity2=String.valueOf(parity(message.substring(1)));
                   message=(parity1.equals(parity2))?"correct data":"corrupted data";
                   sendMessage(message);
               }
               catch(ClassNotFoundException classnot){
                   System.err.println("Data received in unknown format");
               }
           //}while(!message.equals("bye"));
       }
       catch(IOException ioException){
           ioException.printStackTrace();
       }
       finally{
           //4: Closing connection
           try{
               in.close();
               out.close();
               RecieverSocket.close();
           }
           catch(IOException ioException){
               ioException.printStackTrace();
           }
       }
   }
   int parity(String str){
       int n=Integer.valueOf(str);
       int len=str.length();
       int sum=0;
       for(int i=0;i<len;i++){
           sum+=n%10;
           n/=10;
       }
       return (sum%2);
   }
   void sendMessage(String msg)
   {
       try{
           out.writeObject(msg);
           out.flush();
           System.out.println("server>" + msg);
       }
       catch(IOException ioException){
           ioException.printStackTrace();
       }
   }
   public static void main(String args[])
   {
       Reciever server = new Reciever();
       while(true){
           server.run();
       }
   }
}

Sender.java

/*
   Simple parity programm
   this is sender
   data will send with parity bit
   packet=paritybit+message
*/
import java.io.*;
import java.net.*;
public class Sender{
   Socket requestSocket;
   ObjectOutputStream out;
    ObjectInputStream in;
    String message;
   boolean check=true;
   Sender(){}
   void run()
   {
       try{
           BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
           //1. creating a socket to connect to the server
           requestSocket = new Socket("localhost", 2004);
           System.out.println("Connected to localhost in port 2004");
           //2. get Input and Output streams
           out = new ObjectOutputStream(requestSocket.getOutputStream());
           out.flush();
           in = new ObjectInputStream(requestSocket.getInputStream());
           //3: Communicating with the server
           message = (String)in.readObject();
           System.out.println("server>" + message); 
           do{
               try{
                   System.out.println("Enter binary number to send:");
                   message = br.readLine();
                   if(checkbinary(message)){
                       check=false;
                       System.out.println("Parity bit >"+parity(message) );
                       message=String.valueOf(parity(message)).concat(message);
                       sendMessage(message);
                       }else{
                       System.out.println("Entered data is not in binary format.\n Re" );
                   }
               }
               catch(Exception classNot){
                   System.err.println("data received in unknown format");
               }
           }while(check);
           try{
           System.out.println("Data sent" );
           message = (String)in.readObject();
           System.out.println("server>" + message);
           }catch(Exception e){}    
       }
       catch(UnknownHostException unknownHost){
           System.err.println("You are trying to connect to an unknown host!");
       }
       catch(IOException ioException){
           ioException.printStackTrace();
       }
       catch(Exception e){}
       finally{
           //4: Closing connection
           try{
               in.close();
               out.close();
               requestSocket.close();
           }
           catch(IOException ioException){
               ioException.printStackTrace();
           }
       }
   }
   boolean checkbinary(String str){
       int n=Integer.valueOf(str);
       int len=str.length();
       int sum=0;
       for(int i=0;i<len;i++){
           sum=n%10;
           if(sum>1) return false;
       }
       return true;
      
   }
   int parity(String str){
       int n=Integer.valueOf(str);
       int len=str.length();
       int sum=0;
       for(int i=0;i<len;i++){
           sum+=n%10;
           n/=10;
       }
       return (sum%2);      
   }
   void sendMessage(String msg)
   {
       try{
           out.writeObject(msg);
           out.flush();
           System.out.println("client>" + msg);
       }
       catch(IOException ioException){
           ioException.printStackTrace();
       }
   }
   public static void main(String args[])
   {
       Sender client = new Sender();
       client.run();
   }
}

Notar que para este ejemplo se deben abrir dos terminales y ejecutar en primer lugar Reciever y luego Sender.

Referencias

Herramientas personales
Espacios de nombres
Variantes
Acciones
Navegación
Herramientas