Исправление ошибок Рида-Соломона

Коды исправления ошибок

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

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

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

История

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

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

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

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

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

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

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

В 2002 году Шухонг Гао разработал еще одну оригинальную схему декодера, основанную на расширенном алгоритме Евклида . ^[6]

Приложения

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

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

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

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

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

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

Штрих-код

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

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

Передача данных

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

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

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

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

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

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

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

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

Современные версии конкатенированного сверточного кодирования с декодированием Рида-Соломона/Витерби использовались и используются в миссиях Mars Pathfinder , Galileo , Mars Exploration Rover и Cassini , где они работают в пределах примерно 1–1,5 дБ от конечного предела — пропускной способности Шеннона .

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

Конструкции (кодирование)

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

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

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

Формально набор кодовых слов кода Рида–Соломона определяется следующим образом: Поскольку любые два различных полинома степени меньше согласуются в большинстве точек, это означает, что любые два кодовых слова кода Рида–Соломона не согласуются по крайней мере в позициях. Более того, существуют два полинома, которые согласуются в точках, но не равны, и, таким образом, расстояние кода Рида–Соломона равно в точности . Тогда относительное расстояние равно , где — скорость. Этот компромисс между относительным расстоянием и скоростью является асимптотически оптимальным, поскольку по границе Синглтона каждый код удовлетворяет . Будучи кодом, который достигает этого оптимального компромисса , код Рида–Соломона принадлежит к классу кодов, разделяемых на максимальном расстоянии . ${\displaystyle \mathbf {C} }$ $${\displaystyle \mathbf {C} ={\Bigl \{}\;{\bigl (}p(a_{1}),p(a_{2}),\dots ,p(a_{n}){\bigr )}\;{\Big |}\;p{\text{ is a polynomial over }}F{\text{ of degree }}<k\;{\Bigr \}}\,.}$$ ${\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 и число различных сообщений оба равны , и, таким образом, каждое сообщение может быть однозначно отображено в такой многочлен, существуют различные способы выполнения этого кодирования. Первоначальная конструкция Рида и Соломона (1960) интерпретирует сообщение x как коэффициенты многочлена p , тогда как последующие конструкции интерпретируют сообщение как значения многочлена в первых k точках и получают многочлен p путем интерполяции этих значений с многочленом степени меньше k . Последняя процедура кодирования, хотя и немного менее эффективна, имеет то преимущество, что она приводит к систематическому коду , то есть исходное сообщение всегда содержится как подпоследовательность кодового слова. ${\displaystyle q^{k}}$ ${\displaystyle a_{1},\dots ,a_{k}}$

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

В оригинальной конструкции Рида и Соломона (1960) сообщение отображается в полином с Кодовое слово получается путем оценки в различных точках поля . Таким образом, классическая функция кодирования для кода Рида–Соломона определяется следующим образом: Эта функция является линейным отображением , то есть она удовлетворяет для следующей -матрицы с элементами из : ${\displaystyle m=(m_{0},\dots ,m_{k-1})\in F^{k}}$ ${\displaystyle p_{m}}$ $${\displaystyle p_{m}(a)=\sum _{i=0}^{k-1}m_{i}a^{i}\,.}$$ ${\displaystyle m}$ ${\displaystyle p_{m}}$ ${\displaystyle n}$ ${\displaystyle a_{0},\dots ,a_{n-1}}$ ${\displaystyle F}$ ${\displaystyle C:F^{k}\to F^{n}}$ $${\displaystyle C(m)={\begin{bmatrix}p_{m}(a_{0})\\p_{m}(a_{1})\\\cdots \\p_{m}(a_{n-1})\end{bmatrix}}}$$ ${\displaystyle C}$ ${\displaystyle C(m)=Am}$ ${\displaystyle n\times k}$ ${\displaystyle A}$ ${\displaystyle F}$ $${\displaystyle C(m)=Am={\begin{bmatrix}1&a_{0}&a_{0}^{2}&\dots &a_{0}^{k-1}\\1&a_{1}&a_{1}^{2}&\dots &a_{1}^{k-1}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&a_{n-1}&a_{n-1}^{2}&\dots &a_{n-1}^{k-1}\end{bmatrix}}{\begin{bmatrix}m_{0}\\m_{1}\\\vdots \\m_{k-1}\end{bmatrix}}}$$

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

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

Существуют альтернативные процедуры кодирования, которые производят систематический код Рида–Соломона. Один метод использует интерполяцию Лагранжа для вычисления полинома, такого что Тогда оценивается в других точках . ${\displaystyle p_{m}}$ $${\displaystyle p_{m}(a_{i})=m_{i}{\text{ for all }}i\in \{0,\dots ,k-1\}.}$$ ${\displaystyle p_{m}}$ ${\displaystyle a_{k},\dots ,a_{n-1}}$

$${\displaystyle C(m)={\begin{bmatrix}p_{m}(a_{0})\\p_{m}(a_{1})\\\cdots \\p_{m}(a_{n-1})\end{bmatrix}}}$$

Эта функция является линейным отображением. Чтобы сгенерировать соответствующую систематическую кодирующую матрицу G, умножьте матрицу Вандермонда A на обратную левую квадратную подматрицу A. ${\displaystyle C}$

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

${\displaystyle C(m)=Gm}$для следующей -матрицы с элементами из : ${\displaystyle n\times k}$ ${\displaystyle G}$ ${\displaystyle F}$ $${\displaystyle C(m)=Gm={\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}}{\begin{bmatrix}m_{0}\\m_{1}\\\vdots \\m_{k-1}\end{bmatrix}}}$$

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

Дискретное преобразование Фурье по сути то же самое, что и процедура кодирования; оно использует генераторный полином для отображения набора точек оценки в значения сообщения, как показано выше: ${\displaystyle p_{m}}$ $${\displaystyle C(m)={\begin{bmatrix}p_{m}(a_{0})\\p_{m}(a_{1})\\\cdots \\p_{m}(a_{n-1})\end{bmatrix}}}$$

Обратное преобразование Фурье можно использовать для преобразования безошибочного набора значений сообщения n < q обратно в кодирующий полином из k коэффициентов, с тем ограничением, что для того, чтобы это работало, набор точек оценки, используемых для кодирования сообщения, должен быть набором возрастающих степеней α : $${\displaystyle a_{i}=\alpha ^{i}}$$ $${\displaystyle a_{0},\dots ,a_{n-1}=\{1,\alpha ,\alpha ^{2},\dots ,\alpha ^{n-1}\}}$$

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

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

В этом представлении сообщение интерпретируется как коэффициенты полинома . Отправитель вычисляет связанный полином степени , где и отправляет полином . Полином строится путем умножения полинома сообщения , имеющего степень , на порождающий полином степени , которая известна как отправителю, так и получателю. Порождающий полином определяется как полином, корни которого являются последовательными степенями примитива поля Галуа ${\displaystyle p(x)}$ ${\displaystyle s(x)}$ ${\displaystyle n-1}$ ${\displaystyle n\leq q-1}$ ${\displaystyle s(x)}$ ${\displaystyle s(x)}$ ${\displaystyle p(x)}$ ${\displaystyle k-1}$ ${\displaystyle g(x)}$ ${\displaystyle n-k}$ ${\displaystyle g(x)}$ ${\displaystyle \alpha }$ $${\displaystyle g(x)=\left(x-\alpha ^{i}\right)\left(x-\alpha ^{i+1}\right)\cdots \left(x-\alpha ^{i+n-k-1}\right)=g_{0}+g_{1}x+\cdots +g_{n-k-1}x^{n-k-1}+x^{n-k}}$$

Для «узкосмыслового кода» . ${\displaystyle i=1}$

$${\displaystyle \mathbf {C} =\left\{\left(s_{1},s_{2},\dots ,s_{n}\right)\;{\Big |}\;s(a)=\sum _{i=1}^{n}s_{i}a^{i}{\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)\,.}$$

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

Эта функция является линейным отображением. Чтобы сгенерировать соответствующую систематическую кодирующую матрицу G, установите левую квадратную подматрицу G в единичную матрицу, а затем закодируйте каждую строку: ${\displaystyle s}$

$${\displaystyle G={\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}}}$$Игнорируя начальные нули, последняя строка = . ${\displaystyle g(x)}$

${\displaystyle C(m)=Gm}$для следующей -матрицы с элементами из : ${\displaystyle n\times k}$ ${\displaystyle G}$ ${\displaystyle F}$ $${\displaystyle C(m)=Gm={\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}}{\begin{bmatrix}m_{0}\\m_{1}\\\vdots \\m_{k-1}\end{bmatrix}}}$$

Характеристики

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

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

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

Теоретическая граница ошибки может быть описана с помощью следующей формулы для канала AWGN для FSK : ^[11] и для других схем модуляции: где , , , — частота ошибок символов в случае некодированного AWGN, а — порядок модуляции. $${\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 }}$$ ${\textstyle t={\frac {1}{2}}(d_{\min }-1)}$ ${\displaystyle P_{s}=1-(1-s)^{h}}$ ${\displaystyle h={\frac {m}{\log _{2}M}}}$ ${\displaystyle s}$ ${\displaystyle M}$

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

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

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

Является ли код Рида–Соломона циклическим или нет, зависит от тонких деталей конструкции. В исходном представлении Рида и Соломона, где кодовые слова являются значениями многочлена, можно выбрать последовательность точек оценки таким образом, чтобы сделать код циклическим. В частности, если является примитивным корнем поля , то по определению все ненулевые элементы принимают вид для , где . Каждый многочлен над порождает кодовое слово . Поскольку функция также является многочленом той же степени, эта функция порождает кодовое слово ; поскольку выполняется , это кодовое слово является циклическим левым сдвигом исходного кодового слова, полученного из . Таким образом, выбор последовательности степеней примитивных корней в качестве точек оценки делает исходное представление кода Рида–Соломона циклическим . Коды Рида–Соломона в представлении БЧХ всегда циклические , поскольку коды БЧХ являются циклическими . ${\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}$

Замечания

Разработчики не обязаны использовать «естественные» размеры блоков кода Рида–Соломона. Метод, известный как «сокращение», может создать меньший код любого желаемого размера из большего кода. Например, широко используемый код (255,223) может быть преобразован в код (160,128) путем заполнения неиспользуемой части исходного блока 95 двоичными нулями и не передачи их. В декодере та же часть блока загружается локально двоичными нулями.

QR-код версии 3 (29×29) использует чередующиеся блоки. Сообщение содержит 26 байтов данных и закодировано с использованием двух блоков кода Рида-Соломона. Каждый блок представляет собой код Рида-Соломона (255,233), сокращенный до кода (35,13).

Теорема Дельсарта–Геталса–Зейделя ^[12] иллюстрирует пример применения укороченных кодов Рида–Соломона. Параллельно с укорочением, метод, известный как прокалывание, позволяет опустить некоторые закодированные символы четности.

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

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

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

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

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

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

В результате процедуры кодирования Рида-Соломона s ( x ) делится на порождающий полином g ( x ): где α — примитивный элемент. $${\displaystyle g(x)=\prod _{j=1}^{n-k}(x-\alpha ^{j}),}$$

Поскольку s ( x ) является кратным генератору g ( x ), то отсюда следует, что он «наследует» все его корни. Следовательно, $${\displaystyle s(x){\bmod {(}}x-\alpha ^{j})=g(x){\bmod {(}}x-\alpha ^{j})=0}$$ $${\displaystyle s(\alpha ^{j})=0,\ j=1,2,\ldots ,n-k}$$

Переданный полином искажается при передаче полиномом ошибки e ( x ) для получения полученного полинома r ( x ). $${\displaystyle r(x)=s(x)+e(x)}$$ $${\displaystyle e(x)=\sum _{i=0}^{n-1}e_{i}x^{i}}$$

Коэффициент e _i будет равен нулю, если нет ошибки в этой степени x и ненулевой, если есть ошибка. Если есть ν ошибок в различных степенях i _k от x , то $${\displaystyle e(x)=\sum _{k=1}^{\nu }e_{i_{k}}x^{i_{k}}}$$

Цель декодера — найти количество ошибок ( ν ), позиции ошибок ( ik ) и значения ошибок в этих позициях ( eik ) . _Из них можно вычислить e ( x ) и вычесть из r ( _x ), чтобы получить изначально отправленное сообщение s ( _x ).

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

Декодер начинает с оценки полинома, полученного в точках . Мы называем результаты этой оценки «синдромами», S _j . Они определяются как: Обратите внимание, что поскольку имеет корни в , как показано в предыдущем разделе. ${\displaystyle \alpha ^{1}\dots \alpha ^{n-k}}$ $${\displaystyle {\begin{aligned}S_{j}&=r(\alpha ^{j})=s(\alpha ^{j})+e(\alpha ^{j})=0+e(\alpha ^{j})\\&=e(\alpha ^{j})\\&=\sum _{k=1}^{\nu }e_{i_{k}}\left(\alpha ^{j}\right)^{i_{k}},\quad j=1,2,\ldots ,n-k\end{aligned}}}$$ ${\displaystyle s(\alpha ^{j})=0}$ ${\displaystyle s(x)}$ ${\displaystyle \alpha ^{j}}$

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

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

Для удобства определим локаторы ошибок X _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}}$

Синдромы дают систему из n − k ≥ 2 ν уравнений с 2 ​​ν неизвестными, но эта система уравнений нелинейна относительно X _k и не имеет очевидного решения. Однако, если бы X _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 &\ddots &\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}}}$$

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

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

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

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

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

Определим полином локатора ошибок Λ( x ) как $${\displaystyle \Lambda (x)=\prod _{k=1}^{\nu }(1-xX_{k})=1+\Lambda _{1}x^{1}+\Lambda _{2}x^{2}+\cdots +\Lambda _{\nu }x^{\nu }}$$

Нули Λ( x ) являются обратными величинами . Это следует из приведенной выше конструкции записи произведения, поскольку если то один из умноженных членов будет равен нулю , что делает весь многочлен равным нулю. ${\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.\\[1ex]&Y_{k}X_{k}^{j+\nu }\left(1+\Lambda _{1}X_{k}^{-1}+\Lambda _{2}X_{k}^{-2}+\cdots +\Lambda _{\nu }X_{k}^{-\nu }\right)=0.\\[1ex]&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.\\[1ex]&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 \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}$$

Соберите каждый член в отдельную сумму. $${\displaystyle \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}$$

Извлеките постоянные значения, на которые не влияет суммирование. ${\displaystyle \Lambda }$ $${\displaystyle \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}$$

Эти суммирования теперь эквивалентны значениям синдрома, которые мы знаем и можем подставить! Таким образом, это сводится к $${\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 линейных уравнений, а не только одно. Эта система линейных уравнений может быть решена для коэффициентов Λ _i полинома местоположения ошибки: Вышеизложенное предполагает, что декодер знает количество ошибок ν , но это количество еще не определено. Декодер PGZ не определяет ν напрямую, а ищет его, пробуя последовательные значения. Декодер сначала предполагает наибольшее значение для пробного ν и устанавливает линейную систему для этого значения. Если уравнения могут быть решены (т. е. определитель матрицы не равен нулю), то это пробное значение является количеством ошибок. Если линейная система не может быть решена, то пробное ν уменьшается на единицу, и рассматривается следующая меньшая система. (Gill nd, стр. 35) $${\displaystyle {\begin{bmatrix}S_{1}&S_{2}&\cdots &S_{\nu }\\S_{2}&S_{3}&\cdots &S_{\nu +1}\\\vdots &\vdots &\ddots &\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}}}$$

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

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

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

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

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

Рассчитайте i _k , взяв логарифмическое основание X k _. Обычно это делается с помощью предварительно вычисленной таблицы поиска. ${\displaystyle \alpha }$

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

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

Пример

Рассмотрим код Рида–Соломона, определенный в GF (929) с α = 3 и t = 4 (он используется в штрихкодах PDF417 ) для кода RS(7,3). Генераторный полином равен Если полином сообщения равен p ( x ) = 3 x ² + 2 x + 1 , то систематическое кодовое слово кодируется следующим образом. Ошибки при передаче могут привести к тому, что вместо этого будет получено это. Синдромы вычисляются путем оценки r в степенях α . $${\displaystyle g(x)=(x-3)(x-3^{2})(x-3^{3})(x-3^{4})=x^{4}+809x^{3}+723x^{2}+568x+522}$$ $${\displaystyle s_{r}(x)=p(x)\,x^{t}{\bmod {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}}}$$

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

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

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

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

Для расчета значений ошибок применим алгоритм Форни .

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

Λ'(х) = 658 х + 821

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

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

Вычитание из полученного полинома r ( x ) воспроизводит исходное кодовое слово s . ${\displaystyle e_{1}x^{3}+e_{2}x^{4}=74x^{3}+122x^{4}}$

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

Алгоритм Берлекэмпа–Месси представляет собой альтернативную итеративную процедуру поиска полинома локатора ошибок. Во время каждой итерации он вычисляет расхождение на основе текущего экземпляра Λ( x ) с предполагаемым числом ошибок e : и затем корректирует Λ( x ) и e так, чтобы пересчитанное Δ было равно нулю. Статья Алгоритм Берлекэмпа–Месси содержит подробное описание процедуры. В следующем примере C ( x ) используется для представления Λ( x ). $${\displaystyle \Delta =S_{i}+\Lambda _{1}\ S_{i-1}+\cdots +\Lambda _{e}\ S_{i-e}}$$

Пример

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

Конечное значение C — это полином локатора ошибок Λ( x ).

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

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

Определим S ( x ), Λ( x ) и Ω( x ) для t синдромов и e ошибок: $${\displaystyle {\begin{aligned}S(x)&=S_{t}x^{t-1}+S_{t-1}x^{t-2}+\cdots +S_{2}x+S_{1}\\[1ex]\Lambda (x)&=\Lambda _{e}x^{e}+\Lambda _{e-1}x^{e-1}+\cdots +\Lambda _{1}x+1\\[1ex]\Omega (x)&=\Omega _{e}x^{e}+\Omega _{e-1}x^{e-1}+\cdots +\Omega _{1}x+\Omega _{0}\end{aligned}}}$$

Ключевое уравнение: $${\displaystyle \Lambda (x)S(x)=Q(x)x^{t}+\Omega (x)}$$

Для t = 6 и e = 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}}}$$

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

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

A _i ( x ) S ( x ) + B _i ( x ) x ^t = R _i ( x )

где степень R уменьшается с ростом i . Как только степень R _i ( x ) < t /2, тогда

А _i ( x ) = Λ( x )

B _i ( x ) = −Q( x )

Ri ( x ) = Ω ( _x ).

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

R −1  := x t R 0  := S ( x ) A −1  := 0 A 0  := 1 i  := 0 пока степень R i ≥ t /2 i  := i + 1 Q  := R i -2 / R i -1  R i  := R i -2 - Q  R i -1  A i  := A i -2 - Q  A i -1

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

Λ( x ) = A _i / A _i (0)

Ω( x ) = Ri / _Ai ( 0 ₎

A _i (0) — постоянный (низшего порядка) член A _i .

Пример

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

Λ( Икс ) = А _2/544 = 329 Икс ² + 821 Икс + 001

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

Декодер, использующий дискретное преобразование Фурье

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

Преобразуем r ( x ) в R ( x ) с помощью дискретного преобразования Фурье. Поскольку расчет для дискретного преобразования Фурье такой же, как расчет для синдромов, коэффициенты t R ( x ) и E ( x ) такие же, как и у синдромов: $${\displaystyle R_{j}=E_{j}=S_{j}=r(\alpha ^{j})\qquad {\text{for }}1\leq j\leq t}$$

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

Пусть v = количество ошибок. Сгенерируйте E ( x ) с использованием известных коэффициентов , полинома локатора ошибок и этих формул ${\displaystyle E_{1}}$ ${\displaystyle E_{t}}$ $${\displaystyle {\begin{aligned}E_{0}&=-{\frac {1}{\Lambda _{v}}}(E_{v}+\Lambda _{1}E_{v-1}+\cdots +\Lambda _{v-1}E_{1})\\E_{j}&=-(\Lambda _{1}E_{j-1}+\Lambda _{2}E_{j-2}+\cdots +\Lambda _{v}E_{j-v})&{\text{for }}t<j<n\end{aligned}}}$$

Затем вычисляем C ( x ) = R ( x ) − E ( x ) и выполняем обратное преобразование (полиномиальную интерполяцию) C ( x ), чтобы получить c ( x ).

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

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

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

В 2023 году, основываясь на трех захватывающих работах, ^{[17] [18] [19]} теоретики кодирования показали, что коды Рида-Соломона, определенные по случайным точкам оценки, могут фактически достигать емкости декодирования списков (до n − k ошибок) над алфавитами линейного размера с высокой вероятностью. Однако этот результат является комбинаторным, а не алгоритмическим.

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

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

Пример MATLAB

Кодировщик

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

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

Декодер

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

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

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

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

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

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

Декодер Берлекэмпа Уэлча

В 1986 году был разработан декодер, известный как алгоритм Берлекэмпа–Уэлча , который способен восстановить исходный полином сообщения, а также полином «локатора» ошибок, который выдает нули для входных значений, соответствующих ошибкам, со сложностью по времени , где — количество значений в сообщении. Затем восстановленный полином используется для восстановления (пересчета по мере необходимости) исходного сообщения. ${\displaystyle O(n^{3})}$ ${\displaystyle n}$

Пример

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

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

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

р ( х ) = 003 х ² + 002 х + 001

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

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

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

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

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

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

Предположим максимальное количество ошибок: e = 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

Е ( х ) = 001 х ² + 924 х + 006

Q ( х ) / E ( х ) = P ( х ) = 003 х ² + 002 х + 001

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

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

Декодер Гао

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

Пример

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

• ${\displaystyle R_{-1}=\prod _{i=1}^{n}(x-a_{i})}$
• ${\displaystyle R_{0}=}$Интерполяция Лагранжа для i = 1 до n ${\displaystyle \{a_{i},b(a_{i})\}}$
• ${\displaystyle A_{-1}=0}$
• ${\displaystyle A_{0}=1}$

Q ( х ) = R ₂ = 266 х ⁴ + 086 х ³ + 798 х ² + 311 х + 532

Е ( х ) = А ₂ = 708 х ² + 176 х + 532

Разделите Q ( x ) и E ( x ) на наиболее значимый коэффициент E ( x ) = 708. (Необязательно)

Q ( х ) = 003 х ⁴ + 916 х ³ + 009 х ² + 007 х + 006

Е ( х ) = 001 х ² + 924 х + 006

Q ( х ) / E ( х ) = P ( х ) = 003 х ² + 002 х + 001

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

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

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

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

Примечания

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

Ссылки

1. Рид и Соломон (1960)
2. Горенштейн, Д.; Цирлер, Н. (июнь 1961 г.). «Класс циклических линейных кодов с исправлением ошибок в символах p^m». J. SIAM . 9 (2): 207–214. doi :10.1137/0109020. JSTOR  2098821.
3. Петерсон, У. Уэсли (1961). Коды исправления ошибок . MIT Press. OCLC  859669631.
4. Петерсон, В. Уэсли; Уэлдон, Э.Дж. (1996) [1972]. Коды исправления ошибок (2-е изд.). MIT Press. ISBN 978-0-585-30709-1. OCLC  45727875.
5. Сугияма, Y.; Касахара, M.; Хирасава, S.; Намекава, T. (1975). «Метод решения ключевого уравнения для декодирования кодов Гоппы». Информация и управление . 27 (1): 87–99. doi : 10.1016/S0019-9958(75)90090-X .
6. Gao, Shuhong (январь 2002), Новый алгоритм декодирования кодов Рида-Соломона (PDF) , Клемсон
7. Имминк, КАС (1994), «Коды Рида–Соломона и компакт-диск», в Wicker, Stephen B.; Bhargava, Vijay K. (ред.), Коды Рида–Соломона и их применение , IEEE Press , ISBN 978-0-7803-1025-4
8. Хагенауэр, Дж.; Оффер, Э.; Папке, Л. (1994). "11. Сопоставление декодеров Витерби и декодеров Рида-Соломона в каскадной системе". Коды Рида-Соломона и их применение . IEEE Press. стр. 433. ISBN 9780470546345. OCLC  557445046.
9. Andrews, KS; Divsalar, D.; Dolinar, S.; Hamkins, J.; Jones, CR; Pollara, F. (2007). "Разработка турбо- и LDPC-кодов для приложений дальнего космоса" (PDF) . Труды IEEE . 95 (11): 2142–56. doi :10.1109/JPROC.2007.905132. S2CID  9289140.
10. См., например, Лин и Костелло (1983, стр. 171).
11. "Аналитические выражения, используемые в bercoding и BERTool". Архивировано из оригинала 2019-02-01 . Получено 2019-02-01 .
12. Пфендер, Флориан; Циглер, Гюнтер М. (сентябрь 2004 г.), «Kissing Numbers, Sphere Packings, and Some Unexpected Proofs» (PDF) , Notices of the American Mathematical Society , 51 (8): 873–883, архивировано (PDF) из оригинала 2008-05-09 , извлечено 2009-09-28Объясняет теорему Дельсарта-Гёталса-Зейделя, используемую в контексте кода исправления ошибок для компакт-диска .
13. Д. Горенштейн и Н. Цирлер, «Класс циклических линейных кодов с исправлением ошибок в символах p^m», J. SIAM, т. 9, стр. 207–214, июнь 1961 г.
14. Коды исправления ошибок , У. Уэсли Петерсон, 1961 г.
15. Шу Линь и Дэниел Дж. Костелло-младший, «Кодирование с контролем ошибок», второе издание, стр. 255–262, 1982, 2004
16. Guruswami, V.; Sudan, M. (сентябрь 1999 г.), «Улучшенное декодирование кодов Рида–Соломона и кодов алгебраической геометрии», IEEE Transactions on Information Theory , 45 (6): 1757–1767, CiteSeerX 10.1.1.115.292 , doi :10.1109/18.782097 
17. Brakensiek, Joshua; Gopi, Sivakanth; Makam, Visu (2023-06-02). «Общие коды Рида-Соломона достигают емкости декодирования списков». Труды 55-го ежегодного симпозиума ACM по теории вычислений . STOC 2023. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 1488–1501. arXiv : 2206.05256 . doi :10.1145/3564246.3585128. ISBN 978-1-4503-9913-5.
18. Го, Цзэюй; Чжан, Цзыхан (2023). «Случайно проколотые коды Рида-Соломона достигают пропускной способности декодирования списков над алфавитами полиномиального размера». 2023 IEEE 64-й ежегодный симпозиум по основам компьютерной науки (FOCS) . FOCS 2023, Санта-Крус, Калифорния, США, 2023. стр. 164–176. arXiv : 2304.01403 . doi : 10.1109/FOCS57990.2023.00019. ISBN 979-8-3503-1894-4.
19. Альрабиа, Омар; Гурусвами, Венкатесан; Ли, Рэй (2023-08-18), Случайно проколотые коды Рида--Соломона достигают способности декодирования списков над полями линейного размера, arXiv : 2304.09445 , получено 2024-02-08
20. Koetter, Ralf; Vardy, Alexander (2003). «Алгебраическое мягкое декодирование кодов Рида–Соломона». IEEE Transactions on Information Theory . 49 (11): 2809–2825. CiteSeerX 10.1.1.13.2021 . doi :10.1109/TIT.2003.819332. 
21. Франке, Стивен Дж.; Тейлор, Джозеф Х. (2016). "Open Source Soft-Decision Decoder for the JT65 (63,12) Reed–Solomon Code" (PDF) . QEX (май/июнь): 8–17. Архивировано (PDF) из оригинала 2017-03-09 . Получено 2017-06-07 .

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

• Гилл, Джон (nd), EE387 Notes #7, Handout #28 (PDF) , Стэнфордский университет, архивировано из оригинала (PDF) 30 июня 2014 г. , извлечено 21 апреля 2010 г.
• Хонг, Джонатан; Веттерли, Мартин (август 1995 г.), «Простые алгоритмы декодирования BCH» (PDF) , IEEE Transactions on Communications , 43 (8): 2324–33, doi :10.1109/26.403765
• Линь, Шу; Костелло, младший, Дэниел Дж. (1983), Кодирование с контролем ошибок: основы и приложения , Prentice-Hall, ISBN 978-0-13-283796-5
• Massey, JL (1969), «Синтез сдвигового регистра и декодирование BCH» (PDF) , IEEE Transactions on Information Theory , IT-15 (1): 122–127, doi :10.1109/tit.1969.1054260, S2CID  9003708
• Петерсон, Уэсли В. (1960), «Процедуры кодирования и исправления ошибок для кодов Боуза-Чоудхури», Труды IRE по теории информации , IT-6 (4): 459–470, doi :10.1109/TIT.1960.1057586
• Рид, Ирвинг С.; Соломон , Гюстав (1960), «Полиномиальные коды над некоторыми конечными полями», Журнал Общества промышленной и прикладной математики , 8 (2): 300–304, doi :10.1137/0108018
• Уэлч, Л.Р. (1997), Первоначальный взгляд на коды Рида–Соломона (PDF) , Конспект лекций
• Берлекамп, Элвин Р. (1967), Небинарное декодирование BCH , Международный симпозиум по теории информации, Сан-Ремо, Италия, OCLC  45195002, AD0669824
• Берлекамп, Элвин Р. (1984) [1968], Теория алгебраического кодирования (пересмотренная редакция), Лагуна-Хиллз, Калифорния: Aegean Park Press, ISBN 978-0-89412-063-3
• Ципра, Барри Артур (1993), «Вездесущие коды Рида – Соломона», SIAM News , 26 (1)
• Форни, младший, Г. (октябрь 1965 г.), «О декодировании кодов BCH», Труды IEEE по теории информации , 11 (4): 549–557, doi :10.1109/TIT.1965.1053825
• Koetter, Ralf (2005), Коды Рида–Соломона, MIT Lecture Notes 6.451 (видео), архивировано из оригинала 2013-03-13
• MacWilliams, FJ; Sloane, NJA (1977), Теория кодов, исправляющих ошибки, North-Holland, ISBN 978-0-444-85010-2
• Рид, Ирвинг С.; Чен, Сюэминь (2012) [1999], Кодирование с контролем ошибок для сетей передачи данных, Springer, ISBN 9781461550051

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

Информация и руководства

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

Реализации

• Библиотека FEC на языке C Фила Карна (он же KA9Q) включает кодек Рида–Соломона, как произвольную, так и оптимизированную (223,255) версию
• Кодек Рида-Соломона с открытым исходным кодом Schifra C++
• Библиотека RSCode Генри Мински, кодер/декодер Рида–Соломона
• Библиотека мягкого декодирования Рида–Соломона с открытым исходным кодом на языке C++
• Реализация Matlab ошибок и стираний декодирования Рида-Соломона
• Реализация Octave в пакете коммуникаций
• Реализация кодека Рида-Соломона на чистом Python