Técnicas de comunicación de datos digitales

En la sección anterior vimos que si se agrega algo  ( codeword  => Redundancia ) a un mensaje es posible recuperar pese a la existencia de errores el mensaje correcto.

En Teoría de la Información se denomina distancia de Hamming a la efectividad de los códigos de bloque y depende de la diferencia entre una palabra de código válida y otra.

Cuanto mayor sea esta diferencia, menor es la posibilidad de que un código válido se transforme en otro código válido por una serie de errores.

A esta diferencia se le llama distancia de Hamming, y se define como el número de bits que tienen que cambiarse para transformar una palabra de código válida en otra palabra de código válida.

 Figura 1

• d: Distancia de Hamming.
• v1: secuencia de bits 1.
• v2: secuencia de bits 2.

La distancia de Hamming es igual a 3 es este caso por que son 3 los bit distintos entre el conjunto v1 y v2.

Considérese ahora una técnica de código de bloque para corregir errores. Supóngase que se quiere transmitir un bloque de datos con longitud k bits.

En lugar de transmitir cada bloque de k bits, se asigna cada secuencia de entrada a una única palabra-código de n bits. 

Veamos como sería:

 Figura 2

Vemos que para la figura 2 la longitud de los bits a transmitir k=2 y la palábra código es n=5.

Ahora, supóngase que se recibe una palabra-código con el patrón de bits 00100. Ésta no es una palabra-código válida, por lo que el receptor detecta un error. ¿Puede ese error ser corregido?. No es posible asegurar qué bloque de datos fue transmitido ya que el ruido puede haber corrompido 1, 2, 3, 4, o incluso los 5 bits. ( Ver que esto sería el código de Hamming d ) 

Para transformar 00111 en 00100 se necesitarían  dos cambios, tres para transformar 11110 en 00100 y cuatro para transformar 11001 en 00100.

d(00000, 00100) = 1; d(00111, 00100) % 2; d(11110, 00100) = 3; d(11001, 00100) = 4; 

Por tanto, la regla a imponer sería que si se recibe una palabra-código inválida, entonces se selecciona la palabra-código válida más cercana (a distancia mínima). Esto funcionará sólo si hay una única palabra-código a la distancia mínima para cada palabra inválida.

Hay 2⁵ = 32 posibles palabras-código de las que sólo 4 son válidas, quedando 28 palabras-código inválidas. Para las palabras-código in-
válidas, se tiene lo siguiente:

 Figura 3

Vemos que hay 8 posibles candidatas cuando se produce un error en 2 bits en dos palabras de código diferentes .En estos caso no sería posible decidir cual es la palabra original, pero si detectaríamos un error.

Si se tiene un código de bloque (n, k), habrá 2^k palabras-código válidas de un total de 2ⁿ posibles.

Se define la redundancia del código como el cociente del número de bits redundantes entre el número de bits de datos

(n-k)/k

y se define la tasa del código como el cociente del número de bits de datos entre el número de bits totales, k/n.

 La tasa del código es una medida del ancho de banda adicional que se necesita para transmitir los datos a la misma velocidad que si no hubiera código.

La tasa del código es una medida del ancho de  banda adicional que se necesita para transmitir los datos a la misma velocidad que si no hubiera código. Por ejemplo, para transmitir a la misma velocidad, un código cuya tasa sea 1/2 necesitará el doble de capacidad de transmisión que un sistema que no utilice código.

En el código de nuestro ejemplo, la tasa es igual a 2/5 y, por tanto, necesita una capacidad 2,5 veces la de un sistema sin
codificación.

Por ejemplo, si la velocidad de transmisión de los datos a la entrada del codificador es de 1 Mbps, entonces la salida del codificador debe ser igual a 2,5 Mbps para poder trasmitir, ver que si es menor se acumulan bits en el Tx.

Generalizando lo que vimos, para un código constituido por s palabras-código w₁ , w ₂ , ..., w _s  ( donde s=2ⁿ  , n cantidad de bits) se define la distancia mínima del código, d _min como:

 Figura 4

Esto no es ni mas ni menos que la mínima distancia de Hamming de dos codeword.

Se puede demostrar ( no lo hacemos aquí ) que si existe un t que cumpla: 

  [Exp 1]

  el código puede corregir todos los errores de hasta t bits   => (d_min-1)/2 >=t  , con t mayor valor entero  

  [Epx 2]

 el código corregirá todos los errores de hasta t -1 bits y detectará los de t bits =>  d_min/2 >=t

Es más, si lo que interesa es sólo detectar errores y no corregirlos, entonces, el número de errores t que se pueden detectar, verifica que:
t = d_min -1  => de esta expresión podemos concluir:

1. Si se dan d_min errores, cualquier palabra-código puede convertirse en otra válida.( ver d=2 en figura 3) 
2. Cualquier número menor que d_min errores nunca convertirá una palabra-código válida en otra válida. ( ver d=1 en figura 3) 

Conclusiones.

El diseño de los códigos de bloque implica las siguientes consideraciones:

1. Dados unos valores n y k, sería deseable obtener el valor mayor posible de d_min .
2. El código debería ser relativamente fácil de codificar y decodificar, con requisitos mínimos de memoria y tiempo de procesamiento.
3. Sería deseable que el número de bits redundantes, (n-k), sea pequeño para reducir el ancho de banda.
4. Sería deseable que el número de bits redundantes, (n-k), sea grande para reducir la tasa de errores.

 Ver que 3 y 4 son contradictorias, por lo que es una situación de compromiso.

 Figura 4