Un código es un conjunto de palabras: un gran subconjunto de todas las secuencias de bits posibles, elegidas de tal manera que es fácil distinguirlas incluso si se invierten algunos bits.
Puedes pensar en una secuencia de n bits, como un vector en el espacio n-dimensional, una de las esquinas de un hipercubo. Por lo tanto, un código es un subconjunto de estas esquinas. Puede pensar en voltear uno o más bits, como la suma de vectores: el ruido original traduce un poco el vector original (una palabra de código). Un acto de corrección de errores está tratando de adivinar el punto original en este hipercubo desde el cual comenzamos a ver solo la imagen distorsionada. Si lo piensa bien, tiene sentido elegir la palabra de código que está más cerca (en el sentido de la distancia de Hamming) a la palabra recibida, con formato incorrecto, ya que esta apuesta tiene la mayor probabilidad (siempre que dejemos de lado las disputas bayesianas). Por lo tanto, el hiperespacio puede considerarse dividido en grupos de Voronoi. Cuanto más grandes sean, mayor será la posibilidad de que distorsionar un vector un poco no nos haga pasar el límite entre los grupos, y así se restaurará la palabra de código correcta.
Si los bits volteados se eligen de manera maliciosa, entonces el “volumen” de los clústeres no es tan importante como su “radio”: número mínimo de bits que uno tiene que voltear para llegar al borde. Esto debería darle una imagen mental de las bolas de ping-pong que intenta empaquetar en una caja, lo más densamente posible: el radio se relaciona con la tolerancia al error, mientras que el número de bolas es el número de palabras de código o posibles mensajes que puede crear (su “vocabulario”), y se traduce en velocidad de transmisión.
Por supuesto, no es tan simple en un espacio n-dimensional, ya que ni la caja parece una caja, ni las pelotas de ping-pong tienen forma de pelotas … pero esa es una analogía útil, ya que ambos problemas son complicados, dan resultados bastante buenos con heurísticas aleatorias simples, pero son bastante complicados cuando se quiere algo determinista, elegante y demostrable.
Hay una manera muy simple de crear un código muy eficiente: simplemente elija palabras de código (vectores, puntos en el espacio, esquinas del hipercubo, ubicaciones de bolas) al azar, uno por uno, asegurándose de que la nueva palabra de código esté lejos suficiente de los generados anteriormente. Con alta probabilidad obtendrás una gran cantidad de bolas antes de que te atasques.
Hay un gran problema con esta idea: tendrías que asegurarte de que el destinatario del mensaje use el mismo “libro de códigos” (la lista de palabras de código válidas) que tú, a menos que tengas un montón de mensajes sin usar DVD, limita la n que puede usar a un número muy pequeño.
Por lo tanto, siempre hubo un deseo de construir (no adivinar) el código de una manera elegante, de modo que sea fácil demostrar que no se cruzan dos bolas y que sea fácil para el receptor recuperar el centro de una bola teniendo solo un punto dentro de él (o en general: la palabra de código más cercana).
Una forma de aportar estructura a este caos es utilizar álgebra lineal. Si piensa en XOR como módulo de suma 2, entonces sabe cómo “agregar” dos vectores de n bits cada uno. La idea detrás de los códigos lineales es que su código debe cerrarse bajo esta operación: si w y v son palabras de código, debe declarar w XOR v también una palabra de código. Una de las ventajas de este enfoque es que el código ahora tiene mucha “simetría”, de modo que la pregunta “¿cuál es el radio más grande de una pelota que puedo usar?” que es esencialmente lo mismo que “¿a qué distancia están las dos palabras de código más cercanas en mi código?” se vuelve tan trivial como “¿cuál es el peso mínimo de Hamming de una palabra de código en mi código?”.
- Cómo pasar de resolver 2 problemas en CodeChef a resolver 10 preguntas en el concurso largo
- ¿Es posible seleccionar k números de una secuencia dada de n números, de modo que xor de los elementos seleccionados sea igual a m?
- ¿Cuáles son los requisitos previos para comprender el algoritmo de transformación rápida de Fourier para la multiplicación?
- Sea n el número de factores de 2014, incluido 1 y en sí mismo. ¿Cuántos números de dos dígitos también tienen n factores?
- Quiero imprimir todos los números primos hasta un número primo dado máx. Tengo dos métodos: el tamiz de Eratóstenes y el método trivial. ¿Cómo comparo sus tiempos de ejecución? ¿Qué método es más rápido?
Entonces, una vez que decida que su código será lineal, puede enfocarse en un objetivo: asegurarse de que no haya una palabra de código con pequeños 1s.
Otra forma de pensar en secuencias de n bits es pensar en ellas como polinomios: cada bit es un coeficiente. Puede agregar polinomios tal como lo hace con vectores. Pero también puede usar operaciones de división y módulo en polinomios. Si piensa en una tarea de espaciar uniformemente algo a lo largo del eje, podría usar un módulo para eso: por ejemplo, para elegir 11 números muy separados entre sí en el intervalo [0,100], podría elegir aquellos que son divisibles por 10. Dado que nuestro objetivo es poner las bolas en una caja lejos una de la otra, podríamos elegir polinomios que sean divisibles por algún polinomio fijo, llamémoslo C.
Primero, observe que esto daría un código lineal: si dos polinomios son divisibles por C, entonces su suma también es divisible por C.
Ahora, la pregunta es, ¿cuál es el peso mínimo de Hamming de una palabra en dicho código, o en otras palabras: cuál es el polinomio más corto que puedo escribir (suponiendo que solo tengo que escribir explícitamente coeficientes distintos de cero) que es divisible por C?
Por ejemplo, x ^ 226 + x ^ 25 tiene solo dos coeficientes distintos de cero, por lo que el peso de Hamming es 2, y si este polinomio es divisible por C, y 226 es menor que n, entonces hemos encontrado que hay dos palabras que están en la distancia 2 uno del otro.
¿Es posible que haya una palabra de código con peso 1?
Bueno, significaría que x ^ k para algunos k es divisible por C, pero sabemos cuáles son los factores de x ^ k: x * x * x * .. * x, entonces, a menos que C también sea de esta forma, es imposible.
Volviendo al ejemplo de x ^ 226 + x ^ 25, observe que esto es (x ^ 201 + 1) * x ^ 25, y (a menos que C sea divisible entre x) esto significa que x ^ 201 + 1 también es divisible por C, y por lo tanto también una palabra de código, y un ejemplo difícil.
Por lo tanto, podríamos centrar nuestro esfuerzo en las palabras que terminan en 1, ya que siempre podemos “desplazarnos hacia la derecha” dividiendo por x. (Esta es una de las propiedades “cíclicas” de los códigos cíclicos).
Entonces, si hay una palabra de código de peso 2, entonces también hay una palabra de código de la forma x ^ k + 1.
Resulta (francamente, olvidé la prueba, ¡lo siento, Sr. Kościelski!: /) Que para cada polinomio C hay k lo suficientemente alto como para que x ^ k-1 sea divisible por C (tenga en cuenta que en el módulo 2 tenemos que -1 es lo mismo que +1), por lo que la pregunta realmente es: ¿cuál es la k mínima, en comparación con n?
O en otra dirección: qué tan grande puedo usar n si quiero que mis bolas estén separadas más de 2 bits (lo que permite la corrección de un solo bit).
La respuesta obviamente depende de la elección de C y, por ejemplo, en CRC32, el polinomio C se elige de tal manera que n sea lo más grande posible (AFAIR es exponencial en el rango de C, por lo que probablemente sea 2 ^ 32 IIRC).
Ahora, observe que si x ^ n-1 es divisible por C, entonces x ^ n es igual a 1 módulo C.
Esto significa que un bit más a la derecha tiene el mismo “peso” para nuestros cálculos que el bit al lado del bit más a la izquierda de una palabra de código. Puede pensar en la rotación cíclica de una palabra de código como esta: corta el bit menos significativo y lo cose a la izquierda del bit más significativo (intercambie “1” por “x ^ n”), y luego mueva todo a la derecha (“dividir por x”). Ninguna de estas acciones debería cambiar la divisibilidad por C, y es por eso que decimos que el código es cíclico: si “wa” es una palabra de código, entonces “aw” también es una palabra de código.