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

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

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

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

Определение

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

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

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

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

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

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

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

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

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

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

Пределы

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

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

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

В ноябре 2021 года сообщалось о двух препринтах. первая полиномиальная конструкция " $c^{3}$-LTC», а именно локально проверяемые коды с постоянной скоростью. $r$, постоянное расстояние $\delta$ и постоянная локальность $q$.

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

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

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

Примеры

Код Адамара

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

Легко видеть, что для любой допустимой кодировки $w$, это уравнение верно, поскольку оно является определением линейной функции. Однако несколько сложнее показать, что строка, которая $\delta$-далеко от C будет иметь верхнюю границу своей ошибки с точки зрения $\delta$. Одна граница находится с помощью прямого подхода аппроксимации вероятности того, что ровно один из трех зондов даст неправильный результат. Пусть A, B и C — события $w(x)$, $w(y)$, и $w(x\oplus y)$ быть неверным. Пусть E будет событием, когда произошло ровно одно из этих событий. Это выходит на

${\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}}$

Это работает для $0<\delta \leq 5/16$, но вскоре после этого $3\delta -6\delta ^{2}<\delta$. При дополнительной работе можно показать, что ошибка ограничена

$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}}$

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

Длинный код

Длинный код — это еще один код с очень большим раздутием, который близок к локальному тестированию. Учитывая ввод $0\leq i\leq 2^{k}$ (обратите внимание, это занимает $k$ биты для представления), функция, которая возвращает $i^{th}$ бит ввода, $f_{i}(x)=x_{i}$, оценивается по всем возможным $2^{k}$-битовые входы $0\leq x\leq 2^{2^{k}}$, а кодовое слово представляет собой их объединение (длиной $n=2^{2^{k}}$). Способ локальной проверки этого с некоторыми ошибками — выбрать равномерно случайный входной сигнал. $x$ и установить $y=x$, но с небольшой вероятностью перевернуть каждый бит, $\mu >0$. Принять функцию $f$ в качестве кодового слова, если $f(x)=f(y)$. Если $f$ это кодовое слово, оно будет принято $f$ пока $x_{i}$ не изменился, что происходит с вероятностью $1-\mu$. Это нарушает требование о том, чтобы кодовые слова всегда принимались, но может быть достаточно для некоторых нужд.

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

См. также

• Граница Гилберта–Варшамова
• Код Хэмминга
• Код расширителя

Внешние ссылки

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