Локально тестируемый код

Локально проверяемый код — это тип кода с исправлением ошибок , для которого можно определить, является ли строка словом в этом коде, посмотрев на небольшое (часто постоянное) количество бит строки. В некоторых ситуациях полезно знать, повреждены ли данные, не расшифровывая их полностью, чтобы можно было предпринять соответствующие действия в ответ. Например, в коммуникации, если получатель сталкивается с поврежденным кодом, он может запросить повторную отправку данных, что может повысить точность указанных данных. Аналогично, в хранении данных эти коды могут позволить восстановить поврежденные данные и правильно перезаписать их.

Напротив, локально декодируемые коды используют небольшое количество бит кодового слова для вероятностного восстановления исходной информации. Доля ошибок определяет, насколько вероятно, что декодер правильно восстановит исходный бит; однако, не все локально декодируемые коды локально проверяемы. ^[1]

Очевидно, что любое допустимое кодовое слово должно быть принято как кодовое слово, но строки, которые не являются кодовыми словами, могут иметь только один бит, что потребует много (определенно больше, чем постоянное число) проб. Чтобы учесть это, неудача тестирования определяется только в том случае, если строка имеет ошибку по крайней мере на заданную долю своих бит. Это означает, что слова кода должны быть длиннее входных строк за счет добавления некоторой избыточности.

Для измерения расстояния между двумя строками используется расстояние Хэмминга .

${\displaystyle \Дельта (x,y)=|\{i:x_{i}\neq y_{i}\}|}$

Расстояние строки от кода вычисляется по формуле${\displaystyle w}$${\displaystyle C:\{0,1\}^{k}\to \{0,1\}^{n}}$

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

Относительные расстояния вычисляются как доля числа бит.

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

Код называется локально -тестируемым, если существует машина Тьюринга M, имеющая случайный доступ к входным данным , которая делает не более чем неадаптивные запросы и удовлетворяет следующим условиям: ^[2]${\displaystyle C:\{0,1\}^{k}\to \{0,1\}^{n}}$${\displaystyle д}$${\displaystyle \дельта}$${\displaystyle w}$${\displaystyle д}$${\displaystyle w}$

• Для любого и , . Другими словами, M принимает данный доступ к любому кодовому слову C.${\displaystyle x\in \{0,1\}^{k}}$${\displaystyle w=C(x)}$${\displaystyle Pr[M^{w}(1^{k})=1]=1}$
• Для такого, что , . M должен отвергать строки , далекие от C, по крайней мере, в половине случаев.${\displaystyle w\in \{0,1\}^{n}}$${\displaystyle \delta (w,C)>\delta }$${\displaystyle Pr[M^{w}(1^{k})=1]\leq 1/2}$${\displaystyle \дельта}$

Также скорость кода — это отношение длины сообщения к длине кодового слова.

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

Остается открытым вопрос, существуют ли локально проверяемые коды линейного размера, но есть несколько конструкций, которые считаются «почти линейными»: ^[3]

1. Полином сколь угодно близкий к линейному; для любого , .${\displaystyle \epsilon >0}$${\displaystyle n=k^{1+\epsilon }}$
2. Функции вида , где — функция, стремящаяся к 0. Это приближает n к линейной по мере увеличения k. Например:${\displaystyle n=k^{1+\epsilon (k)}}$${\displaystyle \epsilon (k)}$
   • ${\displaystyle 1/\log \log k}$
   • ${\displaystyle 1/(\log k)^{c}}$для некоторых${\displaystyle c\in (0,1)}$
   • ${\displaystyle \exp((\log \log \log k)^{c})/\log k}$для${\displaystyle c\in (0,1)}$

Оба они были достигнуты, даже при постоянной сложности запроса и двоичном алфавите , например, с помощью для любого . Следующая почти линейная цель линейна с точностью до полилогарифмического множителя; . Никто еще не придумал линейно тестируемый код, удовлетворяющий этому ограничению. ^[3]${\displaystyle n=k^{1+1/(\log k)^{c}}}$${\displaystyle c\in (0,1)}$${\displaystyle n={\text{поли}}(\log k)*k}$

В ноябре 2021 года в двух препринтах сообщалось ^{[4] [5] [6] [7]} о первой конструкции «-LTC» за полиномиальное время, а именно локально тестируемых кодов с постоянной скоростью , постоянным расстоянием и постоянной локальностью .${\displaystyle c^{3}}$${\displaystyle r}$${\displaystyle \дельта}$${\displaystyle д}$

Локально проверяемые коды имеют много общего с вероятностно проверяемыми доказательствами (PCP). Это должно быть очевидно из сходства их конструкции. В обоих случаях нам даются случайные неадаптивные запросы в большую строку, и если мы хотим принять, мы должны с вероятностью 1, а если нет, мы должны принять не более чем в половине случаев. Главное отличие в том, что PCP заинтересованы в принятии, если существует , так что . Локально проверяемые коды, с другой стороны, принимают, если это часть кода. Многое может пойти не так, если предположить, что доказательство PCP кодирует локально проверяемый код. Например, определение PCP ничего не говорит о недействительных доказательствах, только о недействительных входных данных.${\displaystyle д}$${\displaystyle x}$${\displaystyle w}$${\displaystyle М^{w}(x)=1}$${\displaystyle w}$

Несмотря на это различие, локально проверяемые коды и PCP достаточно похожи, поэтому зачастую для построения одного из них доказывающий по ходу дела строит и другой. ^[8]

Один из самых известных кодов исправления ошибок, код Адамара , является локально проверяемым кодом. Кодовое слово x кодируется в коде Адамара как линейная функция (mod 2). Это требует перечисления результата этой функции для каждого возможного y, что требует экспоненциально больше бит, чем ее входные данные. Чтобы проверить, является ли строка w кодовым словом кода Адамара, все, что нам нужно сделать, это проверить, является ли кодируемая ею функция линейной. Это означает простую проверку, являются ли x и y равномерно случайными векторами (где обозначает побитовое XOR ).${\displaystyle f(y)={\sum _{i}{x_{i}y_{i}}}}$${\displaystyle w(x)\oplus w(y)=w(x\oplus y)}$${\displaystyle \oplus}$

Легко видеть, что для любого допустимого кодирования это уравнение верно, поскольку это определение линейной функции. Однако несколько сложнее показать, что строка, которая находится далеко от C, будет иметь верхнюю границу своей ошибки в терминах . Одна граница находится прямым подходом аппроксимации шансов того, что ровно один из трех зондов даст неверный результат. Пусть A, B и C будут событиями , , и будут неверными. Пусть E будет событием того, что ровно один из них произойдет. Это приводит к${\displaystyle w}$${\displaystyle \дельта}$${\displaystyle \дельта}$${\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}}}$

Это работает для , но вскоре после этого, . С дополнительной работой можно показать, что ошибка ограничена${\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}}}$

Для любого заданного значения существует только постоянная вероятность ложных срабатываний, поэтому мы можем просто проверить постоянное количество раз, чтобы получить вероятность ниже 1/2. ^[3]${\displaystyle \delta }$

Длинный код — это еще один код с очень большим раздутием, который близок к локально проверяемому. При наличии входных данных (обратите внимание, что для их представления требуются биты) функция, возвращающая бит входных данных, , оценивается на всех возможных -битных входных данных , а кодовое слово является их конкатенацией (длиной ). Способ локального тестирования с некоторыми ошибками — выбрать равномерно случайные входные данные и установить , но с небольшой вероятностью переворота каждого бита, . Принять функцию в качестве кодового слова, если . Если — кодовое слово, оно будет приниматься до тех пор, пока не изменилось, что происходит с вероятностью . Это нарушает требование, чтобы кодовые слова всегда принимались, но может быть достаточно хорошим для некоторых нужд. ^[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 }$

Другие локально проверяемые коды включают коды Рида-Маллера (см. локально декодируемые коды для алгоритма декодирования), коды Рида-Соломона и короткий код.

• Связано Гилберт–Варшамов
• Код Хэмминга
• Расширительный код

• «Прорывы — локально тестируемые коды с постоянной скоростью, расстоянием и локальностью | Институт теории вычислений Саймонса». simons.berkeley.edu . 6 октября 2021 г.