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

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

Программная реализация корректирующих кодов Рида-Соломона действительно очень сложна и действительно требует определенной математической подготовки, изложение основ которой может показаться скучным и неинтересным для «системщиков» и «железячников», но иного пути, видимо, нет. В конце концов никто не обещал вам, что быть программистом – легко, а хорошим программистом быть еще труднее. Так что не говорите потом, что я вас не предупреждал! Шутка! Расслабтесь и разгоните свой страх перед высшей математикой прочь. По ходу описания вам встретится пара формул (ну куда же в математике без формул?), но во всех остальных случаях я буду говорить на интернациональном программистском языке – языке Си, понятным любому системщику. В общем, пристегивайте ремни и поднимайте свои головы с клавиатуры – мы поехали! Конечной целью нашего путешествия станет построение отказоустойчивого RAID-массива 5 уровня на базе… нескольких обыкновенных IDE/SCSI-контроллеров жестких дисков. 4/5 объема такого массива будут отданы непосредственно под полезные данные, а 1/5 – под избыточную информацию, позволяющую восстановить содержимое любого жесткого диска из пяти данных, даже если он будет полностью уничтожен!

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

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

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

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

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

0 –> 0000; 4 –> 0100;   8 –> 1000;   12 –> 1100;