Декодирование списка

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

Уникальная модель декодирования в теории кодирования , которая ограничена выводом единственного допустимого кодового слова из полученного слова, не допускает большей доли ошибок. Это привело к разрыву между эффективностью исправления ошибок для моделей стохастического шума (предложенных Шенноном ) и модели состязательного шума (рассмотренной Ричардом Хэммингом ). С середины 90-х годов значительный прогресс в области алгоритмов, достигнутый сообществом теоретиков кодирования, восполнил этот пробел. Большая часть этого прогресса основана на смягченной модели исправления ошибок, называемой декодированием списка, в которой декодер выводит список кодовых слов для шаблонов патологических ошибок наихудшего случая, где фактическое переданное кодовое слово включается в выходной список. Однако в случае типичных шаблонов ошибок декодер выводит уникальное одно кодовое слово для данного полученного слова, что почти всегда так (однако известно, что это верно не для всех кодов). Улучшение здесь существенно, поскольку эффективность исправления ошибок удваивается. Это связано с тем, что теперь декодер не ограничен барьером половины минимального расстояния. Эта модель очень привлекательна, поскольку иметь список кодовых слов, безусловно, лучше, чем просто сдаваться. Понятие декодирования списков имеет множество интересных приложений в теория сложности .

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

• Вероятностная модель шума, изученная Шенноном, в которой шум канала моделируется именно в том смысле, что вероятностное поведение канала хорошо известно, а вероятность появления слишком большого или слишком малого количества ошибок мала.
• Модель наихудшего случая или состязательного шума, рассмотренная Хэммингом, в которой канал действует как противник, который произвольно искажает кодовое слово с учетом ограничения на общее количество ошибок.

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

Математическая формулировка

Позволять ${\mathcal {C}}$ быть $(n,k,d)_{q}$ код, исправляющий ошибки; другими словами, ${\mathcal {C}}$ это код длины $n$, измерение $k$ и минимальное расстояние $d$ над алфавитом $\Sigma$ размера $q$. Теперь задачу декодирования списка можно сформулировать следующим образом:

Ввод: полученное слово. $x\in \Sigma ^{n}$, ошибка связана $e$

Вывод: список всех кодовых слов. $x_{1},x_{2},\ldots ,x_{m}\in {\mathcal {C}}$ чье расстояние Хэмминга от $x$ самое большее $e$.

Мотивация расшифровки списка

Учитывая полученное слово $y$, который представляет собой зашумленную версию некоторого переданного кодового слова $c$декодер пытается вывести переданное кодовое слово, делая ставку на кодовое слово, которое является «ближайшим» к полученному слову. Расстояние Хэмминга между двумя кодовыми словами используется в качестве метрики при поиске ближайшего кодового слова, учитывая слово, полученное декодером. Если $d$ - минимальное расстояние Хэмминга кода ${\mathcal {C}}$, то существует два кодовых слова $c_{1}$ и $c_{2}$ которые отличаются именно $d$ позиции. Теперь в случае, когда полученное слово $y$ равноудален от кодовых слов $c_{1}$ и $c_{2}$однозначное декодирование становится невозможным, поскольку декодер не может решить, какой из $c_{1}$ и $c_{2}$ для вывода как исходное переданное кодовое слово. В результате половина минимального расстояния действует как комбинаторный барьер, за которым невозможно однозначное исправление ошибок, если мы будем настаивать только на однозначном декодировании. Однако полученные слова, такие как $y$ рассмотренные выше, происходят только в худшем случае, и если посмотреть на то, как шары Хэмминга упакованы в многомерном пространстве, даже для шаблонов ошибок $e$ за половиной минимального расстояния существует только одно кодовое слово $c$ на расстоянии Хэмминга $e$ из полученного слова. Было показано, что это утверждение с высокой вероятностью справедливо для случайного кода, выбранного из естественного ансамбля, и, тем более, для случая кодов Рида – Соломона , который хорошо изучен и широко распространен в реальных приложениях. Фактически, доказательство Шеннона теоремы о пропускной способности для q -арных симметричных каналов можно рассматривать в свете приведенного выше утверждения для случайных кодов.

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

Потенциал декодирования списков

Для существования алгоритма декодирования списка за полиномиальное время нам нужна комбинаторная гарантия того, что любой шар Хэмминга радиуса $pn$ вокруг полученного слова $r$ (где $p$ — доля ошибок, выраженная в длине блока $n$) имеет небольшое количество кодовых слов. Это связано с тем, что размер списка сам по себе явно является нижней границей времени работы алгоритма. Следовательно, мы требуем, чтобы размер списка был полиномом от длины блока. $n$ кода. Комбинаторным следствием этого требования является то, что оно накладывает верхнюю границу на скорость кода. Декодирование списков обещает достичь этой верхней границы. Неконструктивно было показано, что коды скорости $R$ существуют, которые можно декодировать списком с точностью до доли ошибок, приближающейся к $1-R$. Количество $1-R$ в литературе называется способностью декодирования списка. Это существенный выигрыш по сравнению с уникальной моделью декодирования, поскольку теперь у нас есть возможность исправлять вдвое больше ошибок. Естественно, нам нужно иметь хотя бы дробь $R$ передаваемых символов, чтобы они были правильными, чтобы восстановить сообщение. Это теоретико-информационная нижняя граница количества правильных символов, необходимых для выполнения декодирования, и с помощью декодирования списка мы потенциально можем достичь этого теоретико-информационного предела. Однако для реализации этого потенциала нам нужны явные коды (коды, которые можно построить за полиномиальное время) и эффективные алгоритмы для кодирования и декодирования.

( p , L )-список-декодируемость

Для любой доли ошибки $0\leqslant p\leqslant 1$ и целое число $L\geqslant 1$, код ${\mathcal {C}}\subseteq \Sigma ^{n}$ называется списком, декодируемым с точностью до дроби $p$ ошибок с размером списка не более $L$ или $(p,L)$-list-декодируемый, если для каждого $y\in \Sigma ^{n}$, количество кодовых слов $c\in C$ на расстоянии Хэмминга $pn$ от $y$ самое большее $L.$

Комбинаторика декодирования списков

Связь между списочной декодируемостью кода и другими фундаментальными параметрами, такими как минимальное расстояние и скорость, достаточно хорошо изучена. Было показано, что каждый код может быть декодирован в виде списка с использованием небольших списков за пределами половины минимального расстояния до границы, называемой радиусом Джонсона. Это весьма важно, поскольку доказывает существование $(p,L)$-коды, декодируемые списком, с хорошей скоростью и радиусом декодирования списка, намного большим, чем ${\tfrac {d}{2}}.$ Другими словами, граница Джонсона исключает возможность наличия большого числа кодовых слов в шаре Хэмминга радиуса немного большего, чем ${\tfrac {d}{2}}$ а это означает, что с помощью декодирования списка можно исправить гораздо больше ошибок.

Возможность декодирования списка

Теорема (возможность декодирования списка). Позволять $q\geqslant 2,0\leqslant p\leqslant 1-{\tfrac {1}{q}}$ и $\epsilon \geqslant 0.$ Следующие два утверждения справедливы для достаточно большой длины блока. $n$.

и) Если $R\leqslant 1-H_{q}(p)-\epsilon$, то существует $(p,O(1/\epsilon ))$-список декодируемого кода.

2) Если $R\geqslant 1-H_{q}(p)+\epsilon$, то каждый $(p,L)$-list-декодируемый код имеет $L=q^{\Omega (n)}$.

Где

$H_{q}(p)=p\log _{q}(q-1)-p\log _{q}p-(1-p)\log _{q}(1-p)$

это $q$-арная функция энтропии, определенная для $p\in (0,1)$ и расширен за счет непрерывности до $[0,1].$

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

Доказательство возможности декодирования списков является важным, поскольку оно точно соответствует мощности $q$-арный симметричный канал $qSC_{p}$. Фактически, термин «пропускная способность декодирования по списку» следует понимать как пропускную способность состязательного канала при декодировании по списку. Кроме того, доказательство возможности декодирования списками является важным результатом, который указывает на оптимальный компромисс между скоростью кода и долей ошибок, которые можно исправить при декодировании списками.

Эскиз доказательства

Идея доказательства аналогична идее доказательства Шеннона пропускной способности двоичного симметричного канала. $BSC_{p}$ где выбирается случайный код и показывается, что это $(p,L)$-список-декодируемый с высокой вероятностью, пока скорость $R\leqslant 1-H_{q}(p)-{\tfrac {1}{L}}.$ Для ставок, превышающих указанное выше количество, можно показать, что размер списка $L$ становится суперполиномиально большим.

«Плохое» событие определяется как событие, в котором по полученному слову $y\in [q]^{n}$ и $L+1$ сообщения $m_{0},\ldots ,m_{L}\in [q]^{k},$ так случилось, что ${\mathcal {C}}(m_{i})\in B(y,pn)$, для каждого $0\leqslant i\leqslant L$ где $p$ — это доля ошибок, которую мы хотим исправить и $B(y,pn)$ это шар Хэмминга радиуса $pn$ с полученным словом $y$ как центр.

Теперь вероятность того, что кодовое слово ${\mathcal {C}}(m_{i})$ связанный с фиксированным сообщением $m_{i}\in [q]^{k}$ лежит в шаре Хэмминга $B(y,pn)$ дается

$\Pr \left[C(m_{i})\in B(y,pn)\right]={\frac {\mathrm {Vol} _{q}(y,pn)}{q^{n}}}\leqslant q^{-n(1-H_{q}(p))},$

где количество $Vol_{q}(y,pn)$ - объем шара Хэмминга радиуса $pn$ с полученным словом $y$ как центр. Неравенство в приведенном выше соотношении следует из верхней оценки объема шара Хэмминга. Количество $q^{H_{q}(p)}$ дает очень хорошую оценку объема шара Хэмминга радиуса $p$ сосредоточено на любом слове в $[q]^{n}.$ Другими словами, объем шара Хэмминга инвариантен при переносе. Чтобы продолжить набросок доказательства, мы вызовем объединение, связанное с теорией вероятностей, которое говорит нам, что вероятность плохого события, происходящего для данного $(y,m_{0},\dots ,m_{L})$ ограничена сверху величиной $q^{-n(L+1)(1-H_{q}(p))}$.

Учитывая вышесказанное, можно показать, что вероятность возникновения «любого» плохого события меньше, чем $1$. Чтобы это показать, мы прорабатываем все возможные полученные слова. $y\in [q]^{n}$ и все возможные подмножества $L$ сообщения в $[q]^{k}.$

Теперь обратившись к доказательству части (ii), нам нужно показать, что вокруг каждой точки существует суперполиномиальное количество кодовых слов. $y\in [q]^{n}$ когда скорость превышает возможности декодирования списка. Нам нужно это показать $|{\mathcal {C}}\cap B(y,pn)|$ является суперполиномиально большим, если скорость $R\geqslant 1-H_{q}(p)+\epsilon$. Исправить кодовое слово $c\in {\mathcal {C}}$. Теперь для каждого $y\in [q]^{n}$ выбрано случайно, у нас есть

$\Pr[c\in B(y,pn)]=\Pr[y\in B(c,pn)]$

поскольку шары Хэмминга трансляционно-инвариантны. Из определения объема шара Хэмминга и того факта, что $y$ выбирается равномерно случайным образом из $[q]^{n}$ у нас также есть

$\Pr[c\in B(y,pn)]=\Pr[y\in B(c,pn)]={\frac {\mathrm {Vol} (y,pn)}{q^{n}}}\geqslant q^{-n(1-H_{q}(p))-o(n)}$

Давайте теперь определим индикаторную переменную $X_{c}$ такой, что

$X_{c}={\begin{cases}1&c\in B(y,pn)\\0&{\text{otherwise}}\end{cases}}$

Взяв математическое ожидание объема шара Хэмминга, имеем

${\begin{aligned}E[|B(y,pn)|]&=\sum _{c\in {\mathcal {C}}}E[X_{c}]\\[4pt]&=\sum _{c\in {\mathcal {C}}}\Pr[X_{c}=1]\\[4pt]&\geqslant \sum q^{-n(1-H_{q}(p)+o(n))}\\[4pt]&=\sum q^{n(R-1+H_{q}(p)+o(1))}\\[4pt]&\geqslant q^{\Omega (n)}\end{aligned}}$

Таким образом, вероятностным методом мы показали, что если скорость превышает возможности декодирования списка, то размер списка становится суперполиномиально большим. На этом схема доказательства возможности декодирования списка завершена.

Список декодируемых кодов Рида-Соломона

В 2023 году, основываясь на трех плодотворных работах, Теоретики кодирования показали, что с высокой вероятностью коды Рида-Соломона, определенные по случайным точкам оценки, декодируются по спискам до уровня возможности декодирования списка по алфавитам линейного размера.

Алгоритмы декодирования списков

В период с 1995 по 2007 год сообщество теоретиков кодирования разработало все более эффективные алгоритмы декодирования списков. Алгоритмы кодов Рида – Соломона , которые могут декодировать до радиуса Джонсона, который $1-{\sqrt {1-\delta }}$ существовать там, где $\delta$ — нормализованное расстояние или относительное расстояние. Однако для кодов Рида-Соломона $\delta =1-R$ что означает дробь $1-{\sqrt {R}}$ ошибок можно исправить. Некоторые из наиболее известных алгоритмов декодирования списков следующие:

• Судан '95 - Первый известный нетривиальный алгоритм декодирования списка для кодов Рида – Соломона, который достиг эффективного декодирования списка до $1-{\sqrt {2R}}$ ошибки, разработанные Мадху Суданом .
• Гурусвами-Судан '98 - Улучшение описанного выше алгоритма для спискового декодирования кодов Рида-Соломона до $1-{\sqrt {R}}$ ошибки Мадху Судана и его тогдашнего докторанта Венкатесана Гурусвами .
• Парвареш-Варди '05. В своей революционной статье Фарзад Парвареш и Александр Варди представили коды, которые можно расшифровать в виде списка за пределами $1-{\sqrt {R}}$ радиус для низких ставок $R$. Их коды являются вариантами кодов Рида-Соломона, которые получаются путем вычисления $m\geqslant 1$ коррелированные полиномы вместо просто $1$ как и в случае обычных кодов Рида-Соломона.
• совершили еще один прорыв, Гурусвами–Рудра '06 - Венкатесан Гурусвами и Атри Рудра предоставив явные коды, которые обеспечивают способность декодирования списка, то есть их можно декодировать списком до радиуса. $1-R-\epsilon$ для любого $\epsilon >0$. Другими словами, это коррекция ошибок с оптимальной избыточностью. Это ответило на вопрос, который был открыт около 50 лет. Эта работа была включена в раздел «Основные исследования» журнала Communications of ACM (который «посвящен наиболее важным результатам исследований, опубликованных в области компьютерных наук за последние годы») и была упомянута в статье под названием «Coding and Computing Joint Forces». в номере журнала Science от 21 сентября 2007 г. Коды, которые им даются, называются свернутыми кодами Рида-Соломона , которые представляют собой не что иное, как простые коды Рида-Соломона, но рассматриваются как код более крупного алфавита за счет тщательного объединения символов кодовых слов.

Из-за их повсеместного распространения и хороших алгебраических свойств алгоритмы спискового декодирования кодов Рида – Соломона были в центре внимания исследователей. Задачу списочного декодирования кодов Рида–Соломона можно сформулировать следующим образом:

Ввод : Для $[n,k+1]_{q}$ Код Рида-Соломона, нам дана пара $(\alpha _{i},y_{i})$ для $1\leq i\leq n$, где $y_{i}$ это $i$бит полученного слова и $\alpha _{i}$'s - различные точки в конечном поле $F_{q}$ и параметр ошибки $e=n-t$.

Вывод : Цель — найти все полиномы. $P(X)\in F_{q}[X]$ степени максимум $k$ какова длина сообщения такая, что $p(\alpha _{i})=y_{i}$ по крайней мере $t$ значения $i$. Здесь мы хотели бы иметь $t$ как можно меньше, чтобы можно было допустить большее количество ошибок.

С учетом приведенной выше формулировки общая структура алгоритмов списочного декодирования кодов Рида-Соломона выглядит следующим образом:

Шаг 1 : (Интерполяция) Найдите ненулевой двумерный полином. $Q(X,Y)$ такой, что $Q(\alpha _{i},y_{i})=0$ для $1\leq i\leq n$.

Шаг 2 : (Нахождение корня/факторизация) Выведите все степени $k$ полиномы $p(X)$ такой, что $Y-p(X)$ является фактором $Q(X,Y)$ то есть $Q(X,p(X))=0$. Для каждого из этих многочленов проверьте, $p(\alpha _{i})=y_{i}$ по крайней мере $t$ значения $i\in [n]$. Если да, включите такой многочлен $p(X)$ в списке вывода.

Учитывая тот факт, что двумерные полиномы можно эффективно факторизовать, приведенный выше алгоритм работает за полиномиальное время.

Приложения в теории сложности и криптографии

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

• Построение жестких предикатов из односторонних перестановок .
• Прогнозирование свидетелей для задач NP-поиска.
• Усиление сложности булевых функций.
• Средняя твердость перманента случайных матриц.
• Экстракторы и генераторы псевдослучайных чисел .
• Эффективное отслеживание предателей.

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

• Опрос по расшифровке списков, проведенный Мадху Суданом
• Заметки из курса, который ведет Мадху Судан
• Заметки из курса Луки Тревизана
• Заметки из курса Венкатесана Гурусвами
• Заметки из курса Атри Рудры
• П. Элиас, «Декодирование списков для каналов с шумом», Технический отчет 335, Исследовательская лаборатория электроники, Массачусетский технологический институт, 1957.
• П. Элиас, «Коды с исправлением ошибок для декодирования списков», IEEE Transactions on Information Theory, vol. 37, стр. 5–12, 1991.
• Дж. М. Возенкрафт, «Декодирование списков», Ежеквартальный отчет о проделанной работе, Исследовательская лаборатория электроники, Массачусетский технологический институт, том. 48, стр. 90–95, 1958.
• Венкатесана Гурусвами Кандидатская диссертация
• Алгоритмические результаты при декодировании списков
• Сложенный код Рида – Соломона