Коды Рида-Соломона представляют собой группу кодов , исправляющих ошибки , которые были введены Ирвингу С. Рид и Густава Соломона в 1960 году [1] Они имеют множество приложений, наиболее известными из которых включают в себя потребительские технологии , такие как минидисков , компакт - диски , DVD - диски , Диски Blu-ray , QR-коды , технологии передачи данных, такие как DSL и WiMAX , системы вещания , такие как спутниковая связь, DVB и ATSC , а также системы хранения, такие как RAID 6.
Коды Рида – Соломона | |
---|---|
Названный в честь | Ирвинг С. Рид и Гюстав Соломон |
Классификация | |
Иерархия | Линейный блочный код Полиномиальный код Код Рида – Соломона |
Длина блока | п |
Длина сообщения | k |
Расстояние | п - к + 1 |
Размер алфавита | q = p m ≥ n ( p простое) Часто n = q - 1. |
Обозначение | [ n , k , n - k + 1] q- код |
Алгоритмы | |
Берлекамп-Мэсси Евклидов и др. | |
Характеристики | |
Разделимый код максимального расстояния | |
Коды Рида – Соломона работают с блоком данных, рассматриваемым как набор элементов с конечным полем, называемых символами. Коды Рида – Соломона способны обнаруживать и исправлять множественные символьные ошибки. Добавляя т = п - K проверочных символов в данных, код Рида-Соломона может обнаружить (но не правильно) любое сочетание до и в том числе т ошибочных символов, или найти и исправить вплоть до ⌊ т / 2⌋ ошибочными символы в неизвестных местах. В качестве кода стирания он может исправлять до t стираний включительно в местах, которые известны и предоставлены алгоритму, или он может обнаруживать и исправлять комбинации ошибок и стираний. Коды Рида – Соломона также подходят в качестве кодов с множественными пакетами исправления битовых ошибок, поскольку последовательность из b + 1 последовательных битовых ошибок может повлиять не более чем на два символа размера b . Выбор t остается на усмотрение разработчика кода и может выбираться в широких пределах.
Существует два основных типа кодов Рида-Соломона - исходное представление и представление BCH - причем представление BCH является наиболее распространенным, поскольку декодеры представления BCH быстрее и требуют меньше памяти, чем декодеры исходного представления.
История
Коды Рида – Соломона были разработаны в 1960 году Ирвингом С. Ридом и Густавом Соломоном , которые в то время были сотрудниками лаборатории Линкольна Массачусетского технологического института . Их основополагающая статья называлась «Полиномиальные коды над некоторыми конечными полями». ( Рид и Соломон, 1960 ). Исходная схема кодирования, описанная в статье Рида и Соломона, использовала переменный многочлен, основанный на сообщении, которое должно быть закодировано, где кодировщику и декодеру известен только фиксированный набор значений (точек оценки), которые должны быть закодированы. Первоначальный теоретический декодер генерировал потенциальные многочлены на основе подмножеств k (длина незашифрованного сообщения) из n (длина закодированного сообщения) значений полученного сообщения, выбирая наиболее популярный многочлен в качестве правильного, что было непрактично для всех, кроме простейшего из случаи. Первоначально это было решено путем изменения исходной схемы на схему, подобную коду BCH , основанную на фиксированном полиноме, известном как кодеру, так и декодеру, но позже были разработаны практические декодеры на основе исходной схемы, хотя и более медленные, чем схемы BCH. Результатом этого является то, что существует два основных типа кодов Рида-Соломона: те, которые используют исходную схему кодирования, и те, которые используют схему кодирования BCH.
Также в 1960 году практический фиксированный полиномиальный декодер для кодов BCH, разработанный Дэниелом Горенштейном и Нилом Цирлером, был описан в отчете лаборатории Линкольна Массачусетского технологического института, опубликованном Цирлером в январе 1960 года, а затем в статье в июне 1961 года. [2] Декодер Горенштейна – Цирлера и соответствующая работа над кодами BCH описана в книге W. Wesley Peterson (1961) « Коды исправления ошибок» . [3] К 1963 году (или, возможно, раньше) Дж. Дж. Стоун (и другие) осознали, что коды Рида-Соломона могут использовать схему BCH с использованием фиксированного порождающего полинома, что делает такие коды особым классом кодов BCH, [4] но Рид Соломон коды, основанные на исходной схеме кодирования, не являются классом кодов BCH, и в зависимости от набора точек оценки они даже не являются циклическими кодами .
В 1969 году Элвин Берлекамп и Джеймс Мэсси разработали усовершенствованный декодер схемы BCH , который с тех пор известен как алгоритм декодирования Берлекампа-Месси .
В 1975 году Ясуо Сугияма разработал еще один улучшенный декодер схемы BCH, основанный на расширенном алгоритме Евклида . [5]
В 1977 году коды Рида – Соломона были реализованы в программе « Вояджер» в виде составных кодов исправления ошибок . Первое коммерческое применение в массовых потребительских товарах появилось в 1982 году с компакт-диском , где используются два чередующихся кода Рида – Соломона. Сегодня коды Рида-Соломона широко применяются в цифровых устройствах хранения и стандартах цифровой связи , хотя они постепенно заменяются более современными кодами контроля четности с низкой плотностью (LDPC) или турбокодами . Например, коды Рида – Соломона используются в стандарте цифрового видеовещания (DVB) DVB-S , но коды LDPC используются в его преемнике, DVB-S2 .
В 1986 году был разработан оригинальный схемный декодер, известный как алгоритм Берлекампа – Велча .
В 1996 году Мадху Судан и другие разработали варианты декодеров исходной схемы, называемые декодерами списков или программными декодерами, и работа над этими типами декодеров продолжается - см. Алгоритм декодирования списка Гурусвами-Судан .
В 2002 году Шухонг Гао разработал еще одну оригинальную схему декодирования, основанную на расширенном алгоритме Евклида Gao_RS.pdf .
Приложения
Хранилище данных
Кодирование Рида – Соломона очень широко используется в системах хранения данных для исправления пакетных ошибок, связанных с дефектами носителя.
Кодирование Рида – Соломона - ключевой компонент компакт-диска . Это было первое использование кодирования с сильной коррекцией ошибок в массовом потребительском продукте, и DAT и DVD используют аналогичные схемы. В компакт-диске два уровня кодирования Рида – Соломона, разделенные 28-канальным сверточным перемежителем, дают схему, называемую перекрестным чередованием кодирования Рида – Соломона ( CIRC ). Первым элементом декодера CIRC является относительно слабый внутренний (32,28) код Рида – Соломона, сокращенный от кода (255,251) с 8-битовыми символами. Этот код может исправить до 2-х байтовых ошибок на 32-байтовый блок. Что еще более важно, он помечает как стирающие любые неисправимые блоки, т. Е. Блоки с более чем 2-байтовыми ошибками. Декодированные 28-байтовые блоки с индикацией стирания затем распространяются обращенным перемежителем на разные блоки внешнего кода (28,24). Благодаря обращенному чередованию стертый 28-байтовый блок внутреннего кода становится одним стертым байтом в каждом из 28 внешних кодовых блоков. Внешний код легко исправляет это, поскольку он может обрабатывать до 4 таких стираний на блок.
Результатом является CIRC, который может полностью исправить пакеты ошибок размером до 4000 бит или около 2,5 мм на поверхности диска. Этот код настолько силен, что большинство ошибок при воспроизведении компакт-дисков почти наверняка вызваны ошибками отслеживания, которые приводят к смещению трека лазера, а не пакетами неисправимых ошибок. [6]
DVD используют аналогичную схему, но с гораздо большими блоками, внутренним кодом (208,192) и внешним кодом (182,172).
Исправление ошибок Рида – Соломона также используется в файлах архива, которые обычно публикуются вместе с мультимедийными файлами на USENET . Служба распределенного онлайн-хранилища Wuala (прекращенная в 2015 году) также использовалась для использования Reed-Solomon при разделении файлов.
Штрих-код
Почти все двумерные штрих-коды, такие как PDF-417 , MaxiCode , Datamatrix , QR Code и Aztec Code, используют коррекцию ошибок Рида – Соломона, чтобы обеспечить правильное считывание, даже если часть штрих-кода повреждена. Когда сканер штрих-кода не может распознать символ штрих-кода, он будет рассматривать его как стирание.
Кодирование Рида-Соломона менее распространено в одномерных штрих-кодах, но используется в символике PostBar .
Передача информации
Специализированные формы кодов Рида-Соломон, в частности Коши -rs и Вандермонд -rs, может быть использованы для преодоления ненадежного характера передачи данных по стиранию каналов . Процесс кодирования предполагает код RS ( N , K ), который приводит к N кодовым словам длиной N символов, каждое из которых хранит K символов данных, которые генерируются, которые затем отправляются по каналу стирания.
Любой комбинации K кодовых слов, полученных на другом конце, достаточно для восстановления всех N кодовых слов. Кодовая скорость обычно устанавливается равной 1/2, если вероятность стирания канала не может быть адекватно смоделирована и не считается меньшей. В заключение, N обычно составляет 2 К , что означает, что по крайней мере половина всех отправленных кодовых слов должна быть принята, чтобы восстановить все отправленные кодовые слова.
Коды Рида-Соломона также используются в XDSL системах и CCSDS «s спецификации протокола космической связи в форме упреждающей коррекции ошибок .
Космическая передача
Одним из важных применений кодирования Рида-Соломона было кодирование цифровых изображений, отправленных обратно программой « Вояджер» .
Вояджер представил кодирование Рида-Соломона, объединенное со сверточными кодами , практика, которая с тех пор стала очень широко распространенной в дальнем космосе и спутниковой связи (например, прямое цифровое вещание).
Декодеры Витерби обычно генерируют ошибки короткими пакетами. Исправление этих пакетных ошибок лучше всего выполнять с помощью коротких или упрощенных кодов Рида – Соломона.
Современные версии конкатенированного сверточного кодирования с декодированием Рида – Соломона / Витерби использовались и используются в миссиях Mars Pathfinder , Galileo , Mars Exploration Rover и Cassini , где они работают в пределах примерно 1–1,5 дБ от предельного значения - пропускной способности Шеннона .
Эти сцепленные коды теперь заменяются более мощными турбокодами :
Годы | Код | Миссия (и) |
---|---|---|
1958 – настоящее время | Некодированный | Explorer, Mariner, многие другие |
1968–1978 | сверточные коды (СС) (25, 1/2) | Пионер, Венера |
1969–1975 | Код Рида-Мюллера (32, 6) | Моряк, Викинг |
1977 – настоящее время | Двоичный код Голея | Путешественник |
1977 – настоящее время | RS (255, 223) + CC (7, 1/2) | Вояджер, Галилей и многие другие |
1989–2003 гг. | RS (255, 223) + CC (7, 1/3) | Путешественник |
1958 – настоящее время | RS (255, 223) + CC (14, 1/4) | Галилео |
1996 – настоящее время | RS + CC (15, 1/6) | Кассини, Марс-следопыт, другие |
2004 – настоящее время | Турбокоды [nb 1] | Посланник, стерео, ТОиР, другие |
оценка 2009 г. | Коды LDPC | Созвездие, MSL |
Конструкции
Код Рида – Соломона на самом деле представляет собой семейство кодов, где каждый код характеризуется тремя параметрами: размером алфавита q , длиной блока n и длиной сообщения k, где k
Исходный взгляд Рида и Соломона: кодовое слово как последовательность значений
Существуют разные процедуры кодирования для кода Рида – Соломона, и, следовательно, существуют разные способы описания набора всех кодовых слов. В исходной точке зрения Рида и Соломона (1960) каждое кодовое слово кода Рида – Соломона представляет собой последовательность значений функций полинома степени меньше k . Чтобы получить кодовое слово кода Рида – Соломона, символы сообщения (каждый в алфавите размера q) обрабатываются как коэффициенты полинома p степени меньше k над конечным полем F с q элементами. В свою очередь, многочлен p вычисляется в n ≤ q различных точках.поля F , а последовательность значений - соответствующее кодовое слово. Обычный выбор для набора точек оценки включает {0, 1, 2, ..., n - 1}, {0, 1, α , α 2 , ..., α n −2 } или для n < q , {1, α , & alpha ; 2 , ..., α п -1 }, ..., где α представляет собой примитивный элемент из F .
Формально набор кодовых слов кода Рида – Соломона определяется следующим образом:
Поскольку любые два различных многочлена степени меньше согласен в лучшем случае точек, это означает, что любые два кодовых слова кода Рида – Соломона не совпадают по крайней мере в позиции. Кроме того, есть два многочлена, которые согласуются вточки, но не равны, и, таким образом, расстояние кода Рида – Соломона точно равно. Тогда относительное расстояние равно, где это ставка. Этот компромисс между относительным расстоянием и скоростью является асимптотически оптимальным, поскольку, согласно границе Синглтона , каждый код удовлетворяет. Код Рида – Соломона, являющийся кодом, позволяющим достичь этого оптимального компромисса, принадлежит к классу кодов с разделением на максимальное расстояние .
В то время как количество различных многочленов степени меньше k и количество разных сообщений равны, и, таким образом, каждое сообщение может быть однозначно сопоставлено с таким многочленом, есть разные способы сделать это кодирование. Первоначальная конструкция Рида и Соломона (1960) интерпретирует сообщение x как коэффициенты многочлена p , тогда как последующие конструкции интерпретируют сообщение как значения многочлена в первых k точках.и получить полином p путем интерполяции этих значений полиномом степени меньше k . Последняя процедура кодирования, хотя и немного менее эффективна, имеет то преимущество, что она дает систематический код , то есть исходное сообщение всегда содержится как подпоследовательность кодового слова.
Простая процедура кодирования: сообщение как последовательность коэффициентов.
В первоначальной конструкции Рида и Соломона (1960) сообщение отображается в полином с участием
Кодовое слово получается путем оценки в разные точки поля . Таким образом, классическая функция кодирования для кода Рида – Соломона определяется следующим образом:
Эта функция является линейным отображением , т. е. удовлетворяет для следующего -матрица с элементами из :
Эта матрица является транспонированной матрицей Вандермонда над. Другими словами, код Рида – Соломона является линейным кодом , и в классической процедуре кодирования его порождающая матрица имеет вид.
Систематическая процедура кодирования: сообщение как начальная последовательность значений.
Существует альтернативная процедура кодирования, которая также производит код Рида – Соломона, но делает это систематическим образом. Здесь отображение из сообщения к многочлену работает иначе: полином теперь определяется как единственный многочлен степени меньше, чем такой, что
- справедливо для всех .
Чтобы вычислить этот многочлен из , можно использовать интерполяцию Лагранжа . Как только он был найден, он оценивается в других точках.поля. Альтернативная функция кодирования для кода Рида – Соломона опять же просто последовательность значений:
С первого записи каждого кодового слова совпадают с , эта процедура кодирования действительно носит систематический характер . Поскольку интерполяция Лагранжа является линейным преобразованием,является линейным отображением. Фактически у нас есть, где
Дискретное преобразование Фурье и его обратное
Дискретное преобразование Фурье , по существу , такой же , как процедура кодирования; он использует полином генератора p (x) для отображения набора точек оценки в значения сообщения, как показано выше:
Обратное преобразование Фурье может использоваться для преобразования безошибочного набора из n < q значений сообщения обратно в кодирующий полином из k коэффициентов с ограничением, что для того, чтобы это работало, набор точек оценки, используемых для кодирования сообщения, должен - набор возрастающих степеней α :
Однако интерполяция Лагранжа выполняет то же преобразование без ограничения на набор точек оценки или требования безошибочного набора значений сообщения и используется для систематического кодирования и на одном из этапов декодера Gao .
Представление BCH: кодовое слово как последовательность коэффициентов
В этом представлении сообщение интерпретируется как коэффициенты многочлена . Отправитель вычисляет связанный многочлен степени где и отправляет многочлен . Полином строится путем умножения полинома сообщения , имеющий степень , с образующим полиномом степени это известно как отправителю, так и получателю. Образующий полином определяется как многочлен, корни которого являются последовательными степенями примитива поля Галуа
Для "узкого смысла кода", .
Систематическая процедура кодирования
Процедура кодирования для представления кодов Рида – Соломона BCH может быть изменена для получения систематической процедуры кодирования , в которой каждое кодовое слово содержит сообщение в качестве префикса и просто добавляет символы с исправлением ошибок в качестве суффикса. Здесь вместо отправки, кодировщик строит переданный многочлен такие, что коэффициенты при наибольшие одночлены равны соответствующим коэффициентам при , а младшие коэффициенты выбраны именно так, что делится на . Тогда коэффициенты при являются подпоследовательностью (а именно префиксом) коэффициентов . Чтобы получить в целом систематический код, мы строим многочлен сообщения интерпретируя сообщение как последовательность его коэффициентов.
Формально конструкция осуществляется путем умножения от чтобы освободить место для отметьте символы, разделив этот продукт на чтобы найти остаток, а затем компенсировать этот остаток путем его вычитания. В контрольные символы создаются путем вычисления остатка :
Остальные имеют степень не выше , а коэффициенты при в полиноме равны нулю. Следовательно, следующее определение кодового слова обладает тем свойством, что первые коэффициенты идентичны коэффициентам :
В результате кодовые слова действительно являются элементами , то есть делятся на порождающий полином : [9]
Характеристики
Код Рида – Соломона представляет собой код [ n , k , n - k + 1]; другими словами, это линейный блочный код длины n (над F ) с размерностью k и минимальным расстоянием Хэмминга Код Рида – Соломона оптимален в том смысле, что минимальное расстояние имеет максимальное значение, возможное для линейного кода размера ( n , k ); это известно как граница Синглтона . Такой код также называется кодом с разделением на максимальное расстояние (MDS) .
Исправляющая способность кода Рида-Соломона определяется его минимальным расстоянием или, что эквивалентно, , мера избыточности в блоке. Если расположение символов ошибки заранее не известно, то код Рида – Соломона может исправить доошибочные символы, т. е. он может исправить вдвое меньше ошибок, чем есть избыточные символы, добавленные в блок. Иногда местоположения ошибок известны заранее (например, «дополнительная информация» в отношениях сигнал / шум демодулятора ) - это называется стиранием . Код Рида – Соломона (как и любой MDS-код ) может исправить вдвое больше стираний, чем ошибок, и любая комбинация ошибок и стираний может быть исправлена до тех пор, пока выполняется соотношение 2 E + S ≤ n - k , где количество ошибок и - количество стираний в блоке.
Теоретическая граница ошибки может быть описана следующей формулой для канала AWGN для FSK : [10]
и для других схем модуляции:
где , , , - частота ошибок символа в случае некодированного AWGN и - порядок модуляции.
Для практического использования кодов Рида – Соломона обычно используется конечное поле с участием элементы. В этом случае каждый символ может быть представлен как-битовое значение. Отправитель отправляет точки данных как закодированные блоки, а количество символов в закодированном блоке равно. Таким образом, код Рида – Соломона, работающий с 8-битными символами, имеетсимволов на блок. (Это очень популярное значение из-за преобладания байт-ориентированных компьютерных систем.) Число, с участием , символов данных в блоке является параметром конструкции. Часто используемый код кодирует восьмибитовых символов данных плюс 32 восьмибитовых символа четности в -символьный блок; это обозначается как код и способен исправлять до 16 ошибок символа в блоке.
Обсуждаемые выше свойства кода Рида – Соломона делают его особенно подходящим для приложений, в которых ошибки возникают в пакетном режиме . Это связано с тем, что для кода не имеет значения, сколько битов в символе ошибочно - если несколько битов в символе повреждены, это считается только одной ошибкой. И наоборот, если поток данных характеризуется не пакетами ошибок или выпадениями, а случайными одиночными ошибками, код Рида – Соломона обычно является плохим выбором по сравнению с двоичным кодом.
Код Рида – Соломона, как и сверточный код , является прозрачным кодом. Это означает, что если символы канала были инвертированы где-то вдоль линии, декодеры все равно будут работать. Результатом будет инверсия исходных данных. Однако код Рида – Соломона теряет прозрачность при сокращении кода. «Недостающие» биты в сокращенном коде должны быть заполнены нулями или единицами, в зависимости от того, дополняются ли данные или нет. (Другими словами, если символы инвертированы, то заполнение нулями должно быть инвертировано в заполнение одним.) По этой причине обязательно, чтобы смысл данных (т.е. истинный или дополняемый) был разрешен до декодирования Рида – Соломона.
Будет ли код Рида-Соломона является циклическим или нет , зависит от тонких деталей конструкции. В исходной точке зрения Рида и Соломона, где кодовые слова являются значениями полинома, можно выбрать последовательность точек оценки таким образом, чтобы сделать код циклическим. В частности, еслиэто примитивный корень поля, то по определению все ненулевые элементы принять форму для , где . Каждый полином над рождает кодовое слово . Поскольку функция также является полиномом той же степени, эта функция порождает кодовое слово ; посколькувыполняется, это кодовое слово является циклическим сдвигом влево исходного кодового слова, полученным из. Таким образом, выбор последовательности примитивных корневых степеней в качестве точек оценки делает исходное представление кода Рида – Соломона циклическим . Коды Рида – Соломона в представлении BCH всегда циклические, потому что коды BCH цикличны .
Замечания
От разработчиков не требуется использовать «естественные» размеры блоков кода Рида – Соломона. Метод, известный как «сокращение», может производить меньший код любого желаемого размера из большего кода. Например, широко используемый код (255,223) можно преобразовать в код (160,128), добавив в неиспользуемую часть исходного блока 95 двоичных нулей и не передав их. В декодере та же часть блока загружается локально двоичными нулями. Теорема Дельсарта – Гетальса – Зейделя [11] иллюстрирует пример применения сокращенных кодов Рида – Соломона. Параллельно с сокращением метод, известный как выкалывание, позволяет опускать некоторые закодированные символы четности.
Декодеры просмотра BCH
Декодеры, описанные в этом разделе, используют представление BCH кодового слова как последовательности коэффициентов. Они используют фиксированный полином генератора, известный как кодировщику, так и декодеру.
Декодер Петерсона – Горенштейна – Цирлера
Даниэль Горенштейн и Нил Цирлер разработали декодер, который был описан Цирлером в отчете лаборатории Линкольна Массачусетского технологического института в январе 1960 года, а затем в статье в июне 1961 года. [12] Декодер Горенштейна – Цирлера и связанные с ним работы по кодам BCH описаны в книга Уэсли Петерсона « Коды исправления ошибок » (1961). [13]
Формулировка
Переданное сообщение, , рассматривается как коэффициенты многочлена s ( x ):
В результате процедуры кодирования Рида-Соломона s ( x ) делится на порождающий полином g ( x ):
где α - первообразный корень.
Поскольку s ( x ) кратно генератору g ( x ), отсюда следует, что он «наследует» все свои корни:
Переданный полином искажается при передаче полиномом ошибок e ( x ), чтобы получить полученный полином r ( x ).
где e i - коэффициент для i-й степени x . Коэффициент e i будет равен нулю, если нет ошибки при этой степени x, и ненулевым, если есть ошибка. Если имеется ν ошибок при различных степенях i k функции x , то
Цель декодера - найти количество ошибок ( ν ), позиции ошибок ( i k ) и значения ошибок в этих позициях ( e i k ). Из них можно вычислить e ( x ) и вычесть из r ( x ), чтобы получить первоначально отправленное сообщение s ( x ).
Расшифровка синдрома
Декодер начинает с оценки полинома, полученного в определенных точках. Мы называем результаты этой оценки «синдромами», S j . Они определяются как:
Преимущество рассмотрения синдромов в том, что полином сообщения выпадает. Другими словами, синдромы относятся только к ошибке и не зависят от фактического содержимого передаваемого сообщения. Если все синдромы равны нулю, алгоритм останавливается на этом и сообщает, что сообщение не было повреждено при передаче.
Локаторы ошибок и значения ошибок
Для удобства определите локаторы ошибок X k и значения ошибок Y k как:
Тогда синдромы могут быть записаны в терминах этих локаторов ошибок и значений ошибок как
Это определение значений синдрома эквивалентно предыдущему, поскольку .
Синдромы дают систему n - k ≥ 2 ν уравнений с 2 ν неизвестными, но эта система уравнений нелинейна по X k и не имеет очевидного решения. Однако, если X k были известны (см. Ниже), то синдромные уравнения представляют собой линейную систему уравнений, которую можно легко решить для значений ошибки Y k .
Следовательно, проблема заключается в нахождении X k , потому что тогда была бы известна крайняя левая матрица, и обе части уравнения можно было бы умножить на обратное, что даст Y k
В варианте этого алгоритма, где местоположения ошибок уже известны (когда он используется в качестве кода стирания ), это конец. Места возникновения ошибок ( X k ) уже известны некоторым другим методом (например, в FM-передаче участки, где поток битов был нечетким или преодолен с помехами, можно определить с помощью частотного анализа с вероятностью). В этом сценарии до ошибки можно исправить.
Остальная часть алгоритма служит для поиска ошибок и потребует значений синдрома до , а не просто используется до сих пор. Вот почему необходимо добавить в 2 раза больше символов исправления ошибок, чем можно исправить, не зная их местоположения.
Многочлен локатора ошибок
Существует линейное рекуррентное соотношение, порождающее систему линейных уравнений. Решение этих уравнений идентифицирует эти места ошибки X k .
Определим полином локатора ошибок Λ ( x ) как
Нули Λ ( x ) являются обратными величинами. Это следует из приведенной выше конструкции обозначения произведения, поскольку если тогда один из умноженных членов будет равен нулю , в результате чего весь многочлен равен нулю.
Позволять быть любым целым таким, что . Умножьте обе стороны на и все равно будет ноль.
Суммируйте от k = 1 до ν, и оно все равно будет равно нулю.
Соберите каждый член в отдельную сумму.
Извлеките постоянные значения на которые суммирование не влияет.
Эти суммы теперь эквивалентны значениям синдромов, которые мы знаем и можем подставить! Следовательно, это сводится к
Вычитание с обеих сторон дает
Напомним, что j было выбрано как любое целое число от 1 до v включительно, и эта эквивалентность верна для любого и всех таких значений. Следовательно, у нас есть v линейных уравнений, а не одно. Таким образом, эта система линейных уравнений может быть решена относительно коэффициентов Λ i полинома определения ошибки:
Вышесказанное предполагает, что декодеру известно количество ошибок ν , но это количество еще не определено. Декодер PGZ не определяет ν напрямую, а скорее ищет его, пробуя последовательные значения. Декодер сначала принимает наибольшее значение для пробного ν и устанавливает линейную систему для этого значения. Если уравнения могут быть решены (т. Е. Определитель матрицы отличен от нуля), то пробным значением является количество ошибок. Если линейная система не может быть решена, тогда испытание ν сокращается на единицу, и исследуется следующая меньшая система. ( Гилл , стр. 35)
Найдите корни полинома локатора ошибок
Используйте коэффициенты Λ i, найденные на последнем шаге, для построения полинома местоположения ошибки. Корни полинома определения местоположения ошибки могут быть найдены путем исчерпывающего поиска. Локаторы ошибок X k являются обратными этим корням. Порядок коэффициентов полинома определения местоположения ошибки может быть изменен на обратный, и в этом случае корни этого обратного полинома являются локаторами ошибок. (не их обратные ). Поиск Chien - эффективное выполнение этого шага.
Рассчитайте значения ошибок
Как только локаторы ошибок X k известны, можно определить значения ошибок. Это можно сделать прямым решением для Y k в матрице уравнений ошибок, приведенной выше, или с помощью алгоритма Форни .
Рассчитайте места ошибок
Рассчитайте i k , взяв базу журналаиз X k . Обычно это делается с помощью предварительно вычисленной таблицы поиска.
Исправьте ошибки
Наконец, 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 + 2 x + 1 , то систематическое кодовое слово кодируется следующим образом.
Ошибки при передаче могут привести к получению этого сообщения.
Синдромы рассчитываются путем вычисления r при степенях α .
Использование исключения Гаусса :
- Λ (x) = 329 x 2 + 821 x + 001, с корнями x 1 = 757 = 3 −3 и x 2 = 562 = 3 −4
Коэффициенты можно поменять местами, чтобы получить корни с положительными показателями, но обычно это не используется:
- R (x) = 001 x 2 + 821 x + 329, с корнями 27 = 3 3 и 81 = 3 4
с журналом корней, соответствующим местоположениям ошибок (справа налево, ячейка 0 - последний член в кодовом слове).
Чтобы вычислить значения ошибок, примените алгоритм Форни .
- Ω (x) = S (x) Λ (x) mod x 4 = 546 x + 732
- Λ '(х) = 658 х + 821
- е 1 = −Ω (x 1 ) / Λ '(x 1 ) = 074
- е 2 = −Ω (x 2 ) / Λ '(x 2 ) = 122
Вычитание e 1 x 3 и e 2 x 4 из принятого полинома r воспроизводит исходное кодовое слово s .
Декодер Берлекампа – Месси
Алгоритм Берлекемп-Massey альтернативная итерационная процедура для нахождения локатора ошибки полинома. Во время каждой итерации он вычисляет расхождение на основе текущего экземпляра Λ (x) с предполагаемым количеством ошибок e :
а затем регулирует Λ ( x ) и e так, чтобы пересчитанное Δ было равно нулю. В статье « Алгоритм Берлекампа – Месси » подробно описана процедура. В следующем примере C ( x ) используется для представления Λ ( x ).
Пример
Используя те же данные, что и в приведенном выше примере Peterson Gorenstein Zierler:
п | S n +1 | d | C | B | б | м |
---|---|---|---|---|---|---|
0 | 732 | 732 | 197 х + 1 | 1 | 732 | 1 |
1 | 637 | 846 | 173 х + 1 | 1 | 732 | 2 |
2 | 762 | 412 | 634 х 2 + 173 х + 1 | 173 х + 1 | 412 | 1 |
3 | 925 | 576 | 329 х 2 + 821 х + 1 | 173 х + 1 | 412 | 2 |
Конечным значением C является многочлен локатора ошибок Λ ( x ).
Евклидов декодер
Другой итерационный метод вычисления как полинома локатора ошибок, так и полинома значения ошибки основан на адаптации Сугиямы расширенного алгоритма Евклида .
Определите S (x), Λ (x) и Ω (x) для t синдромов и e ошибок:
Ключевое уравнение:
Для t = 6 и e = 3:
Средние члены равны нулю из-за связи между Λ и синдромами.
Расширенный алгоритм Евклида может найти серию многочленов вида
- А я ( х ) S ( х ) + В я ( х ) х t = R я ( х )
где степень R уменьшается с увеличением i . Если степень R i ( x ) < t / 2, то
А я (х) = Λ (х)
В я (х) = -Q (х)
R i (x) = Ω (x).
B (x) и Q (x) сохранять не нужно, поэтому алгоритм становится:
- R −1 = x t
- R 0 = S (х)
- А −1 = 0
- А 0 = 1
- я = 0
- а степень R i ≥ t / 2
- я = я + 1
- Q = R i-2 / R i-1
- R i = R i-2 - QR i-1
- A i = A i-2 - QA i-1
чтобы установить младший член Λ (x) равным 1, разделите Λ (x) и Ω (x) на A i (0):
- Λ (х) = A i / A i (0)
- Ω (х) = R i / A i (0)
A i (0) - постоянный член (младшего разряда) A i .
Пример
Используя те же данные, что и в приведенном выше примере Петерсона – Горенштейна – Цирлера:
я | R i | А я |
---|---|---|
−1 | 001 х 4 + 000 х 3 + 000 х 2 + 000 х + 000 | 000 |
0 | 925 х 3 + 762 х 2 + 637 х + 732 | 001 |
1 | 683 х 2 + 676 х + 024 | 697 х + 396 |
2 | 673 х + 596 | 608 х 2 + 704 х + 544 |
- Λ (х) = A 2 /544 = 329 х 2 + 821 + 001 х
- Ω (х) = Р 2 / = 546 544 По й + 732
Декодер с использованием дискретного преобразования Фурье
Для декодирования можно использовать дискретное преобразование Фурье. [14] Чтобы избежать конфликта с названиями синдромов, пусть 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 линейного блочного кода размера ( п , K ) ограничена сверху на п - к + 1 расстояние d обычно понимается , чтобы ограничить возможность коррекции ошибок к ⌊ (d- 1) / 2⌋. Код Рида – Соломона достигает этой границы с равенством и, таким образом, может исправлять до (nk) / 2⌋ ошибок. Однако эта граница исправления ошибок не точна.
В 1999 году Мадху Судан и Венкатесан Гурусвами из Массачусетского технологического института опубликовали «Улучшенное декодирование кодов Рида – Соломона и алгебраической геометрии», в котором представлен алгоритм, позволяющий исправлять ошибки, превышающие половину минимального расстояния кода. [15] Это применимо к кодам Рида – Соломона и в более общем плане к алгебро-геометрическим кодам . Этот алгоритм создает список кодовых слов (это алгоритм декодирования списка ) и основан на интерполяции и факторизации многочленов по и его расширения.
Мягкое декодирование
Алгебраические методы декодирования, описанные выше, являются методами жесткого решения, что означает, что для каждого символа принимается жесткое решение о его значении. Например, декодер может связать с каждым символом дополнительное значение, соответствующее уверенности демодулятора канала в правильности символа. Появление LDPC и турбокодов , в которых используются итерационные методы декодирования распространения уверенности с мягким решением для достижения эффективности исправления ошибок, близкой к теоретическому пределу , подстегнуло интерес к применению декодирования с мягким решением к традиционным алгебраическим кодам. В 2003 году Ральф Кёттер и Александр Варди представили алгоритм полиномиального алгебраического декодирования списков с мягким решением для кодов Рида – Соломона, который был основан на работе Судана и Гурусвами. [16] В 2016 году Стивен Дж. Франке и Джозеф Х. Тейлор опубликовали новый декодер с мягким решением. [17]
Пример Matlab
Кодировщик
Здесь мы представляем простую реализацию Matlab для кодировщика.
функция [закодировано] = rsEncoder ( msg, m, prim_poly, n, k ) % RSENCODER Кодировать сообщение с помощью алгоритма Рида-Соломона % m - количество бит на символ % prim_poly: примитивный многочлен p (x). Т.е. для DM это 301 % k - размер сообщения % n - общий размер (k + избыточный) % Пример: msg = uint8 ('Тест') % enc_msg = rsEncoder (сообщение, 8, 301, 12, число (сообщение)); % Получить альфа альфа = gf ( 2 , m , prim_poly ); % Получите порождающий многочлен Рида-Соломона g (x) g_x = genpoly ( k , n , альфа ); % Умножьте информацию на X ^ (nk) или просто заполните нулями в конце, чтобы % получить место для добавления избыточной информации msg_padded = gf ([ msg zeros ( 1 , n - k )], m , prim_poly ); % Получить остаток от деления расширенного сообщения на % Порождающий многочлен Рида-Соломона g (x) [ ~ , остаток ] = deconv ( msg_padded , g_x ); % Теперь верните сообщение с избыточной информацией encoded = 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 (сообщение)) max_errors = floor (( n - k ) / 2 ); ориг_вала = закодировано . х ; % Инициализировать вектор ошибки ошибки = нули ( 1 , n ); г = []; S = []; % Получить альфа альфа = gf ( 2 , m , prim_poly ); % Найдите синдромы (проверьте, не разбивает ли сообщение генератор % полином результат равен нулю) Synd = polyval ( закодирован , альфа ^. ( 1 : п - к )); Синдромы = обрезка ( Synd ); % Если все синдромы нулевые (полностью делимые), ошибок нет. если пусто ( Syndromes . x ) декодировано = orig_val ( 1 : k ); error_pos = []; error_mag = []; г = []; S = Synd ; возврат ; конец % Подготовьтесь к эвклидовому алгоритму (используется для поиска ошибки при обнаружении % полиномов) 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 ); g0 = f1 ; g1 = f0 ; % Выполните алгоритм Евклида на многочленах r0 (x) и Syndromes (x) в %, чтобы найти полином обнаружения ошибки пока правда % Сделайте длинное деление [ частное , остаток ] = деконв ( r0 , r1 ); % Добавьте нули частное = pad ( частное , длина ( g1 )); % Найти частное * g1 и дополнить c = conv ( частное , g1 ); c = обрезка ( c ); c = площадка ( c , длина ( g0 )); % Обновить g как коэффициент g0 * g1 g = g0 - c ; % Проверить, меньше ли степень остатка (x) max_errors если все ( остаток ( 1 : конец - max_errors ) == 0 ) перерыв ; конец % Обновить r0, r1, g0, g1 и удалить ведущие нули r0 = обрезка ( r1 ); r1 = обрезка ( остаток ); g0 = g1 ; g1 = g ; конец % Удалить ведущие нули г = обрезка ( г ); % Найдите нули полинома ошибок на этом поле Галуа evalPoly = polyval ( g , alpha . ^ ( n - 1 : - 1 : 0 )); error_pos = gf ( найти ( evalPoly == 0 ), m ); % Если ошибочной позиции не обнаружено, мы возвращаем полученную работу, потому что % в принципе ничего не поделаешь и возвращаем полученное сообщение если пусто ( error_pos ) декодировано = orig_val ( 1 : k ); error_mag = []; возврат ; конец % Подготовьте линейную систему для решения полинома ошибок и нахождения ошибки % величины size_error = длина ( error_pos ); Syndrome_Vals = Синдромы . х ; b (:, 1 ) = Syndrome_Vals ( 1 : ошибка_размера ); для idx = 1 : size_error e = alpha . ^ ( idx * ( n - error_pos . x )); эрр = е . х ; эр ( idx , :) = ошибка ; конец % Решите линейную систему error_mag = ( gf ( er , m , prim_poly ) \ gf ( b , m , prim_poly )) ' ; % Поместите величину ошибки в вектор ошибки ошибки ( error_pos . x ) = error_mag . х ; % Принесите этот вектор в поле галуа errors_gf = gf ( ошибки , m , prim_poly ); % Теперь, чтобы исправить ошибки, просто добавьте закодированный код decoded_gf = закодировано ( 1 : k ) + errors_gf ( 1 : k ); декодированный = decoded_gf . х ; конец% Удалить ведущие нули из массива Галуафункция gt = trim ( g ) gx = 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 миллиардов подмножеств.
Декодер Berlekamp Welch
В 1986 году был разработан декодер, известный как алгоритм Берлекампа – Велча, как декодер, способный восстанавливать исходный полином сообщения, а также полином «локатора» ошибок, который выдает нули для входных значений, соответствующих ошибкам, с временной сложностью. O (n ^ 3), где n - количество значений в сообщении. Восстановленный полином затем используется для восстановления (при необходимости пересчета) исходного сообщения.
Пример
Используя RS (7,3), GF (929) и набор точек оценки a i = i - 1
- а = {0, 1, 2, 3, 4, 5, 6}
Если полином сообщения
- р ( х ) = 003 х 2 + 002 х + 001
Кодовое слово
- c = {001, 006, 017, 034, 057, 086, 121}
Ошибки при передаче могут привести к получению этого сообщения.
- b = c + e = {001, 006, 123, 456, 057, 086, 121}
Ключевые уравнения:
Предположим максимальное количество ошибок: e = 2. Ключевые уравнения принимают следующий вид:
Использование исключения Гаусса :
- Q ( x ) = 003 x 4 + 916 x 3 + 009 x 2 + 007 x + 006
- Е ( х ) = 001 х 2 + 924 х + 006
- Q ( x ) / E ( x ) = P ( x ) = 003 x 2 + 002 x + 001
Пересчитайте P (x), где E (x) = 0: {2, 3}, чтобы исправить b, что приведет к исправлению кодового слова:
- c = {001, 006, 017, 034, 057, 086, 121}
Декодер гао
В 2002 году Шухонг Гао разработал улучшенный декодер на основе расширенного алгоритма Евклида Gao_RS.pdf .
Пример
Используя те же данные, что и в приведенном выше примере Berlekamp Welch:
- Интерполяция Лагранжа для i = от 1 до n
я | R i | А я |
---|---|---|
−1 | 001 х 7 + 908 х 6 + 175 х 5 + 194 х 4 + 695 х 3 + 094 х 2 + 720 х + 000 | 000 |
0 | 055 х 6 + 440 х 5 + 497 х 4 + 904 х 3 + 424 х 2 + 472 х + 001 | 001 |
1 | 702 х 5 + 845 х 4 + 691 х 3 + 461 х 2 + 327 х + 237 | 152 х + 237 |
2 | 266 х 4 + 086 х 3 + 798 х 2 + 311 х + 532 | 708 х 2 + 176 х + 532 |
- Q ( х ) = R 2 = 266 х 4 + 086 х 3 + 798 х 2 + 311 х + 532
- Е ( х ) = А 2 = 708 х 2 + 176 х + 532
разделите Q (x) и E (x) на наиболее значимый коэффициент при E (x) = 708. (Необязательно)
- Q ( x ) = 003 x 4 + 916 x 3 + 009 x 2 + 007 x + 006
- Е ( х ) = 001 х 2 + 924 х + 006
- Q ( x ) / E ( x ) = P ( x ) = 003 x 2 + 002 x + 001
Пересчитайте P ( x ), где E ( x ) = 0: {2, 3}, чтобы исправить b, что приведет к исправлению кодового слова:
- c = {001, 006, 017, 034, 057, 086, 121}
Смотрите также
- Код BCH
- Циклический код
- Чиен поиск
- Алгоритм Берлекампа – Месси
- Прямое исправление ошибок
- Алгоритм Берлекампа – Велча
- Сложенный код Рида – Соломона
Заметки
- ^ Авторы Andrews et al. (2007), предоставляют результаты моделирования, которые показывают, что при той же кодовой скорости (1/6) турбокоды превосходят сцепленные коды Рида-Соломона до 2 дБ ( частота ошибок по битам ). [8]
Рекомендации
- ↑ Рид и Соломон (1960)
- ^ Д. Горенштейн и Н. Цирлер, "Класс циклических линейных кодов с исправлением ошибок в символах p ^ m", J. SIAM, vol. 9, стр. 207-214, июнь 1961 г.
- ^ Коды исправления ошибок W_Wesley_Peterson, 1961
- ^ Коды исправления ошибок, автор W_Wesley_Peterson, второе издание, 1972 г.
- ^ Ясуо Сугияма, Масао Kasahara, Shigeichi Хирасава и Toshihiko Namekawa. Метод решения ключевого уравнения для декодирования кодов Гоппа. Информация и контроль, 27: 87–99, 1975.
- ^ Immink, KAS (1994), "Рида-Соломона и компакт - диск", в плетеная, Стивен B .; Бхаргава, Виджай К. (ред.), Коды Рида – Соломона и их приложения , IEEE Press , ISBN 978-0-7803-1025-4
- ^ Дж. Хагенауэр, Э. Оффер и Л. Папке, Коды Рида-Соломона и их приложения. Нью-Йорк IEEE Press, 1994 - стр. 433
- ^ а б Эндрюс, Кеннет С. и др. «Разработка кодов турбо и LDPC для приложений дальнего космоса». Протоколы IEEE 95.11 (2007): 2142-2156.
- ^ См., Например, Lin & Costello (1983 , с. 171).
- ^ «Аналитические выражения, используемые в кодировании и BERTool» . Архивировано 01 февраля 2019 года . Проверено 1 февраля 2019 .
- ^ Пфендер, Флориан; Зиглер, Гюнтер М. (сентябрь 2004 г.), «Целующиеся числа, упаковки сфер и некоторые неожиданные доказательства» (PDF) , Уведомления Американского математического общества , 51 (8): 873–883, заархивировано (PDF) с оригинала на 2008-05-09 , проверено 28.09.2009. Объясняет теорему Дельсарта-Гетальса-Зейделя в контексте кода исправления ошибок для компакт-диска .
- ^ Д. Горенштейн и Н. Цирлер, "Класс циклических линейных кодов с исправлением ошибок в символах p ^ m", J. SIAM, vol. 9. С. 207–214, июнь 1961 г.
- ^ Коды исправления ошибок Уэсли Петерсон, 1961
- ↑ Шу Линь и Дэниел Дж. Костелло-младший, «Кодирование с контролем ошибок», второе издание, стр. 255–262, 1982, 2004
- ^ Гурусвами, V .; Судан, М. (сентябрь 1999 г.), «Улучшенное декодирование кодов Рида – Соломона и кодов алгебраической геометрии», IEEE Transactions on Information Theory , 45 (6): 1757–1767, CiteSeerX 10.1.1.115.292 , doi : 10.1109 / 18.782097
- ^ Кёттер, Ральф; Варди, Александр (2003). "Алгебраическое декодирование с мягким решением кодов Рида – Соломона". IEEE Transactions по теории информации . 49 (11): 2809–2825. CiteSeerX 10.1.1.13.2021 . DOI : 10.1109 / TIT.2003.819332 .
- ^ Franke, Стивен Дж .; Тейлор, Джозеф Х. (2016). «Декодер Soft-Decision с открытым исходным кодом для кода Рида – Соломона JT65 (63,12)» (PDF) . QEX (май / июнь): 8–17. Архивировано (PDF) из оригинала на 2017-03-09 . Проверено 7 июня 2017 .
дальнейшее чтение
- Гилл, Джон (nd), EE387 Notes # 7, раздаточный материал # 28 (PDF) , Стэнфордский университет, заархивировано из оригинала (PDF) 30 июня 2014 г. , получено 21 апреля 2010 г.
- Хонг, Джонатан; Веттерли, Martin (август 1995), "Простые алгоритмы МПБ декодировании" (PDF) , IEEE Transactions по сообщениям , 43 (8): 2324-2333, DOI : 10,1109 / 26.403765
- Линь, Шу; Костелло младший, Дэниел Дж. (1983), Кодирование с контролем ошибок: основы и приложения , Нью-Джерси, Нью-Джерси: Прентис-Холл, ISBN 978-0-13-283796-5
- Масси, JL (1969), "Синтез регистра сдвига и ВСН декодирования" (PDF) , IEEE Transactions по теории информации , ИТ-15 (1): 122-127, DOI : 10,1109 / tit.1969.1054260
- Петерсон, Уэсли В. (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 , Международный симпозиум по теории информации, Сан-Ремо, Италия
- Берлекамп, Элвин Р. (1984) [1968], Алгебраическая теория кодирования (пересмотренная редакция), Лагуна-Хиллз, Калифорния: Aegean Park Press, ISBN 978-0-89412-063-3
- Ципра, Барри Артур (1993), «Вездесущие коды Рида – Соломона» , SIAM News , 26 (1)
- Форни-младший, Г. (октябрь 1965), "О декодировании кодов БЧХ", IEEE Transactions по теории информации , 11 (4): 549-557, да : 10,1109 / TIT.1965.1053825
- Koetter, Ralf (2005), коды Рида – Соломона , MIT Lecture Notes 6.451 (видео), заархивировано из оригинала 13 марта 2013 г.
- MacWilliams, FJ; Слоан, штат Нью-Джерси (1977), Теория кодов с исправлением ошибок , Нью-Йорк, Нью-Йорк: издательство North-Holland Publishing Company
- Рид, Ирвинг С .; Чен, Сюэминь (1999), Кодирование с контролем ошибок для сетей передачи данных , Бостон, Массачусетс: Kluwer Academic Publishers
Внешние ссылки
Информация и учебные пособия
- Введение в коды Рида – Соломона: принципы, архитектура и реализация (CMU)
- Учебное пособие по кодированию Рида – Соломона для обеспечения отказоустойчивости в RAID-подобных системах
- Алгебраическое мягкое декодирование кодов Рида – Соломона.
- Викиверситет: коды Рида – Соломона для программистов
- Белая книга BBC R&D WHP031
- Гейзель, Уильям А. (август 1990 г.), Учебное пособие по кодированию с исправлением ошибок Рида – Соломона , Технический меморандум, НАСА , TM-102162
- Гао, Шухонг (январь 2002 г.), Новый алгоритм декодирования кодов Рида-Соломона (PDF) , Клемсон
- Составные коды доктора Дэйва Форни (scholarpedia.org).
- Рид, Джефф А. (апрель 1995 г.), CRC и Рид Соломон ECC (PDF)
Реализации
- Кодек Рида – Соломона Schifra с открытым исходным кодом C ++
- Библиотека RSCode Генри Мински, кодировщик / декодер Рида – Соломона
- Библиотека программного декодирования Рида – Соломона с открытым исходным кодом C ++
- Реализация в Matlab ошибок и стираний декодирования Рида – Соломона
- Реализация Octave в коммуникационном пакете
- Реализация кодека Рида – Соломона на чистом Python