Электронная библиотека
Программисту веб-дизайнеру
Другие материалы
Бесплатная электронная библиотека. Скачать книги DJVU, PDF бесплатно
М.Н. Аршинов, Л.Е. Садовский, Коды и математика
• Бесплатно скачать книгу, объем 1.90 Мб, формат .djvu (Рассказы о кодировании, 1983)
1. Кодирование - история и первые шаги
2. Шифры, шифры, шифры
3. Код Фано - экономный код
4. Свойство префикса, или куда идти роботу
5. Еще о свойстве префикса и однозначной декодируемое
6. Оптимальный код
7. Об избыточности, шумах и криптограмме, которую нельзя расшифровать
8. Коды - антиподы
9. Код Хемминга
10. Необычное обычное расстояние
11. Линейные или групповые коды
12. Декодирование по синдрому и еще раз о коде Хемминга
13. О кодах, исправляющих несимметричные ошибки
14. Циклические коды
15. О границах возможного в кодировании и совершенных кодах
16. Кодирует и декодирует ЭВМ
17. Голосование
18. Многоступенчатое голосование и коды Рида-Маллера
19. Латинские квадраты и коды
20. Матрицы Адамара и кодирование
21. Задача об ожерельях, функция Мёбиуса и синхронизируемые коды
Приложение
1. Сравнения и классы вычетов
2. Группы
3. Кольца и поля
4. Арифметическое n-мерное векторное пространство
5. Алгебра матриц
6. Задачи и дополнения
Краткая аннотация книги
В популярной форме книга знакомит читателя с основными понятиями и идеями теории эффективного и помехоустойчивого кодирования - важного направления математики. Имея своими первоисточниками криптографию (искусство засекречивания истинного содержания сообщения), но главным образом решая различные проблемы, возникающие при передаче информации по линиям связи, теория кодирования в настоящее время выросла в обширную и разветвленную область знания со своим кругом объектов и задач. Не ставя перед собой цели систематического изложения теории, авторы стремятся отразить главные ее черты.
Право же, не будет ошибкой предположить, ¦что у большинства читателей слова "код", "кодирование" вызывают примерно одинаковые представления. Ведь все хорошо знают, что коды или шифры используются для передачи секретной информации. Менее известно, однако, что в наше время коды приобрели и иное значение, быть может, более обыденное, но зато куда более важное л широкое. В этой их новой роли коды и кодирование - прежде всего средство для экономной, удобной и практически безошибочной передачи сообщений. Новые применения кодов сложились в результате бурного развития различных средств связи, неизмеримо возросшего объема передаваемой информации.
Решать возникшие в связи с этим задачи было бы невозможно без привлечения самых разнообразных математических методов. Неслучайно поэтому теория кодирования считается сейчас одним из наиболее важных разделов прикладкой математики. Желание познакомить широкий круг читателей с задачами и методами этой теории и является основной нашей целью. Все же немного места уделили мы также кодам в их изначальном смысле - как средству обеспечения секретности. Первая часть книги (§§ 1-10) написана вполне элементарно, и для ее понимания читателю достаточно ознакомиться с приложением 1, содержащим простейшие сведения о сравнениях.
В дальнейшем изложении, однако, существенно используются основные факты линейной алгебры, а также факты, связанные с понятиями поля и группы. Все необходимые определения и теоремы содержатся в приложениях 2-5.
Не освоившись с материалом этих приложений, читатель не смог бы свободно ориентироваться во второй части книги. В заключение отметим, что в конце большинства параграфов имеется раздел "Задачи и дополнения", где рассматриваются некоторые более специальные и, как правило, более трудные вопросы, а также приводятся задачи для самостоятельного решения. Читателю, желающему основательно разобраться в содержании книги, мы рекомендуем не пренебрегать этими задачами. М. Н. Аришнов, Л. Е, Садовский
Коды появились в глубокой древности в виде криптограмм (по-гречески - тайнописи), когда ими пользовались для засекречивания важного сообщения от тех, кому оно не было предназначено. Уже знаменитый греческий историк Геродот (V век до н. э.) приводил примеры писем, понятных лишь для одного адресата. Спартанцы имели специальный механический прибор, при помощи которого важные сообщения можно было писать особым способом, обеспечивающим сохранение тайны. Собственная секретная азбука была у Юлия Цезаря. В средние века и эпоху Возрождения над изобретением тайных шифров трудились многие выдающиеся люди, в их числе философ Фрэнсис Бэкон, крупные математики Франсуа Виет, Джероламо Кардано, Джон Валлис.
С течением времени начали появляться по-настоящему сложные шифры. Один из них, употребляемый и поныне, связан с именем ученого аббата из Вюрцбурга Трнтемнуса, которого к занятиям криптографией побуждало, быть может, не только монастырское уединение, но и потребность сохранять от огласки некоторые духовные тайны. Различные хитроумные приемы кодирования применяли шифровальщики при папском дворе и дворах европейских королей. Вместе с искусством шифрования развивалось и искусство дешифровки, или, как говорят, криптоанализа.
Секретные шифры являются неотъемлемой принадлежностью многих детективных романов, в которых действуют изощренные в хитрости шпионы. Писатель-романтик Эдгар По, которого иногда причисляют к создателям детективного жанра, в своем рассказе "Золотой жук" в художественной форме изложил простейшие приемы шифрования и расшифровки сообщений. Эдгар По относился к проблеме расшифровки оптимистически, вложив в уста своего героя следующую фразу: "...едва ли разуму человека дано загадать такую загадку, которую разум другого его собрата, направленный должным образом, не смог бы раскрыть. Прямо скажу, если текст зашифрован без грубых ошибок и документ в приличной сохранности, я больше ни в чем не нуждаюсь; последующие трудности для меня просто не существуют". Столетие спустя это высказывание было опровергнуто ученым, заложившим основы теории информации, Клодом Шенноном. Шеннон показал, как можно построить криптограмму, которая не поддается никакой расшифровке, если, конечно, не известен способ ее составления.
О некоторых приемах криптографии и криптоанализа мы расскажем в следующем параграфе, в остальных частях книги речь будет идти в основном об ином направлении в кодировании, которое возникло уже в близкую нам эпоху. Связано оно с проблемой передачи сообщений по линиям связи, без которых (т. е. без телеграфа, телефона, радио, телевидения и т. д.) немыслимо наше нынешнее существование. В задачу такого кодирования, как уже говорилось, входит отнюдь не засекречивание сообщений, а иная цель: сделать передачу сообщений быстрой, удобной и надежной. Предназначенное для этой цели кодирующее устройство сопоставляет каждому символу передаваемого текста, а иногда и целым словам или фразам (сообщениям) определенную комбинацию сигналов (приемлемую для передачи по данному каналу связи), называемую кодом или кодовым словом. При этом операцию перевода сообщений в определенные последовательности сигналов называют кодированием, а обратную операцию, восстанавливающую по принятым сигналам (кодовым словам) передаваемые сообщения,- декодированием. Заметим сразу же, что различные символы или сообщения должны кодироваться различными кодовыми словами, в противном случае по кодовым словам нельзя было бы восстановить передаваемые сообщения.
Исторически первый код, предназначенный для передачи сообщений, связан с именем изобретателя телеграфного аппарата Сэмюэля Морзе и известен всем как азбука Морзе. В этом коде каждой букве или цифре сопоставляется своя последовательность из кратковременных (называемых точками) и длительных (тире) импульсов тока, разделяемых паузами. Другой код, столь же широко распространенный в телеграфии (код Бодо), использует для кодирования два элементарных сигнала - импульс и паузу, при этом сопоставляемые-буквам кодовые слова состоят из пяти таких сигналов.
Коды, использующие два различных элементарных сигнала, называются двоичными. Удобно бывает, отвлекаясь от их физической природы, обозначать эти два сигнала символами 0 и 1. Тогда кодовые слова можно представлять как последовательности из нулей и единиц. Двоичное кодирование тесно связано с принципом дихотомии (деления пополам).
Примечание. Сохраняйте книги на мобильный телефон и скачивайте их с Вашего телефона на компьютер. Удобное скачивание книг через мобильный телефон (в память телефона) и на Ваш компьютер через мобильный интерфейс. Быстрый Интернет без излишних тэгов. Материал носит неофициальный характер и приведен для ознакомления. Прямые ссылки на файлы книг запрещены.