¿Buenos códigos decodificables por circuitos de tamaño lineal?

Estoy buscando códigos de corrección de errores del siguiente tipo:

códigos binarios con tasa constante,
decodificable a partir de una fracción constante de errores, por un decodificador implementable como un circuito booleano de tamaño , donde es la longitud de codificación. $O(N)$ $N$

Algunos antecedentes:

Spielman, en códigos de corrección de errores codificables y decodificables en tiempo lineal , proporcionó códigos decodificables en tiempo en el modelo RAM de costo logarítmico , y también decodificables por circuitos de tamaño . $O(N)$ $O(N \log N)$
Guruswami e Indyk dieron una construcción mejorada en códigos codificables / decodificables de tiempo lineal con una tasa casi óptima . No analizan la complejidad del circuito resultante, aunque creo que también es . $\Theta(N \log N)$

¡Gracias por adelantado!

co.combinatorics it.information-theory coding-theory Andy Drucker
fuente

Andy, casualmente, también me encontré con este problema hace aproximadamente un año y después de una breve búsqueda, llegó a la conclusión de que la pregunta estaba abierta. Entonces, también tengo curiosidad si se sabe una respuesta.

arnab

Este informe de ECCC acaba de salir. No lo he comprobado, pero espero que también dé el circuito

Θ (N \log N)

$\Theta(N \log N)$

Peter Shor

¿Se puede lograr la decodificación

en el modelo AWGN o en el modelo binario?

O (N)

$O(N)$

T ....

Los buenos códigos binarios que son completamente codificables y descodificables en tiempo completamente lineal (

) y logran una tasa de error

donde

es la longitud de bloque del código probablemente requiera una idea fundamentalmente nueva. Lo mejor hasta ahora es a lo largo de las líneas del teorema

en arxiv.org/pdf/1304.4321v2.pdf . Veamos si alguien mejora el

allí en el tiempo de codificación y decodificación

que creo que debería ser posible (incluso con

O (N)

$O(N)$

2^{- N}

$2^{-N}$

N

$N$

1

$1$

2^{- N^{0.49}}

$2^{-N^{0.49}}$

2^{- N^{1 - μ}}

$2^{-N^{1-\mu}}$

N^{1 + ϵ}

$N^{1+\epsilon}$

). Sin embargo, llevar

puede necesitar más que unos pocos trucos.

μ = 0

$\mu=0$

ϵ

$\epsilon$

0

$0$

T ....

Echa un vistazo a los códigos de expansión. Estos códigos logran codificación y decodificación de tiempo lineal. La linealidad es wrt al tamaño de la palabra de código. Pero no estoy seguro de si pueden decodificarse utilizando circuitos lineales.

Vivek Bagaria

¿Buenos códigos decodificables por circuitos de tamaño lineal?

Respuestas: