Читать онлайн «Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение»

И Р язи Р. МОРЕЛОС-САРАГОСА Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение Перевод с английского В. Б. Афанасьева Рекомендовано ИППИ РАН а качестве учебного пособия для студентов, обучающихся по нвпрввлениям подготовки "Приклвдные мвтемвтикв и физике" и "Телекоммуниквции" ТЕХНОСФЕРА Москва 2005 Р. Морелос- Сарагоса Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. Москва: Техносфера, 2005. - 320с. ISBN 5-94836-035-0 Новейшее пособие по теории и практике цифровой связи, не имеющее аналогов в литературе на русском языке. Наиболее активно идеи помехоустойчивого кодирования внедряются в системах мобильной связи и в магистральных высокоскоростных линиях. Быстрое распространение Интернета и средств Мультимедиа стимулирует применение кодов, исправляющих ошибки, для защиты банков данных огромной емкости от случайных или преднамеренных искажений. Помимо классических алгоритмов декодирования блоковых и сверточ- ных кодов детально рассмотрены современные идеи декодирования с «мягким решением» и итеративного декодирования. Идеальное учебное пособие для студентов программистских и связных специальностей, инженеров-разработчиков и практиков. The Art of Error Correcting Coding in wilbv a sons, n © 2002 by Jon Wiley & Sons, Ltd Baffins Lane, Chichester, West Sussex, P019 1UD, England © 2005, ЗАО «РИЦ «Техносфера» перевод на русский язык, оригинал-макет, оформление. ISBN 5-94836-035-0 ISBN 0471 49581 6 (англ. ) Содержание Предисловие автора 12 Предисловие 14 Глава 1. Введение 17 1. 1. Кодирование для исправления ошибок: Основные положения 18 1. 1. 1. Блоковые и сверточные коды 19 1. 1. 2. Хеммингово расстояние, Хемминговы сферы и корректирующая способность 20 1. 2. Линейные блоковые коды 23 1. 2. 1. Порождающая и проверочная матрицы ... . 24 1. 2. 2. Вес как расстояние 25 1. 3. Кодирование и декодирование линейных блоковых кодов 26 1. 3. 1. Кодирование с помощью матриц G и Н ... . 26 1. 3. 2. Декодирование по стандартной таблице ... . 26 1. 3. 3. Хемминговы сферы, области декодирования и стандартная таблица 32 1. 4. Распределение весов и вероятность ошибки 34 1. 4. 1. Распределение весов и вероятность необнаруженной ошибки в ДСК 34 1. 4. 2. Границы вероятности ошибки в ДСК, каналах с АБГШ и с замираниями 36 1. 5 Общая структура жесткого декодера для линейных кодов 47 Глава 2. Коды Хемминга, Голея и Рида-Маллера 49 2. 1. Коды Хемминга 49 4 Содержание 2. 1. 1. Процедуры кодирования и декодирования . 50 2. 2. Двоичный код Голея 53 2. 2. 1 Кодирование 54 2. 2. 2. Декодирование 55 2. 2. 3. Арифметическое декодирование расширенного (24,12,8) кода Голея 55 2. 3. Двоичные коды Рида-Маллера 57 2. 3. 1. Булевы полиномы и РМ коды 58 2. 3. 2. Конечные геометрии и мажоритарное декодирование 60 Глава 3 Двоичные циклические коды и коды БЧХ 67 3. 1. Двоичные циклические коды 67 3. 1. 1. Порождающий и проверочный полиномы . . 67 3. 1. 2. Порождающий многочлен 69 3. 1. 3. Кодирование и декодирование двоичных циклических кодов 70 3. 1. 4.