Código localmente decodificable

---

Un código decodificable localmente (LDC) es un código de corrección de errores que permite decodificar un solo bit del mensaje original con alta probabilidad al examinar (o consultar) solo una pequeña cantidad de bits de una palabra clave posiblemente corrupta . ^{[1] [2] [3]} Esta propiedad podría ser útil, por ejemplo, en un contexto donde la información se transmite a través de un canal ruidoso, y solo se requiere un pequeño subconjunto de los datos en un momento determinado y no hay necesidad de decodificar el mensaje completo a la vez. Tenga en cuenta que los códigos decodificables localmente no son un subconjunto de los códigos comprobables localmente , aunque existe cierta superposición entre los dos. ^[4]

Las palabras en clave se generan a partir del mensaje original utilizando un algoritmo que introduce una cierta cantidad de redundancia en la palabra en clave; por lo tanto, la palabra clave siempre es más larga que el mensaje original. Esta redundancia se distribuye a lo largo de la palabra clave y permite recuperar el mensaje original con buena probabilidad incluso en presencia de errores. Cuanto más redundante sea la palabra clave, más resistente será frente a los errores y se requerirán menos consultas para recuperar un poco del mensaje original.

Más formalmente, un código localmente decodificable codifica un mensaje de bits en una palabra de código de bits, de modo que cualquier bit del mensaje se puede recuperar con probabilidad mediante el uso de un algoritmo de decodificación aleatorio que consulta solo bits de la palabra de código , incluso si hasta ubicaciones de la palabra clave se ha corrompido.${\ estilo de visualización (q, \ delta, \ épsilon)}$${\ estilo de visualización n}$${\ estilo de visualización x}$${\ estilo de visualización N}$${\ estilo de visualización C (x)}$${\ estilo de visualización x_ {i}}$${\ estilo de visualización 1-\ épsilon}$${\ estilo de visualización q}$${\ estilo de visualización C (x)}$${\displaystyle \delta N}$

Además, un decodificador local perfectamente fluido es un decodificador tal que, además de generar siempre la salida correcta con acceso a una palabra de código no corrupta, para cada y la consulta para recuperar el bit es uniforme . ^[5] (La notación denota el conjunto ). Informalmente, esto significa que el conjunto de consultas requeridas para decodificar cualquier bit dado se distribuye uniformemente sobre la palabra clave.${\displaystyle j\in [q]}$${\displaystyle i\in [n]}$${\displaystyle j^{th}}$${\displaystyle i^{th}}$${\displaystyle [N]}$${\displaystyle [y]}$${\displaystyle \{1,\ldots ,y\}}$

---