Книга американского ученого освещает основные вопросы общей теории линейных кодов, исследования циклических (двоичных и недвоичных) кодов для метрик Хэмминга и Ли, вычисление параметров оптимальных кодов, а также вопросы построения кодирующих и декодирующих устройств. Теоретические исследования сопровождаются большим числом примеров и задач, что делает книгу интересной и доступной не только для математиков, но и для широкого круга специалистов, связанных с разработкой систем передачи цифровой информации, а также для аспирантов и студентов соответствующих специальностей.
Author(s): Берлекэмп Э.
Publisher: Мир
Year: 1971
Language: Russian
Pages: 480
City: М.
Титульный лист ......Page 3
Аннотация ......Page 4
Предисловие редактора перевода ......Page 5
Предисловие автора ......Page 7
1.1. Коды с повторением и коды с одной проверкой па четность ......Page 11
1.2. Линейные коды ......Page 14
1.3. Коды Хэмминга ......Page 18
1.4. Конструктивное введение в теорию БЧХ-кодов, исправляющих двойные ошибки ......Page 22
Задачи ......Page 30
2.1. Более подробно об алгоритме Евклида ......Page 32
*2.2. Логические цепи ......Page 40
*2.3. Мультипликативное обращение ......Page 47
*2.4. Умножение ......Page 54
*2.5. Решение систем линейных уравнений ......Page 61
*2.6. Специальный метод решения систем уравнений, матрицы которых состоят почти сплош из нулей ......Page 72
Задачи ......Page 78
3.1. Грубый подход к решению ......Page 80
3.2. Производящие функции ......Page 82
3.3. Число неприводимых нормированных q-ичных многочленов заданной степени ......Page 86
*3.4. Формула обращения Мёбиуса ......Page 90
Задачи ......Page 94
4.1. Определения ......Page 96
4.2. Мультипликативная структура конечных полей ......Page 97
4.3. Круговые многочлены ......Page 98
4.4. Алгебраическая структура конечных полей ......Page 104
4.5. Примеры ......Page 112
*4.6. Алгебраическое замыкание ......Page 119
*4.7. Определение минимальных многочленов ......Page 120
Задачи ......Page 125
5.1. Переупорядочение столбцов проверочной матрицы кодов Хэмминга ......Page 128
5.2. Переупорядочение столбцов проверочной матрицы двоичных БЧХ-кодов, исправляющих двойные ошибки ......Page 134
5.3. Общие свойства циклических кодов ......Page 138
5.4. Процедура Ченя ......Page 142
5.5. Описание общей схемы декодера для произвольного циклического двоичного кода ......Page 145
5.6. Пример ......Page 148
5.7. Пример ......Page 150
5.8. Эквивалентность определений циклических кодов при помощи различных примитивных корней n-й степени из единицы ......Page 151
Задачи ......Page 154
6.1. Общий алгоритм ......Page 156
*6.2. Определение периода многочлена ......Page 160
*6.3. Трехчлены над GF (2) ......Page 163
6.4. Полное разложение многочлена x^n—1 ......Page 165
*6.5. Определение степеней неприводимых делителей круговых многочленов ......Page 166
*6.6. Четно или нечетно число неприводимых делителей f(х) над GF(q)? ......Page 169
*6.7. Квадратичный закон взаимности ......Page 181
Задачи ......Page 183
7.1. Примеры ......Page 185
7.2. Ключевое уравнение для декодирования двоичных БЧХ-кодов ......Page 186
7.3. Эвристическое решение ключевого уравнения ......Page 189
7.4. Алгоритм решения ключевого уравнения над произвольным полем ......Page 193
*7.5. Связь с матричными методами декодирования ......Page 197
*7.6. Упрощение алгоритма 7.4 для двоичных БЧХ-кодов ......Page 200
7.7. Реализация декодеров для двоичных БЧХ-кодов ......Page 204
Задачи ......Page 208
8.1. Схемы модуляции ......Page 210
8.2. Весовые функции ......Page 213
Задача ......Page 215
9.1. Локаторы ошибок и многочлен ошибок ......Page 216
9.2. Коды, исправляющие две ошибки ......Page 218
9.3. Негациклические коды ......Page 220
Задачи ......Page 225
10.1. Обобщенные БЧХ-коды и алгоритм их декодирования ......Page 227
10.2. Примеры ......Page 230
*10.3. БЧХ-коды общего типа и 1-удлиненные БЧХ-коды ......Page 231
10.4. Совместное декодирование стираний и ошибок ......Page 238
10.5. Декодирование более чем t ошибок ......Page 240
10.6. Примеры ......Page 246
Задача ......Page 249
11.1. Как найти их корни ......Page 250
11.2. Наименьшее аффинное кратное ......Page 253
*11.3. Общие свойства линеаризированных и аффинных многочленов ......Page 255
*11.4. Преобразования функции ~f(z) ......Page 264
*11.5. Подсчет корней ......Page 266
11.6. Кодовые слова с малым весом в некоторых кодах ......Page 271
Задачи ......Page 280
12.1. Сведение задачи к перечислению некоторых чисел по модулю n ......Page 282
*12.2. Сведение задачи для случая примитивных БЧХ-кодов к перечислению некоторых q-ичных последовательностей ......Page 283
*12.3. Теорема о числе последовательностей ......Page 287
*12.4. Примеры ......Page 293
*12.5. Определение числа информационных символов в непримитивных БЧХ-кодах ......Page 296
12.6. Асимптотические результаты ......Page 299
*12.7. Истинные расстояния ......Page 303
Задачи ......Page 305
13.1. Граница сферической упаковки Хэмминга — Рао для больших скоростей ......Page 306
*13.2. Совершенные коды ......Page 310
*13.3. Граница d ≤ n + 1 — k ......Page 317
13.4. Граница Плоткина для малых скоростей (граница среднего расстояния) ......Page 318
*13.5. Эквидистантные коды ......Page 323
13.6. Граница Элайеса ......Page 325
13.7. Граница Гилберта ......Page 329
13.8. Асимптотические границы для вероятности ошибки и конечные частные случаи ......Page 331
14.1. 1-удлинение кода (добавление проверочных символов) ......Page 338
14.2. 1-укорочение кода (выбрасывание проверочных символов) ......Page 340
14.4. Выбрасывание кодовых слов ......Page 342
14.7. Подкоды над подполями ......Page 343
14.8. Прямое произведение кодов и его свойства ......Page 345
14.9. Каскадные коды ......Page 354
15.1. Коды Сривэставы — нециклические коды с алгебраическим алгоритмом декодирования ......Page 358
15.2. Вычетные коды — хорошие коды с трудным декодированием ......Page 360
15.3. Коды Рида — Маллера — слабые коды с легким декодированием ......Page 369
15.4. Пороговое декодирование — лучший из известных алгоритмов декодирования некоторых кодов ......Page 374
15.5. Ортогонализируемые коды, основанные на конечных геометриях ......Page 382
15.6. Сверточные коды — обзор ......Page 395
Задачи ......Page 402
16.1. Соотношения между нумераторами весов и вероятностью отказа от декодирования ......Page 404
16.2. Уравнения Мак-Вильямс — Плесе для нумераторов весов дуальных кодов ......Page 407
16.3. Ограничения весов ......Page 413
16.4. Нумераторы весов Казами для некоторых подкодов РМ-кода второго порядка ......Page 423
16.5. Нумераторы весов для кодов Рида — Соломона ......Page 435
Приложение А ......Page 447
Приложение В ......Page 448
Литература ......Page 449
Именной указатель ......Page 461
Предметный указатель ......Page 463
Оглавление ......Page 474
Выходные данные ......Page 479
