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 examinando (o preguntando) solo una pequeña cantidad de bits de una palabra de código posiblemente dañada . [1] [2] [3] Esta propiedad podría ser útil, digamos, 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 particular y no es necesario decodificar el mensaje completo a la vez. Tenga en cuenta que los códigos decodificables localmente no son un subconjunto de códigos comprobables localmente , aunque existe cierta superposición entre los dos. [4]
Las palabras de código se generan a partir del mensaje original utilizando un algoritmo que introduce una cierta cantidad de redundancia en la palabra de código; por lo tanto, la palabra clave siempre es más larga que el mensaje original. Esta redundancia se distribuye a través de la palabra de código y permite recuperar el mensaje original con buena probabilidad incluso en presencia de errores. Cuanto más redundante sea la palabra de código, más resistente será contra los errores y menos consultas necesarias para recuperar un poco del mensaje original.
Descripción general
Más formalmente, un -código decodificable localmente codifica un -mensaje de bits a una -palabra de código de bits tal que cualquier pedacito del mensaje se puede recuperar con probabilidad mediante el uso de un algoritmo de decodificación aleatorio que solo consulta bits de la palabra en clave , incluso si hasta las ubicaciones de la palabra de código se han corrompido.
Además, un decodificador local perfectamente fluido es un decodificador tal que, además de generar siempre la salida correcta, se da acceso a una palabra de código no corrupta, para cada y la consulta para recuperar el poco es uniforme sobre . [5] (La notación denota el conjunto ). De manera informal, esto significa que el conjunto de consultas necesarias para decodificar cualquier bit dado se distribuye uniformemente sobre la palabra de código.
Los decodificadores de listas locales son otro subconjunto interesante de decodificadores locales. La decodificación de listas es útil cuando una palabra de código está dañada en más de lugares donde es la distancia mínima de Hamming entre dos palabras de código. En este caso, ya no es posible identificar exactamente qué mensaje original se ha codificado, ya que podría haber varias palabras de código dentrodistancia de la palabra de código dañada. Sin embargo, dado un radio, es posible identificar el conjunto de mensajes que se codifican en palabras de código que se encuentran dentro de la palabra de código dañada. Un límite superior en el tamaño del conjunto de mensajes se puede determinar mediante y . [6]
Los códigos decodificables localmente también se pueden concatenar, donde un mensaje se codifica primero usando un esquema, y la palabra de código resultante se codifica nuevamente usando un esquema diferente. (Tenga en cuenta que, en este contexto, la concatenación es el término utilizado por los eruditos para referirse a lo que generalmente se llama composición ; ver [5] ). Esto puede ser útil si, por ejemplo, el primer código tiene algunas propiedades deseables con respecto a la tasa, pero tiene alguna propiedad indeseable, como producir una palabra de código sobre un alfabeto no binario. El segundo código puede transformar el resultado de la primera codificación sobre un alfabeto no binario en un alfabeto binario. La codificación final todavía se puede decodificar localmente y requiere pasos adicionales para decodificar ambas capas de codificación. [7]
Longitud de la palabra clave y complejidad de la consulta
La tasa de un código se refiere a la relación entre la longitud de su mensaje y la longitud de la palabra de código: y el número de consultas necesarias para recuperar 1 bit del mensaje se denomina complejidad de consulta de un código.
La tasa de un código está inversamente relacionada con la complejidad de la consulta, pero la forma exacta de esta compensación es un gran problema abierto. [8] [9] Se sabe que no hay LDC que consulten la palabra de código en una sola posición, y que el tamaño óptimo de la palabra de código para la complejidad de la consulta 2 es exponencial en el tamaño del mensaje original. [8] Sin embargo, no se conocen límites inferiores estrictos para los códigos con una complejidad de consulta superior a 2. Al acercarse a la compensación desde el lado de la longitud de la palabra de código, los únicos códigos conocidos con una longitud de palabra de código proporcional a la longitud del mensaje tienen complejidad de consulta por [8] [ necesita actualización ] También hay códigos intermedios, que tienen palabras en clave polinomiales en el tamaño del mensaje original y complejidad de consulta polilogarítmica. [8]
Aplicaciones
Los códigos decodificables localmente tienen aplicaciones para la transmisión y el almacenamiento de datos, la teoría de la complejidad, las estructuras de datos, la desaleatorización, la teoría del cálculo tolerante a fallas y los esquemas de recuperación de información privada. [9]
Transmisión y almacenamiento de datos
Los códigos decodificables localmente son especialmente útiles para la transmisión de datos a través de canales ruidosos. El código Hadamard (un caso especial de los códigos Reed Muller) fue utilizado en 1971 por Mariner 9 para transmitir imágenes de Marte a la Tierra. Se eligió en lugar de un código de 5 repeticiones (donde cada bit se repite 5 veces) porque, para aproximadamente el mismo número de bits transmitidos por píxel, tenía una mayor capacidad de corrección de errores. (El código Hadamard cae bajo el paraguas general de la corrección de errores hacia adelante , y resulta que es decodificable localmente; el algoritmo real utilizado para decodificar la transmisión desde Marte era un esquema genérico de corrección de errores). [10]
Los LDC también son útiles para el almacenamiento de datos, donde el medio puede dañarse parcialmente con el tiempo o el dispositivo de lectura está sujeto a errores. En ambos casos, un LDC permitirá la recuperación de información a pesar de los errores, siempre que haya relativamente pocos. Además, los PMA no exigen que se decodifique todo el mensaje original; un usuario puede decodificar una parte específica del mensaje original sin necesidad de decodificar todo. [11]
Teoría de la complejidad
Una de las aplicaciones de los códigos decodificables localmente en la teoría de la complejidad es la amplificación de la dureza. Utilizando LDC con longitud de palabra de código polinomial y complejidad de consulta polilogarítmica, se puede tomar una función que es difícil de resolver en las entradas del peor de los casos y diseñar una función eso es difícil de calcular en entradas de casos promedio.
Considerar limitado solo a la longitud entradas. Entonces podemos ver como una cadena binaria de longitud , donde cada bit es para cada . Podemos usar un código decodificable localmente de longitud polinomial con complejidad de consulta polilogarítmica que tolera una fracción constante de errores para codificar la cadena que representa para crear una nueva cadena de longitud . Creemos que esta nueva cadena define un nuevo problema en longitud entradas. Si es fácil de resolver en promedio, es decir, podemos resolver correctamente en una gran fracción de entradas, luego por las propiedades de la LDC usada para codificarla, podemos usar calcular probabilísticamente en todas las entradas. Por lo tanto, una solución a para la mayoría de las entradas nos permitiría resolver en todas las entradas, contradiciendo nuestra suposición de que es difícil para las entradas del peor de los casos. [5] [8] [12]
Esquemas de recuperación de información privada
Un esquema de recuperación de información privada permite a un usuario recuperar un elemento de un servidor en posesión de una base de datos sin revelar qué elemento se recupera. Una forma común de garantizar la privacidad es tenerservidores separados que no se comunican, cada uno con una copia de la base de datos. Dado un esquema apropiado, el usuario puede realizar consultas a cada servidor que individualmente no revelan qué bit está buscando el usuario, pero que en conjunto brindan suficiente información para que el usuario pueda determinar el bit particular de interés en la base de datos. [3] [11]
Se puede ver fácilmente que los códigos decodificables localmente tienen aplicaciones en este entorno. Un procedimiento general para producir un-esquema de información privada del servidor de una manera perfectamente fluida -La consulta de código decodificable localmente es la siguiente:
Dejar ser un LDC perfectamente fluido que codifique -bit mensajes a -palabras en clave de bits. Como paso de preprocesamiento, cada uno de los servidores codifica el base de datos de bits con el codigo , por lo que ahora cada servidor almacena el -palabra de código de bits . Un usuario interesado en obtener el un poco de genera aleatoriamente un conjunto de consultas tal que se puede calcular a partir de usando el algoritmo de decodificación local por . El usuario envía cada consulta a un servidor diferente y cada servidor responde con el bit solicitado. El usuario luego usa computar de las respuestas. [8] [11] Dado que el algoritmo de decodificación es perfectamente fluido, cada consultase distribuye uniformemente sobre la palabra clave; por lo tanto, ningún servidor individual puede obtener información sobre las intenciones del usuario, por lo que el protocolo es privado siempre que los servidores no se comuniquen. [11]
Ejemplos de
El código Hadamard
El código Hadamard (o Walsh-Hadamard) es un ejemplo de un código simple decodificable localmente que mapea una cadena de longitud a una palabra en clave de longitud . La palabra en clave de una cadena se construye de la siguiente manera: para cada , la bit de la palabra de código es igual a , dónde (mod 2). Es fácil ver que cada palabra en clave tiene una distancia de Hamming de de cualquier otra palabra en clave.
El algoritmo de decodificación local tiene una complejidad de consulta 2, y todo el mensaje original se puede decodificar con buena probabilidad si la palabra de código se corrompe en menos de de sus bits. Para, si la palabra de código está dañada en un fracción de lugares, un algoritmo de decodificación local puede recuperar la poco del mensaje original con probabilidad .
Prueba: dada una palabra en clave y un índice , el algoritmo para recuperar el un poco del mensaje original funciona de la siguiente manera:
Dejar consulte el vector en que tiene 1 en el posición y ceros en otros lugares. Para, denota el bit único en que corresponde a . El algoritmo elige un vector aleatorio y el vector (dónde denota XOR bit a bit ). Las salidas del algoritmo (mod 2).
Corrección: por linealidad,
Pero , así que solo tenemos que mostrar que y con buena probabilidad.
Desde y están distribuidos uniformemente (aunque sean dependientes), el límite de unión implica que y con probabilidad al menos . Nota: para ampliar la probabilidad de éxito, se puede repetir el procedimiento con diferentes vectores aleatorios y obtener la respuesta mayoritaria. [13]
El código Reed-Muller
La idea principal detrás de la decodificación local de los códigos Reed-Muller es la interpolación polinómica . El concepto clave detrás de un código Reed-Muller es un polinomio multivariante de grados en variables. El mensaje se trata como la evaluación de un polinomio en un conjunto de puntos predefinidos. Para codificar estos valores, se extrapola un polinomio de ellos, y la palabra clave es la evaluación de ese polinomio en todos los puntos posibles. En un nivel alto, para decodificar un punto de este polinomio, el algoritmo de decodificación elige un conjunto de puntos en una línea que pasa por el punto de interés . Luego consulta la palabra clave para la evaluación del polinomio en puntos ene interpola ese polinomio. Entonces es simple evaluar el polinomio en el punto que producirá. Esta forma indirecta de evaluar es útil porque (a) el algoritmo se puede repetir usando diferentes líneas a través del mismo punto para mejorar la probabilidad de corrección, y (b) las consultas se distribuyen uniformemente sobre la palabra de código.
Más formalmente, dejemos ser un campo finito, y dejar ser números con . El código Reed-Muller con parámetros es la función RM: que mapea cada -polinomio variable encima de grado total a los valores de en todas las entradas en . Es decir, la entrada es un polinomio de la forma especificado por la interpolación de la valores de los puntos predefinidos y la salida es la secuencia para cada . [14]
Para recuperar el valor de una titulación polinomio en un punto , el decodificador local dispara una línea afín aleatoria a través de. Entonces escoge puntos en esa línea, que utiliza para interpolar el polinomio y luego evaluarlo en el punto donde el resultado es . Para hacerlo, el algoritmo elige un vector uniformemente al azar y considera la línea mediante . El algoritmo elige un subconjunto arbitrario de , dónde y consulta las coordenadas de la palabra de código que corresponden a puntos para todos y obtiene valores . Luego usa la interpolación polinomial para recuperar el polinomio univariante único con grado menor o igual a tal que para todos . Luego, para obtener el valor de, solo evalúa . Para recuperar un solo valor del mensaje original, se eligeser uno de los puntos que define el polinomio. [8] [14]
Cada consulta individual se distribuye uniformemente al azar sobre la palabra de código. Por lo tanto, si la palabra en clave se corrompe en un fracción de ubicaciones, por el límite de unión, la probabilidad de que el algoritmo muestree solo coordenadas no corrompidas (y por lo tanto recupere correctamente el bit) es al menos . [8] Para otros algoritmos de decodificación, consulte. [8]
Ver también
Referencias
- ^ Sergey Yekhanin. "Códigos decodificables localmente: una breve encuesta" (PDF) .
- ^ Rafail Ostrovsky; Omkant Pandey; Amit Sahai. "Códigos privados decodificables localmente" (PDF) .
- ^ a b Sergey Yekhanin. Nuevos códigos decodificables localmente y esquemas de recuperación de información privada, Informe técnico ECCC TR06-127 , 2006.
- ^ Tali Kaufman; Michael Viderman. "Códigos localmente comprobables frente a códigos decodificables localmente" .
- ^ a b c Luca Trevisan. "Algunas aplicaciones de la teoría de la codificación en la complejidad computacional" (PDF) .
- ^ Arora, Sanjeev ; Barak, Boaz (2009). "Sección 19.5". Complejidad computacional: un enfoque moderno . Cambridge . ISBN 978-0-521-42426-4.
- ^ Arora y Barak 2009 , sección 19.4.3
- ^ a b c d e f g h yo Sergey Yekhanin. "Códigos decodificables localmente" (PDF) .
- ^ a b Sergey Yekhanin. "Códigos decodificables localmente" (PDF) .
- ^ "Combinatoria en el espacio El sistema de telemetría Mariner 9" (PDF) .
- ^ a b c d Sergey Yekhanin. "Recuperación de información privada" (PDF) .
- ^ Arora y Barak 2009 , sección 19.4
- ^ Arora y Barak 2009 , sección 11.5.2
- ^ a b Arora y Barak 2009 , sección 19.4.2