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

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

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

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

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

История

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

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

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

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

В 1977 году коды Рида–Соломона были реализованы в программе «Вояджер» в виде составных кодов с исправлением ошибок . Первое коммерческое применение в потребительских товарах массового производства появилось в 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).

Исправление ошибок Рида-Соломона также используется в архивных файлах, которые обычно публикуются вместе с мультимедийными файлами в 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).

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

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

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

Современные версии каскадного сверточного кодирования, декодированного Ридом-Соломоном/Витерби, использовались и используются в миссиях 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, α , α 2 ^, ..., α ^{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}}$ ${\displaystyle k}$

$${\displaystyle p_{m}(a_{i})=m_{i}{\text{ for all }}i\in \{0,\dots ,k-1\}.}$$

интерполяцию Лагранжа ${\displaystyle p_{m}}$ ${\displaystyle 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}}}$$

Этот вариант является систематическим , поскольку первые записи , точно соответствуют определению . ${\displaystyle k}$ ${\displaystyle p_{m}(a_{0}),\dots ,p_{m}(a_{k-1})}$ ${\displaystyle m_{0},\dots ,m_{k-1}}$ ${\displaystyle p_{m}}$

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

Дискретное преобразование Фурье по существу совпадает с процедурой кодирования; он использует полином генератора для сопоставления набора точек оценки со значениями сообщения, как показано выше: ${\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)\,.}$$

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

Код Рида – Соломона представляет собой код [ n , k , n − k + 1]; другими словами, это линейный блочный код длины n (над F ) с размерностью 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]

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

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

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

Является ли код Рида-Соломона циклическим или нет, зависит от тонких деталей конструкции. В исходной точке зрения Рида и Соломона, где кодовые слова являются значениями полинома, можно выбрать последовательность точек оценки таким образом, чтобы сделать код циклическим. В частности, если – примитивный корень поля , то по определению все ненулевые элементы поля принимают вид для , где . Каждый полином выше порождает кодовое слово . Поскольку функция также является полиномом той же степени, эта функция порождает кодовое слово ; поскольку выполняется, это кодовое слово представляет собой циклический сдвиг влево исходного кодового слова, полученного из . Таким образом, выбор последовательности примитивных корневых степеней в качестве точек оценки делает исходный код Рида-Соломона циклическим . Коды Рида-Соломона в представлении BCH всегда цикличны, поскольку коды BCH являются циклическими . ${\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 двоичными нулями и не передавая их. В декодере та же часть блока локально загружается двоичными нулями. Теорема Дельсарта–Гёталса–Зейделя ^[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 ₎ и значения ошибок в этих позициях ( e _{i k} ). Из них можно вычислить e ( x ) и вычесть из r ( x ), чтобы получить первоначально отправленное сообщение s ( x ).

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

Декодер начинает с оценки полинома, полученного в точках . Мы называем результаты этой оценки «синдромами» _, Sj . Они определяются как: ${\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 полинома местоположения ошибки:

$${\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). Полином генератора

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

p ( x ) = 3 x ² + 2 x + 1

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

rα

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

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

xe«Алгоритм Берлекэмпа – Мэсси»Cxx

Пример

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

Окончательное значение 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}}}$$

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

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

А _я ( Икс ) S ( Икс ) + B _я ( Икс ) Икс ^{т знак} равно р _я ( Икс )

где степень R уменьшается с увеличением i . Если степень R _i ( x ) < t /2, то

А _я ( Икс ) знак равно Λ( Икс )

B _я ( Икс ) знак равно -Q( Икс )

р _я ( Икс ) знак равно Ω( Икс ).

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):

Λ( Икс ) знак равно А _я / А _я (0)

Ω( x ) = р _я / А _я (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.

 закодированная функция = rsEncoder ( msg, m, prim_poly, n, k )   % RSENCODER Закодировать сообщение с помощью алгоритма Рида-Соломона. % m — количество бит на символ % prim_poly: примитивный полином p(x). Т.е. для ДМ это 301 %k — размер сообщения % n — общий размер (k+избыточный) % Пример: msg = uint8('Тест') % 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 ([ нули msg ( 1 , n - k )], m , prim_poly );         % Получить остаток от деления расширенного сообщения на % порождающий полином Рида-Соломона g(x) [ ~ , остаток ] = deconv ( msg_padded , g_x );     % Теперь верните сообщение с избыточной информацией закодировано = msg_padded - остаток ;    конец% Найдите порождающий полином Рида-Соломона g(x), кстати, это% то же, что и функция rsgenpoly в Matlabфункция  g = genpoly ( k, n, альфа )   г = 1 ;   % Умножение на поле Галуа — это всего лишь свертка для k = mod ( 1 : n - k , n )         г = conv ( г , [ 1 альфа .^ ( k )]);       конецконец

Декодер

Теперь часть декодирования:

функция [decoded, error_pos, error_mag, g, S] = rsDecoder ( encoded, m, prim_poly, n, k )  % RSDECODER Декодировать сообщение, закодированное Ридом-Соломоном % Пример: % [dec, ​​~, ~, ~, ~] = rsDecoder(enc_msg, 8, 301, 12, numel(msg)) max_errors = пол (( n - k ) / 2 );       orig_vals = закодировано . Икс ;   % Инициализировать вектор ошибок ошибки = нули ( 1 , n );    г = [];   С = [];   % Получить альфу альфа = gf ( 2 , m , prim_poly );     % Найдите синдромы (Проверьте, можно ли разделить сообщение по генератору % полиномиальный результат равен нулю) Synd = поливал ( закодировано , альфа .^ ( 1 : n - k ));        Синдромы = обрезка ( Synd );   % Если все синдромы равны нулям (совершенно делимым), ошибок нет если пусто ( Синдромы . x )  декодировано = orig_vals ( 1 : k );   error_pos = [];   error_mag = [];   г = [];   S = Синд ;   возвращаться ; конец % Подготовка к алгоритму Евклида (используется для поиска ошибки при обнаружении % полиномов) r0 = [ 1 , нули ( 1 , 2 * max_errors )]; r0 = gf ( r0 , m , prim_poly ); r0 = обрезка ( r0 );               size_r0 = длина ( r0 );   r1 = Синдромы ;   f0 = gf ([ нули ( 1 , size_r0 - 1 ) 1 ], m , prim_poly );         f1 = gf ( нули ( 1 , size_r0 ), m , prim_poly );      г0 = f1 ; г1 = f0 ;      % Выполнить алгоритм Евклида для полиномов r0(x) и Syndromes(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 = Синдромы . Икс ;   b (:, 1 ) = Syndrome_Vals ( 1 : size_error );    для idx = 1 : size_error      e = альфа .^ ( idx * ( n - error_pos . x ));         ошибка = е . Икс ;   э-э ( idx , :) = ошибка ;    конец % Решите линейную систему error_mag = ( gf ( er , m , prim_poly ) \ gf ( b , m , prim_poly )) ' ;         % Поместите величину ошибки в вектор ошибки ошибки ( error_pos . x ) = error_mag . Икс ;   % Приведите этот вектор к полю Галуа error_gf = gf ( ошибки , m , prim_poly );     % Теперь, чтобы исправить ошибки, просто добавьте закодированный код decoded_gf = закодировано ( 1 : k ) + error_gf ( 1 : k );     декодированный = decoded_gf . Икс ;  конец% Удалить ведущие нули из массива Галуафункция  gt = обрезка ( g )   гх = г . Икс ;   gt = gf ( gx ( find ( gx , 1 ) : конец ) , g.m , g.prim_poly ) ; _ _       конец% Добавить ведущие нулифункция  xpad = площадку ( 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 ( Икс ) / Е ( Икс ) = П ( Икс ) = 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 ( Икс ) / Е ( Икс ) = П ( Икс ) = 003 Икс ² + 002 Икс + 001

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

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

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

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

Примечания

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

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

1. Рид и Соломон (1960)
2. Горенштейн, Д.; Цирлер, Н. (июнь 1961 г.). «Класс циклических линейных кодов, исправляющих ошибки в символах p^m». Дж. СИАМ . 9 (2): 207–214. дои : 10.1137/0109020. JSTOR  2098821.
3. Петерсон, В. Уэсли (1961). Коды исправления ошибок . МТИ Пресс. ОСЛК  859669631.
4. Петерсон, В. Уэсли; Уэлдон, Э.Дж. (1996) [1972]. Коды исправления ошибок (2-е изд.). МТИ Пресс. ISBN 978-0-585-30709-1. ОСЛК  45727875.
5. Сугияма, Ю.; Касахара, М.; Хирасава, С.; Намекава, Т. (1975). «Метод решения ключевого уравнения для декодирования кодов Гоппы». Информация и контроль . 27 (1): 87–99. дои : 10.1016/S0019-9958(75)90090-X .
6. Гао, Шухун (январь 2002 г.), Новый алгоритм декодирования кодов Рида-Соломона (PDF) , Клемсон
7. Имминк, KAS (1994), «Коды Рида – Соломона и компакт-диск», в Wicker, Стивен Б.; Бхаргава, Виджай К. (ред.), Коды Рида-Соломона и их приложения , IEEE Press , ISBN 978-0-7803-1025-4
8. Хагенауэр, Дж.; Оффер, Э.; Папке, Л. (1994). «11. Сопоставление декодеров Витерби и декодеров Рида-Соломона в каскадной системе». Коды Рида-Соломона и их приложения . IEEE Пресс. п. 433. ИСБН 9780470546345. OCLC  557445046.
9. Эндрюс, Канзас; Дивсалар, Д.; Долинар, С.; Хэмкинс, Дж.; Джонс, ЧР; Поллара, Ф. (2007). «Разработка турбо-кодов и кодов LDPC для приложений дальнего космоса» (PDF) . Труды IEEE . 95 (11): 2142–56. doi :10.1109/JPROC.2007.905132. S2CID  9289140.
10. См., например, Лин и Костелло (1983, стр. 171).
11. «Аналитические выражения, используемые в беркодировании и BERTool». Архивировано из оригинала 01 февраля 2019 г. Проверено 1 февраля 2019 г.
12. Пфендер, Флориан; Циглер, Гюнтер М. (сентябрь 2004 г.), «Целующиеся числа, упаковки сфер и некоторые неожиданные доказательства» (PDF) , Уведомления Американского математического общества , 51 (8): 873–883, в архиве (PDF) с оригинала на 09 мая 2008 г. , получено 28 сентября 2009 г.. Объясняет теорему Дельсарта-Гёталя-Зейделя, используемую в контексте кода исправления ошибок для компакт-диска .
13. Д. Горенштейн и Н. Цирлер, «Класс циклических линейных кодов с исправлением ошибок в символах p^m», J. SIAM, vol. 9, стр. 207–214, июнь 1961 г.
14. Коды, исправляющие ошибки Уэсли Петерсона, 1961 г.
15. Шу Линь и Дэниел Дж. Костелло-младший, «Кодирование контроля ошибок», второе издание, стр. 255–262, 1982, 2004 г.
16. Гурусвами, В.; Судан, М. (сентябрь 1999 г.), «Улучшенное декодирование кодов Рида – Соломона и кодов алгебраической геометрии», IEEE Transactions on Information Theory , 45 (6): 1757–1767, CiteSeerX 10.1.1.115.292 , doi : 10.1109/18.782097 
17. Бракензик, Джошуа; Гопи, Шивакант; Макам, Вису (2 июня 2023 г.). «Общие коды Рида-Соломона обеспечивают способность декодирования списка». Материалы 55-го ежегодного симпозиума ACM по теории вычислений . STOC 2023. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники: 1488–1501. дои : 10.1145/3564246.3585128. ISBN 978-1-4503-9913-5.
18. Го, Зею; Чжан, Зихан. «Случайно проколотые коды Рида-Соломона достигают способности декодирования списка по алфавитам полиномиального размера». 64-й ежегодный симпозиум IEEE по основам информатики , 2023 г. FOCS 2023, Санта-Крус, Калифорния, США, 2023: 164–176. doi : 10.1109/FOCS57990.2023.00019. ISBN 979-8-3503-1894-4.
19. Альрабия, Омар; Гурусвами, Венкатесан; Ли, Рэй (18 августа 2023 г.), Случайно проколотые коды Рида-Соломона обеспечивают способность декодирования списка над полями линейного размера, doi : 10.48550/arXiv.2304.09445 , получено 8 февраля 2024 г.
20. Кеттер, Ральф; Варди, Александр (2003). «Алгебраическое декодирование кодов Рида – Соломона с мягким решением». Транзакции IEEE по теории информации . 49 (11): 2809–2825. CiteSeerX 10.1.1.13.2021 . дои : 10.1109/TIT.2003.819332. 
21. Франке, Стивен Дж.; Тейлор, Джозеф Х. (2016). «Декодер мягкого решения с открытым исходным кодом для кода Рида – Соломона JT65 (63,12)» (PDF) . QEX (май/июнь): 8–17. Архивировано (PDF) из оригинала 9 марта 2017 г. Проверено 7 июня 2017 г.

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

• Гилл, Джон (nd), Примечания EE387 № 7, Раздаточный материал № 28 (PDF) , Стэнфордский университет, заархивировано из оригинала (PDF) 30 июня 2014 г. , получено 21 апреля 2010 г.
• Хонг, Джонатан; Веттерли, Мартин (август 1995 г.), «Простые алгоритмы декодирования BCH» (PDF) , IEEE Transactions on Communications , 43 (8): 2324–33, doi : 10.1109/26.403765
• Лин, Шу; Костелло-младший, Дэниел Дж. (1983), Кодирование с контролем ошибок: основы и приложения , Прентис-Холл, ISBN 978-0-13-283796-5
• Мэсси, Дж.Л. (1969), «Синтез сдвиговых регистров и декодирование BCH» (PDF) , IEEE Transactions on Information Theory , IT-15 (1): 122–127, doi : 10.1109/tit.1969.1054260, S2CID  9003708
• Петерсон, Уэсли В. (1960), «Процедуры кодирования и исправления ошибок для кодов Бозе-Чаудхури», IRE Transactions on Information Theory , 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 Transactions on Information Theory , 11 (4): 549–557, doi : 10.1109/TIT.1965.1053825
• Кеттер, Ральф (2005), Коды Рида – Соломона, MIT Lecture Notes 6.451 (Видео), заархивировано из оригинала 13 марта 2013 г.
• МакВильямс, Ф.Дж.; Слоан, NJA (1977), Теория кодов, исправляющих ошибки, Северная Голландия, ISBN 978-0-444-85010-2
• Рид, Ирвинг С .; Чен, Сюэмин (2012) [1999], Кодирование с контролем ошибок для сетей передачи данных, Springer, ISBN 9781461550051

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

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

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

Реализации

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