Error booleano que corrige el código sobre

¿Hay alguna construcción conocida de un código de corrección de error lineal (con parámetros razonables), de modo que cuando se le da un vector booleano , también devuelve un vector booleano whp? (aunque se acabó ) $\mathsf{ECC}:\mathbb{F}_q^n \to \mathbb{F}_q^m$ $v\in \{0,1\}^n$ $\mathbb{F}_q$

(es decir, , donde se toma la probabilidad de elegir uniformemente , y es arbitrariamente pequeño) $\Pr[\mathsf{ECC}(v) \in \{0,1\}^m]>1-\epsilon$ $v\in \{0,1\}^n$ $\epsilon$

Si no, ¿qué pasa si relajamos la condición a

Pr [{E C C}_{i} (v) \in {0, 1}] > 1 - ϵ

$\Pr[\mathsf{ECC}_i(v) \in \{0,1\}]> 1-\epsilon$ Donde

{E C C}_{i}

$\mathsf{ECC}_i$ devuelve la coordenada

i

$i$ ' de

E C C

$\mathsf{ECC}$ ,

ϵ

$\epsilon$ es arbitrariamente pequeño, y la probabilidad se toma sobre la elección uniforme de

v \in {0, 1}^{n}

$v\in \{0,1\}^n$ elección uniforme de una coordenada

i \in [m]

$i\in[m]$ .

Por curiosidad, ¿tienes alguna aplicación en mente?

Tsuyoshi Ito

Sí, en realidad tengo un par de aplicaciones para un código de corrección de errores con dicha propiedad. Sin embargo, creo que no es factible explicarlo dentro del alcance de un comentario. Puede contactarme por correo si está interesado.

Gracias por la respuesta. Si no cabe en un comentario, probablemente no tenga tiempo para entenderlo de todos modos, así que lo dejaré como está. ¡Gracias!

Tsuyoshi Ito

Respuestas:

Si. Por ejemplo, un código Reed-Solomon contiene un código BCH, que es un código lineal binario, como un subcódigo. Estos se llaman subcampos-subcódigos.

Mahdi Cheraghchi
fuente

¿Significa que dado un código Reed-Solomon (lineal en F_q), la probabilidad de que el código devuelva una palabra de código binario, dada una entrada binaria, es 1? ¿Puede dirigirme a algún documento / encuesta en el que pueda leer sobre esta propiedad con más detalle? Soy un poco nuevo en la teoría de la codificación. ¡Gracias!

La mejor referencia para leer sobre códigos BCH binarios son los libros de texto clásicos "La teoría de los códigos de corrección de errores" de MacWilliams y Sloane y también la "Introducción a la teoría de la codificación" de van Lint.

Mahdi Cheraghchi

@TomGur: No estoy seguro de que los códigos BCH cumplan con sus requisitos. Hasta cierto punto, la respuesta depende de cuánto esfuerzo computacional desea que el decodificador ponga a la tarea. Los decodificadores "listos para usar" son decodificadores de distancia acotada, y solo corrigen hasta un límite de decodificación único (<la mitad de la distancia mínima). Para los códigos BCH, una fracción no despreciable del espacio binario está fuera de rango y se producirá un error de decodificador. Solo tener un código no es suficiente a menos que especifique el algoritmo de decodificación (no todos los ECC tienen uno eficiente conocido).

Jyrki Lahtonen