Hamming


Distancia de Hamming, Peso de Hamming, Espacio de Hamming, Esferas de Hamming, Distancia Mínima de Hamming, Hamming, Hamming ¡Hamming por todas partes! Conceptos esenciales para entender como funciona un código corrector de errores, sea cual sea y no solo el propio "Código Hamming" (artículo sobre "Código Hamming" que recomiendo que leas antes que este otro, puedes hacer click aquí para verlo). Como una buena película, seguro que te acogerá y sorprenderá en más de un detalle.

Nota sobre la redacción de este artículo: No pretende ser un trabajo ni matemático ni científico, solo quiere dar a conocer en terminos sencillos conceptos “Complejos” sobre los términos de los que trata este artículo.

 

Distancia de Hamming

La “distancia de Hamming” son los pasos que hay que dar para convertir algo en otro algo.

Por ejemplo, para convertir la palabra “Casa” en otra palabra diferente:

  • Casa” en “Masa” ha cambiado una letra (un paso), por lo que la distancia de Hamming es 1.
  • Casa” en “Mapa”, la distancia de Hamming es de 2.
  • Casa” en “Mopa”, la distancia de Hamming es de 3.
  • Casa” en “Mopx”, la distancia de Hamming es de 4.

Para binario, la “distancia de Hamming” son los bits que cambian de un grupo de bits a otro grupo de bits.

Empecemos de menos a más. Si tenemos un bit, por ejemplo, el 0 y se cambia a 1, la distancia de Hamming es de 1; la misma distancia si se cambia de 1 a 0.

Nota sobre las siguientes imágenes: En las siguientes imágenes pinto a la izquierda la tabla con los bits ordenados, y a la derecha en azul el grafo con la representación espacial de los bits al cambiar unos por otros.

distancia-de-hamming-con-1-dimension-www-jarroba-comTe habrás fijado que he dibujado una línea azul desde el 0 al 1. Cada línea azul representará 1 cambio o 1 paso de distancia (realmente por teoría de grafos se cuenta en aristas; es decir, las líneas rectas que van de un punto/nodo a otro que une. Sin que sirvan de confusión quiero llamar a las aristas pasos para representar la distancia, pues al andar como personas, cuantos más pasos damos, mayor es la distancia desde el origen. Así que aquí hablando: 1 paso = 1 arista).

Ahora vamos a ver los mismo, pero con 2 bits. Tendríamos lo siguiente:

distancia-de-hamming-con-2-dimensiones-www-jarroba-comCon esto las uniones azules de los bits nos han pintado un cuadrado.

¿Antes una línea ahora un cuadrado, con 3 bits pintará un cubo? Veámoslo:

distancia-de-hamming-con-3-dimensiones-www-jarroba-comNota sobre los colores azules de los nodos y aristas: El color azul oscuro quiere ayudar en la visualización del dibujo del cubo de las partes ocultas en dimensiones superiores a las pintadas sobre la pantalla (en papel o en la pantalla donde lo estás viendo dibujado, solo se pueden pintar en 2 Dimensiones, pero podemos representar las que queramos). Si bien podría interpretarse el dibujo tridimensional del cubo desde otra perspectiva, quise ayudar al ojo a obtener una representación mental rápida del cubo en 3D (3 Dimensiones); de este modo, el azul oscuro es la parte oculta del cubo, y el azul claro la parte que se ve directamente. Y ya la siguiente imagen en 4D (4 Dimensiones) que representa un teseracto (podríamos decir que es un cubo de 4 Dimensiones) pintado en un papel de 2D (2 Dimensiones), he querido facilitar un poco la visualización ya de por sí compleja de imaginar por encontrarse una dimensión por encima de las 3D a las que estamos acostumbrados.

Y para 4 bits, ya nos vamos a una dimensión por encima de la nuestra, a las 4 dimensiones y pintaríamos un teseracto (si te imaginas un cubo real en 3D, realmente ninguna arista corta a otra pese a que esté pintado en 2D sobre el papel; el teseracto tampoco corta ninguna arista a otra, aunque su representación en 2D y 3D se corten. Y como el cubo, el área contenida dentro de cuatro aristas forma un plano cuadrado que es siempre la cara exterior de la figura geométrica):

distancia-de-hamming-con-4-dimensiones-www-jarroba-comPese a la curiosidad de las líneas, cuadrados, cubos, teseracto y otros hipercubos (cualquier cubo de N Dimensiones es un hipercubo; es decir, un punto es un hipercubo de 0 Dimensiones, una línea es un hipercubo de 1 Dimensión, un cuadrado es un hipercubo de 2 Dimensiones, y así indefinidamente), para la Distancia de Hamming lo que más nos interesa es el grafo que dibuja y las aristas/pasos entre nodos/puntos; y entender al menos unas bases el concepto de las dimensiones.

Nota respecto a la simbología de las fórmulas: represento el “elevado a” con el acento circunflejo “^”. Por ejemplo, 2 elevado a 3 = 2^3 = 8

La gracia de las combinaciones de bits es que representan cubos N Dimensionales. Es decir, seguiría la fórmula que responde a ¿Cuántos puntos (“intersecciones de las aristas”) tiene un cubo, línea cuadrado, etc? Que son 2^N, siendo N las Dimensiones. De este modo para 1 bit son 2^1 = 2 combinaciones de bits, para 2 bits son 2^2=4 combinaciones de bits, para 3 bits son 2^3=8 combinaciones de bits, etc.

Como puedes comprobar, se puede representar en el espacio dimensional los pasos que definen la “distancia de Hamming”. Por lo que el número de dígitos de la palabra (la cantidad de bits) son las “Dimensiones” del espacio con el que trabajamos (Es el llamado “Espacio de Hamming”, pero lo veremos más adelante). Que, por cierto, si te fijas cada grupo de bits está en un punto azul, pues bien, cada combinación diferente en el espacio se llama precisamente “Punto” (en las imágenes de arriba de las dimensiones, la tabla de la izquierda contiene todos los puntos del espacio de N-Dimensiones).

 

Distancia de Hamming entre dos puntos

Quedémonos en el espacio de 2 Dimensiones (2 bits). Si queremos ir del punto 00 al punto 01 ¿Cuál será la Distancia (“Distancia de Hamming”)?

La Distancia de ir del punto 00 al punto 01 es de 1 (1 arista recorrida).

distancia-de-hamming-1-con-2-dimensiones-www-jarroba-com

¿Y la “Distancia de Hamming” de ir del punto 00 al punto 11?

distancia-de-hamming-2-con-2-dimensiones-www-jarroba-com

La Distancia de ir del punto 00 al punto 11 es de 2 (2 aristas recorridas).

Ahora te puedo preguntar ¿Y con 3 Dimensiones la “Distancia de Hamming” de ir del punto 100 al punto 011?

distancia-de-hamming-3-con-3-dimensiones-www-jarroba-comLa Distancia de ir del punto 100 al punto 011 es de 3 (3 aristas recorridas).

 

Distancia mínima de Hamming

¿En el cubo de 3 Dimensiones se me ocurre que podría ir por un camino más largo y tener más aristas/pasos recorridos que solo 3? Aquí depende de si queremos obtener la “Distancia Máxima de Hamming”, “Cualquier Distancia de Hamming” o la “Distancia Mínima de Hamming”.

Da igual que camino escojamos en el grafo, pero lo que verdaderamente nos interesa es laDistancia Mínima de Hamming”, siempre es el camino mínimo entre dos puntos/nodos. Es decir, la “Distancia Mínima de Hamming” mide el menor número de sustituciones (de los símbolos con los que trabajemos, en el caso de las imágenes de los últimos ejemplos los símbolos son 0 y 1) requeridos para cambiar algo a otro algo (para ir de un punto a otro).

La “Distancia Mínima de Hamming” máxima de N Dimensiones; es decir, ir de un punto a su más lejano con las dimensiones que sean, su camino mínimo corresponderá con el número de las dimensiones (un ejemplo, en la imagen del cubo anterior, el punto más alejado de 100 era el 011, y su camino mínimo para conectar ambos puntos era de 3 aristas, que coincide con las 3 Dimensiones con las que trabajamos).

En nuestra necesidad está si queremos conocer la mínima distancia, la máxima distancia, o una distancia intermedia. Lo normal es que nos interese la “distancia mínima de Hamming”, es decir, cuántos símbolos (símbolos me refiero a “letras” entre dos palabras; o bien, “0s” o “1s” entre dos códigos binarios; jeroglíficos entre dos frases en egipcio antiguo; etc) es el mínimo que hay que cambiar para que NO podamos ni detectar ni corregir errores.

La “distancia de Hamming” sirve para conocer la eficiencia tanto de códigos detectores de errores, como códigos correctores de errores, o hasta qué distancia podemos corregir un error o simplemente detectarlo. Siempre podremos asegurar una “distancia mínima de Hamming” para corregir o detectar los errores. A partir de este mínimo ya no se puede asegurar la corrección o detección (veremos ejemplos más adelante sobre esto).

 

Peso de Hamming

Por cierto, la “Distancia de Hamming” entre dos puntos A y B, también se conoce como el “Peso de Hamming” a la diferencia entre dos puntos (A – B). Es otra forma de determinar la longitud del camino (la cantidad de aristas) entre dos nodos/puntos. Pero es lo mismo, da como resultado la “Distancia de Hamming” (Por ejemplo, la “Distancia de Hamming” entre un objeto que pesa 7 Kilogramos y otro de 2 Kilogramos es de 5 Kilogramos, que es lo mismo que el “Peso de Hamming” 7 – 2 = 5).

Para calcular la diferencia de peso entre dos números binarios, su peso es la cantidad de unos de cada número binario. Para calcular el peso entre dos puntos se aplicará la función XOR (como resta de pesos) a los pesos de esos dos puntos.

Por ejemplo, en el anterior ejemplo de 3 Dimensiones queremos conocer el peso entre cualquiera de sus dos puntos. Calculamos el peso de cada punto sumando la cantidad de 1s de dicho punto (Represento el peso de cada punto con el símbolo de una pesa gris a su lado; recuerdo que el decimal 3 en binario es 11, 2 en binario es 01, 1 en binario es 01 y 0 en binario es 00):

pesos-de-puntos-en-3-dimensiones-www-jarroba-comAhora queremos conocer el peso entre los puntos 100 y 011. El peso de 100 es de 01 (1 en decimal), y el peso de 011 su peso es de 10 (2 en decimal).

Restaríamos sus pesos con XOR (más ejemplos de XOR en el artículo de Dígito de control – Detección de errores):

01 XOR 10 = 0 XOR 1 y 1 XOR 0 = 11

11 binario que es 3 en decimal, por lo que el “Peso de Hamming” es 3 (lo mismo que la “Distancia de Hamming” que vimos previamente).

 

Espacio de Hamming

El espacio de Hamming son todas las combinaciones de cadenas de bits del mismo tamaño (“códigos de bloque lineales” por ser todos del mismo tamaño). Es decir, son todos los puntos de una dimensión N (por ejemplo, para binario abría un total de 2^N puntos/combinaciones en el “Espacio de Hamming”).

¿Por qué se llama “Espacio”? Piensa en los planetas, en las estrellas, en todo aquello que nos rodea están en el “Espacio”. Ahora supongamos que vivimos en un espacio finito que solo tiene unos pocos planetas, y nada más que esos pocos planetas. A estos planetas, que son elementos del Espacio, los llamaremos “Puntos”, que son puntos finitos. Entonces, cualquier grupo de planetas de este espacio lo llamaremos código y a los elementos de cada código lo llamaremos “Palabras del código” (del inglés “CodeWord”). Ahora los planetas sustitúyelos por los bits que se generan por aplicar el “Código de Hamming” a cada mensaje de todas las posibilidades con la misma “longitud de mensaje” (¿Raro? continúa leyendo).

Pongamos el ejemplo del anterior artículo sobre códigos de Hamming de “Hamming(7,4)”, donde cada posible “Mensaje” ocupa 4 bits de “Longitud del Mensaje”. Como vimos anteriormente, podemos elegir uno de esos “Mensajes” y convertirlo en un “Bloque del código” que tendrá una “Longitud del Bloque” de 7 (al sumar los 3 bits de Paridad).

ejemplo-de-dato-con-bits-de-paridad-www-jarroba-comAhora si hacemos esto con todos los posibles Mensajes de “Hamming(7,4)” tenemos (en la siguiente imagen, donde pongo “Código Hamming” es que he realizado el “Código de Haming” a cada “Mensaje” de la izquierda, para conseguir el “Código del bloque” de la derecha):

conversion-de-4-a-7-bits-con-el-codigo-de-hamming-www-jarroba-comFácil y sencillo, ya sabemos hacerlo con soltura, tanto que podemos sacar las siguientes propiedades del ejemplo (la manera en la que escribo las fórmulas es, primero el título, la igualo al nombre de la variable que suele ser una letra, luego lo igualo a la fórmula o fórmulas, y por último lo vuelvo a igualar al valor para este ejemplo; si has entendido hasta aquí, te aseguro que las fórmulas son muy sencillas y tan lógicas que podrías deducirlas fácilmente, te lo aseguro 😉 ):

  • Bits de paridad = r = 3 bits de paridad
  • Longitud del bloque (el tamaño del Mensaje junto con los bits de paridad necesarios para cumplir el “código de Hamming”) = n = 2^r – 1 = 2^3 – 1 = 7
  • Longitud del mensaje (el tamaño del Mensaje) = k = n – r = 2^r – r – 1 = 2^3 – 3 – 1 = 4

 

Longitud de cada parte

Diferenciamos dos tipos de longitudes, las del dato sin procesar por el codificador (Un codificador es por ejemplo el “código Hamming”) y la longitud del dato ya procesado por el codificador.

Cuando decimos, por ejemplo Hamming(7, 4), indicamos primero la longitud del “Bloque del código” (llamaremos con la letra “n”) y luego la “Longitud del Mensaje” (distinguiremos con la letra “k”). Por lo que para cualquier “Hamming(n, k)” tendremos una longitud del bloque “k” y una longitud del mensaje “n” que se cumplirá para “r” “Bits de Paridad”.

dimensiones-de-las-palabras-www-jarroba-comResumo todo lo que tenemos y pongo un ejemplo de datos para Hamming(7, 4) dados los bits de paridad:

  • Bits de paridad = r = 3 bits de paridad
  • Mensaje” o “Secuencia de Datos” (“Data Sequence”): normalmente el trozo de lo queremos enviar
  • Longitud del mensaje (el tamaño del Mensaje) = k = n – r = 2^r – r – 1 = 2^3 – 3 – 1 = 4
  • Bloque del código” (“Block Code”): El resultado de aplicar un codificador al mensaje para que le añada bits de redundancia
  • Longitud del Bloque del código” (el tamaño del Mensaje junto con los bits de paridad necesarios para cumplir el “código de Hamming”) = n = 2^r – 1 = 2^3 – 1 = 7

Recuerdo que cuando mandamos el “Bloque del código” por cualquier medio a otro lado ya se llama “Palabra del código”, que debería de ser igual al “Bloque del código” (salvo transformaciones/errores producidos por el camino). Al final se llaman “Palabras del Código” por dos razones, la principal por haber sido enviado por el medio (por ejemplo, Internet); y dos, a razón de que puede llegar algo diferente al destino que cuando se generó el “Bloque del código” (por errores introducidos por el camino/medio).

 

Hasta aquí no he dicho nada raro.

En el “espacio de Hamming” todas las “palabras del código” son del mismo tamaño (tienen la misma cantidad de bits, en este ejemplo todas las palabras tienen 7 bits, se dice algebraicamente que es un “sub-espacio lineal”), por lo que se dice que el “código de Hamming” es un código lineal. Como todas las palabras tienen idéntico tamaño, a cada palabra de la llama “Código del bloque” (del inglés “block code”); se las llama así para diferenciarlas de los códigos/palabras de longitud variable.

Ahora un interludio para descansar un poco de tanto número.

 

Un ejemplo aclaratorio con el idioma español

Los elementos del alfabeto son: A, B, C, D, E, F, G, H, I, J, K, L, M, N, Ñ, O, P, Q, R, S, T, U, V, W, X, Y, Z.

Contando el total de elementos obtenemos el tamaño del alfabeto que es de: 27

Las “palabras del código” (del inglés “code word”) del idioma español serán todas las que existen en el diccionario de la RAE (el diccionario de las palabras españolas; si tienes curiosidad lo puedes consultar en http://www.rae.es/). Podemos empezar a poner cada palabra del diccionario hasta la última: A, AD, AH, AJ, <…Aproximadamente 93000 palabras más …>, ZUZÓN. Por lo que el conjunto de palabras, o “palabras del código”, escritas con los símbolos del alfabeto, serán todas las palabras con las que trabajaremos, será nuestro diccionario de palabras, nuestro espacio.

Para este ejemplo tendríamos las siguientes propiedades:

  • Alfabeto = 27
  • Elementos = A, B, C, D, E, F, G, H, I, J, K, L, M, N, Ñ, O, P, Q, R, S, T, U, V, W, X, Y, Z
  • “Palabras del código” = 93000 Aproximadamente
  • Longitud de las palabras (cantidad de letras de la palabra) = variable, entre 1 (por ejemplo, la palabra “a”) y 23 (la palabra “electroencefalografista”)

Curiosidad: Las palabras del diccionario de la RAE no hace un “sub-espacio lineal”, pues no tienen todas las palabras la misma cantidad de letras.

 

Después del interludio creo que puedes deducir las siguientes propiedades del “Espacio de Hamming” para este ejemplo:

  • Alfabeto = Q = 2 (porque estamos trabajando con binario, que son dos símbolos, el 1 y el 0). También llamado “Bloque del código binario” (del inglés “Binary block code”)
  • Elementos = q = 0 y 1
  • Palabras del código” (Cantidad de códigos de bloque del Espacio de Hamming) = C = 2^k = 2^4 = 16

Como es lógico, la cantidad de “Palabras del código” y los “Mensajes” coinciden, pues un “Mensaje” genera un único “Bloques del código” (ver imagen anterior).

Analicemos un poco más poniendo a nuestro amigo como conejillo de indias. Si mandamos un “Bloque del código” a nuestro amigo por Internet con “Hamming(7,4)”, le tiene que llegar un código de 7 bits, que puede haberse introducido errores o no, y le llegaría una de estas posibilidades:

  • Cantidad de posibilidades con 7 bits = 2^n = 2^7 = 128

Son muchas en comparación con las 16 “Bloque del código” que entendemos como “buenas”, aunque realmente si hemos mandado un mensaje a nuestro amigo, solo existe 1 posibilidad como buena (Si le envío la palabra “Hola” quiero que mi amigo reciba “Hola”, no otra palabra válida).

Los códigos válidos o correctos, llamados “Bloque del código”. Si enviamos cualquier “Bloque del código” a otro ordenador y resulta que el otro ordenador recibe un código inválido, será reconocido como erróneo. Sin embargo, si enviamos cualquier “Bloque del código” válido, y por el camino se convierte en otro válido, el ordenador de nuestro amigo lo reconocerá como código correcto.

 

La distancia de Hamming con el "Código de Hamming"

Recuerdo la pregunta formulada anteriormente “¿El código de Hamming hasta cuantos bits puede corregir?”. Podemos entender que la “distancia de Hamming” es la diferencia entre un código que se valida como código correcto y otro código correcto. Es decir, teniendo un código correcto, vamos cambiando los bits correctos por bits erróneos -y recalculamos con la fórmula anterior (el código de Hamming)- hasta que la fórmula nos vuelva a indicar que es un código correcto.

Nota sobre las “Matrices Síndrome”: las explicaciones son una extensión al artículo anterior de Hamming, utilizo “Matrices Síndrome” propias que ya se explicaron en ese otro artículo.

Pongamos un ejemplo rápido. Queremos enviar al ordenador de nuestro amigo la siguiente secuencia de bits (el dato con los bits de paridad incluidos).

distancia-hamming-datos-correctos-con-comprobacion-a-enviar-www-jarroba-comPero el ordenador de nuestro amigo recibe el dato erróneo/corrupto. Lo que el ordenador de nuestro amigo no sabe es cuántos errores hay o si quiera hay algún error (en la imagen he marcado en rojo los errores; el ordenador de nuestro amigo no verá nada marcado de ningún color, es decir, para su ordenador todos los bits podrían estar o bien o mal).

distancia-hamming-datos-recibidos-con-comprobacion-www-jarroba-comDe este modo el ordenador de nuestro amigo comprueba con el código Hamming si hay errores.

distancia-hamming-matriz-de-decuccion-que-da-por-correcto-un-codigo-erroneo-www-jarroba-comEl ordenador de nuestro amigo deduce que la secuencia de bits es correcta, está convencido completamente, pues no detecta ningún error (de este modo ni se intenta corregir, ni se vuelve a pedir la cadena de bits, pues se da por buena dicha secuencia de bits).

Si el dato confundido como correcto fuera parte de, por ejemplo, un fichero ejecutable (como cuando descargamos un juego o un programa), al intentar ejecutarlo saltaría un error indicándonos algo como “el fichero está corrupto vuelve a descargarlo”; o si fuera parte de una imagen, esa parte de la imagen aceptada como correcta se vería mal. Esto es debido a que se ha tomado como correcta una secuencia de bits que no es la que se envió.

Con el anterior ejemplo, la distancia de Hamming para “Hamming(7,4)” es: poner un bit erróneo y comprobar con el método de Hamming, nos dirá que no es correcto; añadir otro bit erróneo más junto al anterior, volver a comprobar y nos dirá que es incorrecto; otro tercer bit erróneo, y la comprobación nos dirá que tampoco es correcto; y el cuarto bit erróneo que pongamos, comprobaremos que efectivamente, el método de Hamming nos dice que es “correcto” (este último paso es el ya visto en la imagen anterior). 4 bits hemos tenido que cambiar, por lo que la distancia de “Hamming(7,4)” es de 4 (no confundir con el 4 del nombre “Hamming(7,4)”).

Por tanto, cuanto mayor sea la “distancia de Hamming” mayor será la posibilidad de detectar y corregir errores.

 

Analicemos Hamming(7,4)

Para “Hamming(7,4)”, siendo el segundo número las dimensiones antes de aplicar Hamming y el primer número las dimensiones después de aplicar Hamming.

Si queremos enviar cualquier mensaje por Internet al ordenador de nuestro amigo, dividiríamos el mensaje en trozos de 4 bits (“Secuencia de Código”). Cada uno de estos 4 bits solo puede corresponder con alguna de la siguiente tabla de 4 Dimensiones (4 bits de datos):

4-dimensiones-en-el-espacio-de-hamming-www-jarroba-comCon 4 bits son 2^4 = 16 combinaciones posibles.

Antes de enviar cualquier mensaje a nuestro amigo, tenemos que aplicar el “Código Hamming” a la “Secuencia de Código” elegida.

Para cualquier combinación después de aplicar el “Código Hamming” tendríamos cadenas de 7 bits (bits de datos más paridad). Cada “Secuencia de Código” de 4 bits de datos, se convierte en un “Bloque del Código” de 7 bits.

conversion-de-4-a-7-bits-con-el-codigo-de-hamming-www-jarroba-comCuando nuestro amigo reciba cualquier “Palabra del código” puede haberse transformado por el camino (por cualquier cosa, como una tormenta, o por la calidad de los cables por los que se transportó, etc).

Es decir, nuestro amigo puede recibir cualquiera de las siguientes combinaciones de la derecha de 7 Dimensiones (7 bits de datos). Donde solo 16 “Palabras del código” corresponden con los “Bloque del Código” anteriores correctos (los pintados de púrpura en la siguiente imagen); el resto de “Palabras del código” al aplicar el “Código de Hamming” al revés (para localizar si hay errores o no) nos dará como datos erróneos (los pintados de rojo en la siguiente imagen):

conversion-de-4-a-7-bits-del-espacio-de-hamming-con-el-codigo-de-hamming-y-las-comibinaciones-posibles-de-error-www-jarroba-com

Hagamos un juego antes de continuar.

 

Juego de los errores

Para mejor comprensión recomiendo seguir el siguiente juego de simulación de lo que hace un ordenador para comunicarse con otro:

  1. Revisa la imagen anterior.
  2. Elige una “Secuencia de Código” de bits de 4 Dimensiones (1 fila cualquiera de la columna de bits de la izquierda)
  3. Mediante el “Código de Hamming” (y así practicas 😉 ) conviértelo para añadirle los bits de paridad y tener el “Bloque del Código” de 7 bits (o sigue la flecha hasta la columna del centro con el “Espacio de Hamming, y acuérdate de la combinación de bits a la que apunta).
  4. Ahora piensa que envías ese “Bloque del Código” de 7 bits a tu amigo. Nuestro amigo espera un código cualquiera de 7 dimensiones (de la columna derecha con errores o sin errores).
  5. Vamos a simular que pueden introducirse un número cualquiera de errores durante el envío del “Bloque del Código” a nuestro amigo. Para ello cierra los ojos y con el dedo aleatoriamente elige una fila de 7 bits en la columna de la derecha gigante. Donde caiga el dedo será lo que le ha llegado a nuestro amigo (con más o menos errores). Nuestro amigo habrá recibido una “Palabra del Código”.

Si el dedo ha caído en color púrpura al comprobar los errores de la “Palabra del Código” aplicando el “Código de Hamming” veremos que nos marca como correcto, entonces dejaremos pasar la “Palabra del Código” como correcta, aunque no lo sea. Sin embargo, si cae en rojo aplicando el “Código de Hamming” detectaremos que hay errores y podremos incluso corregirlos.

Al corregir el código erróneo puede que nos salga otro código diferente o el mismo o no poder corregirlo, solo detectarlo.

Nota sobre la aleatoriedad de este ejemplo: Cuando se envía a nuestro amigo algo, realmente no recibe algo completamente aleatorio, solo lo he querido simular de una manera sencilla y rápida. En este ejemplo hemos escogido una “Palabra del Código” aleatoria completamente. Realmente por estadística no es un suceso completamente aleatorio pues partimos de un “Bloque del Código” en el que por el camino puede verse modificados uno, unos pocos bits o ninguno; pero siempre partiendo del “Bloque del Código” original, no de manera aleatoria. Por lo que siempre estaremos “cerca” del código de origen y será estadísticamente fácil corregirlo. Veamos esto.

 

Como puedes apreciar es muy probable poder detectar “Palabras del Código” recibidas que sean erróneas. Aunque no todas las “Palabras del Código” corregirán y darán como resultado al mensaje original. Solo los “cercanos” (los que han cambiado pocos bits respecto al “Bloque del Código” original que mandamos a nuestro amigo) serán los que efectivamente corrijan.

Dicho de otro modo, si volvemos a las dimensiones espaciales, solo las palabras dentro de un radio de distancia podrán ser detectadas y corregidas.

 

Esfera de Hamming

Pongo esta explicación en un cuadro aparte, pues tengo que cambiar el ejemplo a uno más sencillo (de lo contrario lo complicado sería entender el ejemplo 😉 ) y por no romper su continuidad.

Para ver el ejemplo simple, supongamos que la “Palabra del Código” en vez de tener 7 bits tiene 3 bits. 3 Dimensiones que podemos representar en un cubo. Si la “Bloque del Código” antes de enviar es por ejemplo 010, podríamos corregir cualquier “Palabra del Código” dentro de radio 1 (distancia 1 como máximo). Un radio en 3 Dimensiones dibuja una esfera como la siguiente, que englobaría las palabras “cercanas” de radio 1: 000, 110 y 011

esfera-de-hamming-www-jarroba-comPor cierto, a esta distancia desde un centro que traza un radio cualquiera se le conoce como Esfera de Hamming.

 

Código Corrector

El “Código de Hamming” es uno de los muchos “Códigos Correctores” que existen.

Para que sea un “Código Corrector” eficaz ha de seguir una serie de pautas. Analicemos el “Código de Hamming”

Capacidad de detectar de errores

Escojamos dos “Palabras del código” cuales quiera del “Espacio de Hamming”. En el siguiente ejemplo hemos escogido: “0 0 0 1 1 1 1” y “0 1 1 0 0 1 1”

espacio-de-hamming-para-hammin-7-4-eligiendo-dos-cualesquiera-www-jarroba-comY contemos la distancia entre esas dos palabras (que no es más que contar los bits que cambian). Para este ejemplo podemos ver que es de 4 (en la siguiente imagen represento a la distancia con la pesa, y los bits cambiados los he pintado de blanco):

deteccion-y-correcion-de-errores-buscando-distancia-minima-4-www-jarroba-comNo podemos quedarnos con la primera coincidencia, hay que buscar la “Distancia Mínima de Hamming”. Por lo que escogemos otras dos “Palabras del código” cuales quiera. Para este ejemplo: “0 0 0 1 1 1 1” y “0 1 0 0 1 0 1”

deteccion-y-correcion-de-errores-buscando-distancia-minima-3-www-jarroba-comVemos que esta vez la distancia ya no es de 4 sino de 3, que es menor. Así repetiríamos con todas las combinaciones posibles hasta que asegure cuál es la “Distancia Mínima de Hamming”.

 

Aclaración y resumen

A continuación, dejo una imagen resumen con todo lo que hemos hecho para realizar este cálculo (síguela con este párrafo de resumen para que veas el conjunto de cosas).

  • De un mensaje de Dimensión 4 lo hemos convertido a un “Bloque del código” de Dimensión 7 con el “Código Hamming”.
  • De enviar el “Bloque del código” a un amigo a través de Internet, podría ir variando por el camino introduciéndose errores, por cada error introducido se aleja 1 de distancia.
  • En la imagen puedes ver desde el “Bloque del código” correcto en verde (que además el mismo “Bloque del código” que hemos visto en las imágenes anteriores, para que tengas con que hilar las ideas con esta nueva imagen de abajo), como buscamos la “Mínima distancia de Hamming” al realizar todas las combinaciones de errores por distancia: primero un error, en la siguiente columna otro más, y así hasta el máximo que es tener todos los bits invertidos.

Si buscáramos todos los caminos mínimos para el “Bloque del Código” escogido para el ejemplo, el “0 0 0 1 1 1 1” respecto a los demás “Bloques de Código” generados por el “Código Corrector”, tendríamos (la siguiente imagen la he resumido, entre el “Bloque del Código” escogido y otros, he pintado solo los “Bloques de Código” con el peso/distancia -la variación de 0s o 1s- y los grupos de bits rojos de la imagen anterior los omito por claridad pero están contenidos en la línea los grupos de bits por los que pasa el camino mínimo):

distancia-respecto-a-una-palabra-del-codigo-www-jarroba-com

Si recuerdas cuando dibujábamos el cuadrado para 2 Dimensiones, el cubo para 3 Dimensiones, etc; esto realmente es una “esquina” de nuestro hipercubo de 7 Dimensiones. Mirando desde cada esquina de cada “Bloque del Código” y contando los pasos hasta el siguiente “Bloque del Código”, comprobaríamos que al hacer todas la distancia mínima es de 3 para Hamming(7,4).

deteccion-y-correcion-de-errores-buscando-distancia-minima-con-todos-www-jarroba-com

 

En este caso, para nuestro ejemplo de Hamming(7,4), después de hacer todas las combinaciones (que son unas cuantas), encontramos que la “Distancia Mínima de Hamming” para Hamming(7,4) es de 3.

La distancia de 3 es lo que nos asegura que encontramos al menos un “Bloque del Código”, por lo que los errores que es capaz de detectar Hamming(7,4) será uno menos 3 – 1 = 2. 2 son los errores que el “Código Corrector” Hamming(7,4) es capaz de detectar.

Por lo que un “Código Corrector” detecta e errores si entre cualesquiera dos palabras C1 y C2, de las que genera el “Código Corrector”, aseguramos una “Distancia Mínima de Hamming” d. Y por lo que hemos visto podemos relacionar: d = e + 1

 

Capacidad de corrección de errores

Tomemos dos “Palabras del Código” cualesquiera y comprobemos su distancia. Por ejemplo, para la palabra C1 “0 0 0 1 1 1 1” y C2 “0 1 0 0 1 0 1” su distancia (como vimos previamente) es de 3.

deteccion-y-correcion-de-errores-buscando-distancia-minima-3-www-jarroba-comTomemos como referencia la palabra C1 (a la “Palabra del Código” que tomo como referencia la llamaré “Origen”, porque es desde donde empezamos todo 🙂 ) y empecemos a introducir errores que lo “acerquen” con los menos pasos posibles a la palabra C2. Introducimos un primer error a la palabra C1 (en la imagen siguiente he cambiado un 1 por un 0, dando como resultado “0 0 0 1 1 0 1”), podemos probar que esta nueva palabra errónea se ha acercado 1 paso a la palabra C2. En resumen, la palabra errónea está a 1 paso de C1 y a 2 pasos de C2.

demostracion-capacidad-de-correcion-de-errores-del-codigo-hamming-1-www-jarroba-comEsta palabra errónea se puede detectar como errónea (como vimos anteriormente) y si la corregimos podemos asegurar que nos da como resultado la palabra origen C1. Se puede corregir hacia su palara origen porque no existe otra “Palabra del Código” tan cercana, si dos palabras del código son igual de cercanas entonces no se puede corregir hacia su origen (veamos esto último a continuación).

Introduzcamos otro error más a la palabra C1 al cambiar un segundo bit que lo acerque otro paso más a C2 (en la imagen siguiente he cambiado un 0 por un 1, por lo que tenemos “0 1 0 1 1 0 1”). Resumo otra vez, la nueva palabra errónea está a 2 pasos de C1 y a 1 pasos de C2.

demostracion-capacidad-de-correcion-de-errores-del-codigo-hamming-2-www-jarroba-comYa no puede estar más cerca la palabra errónea, está a un único paso la palabra con errores de C2.

Esta nueva palabra errónea “0 1 0 1 1 0 1” se puede detectar como errónea, pero no se puede corregir hacia su origen ya que existe al menos una “Palabra del Código” que es más cercana que la de origen. Esto quiere decir, que, si intentáramos corregir esta última palabra errónea “0 1 0 1 1 0 1”, no conseguiríamos la palabra C1, sino la palabra C2.

¿Recuerdas las “Esferas de Hamming”? Desde cada “Palabra del Código” las “Esferas de Hamming” no se pueden cortar (intersecar) para asegurar que corregimos correctamente la palabra hacia su “Palabra del Código” origen.

demostracion-capacidad-de-correcion-de-errores-del-codigo-hamming-3-www-jarroba-comPues si dos “Esferas de Hamming” o más se cortan puede pasar dos cosas:

  • Que la palabra sea corregida hacia otra “Palabra del Código” diferente a la de origen.
  • Que no se pueda saber hacia cuál de las “Palabras del Código” cuyas “Esferas de Hamming” se cortan es la de origen (no he pintado ejemplo de este caso, pero puedes imaginar que ocurriría si en vez de ser pares las palabras erróneas entre dos “Palabras del Código” fueran impares; la palabra errónea que está justo en medio está a igual de distancia de ambas “Palabras del Código”, por lo que no se puede saber cuál es su origen).

Por lo que como mucho corregiríamos hasta la media de las “Palabras del Código”. Por ejemplo, la media de edad de una persona de 20 años y una de 40 es (20+40)/2 que es 30.

De esta forma para Hamming(7,4), entre las dos “Palabras del Código” anterior (que cumplen la “distancia mínima de Hamming”) podemos deducir que es la media (de 2, son 2 palabras) de la “Capacidad de detectar errores” (que son el número mínimo de errores entre las dos palabras; o como vimos anteriormente era “Distancia Mínima de Hamming” d menos 1: d – 1). Por lo que: (3 – 1) / 2 = 1.

Entonces el “Código Corrector” tiene la capacidad de corregir errores si entre cualesquier dos palabras C1 y C2, de las que genera el “Código Corrector”, aseguramos la media entre la “Capacidad de detectar errores”. Por lo que: E = (d – 1) / 2

 

Ratio y Sobrecarga

Por ejemplo, no es lo mismo enviar a nuestro amigo un “Bloque del código” mediante Hamming(7,4) que mediante Hamming(31,26):

  • Hamming(7,4): Longitud del mensaje 4, longitud del “Bloque del código” 7, bits de paridad 3
  • Hamming(31,26): Longitud del mensaje 26, longitud del “Bloque del código” 31, bits de paridad 7

A ojo puedes ver que para Hamming(7,4) los bits realmente útiles (los bits de paridad son también “útiles” para la corrección de errores, me refiero a “útiles” para el usuario; al usuario le da igual los bits de paridad, lo más probable es que ni sepa que existen, él quiere que con el menor consumo obtener la máxima información), envía casi los mismos bits de información que los de paridad (casi el 50% datos vs 50% de paridad). Sin embargo, con Hamming(31,26) puedes ver que la relación 26 bits de información contra los 7 bits de paridad da mucha más información y menos en bits de paridad (aproximadamente el 80% de datos vs 20% de paridad).

Entonces, si queremos enviar a nuestro amigo un mensaje cualquiera, por ejemplo de 100 bits, y lo tenemos que dividir en cachos según Hamming(7,4) o Hamming(31,26):

  • Hamming(7,4): para un mensaje de 100 bits, 75 bits adicionales serían bits de paridad ( (100 / 4) * 3 = 75). Enviaríamos un total de 175 bits (casi tenemos que duplicar el tamaño del mensaje para enviar los datos y poder corregirlos en el destino)
  • Hamming(31,26): para un mensaje de 100 bits, 27 bits adicionales serían bits de paridad ( (100 / 26) * 7 = 27). Enviaríamos un total de 127 bits (sumamos solo un cuarto del tamaño del mensaje)

Si nuestro medio de transmisión (cable, Wi-Fi, 4G, etc) es de por ejemplo 16 bits por segundo (lo sé, no hay nada más rápido en el mercado 😛 ), quiere decir que para:

  • Hamming(7,4): enviamos 175 bits, por lo que tarda 11 segundos en enviarse todos los bits (175 / 16 = 11)
  • Hamming(31,26): enviamos 127 bits, por lo que tarda 8 segundos en enviarse todos los bits (127 / 16 = 8)

Por tanto, para medir la velocidad de transmisión utilizamos la Ratio. Para calcular la Ratio dividimos la longitud del mensaje entre la longitud del “Bloque del código”. La Ratio = R = k/n

Para nuestros ejemplos tendríamos:

  • Hamming(7,4): Ratio = R = k/n = 4/7 = 0,57
  • Hamming(31,26): Ratio = R = k/n = 26/31 = 0,84

Una Ratio grande significa que la cantidad de bits del mensaje por cada “Bloque del código” transmitido es alto. Es decir, cuantos más datos tenga un “Bloque del código” y menos bits de paridad (bits redundantes) haya, la Ratio será mayor.

La Ratio no puede exceder de 1 ya que los datos se comprimen sin pérdidas. Por lo que cuantos más datos tenga y menos bits de paridad, más se acercará a 0; de lo contrario, a más bits de paridad, se acercará más a 1. A este 1 – R lo llamamos Sobrecarga, que se produce debido a la codificación del “Bloque del Código. Si todos son datos (sin ningún bit de paridad), por ejemplo para Hamming(7,7) será 7/7 = 1 y la Sobrecarga será 1 – 1 = 0. Por el contrario, si todos son datos de paridad, por ejemplo Hamming(7,0), será 0/7 = 0 y la Sobrecarga será 1 – 0 = 1. Es decir, cuántos más bits redundantes más sobrecargado estará nuestro “Bloque del código”.

En nuestros ejemplos anteriores podemos calcular la Sobrecarga de una menara muy sencilla:

  • Hamming(7,4): Sobrecarga = 1 – R = 1 – 0,57 = 0,43
  • Hamming(31,26): Sobrecarga = 1 – R = 1 – 0,84 = 0,16

 

Ejemplo completo con todas las propiedades y resumen

Resumo todas las propiedades que hemos visto para el ejemplo para “Hamming(7,4)”:

  • Alfabeto = Q = 2
  • Elementos = q = 0 y 1
  • Palabras del código” = C = 2^k = 2^4 = 16
  • Bits de paridad = r = 3
  • Longitud del Mensaje = k = n – r = 2^r – r – 1 = 2^3 – 3 – 1 = 4
  • Longitud del “Bloque del Código” = n = 2^r – 1 = 2^3 – 1 = 7
  • Hamming(n, k) = Hamming(7, 4)
  • Distancia Mínima de Hamming” = d = 3
  • Capacidad de detectar de errores del “Código Corrector” = e = d – 1 = 2
  • Capacidad de corrección de errores del “Código Corrector” = E = (d – 1) / 2 = (3 – 1) / 2 = 1
  • Ratio = R = k/n = 4/7 = 0,57
  • Sobrecarga = 1 – R = 1 – 0,57 = 0,43
  • Distancia relativa = ẟ = d/n = 3/7 = 0,43

 

Extras

 

Distancia de Hamming y Distancia Mínima de Hamming con textos (Strings)

La “distancia de Hamming” se puede aplicar a muchas otras cosas (a otros algoritmos de detección y corrección de errores diferentes al “algoritmo de Hamming”) como a ti mismo.

Por ejemplo ¿Cuántas letras hay que cambiar a la palabra “Pasajero” para que para ti signifique otra cosa diferente?

Si cambiamos una sola letra “Pasajiro” por parecido a la palabra “Pasajero” todavía puedes entender la palabra ¡Puedes detectar que hay un error y hasta corregirla!

Si cambia otra letra más como “Pasajizo”, ya puede que cueste más y no tengamos la certeza de qué palabra proviene, pero podemos asegurar que hay letras que están mal (debido a que dicha palabra no existe en el diccionario; sabemos que está mal, pero no podemos corregirla, ya que corregirla podría llevarnos a cometer el error de pensar que es otra palabra que no es, como las palabras “Posadero” o “Forajizo” que existen en el diccionario)

Cambiando una tercera letra “Pasadizo” ya la palabra cambia completamente a una que palabra que realmente existe. Al ser una palabra que existe la tomaríamos como buena. Por tanto, nuestra “distancia de Hamming” de la palabra “Pasajero” a “Pasadizo” es de 3.

Puede que otras letras y orden de modificación con esta palabra acorten o alarguen la “distancia de Hamming”.

Como “Pasajera”, cambiando la última letra del mensaje original “Pasajero”, sigue existiendo y no podríamos detectar errores, por lo que la “distancia de Hamming” sería de 1. Esta distancia podemos decir que es la mínima, por ello se llama “distancia mínima de Hamming”.

¿Pero no hemos dicho que la “distancia de Hamming” para la palabra “Pasajero” era de 3 en el anterior ejemplo?

No confundamos la “distancia de Hamming” con la “distancia MÍNIMA de Hamming”.

Habría que hacerlo con todas las combinaciones posibles, hago con las siguientes pocas para ver el ejemplo:

  • De “Pasajero” a “Pasadizo” hay una “distancia de Hamming” de 3
  • De “Pasajero” a “Posadero” hay una “distancia de Hamming” de 4
  • De “Pasajero” a “Pasajera” hay una “distancia de Hamming” de 1

De todas las “distancias de Hamming” (de todas las combinaciones posibles que nos dan palabras válidas) nos quedamos con la más pequeña (la mínima). Así la “distancia mínima de Hamming” para la palabra “Pasajero” es de 1. De este modo aseguramos la cantidad de letras mínimas que se tienen que modificar para que dejemos de detectar y corregir (para tener más seguridad hay que hacer todas las combinaciones para deducir la “distancia mínima de Hamming”). Como puedes ver, nosotros mismos como humanos no seríamos un buen algoritmo de detección y corrección de errores, pues no podríamos asegurar una distancia “distancia mínima de Hamming” superior a 1 (no nos pongamos tristes como humanos de no valer como algoritmo, es solo un ejemplo para que entender el concepto; un humano por fortuna no es un algoritmo, un humano diseña algoritmos para que hagan este trabajo tedioso y nuestro lenguaje no fue diseñado para cumplir una “distancia mínima de Hamming” grande, pero los mensajes en binario que diseñamos a posteriori sí 🙂 )

 

Método para calcular los bits de paridad desde la “Longitud del mensaje”

Se pueden calcular los “Bits de Paridad” desde la “Longitud del mensaje”, aunque no con una fórmula directa, sino con una función. Sabemos que cada bit de paridad está en una posición 2^X (1, 2, 4, 8, 16, etc), y los espacios entre estos añadiremos los bits de datos (de la “Longitud del mensaje”). Entonces si tenemos “Longitud del mensaje” que es por ejemplo 4, por iteraciones podemos hacer:

  1. [4 Datos (bits del mensaje que quedan por repartir)] 1ª pos (posición): Paridad (Bit de Paridad).
  2. [4 Datos] 1ª pos: Paridad. 2ª pos: Paridad.
  3. [3 Datos] 1ª pos: Paridad. 2ª pos: Paridad. 3ª pos: Dato (Bit del dato).
  4. [3 Datos] 1ª pos: Paridad. 2ª pos: Paridad. 3ª pos: Dato. 4ª pos: Paridad.
  5. [2 Datos] 1ª pos: Paridad. 2ª pos: Paridad. 3ª pos: Dato. 4ª pos: Paridad. 5ª pos: Dato.
  6. [1 Datos] 1ª pos: Paridad. 2ª pos: Paridad. 3ª pos: Dato. 4ª pos: Paridad. 5ª pos: Dato. 6ª pos: Dato.
  7. [0 Datos] 1ª pos: Paridad. 2ª pos: Paridad. 3ª pos: Dato. 4ª pos: Paridad. 5ª pos: Dato. 6ª pos: Dato. 7ª pos: Dato.

Con esto sacamos no solo la colocación de los bits (de datos y de Paridad), también la cantidad de bits de Paridad es de 3 para 4 bits de Datos.

 

Bibliografía

Comparte esta entrada en:
Safe Creative #1401310112503
Hamming por "www.jarroba.com" esta bajo una licencia Creative Commons
Reconocimiento-NoComercial-CompartirIgual 3.0 Unported License.
Creado a partir de la obra en www.jarroba.com

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Uso de cookies

Este sitio web utiliza cookies para que usted tenga la mejor experiencia de usuario. Si continúa navegando está dando su consentimiento para la aceptación de las mencionadas cookies y la aceptación de nuestra política de cookies

ACEPTAR