Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Коды и математика (рассказы о кодировании)
Автор: Аршинов М.Н.Другие авторы: Садовский Л.Е.
Издательство: М.: Наука
Год издания: 1983
Страницы: 144
Читать: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
Скачать:
М.Н.Аршинов, Л.Е.Садовский КОДЫ И МАТЕМАТИКА (РАССКАЗЫ О КОДИРОВАНИИ)
М.: Наука, 1983. —144 с. (Библиотечка «Квант». Вып. 30).
Б популярной форме книга знакомит читателя с основными понятиями и идеями теории эффективного и помехоустойчивого кодирования - важного направления математики.
Имея своими первоисточниками криптографию (искусство засекречивания истинного содержания сообщения), но главным образом решая различные проблемы, возникающие при передаче информации по линиям связи, теория кодирования в настоящее время выросла в обширную и разветвленную область знания со своим кругом объектов и задач.
Не ставя перед собой цели систематического изложения теории, авторы
стремятся отразить главные ее черты.
СОДЕРЖАНИЕ
Предисловие 3
1. Кодирование - история и первые шаги 5
2. Шифры, шифры, шифры 10
3. Код Фано — экономный код 18
4. Свойство префикса, или куда идти роботу 24
5. Еще о свойстве префикса и однозначной декодируемости 27
6. Оптимальный код 32
7. Об избыточности, шумах и криптограмме, которую нельзя расшифровать 37
8. Коды - антиподы 40
9. Код Хемминга 45
10. Необычное обычное расстояние 48
11. Линейные или групповые коды 50
12. Декодирование по синдрому и еще раз о коде Хемминга 61
13. О кодах, исправляющих несимметричные ошибки 65
14. Циклические коды 68
15. О границах возможного в кодировании и совершенных кодах 77
16. Кодирует и декодирует ЭВМ 82
17. Голосование 93
18. Многоступенчатое голосование и коды Рида-Маллера 97
19. Латинские квадраты и коды 102
20. Матрицы Адамара и кодирование 107
21. Задача об ожерельях, функция Мёбиуса и синхронизируемые коды 112 Заключение 116 Приложение 117
1. Сравнения и классы вычетов 117
2. Группы 120
3. Кольца и поля 125
4. Арифметическое и-мерное векторное пространство 129
5. Алгебра матриц 132
6. Задачи и дополнения 136 Литература 142 ПРЕДИСЛОВИЕ
Право же, не будет ошибкой предположить, ^to у большинства читателей слова «код», «кодирование» вызывают примерно одинаковые представления. Ведь все хорошо знают, что коды или шифры используются для передачи секретной информации. Менее известно, однако, что в наше время коды приобрели и иное значение, быть может, более обыденное, но зато куда более важное л широкое. В этой их новой роли коды и кодирование — прежде всего средство для экономной, удобной и практически безошибочной передачи сообщений. Новые применения кодов сложились в результате бурного развития различных средств связи, неизмеримо возросшего объема передаваемой информации.
Решать возникшие в связи с этим задачи было бы невозможно без привлечения самых разнообразных математических методов. Неслучайно поэтому теория кодирования считается сейчас одним из наиболее важных разделов прикладкой математики. Желание познакомить широкий круг читателей с задачами и методами этой теории и является основной нашей целью. Все же немного места уделили мы также кодам в их изначальном смысле — как средству обеспечения секретности.
Первая часть книги (§§ 1—10) написана вполне элементарно, и для ее понимания читателю достаточно ознакомиться с приложением 1, содержащим простейшие сведения о сравнениях.
В дальнейшем изложении, однако, существенно используются основные факты линейной алгебры, а также факты, связанные с понятиями поля и группы. Все необходимые определения и теоремы содержатся в приложениях 2—5.
1* з Не освоившись с материалом этих приложений, читатель не смог бы свободно ориентироваться во второй части книги.
В заключение отметим, что в конце большинства параграфов имеется раздел «Задачи и дополнения», где рассматриваются некоторые более специальные и, как правило, более трудные вопросы, а также приводятся задачи для самостоятельного решения. Читателю, желающему основательно разобраться в содержании книги, мы рекомендуем не пренебрегать этими задачами.
М. Н. Аришнов, Л. Е. Садовский 1. КОДИРОВАНИЕ - ИСТОРИЯ
И ПЕРВЫЕ ШАГИ
Коды появились в глубокой древности в виде криптограмм (по-гречески — тайнописи), когда ими пользовались для засекречивания важного сообщения от тех, кому оно не было предназначено. Уже знаменитый греческий историк Геродот (V век до н. э.) приводил примеры писем, понятных лишь для одного адресата. Спартанцы имели специальный механический прибор, при помощи которого важные сообщения можно было писать особым способом, обеспечивающим сохранение тайны. Собственная секретная азбука была у Юлия Цезаря. В средние века и эпоху Возрождения над изобретением тайных шифров трудились многие выдающиеся люди, в их числе философ Фрэнсис Бэкон, крупные математики Франсуа Виег, Джероламо Кардано, Джон Валлис.
С течением времени начали появляться по-настоящему сложные шифры. Один из них, употребляемый и поныне, связан с именем ученого аббата из Вюрцбурга Трнтемиуса, которого к занятиям криптографией побуждало, быть может, не только монастырское уединение, IIO и потребность сохранять от огласки некоторые духовные тайны. Различные хитроумные приемы кодирования применяли шифровальщики при папском дворе и дворах европейских королей. Вместе с искусством шифрования развивалось и искусство дешифровки, или, как говорят, криптоанализа.
