Un código comprobable localmente es un tipo de código de corrección de errores para el cual se puede determinar si una cadena es una palabra en ese código mirando un número pequeño (frecuentemente constante) de bits de la cadena. En algunas situaciones, es útil saber si los datos están dañados sin decodificarlos todos para que se puedan tomar las medidas adecuadas en respuesta. Por ejemplo, en la comunicación, si el receptor encuentra un código corrupto, puede solicitar que se reenvíen los datos, lo que podría aumentar la precisión de dichos datos. Del mismo modo, en el almacenamiento de datos, estos códigos pueden permitir que los datos dañados se recuperen y se vuelvan a escribir correctamente.
Por el contrario, los códigos decodificables localmente utilizan una pequeña cantidad de bits de la palabra de código para recuperar probabilísticamente la información original. La fracción de errores determina la probabilidad de que el decodificador recupere correctamente el bit original; sin embargo, no todos los códigos decodificables localmente son comprobables localmente. [1]
Claramente, cualquier palabra de código válida debe aceptarse como una palabra de código, pero las cadenas que no son palabras de código podrían tener solo un bit de diferencia, lo que requeriría muchas sondas (ciertamente más que un número constante). Para tener en cuenta esto, la falla de prueba solo se define si la cadena está desfasada por al menos una fracción establecida de sus bits. Esto implica que las palabras del código deben ser más largas que las cadenas de entrada agregando algo de redundancia.
Definición
Para medir la distancia entre dos cuerdas, se utiliza la distancia de Hamming
La distancia de una cuerda de un código es calculado por
Las distancias relativas se calculan como una fracción del número de bits.
Un codigo se llama -local -Estable si existe una máquina de Turing M a la que se le ha dado acceso aleatorio a una entrada que hace como mucho consultas no adaptables de y satisface lo siguiente: [2]
- Para cualquier y , . En otras palabras, M acepta el acceso dado a cualquier palabra clave de C.
- Para tal que , . M debe rechazar cadenas-lejos de C al menos la mitad del tiempo.
Limites
Sigue siendo una pregunta abierta si existen códigos de tamaño lineal comprobables localmente, pero hay varias construcciones que se consideran "casi lineales": [3]
- Polinomio arbitrariamente cercano a lineal; para cualquier, .
- Funciones del formulario , dónde es una función que tiende hacia 0. Esto hace que n se acerque más a lineal a medida que k aumenta. Por ejemplo:
- para algunos
- por
Ambos se han logrado, incluso con una complejidad de consulta constante y un alfabeto binario , como con para cualquier . El siguiente objetivo casi lineal es lineal hasta un factor polilogarítmico ;. Nadie ha creado todavía un código comprobable linealmente que satisfaga esta restricción. [3]
Conexión con pruebas comprobables probabilísticamente
Los códigos comprobables localmente tienen mucho en común con las pruebas comprobables probabilísticamente (PCP). Esto debería ser evidente por las similitudes de su construcción. En ambos, se nos daconsultas aleatorias no adaptativas en una cadena grande y si queremos aceptar, debemos con probabilidad 1, y si no, debemos aceptar no más de la mitad de las veces. La principal diferencia es que los PCP están interesados en aceptar si existe un así que eso . Los códigos comprobables localmente, por otro lado, aceptansi es parte del código. Muchas cosas pueden salir mal asumiendo que una prueba de PCP codifica un código comprobable localmente. Por ejemplo, la definición de PCP no dice nada sobre pruebas inválidas, solo entradas inválidas.
A pesar de esta diferencia, los códigos comprobables localmente y los PCP son lo suficientemente similares como para que, con frecuencia, para construir uno, un probador construya el otro a lo largo del camino. [4]
Ejemplos de
Código Hadamard
Uno de los códigos de corrección de errores más famosos, el código Hadamard , es un código comprobable localmente. Una palabra de código x está codificada en el código de Hadamard para ser la función lineal(mod 2). Esto requiere enumerar el resultado de esta función para cada y posible, lo que requiere exponencialmente más bits que su entrada. Para probar si una cadena w es una palabra clave del código Hadamard, todo lo que tenemos que hacer es probar si la función que codifica es lineal. Esto significa simplemente comprobar sipara xey vectores uniformemente aleatorios (dondedenota XOR bit a bit ).
Es fácil ver que para cualquier codificación válida , esta ecuación es verdadera, ya que esa es la definición de una función lineal. Un poco más difícil, sin embargo, es mostrar que una cadena que es-lejos de C tendrá un límite superior en su error en términos de . Se encuentra un límite mediante el enfoque directo de aproximar las posibilidades de que exactamente una de las tres sondas produzca un resultado incorrecto. Sean A, B y C los eventos de, , y siendo incorrecto. Sea E el evento de que ocurra exactamente uno de estos. Esto sale a
Esto funciona para , pero poco después, . Con trabajo adicional, se puede demostrar que el error está limitado por
Para cualquier dado , esto solo tiene una probabilidad constante de falsos positivos, por lo que simplemente podemos verificar un número constante de veces para obtener la probabilidad por debajo de 1/2. [3]
Código largo
El código largo es otro código con una ampliación muy grande que está cerca de ser comprobable localmente. Dada una entrada (nota, esto requiere bits para representar), la función que devuelve el poco de la entrada, , se evalúa en todos los posibles entradas de bits , y la palabra clave es la concatenación de estos (de longitud ). La forma de probar esto localmente con algunos errores es elegir una entrada uniformemente aleatoria y establecer , pero con una pequeña posibilidad de cambiar cada bit, . Aceptar una función como palabra clave si . Si es una palabra en clave, esto aceptará Mientras no cambió, lo que ocurre con probabilidad . Esto viola el requisito de que las palabras en clave siempre se acepten, pero pueden ser lo suficientemente buenas para algunas necesidades. [5]
Otros códigos comprobables localmente incluyen códigos Reed-Muller (ver códigos decodificables localmente para un algoritmo de decodificación), códigos Reed-Solomon y el código corto.
Referencias
- ^ Kaufman, Tali; Viderman, Michael. "Códigos localmente comprobables frente a códigos decodificables localmente" .
- ^ Ben-Sasson, Eli; Sudán, Madhu. "Códigos y productos de códigos robustos y comprobables localmente" (PDF) .
- ^ a b c Goldreich, Oded. "Pruebas y códigos breves comprobables localmente (encuesta)" . CiteSeerX 10.1.1.110.2530 .
- ^ Cheraghchi, Mahdi. "Códigos comprobables localmente" .
- ^ Kol, Gillat; Raz, Ran. "Límites de códigos comprobables localmente con pruebas únicas" (PDF) .