Código comprobable localmente

Tipo de código de corrección de errores

Un código comprobable localmente es un tipo de código de corrección de errores en el que se puede determinar si una cadena es una palabra en ese código observando una pequeña cantidad (con frecuencia constante) de bits de la cadena. En algunas situaciones, es útil saber si los datos están dañados sin decodificarlos por completo para poder tomar las medidas adecuadas en respuesta. Por ejemplo, en la comunicación, si el receptor encuentra un código dañado, puede solicitar que se vuelvan a enviar los datos, lo que podría aumentar la precisión de dichos datos. De manera similar, en el almacenamiento de datos, estos códigos pueden permitir recuperar los datos dañados y reescribirlos correctamente.

Por el contrario, los códigos decodificables localmente utilizan una pequeña cantidad de bits de la palabra clave para recuperar de manera probabilística 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 se pueden probar localmente. ^[1]

Claramente, cualquier palabra de código válida debe aceptarse como palabra de código, pero las cadenas que no son palabras de código podrían tener un error de solo un bit, lo que requeriría muchas pruebas (ciertamente más de un número constante). Para tener esto en cuenta, la falla de prueba solo se define si la cadena tiene un error de 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

${\displaystyle \Delta (x,y)=|\{i:x_{i}\neq y_{i}\}|}$

La distancia de una cadena a un código se calcula mediante ${\displaystyle w}$ ${\displaystyle C:\{0,1\}^{k}\to \{0,1\}^{n}}$

${\displaystyle \Delta (w,C)=\min _{x}\{\Delta (w,C(x))\}}$

Las distancias relativas se calculan como una fracción del número de bits.

${\displaystyle \delta (x,y)=\Delta (x,y)/n{\text{ and }}\delta (w,C)=\Delta (w,C)/n}$

Un código se denomina -local -comprobable si existe una máquina de Turing M dado acceso aleatorio a una entrada que realiza como máximo consultas no adaptativas y satisface lo siguiente: ^[2] ${\displaystyle C:\{0,1\}^{k}\to \{0,1\}^{n}}$ ${\displaystyle q}$ ${\displaystyle \delta }$ ${\displaystyle w}$ ${\displaystyle q}$ ${\displaystyle w}$

• Para cualquier y , . En otras palabras, M acepta el acceso dado a cualquier palabra de código de C. ${\displaystyle x\in \{0,1\}^{k}}$ ${\displaystyle w=C(x)}$ ${\displaystyle Pr[M^{w}(1^{k})=1]=1}$
• Para tal que , . M debe rechazar cadenas -lejos de C al menos la mitad del tiempo. ${\displaystyle w\in \{0,1\}^{n}}$ ${\displaystyle \delta (w,C)>\delta }$ ${\displaystyle Pr[M^{w}(1^{k})=1]\leq 1/2}$ ${\displaystyle \delta }$

Además, la velocidad de un código es la relación entre la longitud de su mensaje y la longitud de la palabra de código.

${\displaystyle r={\frac {|x|}{|C(x)|}}}$

Límites

Sigue siendo una cuestión abierta si existen códigos de tamaño lineal que se puedan probar localmente, pero hay varias construcciones que se consideran "casi lineales": ^[3]

1. Polinomio arbitrariamente cercano a lineal; para cualquier , . ${\displaystyle \epsilon >0}$ ${\displaystyle n=k^{1+\epsilon }}$
2. Funciones de la forma , donde es una función que tiende a 0. Esto hace que n se acerque más a la linealidad a medida que k aumenta. Por ejemplo: ${\displaystyle n=k^{1+\epsilon (k)}}$ ${\displaystyle \epsilon (k)}$
   • ${\displaystyle 1/\log \log k}$
   • ${\displaystyle 1/(\log k)^{c}}$Para algunos ${\displaystyle c\in (0,1)}$
   • ${\displaystyle \exp((\log \log \log k)^{c})/\log k}$para ${\displaystyle c\in (0,1)}$

Ambos se han logrado, incluso con una complejidad de consulta constante y un alfabeto binario , como con for any . El siguiente objetivo casi lineal es lineal hasta un factor polilogarítmico ; . Nadie ha logrado aún un código linealmente comprobable que satisfaga esta restricción. ^[3] ${\displaystyle n=k^{1+1/(\log k)^{c}}}$ ${\displaystyle c\in (0,1)}$ ${\displaystyle n={\text{poly}}(\log k)*k}$

En noviembre de 2021, dos preimpresiones informaron ^{[4] [5] [6] [7]} la primera construcción en tiempo polinomial de " -LTC", es decir, códigos comprobables localmente con tasa constante , distancia constante y localidad constante . ${\displaystyle c^{3}}$ ${\displaystyle r}$ ${\displaystyle \delta }$ ${\displaystyle q}$

Conexión con pruebas probabilísticamente comprobables

Los códigos comprobables localmente tienen mucho en común con las pruebas comprobables probabilísticamente (PCP). Esto debería ser evidente a partir de las similitudes de su construcción. En ambos, se nos dan consultas aleatorias no adaptativas en una cadena grande y si queremos aceptar, debemos hacerlo con una probabilidad de 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 tal que . Los códigos comprobables localmente, por otro lado, aceptan si es parte del código. Muchas cosas pueden salir mal al suponer que una prueba 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. ${\displaystyle q}$ ${\displaystyle x}$ ${\displaystyle w}$ ${\displaystyle M^{w}(x)=1}$ ${\displaystyle w}$

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 sobre la marcha. ^[8]

Ejemplos

Código Hadamard

Uno de los códigos de corrección de errores más famosos, el código Hadamard , es un código que se puede probar localmente. En el código Hadamard, una palabra clave x se codifica como la función lineal (mod 2). Esto requiere enumerar el resultado de esta función para cada posible y, 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 verificar si para x e y hay vectores uniformemente aleatorios (donde denota XOR bit a bit ). ${\displaystyle f(y)={\sum _{i}{x_{i}y_{i}}}}$ ${\displaystyle w(x)\oplus w(y)=w(x\oplus y)}$ ${\displaystyle \oplus }$

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. Sin embargo, algo más difícil es demostrar que una cadena que está -lejos de C tendrá un límite superior en su error en términos de . Un límite se encuentra mediante el enfoque directo de aproximar las probabilidades de que exactamente una de las tres sondas arroje un resultado incorrecto. Sean A, B y C los eventos de , , y que sean incorrectos. Sea E el evento de que ocurra exactamente uno de estos. Esto resulta en ${\displaystyle w}$ ${\displaystyle \delta }$ ${\displaystyle \delta }$ ${\displaystyle w(x)}$ ${\displaystyle w(y)}$ ${\displaystyle w(x\oplus y)}$

${\displaystyle {\begin{aligned}P(E)&\geq P(A\cup B\cup C)-3*P(A\cup B)\\&\geq 3*P(A)-3*P(A\cup B)-3*P(A\cup B)\\&\geq 3\delta -6\delta ^{2}\end{aligned}}}$

Esto funciona para , pero poco después, . Con trabajo adicional, se puede demostrar que el error está limitado por ${\displaystyle 0<\delta \leq 5/16}$ ${\displaystyle 3\delta -6\delta ^{2}<\delta }$

${\displaystyle f(x)={\begin{cases}3\delta -6\delta ^{2}&:0\leq \delta \leq 5/16\\45/128&:5/16\leq \delta \leq 45/128\\\delta &:45/128\leq \delta \leq 1/2\end{cases}}}$

Para cualquier valor dado , esto solo tiene una probabilidad constante de falsos positivos, por lo que podemos simplemente verificar un número constante de veces para obtener la probabilidad por debajo de 1/2. ^[3] ${\displaystyle \delta }$

Código largo

El código Long es otro código con una explosión muy grande que está cerca de ser comprobable localmente. Dada una entrada (nótese que esto requiere bits para representarse), la función que devuelve el bit de la entrada, , se evalúa en todas las posibles entradas de -bit , y la palabra de código es la concatenación de estas (de longitud ). La forma de probar esto localmente con algunos errores es elegir una entrada aleatoria uniforme y establecer , pero con una pequeña posibilidad de invertir cada bit, . Acepte una función como una palabra de código si . Si es una palabra de código, esto aceptará siempre que no haya cambiado, lo que sucede con una probabilidad . Esto viola el requisito de que las palabras de código siempre se acepten, pero puede ser lo suficientemente bueno para algunas necesidades. ^[9] ${\displaystyle 0\leq i\leq 2^{k}}$ ${\displaystyle k}$ ${\displaystyle i^{th}}$ ${\displaystyle f_{i}(x)=x_{i}}$ ${\displaystyle 2^{k}}$ ${\displaystyle 0\leq x\leq 2^{2^{k}}}$ ${\displaystyle n=2^{2^{k}}}$ ${\displaystyle x}$ ${\displaystyle y=x}$ ${\displaystyle \mu >0}$ ${\displaystyle f}$ ${\displaystyle f(x)=f(y)}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle x_{i}}$ ${\displaystyle 1-\mu }$

Otros códigos comprobables localmente incluyen los códigos Reed-Muller (consulte los códigos decodificables localmente para obtener un algoritmo de decodificación), los códigos Reed-Solomon y el código corto.

Véase también

• Límite Gilbert-Varshamov
• Código de Hamming
• Código de expansión

Referencias

1. Kaufman, Tali ; Viderman, Michael. "Códigos comprobables localmente frente a códigos decodificables localmente".
2. Ben-Sasson, Eli; Sudan, Madhu. "Códigos robustos y comprobables localmente y productos de códigos" (PDF) .
3. Goldreich, Oded (2005). "Códigos y pruebas breves comprobables localmente (encuesta)". CiteSeerX 10.1.1.110.2530 . 
4. Panteleev, Pavel; Kalachev, Gleb (5 de noviembre de 2021). "Códigos LDPC clásicos cuánticos asintóticamente buenos y comprobables localmente". arXiv : 2111.03654 [cs.IT].
5. Dinur, Irit ; Evra, Shai ; Livne, Ron; Lubotzky, Alexander ; Mozes, Shahar (8 de noviembre de 2021). "Códigos comprobables localmente con velocidad, distancia y localidad constantes". arXiv : 2111.04808 [cs.IT].
6. Rorvig, Mordechai (24 de noviembre de 2021). "Los investigadores derrotan la aleatoriedad para crear un código ideal". Quanta Magazine . Consultado el 24 de noviembre de 2021 .
7. Rorvig, Mordechai (6 de enero de 2022). "Los investigadores demuestran que los qubits pueden ser tan seguros como los bits". Quanta Magazine . Consultado el 2 de febrero de 2022 .
8. Cheraghchi, Mahdi. "Códigos comprobables localmente".
9. Kol, Gillat; Raz, Ran. "Límites en códigos comprobables localmente con pruebas únicas" (PDF) .

Enlaces externos

• "Avances: códigos comprobables localmente con velocidad, distancia y localidad constantes | Instituto Simons para la teoría de la computación". simons.berkeley.edu . 6 de octubre de 2021.