Помехоустойчивое кодирование

[Paul Kellerman]

Хотелось прояснить кое-какие вопросы по помехоустойчивому кодиро-
ванию со специалистом в этой области. Требуется "просветление" по
части алгоритмов кодирования / декодирования и их математической
основы конкретно для систематического кодирования Рида-Соломона.

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

P.P.S. Хотелось бы подискутировать здесь, не отсылаясь к литературе.

[Paul Kellerman]

Одна из наиболее острых проблем в информационных технологиях –
это защита данных от разрушения. Как говорил один мудрый человек:
«энтропия слепа, но терпелива»... «Энтропия» не имеет собственной
воли и не разрушает целенаправленно конкретный порядок в конкре-
тной структуре, но у нее есть единственная цель – глобальный хаос, и
она случайным образом, вслепую, наносит свои удары по любым упоря-
доченным структурам, делая из них бесформенную бессмыслицу. «Энт-
ропия» вечна, фундаментальна и непобедима. Сколько не восстанавли-
вай порядок, она снова терпеливо стремится везде достичь беспорядка.
Чтобы противостоять «энтропии» необходимо непрерывно затрачивать
энергию, проявлять изобретательность и применять спец. технологии.

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

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

К сожалению, в большинстве ВУЗ коды Рида-Соломона изучают поверх-
ностно, «галопом по Европе», в рамках курса «Передачи информации»,
и из-за сложности понимания используемой в технологии нестандартной
алгебры конечных полей, которая редко где изучается в рамках обще-
образовательной программы, технология остается неосвоенной. Здесь
нужно сказать, что сами преподаватели зачастую недостаточно глубо-
ко разбираются в технологии, поскольку для них – это лишь небольшая
часть их курса, или же излишне углубляются в теорию в ущерб аспектов
практической реализации, и делая тем самым, технологию для студента
«скучной и непонятной». Я уж не говорю о том, что далеко не все спе-
циалисты по системным и сетевым технологиям имеют профильное IT-
образование, и им вообще это незнакомо.

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

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

http://icc.mpei.ru/lang/rus/docs/articles/rscmath.pdf

(Для просмотра требуется программа Adobe Acrobat Reader)

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

- Обнаружение и коррекция неумышленных ошибок (помех)
*при пере-даче данных по каналам связи, ошибок в данных
*на носителях информации при их сбое или отказе.

- Обнаружение и коррекция (при поддержке системы открытых и *
*закрытых ключей) умышленной модификации информационных *
*сообщений с целью дезинформации.

- Обнаружение и коррекция умышленной модификации информации
*об авторе или исполняемого кода с целью «взлома» программного *
*обеспечения.

- Защита программного обеспечения или данных от копирования с *
*лицензионного диска, при использовании специальных «настоящих»
*и «ложных» ошибок в секторах.

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

- Обнаружение и коррекция ошибок в цепях ДНК в генной инженерии.

P.S. Как известно, специфика российского рынка IT такова, что бытует
мнение, что в IT «нечего считать» и математика вообще не при делах.
Программисты что-то разрабатывают, сетевые специалисты что-то ад-
министрируют, дилеры чем-то торгуют, ну а фундаментальные теорети-
ческие основы – это что-то вроде балласта, "лежит в мозгу" и занимает
только место. Что касается хакеров, то они в большинстве своем увере-
ны, что официальная техническая документация и добытые бессонными
ночами неофициальные детали, а также исходные либо дизассемблиро-
ванные листинги программ – панацея на все случае жизни.

Однако, даже такие титаны хакерской мысли, как Крис Касперски, при-
знают, что когда дело касается защиты информации от умышленного
или неумышленного искажения – без математики никуда. Без нее непо-
нятные манипуляции с битыми и байтами в исходных кодах программы
вам будут казаться «чистым шаманством», и никогда не поймете истин-
ного смысла всех этих манипуляций. А, как известно, «шаманский взг-
ляд» на вещи – это всегда следствие невежества.

[YuliaP]

Уважаемый PavelAR! У меня не загрузился сам pdf-ник (видимо, проблемы с сервером). Скромно так прошу - не вышлете ли на почту (в профиле должна быть указана). Материал, тем более в доступном изложении, нам сейчас до зарезу нужен для дисциплины "Защита информации" (учебников явно маловато). Если Вы, конечно, разрешите его использовать в преподавании...

[Chief CLMiS]

PavelAR
http://icc.mpei.ru/lang/rus/docs/articles/article11.pdf Ссылочка почему-то не работает. Нашел работающую :)
http://icc.mpei.ru/lang/rus/docs/articles/rscmath.pd

[Paul Kellerman]

Chief CLMiS

Спасибо что выложили верную ссылку :) Я вчера сам попросил ответ-
ственных за сайт переименовать файл, но не успел здесь выложить
обновленную ссылку... И вы меня чуточку опередили :) Respect

YuliaP

нужен для дисциплины "Защита информации"

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

разрешите его использовать в преподавании

Именно для преподавания, в первую очередь, оно и разрабатывалось :)

[YuliaP]

Большое спасибо!!! Справку о внедрении надо будет? ;)

[Paul Kellerman]

YuliaP

Большое спасибо!!! Справку о внедрении надо будет?

Всегда пожалуйста

То, что оно реально кем-то используется - это и есть настоящее внед-
рение, и в официальных "бумажных" подтверждениях не нуждается :)

Мне гораздо важнее и интереснее научные дискуссии в этом и в других
взаимоинтересных направлениях и обмен опытом, публикациями и т.п.

[Nazym]

http://icc.mpei.ru/lang/rus/docs/articles/article11.pdf

Может я зашла по этой ссылке очень поздно, но я тоже хочу почитать
Если можно... :confused:

[Paul Kellerman]

Новая ссылка:
http://icc.mpei.ru/documents/00000885.pdf

К сожалению разработчики сайта регулярно меняют что-то и в том числе
и структуру документов, поэтому в будущем просто заходите на сам сайт
http://icc.mpei.ru и там дальше в раздел "Библиотека документов", ну там
покопавшись в подразделах (структура может меняться) найдете статью.

[Paul Kellerman]

Уважаемые коллеги, на сайт (где статья) также наконец-то выложили
демонстрационную программу (кодер и декодер кодов Рида-Соломона
и генератор ошибок) и описание к ней (в виде RAR-архива). Скачать ее
можно по ссылке: http://icc.mpei.ru/documents/00000898.rar

Буду очень признателен, если вы ее посмотрите и на досуге погоняете.
Она не требует установки и настройки и очень проста в использовании.

Суть ее предельно проста: забиваете любую текстовую строку в поле
Source Information (длина ограничивается 126 символами), выбираете
число контрольных байтов (от 2 до 128) и нажимаете кнопку Encode и
программа сформирует кадр с информационными и контрольными бай-
тами и отобразит их в 16-ричном виде. После этого можете либо сразу
декодировать его, либо же смоделировать "помеху" ("ошибку"), для это-
го выбираете количество искажаемых байтов (от 1 до 128, и оно разу-
меется должно быть меньше, чем полный размер кадра = сумма коли-
чества информационных и контрольных байтов), и нажимаете кнопку
Corrupt и программа случайным образом в кадре выберет заданное ко-
личество байтов и также случайным образом исказит каждый из них.
После этого нажимаете кнопку Decode и если удвоенное количество
искажаемых байт было меньше либо равно количества контрольных,
программа гарантированно исправит все ошибки, в противном случае
выведет одно из сообщений о невозможности исправить ошибки. Все
сообщения выводится внизу в строке состояния программы. В общем,
если не лень - погоняйте, если что-то непонятно смотрите описание.

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

P.S. Буду не только не против, но даже очень рад, если профильные IT-
преподаватели захотят ее использовать в учебном процессе. Только не
пытайтесь ее выдавать, как свою собственную разработку. В программе,
как минимум, один основной и один запасной механизм отображения ин-
формации об авторе (как запустить запасной - знает только PavelAR) :)