Читать онлайн «Введение в теорию кодирования»

А. А. МАРКОВ ВВЕДЕНИЕ В ТЕОРИЮ КОДИРОВАНИЯ Допущено Министерством высшего и среднего специального образования СССР в качестве учебного пособил для студентов вузов, обучающихся по специальности «Прикладная математипа» ш МОСКВА «НАУКА» ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ 1982 22. 18 M 26 УДК 519. 0 Введение в теорию кодирования. Марков А. А. — М. : Наука. Главная редакция физико-математической литературы, 1982. — 192 с. Книга является введением в основания теории кодирования — раздела дискретной математики, имеющего приложения в различных областях естествознания. Предназначена студентам, специализирующимся по прикладной математике, н научным работникам в этой области. Александр Александрович Марков ВВЕДЕНИЕ В ТЕОРИЮ КОДИРОВАНИЯ Редакторы Р. Л. Смелянский, Е. Ю. Ходан Технический редактор Е В. Морозова Коррекюры Г. В. П о д в о л ь с к а я, В. П. С о р о к и и а ИВ MS 11860 Сдано в набор 28 05. 81. Подписано к печати 11 12 81 Т-30833. Формат 84х108'/з2. Бумага тип. JM5 2. Обыкновенная гарнитура. Высокая печать. Условн. печ л. 10,08. Уч. -плд. л. 10,Л. Тираж 15 000 экз. Заказ Л1 594. Цена 35 коп. Издательство «Наука» Главная редакция физико-математической литературы 117071, Москва, В-71, Ленинский проспект, 15 4-я типография издательства «Наука» 630077, Новосибирск, 77, Станиславского, 25 (г}) Издательство «Наука»! ^-" Гл; 170°П7000() — (ЮГ) Главная редакция ]\1 — — t | Qi физико-математической Ч). Ч/1)2)-К2 литературы, 1982 ОГЛАВЛЕНИЕ Предисловие 3 Глава I. Элементы комбинаторного анализа ... 5 § 1. Комбинаторные операции и функции ... 5 § 2. Отношения порядка и нумерации . . . . 11 § 3. Отношения эквивалентности и разбиения . . 15 § 4. Независимые множества в графах ... . 28 § 5. Комбинаторная теория полугрупп ... . 42 § 6. Регулярные множества слов 61 Глава II. Комбинаторно-логические основания теории кодирования 81 § 1. Модель канала связи и проблематика теории ко- дярования 82 § 2. Условия взаимной однозначности алфавитного кодирования 93 § 3. Условия полноты кодов и построение матриц оптимального кодирования ... ... . 120 § 4. Вопросы декодирования и конструктивная взаимная однозначность алфавитного кодирования 128 § 5. Помехоустойчивое кодирование 144 Глава III. Статистические характеристики кодирования 153 § 1. Статистическая характеристика структуры языковых групп, связанных с алфавитным кодированием . 153 § 2. Алгоритм статистически оптимального кодирования 156 § 3. Статистическая характеристика эффективности автоматного кодирования 165 § 4. Статистический подход к помехоустойчивости кодирования 168 Приложение 179 Литература 189 Предметный указатель . 192 ПРЕДИСЛОВИЕ Под кодированием в широком смысле понимается переход от одного способа задания информации к другому, допускающий восстановление исходной информации. Оно является методом, распространенным в математике и ее приложениях. Теория кодирования как раздел математики, имеющий кодирование объектом исследования, возникла в 40-х годах XX века после работ К.