Сохранность книги — хорошая

ERROR-CORRECTING CODES
SECOND EDITION
W. Wesley Peterson
E. J. Weldon, Jr
THE MIT PRESS
CAMBRIDGE, MASSACHUSETTS AND LONDON, ENGLAND
1972

Пер. с англ.

Формат 60x90 1/16. Бумага типографская №1

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

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

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

Основным средством обеспечения высокой помехоустойчивости сложной системы является введение избыточности, необходимой для обнаружения и исправления ошибок, возникающих при работе системы и её элементов. Теоретической базой эффективного использования вводимой избыточности является теория помехоустойчивого кодирования.

В мировой литературе насчитывается более десятка монографий, посвящённых теории помехоустойчивого кодирования. Первой и, пожалуй, методически наиболее совершенной книгой этого направления явилась монография У. Питерсона «Коды, исправляющие ошибки», изданная в 1961 г. и переведённая на русский язык в 1964 г.

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

Монография отличалась широтой и полнотой охвата материала. Однако десятилетие, прошедшее со времени её издания, было периодом очень быстрого развития теории кодирования и поэтому естественно, что эта монография представляется теперь несколько устаревшей и не отражающей последних достижений науки.

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

Книга У. Питерсона и Э. Уэлдона сохраняет все методические достоинства первого издания. Она написана на очень высоком теоретическом уровне. Существенно расширен круг рассматриваемых вопросов за счёт включения многих новых результатов, полученных за последнее десятилетие.

Несомненно, что данная книга будет полезной и интересной не только для специалистов, работающих в области теории кодирования, но и для инженеров, занимающихся вопросами её применения. Она может быть использована как учебник для подготовки специалистов математического и инженерного профиля.
Перевод выполнен Л. Е. Филипповой (гл. 1—8 и приложения), И. М. Бояриновым (гл. 9, разд. 9.4—9.8; гл. 10) и В. Н. Дынькиным (гл. 9, разд. 9.1—9.3; гл. 11—15).

ПРЕДИСЛОВИЕ К РУССКОМУ ИЗДАНИЮ
Р. Л. Добрушин, С. И. Самойленко

Предисловие к русскому изданию	5
Предисловие авторов	7

1. Проблема кодирования	9

1.1. Канал связи	9
1.2. Несколько общих замечаний о кодах, обнаруживающих
и исправляющих ошибки	11
1.3. Типы кодов	13
1.4. Блоковые коды	15
1.5. Древовидные коды	19
1.6. Проблема кодирования	25

2. Введение в алгебру	29

2.1. Группы	29
2.2. Кольца	32
2.3. Поля	34
2.4. Подгруппы и факторгруппы	35
2.5. Векторные пространства и линейные алгебры	39
2.6. Матрицы	42

3. Линейные коды	52

3.1. Метрика Хэмминга и метрика Ли	52
3.2. Описание линейных блоковых кодов при помощи матриц	54
3.3. Описание древовидных линейных кодов при помощи матриц	59
3.4. Стандартное расположение	65
3.5. Поэтапное декодирование для блоковых кодов	70
3.6. Модулярное представление линейных блоковых кодов	73
3.7. Эквивалентность линейных блоковых кодов	76
3.8. Распределения весов и тождества Мак-Уильямс	78
3.9. Максимально разнесённые коды	84

4. Возможности исправления ошибок с помощью линейных кодов	91

4.1. Границы минимального расстояния для блоковых кодов	91
4.2. Границы вероятности ошибки для блоковых кодов, используемых
при передаче по двоичному симметричному каналу	103
4.3. Обсуждение границ для блоковых кодов	114
4.4. Границы минимального расстояния для свёрточных кодов	116
4 5. Границы вероятности ошибки для свёрточных кодов, используемых
при передаче по двоичному симметричному каналу	120
4.6. Границы для кодов, исправляющих и обнаруживающих пакеты ошибок	125

5. Важные линейные блоковые коды	134

5.1. Коды Хэмминга	134
5.2. (23, 12)-код Голея	138
5.3. Оптимальные коды для двоичного симметричного канала	139
5.4. Двоичные коды с большим минимальным расстоянием	141
5.5. Коды Рида-Маллера	144
5.6. Коды, получаемые с помощью матриц Адамара	149
5.7. Произведения кодов	150
5.8. Теоретико-графовые коды	156
5.9. Низкоплотностные коды	159
5.10. Каскадные коды	160

6. Кольца многочленов и поля Галуа	166

6.1. Идеалы, классы вычетов и кольцо классов вычетов	166
6.2. Идеалы и классы вычетов целых чисел	168
6.3. Идеалы многочленов и классы вычетов	170
6.4. Алгебра классов вычетов многочленов	172
6.5. Поля Галуа	177
6.6. Мультипликативная группа поля Галуа	18Э
6.7. Структура конечных полей. Резюме	185
6.8. Векторные подпространства и линейные преобразования конечных
полей	188

7. Линейные переключательные схемы	195

7.1. Определения	195
7.2. Умножение и деление многочленов	196
7.3. Вычисления в алгебрах многочленов и полях Галуа	203
7.4. Линейные рекуррентные соотношения и генераторы с регистром
сдвига	206
7.5. Z-преобразования, передаточные функции и синтез	213
7.6. Анализ общей линейной переключательной схемы с конечным числом
состояний	221

8. Циклические коды	232

8.1. Циклические коды и идеалы	232
8.2. Матричное описание циклических кодов	238
8.3. Описание циклических кодов при помощи ассоциированных
многочленов	243
8.4. Коды Хэмминга	246
8.5. Коды, задаваемые последовательностями максимальной длины	249
8.6. Некоторые двоичные циклические коды	251
8.7. Методы кодирования	251
8.8. Обнаружение ошибок с помощью циклических кодов	256
8.9. Некоторые простые методы исправления ошибок для коротких
циклических кодов	258
8.10. Укороченные циклические коды	270
8.11. Симметрия кодов	273
8.12. Произведение циклических кодов	280
8.13. Квадратично-вычетные коды	284
8.14. Квазициклические коды	287
8.15. Коды, основанные на китайской теореме об остатках	292

9. Коды Боуза-Чоудхури-Хоквингема	301

9.1. Граница БЧХ	301
9.2. Определение кодов	304
9.3. Истинный минимальный вес БЧХ-кодов	310
9.4. Процедура исправления ошибок	315
9.5. Усовершенствования процедуры исправления ошибок	321
9.6. Упрощения в двоичном случае	331
9.7. Исправление стираний и ошибок	337
9.8. Негациклические коды	339

10. Коды с мажоритарным декодированием	343

10.1. Мажоритарное декодирование	343
10.2. Евклидово-геометрические коды	351
10.3. Проективно-геометрические коды	361
10.4. Модификации основного алгоритма мажоритарного декодирования	367
10.5. Обобщённые коды Рида-Маллера	375
10.6. Полиномиальные коды	384

11. Циклические коды, исправляющие пакеты ошибок	391

11.1. Аналитические методы построения кодов	о91
11.2. Некоторые хорошие коды, исправляющие пакеты ошибок,
построенные с помощью ЭВМ	398
11.3. Декодирование	399
11.4. Исправление многократных пакетов	405
11.5. Исправление пакетов и случайных ошибок	406

12. Синхронизация блоковых кодов	410

12.1. Коды, которые только восстанавливают синхронизацию	412
12.2. Коды, которые восстанавливают синхронизацию или исправляют
аддитивные ошибки	418
12.3. Коды, которые восстанавливают синхронизацию и исправляют
аддитивные ошибки	423

13. Свёрточные коды, исправляющие случайные ошибки	429

13.1. Кодирование и вычисление синдрома	429
13.2. Исправление и размножение ошибок	436
13.3. Коды, исправляющие одиночные и двойные ошибки	439
13.4. Самоортогональные коды	441
13.5. Ортогонализируемые коды	446
13.6. Коды, построенные с помощью ЭВМ	448
13.7. Алгоритм декодирования Витерби	449
13.8. Последовательное декодирование	458

14. Свёрточные коды, исправляющие пакеты ошибок	465

14.1. Некоторые определения	465
14.2. Коды Берлекэмпа-Препарата-Месси	468
14.3. Коды Ивадаре	473
14.4. Низкоскоростные коды	480
14.5. Коды, исправляющие пакеты ошибок и случайные ошибки	481

15. Арифметические коды	489

15.1. Определение понятий «ошибка» и «расстояние»	489
15.2. Свойства арифметического веса в двоичном случае	491
15.3. Арифметические коды	493
15.4. Совершенные арифметические коды, исправляющие одиночные ошибки	496
15.5. Арифметические коды с большим минимальным расстоянием	498
15.6. Самодополняющиеся AN + B-коды	501
15.7. Реализация AN- и AN + B-кодов	502
15.8. Раздельные сумматор и проверяющее устройство	504

Приложение А. Неравенства, включающие биномиальные коэффициенты	509
Приложение Б. Краткая таблица значений энтропии (по основанию 10)
и её первой производной	512
Приложение В. Таблицы неприводимых многочленов над полем GF(2)	513
Приложение Г. Перечень двоичных циклических кодов нечётной длины	533
Литература	575

Книги на ту же тему

Теория информации и её приложения (Сборник переводов), Харкевич А. А., ред., 1959
Основы кодирования, Вернер М., 2006
Помехозащищённость систем радиосвязи с расширением спектра сигналов методом псевдослучайной перестройки рабочей частоты. — 2-е изд., перераб. и доп., Борисов В. И., Зинчук В. М., Лимарев А. Е., 2008
Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение, Морелос-Сарагоса Р., 2005
Коды и математика (рассказы о кодировании), Аршинов М. Н., Садовский Л. Е., 1983
Информатика, Луенбергер Д. Д., 2008
Эффективное кодирование, Новик Д. А., 1965
Теория арифметических кодов, Дадаев Ю. Г., 1981
Теоретические основы информационной техники: Учебное пособие для вузов. — 2-е изд., перераб. и доп., Темников Ф. Е., Афонин В. А., Дмитриев В. И., 1979
Стереофоническое радиовещание и звукозапись: Учебное пособие для вузов, Ковалгин Ю. А., Вологдин Э. И., Кацнельсон Л. Н., 2007
Системы связи с шумоподобными сигналами, Варакин Л. Е., 1985
Теория передачи дискретной информации: Учебник для вузов связи, Шварцман В. О., Емельянов Г. А., 1979
Цифровое радиовещание, Рихтер С. Г., 2008
Повышение достоверности передачи цифровой информации, Котов П. А., 1966
Многомерные многоскоростные системы обработки сигналов, Чобану М. К., 2009
Введение в алгебраическую теорию информации, Гоппа В. Д., 1995
Введение в квантовую теорию информации, Холево А. С., 2002
Сеточные методы равномерного зондирования для исследования и оптимизации динамических стохастических систем, Антонова Г. М., 2007
Криптографические методы защиты информации в компьютерных системах и сетях, Иванов М. А., 2001
Криптография, Смарт Н., 2006
Элементарное введение в абстрактную алгебру, Фрид Э., 1979
Введение в алгебру. Часть III. Основные структуры: Учебник для вузов. — 2-е изд., исправл., Кострикин А. И., 2001
Алгебра, Ленг С., 1968
Алгебраическая алгоритмика (с упражнениями и решениями), Ноден П., Китте К., 1999
Булевы алгебры, Сикорский Р., 1969
Группы и их графы, Гроссман И., Магнус В., 1971
Основы теории групп, Каргаполов М. И., Мерзляков Ю. И., 1972

elapsed time 0.024 sec

/Наука и Техника/Математика

ОГЛАВЛЕНИЕ

Книги на ту же тему