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

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

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

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

Определение

Чтобы измерить расстояние между двумя струнами, Расстояние Хэмминга используется

{displaystyle Delta (x, y) = | {i: x_ {i} eq y_ {i}} |}

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

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

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

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

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

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

Пределы

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

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

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

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

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

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

Примеры

Код Адамара

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

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

{displaystyle {egin {выровнено} P (E) & geq P (Acup Bcup C) -3 * P (Acup B) & geq 3 * P (A) -3 * P (Acup B) -3 * P (Acup B) & geq 3delta -6delta ^ {2} конец {выровнено}}}

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

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

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

Длинный код

В Длинный код это еще один код с очень большим разрывом, близкий к тестируемому локально. Учитывая ввод ${displaystyle 0leq ileq 2 ^ {k}}$ (обратите внимание, это занимает ${displaystyle k}$ бит для представления), функция, которая возвращает ${displaystyle i ^ {th}}$ бит ввода, ${displaystyle f_ {i} (x) = x_ {i}}$ , оценивается по всем возможным ${displaystyle 2 ^ {k}}$ -битовые входы ${displaystyle 0leq xleq 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]

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