Исправление ошибок Рида – Соломона - Reed–Solomon error correction

Коды Рида – Соломона
Названный в честь	Ирвинг С. Рид и Гюстав Соломон
Классификация
Иерархия	Линейный блочный код Полиномиальный код Код Рида – Соломона
Длина блока	п
Длина сообщения	k
Расстояние	п − k + 1
Размер алфавита	q = пм ≥ п  (п премьер) Часто п = q − 1.
Обозначение	[п, k, п − k + 1]q-код
Алгоритмы
Берлекамп – Мэсси Евклидово и другие.
Свойства
Разделимый код максимального расстояния

Коды Рида – Соломона группа коды с исправлением ошибок которые были представлены Ирвинг С. Рид и Гюстав Соломон в 1960 г.^[1]У них много приложений, наиболее известными из которых являются потребительские технологии, такие как Компакт-диски, DVD, Блю рей диски, QR коды, передача информации такие технологии как DSL и WiMAX, трансляция такие системы, как спутниковая связь, DVB и ATSC, и системы хранения, такие как RAID 6.

Коды Рида – Соломона работают с блоком данных, рассматриваемым как набор конечное поле элементы, называемые символами. Коды Рида – Соломона способны обнаруживать и исправлять множественные символьные ошибки. Добавлением т = п − k проверять символы в данных, код Рида – Соломона может обнаруживать (но не исправлять) любую комбинацию до включительно т ошибочные символы, или найти и исправить до включительно ⌊т/2⌋ ошибочные символы в неизвестных местах. Как код стирания, он может исправить до т стирание в местах, которые известны и предоставлены алгоритму, или он может обнаруживать и исправлять комбинации ошибок и стираний. Коды Рида – Соломона также подходят в качестве многократныхвзрыв коды с исправлением битовых ошибок, поскольку последовательность б + 1 последовательные битовые ошибки могут повлиять не более чем на два символа размера б. Выбор т зависит от разработчика кода и может быть выбран в широких пределах.

Существует два основных типа кодов Рида – Соломона - исходный вид и BCH view - наиболее распространенным является представление BCH, поскольку декодеры представления BCH работают быстрее и требуют меньше памяти, чем исходные декодеры представления.

История

Коды Рида – Соломона были разработаны в 1960 г. Ирвинг С. Рид и Гюстав Соломон, которые тогда были сотрудниками Лаборатория Линкольна Массачусетского технологического института. Их основополагающая статья называлась «Полиномиальные коды над некоторыми конечными полями». (Рид и Соломон 1960 ). Исходная схема кодирования, описанная в статье Рида и Соломона, использовала переменный многочлен на основе сообщения, которое нужно кодировать, где кодировщику и декодеру известен только фиксированный набор значений (точек оценки), которые должны быть закодированы. Первоначальный теоретический декодер генерировал потенциальные многочлены на основе подмножеств k (длина незашифрованного сообщения) из п (длина закодированного сообщения) значения полученного сообщения, выбирая наиболее популярный полином в качестве правильного, что было непрактично во всех случаях, кроме простейшего. Первоначально это было решено путем изменения исходной схемы на Код BCH подобная схема основана на фиксированном полиноме, известном как кодеру, так и декодеру, но позже были разработаны практические декодеры на основе исходной схемы, хотя и более медленные, чем схемы BCH. Результатом этого является то, что существует два основных типа кодов Рида-Соломона: те, которые используют исходную схему кодирования, и те, которые используют схему кодирования BCH.

Также в 1960 году практический фиксированный полиномиальный декодер для Коды BCH разработан Даниэль Горенштейн и Нил Зирлер был описан в отчете лаборатории Линкольна Массачусетского технологического института Зирлера в январе 1960 года, а затем в статье в июне 1961 года.^[2] Декодер Горенштейна – Цирлера и связанная с ним работа над кодами BCH описаны в книге «Коды с исправлением ошибок» автора. В. Уэсли Петерсон (1961).^[3] К 1963 году (или, возможно, раньше) Дж. Дж. Стоун (и другие) признали, что коды Рида-Соломона могут использовать схему БЧХ с использованием фиксированного порождающего полинома, что делает такие коды особым классом кодов БЧХ,^[4] но коды Рида-Соломона, основанные на исходной схеме кодирования, не являются классом кодов BCH, и в зависимости от набора точек оценки они даже не циклические коды.

В 1969 году усовершенствованный декодер схемы BCH был разработан Элвин Берлекамп и Джеймс Мэсси, и с тех пор известен как Алгоритм декодирования Берлекампа-Месси.

В 1975 году Ясуо Сугияма разработал еще один улучшенный декодер схемы BCH, основанный на расширенный алгоритм Евклида.^[5]

В 1977 году коды Рида – Соломона были реализованы в Программа "Вояджер" в виде составные коды исправления ошибок. Первое коммерческое применение в массовых потребительских товарах появилось в 1982 году с компакт-диск, где два чередующийся Используются коды Рида – Соломона. Сегодня коды Рида – Соломона широко применяются в цифровое хранилище устройства и цифровая связь стандартов, хотя они постепенно заменяются более современными коды с низкой плотностью проверки четности (LDPC) или турбокоды. Например, коды Рида – Соломона используются в Цифровое видеовещание (DVB) стандарт DVB-S, но коды LDPC используются в его преемнике, DVB-S2.

В 1986 году оригинальная схема декодера, известная как Алгоритм Берлекампа – Велча был развит.

В 1996 году Мадху Судан и другие разработали варианты декодеров исходных схем, называемые декодерами списков или программными декодерами, и работа над этими типами декодеров продолжается - см. Алгоритм декодирования списка Гурусвами – Судан.

В 2002 году Шухонг Гао разработал еще одну оригинальную схему декодера, основанную на расширенный алгоритм Евклида Gao_RS.pdf .

Приложения

Хранилище данных

Кодирование Рида – Соломона очень широко используется в системах хранения данных для исправления пакетных ошибок, связанных с дефектами носителя.

Кодирование Рида – Соломона - ключевой компонент компакт-диск. Это было первое использование сильного кодирования с исправлением ошибок в массовом потребительском продукте, и DAT и DVD использовать аналогичные схемы. На компакт-диске два уровня кодирования Рида – Соломона, разделенные 28-полосным сверточный перемежитель дает схему, называемую кодированием Рида – Соломона с перекрестным чередованием (CIRC ). Первым элементом декодера CIRC является относительно слабый внутренний (32,28) код Рида – Соломона, сокращенный от кода (255,251) с 8-битовыми символами. Этот код может исправить до 2-х байтовых ошибок на 32-байтовый блок. Что еще более важно, он помечает как стирающие любые неисправимые блоки, то есть блоки с ошибками более 2 байтов. Декодированные 28-байтовые блоки с индикацией стирания затем распространяются обращенным перемежителем на разные блоки внешнего кода (28,24). Благодаря обратному чередованию стертый 28-байтовый блок внутреннего кода становится одним стертым байтом в каждом из 28 внешних кодовых блоков. Внешний код легко исправляет это, так как он может обрабатывать до 4 таких стираний на блок.

Результатом является CIRC, который может полностью исправить пакеты ошибок размером до 4000 бит или около 2,5 мм на поверхности диска. Этот код настолько силен, что большинство ошибок при воспроизведении компакт-дисков почти наверняка вызваны ошибками отслеживания, которые приводят к смене трека лазером, а не пакетами неисправимых ошибок.^[6]

DVD используют аналогичную схему, но с гораздо большими блоками, внутренним кодом (208,192) и внешним кодом (182,172).

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

Штрих-код

Почти все двумерные штрих-коды, такие как PDF-417, MaxiCode, Datamatrix, QR код, и Кодекс ацтеков используйте исправление ошибок Рида – Соломона, чтобы обеспечить правильное считывание, даже если часть штрих-кода повреждена. Когда сканер штрих-кода не может распознать символ штрих-кода, он будет рассматривать его как стирание.

Кодирование Рида – Соломона менее распространено в одномерных штрих-кодах, но используется PostBar символика.

Передача информации

Специализированные формы кодов Рида – Соломона, в частности Коши -RS и Vandermonde -RS, может использоваться для преодоления ненадежного характера передачи данных по каналы стирания. Процесс кодирования предполагает код RS (N, K), что приводит к N кодовые слова длины N символы, каждый хранящий K символы генерируемых данных, которые затем отправляются по каналу стирания.

Любая комбинация K кодовых слов, полученных на другом конце, достаточно, чтобы восстановить все N кодовые слова. Кодовая скорость обычно устанавливается равной 1/2, если вероятность стирания канала не может быть адекватно смоделирована и не считается меньшей. В заключении, N обычно 2K, что означает, что по крайней мере половина всех отправленных кодовых слов должна быть получена, чтобы восстановить все отправленные кодовые слова.

Коды Рида – Соломона также используются в xDSL системы и CCSDS с Спецификации протокола космической связи как форма упреждающее исправление ошибок.

Космическая передача

Система конкатенированного кодирования глубокого космоса.^[7] Замечание: RS (255, 223) + CC («длина ограничения» = 7, кодовая скорость = 1/2).

Одним из важных применений кодирования Рида-Соломона было кодирование цифровых изображений, отправленных обратно Вояджер Космический зонд.

Вояджер представил кодирование Рида-Соломона соединенный с участием сверточные коды, практика, которая с тех пор стала очень распространенной в дальнем космосе и спутниковой связи (например, прямое цифровое вещание).

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

Современные версии конкатенированного сверточного кодирования с декодированием Рида – Соломона / Витерби использовались и используются на Марс-следопыт, Галилео, Марсоход для исследования Марса и Кассини миссии, где они выполняются в пределах 1–1,5 дБ конечного предела, будучи Емкость Шеннона.

Эти объединенные коды теперь заменяются более мощными турбокоды:

Схемы кодирования каналов, используемые миссиями НАСА^[8]

Лет	Код	Миссия (и)
1958-настоящее время	Некодированный	Explorer, Mariner, многие другие
1968-1978	сверточные коды (CC) (25, 1/2)	Пионер, Венера
1969-1975 (32, 6)	Код Рида-Мюллера	Моряк, Викинг
1977-настоящее время	Двоичный код Голея	Вояджер
1977-настоящее время	RS (255, 223) + CC (7, 1/2)	"Вояджер", "Галилей" и многие другие.
1989-2003	RS (255, 223) + CC (7, 1/3)	Вояджер
1958-настоящее время	RS (255, 223) + CC (14, 1/4)	Галилео
1996-настоящее время	RS + CC (15, 1/6)	Кассини, Марс-следопыт, другие
2004-настоящее время	Турбо коды[nb 1]	Посланник, стерео, ТОиР, другие
оценка 2009 г.	Коды LDPC	Созвездие, MSL

Конструкции

Код Рида – Соломона на самом деле представляет собой семейство кодов, в котором каждый код характеризуется тремя параметрами: алфавит размер q, а длина блока п, а длина сообщения k, с участием к <п ≤ q. Набор символов алфавита интерпретируется как конечное поле порядка q, и поэтому, q должен быть основная сила. В наиболее полезных параметризациях кода Рида – Соломона длина блока обычно является некоторым постоянным кратным длине сообщения, то есть показатель р = k/п - некоторая константа, и, кроме того, длина блока равна или на единицу меньше размера алфавита, то есть п = q или п = q − 1.^{[нужна цитата ]}

Исходный взгляд Рида и Соломона: кодовое слово как последовательность значений

Для кода Рида – Соломона существуют разные процедуры кодирования, и, следовательно, есть разные способы описания набора всех кодовых слов. Рид и Соломон (1960), каждое кодовое слово кода Рида – Соломона представляет собой последовательность значений функции полинома степени меньше k. Чтобы получить кодовое слово кода Рида – Соломона, сообщение интерпретируется как описание полинома п степени меньше чем k над конечным полем F с участием q элементов, а многочлен п оценивается в п ≤ q отдельные точки ${\displaystyle a_{1},\dots ,a_{n}}$ поля F, а последовательность значений - соответствующее кодовое слово. Обычный выбор для набора оценок: {0, 1, 2, ..., п − 1}, {0, 1, α, α², ..., α^п−2}, или для п < q, {1, α, α², ..., α^п−1}, ... , где α это примитивный элемент из F.

Формально набор ${\displaystyle \mathbf {C} }$ кодовых слов кода Рида – Соломона определяется следующим образом:

${\displaystyle \mathbf {C} ={\Big \{}\;{\big (}p(a_{1}),p(a_{2}),\dots ,p(a_{n}){\big )}\;{\Big |}\;p{\text{ is a polynomial over }}F{\text{ of degree }}<k\;{\Big \}}\,.}$

Поскольку любые два отчетливый многочлены степени меньше чем ${\displaystyle k}$ согласен в лучшем случае ${\displaystyle k-1}$ точек, это означает, что любые два кодовых слова кода Рида – Соломона не совпадают по крайней мере в ${\displaystyle n-(k-1)=n-k+1}$ Кроме того, есть два многочлена, которые согласуются в ${\displaystyle k-1}$ точки, но не равны, и, следовательно, расстояние кода Рида – Соломона точно ${\displaystyle d=n-k+1}$.Тогда относительное расстояние ${\displaystyle \delta =d/n=1-k/n+1/n=1-R+1/n\sim 1-R}$, где ${\displaystyle R=k/n}$ Этот компромисс между относительным расстоянием и скоростью является асимптотически оптимальным, поскольку Граница синглтона, каждый код удовлетворяет ${\displaystyle \delta +R\leq 1+1/n}$Поскольку код Рида-Соломона достигает этого оптимального компромисса, он принадлежит к классу коды максимального расстояния.

В то время как количество различных многочленов степени меньше k и количество разных сообщений равно ${\displaystyle q^{k}}$, и, таким образом, каждое сообщение может быть однозначно сопоставлено с таким многочленом, есть разные способы сделать это кодирование. Рид и Соломон (1960) интерпретирует сообщение Икс как коэффициенты полинома п, тогда как последующие конструкции интерпретируют сообщение как ценности полинома на первом k точки ${\displaystyle a_{1},\dots ,a_{k}}$ и получим многочлен п путем интерполяции этих значений полиномом степени меньше, чем kПоследняя процедура кодирования, будучи немного менее эффективной, имеет то преимущество, что систематический код, то есть исходное сообщение всегда содержится как подпоследовательность кодового слова.

Простая процедура кодирования: сообщение как последовательность коэффициентов

В оригинальной конструкции Рид и Соломон (1960), сообщение ${\displaystyle x=(x_{1},\dots ,x_{k})\in F^{k}}$ отображается в полином ${\displaystyle p_{x}}$ с участием

${\displaystyle p_{x}(a)=\sum _{i=1}^{k}x_{i}a^{i-1}\,.}$

Кодовое слово ${\displaystyle x}$ получается путем оценки ${\displaystyle p_{x}}$ в ${\displaystyle n}$ разные точки ${\displaystyle a_{1},\dots ,a_{n}}$ поля ${\displaystyle F}$.Таким образом, классическая функция кодирования ${\displaystyle C:F^{k}\to F^{n}}$ для кода Рида – Соломона определяется следующим образом:

${\displaystyle C(x)={\big (}p_{x}(a_{1}),\dots ,p_{x}(a_{n}){\big )}\,.}$

Эта функция ${\displaystyle C}$ это линейное отображение, то есть удовлетворяет ${\displaystyle C(x)=x\cdot A}$ для следующих ${\displaystyle (k\times n)}$-матрица ${\displaystyle A}$ с элементами из ${\displaystyle F}$:

${\displaystyle A={\begin{bmatrix}1&\dots &1&\dots &1\\a_{1}&\dots &a_{k}&\dots &a_{n}\\a_{1}^{2}&\dots &a_{k}^{2}&\dots &a_{n}^{2}\\\vdots &&\vdots &&\vdots \\a_{1}^{k-1}&\dots &a_{k}^{k-1}&\dots &a_{n}^{k-1}\end{bmatrix}}}$

Эта матрица является транспонированной Матрица Вандермонда над ${\displaystyle F}$. Другими словами, код Рида – Соломона является линейный код, а в классической процедуре кодирования его матрица генератора является ${\displaystyle A}$.

Систематическая процедура кодирования: сообщение как начальная последовательность значений.

Существует альтернативная процедура кодирования, которая также производит код Рида – Соломона, но делает это в систематический путь. Здесь отображение из сообщения ${\displaystyle x}$ к многочлену ${\displaystyle p_{x}}$ работает иначе: полином ${\displaystyle p_{x}}$ теперь определяется как единственный многочлен степени меньше, чем ${\displaystyle k}$ такой, что

${\displaystyle p_{x}(a_{i})=x_{i}}$ относится ко всем ${\displaystyle i\in \{1,\dots ,k\}}$.

Чтобы вычислить этот полином ${\displaystyle p_{x}}$ от ${\displaystyle x}$, можно использовать Интерполяция Лагранжа.Как только он был найден, он оценивается в других точках. ${\displaystyle a_{k+1},\dots ,a_{n}}$ поля. Альтернативная функция кодирования ${\displaystyle C:F^{k}\to F^{n}}$ для кода Рида – Соломона опять же просто последовательность значений:

${\displaystyle C(x)={\big (}p_{x}(a_{1}),\dots ,p_{x}(a_{n}){\big )}\,.}$

С первого ${\displaystyle k}$ записи каждого кодового слова ${\displaystyle C(x)}$ совпадают с ${\displaystyle x}$, эта процедура кодирования действительно систематический.Поскольку интерполяция Лагранжа является линейным преобразованием, ${\displaystyle C}$ является линейным отображением. Фактически у нас есть ${\displaystyle C(x)=x\cdot G}$, где

${\displaystyle G=(A{\text{'s left square submatrix}})^{-1}\cdot A={\begin{bmatrix}1&0&0&\dots &0&g_{1,k+1}&\dots &g_{1,n}\\0&1&0&\dots &0&g_{2,k+1}&\dots &g_{2,n}\\0&0&1&\dots &0&g_{3,k+1}&\dots &g_{3,n}\\\vdots &\vdots &\vdots &&\vdots &\vdots &&\vdots \\0&\dots &0&\dots &1&g_{k,k+1}&\dots &g_{k,n}\end{bmatrix}}}$

Дискретное преобразование Фурье и его обратное

А дискретное преобразование Фурье по сути такая же, как и процедура кодирования; он использует полином генератора п(x), чтобы сопоставить набор точек оценки со значениями сообщения, как показано выше:

${\displaystyle C(x)={\big (}p_{x}(a_{1}),\dots ,p_{x}(a_{n}){\big )}\,.}$

Обратное преобразование Фурье можно использовать для преобразования безошибочного набора п < q значения сообщения обратно в полином кодирования k коэффициентов, с ограничением, что для того, чтобы это работало, набор точек оценки, используемых для кодирования сообщения, должен быть набором возрастающих степеней α:

${\displaystyle a_{i}=\alpha ^{i-1}}$

${\displaystyle a_{1},\dots ,a_{n}=\{1,\alpha ,\alpha ^{2},\dots ,\alpha ^{n-1}\}}$

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

Представление BCH: кодовое слово как последовательность коэффициентов

В этом представлении отправитель снова отображает сообщение ${\displaystyle x}$ к многочлену ${\displaystyle p_{x}}$, и для этого можно использовать любое из двух описанных отображений (где сообщение интерпретируется как коэффициенты ${\displaystyle p_{x}}$ или как исходная последовательность значений ${\displaystyle p_{x}}$). После того, как отправитель построил многочлен ${\displaystyle p_{x}}$ каким-то образом, однако, вместо того, чтобы отправлять ценности из ${\displaystyle p_{x}}$ во всех точках отправитель вычисляет некоторый связанный многочлен ${\displaystyle s}$ степени не более ${\displaystyle n-1}$ для ${\displaystyle n=q-1}$ и отправляет ${\displaystyle n}$ коэффициенты этого полинома. Полином ${\displaystyle s(a)}$ строится путем умножения полинома сообщения ${\displaystyle p_{x}(a)}$, имеющий степень не выше ${\displaystyle k-1}$, с порождающий полином ${\displaystyle g(a)}$ степени ${\displaystyle n-k}$ это известно как отправителю, так и получателю. Образующий полином ${\displaystyle g(x)}$ определяется как многочлен, корни которого в точности ${\displaystyle \alpha ,\alpha ^{2},\dots ,\alpha ^{n-k}}$, т.е.

${\displaystyle g(x)=(x-\alpha )(x-\alpha ^{2})\cdots (x-\alpha ^{n-k})=g_{0}+g_{1}x+\cdots +g_{n-k-1}x^{n-k-1}+x^{n-k}\,.}$

Передатчик отправляет ${\displaystyle n=q-1}$ коэффициенты ${\displaystyle s(a)=p_{x}(a)\cdot g(a)}$. Таким образом, с точки зрения BCH кодов Рида – Соломона множество ${\displaystyle \mathbf {C} }$ кодовых слов определено для ${\displaystyle n=q-1}$ следующим образом:^[9]

${\displaystyle \mathbf {C} =\left\{\left(s_{1},s_{2},\dots ,s_{n}\right)\;{\Big |}\;s(a)=\sum _{i=1}^{n}s_{i}a^{i-1}{\text{ is a polynomial that has at least the roots }}\alpha ^{1},\alpha ^{2},\dots ,\alpha ^{n-k}\right\}\,.}$

Систематическая процедура кодирования

Процедура кодирования для представления кодов Рида – Соломона BCH может быть изменена для получения систематическая процедура кодирования, в котором каждое кодовое слово содержит сообщение в качестве префикса и просто добавляет символы исправления ошибок в качестве суффикса. Здесь вместо отправки ${\displaystyle s(x)=p(x)g(x)}$, кодировщик строит переданный полином ${\displaystyle s(x)}$ такие, что коэффициенты при ${\displaystyle k}$ наибольшие одночлены равны соответствующим коэффициентам при ${\displaystyle p(x)}$, а младшие коэффициенты ${\displaystyle s(x)}$ выбраны именно так, что ${\displaystyle s(x)}$ делится на ${\displaystyle g(x)}$. Тогда коэффициенты при ${\displaystyle p(x)}$ являются подпоследовательностью (а именно префиксом) коэффициентов ${\displaystyle s(x)}$. Чтобы получить в целом систематический код, мы строим полином сообщения ${\displaystyle p(x)}$ интерпретируя сообщение как последовательность его коэффициентов.

Формально построение осуществляется путем умножения ${\displaystyle p(x)}$ от ${\displaystyle x^{t}}$ чтобы освободить место для ${\displaystyle t=n-k}$ отметьте символы, разделив этот продукт на ${\displaystyle g(x)}$ чтобы найти остаток, а затем компенсировать этот остаток путем его вычитания. В ${\displaystyle t}$ контрольные символы создаются путем вычисления остатка ${\displaystyle s_{r}(x)}$:

${\displaystyle s_{r}(x)=p(x)\cdot x^{t}\ {\bmod {\ }}g(x).}$

Остальные имеют степень не выше ${\displaystyle t-1}$, а коэффициенты при ${\displaystyle x^{t-1},x^{t-2},\dots ,x^{1},x^{0}}$ в полиноме ${\displaystyle p(x)\cdot x^{t}}$ равны нулю. Следовательно, следующее определение кодового слова ${\displaystyle s(x)}$ обладает тем свойством, что первые ${\displaystyle k}$ коэффициенты идентичны коэффициентам ${\displaystyle p(x)}$:

${\displaystyle s(x)=p(x)\cdot x^{t}-s_{r}(x)\,.}$

В результате кодовые слова ${\displaystyle s(x)}$ действительно являются элементами ${\displaystyle \mathbf {C} }$, то есть они делятся на порождающий полином ${\displaystyle g(x)}$:^[10]

${\displaystyle s(x)\equiv p(x)\cdot x^{t}-s_{r}(x)\equiv s_{r}(x)-s_{r}(x)\equiv 0\mod g(x)\,.}$

Свойства

Код Рида – Соломона - это [п, k, п − k + 1] код; другими словами, это линейный блочный код длины п (над F) с участием измерение k и минимум Расстояние Хэмминга ${\textstyle d_{\min }=n-k+1.}$ Код Рида – Соломона оптимален в том смысле, что минимальное расстояние имеет максимальное значение, возможное для линейного кода размера (п, k); это известно как Граница синглтона. Такой код еще называют код максимального разделяемого расстояния (MDS).

Исправляющая способность кода Рида – Соломона определяется его минимальным расстоянием или, что эквивалентно, ${\displaystyle n-k}$, мера избыточности в блоке. Если расположение символов ошибки заранее не известно, то код Рида – Соломона может исправить до ${\displaystyle (n-k)/2}$ ошибочные символы, то есть он может исправить вдвое меньше ошибок, чем добавлено избыточных символов в блок. Иногда места ошибок известны заранее (например, "дополнительная информация" в демодулятор отношения сигнал / шум ) - они называются стирания. Код Рида – Соломона (как и любой Код MDS ) может исправить вдвое больше стираний, чем ошибок, и любую комбинацию ошибок и стираний можно исправить до тех пор, пока соотношение 2E + S ≤ п − k удовлетворено, где ${\displaystyle E}$ количество ошибок и ${\displaystyle S}$ - количество стираний в блоке.

Теоретическая производительность BER кода Рида-Соломона (N = 255, K = 233, QPSK, AWGN). Ступенчатая характеристика.

Теоретическая граница ошибки может быть описана следующей формулой для AWGN канал для ФСК:^[11]

${\displaystyle P_{b}\approx {\frac {2^{m-1}}{2^{m}-1}}{\frac {1}{n}}\sum _{\ell =t+1}^{n}\ell {n \choose \ell }P_{s}^{\ell }(1-P_{s})^{n-\ell }}$

и для других схем модуляции:

${\displaystyle P_{b}\approx {\frac {1}{m}}{\frac {1}{n}}\sum _{\ell =t+1}^{n}\ell {n \choose \ell }P_{s}^{\ell }(1-P_{s})^{n-\ell }}$

где ${\displaystyle t={\frac {1}{2}}(d_{\min }-1)}$, ${\displaystyle P_{s}=1-(1-s)^{h}}$, ${\displaystyle h={\frac {m}{\log _{2}M}}}$, ${\displaystyle s}$ - частота ошибок символа в случае некодированного AWGN и ${\displaystyle M}$ - порядок модуляции.

Для практического использования кодов Рида – Соломона обычно используется конечное поле ${\displaystyle F}$ с участием ${\displaystyle 2^{m}}$ элементы. В этом случае каждый символ может быть представлен как ${\displaystyle m}$-битовое значение. Отправитель отправляет точки данных как закодированные блоки, и количество символов в закодированном блоке равно ${\displaystyle n=2^{m}-1}$. Таким образом, код Рида – Соломона, работающий с 8-битными символами, имеет ${\displaystyle n=2^{8}-1=255}$ символов на блок. (Это очень популярное значение из-за преобладания байтовый компьютерные системы.) Количество ${\displaystyle k}$, с участием ${\displaystyle k<n}$, из данные символы в блоке - это параметр дизайна. Часто используемый код кодирует ${\displaystyle k=223}$ восьмибитовых символов данных плюс 32 восьмибитовых символа четности в ${\displaystyle n=255}$-символьный блок; это обозначается как ${\displaystyle (n,k)=(255,223)}$ код и способен исправлять до 16 ошибок символов в блоке.

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

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

Является ли код Рида – Соломона циклический или нет, зависит от тонких деталей конструкции. В исходной точке зрения Рида и Соломона, где кодовые слова являются значениями полинома, можно выбрать последовательность точек оценки таким образом, чтобы сделать код циклическим. В частности, если ${\displaystyle \alpha }$ это первобытный корень поля ${\displaystyle F}$, то по определению все ненулевые элементы ${\displaystyle F}$ принять форму ${\displaystyle \alpha ^{i}}$ для ${\displaystyle i\in \{1,\dots ,q-1\}}$, где ${\displaystyle q=|F|}$. Каждый полином ${\displaystyle p}$ над ${\displaystyle F}$ дает начало кодовое слово ${\displaystyle (p(\alpha ^{1}),\dots ,p(\alpha ^{q-1}))}$. Поскольку функция ${\displaystyle a\mapsto p(\alpha a)}$ также является многочленом той же степени, эта функция дает кодовое слово ${\displaystyle (p(\alpha ^{2}),\dots ,p(\alpha ^{q}))}$; поскольку ${\displaystyle \alpha ^{q}=\alpha ^{1}}$ это кодовое слово циклический сдвиг влево исходного кодового слова, полученного из ${\displaystyle p}$. Таким образом, выбор последовательности примитивных корневых степеней в качестве точек оценки делает исходный вид кода Рида – Соломона циклический. Коды Рида – Соломона в представлении BCH всегда циклические, потому что Коды BCH циклические.

Замечания

От разработчиков не требуется использовать «естественные» размеры блоков кода Рида – Соломона. Метод, известный как «сокращение», может производить меньший код любого желаемого размера из большего кода. Например, широко используемый код (255,223) можно преобразовать в код (160,128), добавив в неиспользуемую часть исходного блока 95 двоичных нулей и не передав их. В декодере эта же часть блока загружается локально двоичными нулями. Дельсарт-Гёталь-Зайдель^[12] Теорема иллюстрирует пример применения сокращенных кодов Рида – Соломона. Параллельно с сокращением используется метод, известный как прокалывание позволяет опустить некоторые закодированные символы четности.

Декодеры просмотра BCH

Декодеры, описанные в этом разделе, используют представление BCH кодового слова как последовательности коэффициентов. В них используется фиксированный полином генератора, известный как кодировщику, так и декодеру.

Декодер Петерсона – Горенштейна – Цирлера

Основная статья: Алгоритм Петерсона – Горенштейна – Цирлера

Дэниел Горенштейн и Нил Цирлер разработали декодер, который был описан Цирлером в отчете лаборатории Линкольна Массачусетского технологического института в январе 1960 года, а затем в статье в июне 1961 года.^[13] Декодер Горенштейна – Цирлера и связанные с ним работы по кодам BCH описаны в книге. Коды исправления ошибок от В. Уэсли Петерсон (1961).^[14]

Формулировка

Переданное сообщение, ${\displaystyle (c_{0},\ldots ,c_{i},\ldots ,c_{n-1})}$, рассматривается как коэффициенты полинома s(Икс):

${\displaystyle s(x)=\sum _{i=0}^{n-1}c_{i}x^{i}}$

В результате процедуры кодирования Рида-Соломона, s(Икс) делится на порождающий полином г(Икс):

${\displaystyle g(x)=\prod _{j=1}^{n-k}(x-\alpha ^{j}),}$

где α первобытный корень.

поскольку s(Икс) кратна образующей г(Икс), то он "наследует" все свои корни:

${\displaystyle s(\alpha ^{j})=0,\ j=1,2,\ldots ,n-k}$

Переданный полином искажается при передаче полиномом ошибки е(Икс) для получения полученного многочлена р(Икс).

${\displaystyle r(x)=s(x)+e(x)}$

${\displaystyle e(x)=\sum _{i=0}^{n-1}e_{i}x^{i}}$

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

${\displaystyle e(x)=\sum _{k=1}^{\nu }e_{i_{k}}x^{i_{k}}}$

Задача декодера - найти количество ошибок (ν), положения ошибок (я_k), а значения ошибок в этих положениях (е_яk). От тех, е(Икс) можно вычислить и вычесть из р(Икс), чтобы получить изначально отправленное сообщение s(Икс).

Расшифровка синдрома

Декодер начинает с оценки полинома, полученного в определенных точках. Мы называем результаты этой оценки «синдромами», S_j. Они определяются как:

${\displaystyle {\begin{aligned}S_{j}&=r(\alpha ^{j})=s(\alpha ^{j})+e(\alpha ^{j})=0+e(\alpha ^{j})=e(\alpha ^{j}),\ j=1,2,\ldots ,n-k\\&=\sum _{k=1}^{\nu }e_{i_{k}}\left(\alpha ^{j}\right)^{i_{k}}\end{aligned}}}$

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

Локаторы ошибок и значения ошибок

Для удобства определим локаторы ошибок Икс_k и значения ошибок Y_k так как:

${\displaystyle X_{k}=\alpha ^{i_{k}},\ Y_{k}=e_{i_{k}}}$

Тогда синдромы могут быть записаны в терминах этих локаторов ошибок и значений ошибок как

${\displaystyle S_{j}=\sum _{k=1}^{\nu }Y_{k}X_{k}^{j}}$

Это определение значений синдрома эквивалентно предыдущему, поскольку ${\displaystyle (\alpha ^{j})^{i_{k}}=\alpha ^{j*i_{k}}=(\alpha ^{i_{k}})^{j}=X_{k}^{j}}$.

Синдромы дают систему п − k ≥ 2ν уравнения в 2ν неизвестных, но эта система уравнений нелинейна в Икс_k и не имеет очевидного решения. Однако если Икс_k были известны (см. ниже), то синдромные уравнения представляют собой линейную систему уравнений, которую легко решить для Y_k значения ошибок.

${\displaystyle {\begin{bmatrix}X_{1}^{1}&X_{2}^{1}&\cdots &X_{\nu }^{1}\\X_{1}^{2}&X_{2}^{2}&\cdots &X_{\nu }^{2}\\\vdots &\vdots &&\vdots \\X_{1}^{n-k}&X_{2}^{n-k}&\cdots &X_{\nu }^{n-k}\\\end{bmatrix}}{\begin{bmatrix}Y_{1}\\Y_{2}\\\vdots \\Y_{\nu }\end{bmatrix}}={\begin{bmatrix}S_{1}\\S_{2}\\\vdots \\S_{n-k}\end{bmatrix}}}$

Следовательно, проблема заключается в поиске Икс_k, потому что тогда была бы известна самая левая матрица, и обе части уравнения можно было бы умножить на ее обратную, давая Y_k

В варианте этого алгоритма, где места ошибок уже известны (когда он используется как код стирания ), это конец. Расположение ошибок (Икс_k) уже известны каким-либо другим методом (например, в FM-передаче участки, где битовый поток был нечетким или преодолен помехами, можно определить с помощью частотного анализа с вероятностью). В этом сценарии до ${\displaystyle n-k}$ ошибки можно исправить.

Остальная часть алгоритма служит для поиска ошибок и потребует значений синдрома до ${\displaystyle 2v}$, а не просто ${\displaystyle v}$ используется до сих пор. Вот почему необходимо добавить в 2 раза больше символов исправления ошибок, чем можно исправить, не зная их местоположения.

Полином локатора ошибок

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

Определить многочлен локатора ошибок Λ (Икс) так как

${\displaystyle \Lambda (x)=\prod _{k=1}^{\nu }(1-xX_{k})=1+\Lambda _{1}x^{1}+\Lambda _{2}x^{2}+\cdots +\Lambda _{\nu }x^{\nu }}$

Нули Λ (Икс) являются обратными ${\displaystyle X_{k}^{-1}}$. Это следует из приведенной выше конструкции обозначения произведения, поскольку если ${\displaystyle x=X_{k}^{-1}}$ тогда один из умноженных членов будет равен нулю ${\displaystyle (1-X_{k}^{-1}\cdot X_{k})=1-1=0}$, что приводит к нулевому значению всего полинома.

${\displaystyle \Lambda (X_{k}^{-1})=0}$

Позволять ${\displaystyle j}$ быть любым целым таким, что ${\displaystyle 1\leq j\leq \nu }$. Умножьте обе стороны на ${\displaystyle Y_{k}X_{k}^{j+\nu }}$ и все равно будет ноль.

${\displaystyle {\begin{aligned}&Y_{k}X_{k}^{j+\nu }\Lambda (X_{k}^{-1})=0.\\&Y_{k}X_{k}^{j+\nu }(1+\Lambda _{1}X_{k}^{-1}+\Lambda _{2}X_{k}^{-2}+\cdots +\Lambda _{\nu }X_{k}^{-\nu })=0.\\&Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu }X_{k}^{-1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu }X_{k}^{-2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j+\nu }X_{k}^{-\nu }=0.\\&Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j}=0.\\\end{aligned}}}$

Сумма за k = От 1 до ν и все равно будет ноль.

${\displaystyle {\begin{aligned}&\sum _{k=1}^{\nu }\left(Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j}\right)=0\\\end{aligned}}}$

Соберите каждый член в отдельную сумму.

${\displaystyle {\begin{aligned}&\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu }\right)+\left(\sum _{k=1}^{\nu }\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}\right)+\left(\sum _{k=1}^{\nu }\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}\right)+\cdots +\left(\sum _{k=1}^{\nu }\Lambda _{\nu }Y_{k}X_{k}^{j}\right)=0\end{aligned}}}$

Извлеките постоянные значения ${\displaystyle \Lambda }$ на которые суммирование не влияет.

${\displaystyle {\begin{aligned}&\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu }\right)+\Lambda _{1}\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu -1}\right)+\Lambda _{2}\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu -2}\right)+\cdots +\Lambda _{\nu }\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j}\right)=0\end{aligned}}}$

Эти суммы теперь эквивалентны значениям синдромов, которые мы знаем и можем подставить! Следовательно, это сводится к

${\displaystyle S_{j+\nu }+\Lambda _{1}S_{j+\nu -1}+\cdots +\Lambda _{\nu -1}S_{j+1}+\Lambda _{\nu }S_{j}=0\,}$

Вычитание ${\displaystyle S_{j+\nu }}$ с обеих сторон дает

${\displaystyle S_{j}\Lambda _{\nu }+S_{j+1}\Lambda _{\nu -1}+\cdots +S_{j+\nu -1}\Lambda _{1}=-S_{j+\nu }\ }$

Напомним, что j было выбрано любое целое число от 1 до v включительно, и эта эквивалентность верна для любых без исключения таких значений. Следовательно, мы имеем v линейные уравнения, а не одно. Таким образом, эта система линейных уравнений может быть решена относительно коэффициентов Λ_я полинома определения места ошибки:

${\displaystyle {\begin{bmatrix}S_{1}&S_{2}&\cdots &S_{\nu }\\S_{2}&S_{3}&\cdots &S_{\nu +1}\\\vdots &\vdots &&\vdots \\S_{\nu }&S_{\nu +1}&\cdots &S_{2\nu -1}\end{bmatrix}}{\begin{bmatrix}\Lambda _{\nu }\\\Lambda _{\nu -1}\\\vdots \\\Lambda _{1}\end{bmatrix}}={\begin{bmatrix}-S_{\nu +1}\\-S_{\nu +2}\\\vdots \\-S_{\nu +\nu }\end{bmatrix}}}$

Вышесказанное предполагает, что декодер знает количество ошибок. ν, но это количество еще не определено. Декодер PGZ не определяет ν напрямую, а скорее ищет его, пробуя последовательные значения. Декодер сначала принимает наибольшее значение для пробной версии. ν и устанавливает линейную систему для этого значения. Если уравнения могут быть решены (т. Е. Определитель матрицы отличен от нуля), то пробным значением является количество ошибок. Если линейная система не может быть решена, то испытание ν сокращается на единицу и исследуется следующая меньшая система. (Гилл н.д., п. 35)

Найдите корни полинома локатора ошибок

Используйте коэффициенты Λ_я найденный на последнем шаге для построения полинома местоположения ошибки. Корни полинома определения местоположения ошибки могут быть найдены путем исчерпывающего поиска. Локаторы ошибок Икс_k являются обратными этим корням. Порядок коэффициентов полинома определения ошибки может быть изменен на обратный, и в этом случае корни этого обратного полинома являются локаторами ошибок. ${\displaystyle X_{k}}$ (не их обратные ${\displaystyle X_{k}^{-1}}$). Чиен поиск - эффективная реализация этого шага.

Рассчитайте значения ошибок

Как только локаторы ошибок Икс_k известны, значения ошибок могут быть определены. Это можно сделать прямым решением для Y_k в уравнения ошибок матрицу, приведенную выше, или используя Алгоритм Форни.

Рассчитайте места ошибок

Рассчитать я_k взяв базу журнала ${\displaystyle \alpha }$ из Икс_k. Обычно это делается с помощью предварительно вычисленной таблицы поиска.

Исправьте ошибки

Наконец, e (x) генерируется из я_k и е_яk а затем вычитается из r (x), чтобы получить первоначально отправленное сообщение s (x) с исправленными ошибками.

пример

Рассмотрим код Рида – Соломона, определенный в GF(929) с участием α = 3 и т = 4 (это используется в PDF417 штрих-коды) для кода RS (7,3). Генераторный полином равен

${\displaystyle g(x)=(x-3)(x-3^{2})(x-3^{3})(x-3^{4})=x^{4}+809x^{3}+723x^{2}+568x+522}$

Если полином сообщения п(Икс) = 3 Икс² + 2 Икс + 1, то систематическое кодовое слово кодируется следующим образом.

${\displaystyle s_{r}(x)=p(x)\,x^{t}\mod g(x)=547x^{3}+738x^{2}+442x+455}$

${\displaystyle s(x)=p(x)\,x^{t}-s_{r}(x)=3x^{6}+2x^{5}+1x^{4}+382x^{3}+191x^{2}+487x+474}$

Ошибки при передаче могут привести к получению этого сообщения.

${\displaystyle r(x)=s(x)+e(x)=3x^{6}+2x^{5}+123x^{4}+456x^{3}+191x^{2}+487x+474}$

Синдромы рассчитываются путем оценки р во власти α.

${\displaystyle S_{1}=r(3^{1})=3\cdot 3^{6}+2\cdot 3^{5}+123\cdot 3^{4}+456\cdot 3^{3}+191\cdot 3^{2}+487\cdot 3+474=732}$

${\displaystyle S_{2}=r(3^{2})=637,\;S_{3}=r(3^{3})=762,\;S_{4}=r(3^{4})=925}$

${\displaystyle {\begin{bmatrix}732&637\\637&762\end{bmatrix}}{\begin{bmatrix}\Lambda _{2}\\\Lambda _{1}\end{bmatrix}}={\begin{bmatrix}-762\\-925\end{bmatrix}}={\begin{bmatrix}167\\004\end{bmatrix}}}$

С помощью Гауссово исключение:

${\displaystyle {\begin{bmatrix}001&000\\000&001\end{bmatrix}}{\begin{bmatrix}\Lambda _{2}\\\Lambda _{1}\end{bmatrix}}={\begin{bmatrix}329\\821\end{bmatrix}}}$

Λ (х) = 329 х² + 821 x + 001, с корнями x₁ = 757 = 3⁻³ и х₂ = 562 = 3⁻⁴

Коэффициенты можно поменять местами, чтобы получить корни с положительными показателями, но обычно это не используется:

R (х) = 001 х² + 821 x + 329, с корнями 27 = 3³ и 81 = 3⁴

с журналом корней, соответствующим местоположениям ошибок (справа налево, ячейка 0 - это последний член в кодовом слове).

Чтобы вычислить значения ошибок, примените Алгоритм Форни.

Ω (x) = S (x) Λ (x) mod x⁴ = 546 х + 732

Λ '(х) = 658 х + 821

е₁ = −Ω (x₁) / Λ '(x₁) = 074

е₂ = −Ω (x₂) / Λ '(x₂) = 122

Вычитание е₁ Икс³ и е₂ Икс⁴ от полученного многочлена р воспроизводит исходное кодовое слово s.

Декодер Берлекампа – Месси

В Алгоритм Берлекампа-Месси является альтернативной итерационной процедурой поиска полинома локатора ошибок.Во время каждой итерации он вычисляет несоответствие на основе текущего экземпляра Λ (x) с предполагаемым количеством ошибок. е:

${\displaystyle \Delta =S_{i}+\Lambda _{1}\ S_{i-1}+\cdots +\Lambda _{e}\ S_{i-e}}$

а затем регулирует Λ (Икс) и е так что пересчитанное Δ будет равно нулю. Статья Алгоритм Берлекампа-Месси есть подробное описание процедуры. В следующем примере C(Икс) используется для представления Λ (Икс).

пример

Используя те же данные, что и в приведенном выше примере Peterson Gorenstein Zierler:

п	Sп+1	d	C	B	б	м
0	732	732	197 Икс + 1	1	732	1
1	637	846	173 Икс + 1	1	732	2
2	762	412	634 Икс^2 + 173 Икс + 1	173 Икс + 1	412	1
3	925	576	329 Икс^2 + 821 Икс + 1	173 Икс + 1	412	2

Окончательное значение C - многочлен локатора ошибок, Λ (Икс).

Евклидов декодер

Другой итерационный метод вычисления как полинома локатора ошибок, так и полинома значения ошибки основан на адаптации Сугиямы расширенный алгоритм Евклида .

Определим S (x), Λ (x) и Ω (x) для т синдромы и е ошибки:

${\displaystyle S(x)=S_{t}x^{t-1}+S_{t-1}x^{t-2}+\cdots +S_{2}x+S_{1}}$

${\displaystyle \Lambda (x)=\Lambda _{e}x^{e}+\Lambda _{e-1}x^{e-1}+\cdots +\Lambda _{1}x+1}$

${\displaystyle \Omega (x)=\Omega _{e}x^{e}+\Omega _{e-1}x^{e-1}+\cdots +\Omega _{1}x+\Omega _{0}}$

Ключевое уравнение:

${\displaystyle \Lambda (x)S(x)=Q(x)x^{t}+\Omega (x)}$

Для т = 6 и е = 3:

${\displaystyle {\begin{bmatrix}\Lambda _{3}S_{6}&x^{8}\\\Lambda _{2}S_{6}+\Lambda _{3}S_{5}&x^{7}\\\Lambda _{1}S_{6}+\Lambda _{2}S_{5}+\Lambda _{3}S_{4}&x^{6}\\S_{6}+\Lambda _{1}S_{5}+\Lambda _{2}S_{4}+\Lambda _{3}S_{3}&x^{5}\\S_{5}+\Lambda _{1}S_{4}+\Lambda _{2}S_{3}+\Lambda _{3}S_{2}&x^{4}\\S_{4}+\Lambda _{1}S_{3}+\Lambda _{2}S_{2}+\Lambda _{3}S_{1}&x^{3}\\S_{3}+\Lambda _{1}S_{2}+\Lambda _{2}S_{1}&x^{2}\\S_{2}+\Lambda _{1}S_{1}&x\\S_{1}\end{bmatrix}}={\begin{bmatrix}Q_{2}x^{8}\\Q_{1}x^{7}\\Q_{0}x^{6}\\0\\0\\0\\\Omega _{2}x^{2}\\\Omega _{1}x\\\Omega _{0}\end{bmatrix}}}$

Средние члены равны нулю из-за связи между Λ и синдромами.

Расширенный алгоритм Евклида может найти серию многочленов вида

А_я(Икс) S(Икс) + B_я(Икс) Икс^т = р_я(Икс)

где степень р уменьшается как я увеличивается. Однажды степень р_я(Икс) < т/ 2, то

А_я(х) = Λ (х)

B_я(х) = −Q (х)

р_я(х) = Ω (х).

B (x) и Q (x) не нужно сохранять, поэтому алгоритм становится:

р₋₁ = х^т

р₀ = S (х)

А₋₁ = 0

А₀ = 1

я = 0

а степень R_я ≥ т / 2

я = я + 1

Q = R_i-2 / Р_я-1

р_я = R_i-2 - Q R_я-1

А_я = А_i-2 - Q A_я-1

чтобы установить младший член Λ (x) равным 1, разделите Λ (x) и Ω (x) на A_я(0):

Λ (х) = А_я / А_я(0)

Ω (x) = R_я / А_я(0)

А_я(0) - постоянный член (младшего порядка) A_я.

пример

Используя те же данные, что и в приведенном выше примере Петерсона – Горенштейна – Цирлера:

я	ря	Ая
−1	001 х^4 + 000 х^3 + 000 х^2 + 000 х + 000	000
0	925 х^3 + 762 х^2 + 637 х + 732	001
1	683 х^2 + 676 х + 024	697 х + 396
2	673 х + 596	608 х^2 + 704 х + 544

Λ (х) = А₂ / 544 = 329 х² + 821 х + 001

Ω (x) = R₂ / 544 = 546 х + 732

Декодер с использованием дискретного преобразования Фурье

Для декодирования можно использовать дискретное преобразование Фурье.^[15] Чтобы избежать конфликта с названиями синдромов, позвольте c(Икс) = s(Икс) закодированное кодовое слово. р(Икс) и е(Икс) такие же, как указано выше. Определить C(Икс), E(Икс), и р(Икс) как дискретные преобразования Фурье c(Икс), е(Икс), и р(Икс). поскольку р(Икс) = c(Икс) + е(Икс), и поскольку дискретное преобразование Фурье является линейным оператором, р(Икс) = C(Икс) + E(Икс).

Преобразовать р(Икс) к р(Икс) с помощью дискретного преобразования Фурье. Поскольку расчет для дискретного преобразования Фурье такой же, как расчет для синдромов, т коэффициенты р(Икс) и E(Икс) такие же, как синдромы:

${\displaystyle R_{j}=E_{j}=S_{j}=r(\alpha ^{j})}$

${\displaystyle {\text{for }}1\leq j\leq t}$

Использовать ${\displaystyle R_{1}}$ через ${\displaystyle R_{t}}$ как синдромы (они такие же) и сгенерировать полином локатора ошибок, используя методы любого из вышеперечисленных декодеров.

Пусть v = количество ошибок. Сгенерируйте E (x), используя известные коэффициенты ${\displaystyle E_{1}}$ к ${\displaystyle E_{t}}$, полином локатора ошибок, и эти формулы

${\displaystyle E_{0}=-{\frac {1}{\Lambda _{v}}}(E_{v}+\Lambda _{1}E_{v-1}+\cdots +\Lambda _{v-1}E_{1})}$

${\displaystyle E_{j}=-(\Lambda _{1}E_{j-1}+\Lambda _{2}E_{j-2}+\cdots +\Lambda _{v}E_{j-v})}$

${\displaystyle {\text{for }}t<j<n}$

Затем вычислите C(Икс) = р(Икс) − E(Икс) и обратное преобразование (полиномиальная интерполяция) C(Икс) производить c(Икс).

Декодирование за пределами исправления ошибок

В Граница синглтона заявляет, что минимальное расстояние d линейного блочного кода размером (п,k) ограничена сверху п − k + 1. Расстояние d обычно понималось, что возможность исправления ошибок ограничивается ⌊d/ 2⌋. Код Рида – Соломона достигает этой границы с равенством и, таким образом, может исправлять до (п − k + 1) / 2⌋ ошибок. Однако этот предел исправления ошибок не точен.

В 1999 году, Мадху Судан и Венкатесан Гурусвами в Массачусетском технологическом институте опубликовал «Улучшенное декодирование кодов Рида – Соломона и алгебраической геометрии», в котором представлен алгоритм, позволяющий исправлять ошибки, превышающие половину минимального расстояния кода.^[16] Это относится к кодам Рида – Соломона и в более общем смысле к алгебро-геометрические коды. Этот алгоритм создает список кодовых слов (это список-декодирование алгоритм) и основан на интерполяции и факторизации многочленов по ${\displaystyle GF(2^{m})}$ и его расширения.

Мягкое декодирование

Алгебраические методы декодирования, описанные выше, являются методами жесткого решения, что означает, что для каждого символа принимается жесткое решение о его значении. Например, декодер может связать с каждым символом дополнительное значение, соответствующее каналу. демодулятор уверенность в правильности обозначения. Появление LDPC и турбокоды, которые используют повторяющиеся мягкое решение методы декодирования распространения убеждений для достижения производительности исправления ошибок, близкой к теоретический предел, вызвало интерес к применению декодирования с мягким решением к обычным алгебраическим кодам. В 2003 году Ральф Кёттер и Александр Варди представил алгоритм полиномиального алгебраического декодирования списков с мягким решением для кодов Рида – Соломона, который был основан на работе Судана и Гурусвами.^[17]В 2016 году Стивен Дж. Франке и Джозеф Х. Тейлор опубликовали новый декодер с мягким решением.^[18]

Пример Matlab

Кодировщик

Здесь мы представляем простую реализацию Matlab для кодировщика.

функция[закодировано] =rsEncoder(msg, m, prim_poly, n, k)% RSENCODER Кодировать сообщение с помощью алгоритма Рида-Соломона    % m - количество бит на символ    % prim_poly: Примитивный многочлен p (x). Т.е. для DM - 301    % k - размер сообщения    % n - общий размер (k + избыточный)    % Пример: msg = uint8 ('Тест')    % enc_msg = rsEncoder (сообщение, 8, 301, 12, число (сообщение));     % Получить альфа    альфа = gf(2, м, prim_poly);     % Получите порождающий многочлен Рида-Соломона g (x)    g_x = генполия(k, п, альфа);     % Умножьте информацию на X ^ (n-k) или просто добавьте нули в конце, чтобы    % получить место для добавления избыточной информации    msg_padded = gf([сообщение нули(1, п - k)], м, prim_poly);     % Получить остаток от деления расширенного сообщения на    % Порождающий многочлен Рида-Соломона g (x)    [~, остаток] = деконв(msg_padded, g_x);     % Теперь верните сообщение с избыточной информацией    закодированный = msg_padded - остаток;конец% Найдите порождающий многочлен Рида-Соломона g (x), между прочим, это% то же, что и функция rsgenpoly в Matlabфункцияг =генполия(k, n, альфа)г = 1;    % Умножение на поле Галуа - это просто свертка    для k = mod (1: n - k, n)        г = Конв(г, [1 альфа .^ (k)]);    конецконец

Декодер

Теперь расшифровка:

функция[декодировано, error_pos, error_mag, g, S] =rsDecoder(закодировано, m, prim_poly, n, k)% RSDECODER Расшифровать сообщение, закодированное Ридом-Соломоном    %   Пример:    % [dec, ​​~, ~, ~, ~] = rsDecoder (enc_msg, 8, 301, 12, numel (сообщение))    max_errors = этаж((п - k) / 2);    orig_val = закодированный.Икс;    % Инициализировать вектор ошибки    ошибки = нули(1, п);    г = [];    S = [];     % Получить альфа    альфа = gf(2, м, prim_poly);     % Найдите синдромы (проверьте, не разбивает ли сообщение генератор    % полином результат равен нулю)    Synd = поливал(закодированный, альфа .^ (1:п - k));    Синдромы = отделка(Synd);     % Если все синдромы нулевые (полностью делимые), ошибок нет    если пусто (Syndromes.x)        расшифрованный = orig_val(1:k);        error_pos = [];        error_mag = [];        г = [];        S = Synd;        вернуть;    конец% Подготовьтесь к эвклидовому алгоритму (используется для поиска ошибки    % полиномов)    r0 = [1, нули(1, 2 * max_errors)]; r0 = gf(r0, м, prim_poly); r0 = отделка(r0);    size_r0 = длина(r0);    r1 = Синдромы;    f0 = gf([нули(1, size_r0 - 1) 1], м, prim_poly);    f1 = gf(нули(1, size_r0), м, prim_poly);    g0 = f1; g1 = f0;     % Выполните алгоритм Евклида на многочленах r0 (x) и Syndromes (x) в    %, чтобы найти многочлен обнаружения ошибки    в то время как правда        % Сделайте длинное деление        [частное, остаток] = деконв(r0, r1);        % Добавьте нули        частное = подушечка(частное, длина(g1));             % Найти частное * g1 и дополнить        c = Конв(частное, g1);        c = отделка(c);        c = подушечка(c, длина(g0));             % Обновить g как коэффициент g0 * g1        г = g0 - c;             % Проверить, меньше ли степень остатка (x) max_errors        если все (остаток (1: конец - max_errors) == 0)            перерыв;        конец% Обновить r0, r1, g0, g1 и удалить ведущие нули        r0 = отделка(r1); r1 = отделка(остаток);        g0 = g1; g1 = г;    конец% Удалить ведущие нули    г = отделка(г);     % Найдите нули полинома ошибок на этом поле Галуа    evalPoly = поливал(г, альфа .^ (п - 1 : - 1 : 0));    error_pos = gf(найти(evalPoly == 0), м);     % Если ошибочной позиции не обнаружено, мы возвращаем полученную работу, потому что    % по сути это ничего, что мы могли бы сделать и возвращаем полученное сообщение    если isempty (error_pos)        расшифрованный = orig_val(1:k);        error_mag = [];        вернуть;    конец% Подготовьте линейную систему для решения полинома ошибок и нахождения ошибки    % величины    size_error = длина(error_pos);    Синдром_Вальс = Синдромы.Икс;    б(:, 1) = Синдром_Вальс(1:size_error);    для idx = 1: size_error        е = альфа .^ (idx * (п - error_pos.Икс));        ошибаться = е.Икс;        э(idx, :) = ошибаться;    конец% Решите линейную систему    error_mag = (gf(э, м, prim_poly) \ gf(б, м, prim_poly))';    % Поместите величину ошибки в вектор ошибки    ошибки(error_pos.Икс) = error_mag.Икс;    % Принесите этот вектор в поле галуа    errors_gf = gf(ошибки, м, prim_poly);     % Теперь, чтобы исправить ошибки, просто добавьте закодированный код    decoded_gf = закодированный(1:k) + errors_gf(1:k);    расшифрованный = decoded_gf.Икс;конец% Удалить ведущие нули из массива Галуафункцияgt =отделка(г)gx = г.Икс;    gt = gf(gx(найти(gx, 1) : конец), г.м, г.prim_poly);конец% Добавить ведущие нулифункцияxpad =подушечка(х, к)len = длина(Икс);    если (len < k)        xpad = [нули(1, k - len) Икс];    конецконец

Оригинальные декодеры вида Рида Соломона

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

Теоретический декодер

Рид и Соломон (1960) описал теоретический декодер, который исправляет ошибки, находя самый популярный полином сообщений. Декодер знает только набор значений ${\displaystyle a_{1}}$ к ${\displaystyle a_{n}}$ и какой метод кодирования использовался для генерации последовательности значений кодового слова. Исходное сообщение, многочлен и любые ошибки неизвестны. Процедура декодирования может использовать такой метод, как интерполяция Лагранжа на различных подмножествах из n значений кодового слова, взятых k за раз, для многократного создания потенциальных многочленов, пока не будет создано достаточное количество совпадающих многочленов, чтобы разумно устранить любые ошибки в полученном кодовом слове. После определения полинома любые ошибки в кодовом слове можно исправить путем повторного вычисления соответствующих значений кодового слова. К сожалению, во всех случаях, кроме самых простых, существует слишком много подмножеств, поэтому алгоритм непрактичен. Количество подмножеств - это биномиальный коэффициент, ${\displaystyle \textstyle {\binom {n}{k}}={n! \over (n-k)!k!}}$, а количество подмножеств невозможно даже для скромных кодов. Для ${\displaystyle (255,249)}$ код, который может исправить 3 ошибки, наивный теоретический декодер проверил бы 359 миллиардов подмножеств.

Декодер Berlekamp Welch

В 1986 году декодер, известный как Алгоритм Берлекампа – Велча был разработан как декодер, который может восстанавливать исходный полином сообщения, а также полином «локатора» ошибок, который производит нули для входных значений, соответствующих ошибкам, с временной сложностью O (n ^ 3), где n - число значений в сообщении. Восстановленный многочлен затем используется для восстановления (при необходимости пересчета) исходного сообщения.

пример

Используя RS (7,3), GF (929) и набор точек оценки а_я = я − 1

а = {0, 1, 2, 3, 4, 5, 6}

Если полином сообщения

п(Икс) = 003 Икс² + 002 Икс + 001

Кодовое слово

c = {001, 006, 017, 034, 057, 086, 121}

Ошибки при передаче могут привести к получению этого сообщения.

б = c + е = {001, 006, 123, 456, 057, 086, 121}

Ключевые уравнения:

${\displaystyle b_{i}E(a_{i})-Q(a_{i})=0}$

Предположим максимальное количество ошибок: е = 2. Ключевые уравнения становятся:

${\displaystyle b_{i}(e_{0}+e_{1}a_{i})-(q_{0}+q_{1}a_{i}+q_{2}a_{i}^{2}+q_{3}a_{i}^{3}+q_{4}a_{i}^{4})=-b_{i}a_{i}^{2}}$

${\displaystyle {\begin{bmatrix}001&000&928&000&000&000&000\\006&006&928&928&928&928&928\\123&246&928&927&925&921&913\\456&439&928&926&920&902&848\\057&228&928&925&913&865&673\\086&430&928&924&904&804&304\\121&726&928&923&893&713&562\end{bmatrix}}{\begin{bmatrix}e_{0}\\e_{1}\\q_{0}\\q_{1}\\q_{2}\\q_{3}\\q_{4}\end{bmatrix}}={\begin{bmatrix}000\\923\\437\\541\\017\\637\\289\end{bmatrix}}}$

С помощью Гауссово исключение:

${\displaystyle {\begin{bmatrix}001&000&000&000&000&000&000\\000&001&000&000&000&000&000\\000&000&001&000&000&000&000\\000&000&000&001&000&000&000\\000&000&000&000&001&000&000\\000&000&000&000&000&001&000\\000&000&000&000&000&000&001\end{bmatrix}}{\begin{bmatrix}e_{0}\\e_{1}\\q_{0}\\q_{1}\\q_{2}\\q_{3}\\q_{4}\end{bmatrix}}={\begin{bmatrix}006\\924\\006\\007\\009\\916\\003\end{bmatrix}}}$

Q(Икс) = 003 Икс⁴ + 916 Икс³ + 009 Икс² + 007 Икс + 006

E(Икс) = 001 Икс² + 924 Икс + 006

Q(Икс) / E(Икс) = п(Икс) = 003 Икс² + 002 Икс + 001

Пересчитать Р (х) где E (x) = 0: {2, 3} исправлять б в результате получено исправленное кодовое слово:

c = {001, 006, 017, 034, 057, 086, 121}

Декодер гао

В 2002 году Шухонг Гао разработал улучшенный декодер на основе расширенного алгоритма Евклида. Gao_RS.pdf .

пример

Используя те же данные, что и в приведенном выше примере Берлекампа Велча:

${\displaystyle R_{-1}=\prod _{i=1}^{n}(x-a_{i})}$

${\displaystyle R_{0}=}$ Интерполяция Лагранжа ${\displaystyle \{a_{i},b(a_{i})\}}$ для я = От 1 до п

${\displaystyle A_{-1}=0}$

${\displaystyle A_{0}=1}$

я	ря	Ая
−1	001 х^7 + 908 х^6 + 175 х^5 + 194 х^4 + 695 х^3 + 094 х^2 + 720 х + 000	000
0	055 х^6 + 440 х^5 + 497 х^4 + 904 х^3 + 424 х^2 + 472 х + 001	001
1	702 х^5 + 845 х^4 + 691 х^3 + 461 х^2 + 327 х + 237	152 х + 237
2	266 х^4 + 086 х^3 + 798 х^2 + 311 х + 532	708 х^2 + 176 х + 532

Q(Икс) = р₂ = 266 Икс⁴ + 086 Икс³ + 798 Икс² + 311 Икс + 532

E(Икс) = А₂ = 708 Икс² + 176 Икс + 532

делить Q(x) и E(x) по старшему коэффициенту при E(x) = 708. (Необязательно)

Q(Икс) = 003 Икс⁴ + 916 Икс³ + 009 Икс² + 007 Икс + 006

E(Икс) = 001 Икс² + 924 Икс + 006

Q(Икс) / E(Икс) = п(Икс) = 003 Икс² + 002 Икс + 001

Пересчитать п(Икс) где E(Икс) = 0 : {2, 3} исправлять б в результате получено исправленное кодовое слово:

c = {001, 006, 017, 034, 057, 086, 121}

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

• Код BCH
• Циклический код
• Чиен поиск
• Алгоритм Берлекампа-Месси
• Прямое исправление ошибок
• Алгоритм Берлекампа – Велча
• Сложенный код Рида – Соломона

Заметки

1. Авторы в^[8] предоставить результаты моделирования, которые показывают, что для той же кодовой скорости (1/6) турбокоды превосходят сцепленные коды Рида-Соломона до 2 дБ (частота ошибок по битам ).

использованная литература

• Джилл, Джон (нет данных), EE387 Заметки № 7, Раздаточный материал № 28 (PDF), Стэнфордский университет, архив из оригинал (PDF) 30 июня 2014 г., получено 21 апреля, 2010
• Хонг, Джонатан; Веттерли, Мартин (август 1995), «Простые алгоритмы декодирования BCH» (PDF), Транзакции IEEE по коммуникациям, 43 (8): 2324–2333, Дои:10.1109/26.403765
• Линь, Шу; Костелло-младший, Дэниел Дж. (1983), Кодирование с контролем ошибок: основы и приложения, Нью-Джерси, Нью-Джерси: Прентис-Холл, ISBN  978-0-13-283796-5
• Мэсси, Дж. Л. (1969), «Синтез регистров сдвига и декодирование BCH» (PDF), IEEE Transactions по теории информации, ИТ-15 (1): 122–127, Дои:10.1109 / tit.1969.1054260
• Петерсон, Уэсли В. (1960), "Процедуры кодирования и исправления ошибок для кодов Бозе-Чаудхури", Сделки IRE по теории информации, IT-6 (4): 459–470, Дои:10.1109 / TIT.1960.1057586
• Рид, Ирвинг С.; Соломон, Гюстав (1960), "Полиномиальные коды над некоторыми конечными полями", Журнал Общества промышленной и прикладной математики, 8 (2): 300–304, Дои:10.1137/0108018
• Уэлч, Л. Р. (1997), Первоначальный взгляд на коды Рида – Соломона (PDF), Конспект лекций

дальнейшее чтение

• Берлекамп, Элвин Р. (1967), Недвоичное декодирование BCH, Международный симпозиум по теории информации, Сан-Ремо, Италия
• Берлекамп, Элвин Р. (1984) [1968], Алгебраическая теория кодирования (Пересмотренное издание), Laguna Hills, CA: Aegean Park Press, ISBN  978-0-89412-063-3
• Сипра, Барри Артур (1993), "Вездесущие коды Рида – Соломона", Новости SIAM, 26 (1)
• Форни младший, Г. (Октябрь 1965 г.), «О декодировании кодов BCH», IEEE Transactions по теории информации, 11 (4): 549–557, Дои:10.1109 / TIT.1965.1053825
• Кёттер, Ральф (2005), Коды Рида – Соломона, MIT Lecture Notes 6.451 (видео), архивировано с оригинал на 2013-03-13
• MacWilliams, F.J .; Слоан, Н. Дж. А. (1977), Теория кодов, исправляющих ошибки, Нью-Йорк, Нью-Йорк: Издательская компания Северной Голландии.
• Рид, Ирвинг С.; Чен, Сюэминь (1999), Кодирование с контролем ошибок для сетей передачи данных, Бостон, Массачусетс: Kluwer Academic Publishers

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

Информация и учебные пособия

• Введение в коды Рида – Соломона: принципы, архитектура и реализация (CMU)
• Учебное пособие по кодированию Рида – Соломона для обеспечения отказоустойчивости в RAID-подобных системах
• Алгебраическое мягкое декодирование кодов Рида – Соломона
• Викиверситет: коды Рида – Соломона для программистов
• Белая книга BBC R&D WHP031
• Гейзель, Уильям А. (август 1990 г.), Учебное пособие по кодированию с исправлением ошибок Рида – Соломона (PDF), Технический меморандум, НАСА, TM-102162
• Гао, Шухун (январь 2002 г.), Новый алгоритм декодирования кодов Рида-Соломона (PDF), Клемсон
• Составные коды автор Dr. Дэйв Форни (scholarpedia.org).

Реализации

• Кодек Рида – Соломона Schifra с открытым исходным кодом C ++
• Библиотека RSCode Генри Мински, кодировщик / декодер Рида – Соломона
• Библиотека программного декодирования Рида – Соломона с открытым исходным кодом C ++
• Реализация в Matlab ошибок и стираний декодирования Рида – Соломона
• Реализация Octave в коммуникационном пакете
• Реализация кодека Рида – Соломона на чистом Python

1. Рид и Соломон (1960)
2. Д. Горенштейн и Н. Цирлер, "Класс циклических линейных кодов с исправлением ошибок в символах p ^ m", J. SIAM, vol. 9, стр. 207-214, июнь 1961 г.
3. Коды исправления ошибок, автор W_Wesley_Peterson, 1961 г.
4. Коды исправления ошибок, автор W_Wesley_Peterson, второе издание, 1972 г.
5. Ясуо Сугияма, Масао Касахара, Сигейчи Хирасава и Тошихико Намекава. Метод решения ключевого уравнения для декодирования кодов Гоппа. Информация и контроль, 27: 87–99, 1975.
6. Имминк, К.А.С. (1994), «Коды Рида – Соломона и компакт-диск», в Wicker, Stephen B .; Бхаргава, Виджай К. (ред.), Коды Рида – Соломона и их приложения, IEEE Press, ISBN  978-0-7803-1025-4
7. Дж. Хагенауэр, Э. Оффер и Л. Папке, Коды Рида-Соломона и их приложения. Нью-Йорк IEEE Press, 1994 - стр. 433
8. Эндрюс, Кеннет С. и др. «Разработка кодов турбо и LDPC для приложений дальнего космоса». Протоколы IEEE 95.11 (2007): 2142-2156.
9. Лидл, Рудольф; Пильц, Гюнтер (1999). Прикладная абстрактная алгебра (2-е изд.). Вайли. п. 226.
10. Увидеть Лин и Костелло (1983), п. 171), например.
11. «Аналитические выражения, используемые в кодировании и BERTool». В архиве с оригинала на 2019-02-01. Получено 2019-02-01.
12. Пфендер, Флориан; Циглер, Гюнтер М. (сентябрь 2004 г.), «Целующиеся числа, упаковки сфер и некоторые неожиданные доказательства» (PDF), Уведомления Американского математического общества, 51 (8): 873–883, в архиве (PDF) из оригинала 2008-05-09, получено 2009-09-28. Объясняет теорему Дельсарта-Гётальса-Зейделя в контексте кода исправления ошибок для компакт-диск.
13. Д. Горенштейн и Н. Цирлер, "Класс циклических линейных кодов с исправлением ошибок в символах p ^ m", J. SIAM, vol. 9. С. 207–214, июнь 1961 г.
14. Коды исправления ошибок Уэсли Петерсон, 1961 г.
15. Шу Линь и Дэниел Дж. Костелло-младший, "Кодирование с контролем ошибок", второе издание, стр. 255–262, 1982, 2004
16. Гурусвами, V .; Судан, М. (сентябрь 1999 г.), «Улучшенное декодирование кодов Рида – Соломона и кодов алгебраической геометрии», IEEE Transactions по теории информации, 45 (6): 1757–1767, CiteSeerX  10.1.1.115.292, Дои:10.1109/18.782097
17. Кёттер, Ральф; Варди, Александр (2003). «Алгебраическое декодирование с мягким решением кодов Рида – Соломона». IEEE Transactions по теории информации. 49 (11): 2809–2825. CiteSeerX  10.1.1.13.2021. Дои:10.1109 / TIT.2003.819332.
18. Franke, Стивен Дж .; Тейлор, Джозеф Х. (2016). "Декодер Soft-Decision с открытым исходным кодом для кода Рида-Соломона JT65 (63,12)" (PDF). QEX (Май / июнь): 8–17. В архиве (PDF) из оригинала на 2017-03-09. Получено 2017-06-07.