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

Locally decodable code

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

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

Обзор

Более формально -локально декодируемый код кодирует -битовое сообщение для -битовое кодовое слово такой, что любой бит сообщения можно восстановить с вероятностью с помощью алгоритма рандомизированного декодирования, который запрашивает только биты кодового слова , даже если до места кодового слова были повреждены.

Более того, идеально гладкий локальный декодер - это такой декодер, который, помимо того, что всегда генерирует правильный вывод при доступе к неповрежденному кодовому слову, для каждого и то запрос на восстановление бит однороден по .[5](Обозначение обозначает множество ). Неформально это означает, что набор запросов, необходимых для декодирования любого заданного бита, равномерно распределяется по кодовому слову.

Декодеры локального списка - еще одно интересное подмножество локальных декодеров. Расшифровка списка полезна, когда кодовое слово повреждено более чем на места, где это минимум Расстояние Хэмминга между двумя кодовыми словами. В этом случае больше невозможно точно определить, какое исходное сообщение было закодировано, так как внутри могло быть несколько кодовых слов. расстояние поврежденного кодового слова. Однако, учитывая радиус , можно идентифицировать набор сообщений, которые кодируются в кодовые слова, которые находятся в пределах поврежденного кодового слова. Верхний предел размера набора сообщений может быть определен и .[6]

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

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

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

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

Приложения

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

Передача и хранение данных

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

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

Теория сложности

Одно из приложений локально декодируемых кодов в теория сложности усиление твердости. Используя LDC с полиномиальной длиной кодового слова и полилогарифмической сложностью запроса, можно взять функцию это трудно решить для входных данных наихудшего случая и разработать функцию это трудно вычислить для входных данных среднего случая.

Учитывать ограничено только длиной входы. Тогда мы можем увидеть как двоичная строка длины , где каждый бит для каждого . Мы можем использовать локально декодируемый код полиномиальной длины с полилогарифмической сложностью запроса, допускающей некоторую постоянную долю ошибок для кодирования строки, представляющей создать новую строку длины . Мы думаем об этой новой строке как об определении новой проблемы по длине входы. Если в среднем легко решить, то есть мы можем решить правильно на большой дроби входных данных, то по свойствам LDC, используемого для его кодирования, мы можем использовать вероятностно вычислить на всех входах. Таким образом, решение для большинства входов позволит нам решить на всех входах, что противоречит нашему предположению, что сложно на входах в худшем случае.[5][8][12]

Схемы поиска частной информации

А поиск частной информации Схема позволяет пользователю получить элемент с сервера, владеющего базой данных, не раскрывая, какой элемент извлекается. Один из распространенных способов обеспечения конфиденциальности - наличие отдельные, не взаимодействующие серверы, каждый с копией базы данных. При наличии соответствующей схемы пользователь может делать запросы к каждому серверу, которые по отдельности не раскрывают, какой бит ищет пользователь, но вместе предоставляют достаточно информации, чтобы пользователь мог определить конкретный интересующий бит в базе данных.[3][11]

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

Позволять быть идеально гладким LDC, который кодирует -битовые сообщения для -битовые кодовые слова. На этапе предварительной обработки каждый из серверы кодирует -битовая база данных с кодом , поэтому теперь каждый сервер хранит -битовое кодовое слово . Пользователь, заинтересованный в получении немного случайным образом генерирует набор запросы такой, что можно вычислить из с использованием алгоритма локального декодирования за . Пользователь отправляет каждый запрос на другой сервер, и каждый сервер отвечает запрошенным битом. Затем пользователь использует вычислить из ответов.[8][11]Поскольку алгоритм декодирования идеально гладкий, каждый запрос равномерно распределяется по кодовому слову; таким образом, ни один отдельный сервер не может получить информацию о намерениях пользователя, поэтому протокол является частным, пока серверы не обмениваются данными.[11]

Примеры

Код Адамара

В Адамар (или код Уолша-Адамара) является примером простого локально декодируемого кода, который отображает строку длины к кодовому слову длины . Кодовое слово для строки строится следующим образом: для каждого , то бит кодового слова равен , куда (мод 2). Легко видеть, что каждое кодовое слово имеет Расстояние Хэмминга из из любого другого кодового слова.

Алгоритм локального декодирования имеет сложность запроса 2, и все исходное сообщение может быть декодировано с хорошей вероятностью, если кодовое слово повреждено менее чем на его бит. За , если кодовое слово повреждено в доли мест, алгоритм локального декодирования может восстановить бит исходного сообщения с вероятностью .

Доказательство: задано кодовое слово. и индекс , алгоритм восстановления часть исходного сообщения работает следующим образом:

Позволять относятся к вектору в который имеет 1 в позиция и нули в другом месте. За , обозначает единственный бит в что соответствует . Алгоритм выбирает случайный вектор и вектор (куда обозначает побитовое XOR). Выходные данные алгоритма (мод 2).

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

Но , поэтому нам просто нужно показать, что и с хорошей вероятностью.

С и равномерно распределены (хотя и зависимы), связанный союз подразумевает, что и с вероятностью не менее . Примечание: чтобы увеличить вероятность успеха, можно повторить процедуру с разными случайными векторами и взять ответ большинства.[13]

Код Рида-Мюллера

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

Более формально, пусть - конечное поле, и пусть быть числами с . Код Рида-Мюллера с параметрами - функция RM: что отображает каждый -переменный многочлен над общей степени к значениям на всех входах в . То есть вход представляет собой многочлен видазадается интерполяцией значения предопределенных точек, а на выходе - последовательность для каждого .[14]

Чтобы восстановить значение степени полином в точке , локальный декодер выдает случайный аффинный Линия, проходящая через . Затем он выбирает точки на этой строке, которые он использует для интерполяции многочлена, а затем оценивает его в точке, где результат . Для этого алгоритм выбирает вектор равномерно наугад и считает строку через . Алгоритм выбирает произвольное подмножество из , куда , и запрашивает координаты кодового слова, соответствующего точкам для всех и получает значения . Затем он использует полиномиальную интерполяцию для восстановления уникального одномерного полинома со степенью меньше или равной такой, что для всех . Затем, чтобы получить значение , он просто оценивает . Чтобы восстановить одно значение исходного сообщения, выбирают быть одной из точек, определяющих полином.[8][14]

Каждый индивидуальный запрос равномерно распределен случайным образом по кодовому слову. Таким образом, если кодовое слово повреждено не более чем в доля местоположений, по границе объединения, вероятность того, что алгоритм выбирает только неповрежденные координаты (и, таким образом, правильно восстанавливает бит), не менее .[8]О других алгоритмах декодирования см.[8]

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

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

  1. ^ Сергей Еханин. «Локально декодируемые коды: краткий обзор» (PDF).
  2. ^ Рафаил Островский; Омкант Пандей; Амит Сахаи. «Частные локально декодируемые коды» (PDF).
  3. ^ а б Сергей Еханин. Новые локально декодируемые коды и схемы поиска частной информации, Технический отчет ECCC TR06-127, 2006.
  4. ^ Тали Кауфман; Майкл Видерман. «Локально тестируемые и локально декодируемые коды».
  5. ^ а б c Лука Тревизан. "Некоторые приложения теории кодирования в вычислительной сложности" (PDF).
  6. ^ Арора, Санджив; Варак, Вооз (2009). «Раздел 19.5». Вычислительная сложность: современный подход. Кембридж. ISBN 978-0-521-42426-4.CS1 maint: ref = harv (связь)
  7. ^ Арора и Барак 2009, Раздел 19.4.3
  8. ^ а б c d е ж грамм час я Сергей Еханин. "Локально декодируемые коды" (PDF).
  9. ^ а б Сергей Еханин. "Локально декодируемые коды" (PDF).
  10. ^ «Комбинаторика в космосе. Телеметрическая система Mariner 9» (PDF).
  11. ^ а б c d Сергей Еханин. «Поиск частной информации» (PDF).
  12. ^ Арора и Барак 2009, Раздел 19.4
  13. ^ Арора и Барак 2009, Раздел 11.5.2
  14. ^ а б Арора и Барак 2009, Раздел 19.4.2