Contents

Introducci’on

• Los c’odigos de correcci’on de errores son usados en tres situaciones muy concretas:
  1. Cuando no existe enlace de retorno, el receptor tiene que apoyarse en informaci’on extra (redundante) que le permita detectar y corregir los errores de transmisi’on. Dicha informaci’on la proporcionan los c’odigos de correcci’on de errores.
  2. Cuando la probabilidad de los errores de bit es alta y pr’acticamente, todas la tramas contienen algunos bits err’oneos.
  3. Cuando las latencias son muy altas. Por ejemplo, en una transmisi’on desde una nave espacial hasta La Tierra es preferible utilizar c’odigos de correcci’on de errores a tener que indicar a la nave que repita una transmisi’on.

• La idea que hay detr’as de estos c’odigos es la de crear “palabras” que se diferencien en una cantidad suficiente de bits, de manera que, aunque algunos hayan sido alterados, todav’ia sea posible el reconocimiento de la palabra enviada.
• El n’umero de bits que diferencian a dos palabras del c’odigo se llama distancia de Hamming¹ [1]. Por ejemplo, en un c’odigo binario natural de n bits de longitud existen hasta 2ⁿ palabras distintas y la distancia de Hamming es 1. Como puede verse, cuando la distancia es 1 entonces el c’odigo no permite detectar, ni a’un menos corregir, ning’un error, porque cualquier palabra con uno o m’as errores genera otra palabra del c’odigo.
• La capacidad de detecci’on y de correcci’on de errores de un c’odigo depende de su distancia de Hamming. En concreto, para detectar al menos d errores, se necesita una distancia igual a d + 1. Por ejemplo, el c’odigo 0000, 0011, 1100, 1111 tiene una distancia de Hamming igual a 2. Si se recibiera la palabra 1110, sabr’iamos que hay al menos un error y que las palabras que con m’as probabilidad fueron transmitidas son 1100 y 1111.² N’otese, sin embargo, que esta informaci’on es insuficiente para corregir el error porque ambas palabras son equiprobables.
• Sin embargo, para corregir d errores, se necesita una distancia de 2d + 1. Por ejemplo, el c’odigo 00000 00000, 00000 11111, 11111 00000, 11111 11111, tiene una distancia igual a 5, por lo que puede llegar a corregir hasta 2 bits err’oneos. Si se recibe la palabra 00010 11011, lo m’as probable es que se tratara de la palabra 00000 11111. Obs’ervese que nunca sabremos con certeza esto porque implicar’ia que sabemos que s’olo dos bits iban a ser invertidos durante la transmisi’on. Este factor es el que provoca que ning’un c’odigo de correcci’on de errores sea infalible.

1 Paridad 2D

• Consiste en añadir bits de paridad por filas y por columnas. En el ejemplo [2] mostrado en la Figura

  ---

  
  

  Figure 1: Paridad bidimensional (izquierda, c’alculo, derecha, correcci’on de un bit err’oneo).

  ---

  1 se utiliza paridad par y como puede verse permite corregir un error.

2 Hamming

• Hamming ide’o adem’as un sistema de codificaci’on que permite recuperar un n’umero de errores de transmisi’on por palabra transmitida arbitrariamente grande, aunque en esta secci’on se presenta (por motivos de simplicidad) el c’odigo que permite recuperar s’olo un bit err’oneo.
• Para hacer esto, entre los bits de datos se insertan bits de paridad, concretamente en las posiciones 2ⁱ siendo i ≥ 0. Como puede deducirse f’acilmente, si la trama contiene n de datos, entonces un c’odigo de Hamming introduce

  (1)

  de redundancia.

• Supongamos que el tamaño de los s’imbolos originales es de 7 bits (v’ease la Figura

  ---

  
  

  Figure 2: C’odigo de Hamming que corrige 1 bit erroneo en palabras de 7 bits.

  ---

  2). El c’odigo de Hamming inserta en las posiciones que son potencias de dos un bit de paridad.

  Para conocer si se ha producido un error de transmisi’on, el receptor recalcula los bits de paridad. Si no se ha producido ning’un error, los bits de paridad deben coincidir con los que viajan con los datos. Si ha ocurrido un error, los bits de paridad que cambian indican d’onde se ha producido el error. Por ejemplo, si el bit s’eptimo cambiara, de 1 a 0, el receptor va a apreciar que los bits de paridad r₁, r₂ y r₄ son diferentes a los que se reciben. Como es m’as probable que se produzca un error en un bit que en tres, supondr’a que el bit 7 (donde 7 = 1 + 2 + 4) es el bit err’oneo y lo corregir’a. En la Figura

  ---

  
  

  Figure 3: Ejemplo de correcci’on de un bit err’oneo usando un c’odigo de Hamming.

  ---

  3 se muestra dicho ejemplo de correcci’on.

References