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

Paul Kellerman · 12.02.2007, 13:53

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

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

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

Paul Kellerman · 12.03.2007, 18:17

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

YuliaP · 15.03.2007, 09:48

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

Chief CLMiS · 15.03.2007, 10:10

PavelAR

Цитата:

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

Ссылочка почему-то не работает. Нашел работающую

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

Paul Kellerman · 15.03.2007, 11:53

Chief CLMiS

Спасибо что выложили верную ссылку

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

Respect

YuliaP

Цитата:

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

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

Цитата:

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

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

YuliaP · 16.03.2007, 10:03

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

Paul Kellerman · 16.03.2007, 11:47

YuliaP

Цитата:

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

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

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

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

Nazym · 14.01.2009, 09:50

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

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

Paul Kellerman · 14.01.2009, 15:09

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

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

Paul Kellerman · 15.01.2009, 18:03

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

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

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

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

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

12.02.2007, 13:53	#1
Paul Kellerman Gold Member Регистрация: 25.06.2005 Адрес: F000:FFF0 Сообщений: 1,827	Помехоустойчивое кодирование Хотелось прояснить кое-какие вопросы по помехоустойчивому кодиро- ванию со специалистом в этой области. Требуется "просветление" по части алгоритмов кодирования / декодирования и их математической основы конкретно для систематического кодирования Рида-Соломона. P.S. К сожалению, у нас нет специального раздела, предназначенного для обсуждения конкретных научно-технических задач и проблем по областям (направлениям). Вопрос с одной стороны явно не флеймовый, а с другой стороны к диссертации тоже не имеет никакого отношения, поэтому счел вполне подходящим задать вопрос в преподавательской. P.P.S. Хотелось бы подискутировать здесь, не отсылаясь к литературе.

12.03.2007, 18:17	#2
Paul Kellerman Gold Member Регистрация: 25.06.2005 Адрес: F000:FFF0 Сообщений: 1,827	Помехоустойчивое кодирование Одна из наиболее острых проблем в информационных технологиях – это защита данных от разрушения. Как говорил один мудрый человек: «энтропия слепа, но терпелива»... «Энтропия» не имеет собственной воли и не разрушает целенаправленно конкретный порядок в конкре- тной структуре, но у нее есть единственная цель – глобальный хаос, и она случайным образом, вслепую, наносит свои удары по любым упоря- доченным структурам, делая из них бесформенную бессмыслицу. «Энт- ропия» вечна, фундаментальна и непобедима. Сколько не восстанавли- вай порядок, она снова терпеливо стремится везде достичь беспорядка. Чтобы противостоять «энтропии» необходимо непрерывно затрачивать энергию, проявлять изобретательность и применять спец. технологии. В течение большей части второй половины прошлого века математики и специалисты по аппаратным и программным средствам ЭВМ и пробле- мам передачи данных упорно бились над тем, чтобы выработать техно- логию, позволяющую кодировать информацию таким образом, чтобы при разрушении случайно выбранных ее блоков, эти блоки можно было восстановить. После того, как была заложена математическая основа для кодирования, разработаны эффективные алгоритмы кодирования и декодирования, технология ближе к концу прошлого века стала более или менее устоявшейся, и, честно говоря, вообще превратилась в шир- потреб, которым пользуются все повседневно и даже не подозревают о ее существовании. Технология применяется при приеме / передаче данных в сетях и при чтении / записи данных на большинстве носите- лей информации, «на лету» обнаруживая и по возможности исправляя искаженные блоки данных. И здесь, если пользователям и домохозяйкам можно простить их невеже- ственно-потребительское отношение к высоким технологиям, то уж ува- жающие себя специалисты по системным и сетевым технологиям обяза- ны быть знакомы с тонкостями и деталями технологии. Ну, а уж уважа- ющие себя программисты, как в "подтверждение" своей высокой квали- фикации, должны иметь свои собственные корректно работающие про- граммные реализации тех непростых алгоритмов, которые используются в этой технологии. К сожалению, в большинстве ВУЗ коды Рида-Соломона изучают поверх- ностно, «галопом по Европе», в рамках курса «Передачи информации», и из-за сложности понимания используемой в технологии нестандартной алгебры конечных полей, которая редко где изучается в рамках обще- образовательной программы, технология остается неосвоенной. Здесь нужно сказать, что сами преподаватели зачастую недостаточно глубо- ко разбираются в технологии, поскольку для них – это лишь небольшая часть их курса, или же излишне углубляются в теорию в ущерб аспектов практической реализации, и делая тем самым, технологию для студента «скучной и непонятной». Я уж не говорю о том, что далеко не все спе- циалисты по системным и сетевым технологиям имеют профильное IT- образование, и им вообще это незнакомо. Также, к сожалению, большинство литературы и статей по кодам Рида- Соломона либо слишком перегружены теоремами и доказательствами и требуют высокой математической подготовки для понимания материала либо же наоборот упрощены до абсурда так, что ключевые алгоритмы объясняются не на схемах алгоритмов, а прямо примере листингов кодов Си или Паскаля, что никуда не годится с академической точки зрения... Поэтому, я попытался разработать доступный для понимания материал (вполне достаточно знаний алгебры на уровне средней школы) с особым акцентом на саму суть технологии и на детальное описание алгоритмов кодирования и декодирования, чтобы любой мог "с ходу" разобраться и запрограммировать их. Кроме того, в материале в каждом подразделе имеется достаточно количество наглядных примеров. http://icc.mpei.ru/lang/rus/docs/articles/rscmath.pdf (Для просмотра требуется программа Adobe Acrobat Reader) Практическую ценность кодов Рида-Соломона трудно переоценить. С помощью них можно не только обнаруживать, но и частично восстана- вливать информацию практически «из пепла». К сожалению коды Рида- Соломона у большинства специалистов ассоциируются только с помехо- устойчивым кодированием в каналах передачи данных. В действитель- ности, их можно применять везде, где необходимо предотвратить, как неумышленную, так и неумышленную модификацию данных: - Обнаружение и коррекция неумышленных ошибок (помех) при пере-даче данных по каналам связи, ошибок в данных на носителях информации при их сбое или отказе. - Обнаружение и коррекция (при поддержке системы открытых и * закрытых ключей) умышленной модификации информационных сообщений с целью дезинформации. - Обнаружение и коррекция умышленной модификации информации об авторе или исполняемого кода с целью «взлома» программного * обеспечения. - Защита программного обеспечения или данных от копирования с лицензионного диска, при использовании специальных «настоящих» и «ложных» ошибок в секторах. - Восстановление одного или нескольких томов многотомного архива, искаженных или вообще потерянных при загрузке из сети. Аналогич- но, восстановление данных одного или нескольких дисков в многодис- *ковых системах RAID. - Обнаружение и коррекция ошибок в цепях ДНК в генной инженерии. P.S. Как известно, специфика российского рынка IT такова, что бытует мнение, что в IT «нечего считать» и математика вообще не при делах. Программисты что-то разрабатывают, сетевые специалисты что-то ад- министрируют, дилеры чем-то торгуют, ну а фундаментальные теорети- ческие основы – это что-то вроде балласта, "лежит в мозгу" и занимает только место. Что касается хакеров, то они в большинстве своем увере- ны, что официальная техническая документация и добытые бессонными ночами неофициальные детали, а также исходные либо дизассемблиро- ванные листинги программ – панацея на все случае жизни. Однако, даже такие титаны хакерской мысли, как Крис Касперски, при- знают, что когда дело касается защиты информации от умышленного или неумышленного искажения – без математики никуда. Без нее непо- нятные манипуляции с битыми и байтами в исходных кодах программы вам будут казаться «чистым шаманством», и никогда не поймете истин- ного смысла всех этих манипуляций. А, как известно, «шаманский взг- ляд» на вещи – это всегда следствие невежества.

15.03.2007, 09:48	#3
YuliaP Junior Member Регистрация: 31.01.2007 Сообщений: 30	Помехоустойчивое кодирование Уважаемый PavelAR! У меня не загрузился сам pdf-ник (видимо, проблемы с сервером). Скромно так прошу - не вышлете ли на почту (в профиле должна быть указана). Материал, тем более в доступном изложении, нам сейчас до зарезу нужен для дисциплины "Защита информации" (учебников явно маловато). Если Вы, конечно, разрешите его использовать в преподавании...

16.03.2007, 10:03	#6
YuliaP Junior Member Регистрация: 31.01.2007 Сообщений: 30	Помехоустойчивое кодирование Большое спасибо!!! Справку о внедрении надо будет?

14.01.2009, 09:50	#8
Nazym Newbie Регистрация: 14.01.2009 Сообщений: 1	http://icc.mpei.ru/lang/rus/docs/articles/article11.pdf Может я зашла по этой ссылке очень поздно, но я тоже хочу почитать Если можно...
Nazym Newbie Регистрация: 14.01.2009 Сообщений: 1

14.01.2009, 15:09	#9
Paul Kellerman Gold Member Регистрация: 25.06.2005 Адрес: F000:FFF0 Сообщений: 1,827	Новая ссылка: http://icc.mpei.ru/documents/00000885.pdf К сожалению разработчики сайта регулярно меняют что-то и в том числе и структуру документов, поэтому в будущем просто заходите на сам сайт http://icc.mpei.ru и там дальше в раздел "Библиотека документов", ну там покопавшись в подразделах (структура может меняться) найдете статью.

15.01.2009, 18:03	#10
Paul Kellerman Gold Member Регистрация: 25.06.2005 Адрес: F000:FFF0 Сообщений: 1,827	Уважаемые коллеги, на сайт (где статья) также наконец-то выложили демонстрационную программу (кодер и декодер кодов Рида-Соломона и генератор ошибок) и описание к ней (в виде RAR-архива). Скачать ее можно по ссылке: http://icc.mpei.ru/documents/00000898.rar Буду очень признателен, если вы ее посмотрите и на досуге погоняете. Она не требует установки и настройки и очень проста в использовании. Суть ее предельно проста: забиваете любую текстовую строку в поле Source Information (длина ограничивается 126 символами), выбираете число контрольных байтов (от 2 до 128) и нажимаете кнопку Encode и программа сформирует кадр с информационными и контрольными бай- тами и отобразит их в 16-ричном виде. После этого можете либо сразу декодировать его, либо же смоделировать "помеху" ("ошибку"), для это- го выбираете количество искажаемых байтов (от 1 до 128, и оно разу- меется должно быть меньше, чем полный размер кадра = сумма коли- чества информационных и контрольных байтов), и нажимаете кнопку Corrupt и программа случайным образом в кадре выберет заданное ко- личество байтов и также случайным образом исказит каждый из них. После этого нажимаете кнопку Decode и если удвоенное количество искажаемых байт было меньше либо равно количества контрольных, программа гарантированно исправит все ошибки, в противном случае выведет одно из сообщений о невозможности исправить ошибки. Все сообщения выводится внизу в строке состояния программы. В общем, если не лень - погоняйте, если что-то непонятно смотрите описание. Для продвинутых спецов: помимо возможности искажения заданного количества байт в кадре, в программе также можно напрямую лезть в поле кадра и редактировать байтики в 16-ричном виде. Так вы смо- жете ввести конкретные "ошибки" в конкретных байтах кадры, и вооб- ще поэкспериментировать с кодами Рида-Соломона вдоль и поперек. P.S. Буду не только не против, но даже очень рад, если профильные IT- преподаватели захотят ее использовать в учебном процессе. Только не пытайтесь ее выдавать, как свою собственную разработку. В программе, как минимум, один основной и один запасной механизм отображения ин- формации об авторе (как запустить запасной - знает только PavelAR)

Реклама