Algoritmo para generar un código de corrección de errores tamaño k en n bits

Question

Quiero generar un código en n bits para k diferentes entradas que quiero clasificar. El requisito principal de este código es el criterio de corrección de errores: que la distancia mínima pairwise entre dos codificaciones de diferentes entradas se maximiza. No necesito que sea exacta -. Aproximada va a hacer, y la facilidad de uso y velocidad de implementación computacional es una prioridad demasiado

En general, n estará en los cientos, k en las docenas.

También, hay un razonablemente apretado obligado de la distancia de Hamming mínima entre codificaciones binarias k diferente de n bits?

Answer 1

El problema de encontrar la exacta mejor código de corrección de errores para los parámetros dados es muy difícil, ni siquiera aproximadamente mejores códigos son difíciles. Además de eso, algunos códigos no tienen ningún algoritmos de decodificación decente, mientras que para otros el problema decodificación es bastante complicado.

Sin embargo, usted está preguntando acerca de un determinado rango de parámetros, donde n »k, donde si he entendido bien desea un código de k dimensiones de longitud n. (De modo que k bits se codifican en n bits). En este intervalo, primero, un código aleatorio es probable que tenga muy buena distancia mínima. El único problema es que la decodificación es en cualquier lugar de poco práctico intractible, y de hecho el cálculo de la distancia mínima no es tan fácil.

En segundo lugar, si quieres un código explícito para el caso »k n, entonces usted puede hacer razonablemente bien con un BCH código con q = 2. Como la página de Wikipedia explica, hay una buena decodificación algoritmo para códigos BCH.

En cuanto a los límites superiores de la mínima distancia de Hamming, en el rango n »k usted debe comenzar con el de Hamming encuadernado, también conocido como el volumen encuadernado o el empaquetamiento de esferas unido. La idea de la cota es simple y hermoso: Si la distancia mínima es t, entonces el código puede corregir errores de hasta un piso de distancia ((t-1) / 2). Si puede corregir errores a alguna radio, significa que las bolas de Hamming de ese radio no se superponen. Por otra parte, el número total de palabras posibles es 2 ⁿ , por lo que si se divide por el número de puntos en una bola de Hamming (que en el caso binario es una suma de coeficientes de dos términos), se obtiene una cota superior del número de palabras de código libre de errores. Es posible superar esta cota, pero para gran distancia mínima que no es fácil. En este régimen es una muy buena cota.