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

Локально декодируемый код (НРС) является исправлением ошибок коды , который позволяет один битый исходного сообщение, подлежащий декодированию с высокой вероятностью лишь изучение (или запросов) небольшое числа бит , возможно , поврежден кодовым слова . ^{[1] [2] [3]} Это свойство может быть полезно, например, в контексте, когда информация передается по зашумленному каналу, и только небольшое подмножество данных требуется в определенное время, и нет необходимости декодировать все сообщение сразу. Обратите внимание, что локально декодируемые коды не являются подмножеством локально тестируемых кодов , хотя между ними есть некоторое перекрытие. ^[4]

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

Обзор [ править ]

Более формально, локально декодируемый код кодирует -битовое сообщение в -битовое кодовое слово , так что любой бит сообщения может быть восстановлен с вероятностью с помощью алгоритма рандомизированного декодирования, который запрашивает только биты кодового слова , даже если до местоположений кодовое слово повреждено.${\ Displaystyle (д, \ дельта, \ эпсилон)}$${\ displaystyle n}$${\ displaystyle x}$${\ displaystyle N}$${\ Displaystyle C (х)}$${\ displaystyle x_ {i}}$${\ displaystyle 1- \ epsilon}$${\ displaystyle q}$${\ Displaystyle C (х)}$${\ displaystyle \ delta N}$

Кроме того, совершенно гладкая локальный декодер декодер таким образом, что, в дополнении к всегда генерировать правильный вывод предоставлена доступа к неповрежденному кодовому слову, для каждого и на запрос , чтобы восстановить бит равномерно по . ^[5] (Обозначением обозначено множество ). Неформально это означает, что набор запросов, необходимых для декодирования любого заданного бита, равномерно распределяется по кодовому слову.${\ displaystyle j \ in [q]}$${\ Displaystyle я \ в [п]}$${\ displaystyle j ^ {th}}$${\ displaystyle i ^ {th}}$${\ displaystyle [N]}$${\ displaystyle [y]}$${\ displaystyle \ {1, \ ldots, y \}}$

Декодеры локального списка - еще одно интересное подмножество локальных декодеров. Списочное декодирование полезно, когда кодовое слово повреждено более чем в разных местах, где - минимальное расстояние Хэмминга между двумя кодовыми словами. В этом случае больше невозможно точно идентифицировать, какое исходное сообщение было закодировано, поскольку на расстоянии от поврежденного кодового слова могло быть несколько кодовых слов. Однако, учитывая радиус , можно идентифицировать набор сообщений, которые кодируются в кодовые слова, которые находятся в пределах поврежденного кодового слова. Верхнюю границу размера набора сообщений можно определить с помощью и . ^[6]${\ displaystyle \ delta / 2}$${\ displaystyle \ delta}$${\ displaystyle \ delta}$${\ displaystyle \ epsilon}$${\ displaystyle \ epsilon}$${\ displaystyle \ delta}$${\ displaystyle \ epsilon}$

Локально декодируемые коды также могут быть объединены, когда сообщение сначала кодируется с использованием одной схемы, а результирующее кодовое слово снова кодируется с использованием другой схемы. (Обратите внимание, что в этом контексте конкатенация - это термин, используемый учеными для обозначения того, что обычно называется композицией ; см. ^[5] ). Это может быть полезно, если, например, первый код имеет некоторые желательные свойства в отношении скорости, но у него есть некоторые нежелательные свойства, такие как создание кодового слова на основе недвоичного алфавита. Затем второй код может преобразовать результат первого кодирования по недвоичному алфавиту в двоичный алфавит. Окончательное кодирование по-прежнему может декодироваться локально и требует дополнительных шагов для декодирования обоих уровней кодирования. ^[7]

Длина кодового слова и сложность запроса [ править ]

Скорость кода относится к соотношению между длиной его сообщения и длиной кодового слова:, а количество запросов, необходимых для восстановления 1 бита сообщения, называется сложностью запроса кода.${\ displaystyle {\ frac {| x |} {| C (x) |}}}$

Скорость кода обратно пропорциональна сложности запроса, но точная форма этого компромисса является серьезной открытой проблемой. ^{[8] [9]} Известно, что нет LDC, которые запрашивают кодовое слово только в одной позиции, и что оптимальный размер кодового слова для сложности запроса 2 экспоненциально зависит от размера исходного сообщения. ^[8] Однако не существует известных точных нижних границ для кодов со сложностью запроса больше 2. Подходя к компромиссу со стороны длины кодового слова, единственные известные коды с длиной кодового слова, пропорциональной длине сообщения, имеют сложность запроса для ^{[8] [ нуждается в обновлении ]}${\ displaystyle k ^ {\ epsilon}}$${\ displaystyle \ epsilon> 0}$ Есть также промежуточные коды, которые имеют полиномиальные кодовые слова по размеру исходного сообщения и полилогарифмической сложности запроса. ^[8]

Приложения [ править ]

Локально декодируемые коды имеют приложения к передаче и хранению данных, теории сложности, структурам данных, дерандомизации, теории отказоустойчивых вычислений и схемам поиска частной информации. ^[9]

Передача и хранение данных [ править ]

Локально декодируемые коды особенно полезны для передачи данных по каналам с шумом. Код Адамара (частный случай кодов Рида-Мюллера) был использован в 1971 году Mariner 9 для передачи изображений Марса обратно на Землю. Он был выбран вместо кода с 5 повторениями (где каждый бит повторяется 5 раз), потому что для примерно того же количества бит, передаваемых на пиксель, он имел более высокую способность исправлять ошибки. (Код Адамара подпадает под общую схему прямого исправления ошибок , и, как оказалось, его можно декодировать локально; фактический алгоритм, используемый для декодирования передачи с Марса, был общей схемой исправления ошибок.) ^[10]

НРС также полезны для хранения данных, когда носитель со временем может быть частично поврежден или считывающее устройство подвержено ошибкам. В обоих случаях НРС позволит восстановить информацию, несмотря на ошибки, при условии, что их относительно мало. Кроме того, LDC не требуют декодирования всего исходного сообщения; пользователь может декодировать определенную часть исходного сообщения без необходимости декодировать все. ^[11]

Теория сложности [ править ]

Одним из приложений локально декодируемых кодов в теории сложности является усиление жесткости. Используя LDC с полиномиальной длиной кодового слова и полилогарифмической сложностью запроса, можно взять функцию, которую трудно решить для входных данных наихудшего случая, и спроектировать функцию, которую трудно вычислить для входных данных среднего случая.${\displaystyle L:\{0,1\}^{n}\rightarrow \{0,1\}}$${\displaystyle L':\{0,1\}^{N}\rightarrow \{0,1\}}$

Считайте ограничение только вводом длины . Тогда мы можем увидеть двоичную строку длины , где каждый бит соответствует каждому . Мы можем использовать локально декодируемый код полиномиальной длины с полилогарифмической сложностью запроса, допускающей некоторую постоянную долю ошибок для кодирования строки, которая представляет собой создание новой строки длины . Мы думаем об этой новой строке как об определении новой проблемы с вводом длины . Если в среднем легко решить, то есть мы можем правильно решить для большой части входных данных, то по свойствам LDC, используемого для его кодирования, мы можем использовать для вероятностных вычислений для всех входных данных. Таким образом, решение${\displaystyle L}$${\displaystyle t}$${\displaystyle L}$${\displaystyle 2^{t}}$${\displaystyle L(x)}$${\displaystyle x\in \{0,1\}^{t}}$${\displaystyle C}$${\displaystyle L}$${\displaystyle 2^{O(t)}=2^{t'}}$${\displaystyle L'}$${\displaystyle t'}$${\displaystyle L'}$${\displaystyle L'}$${\displaystyle 1-\epsilon }$${\displaystyle L'}$${\displaystyle L}$${\displaystyle L'}$для большинства входных данных позволил бы нам решить для всех входных данных, что противоречит нашему предположению, которое сложно для входных данных наихудшего случая. ^{[5] [8] [12]}${\displaystyle L}$${\displaystyle L}$

Схемы получения частной информации [ править ]

Частная информационно - поисковая система позволяет пользователю получить элемент с сервера в распоряжении базы данных , не раскрывая , какой элемент извлекается. Один из распространенных способов обеспечения конфиденциальности - наличие отдельных серверов без связи, каждый из которых имеет копию базы данных. При наличии соответствующей схемы пользователь может делать запросы к каждому серверу, которые по отдельности не раскрывают, какой бит ищет пользователь, но вместе предоставляют достаточно информации, чтобы пользователь мог определить конкретный интересующий бит в базе данных. ^{[3] [11]}${\displaystyle k}$

Легко видеть, что локально декодируемые коды имеют применение в этой настройке. Общая процедура создания схемы частной информации -сервер из идеально гладкого локально декодируемого кода-запроса выглядит следующим образом:${\displaystyle k}$${\displaystyle k}$

Позвольте быть идеально гладкой LDC, которая кодирует -битовые сообщения в -битовые кодовые слова. На этапе предварительной обработки каждый из серверов кодирует -битовую базу данных с помощью кода , поэтому теперь каждый сервер хранит -битовое кодовое слово . Пользователь, заинтересованный в получении бита, случайным образом генерирует набор запросов , которые могут быть вычислены с использованием алгоритма локального декодирования для . Пользователь отправляет каждый запрос на другой сервер, и каждый сервер отвечает запрошенным битом. Затем пользователь использует для вычисления ответов. ^{[8] [11]}${\displaystyle C}$${\displaystyle n}$${\displaystyle N}$${\displaystyle k}$${\displaystyle S_{1},\ldots ,S_{k}}$${\displaystyle n}$${\displaystyle x}$${\displaystyle C}$${\displaystyle N}$${\displaystyle C(x)}$${\displaystyle i^{th}}$${\displaystyle x}$${\displaystyle k}$${\displaystyle q_{1},\ldots q_{k}}$${\displaystyle x_{i}}$${\displaystyle C(x)_{q_{1}},\ldots C(x)_{q_{k}}}$${\displaystyle A}$${\displaystyle C}$${\displaystyle A}$${\displaystyle x_{i}}$Поскольку алгоритм декодирования идеально гладкий, каждый запрос равномерно распределяется по кодовому слову ; таким образом, ни один отдельный сервер не может получить какую-либо информацию о намерениях пользователя, поэтому протокол является частным, пока серверы не обмениваются данными. ^[11]${\displaystyle q_{j}}$

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

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

Код Адамара (или Уолша-Адамара) является примером простого локально декодируемого кода, который отображает строку длины в кодовое слово длины . Кодовое слово для строки строятся следующим образом : для каждого , то бит кодового слова равно , где (2) мод. Легко видеть , что каждое кодовое слово имеет расстояние Хэмминга от от любого другого кодового слова.${\displaystyle k}$${\displaystyle 2^{k}}$${\displaystyle x\in \{0,1\}^{k}}$${\displaystyle a_{j}\in \{0,1\}^{k}}$${\displaystyle j^{th}}$${\displaystyle x\odot a_{j}}$${\displaystyle x\odot y=\sum \limits _{i=1}^{k}x_{i}y_{i}}$${\displaystyle {\frac {n}{2}}}$

Алгоритм локального декодирования имеет сложность запроса 2, и все исходное сообщение может быть декодировано с хорошей вероятностью, если кодовое слово повреждено менее чем в его битах. Ведь , если кодовое слово повреждено в некоторой части мест, алгоритм локального декодирования может с вероятностью восстановить бит исходного сообщения .${\displaystyle {\frac {1}{4}}}$${\displaystyle \rho <{\frac {1}{4}}}$${\displaystyle \rho }$${\displaystyle i^{th}}$${\displaystyle 1-2\rho }$

Доказательство: с учетом кодового слова и индекса алгоритм восстановления бита исходного сообщения работает следующим образом:${\displaystyle H}$${\displaystyle i}$${\displaystyle i^{th}}$${\displaystyle x}$

Позвольте ссылаться на вектор в, который имеет 1 в позиции и 0 в другом месте. Для получения , обозначает один бит в , что соответствует . Алгоритм выбирает случайный вектор и вектор (где означает побитовое исключающее ИЛИ ). Выходные данные алгоритма (mod 2).${\displaystyle e^{j}}$${\displaystyle \{0,1\}^{k}}$${\displaystyle j^{th}}$${\displaystyle y\in \{0,1\}^{k}}$${\displaystyle f(y)}$${\displaystyle H}$${\displaystyle x\odot y}$${\displaystyle y\in \{0,1\}^{k}}$${\displaystyle y'=y\oplus e^{i}}$${\displaystyle \oplus }$${\displaystyle f(y)\oplus f(y')}$

Правильность: по линейности,

${\displaystyle (x\odot y)\oplus (x\odot y')=(x\odot y)\oplus (x\odot (y\oplus e^{i}))=(x\odot y)\oplus (x\odot y)\oplus (x\odot e^{i})=x\odot e^{i}}$

Но нам просто нужно это показать, и с хорошей вероятностью.${\displaystyle (x\odot e^{i})=x_{i}}$${\displaystyle f(y)=x\odot y}$${\displaystyle f(y')=x\odot y'}$

Так как и равномерно распределены (даже если они зависимы), граница объединения подразумевает это и, по крайней мере, с вероятностью . Примечание: чтобы увеличить вероятность успеха, можно повторить процедуру с разными случайными векторами и взять ответ большинства.^[13]${\displaystyle y}$${\displaystyle y'}$${\displaystyle f(y)=x\odot y}$${\displaystyle f(y')=x\odot y'}$${\displaystyle 1-2\rho }$

Код Рида – Мюллера [ править ]

Основная идея локального декодирования кодов Рида-Маллера - полиномиальная интерполяция . Ключевой концепцией кода Рида-Маллера является многомерный полином степени от переменных. Сообщение рассматривается как оценка многочлена в наборе заранее определенных точек. Для кодирования этих значений из них экстраполируется полином, а кодовое слово - это оценка этого полинома по всем возможным точкам. На высоком уровне, чтобы декодировать точку этого многочлена, алгоритм декодирования выбирает набор точек на линии, которая проходит через интересующую точку . Затем он запрашивает кодовое слово для оценки полинома в точках в${\displaystyle d}$${\displaystyle l}$${\displaystyle S}$${\displaystyle x}$${\displaystyle S}$и интерполирует этот многочлен. Тогда просто вычислить многочлен в точке, которая даст результат . Этот обходной способ оценки полезен, потому что (а) алгоритм может повторяться с использованием разных строк через одну и ту же точку для повышения вероятности правильности, и (б) запросы равномерно распределяются по кодовому слову.${\displaystyle x}$${\displaystyle x}$

Более формально, пусть будет конечным полем, и пусть будут числами с . Код Рида-Мюллера с параметрами является функцией RM: что отображает каждый -переменную многочлен за кадром в полной степени к значениям на всех входах в . То есть входные данные представляют собой полином формы, заданной интерполяцией значений предопределенных точек, а выходными данными является последовательность для каждого . ^[14]${\displaystyle \mathbb {F} }$${\displaystyle l,d}$${\displaystyle d<|\mathbb {F} |}$${\displaystyle \mathbb {F} ,l,d}$${\displaystyle \mathbb {F} ^{\binom {l+d}{d}}\rightarrow \mathbb {F} ^{|\mathbb {F} |^{l}}}$${\displaystyle l}$${\displaystyle P}$${\displaystyle \mathbb {F} }$${\displaystyle d}$${\displaystyle P}$${\displaystyle \mathbb {F} ^{l}}$${\displaystyle P(x_{1},\ldots ,x_{l})=\sum \limits _{i_{1}+\ldots +i_{l}\leq d}c_{i_{1},\ldots ,i_{l}}x_{1}^{i_{1}}x_{2}^{i_{2}}\cdots x_{l}^{i_{l}}}$${\displaystyle {\binom {l+d}{d}}}$${\displaystyle \{P(x_{1},\ldots ,x_{l})\}}$${\displaystyle x_{1},\ldots ,x_{l}\in \mathbb {F} }$

Чтобы восстановить значение полинома степени в точке , локальный декодер пропускает случайную аффинную строку . Затем он выбирает точки на этой линии, которые он использует для интерполяции полинома, а затем оценивает его в точке, где находится результат . Для этого алгоритм выбирает вектор равномерно наугад и учитывает сквозную линию . Алгоритм выбирает произвольное подмножество из , где , и запрашивает координаты кодового слова , которые соответствуют точкам для всех и получают значения . Затем он использует полиномиальную интерполяцию для восстановления уникального одномерного полинома со степенью меньше или равной${\displaystyle d}$${\displaystyle w\in \mathbb {F} ^{n}}$${\displaystyle w}$${\displaystyle d+1}$${\displaystyle w}$${\displaystyle v\in \mathbb {F} ^{n}}$${\displaystyle L=\{w+\lambda v\mid \lambda \in \mathbb {F} \}}$${\displaystyle w}$${\displaystyle S}$${\displaystyle \mathbb {F} }$${\displaystyle |S|=d+1}$${\displaystyle w+\lambda v}$${\displaystyle \lambda \in S}$${\displaystyle \{e_{\lambda }\}}$${\displaystyle h}$${\displaystyle d}$такое что для всех . Затем, чтобы получить значение , он просто оценивает . Чтобы восстановить одно значение исходного сообщения, выбирается одна из точек, определяющих полином. ^{[8] [14]}${\displaystyle h(\lambda )=e_{\lambda }}$${\displaystyle \lambda \in S}$${\displaystyle w}$${\displaystyle h(0)}$${\displaystyle w}$

Каждый индивидуальный запрос равномерно распределен случайным образом по кодовому слову. Таким образом, если кодовое слово повреждено не более чем в части местоположений из-за границы объединения, вероятность того, что алгоритм выбирает только неповрежденные координаты (и, таким образом, правильно восстанавливает бит), составляет не менее . ^[8] О других алгоритмах декодирования см. ^[8]${\displaystyle \delta }$${\displaystyle 1-(d+1)\delta }$

См. Также [ править ]

• Получение частной информации
• Линейный криптоанализ

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