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.

Te 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:

Con 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:

Nota 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):

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

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¹ = 2 combinaciones de bits, para 2 bits son 2²=4 combinaciones de bits, para 3 bits son 2³=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).

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

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?

La 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 la “Distancia 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 10, 1 en binario es 01 y 0 en binario es 00):

Ahora 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).

Ahora 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):

Fá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³ – 1 = 7
• Longitud del mensaje (el tamaño del Mensaje) = k = n – r = 2^r – r – 1 = 2³ – 3 – 1 = 4

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.

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⁴ = 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ⁿ = 2⁷ = 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).

Pero 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).

De este modo el ordenador de nuestro amigo comprueba con el código Hamming si hay errores.

El 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):

Con 4 bits son 2⁴ = 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.

Cuando 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):

Hagamos un juego antes de continuar.

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.

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”

Y 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):

No 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”

Vemos 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”.

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.

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

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

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

Pues 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⁴ = 16
• Bits de paridad = r = 3
• Longitud del Mensaje = k = n – r = 2^r – r – 1 = 2³ – 3 – 1 = 4
• Longitud del “Bloque del Código” = n = 2^r – 1 = 2³ – 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

Bibliografía

• https://en.wikipedia.org/wiki/Hamming(7,4)
• https://en.wikipedia.org/wiki/Hamming_code
• https://en.wikipedia.org/wiki/Hamming_distance
• https://en.wikipedia.org/wiki/Parity-check_matrix
• https://en.wikipedia.org/wiki/List_decoding
• https://en.wikipedia.org/wiki/Block_code
• https://en.wikipedia.org/wiki/Linear_code
• https://books.google.es/books?id=7KBYOt44sugC&pg=PA1&redir_esc=y#v=onepage&q=hamming%20space&f=false
• https://books.google.es/books?id=2eHFTkoUjg4C&pg=PT110&lpg=PT110&dq=tcp+ip+codeword&source=bl&ots=l7G1dvYB2Y&sig=gmp8dZA3FKc-Fxk1iuJ6UxmgD_k&hl=es&sa=X&ved=0ahUKEwjrhsCa17zPAhVErB4KHZyzByQQ6AEIJzAC#v=onepage&q=tcp%20ip%20codeword&f=false