¿Cómo se relaciona el apilamiento de naranjas en 24 dimensiones con la recepción y decodificación de señales de las Voyagers?

Todas las diferentes palabras de datos que un transmisor puede enviar y un receptor puede detectar pueden imaginarse como puntos dispuestos en un gran espacio.

La selección de una codificación de datos para la detección y corrección de errores se trata de mantener palabras de código válidas a cierta distancia entre sí. Como resultado, un ligero cambio ("movimiento") de una palabra válida no hace que parezca otra palabra válida.

Como no voy a hacer ningún dibujo de esferas e hipercubos de 24 dimensiones, voy a restringir esta respuesta a tres dimensiones.

ejemplo de 3 bits

Imagine una palabra de datos que consta de tres dígitos binarios. Podemos organizarlos en forma de cubo tratando cada dígito como la coordenada en una dimensión:

Cada error de transmisión, es decir un bit que es un '0' confundido con un '1' o viceversa, corresponde a avanzar un paso por una de las aristas de este cubo.

En la comunicación diaria normal con tasas de error lo suficientemente bajas, podemos tratar todos los puntos de código como válidos:

Pero, cada bit invertido conduce a otra palabra válida. Entonces, si eliminamos cada segunda palabra válida, obtenemos esto:

Ahora, todas las palabras válidas están separadas por dos bordes. Un bit invertido nos lleva a una palabra no válida y sabemos que hubo un error, pero no podemos corregirlo porque hay tres posibles bits que podrían haber invertido. Esto se denomina código de "0 errores de corrección, 1 error de detección".

Para mejorar la solidez, elimine otras dos palabras de código válidas:

Ahora, todas las palabras válidas están separadas por tres bordes. Si un bit cambia, obtenemos una palabra no válida, pero aún podemos decir de dónde venimos. Si se voltearon dos bits, no podemos corregir la palabra, porque otra palabra válida está más cerca del código incorrecto que de la palabra correcta. Por lo tanto, este código se llama "1 error de corrección, 2 bits de detección"[*]. Esto es lo mejor que podemos obtener con nuestras sencillas palabras de código de 3 bits.

extensión de código de 4 bits

Si agrega otro bit para tener palabras de código de 4 bits, puede aumentar la distancia entre los puntos válidos a tres bordes del cubo entonces de 4 dimensiones. Esto brinda otro nivel de mitigación de errores: si se invierten dos bits, llega a una palabra no válida justo "en el medio" de varias palabras válidas. No puede decidir cuál podría ser el correcto, pero al menos sabe que se voltearon dos bits. Este tipo de código se llama "1 corrección de errores, 3 detección de errores".

Viajero

En el caso de la Voyager, esto no sería suficiente, así que optaron por una palabra clave de 24 bits. Del total de 16 millones de palabras clave, solo definieron 4096 como válidas. Es decir, 12 bits transportan información real y otros 12 se utilizan para la corrección de errores. Esto resultó en un código de "3 errores de corrección, 7 errores de detección". Es decir, si en alguna palabra se recibiesen incorrectamente 3 bits, aún podría corregirse adecuadamente y si se voltearan hasta 7 bits; al menos se sabría que algo anda mal. Este código podría representarse de la misma manera que lo hice anteriormente como las esquinas de un hipercubo de 24 dimensiones.

Ahora, ¿cómo se relaciona esto con el empaquetamiento de esferas? De hecho, las tres imágenes muestran el empaquetamiento más denso posible de esferas con diámetros de$\sqrt 1$,$\sqrt 2$y$\sqrt 3$, respectivamente, bajo la restricción de que sus centros deben estar ubicados en las esquinas del cubo.[**]

Obviamente, esto no parece demasiado espectacular, pero se vuelve mucho más desafiante si no estamos mirando datos binarios digitales, sino que usamos un transmisor que también admita valores intermedios, por ejemplo, usando no un simple encendido/apagado. modulación, pero agregue modulación de amplitud en la parte superior. Al agregar un paso más (por ejemplo, apagado/bajo/alto) para cada uno de los tres dígitos de nuestro ejemplo, no tenemos ocho palabras de código válidas, pero en realidad$3^3 = 27$- ¡comienza a empaquetar tus esferas en esa cuadrícula!

---

[*] Tenga en cuenta que "detectar" no significa que podrá saber cuántos errores de bits hay exactamente. Se refiere a la cantidad de errores de bits que pueden ocurrir antes de que termine con otra palabra de código válida.

[**] Estrictamente hablando, aquí no tratamos con esferas en un espacio euclidiano regular, sino con esferas de Hamming: se definen por el conjunto de esquinas que están a un número determinado de aristas de distancia de su centro. Esto explica el hecho de que en un mundo binario solo las esquinas del cubo representan puntos válidos, mientras que cualquier otro punto tendría coordenadas fraccionarias y simplemente no existe. Prácticamente, no hay diferencia entre los dos en los ejemplos dados aquí.