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

Тип кода, исправляющего ошибки

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

Напротив, локально декодируемые коды используют небольшое количество битов кодового слова для вероятностного восстановления исходной информации. Доля ошибок определяет, насколько вероятно, что декодер правильно восстановит исходный бит; однако не все локально декодируемые коды пригодны для локального тестирования. ^[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 }$

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

${\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{poly}}(\log k)*k}$

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

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

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

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

Примеры

Код Адамара

Один из самых известных кодов исправления ошибок — код Адамара — является локально тестируемым кодом. Кодовое слово x кодируется в коде Адамара как линейная функция (по модулю 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 }$

Длинный код

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

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

Смотрите также

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

Рекомендации

1. Кауфман, Тали ; Видерман, Майкл. «Локально проверяемые и локально декодируемые коды».
2. Бен-Сассон, Эли; Судан, Мадху. «Надежные локально проверяемые коды и продукты кодов» (PDF) .
3. Goldreich, Одед (2005). «Краткие локально проверяемые коды и доказательства (обзор)». CiteSeerX 10.1.1.110.2530 . 
4. Пантелеев, Павел; Калачев, Глеб (05.11.2021). «Асимптотически хорошие квантовые и локально проверяемые классические коды LDPC». arXiv : 2111.03654 [cs.IT].
5. Динур, Ирит ; Эвра, Шай ; Ливн, Рон; Любоцкий, Александр ; Мозес, Шахар (08 ноября 2021 г.). «Локально проверяемые коды с постоянной скоростью, расстоянием и местоположением». arXiv : 2111.04808 [cs.IT].
6. Рорвиг, Мордехай (24 ноября 2021 г.). «Исследователи побеждают случайность, чтобы создать идеальный код». Журнал Кванта . Проверено 24 ноября 2021 г.
7. Рорвиг, Мордехай (6 января 2022 г.). «Кубиты могут быть такими же безопасными, как и биты, показывают исследователи». Журнал Кванта . Проверено 2 февраля 2022 г.
8. Черагчи, Махди. «Локально проверяемые коды».
9. Кол, Гиллат; Раз, Ран. «Границы локально проверяемых кодов с уникальными тестами» (PDF) .

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

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