Коды Рида-Соломона в практических реализациях, или Информация, воскресшая из пепла III

Крис Касперски

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

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

С другой стороны, для практического использования корректирующих кодов можно и не вникать в их сущность, просто откомпилировав исходные тексты кодера/декодера Рида-Соломона, приведенные в данной статье. Также вы можете воспользоваться любой законченной библиотекой, поставляемой сторонними разработчиками. В качестве альтернативного примера в заключение этой статьи будет кратно описан интерфейс библиотеки ElByECC.DLL, разработанной компанией «Elaborate Bytes» и распространяемой вместе с популярным копировщиком Clone CD. Известнейший прожигатель дисков всех времен и народов Ahead Burning ROM имеет аналогичную библиотеку, размещенную в файле NEWTRF.DLL.

Легенда

Напомним читателю основные условные обозначения, используемые в этой статье. Количество символов кодируемого сообщения (называемого также информационным словом) по общепринятому соглашению обозначается буквой k; полная длина кодового слова, включающего в себя кодируемые данные и символы четности, – n. Отсюда, количество символов четности равно: n – k. За максимальным количеством исправляемых ошибок «закреплена» буква t. Поскольку для исправления одной ошибки требуется два символа четности, общее количество символов четности равно 2t. Выражение RS(n, k) описывает определенную разновидность корректирующих кодов Рида-Соломона, оперирующую с n-символьными блоками, k-символов, из которых представляют полезные данные, а все остальные задействованы под символы четности.

Полином, порожденный на основе примитивного члена a, называется порожденным или сгенерированным (generate) полиномом.

Кодировщик (encoder)

Существует по меньшей мере два типа кодеров Рида-Соломона: несистематические и систематические кодировщики.

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

При систематическом кодировании, напротив, исходное информационное слово останется неизменным, а корректирующие коды (часто называемые символами четности) добавляются в его конец, благодаря чему к операции декодирования приходится прибегать лишь в случае действительного разрушения данных. Вычисление несистематических корректирующих кодов Рида-Соломона осуществляется делением информационного слова на порожденный полином. При этом все символы информационного слова сдвигаются на n – k байт влево, а на освободившееся место записывается 2t байт остатка (см. рис. 1).

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

Рисунок 1. Устройство кодового слова

Архитектурно кодировщик представляет собой совокупность сдвиговых регистров (shift registers), объединенных посредством сумматоров и умножителей, функционирующих по правилам арифметики Галуа. Сдвиговый регистр (иначе называемый регистром сдвига) представляет последовательность ячеек памяти, называемых разрядами, каждый из которых содержит один элемент поля Галуа GF(q). Содержащийся в разряде символ, покидая этот разряд, «выстреливается» на выходную линию. Одновременно с этим разряд «засасывает» символ, находящийся на его входной линии. Замещение символов происходит дискретно, в строго определенные промежутки времени, называемые тактами.

При аппаратной реализации сдвигового регистра его элементы могут быть объединены как последовательно, так и параллельно. При последовательном объединении пересылка одного m-разрядного символа потребуем m-тактов, в то время как при параллельном она осуществляется всего за один такт.

Низкая эффективность программных реализаций кодеров Рида-Соломона объясняется тем, что разработчик не может осуществлять параллельное объединение элементов сдвигового регистра и вынужден работать с той шириной разрядности, которую «навязывает» архитектура данной машины. Однако создать 4-элементный 8-битный регистр сдвига параллельного типа на процессорах семейства IA32 вполне реально.