Расшифровка списка - List decoding

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

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

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

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

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

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

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

Вход: Полученное слово ${displaystyle xin Sigma ^{n}}$, граница ошибки ${displaystyle e}$

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

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

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

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

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

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

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

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

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

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

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

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

i) Если ${displaystyle Rleqslant 1-H_{q}(p)-epsilon }$, то существует ${displaystyle (p,O(1/epsilon ))}$-список декодируемых кодов.

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

Где

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

это ${displaystyle q}$-арная функция энтропии, определенная для ${displaystyle pin (0,1)}$ и продлен непрерывностью до ${displaystyle [0,1].}$

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

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

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

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

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

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

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

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

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

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

${displaystyle Pr[cin B(y,pn)]=Pr[yin B(c,pn)]}$

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

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

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

${displaystyle X_{c}={egin{cases}1&cin B(y,pn)�&{ ext{otherwise}}end{cases}}}$

Принимая ожидание объема шара Хэмминга, мы имеем

${displaystyle {egin{aligned}E[|B(y,pn)|]&=sum _{cin {mathcal {C}}}E[X_{c}][4pt]&=sum _{cin {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}}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

внешняя ссылка

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