Могущество кодов Рида-Соломона или информация, воскресшая из пепла

Энтропия слепа, но терпелива. Рано или поздно,
обстреливая наши позиции по квадратам, она нанесет удар по
штабу, по центру связи. И тогда первая линия обороны
уничтожена. И приходится отходить на запасные позиции.
Иными словами, доставать из магнитотеки пакет дисков с копией тома.
Е. В. Лишак, "Тридцать второй день года. (Записки парасистемного программиста)."

Все вы наверняка слышали о существовании помехозащитных кодов Рида-Соломона, широко использующихся в устройствах передачи и хранения данных для обнаружения и исправления как одиночных так и групповых(!) ошибок. Область их применения необычайно широка - кодеры/декодеры Рида-Соломона можно найти и в ленточных запоминающих устройствах, и в контроллерах оперативной памяти, и в модемах, и в жестких дисках, и в CD-ROM/DVD приводах и т.д. Благодаря им некоторые подвинутые архиваторы безболезненно переносят порчу нескольких секторов носителя, содержащего архив, а подчас - и полное разрушение целого тома многотомного архива. Еще коды Рида-Соломона позволяют защитному механизму автоматически восстанавливать байтики, хакнутые взломщиком и/или искаженные в результате сбоя программного/аппаратного обеспечения. Короче говоря, если владение техникой помехозащитного кодирования не превращает вас в бога, то, по крайней мере, поднимает на Олимп, где среди бесшумных вентиляторов и безглючных операционных систем снуют великие компьютерные Гуру.

В то же время лишь немногие программисты могут похвастаться собственной реализацией алгоритмов Рида-Соломона. Да и зачем? Готовых библиотек море - от прагматичных коммерческих пакетов до бесплатных исходников, распространяемых по лицензии GNU. Как говориться, бери - не хочу ^[1]. Что ж, в использовании библиотек есть вполне определенный практический смысл, но никакой хакер не доверит управления программе, до тех пор, пока не поймет - как именно она работает (а эта публикация именно для хакеров и предназначена, естественно, "хакеров" - в хорошем значении этого слова). С другой стороны - при анализе программного обеспечения, распространяемого без исходных кодов, вы не сможете идентифицировать алгоритм Рида-Соломона, если только заранее не разберетесь во всех его тонкостях. Допустим, вам встретилась защита, хитрым образом манипулирующая с EDC/ECC полями ключевых секторов, считанных ею с лазерного диска и каждый такой сектор содержит две умышленно внесенные ошибки (плюс еще ошибки, естественным путем возникающие при небрежном обращении с CD), причем одна из этих ошибок - ложная и исправлять ее не нужно. При штатном копировании защищенного диска микропроцессорная начинка CD-ROM'а автоматически исправляет все ошибки, которые она только может исправить, в результате чего происходит искажение ключевых меток и, как следствие, защищенная программа перестанет работать. Можно, конечно, скопировать диск в "сыром" режиме, т.е. без исправления ошибок, но тогда копия будет содержать как непредумышленные, так и предумышленные ошибки, в результате чего даже при незначительном повреждении оригинала корректирующих возможностей кодов Рида-Соломона уже окажется недостаточно и диск просто перестанет читаться (а как вы хотели? копирование дисков в сыром режиме ведет к накоплению ошибок и потому крайне непрактично с любой точки зрения). Владение базовыми принципами помехозащитного кодирования позволит вам разобраться с логикой работы защитного механизма и понять - какие конкретного ошибки следует исправлять, а какие - нет.

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

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

Корректирующие коды и помехоустойчивое кодирование (азы)

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

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

Впрочем, все это вы уже наверняка знаете (а если не знаете, то без труда найдете исчерпывающее объяснение основ кодирования в любом учебнике по информатике), но знаете ли вы, что такое расстояние Хемминга? Это минимальное количество различий между двумя различными допустимыми кодовыми словами и в теории помехоустойчивого кодирования расстояние Хемминга играет основополагающую роль. Рассмотрим, например, следующий четырехбитный код:

0 -> 0000;    4 -> 0100;     8 -> 1000;    12 -> 1100;
1 -> 0001;    5 -> 0101;     9 -> 1001;    13 -> 1101;
2 -> 0010;    6 -> 0110;    10 -> 1010;    14 -> 1110;
3 -> 0011;    7 -> 0111;    11 -> 1011;    15 -> 1111;

Листинг 1. Пример простейшего четырехбитного кода с расстоянием Хемминга, равным единице. Такой код широко используется в вычислительной технике, несмотря на его невозможность обнаружить ошибки.

Это обыкновенный двоичный код, который можно встретить в некоторых однокристаллках, вмещающий в свои 4 бита 16 символов (т.е. с его помощью можно закодировать 16 букв алфавита). Как нетрудно убедиться, два любых символа отличаются по меньшей мере на один бит, следовательно, расстояние Хемминга для такого кода равно единице (что условно обозначается как d = 1).

А вот другой четырехбитный код:

0 -> 0000;    4 -> 1001;
1 -> 0011;    5 -> 1010;
2 -> 0101;    6 -> 1100;
3 -> 0110;    7 -> 1111;

Листинг 2. Пример четырехбитного кода с расстоянием Хемминга, равным двум, способный обнаруживать одиночные ошибки.

На этот раз два произвольных символа отличаются как минимум в двух позициях, за счет чего информационная емкость такого кода сократилась с 16 до 8 символов. Постойте-постойте! - воскликнет иной читатель. - Что это за бред? Куда девалась комбинация 0001 или 0010 например? Нет, это не бред и указанных комбинаций бит в данном коде действительно нет, точнее - они есть, но объявлены запрещенными. Благодаря этому обстоятельству наш подопечный код способен обнаруживать любые одиночные ошибки. Возьмем, например, символ "1010" и исказим в нем произвольный бит (но только один!). Пусть это будет второй слева бит, тогда искаженный символ станет выглядеть так: "1110". Поскольку комбинация "1110" является запрещенной, декодер может засвидетельствовать наличие ошибки. Увы, только засвидетельствовать, но не исправить, т.к. для исправления даже одного-единственного сбойного байта требуется увеличить расстояние Хемминга, как минимум, до трех. Поскольку 4-битный код с d = 3 способен вмещать в себя лишь два различных символа, то он крайне ненагляден и потому нам лучше выбрать код с большей разрядностью. Хорошо, пусть это будет 10-битный код с d = 5.

0000000000    0000011111    1111100000    1111111111

Листинг 3. Пример 10-битного кода, с расстоянием Хемминга, равном пяти, способного обнаруживать четырехбитные ошибки, а исправлять - двухбитовые.

Возьмем, к примеру, символ "0000011111" и искорежим два любых бита, получив в итоге что-то наподобие: "0100110111". Поскольку такая комбинация является запрещенной, декодер понимает, что произошла ошибка. Достаточно очевидно, что если количество сбойных бит меньше расстояния Хемминга хотя бы наполовину, то декодер может гарантированно восстановить исходный символ. Действительно, если между двумя любыми разрешенными символами существует не менее пяти различий, то искажение двух бит всякого такого символа приведет к образованию нового символа (обозначим его k), причем расстояние Хемминга между k и оригинальным символом равно числу непосредственно искаженных бит (т.е. в нашем случае двум), а расстояние до ближайшего соседнего символа равно: d - k (т.е. в нашем случае трем). Другими словами, пока d - k > k декодер может гарантированно восстановить искаженный символ. В тех случаях, когда d > k >d - k, успешное восстановление уже не гарантируется, но при удачном стечении обстоятельств все-таки оказывается, в принципе, возможным.

Возвращаясь к нашему символу "0000011111", давайте на этот раз исказим не два бита, а четыре: "0100110101" и попробуем его восстановить. Изобразим процесс восстановления графически:

0000000000 0000011111 1111100000  1111111111
0100110101 0100110101 0100110101  0100110101
----------  ----------  ----------  ----------
5 отличий 4 отличия 6 отличий   5 отличий

Листинг 4. Восстановление четырехбитной ошибки.

Грубо говоря, обнаружив ошибку, декодер последовательно сличает искаженный символ со всеми разрешенными символами алфавита, стремясь найти символ наиболее "похожий" на искаженный. Точнее - символ с наименьшим числом различий, а еще точнее - символ, отличающийся от искаженного не более чем в (d - 1) позициях. Легко видеть, что в данном случае нам повезло и восстановленный символ совпал с истинным. Однако, если бы четыре искаженных бита распределились бы так: "0111111111", то декодер принял бы этот символ за "1111111111" и восстановление оказалось бы неверным.

Таким образом, исправляющая способность кода определяется по следующей формуле: для обнаружения r ошибок расстояние Хемминга должно быть больше или равно r, а для коррекции r ошибок расстояние Хемминга должно быть, по крайней мере, на единицу больше удвоенного количества r.

Обнаружение ошибок: d >= r
Исправление ошибок: d > 2r
Информационная емкость: 2 в степени (n/d)

Листинг 5. Корректирующие способности простого кода Хемминга.

Теоретически количество обнаруживаемых ошибок неограниченно, практически же информационная емкость кодовых слов стремительно тает с ростом d. Допустим, у нас есть 24 байта данных и мы хотели бы исправлять до двух ошибок на каждый такой блок. Тогда нам придется добавить к этому блоку еще 49 байт, в результате чего реальная информационная емкость блока сократиться всего до... 30%! Хорошенькая перспектива, не так ли? Столь плачевный результат объясняется тем, что биты кодового слова изолированы друг от друга и изменение одного из них никак не сказывается на окружающих. А что, если...

Пусть все биты, номера которых есть степень двойки, станут играть роль контрольных битов, а оставшиеся и будут обычными ("информационными") битами сообщения. Каждый контрольный бит должен отвечать за четность суммы ^[2] некоторой, принадлежащей ему группы битов, причем один и тот же информационный бит может относиться к различным группам. Тогда один информационный бит сможет влиять на несколько контрольных и потому информационная емкость слова значительно (можно даже сказать, чудовищно) возрастет. Остается только выбрать наиболее оптимальное разделение сфер влияния.

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

Таблица 1. Разделение бит на контрольные и информационные.

Давайте в порядке закрепления материала попробуем пощупать коды Хемминга "в живую" и вручную рассчитаем контрольную сумму 4-битного символа "0101". После резервирования "квартир" для контрольных битов (выделенных в тексте жирным шрифтом) наш символ будет выглядеть так: AB0C101D. Теперь остается только рассчитать значения битов A, B, C и D:

• Бит A, контролирующий биты 3, 5 и 7 равен нулю, т.к. их сумма (0 + 1 + 1) четна.
• Бит B, контролирующий биты 3, 6 и 7 равен одному, т.к. их сумма (0 + 0 + 1) нечетна
• Бит C, контролирующий биты 5, 6 и 7 равен нулю, т.к. их сумма (1 + 0 + 1) четна

Таким образом, "новоиспеченное" кодовое слово будет выглядеть так: "0100101", где жирным шрифтом выделены контрольные биты.

AB0C101
1234567

Листинг 6. Кодовое слово вместе с информационными битами.

Допустим, при передаче наше слово было искажено в одной позиции и стало выглядеть так: 0100111. Сможем ли мы обнаружить такую ошибку? А вот сейчас и проверим! Так, бит A должен быть равен: (0 + 1 + 1) % 2 = 0, что соответствует истине. Бит B должен быть равен (0 + 1 + 1) % 2 = 0, а в нашем слове он равен единице. Запомним номер "неправильного" контрольного бита и продолжим. Бит C должен быть равен (1 + 1 + 1) % 2 = 1, а он равен нулю! Ага, значит, контрольные биты в позициях 2 (бит B) и 4 (бит C) обнаруживают расхождение с действительностью. Их сумма (2 + 4 = 6) и дает позицию сбойного бита. Действительно, в данном случае номер искаженного бита равен 6 - инвертируем его, тем самым восстанавливая наше кодовое слово в исходный вид.

А что, если искажение затронет не информационный, а контрольный бит? Проверка показывает, что позиция ошибки успешно обнаруживается и в этом случае и контрольный бит при желании может быть легко восстановлен по методике, уже описанной выше (только если ли в этом смысл? Ведь контрольные биты все равно "выкусываются" в процессе декодирования кодового слова).

На первый взгляд кажется, что коды Хемминга жутко неэффективны, ведь на 4 информационных бита у нас приходится 3 контрольных, однако, поскольку номера контрольных бит представляют собой степень двойки, то с ростом разрядности кодового слова они начинают располагаться все реже и реже. Так, ближайший к биту C контрольный бит D находится в позиции 8 (т.е. в трех шагах), зато контрольный бит E отделен от бита D уже на 2⁴ - 2³ - 1 = 7 "шагов", а контрольный бит F и вовсе на - 2⁵ - 2⁴ - 1 = 15 "шагов".

Таким образом, с увеличением разрядности обрабатываемого блока эффективность кодов Хемминга стремительно нарастает, что и показывает следующая программа:

Листинг 7. Расчет эффективной информационной емкости кодов Хемминга для слов различной длины.

BLOCK_SIZE    FUEL UP   EFFICIENCY
-----------------------------------
       1          0        0.0%
       2          0        0.0%
       4          1       25.0%
       8          4       50.0%
      16         11       68.8%
      32         26       81.3%
      64         57       89.1%
     128        120       93.8%
     256        247       96.5%
     512        502       98.0%
    1024       1013       98.9%
    2048       2036       99.4%
    4096       4083       99.7%
    8192       8178       99.8%
   16384      16369       99.9%
   32768      32752      100.0%
   65536      65519      100.0%
  131072     131054      100.0%
  262144     262125      100.0%
  524288     524268      100.0%
-----------------------------------

Листинг 8. Результат расчета эффективной информационной емкости кодов Хемминга для слов различной длины.

Из приведенной выше распечатки видно, что при обработке блоков, дотягивающихся хотя бы до 1024 бит, накладными расходами на контрольные биты можно полностью пренебречь.

К сожалению, коды Хемминга способны исправлять лишь одиночные ошибки, т.е. допускают искажение всего лишь одного сбойного бита на весь обрабатываемый блок. Естественно, с ростом размеров обрабатываемых блоков увеличивается и вероятность ошибок. Поэтому, выбор оптимальной длины кодового слова является весьма нетривиальной задачей, как минимум требующей знания характера и частоты возникновения ошибок используемых каналов передачи информации. В частности, для ленточных накопителей, лазерных дисков, винчестеров и тому подобных устройств, коды Хемминга оказываются чрезвычайно неэффективными. Зачем же тогда мы их рассматривали? А затем, что понять прогрессивные системы кодирования (к которым, в том числе, относятся и коды Рида-Соломона), ринувшись атаковать их "с нуля", практически невозможно, ибо они завязаны на сложной, действительно высшей математике, но ведь не Боги горшки обжигают, верно?

Идея кодов Рида-Соломона

Если говорить упрощенно, то основная идея помехозащитного кодирования Рида-Соломона заключается в умножении информационного слова, представленного в виде полинома D, на неприводимый полином G ^[3], известный обоим сторонам, в результате чего получается кодовое слово C, опять-таки представленное в виде полинома.

Декодирование осуществляется с точностью до наоборот: если при делении кодового слова C на полином G декодер внезапно получает остаток, то он может рапортовать наверх об ошибке. Соответственно, если кодовое слово разделилось нацело, его передача завершилась успешно.

Если степень полинома G (называемого также порождающим полиномом) превосходит степень кодового слова по меньшей мере на две степени, то декодер может не только обнаруживать, но и исправлять одиночные ошибки. Если же превосходство степени порождающего полинома над кодовым словом равно четырем, то восстановлению поддаются и двойные ошибки. Короче говоря, степень полинома k связана с максимальным количеством исправляемых ошибок t следующим образом: k = 2 * t. Следовательно, кодовое слово должно содержать два дополнительных символа на одну исправляемую ошибку. В то же время, максимальное количество распознаваемых ошибок равно t, т.е. избыточность составляет один символ на каждую распознаваемую ошибку.

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

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

Впрочем, если как следует подумать головой, частично призвав на помощь и другие части тела, можно сообразить, что умножать информационное слово на порождающий полином вовсе не обязательно, можно поступить гораздо хитрее:

1) Добавляем к исходному информационному слову D справа k нулей, в результате чего у нас получается слово длины n = m + r и полином X^r * D, где m - длина информационного слова;

2) Делим полученный полином X^r * D на порождающий полином G и вычисляем остаток от деления R, такой что: X^r * D = G * Q + R, где Q - частное, которое мы благополучно игнорируем за ненадобностью - сейчас нас интересует только остаток;

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

4) Мысленно прокручиваем пункты 1, 2 и 3, пытаясь обнаружить, на какой же стадии вычислений происходит выход за разрядную сетку и... такой стадии нет! Все пучком! Остается лишь отметить, что информационное слово + корректирующие коды можно записать так: T = X^r * D + R = GQ.

Декодирование полученного слова T осуществляется точно также, как уже и было описано ранее. Если при делении T (которое в действительности является произведением G на Q) на порождающий полином G образуются остаток, то слово T искажено и, соответственно, наоборот.

Теперь - вопрос на засыпку. Как вы собираетесь осуществлять деление полиномов в рамках общепринятой алгебры? В целочисленной арифметике деление определено не для всех пар чисел (вот, в частности, 2 нельзя разделить на 3, а 9 нельзя разделить на 4 - без потери значимости, естественно). Что же касается "плавучки", то ее точность еще та (в смысле, точность катастрофически недостаточна для эффективного использования кодов Рида-Соломона), к тому же она достаточно сложна в аппаратной реализации. Ладно, в IBM PC с процессором Pentium быстродействующий математический сопроцессор всем нам дан по дефолту, но что делать разработчикам ленточных накопителей, винчестеров, CD-приводов, наконец? Пихать в них четвертый Пень?! Нет уж, увольте - лучше воспользоваться специальной арифметикой - арифметикой конечных групп, называемых полями Галуа. Достоинство этой арифметики в том, что операции сложения, вычитания, умножения и деления определены для всех членов поля (естественно, исключая ситуацию деление на ноль), причем, число, полученное в результате любой из этих операций, обязательно присутствует в группе! Т.е. при делении любого целого числа A, принадлежащего множеству 0...255, на любое целое число B из того же множества (естественно, B не должно быть равно нулю), мы получим число C, входящее в данное множество. А потому потерь значимости не происходит и никакой неопределенности не возникает!

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

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

Мы будем исходить из того, что если g = 2ⁿ + 1, то для любого a из диапазона 0...2ⁿ, произведение a * g = c (где с - кодовое слово), будет представлять, по сути, полную мешанину битов обоих исходных чисел.

Допустим, n = 2, тогда g = 3. Легко видеть - на что бы мы не умножали g - хоть на 0, хоть на 1, хоть на 2, хоть на 3, полученный результат делится нацело на g в том и только в том случае, если никакой из его битов не инвертирован (то есть, попросту говоря, одиночные ошибки отсутствуют).

Остаток от деления однозначно указывает на позицию ошибки (при условии, что ошибка одиночная, групповые же ошибки данный алгоритм исправлять не способен). Точнее, если ошибка произошла в позиции x, то остаток от деления k будет равен k = 2^x. Для быстрого определения x по k можно воспользоваться тривиальным табличным алгоритмом. Впрочем, для восстановления сбойного бита знать его позицию совершенно необязательно, достаточно сделать R = e ^ k, где e - искаженное кодовое слово, ^ - операция XOR, а R - восстановленное кодовое слово.

В общем, законченная реализация кодера/декодера может выглядеть так:

Листинг 9. Простейший пример реализации кодера/декодера Рида-Соломона, работающего по обычной арифметике (т.е. с неоправданным расширением разрядной сетки) и исправляющего любые одиночные ошибки в одном 8-битном информационном слове (впрочем, программу легко адаптировать и под 16-байтовые информационные слова). Обратите внимание, что кодер реализуется чуть ли не на порядок проще декодера. В настоящем декодере Рида-Соломона, способном исправлять групповые ошибки, этот разрыв еще значительнее.

i = 00000069    (DATAIN)
g = 00000200    (POLYNOM)
c = 0000d200    (CODEWORD)
e = 0000d208    (RAW RECIVED DATA+ERR)

RS decoder says: (8) error detected
{
        0 to 1 err  position: 3
        restored codeword is: d200
}
RECEIVED DATA IS: 69

Листинг 10. Результат работы простейшего кодера/декодера Рида-Соломона. Обратите внимание - искаженный бит удалось успешно исправить, однако для этого к исходному информационному слову пришлось добавить не два, а целых три бита (если вы возьмете в качестве входного слова максимально допустимое восьмибитное значение 0xFF, то кодовое слово будет равно 0x1FE00, а так как 2¹⁰ для свободных разрядов уже не хватает и приходится увеличивать разрядную сетку до 2¹¹, в то время как младшие биты кодового слова фактически остаются незадействованными и "правильный" кодер должен их "закольцевать", грубо говоря, замкнув обрабатываемые разряды на манер кольца.

Что читать

Несмотря на то, что данный раздел является вполне самодостаточным и весь минимально необходимый математический аппарат излагает самостоятельно без отсылок к сторонней литературе, желание углубить свои знания вполне естественно и его можно только приветствовать. А потому будет лучше, если вы не ограничитесь одной этой книгой, но перевернете целые горы специализированной литературы, с каждым разом все больше и больше ужасаясь глубине той пропасти, что отделяет ваши поверхностные представления от действительно настоящих знаний. Теория помехоустойчивого кодирования столь обширна, что для ее изучения потребуется, как минимум, целая жизнь.

Итак, с чего начать?

• Blahut Richard "Theory and Practice of Error Control Codes", Mass.: Addison-Wesley, 1983
  Очень хорошая книжка из категории "must have"; по слухам есть в электронном виде в сети, однако к сожалению самой книжки я так и не нашел, но тучи ссылок на нее убедительно свидетельствуют о высоком качестве последней. Также имеется ее русскоязычный перевод, выпущенный издательством "Мир" (см. ниже);
  
  
• Блейхут Р. "Теория и практика кодов, контролирующих ошибки" М.: Мир, 1986. 576с.
  Технически грамотный и добротный перевод уже упомянутой выше книги Блейхута (ах, какие в издательстве Мир были переводчики!), электронной копии в сети, к сожалению, нет;
  
  
• James Plank "A tutorial on Reed-Solomon Coding for fault-tolerance in RAID-like systems"
  Неплохое руководство по использованию кодов Рида-Соломона для построения отказоустойчивых RAID-подобных систем, ориентированное на математически неподготовленных системных программистов и доходчиво объясняющее суть помехоустойчивого кодирования с примерами исходных текстов на Си. Электронная копия доступа по адресу: http://www.cs.utk.edu/~plank/plank/papers/CS-96-332.pdf. Настоятельно рекомендую прочитать, даже если вы и не собираетесь заниматься сборкой RAID;
  
  
• Joel Sylvester "Reed Solomon Codes"
  Предельно кратное описание принципов работы кодов Рида-Соломона с блок-схемами вместо исходных текстов. На практическое руководство не тянет, но общую картину все-таки дает, почитайте: http://www.elektrobit.co.uk/pdf/reedsolomon.pdf;
  
  
• Tom Moore "REED-SOLOMON PACKAGE" (old tutorial)
  Роскошный сборник разнообразных руководств по кодам Рида-Соломона, наверное, лучший из всех, что я видел. Включает в себя кратное описание основ теории полей Галуа, базовые принципы построения кодеров/декодеров Рида-Соломона и законченные примеры реализации самих кодеров/декодеров на языке Си (правда, недостаточно добросовестно прокомментированные). Сей stuff неоднократно промелькивал в ФИДО и последний раз постился 28 декабря 1994 года в конференции comp.compression. Его легко найти в "Гугле" по ключевым словам "Reed-Solomon+main+ECC". Настоятельно рекомендую.
  
  
• Ross N.Williams "A painless guide to CRC error detection algorithms"
  Подробное руководство по CRC, полезное, с достаточно внятным и доступным описанием полиномиальной арифметики, без которой работа с кодами Рида-Соломона просто немыслима. Доступно в электронной форме по следующему адресу: ftp://www.internode.net.au/clients/rocksoft/papers/crc_v3.txt. Также имеется его неплохой перевод на русский язык, легко отыскивающийся в сети по запросу "Элементарное руководство по CRC алгоритмам обнаружения ошибок". Настоятельно рекомендую;
  
  
• ftape (драйвер ленточного накопителя из дистрибьютива Linux)
  Ну, какая же запись на магнитную ленту обходится без корректирующих кодов? Представить себе такое, прямо-таки скажем, довольно затруднительно. Поэтому анализ исходных текстов драйверов ленточных накопителей дает довольно-таки богатую пищу для размышлений (при условии, конечно, что исследуемый драйвер действительно использует коды Рида-Соломона, а не что-нибудь другое). Линуховый драйвер ftape как раз и является тем драйвером, что вам нужен;
  
  
• James S. Plank GFLIB "C Procedures for Galois Field Arithmetic and Reed-Solomon Coding"
  Библиотека для работы с кодами Рида-Соломона. Содержит в себе полные исходные тексты всех необходимых функций и распространяется по лицензии GPL. Найти ее можно на любом GNU'том сайте, например, здесь: http://www.cs.utk.edu/~plank/plank/gflib/gflib.tar;

Полиномиальная арифметика и поля Галуа

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

Полиномиальная арифметика

Полиномиальной арифметике посвящен шестой раздел третьего тома "Искусства программирования" Дональда Кнута, где полиному дается следующее определение "Формально говоря, полином над S представляет собой выражение вида: u(x) = u_nxⁿ + ... + u¹x + u₀, где коэффициенты u_n,..., u₁, u₀ - элементы некоторой алгебраической системы S, а переменная x может рассматриваться как формальный символ без определяющего значения. Будем полагать, что алгебраическая система S представляет собой коммутативное кольцо с единицей. Это означает, что S допускает операции сложения, вычитания и умножения, удовлетворяющие обычным свойствам: сложение и умножение являются ассоциативными и коммутативными бинарными операциями, определенными на S, причем умножение дистрибьютивно по отношению к сложению. Существует также единичный элемент по сложению 0 и единичный элемент по умножению 1, такие, что a + 0 = a и a * 1 = a для всех a из S. Вычитание является обратной по отношению к сложению операцией, но о возможности деления как операции, обратной по отношению к умножению, ничего не предполагается. Полином 0x^n + m + ... + 0x ^n + 1 +  u_nxⁿ + ... + u¹x + u₀ рассматривается как идентичный u_nxⁿ + ... + u¹x + u₀, хотя формально он отличается от него".

Таким образом, вместо того, чтобы представлять информационное слово D, кодовое слово C и остаток от деления R в виде целых чисел (как это делалось нами ранее), мы можем связать их с соответствующими коэффициентами двоичного полинома, выполняя все последующие математические манипуляции по правилам полиномиальной арифметики. Выигрыш от такого преобразования, на первый взгляд, далеко неочевиден, но не будем спешить, а лучше преобразуем любое пришедшее нам в голову число (например, 69h) в двоичный полином. Запустив "Калькулятор" или любое другое подходящее приложение по вашему вкусу, переведем наше число в двоичный вид (при соответствующих навыках эту операцию можно выполнить и в уме, см. "Техника и философия хакерских атак"): 69h -> 1101001.

Ага, крайний правый коэффициент равен единице, затем следуют два нулевых коэффициента, потом единичный коэффициент... короче говоря, получается следующее: 1x⁶ + 1x⁵ + 0x⁴ + 1x³+ 0x² + 0x + 1. По сути говоря, битовая строка "1101001" является одной из форм записи вышеуказанного полинома - ненаглядной с точки зрения неподготовленного человека, но удобной для машинной обработки. Постойте, но если 69h уже представляет собой полином, то в чем разница между сложением полиномов 69h и 27h и сложением целых чисел 69h и 27h?! Разница, несомненно, есть. Как еще показал Ницше: фактов нет, а есть одни лишь интерпретации. Интерпретация же чисел и полиномов различна и математические операции над ними выполняются по совершенно независимым правилам.

Коэффициенты в полиномиальной арифметики строго типизированы и коэффициент при x^k имеет иной тип, нежели при x^m (конечно, при том условии, что k не равно m). А операции над числами различных типов категорически недопустимы! Все коэффициенты обрабатываются независимо, а возникающий при этом перенос в старший разряд (заем из старшего разряда) попросту не учитывается. Покажем это на примере сложения чисел 69h и 27h:

 1101001 (69h)                 1101001 (69h)
+0100111 (27h)                +0100111 (27h)
 -------                        -------
 1001110 (4Eh)                10010000 (90h)

Листинг 11. Сложение, выполненное по правилам полиномиальной двоичной арифметики (слева) и сложение, выполненное по правилам обычной арифметики (справа).

Простейшие расчеты показывают, что сложение полиномов по модулю два, дает тот же самый результат, что их вычитание и "волшебным" образом совпадает с битовой операцией XOR. Впрочем, совпадение с XOR - чистая случайность, но вот эквивалентность сложения и вычитания заставляет заново пересматривать привычную природу вещей, вспоминая задачки из серии "у Маши было одно яблоко, Петя отнял у нее его, затем ей подарил еще одно, спрашивается: сколько всего яблок у Маши осталось? А сколько у нее было бы, если бы первое яблоко осталось неотнятым?". С точки зрения арифметики по модулю два ответ: один и ноль соответственно. Да! Не отними бы Петя у Маши яблоко, 1 + 1 = 0 и бедная Маша вообще осталась бы ни с чем. Так что мальчики, почаще отнимайте яблоки и девушек - учите их компьютерной грамотности!

Впрочем, мы отвлеклись. Ладно, оставим в покое половые разборки между молодежью, а вернемся к фиктивному члену x нашего полинома и его коэффициентам. Благодаря их типизации и отсутствию взаимных связей, мы можем осуществлять обработку сколь угодно длинных чисел, просто XOR'я составляющие их биты на потоке. Это и есть одно из тех достоинств полиномиальной арифметики, которые не видны с первого взгляда, но благодаря которым полиномиальная арифметика стала так широко распространена.

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

Поля Галуа

В далеких шестидесятых, когда компьютеры были большими, а 20-мегабайтовые винчестеры напоминали собой стиральные машины, родилась одна из красивейших легенд о зеленом инопланетном существе, прилетевшим со звезд и записавшим всю Британскую энциклопедию на тонкий металлический стержень нежно-серебристого цвета, который существо и увезло с собой. Сегодня, когда габариты 100 Гб жестких дисков сократились до размеров сигаретной пачки, такая плотность записи информации уже не кажется удивительной и даже вызывает улыбку. Но! Все дело в том, что инопланетное существо обладало технологией записи бесконечного количества информации на бесконечно крошечном отрезке и Британская энциклопедия была выбрала лишь для примера. С тем же успехом инопланетянин мог скопировать содержимое всех серверов Интернета, нанеся на свой металлический стержень всего одну-единственную риску. Не верите? А зря! Переводим Британскую энциклопедию в цифровую форму, получая огромное-преогромное число. Затем - ставим впереди него запятую, преобразуя записываемую информацию в длиннющую десятичную дробь. Теперь только остается найти два числа A и B, таких, что результат деления A и B как раз и будет равен данному числу с точностью до последнего знака. Запись этих чисел на металлических стержень осуществляется нанесением риски, делящей последний на два отрезка с длинами, кратными величинам А и B соответственно. Для считывания информации достаточно всего лишь измерить длины отрезков А и B, а затем - поделить один на другой. Первый десяток чисел после запятой будет более или менее точен, ну а потом... Потом жестокая практика опустит абстрактную теорию по самые помидоры, окончательно похоронив последнюю под толстым слоем информационного мусора, возникающего из невозможности точного определения геометрических размеров объектов реального мира.

В цифровом мире дела обстоят еще хуже. Каждый программист знает, что на деление целых и вещественных чисел наложены достаточно жесткие ограничения. Помимо того, что деление весьма прожорливая в плане процессорных ресурсов операция, так она еще и математически неточная! То есть, если c = a * b, то еще не факт, что a = c / b! Таким образом, для практической реализации кодов Рида-Соломона обычная арифметика непригодна и приходится прибегать к помощи особой математики - математики конечных групп Галуа.

Под группой здесь понимается совокупность целых чисел, последовательно пронумерованных от 0 до 2ⁿ - 1 например: {0, 1, 2, 3} или {00h 01h, 02h, 03h, 04h, 05h, 06h, 07h, 08h, 09h, 0Ah, 0Bh, 0Ch, 0Dh, 0Eh, 0Fh}. Группы, содержащие 2ⁿ элементов, называются полями Галуа (Galois Field) и обозначаются так: GF(2ⁿ) ^[4].

Члены групп в обязательном порядке подчиняются ассоциативному, коммутативному и дистрибьютивному законам, но обрабатываются довольно противоестественным на первый взгляд образом:

1. Сумма двух любых членов группы всегда присутствует в данной группе;
   
   
2. Для каждого члена "а" группы существует тождественный (identity) ему член, обычно записываемый как "e", удовлетворяющий следующему условию: a + e = e + a = a;
   
   
3. Для каждого члена "a" группы существует обратный (inverse) ему член "-a", такой что: a + -a = 0;

Начнем с первого тезиса. Не кажется ли он вам бредом? Допустим, у нас есть группа {0, 1, 2, 3}. Это каким же в дупель пьяным нужно быть, чтобы при вычислении значения 2 + 3 получить число меньшее или равное 3?! Оказывается, сложение в полях Галуа осуществляется без учета переноса и сумма двух членов группы равна: c = (a + b) % 2ⁿ, где операция "%" обозначает взятие остатка. Применительно к нашему случаю: (2 + 3) % 4 = 1. У математиков это называется "сложением по модулю 4".

Естественно, вас интересует: а применяется ли сложение по модулю на практике или используется лишь в абстрактных конструкциях теоретиков? Хороший вопрос! Сложение по модулю мы машинально выполняем десятки раз на дню, даже не задумываясь о том, что это и есть сложение без учета переноса. Вот, например, проснувшись в шесть вечера по утру, вы просидели за компьютером девять часов кряду, а потом неожиданно бросили взгляд на свои наручные часы. Какое положение занимала часовая стрелка в это время, при условии, что часы идут точно? Искомое значение со всей очевидностью представляет собой сумму 6 и 9 по модулю 12 и равно оно: (6 + 9) % 12 = 3. Вот вам наглядный пример практического использования арифметики Галуа. А теперь давайте в порядке эксперимента вычтем из числа 3 число 6... (если не догадались, как это правильно сделать, возьмите в руки часы).

Теперь самое главное: раз результат деления одного члена группы на другой, естественно, не равный нулю член, в обязательном порядке должен присутствовать в данной группе, то несмотря на то, что деление осуществляется в целых числах, оно будет точным. Точным, а не округленным! Следовательно, если c = a * b, то a = c / b. Другими словами, умножение и деление непротиворечивым образом определено для всех членов группы, конечно, за исключением невозможности деления на нуль, причем расширения разрядной сетки при умножении не происходит!

Конечно, это не совсем обычное умножение (и далеко не во всяком поле Галуа дважды два будет рано четырем), однако никто и не требует от арифметики Галуа ее соответствия "здравому смыслу" и "житейскому опыту". Главное, что она работает, причем работает хорошо. И существование жестких дисков, CD-ROM/DVD приводов - лучшее тому подтверждение, ибо все они так или иначе используют эту арифметику в своих целях.

Как уже говорилось, в вычислительной технике наибольшее распространение получили поля Галуа с основанием 2, что объясняется естественностью этих полей с точки зрения машинной обработки, двоичной по своей природе.

Для реализации кодера/декодера Рида-Соломона нам потребуются четыре базовых арифметических операции: сложение, вычитание, умножение и деление. Ниже они будут рассмотрены во всех подробностях.

Сложение и вычитание в полях Галуа

Сложение по модулю два в полях Галуа тождественно вычитанию и реализуется битовой операцией XOR. Этот вопрос мы уже обсуждали при изучении полиномиальной арифметики, поэтому не будем лишний раз повторяться, а просто приведем законченный пример программной реализации функции сложения/вычитания:

Листинг 12. Функция, реализующая сложение/вычитание в полях Галуа.

Умножение в полях Галуа

Открыв учебник математики за третий класс (если мне не изменяет память), мы найдем, что умножение представляет собой многократное сложение и, коль скоро, сложение в полях Галуа мы выполнять уже научились, мы имеем все основания считать, что реализация функции умножения не создаст особого труда. Так? А вот и нет! Я всегда знал, что дважды два равно четырем, до конца никогда не верил в это и, впервые столкнувшись с полями Галуа понял, насколько был прав ^[5]. Выяснилось, что существуют и такие математики, где дважды два не равно четырем, а операция умножения определяется не через сложение, а совсем по-другому.

Действительно, если попытаться "обернуть" функцию gf_sum в цикл, мы получим то же самое сложение только в профиль. a * b будет равно а, если b четно, и нулю, если b - нечетно. Ну, и кому такое умножение нужно? Собственно, функция "настоящего" умножения Галуа настолько сложна и ресурсоемка, что для упрощения ее реализации приходится к временному преобразованию полиномов в индексную форму, последующему сложению индексов, выполняемому по модулю GF, и обратному преобразованию суммы индексов в полиномиальную форму.

Что такое индекс? Это - показатель степени при основании два, дающий искомый полином. Например, индекс полинома 8 равен 3 (2³ = 8), а индекс полинома 2 равен 1 (2¹ = 2). Легко показать, что a * b = 2ⁱ + 2^j = 2^(i+j). В частности, 2 * 8 = 2³ + 2¹ = 2⁽³⁺¹⁾ = 4⁴ = 16. Составим следующую табличку и немного поэкспериментируем с ней:

i          alpha_of[i]
----------------------
001        0
002        1
004        2
008        3
016        4

Таблица 2. Таблица полиномов (левая колонка) и соответствующих им степеней двойки (правая колонка).

До сих пор мы оперировали понятиями привычной нам арифметики и потому добрые две трети полей таблицы остались незаполненными. В самом деле, уравнения типа 2^x = 3 в целых числах не разрешимы и ряд индексов не соответствует никаким полиномам! Так-то, оно так, но в силу того, что количество полиномов всякого поля Галуа равно количеству всевозможных индексов, мы можем определенным образом сопоставить их друг другу, закрыв глаза на то, что с точки зрения обычной математики такое действие не имеет никакого смысла. Конкретная схема сопоставления может быть любой, главное - чтобы она была внутренне непротиворечивой, то есть удовлетворяла всем правилам групп, перечисленным выше.

Естественно, поскольку от выбранной схемы сопоставления напрямую зависит и конечный результат, обе стороны (кодер и декодер Рида-Соломона) должны соблюдать определенные договоренности. Однако различные кодеры/декодеры Рида-Соломона могут использовать различные схемы сопоставления, несовместимые друг с другом.

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

i alpha index i alpha index i alpha index i alpha index i alpha index i alpha ind
000 001  -1   043 119 218   086 177 219   129 023 112   172 123 220   215 239 170
001 002   0   044 238 240   087 127 189   130 046 192   173 246 252   216 195 251
002 004   1   045 193  18   088 254 241   131 092 247   174 241 190   217 155  96
003 008  25   046 159 130   089 225 210   132 184 140   175 255  97   218 043 134
004 016   2   047 035  69   090 223  19   133 109 128   176 227 242   219 086 177
005 032  50   048 070  29   091 163  92   134 218  99   177 219  86   220 172 187
006 064  26   049 140 181   092 091 131   135 169  13   178 171 211   221 069 204
007 128 198   050 005 194   093 182  56   136 079 103   179 075 171   222 138  62
008 029   3   051 010 125   094 113  70   137 158  74   180 150  20   223 009  90
009 058 223   052 020 106   095 226  64   138 033 222   181 049  42   224 018 203
010 116  51   053 040  39   096 217  30   139 066 237   182 098  93   225 036  89
011 232 238   054 080 249   097 175  66   140 132  49   183 196 158   226 072  95
012 205  27   055 160 185   098 067 182   141 021 197   184 149 132   227 144 176
013 135 104   056 093 201   099 134 163   142 042 254   185 055  60   228 061 156
014 019 199   057 186 154   100 017 195   143 084  24   186 110  57   229 122 169
015 038  75   058 105   9   101 034  72   144 168 227   187 220  83   230 244 160
016 076   4   059 210 120   102 068 126   145 077 165   188 165  71   231 245  81
017 152 100   060 185  77   103 136 110   146 154 153   189 087 109   232 247  11
018 045 224   061 111 228   104 013 107   147 041 119   190 174  65   233 243 245
019 090  14   062 222 114   105 026  58   148 082  38   191 065 162   234 251  22
020 180  52   063 161 166   106 052  40   149 164 184   192 130  31   235 235 235
021 117 141   064 095   6   107 104  84   150 085 180   193 025  45   236 203 122
022 234 239   065 190 191   108 208 250   151 170 124   194 050  67   237 139 117
023 201 129   066 097 139   109 189 133   152 073  17   195 100 216   238 011  44
024 143  28   067 194  98   110 103 186   153 146  68   196 200 183   239 022 215
025 003 193   068 153 102   111 206  61   154 057 146   197 141 123   240 044  79
026 006 105   069 047 221   112 129 202   155 114 217   198 007 164   241 088 174
027 012 248   070 094  48   113 031  94   156 228  35   199 014 118   242 176 213
028 024 200   071 188 253   114 062 155   157 213  32   200 028 196   243 125 233
029 048   8   072 101 226   115 124 159   158 183 137   201 056  23   244 250 230
030 096  76   073 202 152   116 248  10   159 115  46   202 112  73   245 233 231
031 192 113   074 137  37   117 237  21   160 230  55   203 224 236   246 207 173
032 157   5   075 015 179   118 199 121   161 209  63   204 221 127   247 131 232
033 039 138   076 030  16   119 147  43   162 191 209   205 167  12   248 027 116
034 078 101   077 060 145   120 059  78   163 099  91   206 083 111   249 054 214
035 156  47   078 120  34   121 118 212   164 198 149   207 166 246   250 108 244
036 037 225   079 240 136   122 236 229   165 145 188   208 081 108   251 216 234
037 074  36   080 253  54   123 197 172   166 063 207   209 162 161   252 173 168
038 148  15   081 231 208   124 151 115   167 126 205   210 089  59   253 071  80
039 053  33   082 211 148   125 051 243   168 252 144   211 178  82   254 142  88
040 106  53   083 187 206   126 102 167   169 229 135   212 121  41   255 000 175
041 212 147   084 107 143   127 204  87   170 215 151   213 242 157
042 181 142   085 214 150   128 133   7   171 179 178   214 249  85

Листинг 13. Lock-up-таблица для GF(256) Первая слева колонка - полиномы/индексы (обычно обозначается как i), вторая - таблица степеней примитивного полинома 2 (обычно обозначается как alpha_of), третья - индексы, соответствующие данному полиному (обычно обозначается как index_of).

С помощью данной таблицы вы легко сможете осуществлять преобразование из полиномиальной формы в индексную и наоборот. Как пользоваться этой таблицей? Допустим, мы хотим умножить полиномы 69 и 96. Находим в первой колонке число 69. Ему соответствует alpha 47, запоминаем (записываем его на бумажке) и переходим к числу 96, alpha которого равен 217. Складываем 47 и 217 по модулю 256, получая в результате: (217 + 47) % 256 = 8. Теперь переводим результат произведения из индексной формы в полиномиальную: находим в первой колонке число 8 и в третьей колонке видим соответствующий ему полином: 3. (Если же мы выполним обратную операцию, разделив 3 на 69, мы получим 96, что доказывает непротиворечивость операций деления и умножения, а также всей арифметики Галуа в целом). Быстро, не правда ли, хотя местами и не совсем понятно, почему таблица составлена именно так, а не иначе? Хуже всего, что достоверность результата нельзя почувствовать "в живую", поскольку все это - абстракции чистейшей воды, что серьезно осложняет отладку программы (сложно отлаживать то, чей принцип работы до конца не понимаешь).

Впрочем, таблицу умножения не обязательно набивать с клавиатуры вручную и ее вполне можно генерировать и на лету по ходу исполнения программы. Один из примеров реализации генератора выглядит так:

Листинг 14. Процедура генерации look-up таблицы быстрого умножения полиномов.

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

Листинг 15. Функция быстрого табличного умножения полиномов в полях Галуа.

Деление в полях Галуа

Деление в полях Галуа осуществляется практически точно так же, как и умножение с той лишь разницей, что индексы не прибавляются, а вычитаются друг из друга. В самом деле: a / b = 2ⁱ / 2^j = 2^(i-j). Для перевода из полиномиальной в индексную форму и наоборот может использоваться приводимая выше look-up таблица.

Естественно, не забывайте о том, что какими бы извращенными поля Галуа не были, а на нуль даже в абстрактной арифметике делить нельзя и функция деления должна быть снабжена соответствующей проверкой.

Листинг 16. Функция быстрого табличного деления в полиномов в полях Галуа.

Простейшие практические реализации

Хорошим примером воплощения кодера/декодера Рида-Соломона являются древние модели жестких дисков, разработанных в недрах фирмы IBM. Модель IBM 3370 имела простой и наглядный кодер/декодер Рида-Соломона типа (174,171) в поле Галуа GF(256). Другими словами, он оперировал 8-битными ячейками (2⁸ = 256), и на 171 информационный байт приходилось 3 байта суммы четности, что в результате давало кодовое слово с размером 174 байт, причем, как мы увидим далее, все три байта контрольной суммы рассчитывались совершенно независимо друг от друга, поэтому фактически кодер/декодер Рида-Соломона оперировал одним байтом, что значительно упрощало его архитектуру.

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

Ниже приведен фрагмент оригинальной прошивки жесткого диска IBM 3370 (только не спрашивайте: откуда он у меня взялся):

Листинг 17. Ключевой фрагмент кодера Рида-Соломона, вырванный из прошивки IBM 3370.

Листинг 18. Ключевой фрагмент декодера Рида-Соломона, вырванный из IBM 3370.

Ну, что, слабо нам разобраться, как он работает? Что касательно переменной s0 - с ней все предельно ясно: она хранит контрольную сумму, рассчитанную по тривиальному алгоритму. Как вы наверное помните, сложение в полях Галуа осуществляется логической операцией XOR и потому: s0 += input[i].

Назначение переменной s1 выяснить сложнее и чтобы понять суть разворачивающегося вокруг нее метаболизма, мы должны знать содержимое таблицы GF_mult_by_alpha. Несмотря на то, что по соображениям экономии бумажного пространства она здесь не приводится, ее имя говорит само за себя: содержимое s1 суммируется с очередным байтом контролируемого потока данных и умножается на так называемый примитивный член, обозначаемый как alpha, и равный двум. Другими словами: s1 = 2 * (s1 + input[i]).

Допустим, один из байтов потока данных впоследствии будет искажен (обозначим его позицию как err_i), тогда индекс искаженного байта можно определить тривиальным делением s1 на s0. Почему? Так ведь выражение s1 = 2 * (s1 + input[i]) по своей сути есть ни что иное, как завуалированное умножение информационного слова на порожденный полином, динамически генерируемый на основе своего примитивного члена alpha. А контрольная сумма информационного слова, хранящаяся в переменной s0, фактически представляет собой то же самое информационное слово, только представленное в более "компактной" форме. И, как уже говорилось в предыдущей главе: если ошибка произошла в позиции x, то остаток от деления кодового слова на порожденный полином будет равен k = 2^x. Остается лишь по известному k вычислить x, что в данном случае осуществляется путем обращения к таблице GF_log_base_alpha, хранящей пары соответствий между k и 2^x. Коль скоро позиция сбойного байта найдена, его можно исправить путем XOR'а с рассчитанной контрольной суммой s0 (input[err_i] ^= s0). Конечно, сказанное справедливо только для одиночных ошибок, а искажения двух и более байт на блок данный алгоритм исправить не в силах. Собственно, для этого и присутствует третий байт контрольной суммы - sm1, защищающий декодер от "политнекорректных" попыток исправления ошибок, когда их больше одной. Если выражение s1 / s0 = sm1 * s0 становится ложным, контроллер винчестера может засвидетельствовать факт наличия множественных ошибок, констатируя невозможность их исправления.

Однако, как хорошо известно - дефекты магнитной поверхности имеют тенденцию образовывать не одиночные, а групповые ошибки. И чтобы хоть как-то компенсировать слабость корректирующего алгоритма, парни из IBM прибегли к чередованию байт. Винчестер IBM 3370 имел чередование 3:1, то есть сначала шел первый байт первого блока, за ним - первый байт второго блока, за ним - первый байт третьего и только потом - второй байт первого блока. Такой трюк усиливал корректирующую способность винчестера с одной одиночной ошибки, до трех последовательно искаженных байт... Однако если разрушению подвергались не соседние байты, то корректирующая способность вновь опускалась до значений в один искаженный байт на блок, но вероятность такого события была несравнимо меньше.

Естественно, что данный алгоритм может быть реализован не только в самом жестком диске, но и вне его. Варьируя размер блоков и степень чередования, вы обеспечите себе лучшую или худшую защищенность при большей или меньшей избыточности информации. Действительно, пусть у нас есть N секторов на диске. Тогда, разбив их на блоки по 174  сектора в каждом и выделив 3 сектора для хранения контрольной суммы, мы сможем восстановить по меньшей мере N / 174 секторов диска. Исходя из средней емкости диска в 100 Гб (что соответствует 209.715.200 секторам), мы сможем восстановить до 1.205.259 секторов даже при их полном физическом разрушении, затратив всего лишь 2% дискового пространства для хранения контрольных сумм. Согласитесь, что редкая "сыпка" винчестера проходит столь стремительно, чтобы корректирующих способностей кода Рида-Соломона оказалась недостаточно для ее воскрешения (конечно, если эту "сыпку" вовремя заметить и если коэффициент чередования выбран правильно - так, что сектора, принадлежащие одному дисковому блину обслуживались бы разными корректирующими блоками, в противном случае при повреждении поверхности одного из блинов возникнет групповая ошибка, уже неисправимая данной программой).

А как быть, если "навернется" весь жесткий диск целиком? Наиболее разумный выход - создать массив из нескольких дисков, хранящих полезную информацию вперемешку с корректирующими кодами. Главный минус такого подхода - его неэффективность на массивах, состоящих из небольшого количества жестких дисков. Разумный минимум: четыре информационных диска и один контрольный, тогда потеря любого из информационных дисков компенсируется оставшихся в живых контрольным. Ну, а потерянный контрольный диск элементарным образом заменяется на новый, с последующим пересчетом всех контрольные кодов. Правда, одновременный выход двух дисков из строя - это кранты. Массив из пятнадцати дисков, двенадцать из которых - информационные, а оставшиеся три - контрольные, намного более отказоустойчив и допускает одновременный крах двух любых дисков, а при благоприятном стечении обстоятельств - и трех.

Собственно, во всем этом ничего нового нет и соответствующие RAID-контроллеры можно купить буквально в любом магазине. Однако... мне трудно себе представить, сколько будет стоит RAID-контроллер уровня 15 и удастся ли его вообще заставить работать (по личному опыту могу сказать, что RAID-контроллеры даже начальных уровней - вещь крайне глючная, капризная и требовательная как к железу, так и к операционному окружению). Наконец, практически все RAID-контроллеры требуют наличия абсолютно идентичных, ну или близких по своим характеристикам и/или интерфейсам дисков. А коли таковых нет?

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

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

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

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

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

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

С другой стороны, для практического использования корректирующих кодов можно и не вникать в их сущность, просто откомпилировав исходные тексты кодера/декодера Рида-Соломона, приведенные в данной главе. Также вы можете воспользоваться любой законченной библиотекой, поставляемой сторонними разработчикам. В качестве альтернативного примера в заключении этой главы будет кратно описан интерфейс библиотеки ElByECC.DLL, разработанной компанией "Elaborate Bytes" и распространяемой вместе с популярным копировщиком Clone CD. Известнейший прожигатель дисков всех времен и народов Nero 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 вполне реально.

Цепи, основанные на регистрах сдвига, обычно называют фильтрами. Блок-схема фильтра, осуществляющего деление полинома на константу, приведена на рис. 2. Пусть вас не смущает тот факт, что деление реализуется посредством умножения и сложения. Данный прием базируется на вычислении системы двух рекуррентных равенств:

Формула 1. Деление полинома на константу посредством умножения и сложения.

Здесь: Q^(r)(x) и R^(r)(x) - соответственно, частное и остаток на r-шаге рекурсии. Поскольку сложение и вычисление, выполняемое по модулю два, тождественны друг другу, для реализации делителя нам достаточно иметь всего два устройства - устройство сложения и устройство умножения, а без устройства вычитания можно обойтись.

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

Рисунок 2. Устройство простейшего кодера Рида-Соломона.

Простейший пример программной реализации такого фильтра приведен ниже. Это законченный кодера Рида-Соломона, вполне пригодный для практического использования. Конечно, при желании его можно было бы и улучшить, но тогда неизбежно пострадала бы наглядность и компактность листинга.

Листинг 19. Исходный текст простейшего кодера Рида-Соломона.

Декодер (decoder)

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

• Вычисления синдрома ошибки (синдромный декодер);
  
  
• Построения полинома ошибки, осуществляемое либо посредством высокоэффективного, но сложно реализуемого алгоритма Берлекэмпа-Месси, либо посредством простого, но тормозного Евклидового алгоритма;
  
  
• Нахождения корней данного полинома, обычно решающееся лобовым перебором (алгоритм Ченя);
  
  
• Определения характера ошибки, сводящееся к построению битовой маски, вычисляемой на основе обращения алгоритма Форни или любого другого алгоритма обращения матрицы;
  
  
• Наконец, исправления ошибочных символов, путем наложения битовой маски на информационное слово и последовательного инвертирования всех искаженных битов через операцию XOR.

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

Рисунок 3. Схема авторегрессионого спектрального декодера корректирующих кодов Рида-Соломона.

Синдромный декодер

Грубо говоря, синдром есть остаток деления декодируемого кодового слова c(x) на порожденный полином g(x), и если этот остаток равен нулю, кодовое слово считается неискаженным. Ненулевой остаток свидетельствует о наличии, по меньшей мере, одной ошибки. Остаток от деления дает многочлен, не зависящий от исходного сообщения и определяемый исключительно характером ошибки (syndrome - греческое слово, обозначающее совокупность признаков и/или симптомов, характеризующих заболевание).

Принятое кодовое слово v с компонентами v_i = c_i + e_i, где i = 0, ... n - 1, представляет собой сумму кодового слова c и вектора ошибок e. Цель декодирования состоит в очистке кодового слова от вектора ошибки, описываемым полиномом синдрома и вычисляемом по формуле S_j = v(a^j+j0-1), где j изменяется от 1 до 2t, а "a" представляет собой примитивный член "альфа", который мы уже обсуждали в предыдущей главе. Да, мы снова выражаем функцию деления через умножение, поскольку деление - крайне неэффективная в смысле производительности операция.

Блок-схема устройства, осуществляющего вычисление синдрома, приведена на рис. 4 Как видно, она представляет собой типичный фильтр (сравните ее со схемой рис. 2), а потому ни в каких дополнительных пояснениях не нуждается.

Рисунок 4. Блок-схема цепи вычисления синдрома.

Вычисление синдрома ошибки происходит итеративно, так что вычисление результирующего полинома (также называемого ответом от английского "answer") завершается непосредственно в момент прохождения последнего символа четности через фильтр. Всего требуется 2t циклов "прогона" декодируемых данных через фильтр - по одному прогону на каждый символ результирующего полинома.

Пример простой программной реализации синдромного декодера содержится в листинге 2 и он намного нагляднее его словесного описания.

Полином локатора ошибки

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

Если количество искаженных символов не превышает t, между синдромом и локатором ошибки существует следующее однозначное соответствие, выражаемое следующей формулой: НОД[xn-1, E(x)] = L(x) и вычисление локатора сводится к задаче нахождения наименьшего общего делителя, успешно решенной еще Евклидом и элементарно реализуемой как на программном, так и на аппаратном уровне. Правда, за простоту реализации нам приходиться расплачиваться производительностью, точнее - непроизводительностью данного алгоритма, и на практике обычно применяют более эффективный, но и более сложный для понимания алгоритм Берлекэмпа-Месси (Berlekamp-Massy), подробно описанный Кнутом во втором томе "Искусства программирования" (см. также "Теория и практика кодов, контролирующих ошибки" Блейхута) и сводящейся к задаче построения цепи регистров сдвига с линейной обратной связью и по сути своей являющегося разновидностью авторегрессионого фильтра, множители в векторах которого и задают полином L.

Декодер, построенный по такому алгоритму, требует не более 3t операций умножения в каждой из итерации, количество которых не превышает 2t. Таким образом, решение поставленной задачи укладывается всего в 6t² операций умножения. Фактически, поиск локатора сводится к решению системы из 2t уравнений - по одному уравнению на каждый символ синдрома - c t неизвестными. Неизвестные члены и есть позиции искаженных символов в кодовом слове v. Легко видеть, если количество ошибок превышает t, система уравнений становится неразрешима и восстановить разрушенную информацию в этом случае не представляется возможным.

Блок-схема алгоритма Берлекэмпа-Месси приведена на рис. 5, а его законченная программа реализация содержится в листинге 2.

Рисунок 5. Структурная схема алгоритма Берлекэмпа-Месси.

Корни полинома

Коль скоро полином локатора ошибки нам известен, его корни определяют местоположение искаженных символов в принятом кодовом слове. Остается эти корни найти. Чаще всего для этого используется процедура Ченя (Chien search), аналогичная по своей природе обратному преобразованию Фурье и фактически сводящаяся к тупому перебору (brute force, exhaustive search) всех возможных вариантов. Все 2^m возможных символов один за другим подставляются в полином локатора в порядке социалистической очереди и затем выполняется расчет полинома. Если результат обращается в ноль - считается, что искомые корни найдены.

Восстановление данных

Итак, мы знаем какие символы кодового слова искажены, но пока еще не готовы ответить на вопрос: как именно они искажены. Используя полином синдрома и корни полинома локатора, мы можем определить характер разрушений каждого из искаженных символов. Обычно для этой цели используется алгоритм Форни (Forney), состоящий из двух стадий: сначала путем свертки полинома синдрома полиномом локатора L мы получаем некоторый промежуточный полином, условно обозначаемый греческой буквой W. Затем, на основе W-полинома, вычисляется нулевая позиция ошибки (zero error location), которая в свою очередь делится на производную от L-полинома. В результате получается битовая маска, каждый из установленных битов которой соответствует искаженному биту и для восстановления кодового слова в исходный вид, все искаженные биты должны быть инвертированы, что осуществляется посредством логической операции XOR.

На этом процедура декодирования принятого кодового слова считается законченной. Остается отсечь (n - k) символов четности и полученное информационное слово готово к употреблению.

Исходный текст декодера

Ниже приводится исходный текст полноценного декодера Рида-Соломона, снабженный минимально разумным количеством комментариев. При возникновении трудностей в анализе этого листинга обращайтесь к блок-схемам, приведенным на рис. 3, 4 и 5 - они помогут.

Листинг 20. Исходный текст простейшего декодера Рида-Соломона.

Интерфейс с библиотекой ElByECC.DLL

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

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

Насколько законно подобное дизассемблирование? Да, дизассемблирование сторонних программных продуктов действительно запрещено, но тем не менее оно законно. Здесь уместно провести аналогию со вскрытием пломб вашего телевизора, влекущее потерю гарантии, но отнюдь не приводящее к уголовному преследованию. Также, никто не запрещает вызывать функции чужой библиотеки из своей программы. Нелегально распространять эту библиотеку в составе вашего программного обеспечения, действительно, нельзя, но что мешает вам попросить пользователя установить данную библиотеку самостоятельно?

Ниже приводится описание важнейших функций библиотеки ElByECC.DLL, входящей в состав известного копировщика защищенных лазерных дисков Clone CD, условно-бесплатную копию которого можно скачать c cайта: http://www.elby.ch/?lt;/u>. Сам Clone CD проработает всего лишь 21 день, а затем потребует регистрации, однако на продолжительность использования библиотеки ElByECC.DLL не наложено никаких ограничений.

Усилиями хакера по имени МЫЩЪХ был создан h-файл, содержащий прототипы основных функций библиотеки ElByECC.DLL, специальная редакция которого была любезно предоставлена им для настоящей книги.

Несмотря на то, что библиотека ElByECC.DLL ориентирована на работу с секторами лазерных дисков, она может быть приспособлена и для других целей, например, построения отказоустойчивых дисковых массивов, о которых говорилось в предыдущей главе.

Краткое описание основных функций библиотеки приводится ниже.

Подключение библиотеки ElByECC.DLL к своей программе

Существует по меньшей мере два способа подключения динамических библиотек к вашим программам. При динамической компоновке, адреса требуемых функций определяются посредством вызова GetProcAddress, причем сама библиотека ElByECC.DLL должна быть предварительно загружена через LoadLibray. Это может выглядеть например так (обработка ошибок для простоты опущена):

Листинг 21. Динамическая загрузка библиотеки ElByECC.DLL.

Статическая компоновка предполагает наличие специального lib-файла, который может быть автоматически сгенерирован утилитой implib из пакета Borland C++ любой подходящей версии, представляющую собой утилиту командной строки, вызываемую так: "implib.exe ?a ElByECC.lib ElByECC.lib".

GenECCAndEDC_Mode1

Функция GenECCAndEDC_Mode1 осуществляет генерацию корректирующих кодов на основе 2048-байтового блока пользовательских данных и имеет следующий прототип:

Листинг 22. Прототип функции GenECCAndEDC_Mode1.

userdata_src - указатель на 2048-байтовый блок пользовательских данных, для которых необходимо выполнить расчет корректирующих кодов. Сами пользовательские данные в процессе выполнения функции остаются неизменными и автоматически копируются в буфер целевого сектора, где к ним добавляется 104 + 172 байт четности и 4 байта контрольной суммы.

header_src - указатель на 4-байтовый блок, содержащий заголовок сектора. Первые три байта занимает абсолютный адрес, записанный в BCD-форме, а четвертый байт отвечает за тип сектора, которому необходимо присвоить значение 1, соответствующий режиму "корректирующие коды задействованы".

raw_sector_mode1_dst - указатель на 2352-байтный блок, в который будет записан сгенерированный сектор, содержащий 2048-байт пользовательских данных и 104 + 172 байт корректирующих кодов вместе 4 байтами контрольной суммы и представленный следующей структурой:

Листинг 23. Структура "сырого" сектора.

При успешном завершении функция возвращает ненулевое значение и ноль в противном случае.

CheckSector

Функция CheckSector осуществляет проверку целостности сектора по контрольной сумме и при необходимости выполняет его восстановление по избыточным кодам Рида-Соломона.

Листинг 24. Прототип функции CheckSector.

sector - указатель на 2352-байтовый блок данных, содержащий подопытный сектор. Лечение сектора осуществляется "в живую", т.е. непосредственно по месту возникновения ошибки. Если количество разрушенных байт превышают корректирующие способности кодов Рида-Соломона, исходные данные остаются неизменными;

DO - флаг, нулевое значение которого указывает на запрет модификации сектора. Другими словами, соответствует режиму TEST ONLY. Ненулевое значение разрешает восстановление данных, если они действительно подверглись разрушению.

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

Финал

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

Листинг 25. Пример вызова функций ElByECC.DLL из своей программы.

^[2] Т.е. если сумма проверяемых бит четна, то контрольный бит равен нулю и, соответственно, наоборот.

^[4] На самом деле, полями Галуа называют любые конечные поля, но в данном контексте мы будем говорить лишь о тех полях, количество членов которых равно 2ⁿ.