Расшифровка списка

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

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

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

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

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

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

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

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

Ввод: полученное слово , граница ошибки${\ Displaystyle х \ в \ Sigma ^ {п}}$ ${\ 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}$

( p , L ) -лист-декодируемость [ править ]

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

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

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

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

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

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

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

Где

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

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

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

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

Эскиз доказательства [ править ]

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

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

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

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

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

${\displaystyle \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)}}$

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

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

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

${\displaystyle {\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}}}$

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

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

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

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

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

Ввод : Для кода Рида-Соломона нам дается пара для , где - th бит принятого слова, а 's - отдельные точки в конечном поле и параметр ошибки .${\displaystyle [n,k+1]_{q}}$${\displaystyle (\alpha _{i},y_{i})}$${\displaystyle 1\leq i\leq n}$${\displaystyle y_{i}}$${\displaystyle i}$${\displaystyle \alpha _{i}}$${\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 1\leq i\leq n}$

Шаг 2 : (Поиск корня / факторизация) Выведите все многочлены степени , которые являются множителем ie . Для каждого из этих многочленов проверьте, есть ли по крайней мере для значений . Если да, включите такой многочлен в выходной список.${\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 i\in [n]}$${\displaystyle p(X)}$

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

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

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

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

Внешние ссылки [ править ]

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