Проверочная матрица кода РС есть проверочная матрица кода БЧХ длины, являющаяся частью матрицы ДПФ последовательностей с компонентами из поля. Особенности декодирования кодов РС по сравнению с двоичными кодами БЧХ связаны с тем, что вектор ошибки имеет компоненты из поля. Поэтому при декодировании кодов РС недостаточно указать номера искаженных символов, надо еще определить, насколько искажены символы, т. е. найти значения вектора ошибки. Последнее требование усложняет процедуру декодирования кодов РС по сравнению с декодированием двоичных кодов БЧХ. Практическая реализация кода
Кодирование с помощью кода Рида — Соломона может быть реализовано двумя способами: систематическим и несистематическим. При несистематическом кодировании информационное слово умножается на некий неприводимый полином в поле Галуа. Полученное закодированное слово полностью отличается от исходного и для извлечения информационного слова нужно выполнить операцию декодирования и уже потом можно проверить данные на содержание ошибок. Такое кодирование требует большие затраты ресурсов только на извлечение информационных данных, при этом они могут быть без ошибок.Рис. 1 Структура систематического кодового слова Рида — Соломона
При систематическом кодировании к информационному блоку из символов приписываются проверочных символов, при вычислении каждого проверочного символа используются все символов исходного блока. В этом случае нет затрат ресурсов при извлечении исходного блока, если информационное слово не содержит ошибок, но кодировщик/декодировщик должен выполнить k (n-k) операций сложения и умножения для генерации проверочных символов. Кроме того, так как все операции проводятся в поле Галуа, то сами операции кодирования/декодирования требуют много ресурсов и времени. Быстрый алгоритм декодирования, основанный на быстром преобразовании Фурье, выполняется за время порядка. Применение кода
Сразу после появления (60-е годы 20-го века) коды Рида — Соломона стали применяться в качестве внешних кодов в каскадных конструкциях, использующихся в спутниковой связи. В подобных конструкциях q-ые символы РС (их может быть несколько) кодируются внутренними сверточными кодами. На приемном конце эти символы декодируются мягким алгоритмом Витерби (эффективный в каналах с АБГШ). Такой декодер будет исправлять одиночные ошибки в q-ичныхсимволах, когда же возникнут пакетные ошибки и некоторые пакеты q-ичных символов будут декодированы неправильно, тогда внешний декодер Рида — Соломона исправит пакеты этих ошибок. Таким образом будет достигнута требуемая надежность передачи информации. В настоящий момент коды Рида — Соломона имеют очень широкую область применения благодаря их способности находить и исправлять многократные пакеты ошибок. Код Рида — Соломона используется при записи и чтении в контроллерах оперативной памяти, при архивировании данных, записи информации на жесткие диски (ECC), записи на CD/DVD диски.
Даже если поврежден значительный объем информации, испорчено несколько секторов дискового носителя, то коды Рида — Соломона позволяют восстановить большую часть потерянной информации. Также используется при записи на такие носители, как магнитные ленты и штрихкоды. Возможные ошибки при чтении с диска появляются уже на этапе производства диска, так как сделать идеальный диск при современных технологиях невозможно. Также ошибки могут быть вызваны царапинами на поверхности диска, пылью и т. д. Поэтому при изготовлении читаемого компакт-диска используется система коррекции CIRC (CrossInterleavedReedSolomonCode). Эта коррекция реализована во всех устройствах, позволяющих считывать данные с CD дисков, в виде чипа с прошивкой firmware. Нахождение и коррекция ошибок основана на избыточности и перемежении (redundancy & interleaving). Избыточность примерно 25% от исходной информации. При записи на аудиокомпакт-диски используется стандарт RedBook.
Коррекция ошибок происходит на двух уровнях C1 и C2. При кодировании на первом этапе происходит добавление проверочных символов к исходным данным, на втором этапе информация снова кодируется. Кроме кодирования осуществляется также перемешивание (перемежение) байтов, чтобы при коррекции блоки ошибок распались на отдельные биты, которые легче исправляются. На первом уровне обнаруживаются и исправляются ошибочные блоки длиной один и два байта (один и два ошибочных символа соответственно).
Ошибочные блоки длиной три байта обнаруживаются и передаются на следующий уровень. На втором уровне обнаруживаются и исправляются ошибочные блоки, возникшие в C2, длиной 1 и 2 байта. Обнаружение трех ошибочных символов является фатальной ошибкой и не может быть исправлено. Беспроводная и мобильная связь. Этот алгоритм кодирования используется при передаче данных по сетям WiMAX, в оптических линиях связи, в спутниковой и радиорелейной связи. Метод прямой коррекции ошибок в проходящем трафике (ForwardErrorCorrection, FEC) основывается на кодах Рида — Соломона. Заключение
В наш так называемый информационный век нет необходимости кому-то напоминать, что для хранения, поиска и передачи данных важна не только скорость, но и безошибочность. Принцип «что посеешь, то и пожнешь» в данном случае не всегда работает. Машины допускают ошибки, и их просчеты, возникшие не по вине человека, могут превратить безупречно написанную программу в бесполезный и даже опасный хлам. Подобно тому, как архитекторы проектируют здания, которые не разрушаются даже при землетрясении, их компьютерные коллеги придумали изощренные приемы, которые способны противодействовать проявлениям закона Мерфи в цифровом мире. Однако, многие люди, использующие современные технологии, могут и не догадываться о важности пятистраничной статьи, появившейся в 1960 году в журнале Общества промышленной и прикладной математики. В этой статье под названием «Полиномиальные коды над некоторыми конечными полями» Ирвин Рид и Густав Соломон, будущие сотрудники лаборатории Линкольна Массачусетского технологического института, представили идеи, которые лежат в основе современных методов исправления ошибок, применяемых в различном оборудовании, начиная с компьютерных жестких дисков и заканчивая проигрывателями компакт-дисков. Коды Рида-Соломона сделали возможным отправку фотографий внешних планет солнечной системы с космического аппарата Вояджер-2 на Землю. Они дают возможность наслаждаться музыкой с поцарапанного компакт-диска. И в недалеком будущем они позволят ненасытным кабельным телевизионщикам впихнуть в свои системы более 500 каналов. В данной работе была подробно рассмотрена история развития алгебраических кодов, появление на свет кода Рида-Соломона и практическое его применение.
Список литературы
Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. — М.: Мир, 1976. —
С. 596. Блейхут Р. Теория и практика кодов, контролирующих ошибки = Theory and PracticeofErrorControlCodes. —
М.: Мир, 1986. — 576 с. Берлекэмп Э. Алгебраическая теория кодирования = AlgebraicCodingTheory. — М.: Мир, 1971. —
С. 478. Егоров С. И. Коррекция ошибок в информационных каналах периферийных устройств ЭВМ. — Курск: Курск
ГТУ, 2008. — С. 252. Сагалович Ю. Л.
Введение
в алгебраические коды: Учебное пособие.
— М.: МФТИ, 2007. — 262 с. — ISBN 5−7417−0191−4.Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования.
Методы, алгоритмы, применение / пер. с англ. В. Б.
Афанасьева. — М.: Техносфера, 2006. — 320 с. — (Мир связи). —
2000 экз. — ISBN 5−94 836−035−0.М. Вернер Основы кодирования. —
Техносфера, 2004. — 288 с. — ISBN 5−94 836−019−9.
