Введение

Коды коррекции ошибок

Коды Рида — Соломона — это группа кодов коррекции ошибок, представленных Ирвингом С. Ридом и Густавом Соломоном в 1960 году. Они находят широкое применение, включая потребительские технологии, такие как MiniDisc, CD, 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 году Ирвингом С. Ридом и Густавом Соломоном, которые в то время были сотрудниками лаборатории MIT Линкольн. Их основополагающая статья называлась «Полиномиальные коды над определенными конечными полями». Изначальная схема кодирования, описанная в статье Рида и Соломона, использовала переменный полином, основанный на кодируемом сообщении, при этом кодировщик и декодер знали только фиксированный набор значений (точек вычисления). Оригинальный теоретический декодер генерировал потенциальные полиномы на основе подмножеств из k (длина некодируемого сообщения) из n (длина закодированного сообщения) значений принятого сообщения, выбирая наиболее часто встречающийся полином в качестве правильного, что было непрактично для всех случаев, кроме самых простых. Первоначально это было решено путем изменения исходной схемы на схему, подобную коду BCH, основанную на фиксированном полиноме, известном как кодировщику, так и декодеру, но позже были разработаны практические декодеры на основе исходной схемы, хотя и более медленные, чем схемы BCH. В результате существует два основных типа кодов Рида — Соломона: использующие исходную схему кодирования и использующие схему кодирования BCH. Также в 1960 году Дэниел Горенштейн и Нил Зиерлер описали практический декодер с фиксированным полиномом для кодов BCH в отчете лаборатории MIT Линкольн, подготовленном Зиерлером в январе 1960 года, а затем в статье, опубликованной в июне 1961 года. Декодер Горенштейна — Зиерлера и связанные с ним работы по кодам BCH описаны в книге «Коды, исправляющие ошибки» У. Уэсли Петерсона (1961). К 1963 году (или, возможно, раньше) Дж. Дж. Стоун (и другие) осознали, что коды Рида — Соломона могут использовать схему BCH с фиксированным образующим полиномом, что делает такие коды особым классом кодов BCH, но коды Рида — Соломона, основанные на исходной схеме кодирования, не являются классом кодов BCH и, в зависимости от набора точек вычисления, даже не являются циклическими кодами. В 1969 году Элвин Берлекэмп и Джеймс Мэсси разработали улучшенный декодер схемы BCH, который с тех пор известен как алгоритм декодирования Берлекампа — Мэсси. В 1975 году Ясуо Сугияма разработал другой улучшенный декодер схемы BCH, основанный на расширенном алгоритме Евклида. В 1977 году коды Рида — Соломона были реализованы в программе «Вояджер» в виде каскадных кодов коррекции ошибок. Первое коммерческое применение в серийно выпускаемых потребительских товарах появилось в 1982 году с компакт-диском, где используются два чередующихся кода Рида — Соломона. Сегодня коды Рида — Соломона широко используются в устройствах цифрового хранения и стандартах цифровой связи, хотя они постепенно заменяются кодами Боуза — Чоудхури — Хоккенгема (BCH). Например, коды Рида — Соломона используются в стандарте цифрового видеовещания DVB-S в сочетании со внутренним сверточным кодом, а коды BCH используются с LDPC в его преемнике DVB-S2. В 1986 году был разработан декодер исходной схемы, известный как алгоритм Берлекампа — Уэлча. В 1996 году Мадху Судан и другие разработали варианты декодеров исходной схемы, называемые декодерами списков или мягкими декодерами, и работы по этим типам декодеров продолжаются — см. алгоритм декодирования списков Гурусвами — Судана. В 2002 году Шухон Гао разработал еще один декодер исходной схемы, основанный на расширенном алгоритме Евклида.

Штрих-код

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

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

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

Замечания

Дизайнерам не требуется использовать "естественные" размеры блоков кода Рида — Соломона. Техника, известная как "укорачивание", позволяет получить код меньшего размера любой нужной длины из большего кода. Например, широко используемый код (255,223) можно преобразовать в код (160,128), заполнив неиспользуемую часть исходного блока 95 двоичными нулями и не передавая их. В декодере та же часть блока локально заполняется двоичными нулями. Теорема Дельсарта — Гётеальса — Зейделя иллюстрирует пример применения укороченных кодов Рида — Соломона. Наряду с укорачиванием, техника, известная как "пунктирование", позволяет опускать некоторые из закодированных символов четности.

Декодеры BCH

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

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

Даниэль Горенштейн и Нил Зилер разработали декодер, который был описан в отчете Лаборатории Линкольна МТИ, составленном Зилером в январе 1960 года, а затем в научной статье в июне 1961 года. Декодер Горенштейна — Зилера и связанные с ним исследования кодов БХК описаны в книге «Коды, исправляющие ошибки» У. Уэсли Петерсона (1961).

Декодирование синдрома

Декодер начинает с вычисления значения многочлена в точках We. Результаты этого вычисления мы называем "синдромами", Sj. Они определяются как:

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

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

Используйте коэффициенты Λi, найденные на последнем этапе, для построения полинома определения местоположения ошибок. Корни полинома определения местоположения ошибок можно найти методом полного перебора. Локаторы ошибок Xk являются величинами, обратными этим корням. Порядок коэффициентов полинома определения местоположения ошибок можно изменить на обратный, в этом случае корни полученного полинома будут являться локаторами ошибок (а не обратными величинами к ним). Алгоритм поиска Чьена является эффективной реализацией этого шага.

Вычислить значения ошибок

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

Вычислить местоположение ошибок

Вычислите ik, взяв логарифм Xk по заданному основанию. Обычно это делается с использованием предварительно вычисленной таблицы поиска.

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

Наконец, e(x) формируется на основе ik и eik, а затем вычитается из r(x) для восстановления исходного отправленного сообщения s(x) с исправленными ошибками.

Декодер Berlekamp Massey

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

и затем корректирует Λ(x) и e таким образом, чтобы пересчитанное Δ стало равным нулю. В статье «Алгоритм Берлекампа — Масси» содержится подробное описание процедуры. В следующем примере C(x) используется для обозначения Λ(x).

Декодер с использованием дискретной трансформации Фурье

Для декодирования может использоваться дискретное преобразование Фурье. Чтобы избежать конфликта с названиями синдромов, обозначим 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) совпадают с синдромами: используйте коэффициенты от до в качестве синдромов (они одинаковы) и сгенерируйте полином определения ошибок, используя методы из любого из вышеуказанных декодеров. Пусть v – количество ошибок. Сформируйте E(x), используя известные коэффициенты от до , полином определения ошибок, и следующие формулы.

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

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

Ограничение Синглтона утверждает, что минимальное расстояние d линейного блочного кода размера (n,k) ограничено сверху значением n − k + 1. Расстояние d традиционно понималось как предел возможности коррекции ошибок, равный ⌊(d−1) / 2⌋. Код Рида — Соломона достигает этого предела с точностью до равенства и, следовательно, может исправлять до ⌊(n−k) / 2⌋ ошибок. Однако эта граница коррекции ошибок не является точной. В 1999 году Мадху Судан и Венкатесан Гурусвами из MIT опубликовали работу "Улучшенное декодирование кодов Рида — Соломона и алгебраической геометрии", представив алгоритм, позволяющий исправлять ошибки, превышающие половину минимального расстояния кода. Алгоритм применим к кодам Рида — Соломона и, в более общем случае, к алгебраическим геометрическим кодам. Этот алгоритм выдает список кодовых слов (является алгоритмом декодирования списка) и основан на интерполяции и факторизации многочленов над конечным полем и его расширениями. В 2023 году, опираясь на три значимых исследования, теоретики кодирования показали, что коды Рида — Соломона, определенные на случайных точках вычисления, могут фактически достичь пропускной способности декодирования списка (до n−k ошибок) для алфавитов линейного размера с высокой вероятностью. Однако этот результат носит комбинаторный, а не алгоритмический характер.

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

Методы алгебраического декодирования, описанные выше, являются методами жесткого решения, то есть для каждого символа принимается однозначное решение о его значении. Например, декодер может связать с каждым символом дополнительное значение, отражающее уверенность демодулятора канала в правильности этого символа. Разработка кодов LDPC и турбокодов, использующих итеративные методы декодирования с применением вероятностной информации для достижения характеристик исправления ошибок, близких к теоретическому пределу, стимулировала интерес к применению декодирования с использованием вероятностной информации к традиционным алгебраическим кодам. В 2003 году Ральф Кёттер и Александр Варди представили алгоритм алгебраического декодирования списка с использованием вероятностной информации, работающий за полиномиальное время для кодов Рида — Соломона, который базировался на работах Судана и Гурусвами. В 2016 году Стивен Дж. Фрэнк и Джозеф Х. Тейлор опубликовали новый декодер с использованием вероятностной информации.

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

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

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

описал теоретический декодер, который исправляет ошибки, находя наиболее вероятный полином сообщения. Декодер знает только набор значений и метод кодирования, использованный для генерации последовательности значений кодового слова. Оригинальное сообщение, полином и любые ошибки неизвестны. Процедура декодирования может использовать метод, подобный интерполяции Лагранжа, применяемый к различным подмножествам из n значений кодового слова, выбираемым по k элементов, для многократного получения потенциальных полиномов, пока не будет получено достаточное количество совпадающих полиномов, чтобы с уверенностью исключить ошибки в принятом кодовом слове. Как только полином определен, любые ошибки в кодовом слове могут быть исправлены путем пересчета соответствующих значений кодового слова. К сожалению, во всех случаях, кроме самых простых, количество подмножеств слишком велико, что делает алгоритм непрактичным. Число подмножеств равно биномиальному коэффициенту, , и даже для кодов небольшого размера это число недостижимо. Для кода, способного исправлять 3 ошибки, наивный теоретический декодер должен был бы проанализировать 359 миллиардов подмножеств.

Декодер Berlekamp Welch

В 1986 году был разработан декодер, известный как алгоритм Берлекампа — Уэлча, способный восстановить исходный полином сообщения, а также полином "локализатора" ошибок, который обнуляется для входных значений, соответствующих ошибкам, при временной сложности , где — количество значений в сообщении. Восстановленный полином затем используется для восстановления (при необходимости пересчета) исходного сообщения.

Декодер Гао

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