Что читать

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

1. Blahut Richard. Theory and Practice of Error Control Codes. Mass.: Addison-Wesley, 1983. – Очень хорошая книжка из категории «must have»; по слухам, есть в электронном виде в сети, однако, к сожалению, самой книжки я так и не нашел, но тучи ссылок на нее убедительно свидетельствуют о высоком качестве последней. Также имеется ее русскоязычный перевод, выпущенный издательством «Мир» (см. ниже).

2. Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986. – 576с. – Технически грамотный и добротный перевод уже упомянутой выше книги Блейхута (ах, какие в издательстве Мир были переводчики!), электронной копии в сети, к сожалению, нет.

3. 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.

4. Joel Sylvester. Reed Solomon Codes. – Предельно кратное описание принципов работы кодов Рида-Соломона с блок-схемами вместо исходных текстов. На практическое руководство не тянет, но общую картину все-таки дает, почитайте: http://www.elektrobit.co.uk/pdf/reedsolomon.pdf.

5. Tom Moore. REED-SOLOMON PACKAGE. (old tutorial). – Роскошный сборник разнообразных руководств по кодам Рида-Соломона, наверное, лучший из всех, что я видел. Включает в себя кратное описание основ теории полей Галуа, базовые принципы построения кодеров/декодеров Рида-Соломона и законченные примеры реализации самих кодеров/декодеров на языке Си (правда, недостаточно добросовестно прокомментированные). Сей stuff неоднократно промелькивал в ФИДО и последний раз постился 28 декабря 1994 года в конференции comp.compression. Его легко найти в «Google» по ключевым словам «Reed-Solomon+main+ECC». Настоятельно рекомендую.

6. Ross N.Williams. A painless guide to CRC error detection algorithms. – Подробное руководство по CRC, полезное достаточно внятным и доступным описанием полиномиальной арифметики, без которой работа с кодами Рида-Соломона просто немыслима. Доступно в электронной форме по следующему адресу: ftp://www.internode.net.au/clients/rocksoft/papers/crc_v3.txt. Также имеется его неплохой перевод на русский язык, легко отыскивающийся в сети по запросу «Элементарное руководство по CRC-алгоритмам обнаружения ошибок». Настоятельно рекомендую.

7. ftape (драйвер ленточного накопителя из дистрибутива Linux). – Ну какая же запись на магнитную ленту обходится без корректирующих кодов? Представить себе такое, довольно затруднительно. Поэтому анализ исходных текстов драйверов ленточных накопителей дает довольно-таки богатую пищу для размышлений (при условии, конечно, что исследуемый драйвер действительно использует коды Рида-Соломона, а не что-нибудь другое). Драйвер ftape как раз и является тем драйвером, что вам нужен, а непосредственно сам код, ответственный за кодирование/декодирование кодов Рида-Соломона вынесен в файл ftape-ECC.c/ftape-ECC.h. Это достаточно аккуратный, хорошо структурированный и даже местами слегка комментируемый код, также рекомендую.