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

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

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

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

Определение [ править ]

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

${\displaystyle \Delta (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{ and }}\delta (w,C)=\Delta (w,C)/n}$

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

Ограничения [ править ]

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

1. Многочлен сколь угодно близок к линейному; для любого , .${\displaystyle \epsilon >0}$${\displaystyle n=k^{1+\epsilon }}$
2. Функции вида , где - функция, стремящаяся к нулю. Это приближает 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)}$

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

Связь с вероятностно проверяемыми доказательствами [ править ]

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

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

Примеры [ править ]

Код Адамара [ править ]

Один из самых известных кодов с исправлением ошибок, код Адамара , является локально тестируемым кодом. Кодовое слово x закодировано в коде Адамара как линейная функция (mod 2). Это требует перечисления результата этой функции для каждого возможного y, что требует экспоненциально большего количества бит, чем его вход. Чтобы проверить, является ли строка w кодовым словом кода Адамара, все, что нам нужно сделать, это проверить, является ли функция, которую она кодирует, линейной. Это означает простую проверку того, являются ли для x и y равномерно случайными векторами (где означает побитовое исключающее ИЛИ ).${\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 \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}}}$

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

Длинный код [ править ]

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

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

Ссылки [ править ]