¿Dónde puedo encontrar ejemplos de códigos de corrección de errores de los siguientes tipos?

8

Primero, disculpas si esta pregunta es apropiada o trivial para este sitio. Soy un físico que busca ayuda fuera de su zona de confort.

En PRL 87 167902 (2001) se afirma que

"... para un arbitrariamente pequeño existe un código de corrección de errores con (para alguna constante ) tal que la distancia de Hamming entre dos palabras de código distintas y esté entre y ".E : { 0 , 1 } n{ 0 , 1 } m m n / δ c c E ( x ) E ( y ) ( 1 - δ ) m / 2 ( 1 + δ ) m / 2δ>0 0mi:{0 0,1}norte{0 0,1}metrometronorte/ /δCCmi(X)mi(y)(1-δ)metro/ /2(1+δ)metro/ /2

En el documento, esto se conoce debido a pruebas de existencia no constructivas. Me gustaría saber si existen ejemplos explícitos de tales códigos (o códigos similares, o incluso mejores), dado que el documento fue hace 16 años.

En particular, estoy interesado en los códigos donde y la distancia de Hamming entre dos palabras de código distintas tiene una menor enlazado al menos lineal en (soy bastante flexible sobre el comportamiento con , ya que solo necesito el caso ).mi:{0 0,1}norte{0 0,1}metrometro=O(norte)metroδδ=1/ /2

Pregunto aquí porque estoy seguro de que esta será una pregunta muy fácil para la persona correcta, pero no soy esa persona y no estoy seguro de dónde es mejor comenzar a buscar. Cualquier sugerencia de dónde mirar sería muy apreciada.

JMAA
fuente

Respuestas:

9

Si solo necesita algún código donde y donde la distancia es lineal en , entonces lo que está buscando se llama un "código asintóticamente bueno". Existen muchas construcciones explícitas de dichos códigos, y puede encontrar las básicas en las notas de clase de los cursos sobre teoría de la codificación. Por ejemplo, puede encontrar una descripción de una construcción clásica en la Lección 7 aquí . Otro ejemplo de una construcción son los códigos de expansión, que se describen en la Lección 14 allí. m = O ( n ) mmi:{0 0,1}norte{0 0,1}metrometro=O(norte)metro

Si usted está buscando específicamente para los códigos en que la distancia entre dos palabras de código está cerca de , y en particular se superior delimitada por , entonces las cosas son un poco más complicadas. Dichos códigos están estrechamente relacionados con los objetos llamados " -uestros conjuntos", que han sido estudiados durante bastante tiempo en TCS. Puede encontrar una construcción muy reciente de dichos códigos aquí . Las primeras construcciones se pueden encontrar aquí y aquí (aunque solo le dan ). (1+δ)mmetro2 ϵm=poly(n)(1+δ)metro2ϵmetro=pagsoly(norte)

O meir
fuente
Muy útil, gracias. Todavía estoy un poco demasiado familiarizado con el territorio para extraer exactamente lo que necesito, pero este es un muy buen punto de partida para aprender.
JMAA