Алгоритм декодирования списка Гурусвами – Судан - Guruswami–Sudan list decoding algorithm

Эта статья поднимает множество проблем. Пожалуйста помоги Улучши это или обсудите эти вопросы на страница обсуждения. (Узнайте, как и когда удалить эти сообщения-шаблоны) Эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: «Алгоритм расшифровки списка Гурусвами – Судан»  – Новости  · газеты  · книги  · ученый  · JSTOR (Май 2012 г.) (Узнайте, как и когда удалить этот шаблон сообщения) Эта статья может содержать чрезмерное количество сложных деталей, которые могут заинтересовать только определенную аудиторию. Пожалуйста, помогите спиннинг или же переезд любая соответствующая информация и удаление лишних деталей, которые могут противоречить Политика включения Википедии. (август 2013) (Узнайте, как и когда удалить этот шаблон сообщения) (Узнайте, как и когда удалить этот шаблон сообщения)

В теория кодирования, расшифровка списка является альтернативой уникальному декодированию кодов с исправлением ошибок при наличии большого количества ошибок. Если код имеет относительное расстояние ${ displaystyle delta}$, то в принципе возможно восстановить закодированное сообщение, когда до ${ displaystyle delta / 2}$ часть символов кодового слова повреждена. Но когда частота ошибок больше, чем ${ displaystyle delta / 2}$, это вообще невозможно. Декодирование списка решает эту проблему, позволяя декодеру выводить короткий список сообщений, которые могли быть закодированы. Расшифровка списка может исправить более чем ${ displaystyle delta / 2}$ доля ошибок.

Существует множество алгоритмов полиномиального времени для декодирования списков. В этой статье мы сначала представляем алгоритм для Коды Рида – Соломона (RS) который исправляет до ${ displaystyle 1 - { sqrt {2R}}}$ ошибки и связано с Мадху Судан. Далее опишем улучшенный Гурусвами –Судан список алгоритмов декодирования, который может исправить до ${ displaystyle 1 - { sqrt {R}}}$ ошибки.

Вот график скорости R и расстояния ${ displaystyle delta}$ для разных алгоритмов.

https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/81/Graph.jpg

Алгоритм 1 (алгоритм декодирования списка Судана)

Постановка задачи

Вход : Поле ${ displaystyle F}$; n различных пар элементов ${ displaystyle {(x_ {i}, y_ {i}) _ {i = 1} ^ {n}}}$ в ${ displaystyle F times F}$; и целые числа ${ displaystyle d}$ и ${ displaystyle t}$.

Выход: Список всех функций ${ displaystyle f: F to F}$ удовлетворение

${ displaystyle f (x)}$ является многочленом от ${ displaystyle x}$ степени не более ${ displaystyle d}$

${ Displaystyle # {я | е (х_ {я}) = у_ {я} } geq t}$

(1)

Чтобы лучше понять алгоритм Судана, можно сначала узнать другой алгоритм, который можно рассматривать как более раннюю версию или фундаментальную версию алгоритмов для декодирования RS-кодов по списку - Алгоритм Берлекампа – Велча.Welch и Berlekamp изначально пришли с алгоритм который может решить проблему за полиномиальное время с лучшим порогом на ${ displaystyle t}$ быть ${ Displaystyle т geq (п + d + 1) / 2}$. Механизм алгоритма Судана почти такой же, как алгоритм алгоритма Берлекампа – Велча, за исключением шага 1, когда требуется вычислить двумерный многочлен ограниченного ${ Displaystyle (1, к)}$ степень. Алгоритм декодирования списка Судана для кода Рида – Соломона, который является усовершенствованием алгоритма Берлекампа и Велча, может решить проблему с ${ displaystyle t = ({ sqrt {2nd}})}$. Эта граница лучше, чем уникальная граница декодирования. ${ displaystyle 1- left ({ frac {R} {2}} right)}$ за ${ Displaystyle R <0,07}$.

Алгоритм

Определение 1 (взвешенная степень)

Для весов ${ displaystyle w_ {x}, w_ {y} in mathbb {Z} ^ {+}}$, то ${ Displaystyle (ш_ {х}, ш_ {у})}$ - взвешенная степень монома ${ displaystyle q_ {ij} x ^ {i} y ^ {j}}$ является ${ displaystyle iw_ {x} + jw_ {y}}$. В ${ Displaystyle (ш_ {х}, ш_ {у})}$ - взвешенная степень полинома ${ Displaystyle Q (х, y) = сумма _ {ij} q_ {ij} x ^ {i} y ^ {j}}$ является максимумом по одночленам с ненулевыми коэффициентами ${ Displaystyle (ш_ {х}, ш_ {у})}$ - взвешенная степень монома.

Например, ${ displaystyle xy ^ {2}}$ имеет ${ displaystyle (1,3)}$-степень 7

Алгоритм:

Входы: ${ displaystyle n, d, t}$; {${ Displaystyle (x_ {1}, y_ {1}) cdots (x_ {n}, y_ {n})}$} / * Параметры l, m будут установлены позже. * /

Шаг 1. Найдите ненулевой двумерный многочлен ${ Displaystyle Q: F ^ {2} mapsto F}$ удовлетворение

• ${ Displaystyle Q (х, у)}$ имеет ${ displaystyle (1, d)}$-взвешенная степень не более ${ displaystyle D = m + ld}$
• Для каждого ${ Displaystyle я в [п]}$,

${ displaystyle Q (x_ {i}, y_ {i}) = 0}$

(2)

Шаг 2. Разложите Q на неприводимые множители.

Шаг 3. Выведите все многочлены. ${ displaystyle f}$ такой, что ${ Displaystyle (у-е (х))}$ является фактором Q и ${ displaystyle f (x_ {i}) = y_ {i}}$ для не менее t значений ${ Displaystyle я в [п]}$

Анализ

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

Утверждение 1:

Если функция ${ displaystyle Q: F ^ {2} to F}$ удовлетворяющий (2) существует, то его можно найти за полиномиальное время.

Доказательство:

Обратите внимание, что двумерный многочлен ${ Displaystyle Q (х, у)}$ из ${ displaystyle (1, d)}$-взвешенная степень не более ${ displaystyle D}$ можно однозначно записать как ${ displaystyle Q (x, y) = sum _ {j = 0} ^ {l} sum _ {k = 0} ^ {m + (lj) d} q_ {kj} x ^ {k} y ^ { j}}$. Затем нужно найти коэффициенты ${ displaystyle q_ {kj}}$ удовлетворение ограничений ${ displaystyle sum _ {j = 0} ^ {l} sum _ {k = 0} ^ {m + (lj) d} q_ {kj} x_ {i} ^ {k} y_ {i} ^ {j } = 0}$, для каждого ${ Displaystyle я в [п]}$. Это линейная система уравнений с неизвестными {${ displaystyle q_ {kj}}$}. Решение можно найти, используя Гауссово исключение за полиномиальное время.

Утверждение 2:

Если ${ Displaystyle (м + 1) (l + 1) + d { begin {pmatrix} l + 1 2 end {pmatrix}}> п}$ тогда существует функция ${ Displaystyle Q (х, у)}$ удовлетворяющий (2)

Доказательство:

Чтобы гарантировать наличие ненулевого решения, количество коэффициентов в ${ Displaystyle Q (х, у)}$ должно быть больше, чем количество ограничений. Предположим, что максимальная степень ${ displaystyle deg_ {x} (Q)}$ из ${ displaystyle x}$ в ${ Displaystyle Q (х, у)}$ m и максимальная степень ${ displaystyle deg_ {y} (Q)}$ из ${ displaystyle y}$ в ${ Displaystyle Q (х, у)}$ является ${ displaystyle l}$. Тогда степень ${ Displaystyle Q (х, у)}$ будет самое большее ${ displaystyle m + ld}$. Надо видеть, что линейная система однородна. Настройки ${ displaystyle q_ {jk} = 0}$ удовлетворяет всем линейным ограничениям. Однако это не удовлетворяет (2), поскольку решение может быть тождественно нулевым. Чтобы гарантировать, что существует ненулевое решение, нужно убедиться, что количество неизвестных в линейной системе равно ${ Displaystyle (м + 1) (l + 1) + d { begin {pmatrix} l + 1 2 end {pmatrix}}> п}$, так что можно иметь ненулевой ${ Displaystyle Q (х, у)}$. Поскольку это значение больше n, переменных больше, чем ограничений, и поэтому существует ненулевое решение.

Утверждение 3:

Если ${ Displaystyle Q (х, у)}$ - функция, удовлетворяющая (2) и ${ displaystyle f (x)}$ - функция, удовлетворяющая (1) и ${ displaystyle t> m + ld}$, тогда ${ Displaystyle (у-е (х))}$ разделяет ${ Displaystyle Q (х, у)}$

Доказательство:

Рассмотрим функцию ${ Displaystyle р (х) = Q (х, f (х))}$. Это многочлен от ${ displaystyle x}$, и утверждают, что он имеет степень не выше ${ displaystyle m + ld}$. Рассмотрим любой моном ${ displaystyle q_ {jk} x ^ {k} y ^ {j}}$ из ${ Displaystyle Q (х)}$. С ${ displaystyle Q}$ имеет ${ displaystyle (1, d)}$-взвешенная степень не более ${ displaystyle m + ld}$можно сказать, что ${ Displaystyle к + jd leq m + ld}$. Таким образом, термин ${ displaystyle q_ {kj} x ^ {k} f (x) ^ {j}}$ является многочленом от ${ displaystyle x}$ степени не более ${ Displaystyle к + jd leq m + ld}$. Таким образом ${ displaystyle p (x)}$ имеет высшее образование ${ displaystyle m + ld}$

Далее утверждают, что ${ displaystyle p (x)}$ тождественно нулю. С ${ Displaystyle Q (x_ {i}, f (x_ {i}))}$ равен нулю всякий раз, когда ${ Displaystyle у_ {я} = е (х_ {я})}$можно сказать, что ${ displaystyle p (x_ {i})}$ равен нулю для строго больше, чем ${ displaystyle m + ld}$ точки. Таким образом ${ displaystyle p}$имеет больше нулей, чем его степень и, следовательно, тождественно равен нулю, что означает ${ Displaystyle Q (х, е (х)) эквив 0}$

Поиск оптимальных значений для ${ displaystyle m}$ и ${ displaystyle l}$.Обратите внимание, что ${ displaystyle m + ld$ и ${ Displaystyle (м + 1) (l + 1) + d { begin {pmatrix} l + 1 2 end {pmatrix}}> п}$Для заданного значения ${ displaystyle l}$, можно вычислить наименьшее ${ displaystyle m}$ для которого выполняется второе условие. Меняя местами второе условие, можно получить ${ displaystyle m}$ быть в лучшем случае ${ Displaystyle (п + 1-d { begin {pmatrix} l + 1 2 end {pmatrix}}) / 2-1}$Подставляя это значение в первое условие, можно получить ${ displaystyle t}$ быть хотя бы ${ displaystyle { frac {n + 1} {l + 1}} + { frac {dl} {2}}}$Затем минимизируйте указанное выше уравнение неизвестного параметра ${ displaystyle l}$. Это можно сделать, взяв производную уравнения и приравняв ее к нулю. ${ displaystyle l = { sqrt { frac {2 (n + 1)} {d}}} - 1}$Подставляя обратно ${ displaystyle l}$ ценность в ${ displaystyle m}$ и ${ displaystyle t}$ один получит${ displaystyle m geq { sqrt { frac {(n + 1) d} {2}}} - { sqrt { frac {(n + 1) d} {2}}} + { frac { d} {2}} - 1 = { frac {d} {2}} - 1}$${ displaystyle t> { sqrt { frac {2 (n + 1) d ^ {2}} {d}}} - { frac {d} {2}} - 1}$${ displaystyle t> { sqrt {2 (n + 1) d}} - { frac {d} {2}} - 1}$

Алгоритм 2 (алгоритм декодирования списка Гурусвами – Судан)

Определение

Рассмотрим ${ Displaystyle (п, к)}$ Код Рида – Соломона над конечным полем ${ Displaystyle mathbb {F} = GF (q)}$ с оценочным набором ${ Displaystyle ( альфа _ {1}, альфа _ {2}, ldots, альфа _ {п})}$ и положительное целое число ${ displaystyle r}$, декодер списка Гурусвами-Судана принимает вектор ${ displaystyle beta = ( beta _ {1}, beta _ {2}, ldots, beta _ {n})}$ ${ displaystyle in}$ ${ Displaystyle mathbb {F} ^ {п}}$ в качестве входных данных и выводит список многочленов степени ${ displaystyle leq k}$ которые находятся в соответствии 1 к 1 с кодовыми словами.

Идея состоит в том, чтобы добавить больше ограничений на двумерный многочлен ${ Displaystyle Q (х, у)}$ что приводит к увеличению ограничений вместе с количеством корней.

Множественность

Двумерный многочлен ${ Displaystyle Q (х, у)}$ имеет нуль кратности ${ displaystyle r}$ в ${ displaystyle (0,0)}$ Значит это ${ Displaystyle Q (х, у)}$ не имеет срока ${ displaystyle leq r}$, где Икс-степень ${ displaystyle f (x)}$ определяется как максимальная степень любого члена x в ${ displaystyle f (x)}$${ displaystyle qquad}$ ${ Displaystyle deg_ {х} е (х)}$ ${ displaystyle =}$ ${ Displaystyle макс _ {я в I} {я }}$

Например: пусть ${ Displaystyle Q (х, y) = y-4x ^ {2}}$.

https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/76/Fig1.jpg

Следовательно, ${ Displaystyle Q (х, у)}$ имеет нуль кратности 1 в точке (0,0).

Позволять ${ Displaystyle Q (х, y) = y + 6x ^ {2}}$.

https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/76/Fig2.jpg

Следовательно, ${ Displaystyle Q (х, у)}$ имеет нуль кратности 1 в точке (0,0).

Позволять ${ Displaystyle Q (x, y) = (y-4x ^ {2}) (y + 6x ^ {2}) = y ^ {2} + 6x ^ {2} y-4x ^ {2} y-24x ^ {4}}$

https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/76/Fig3.jpg

Следовательно, ${ Displaystyle Q (х, у)}$ имеет нуль кратности 2 в точке (0,0).

Аналогично, если ${ Displaystyle Q (х, у) = [(у- бета) -4 (х- альфа) ^ {2})] [(у- бета) +6 (х- альфа) ^ {2} )]}$Потом, ${ Displaystyle Q (х, у)}$ имеет нуль кратности 2 при ${ Displaystyle ( альфа, бета)}$.

Общее определение множественности

${ Displaystyle Q (х, у)}$ имеет ${ displaystyle r}$ корни в ${ Displaystyle ( альфа, бета)}$ если ${ Displaystyle Q (х, у)}$ имеет нуль кратности ${ displaystyle r}$ в ${ Displaystyle ( альфа, бета)}$ когда ${ Displaystyle ( альфа, бета) neq (0,0)}$.

Алгоритм

Пусть переданное кодовое слово будет ${ Displaystyle (е ( альфа _ {1}), е ( альфа _ {2}), ldots, f ( альфа _ {п}))}$,${ Displaystyle ( альфа _ {1}, альфа _ {2}, ldots, альфа _ {п})}$ быть поддерживающим набором переданного кодового слова и принятого слова быть ${ displaystyle ( beta _ {1}, beta _ {2}, ldots, beta _ {n})}$

Алгоритм следующий:

• Шаг интерполяции

Для полученного вектора ${ displaystyle ( beta _ {1}, beta _ {2}, ldots, beta _ {n})}$, построим ненулевой двумерный многочлен ${ Displaystyle Q (х, у)}$ с ${ Displaystyle (1, к) -}$взвешенная степень не более ${ displaystyle d}$ такой, что ${ displaystyle Q}$ имеет нуль кратности ${ displaystyle r}$ в каждой из точек ${ Displaystyle ( альфа _ {я}, бета _ {я})}$ куда ${ Displaystyle 1 Leq я Leq п}$

${ Displaystyle Q ( альфа _ {я}, бета _ {я}) = 0 ,}$

• Шаг факторизации

Найдите все факторы ${ Displaystyle Q (х, у)}$ формы ${ Displaystyle у-р (х)}$ и ${ Displaystyle р ( альфа _ {я}) = бета _ {я}}$ по крайней мере ${ displaystyle t}$ ценности ${ displaystyle i}$

куда ${ Displaystyle 0 Leq я Leq п}$ & ${ displaystyle p (x)}$ является многочленом степени ${ displaystyle leq k}$

Напомним, что многочлены степени ${ displaystyle leq k}$ находятся в соответствии 1 к 1 с кодовыми словами. Следовательно, этот шаг выводит список кодовых слов.

Анализ

Шаг интерполяции

Лемма:Шаг интерполяции подразумевает ${ displaystyle { begin {pmatrix} r + 1 2 end {pmatrix}}}$ ограничения на коэффициенты ${ displaystyle a_ {i}}$

Позволять ${ displaystyle Q (x, y) = sum _ {i = 0, j = 0} ^ {i = m, j = p} a_ {i, j} x ^ {i} y ^ {j}}$куда ${ displaystyle deg _ {x} Q (x, y) = m}$ и ${ displaystyle deg _ {y} Q (x, y) = p}$

Потом, ${ Displaystyle Q (х + альфа, у + бета)}$ ${ displaystyle =}$ ${ displaystyle sum _ {u = 0, v = 0} ^ {r}}$ ${ displaystyle Q_ {u, v}}$ ${ Displaystyle ( альфа, бета)}$ ${ displaystyle x ^ {u}}$ ${ displaystyle y ^ {v}}$ ........................ (Уравнение 1)

куда ${ displaystyle Q_ {u, v}}$ ${ Displaystyle (х, у)}$ ${ displaystyle =}$ ${ Displaystyle сумма _ {я = 0, j = 0} ^ {я = м, j = p}}$ ${ displaystyle { begin {pmatrix} я u end {pmatrix}}}$ ${ displaystyle { begin {pmatrix} j v end {pmatrix}}}$ ${ displaystyle a_ {i, j}}$ ${ Displaystyle х ^ {я-и}}$ ${ displaystyle y ^ {j-v}}$

Доказательство уравнения 1:

${ Displaystyle Q (х + альфа, у + бета) = сумма _ {я, j} а_ {я, j} (х + альфа) ^ {я} (у + бета) ^ {j}}$

${ Displaystyle Q (х + альфа, y + бета) = сумма _ {я, j} a_ {я, j} { Bigg (} sum _ {u} { begin {pmatrix} я u конец {pmatrix}} x ^ {u} alpha ^ {iu} { Bigg)} { Bigg (} sum _ {v} { begin {pmatrix} i v end {pmatrix}} y ^ {v} beta ^ {jv} { Bigg)}}$................. Использование биномиального разложения

${ Displaystyle Q (х + альфа, y + бета) = sum _ {u, v} x ^ {u} y ^ {v} { Bigg (} sum _ {i, j} { begin {pmatrix } i u end {pmatrix}} { begin {pmatrix} i v end {pmatrix}} a_ {i, j} alpha ^ {iu} beta ^ {jv} { Bigg)} }$

${ Displaystyle Q (х + альфа, y + бета) = сумма _ {и, v}}$ ${ Displaystyle Q_ {и, v} ( альфа, бета) х ^ {и} у ^ {v}}$

Доказательство леммы:

Полином ${ Displaystyle Q (х, у)}$ имеет нуль кратности ${ displaystyle r}$ в ${ Displaystyle ( альфа, бета)}$ если

${ displaystyle Q_ {u, v}}$ ${ Displaystyle ( альфа, бета)}$ ${ Displaystyle Equiv}$ ${ displaystyle 0}$ такой, что ${ Displaystyle 0 leq и + v leq r-1}$

${ displaystyle u}$ может взять ${ displaystyle r-v}$ ценности как ${ Displaystyle 0 Leq V Leq R-1}$. Таким образом, общее количество ограничений равно

${ displaystyle sum _ {v = 0} ^ {r-1} {r-v}}$ ${ displaystyle =}$ ${ displaystyle { begin {pmatrix} r + 1 2 end {pmatrix}}}$

Таким образом, ${ displaystyle { begin {pmatrix} r + 1 2 end {pmatrix}}}$ количество вариантов выбора может быть сделано для ${ Displaystyle (и, v)}$ и каждый выбор подразумевает ограничения на коэффициенты ${ displaystyle a_ {i}}$

Шаг факторизации

Предложение:

${ Displaystyle Q (х, р (х)) эквив 0}$ если ${ Displaystyle у-р (х)}$ фактор ${ Displaystyle Q (х, у)}$

Доказательство:

С, ${ Displaystyle у-р (х)}$ фактор ${ Displaystyle Q (х, у)}$, ${ Displaystyle Q (х, у)}$ можно представить как

${ Displaystyle Q (x, y) = L (x, y) (y-p (x))}$ ${ displaystyle +}$ ${ Displaystyle R (х)}$

куда, ${ Displaystyle L (х, у)}$ частное, полученное, когда ${ Displaystyle Q (х, у)}$ делится на ${ Displaystyle у-р (х)}$${ Displaystyle R (х)}$ это остаток

Сейчас если ${ displaystyle y}$ заменяется на ${ displaystyle p (x)}$, ${ Displaystyle Q (х, р (х))}$ ${ Displaystyle Equiv}$ ${ displaystyle 0}$, только если ${ Displaystyle R (х)}$ ${ Displaystyle Equiv}$ ${ displaystyle 0}$

Теорема:

Если ${ Displaystyle р ( альфа) = бета}$, тогда ${ Displaystyle (х- альфа) ^ {г}}$ фактор ${ Displaystyle Q (х, р (х))}$

Доказательство:

${ Displaystyle Q (х, у)}$ ${ displaystyle =}$ ${ Displaystyle сумма _ {и, v}}$ ${ displaystyle Q_ {u, v}}$ ${ Displaystyle ( альфа, бета)}$ ${ Displaystyle (х- альфа) ^ {и}}$ ${ Displaystyle (у- бета) ^ {v}}$........................... из уравнения 2

${ Displaystyle Q (х, р (х))}$ ${ displaystyle =}$ ${ Displaystyle сумма _ {и, v}}$ ${ displaystyle Q_ {u, v}}$ ${ Displaystyle ( альфа, бета)}$ ${ Displaystyle (х- альфа) ^ {и}}$ ${ Displaystyle (п (х) - бета) ^ {v}}$

Данный, ${ Displaystyle р ( альфа)}$ ${ displaystyle =}$ ${ displaystyle beta}$${ Displaystyle (п (х) - бета)}$ мод ${ Displaystyle (х- альфа)}$ ${ displaystyle =}$ ${ displaystyle 0}$

Следовательно, ${ Displaystyle (х- альфа) ^ {и}}$ ${ Displaystyle (п (х) - бета) ^ {v}}$ мод ${ Displaystyle (х- альфа) ^ {и + v}}$ ${ displaystyle =}$ ${ displaystyle 0}$

Таким образом, ${ Displaystyle (х- альфа) ^ {г}}$ фактор ${ Displaystyle Q (х, р (х))}$.

Как доказано выше,

${ displaystyle t cdot r> D}$

${ displaystyle t> { frac {D} {r}}}$

${ displaystyle { frac {D (D + 2)} {2 (k-1)}}> п { begin {pmatrix} r + 1 2 end {pmatrix}}}$где LHS - верхняя граница числа коэффициентов ${ Displaystyle Q (х, у)}$ RHS - доказанная ранее лемма.

${ Displaystyle D = { sqrt {knr (r-1)}} ,}$

Следовательно, ${ displaystyle t = left lceil { sqrt {kn (1 - { frac {1} {r}})}} right rceil}$

Заменять ${ displaystyle r = 2kn}$,

${ displaystyle t> left lceil { sqrt {kn - { frac {1} {2}}}} right rceil> left lceil { sqrt {kn}} right rceil}$

Следовательно, доказано, что алгоритм декодирования списков Гурусвами – Судана может Коды Рида-Соломона вплоть до ${ displaystyle 1 - { sqrt {R}}}$ ошибки.

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

• https://web.archive.org/web/20100702120650/http://www.cse.buffalo.edu/~atri/courses/coding-theory/
• https://www.cs.cmu.edu/~venkatg/pubs/papers/listdecoding-NOW.pdf
• http://www.mendeley.com/research/algebraic-softdecision-decoding-reedsolomon-codes/
• Р. Дж. МакЭлис. Алгоритм декодирования Гурусвами-Судана для кодов Рида-Соломона.
• М Судан. Декодирование кодов Рида-Соломона за пределами исправления ошибок.