Оглавление

Предисловие редактора перевода Предисловие автора .

Глава 1. Основные двоичные коды.......

1.1. Коды с повторением и коды с одной проверкой на четность

1.2. Линейные коды .........

1.3. Коды Хэмминга . . •.......

1.4. Конструктивное введение в теорию БЧХ-кодов, исправляющих двойные опгабки........

Задачи ... .........

Тлфва 2. Аряфметическне операции по модулю неприводимого двоичного многочлена ..........

2.1. Более подробно об алгоритме Евклида ....

*2.2. Логические цепи........

•2.3. Мультипликативное обращение . . .

•2.4. Умножение..........

•2.5. Решение систем линейных уравнений . .

•12.6. Специальный метод решения систем уравнений, матри1щ

которых состоят почти сплош из нулей . . Задачи..............

Глава 3. Число неправодимых д-ячвых вга(нч>членов заданной стстенн

3.1. Грубый подход к решению .......

3.2. Производящие функции.......

3.3. Число неприводимых нормированных д-ичных многочленов заданной степени........

•3.4. Формула обращения Мёбиуса.......

Задачи.........

Глава 4. Структура конечных поли .

4.1. Определения . . .

4.2. Мультипликативная структура конечных полей

4.3. Круговые многочлены.....

4.4. Алгебраическая структура конечных полей

11 14 18

22 30

32 40 47 54 61

72 .78

80 82

86 90 94

96 97 98 104

4.5. Примеры...........112

•4.6. Алгебраическое замыкание......119

•4.7. Определение минимальных многочленов .... 120 Задачи . . . . . . . ... . .125

Глава 5. Двоичные циканческяе коды . . 128

5.1. Переупорядочение столбцов проверочной матрицы кодов Хэмминга . . . . .... . .128

5.2. Переупорядочение столбцов проверочной матрицы двоичных БЧХ-кодов, исправляющих двойные ошибки. . . . 134

Оглавление

5.3. Общие свойства циклических кодов..... 138

5.4. Процедура Ченя......... 142

5.5. Описание общей схемы декодера для произвольного циклического двоичного кода........ 145

5.6. Пример........... 148

5.7. Пример . . . ....... 150

5.8. Эквивалентность определений циклических кодов при помощи различных примитивных корней п-й степени из единицы 151

Задачи ............ 154

Глава 6. Разложение вгаогочленов над конечными волями . 156

6.1. Общий алгоритм . . ....... 156

*6.2. Определенве периода многочлева...... 160

•6.3. Трехчлевы над (2) . . . . 163

6.4. Полное разложение многочлена i» - 1 . . 165 •6.5. Определение степеней неприводвмых делвтелей круговых

многочленов . . . . •...... 166

•6.6. Четно или нечетно число неприводимых делителей / (х) над

Gf (?)?...... . . . . . 169

•6.7. Квадратичный закон взаимности...... 181

Задачи ............ 183

Глава 7. Двоичные БЧХ-коды, 7.1. Примеры .

исправляющее многократные ошибки

7.2. Ключевое уравневие для декодирования двоичных БЧХ-кодов

7.3. Эврнстическбе решение ключевого уравнения

7.4. Алгоритм решения ключевого уравнения над произвольным полем....... ...

•7.5. Связь с матрвчвымв методами декодирования •7.6. Упрощение алгоритма 7.4 для двоичных БХ-кодов 7.7. Реализация декодеров для двоичных БЧХ-кодов Задачи.........

185 186 189

193 197 200 204 208

Глава 8. Недвоичное кодцрюавие

8.1. Схемы модуляции

8.2. Весовые функции Задача . . .

213 215

Глава 9. Негапршляческне коды для иетравм Ли

9.1. Локаторы ошибок и многочлен ошибок

9.2. Коды, исправлякшще две ошибки .

9.3. Негациклические коды

Задачи . . . . ...

216 218 220 225

Глава 10. Недвокчвое обоб1цшю Горшетейяа - Цщрлцра БЧХ-кодю

в случае метрики Хашошга....... 227

10.1. Обобщенные БЧХ-коды я алгоритм их декодврованяя 227

10.2. Примеры......... . 230

•10.3. БЧХ-коды общэго тива и 1-удлввенщ1е БЧХ-коды 231

10.4. Совместное декодированве стираний и ошибок 238

10.5.. Декодярованке более чем t <ши6ок . . 240

10.6. Примеры . . ,....... 246

Зада»» . . . . .......249

Оглавление

Глава 11. Линеаризированные многочлены и аффинные многочлены 250

11.1. Как найти их корни........ 250

11.2. Наименьшее аффинное кратное...... 253

*11.3. Обпще свойства линеаризированных и аффинных многочленов ........... 255

*11.4. Преобразования функции J (z)...... 264

*11.5. Подсчет корней . ........ 266

11.6. Кодовые слова с малым весом в некоторых кодах . . 271

Задачи............ 280

Глава 12. Нахождение числа информационных символов в БЧХ-кодах 282

12.1. Сведение задачи к перечислению некоторых чисел по модулю п . . ......... 282

*12.2. Сведение задачи для случая примитивных БЧХ-кодов

к перечислению некоторых д-ичных последовательностей 283

*12.3. Теорема о числе последовательностей..... 287

*12.4. Примеры..........293

*12.5. Определение числа информационных символов в непримитивных БЧХ-кодах........ 296

12.6. Асимптотические результаты...... 299

*12.7. Истинные расстояния........ 303

Задачи............ 3Q5

Глава 13. Скорость передачи информации для оптимальных кодов. 306

13.1. Граница сферической зщаковки Хэмминга - Рао для больших скоростей ......... 306

*13.2. Совершенные коды........ 310

*13.3. Граница < п -Ь 1 - ft....... 317

13.4. Граница Плоткина для малых скоростей (граница среднего

расстояния)........... 318

*13.5. Эквидистантные коды........ 323

13.6. Граница Элайеса......... 325

13.7. Граница Гилберта ........ 329

13.8. Асимптотические границы для вероятности ошибки и конечные частные случаи....., , -331

Глава 14. Коды, полученные путем модификации и сочетания других

кодов . .......... 338

14.1. 1-удлинение кода (добавление проверочных символов) 338

14.2. 1-укорочение кода (выбрасывание проверочных символов) 340

14.3. Присоединение дополнительных кодовых слов. . . 342

14.4. Выбрасывание кодовых слов...... 342

14.5. 2-удлинение кода (добавление информационных символов) 343

14.6. 2-укорочение кода (вычеркивание информационных символов) ... . . - . . . . . . . 343

14.7. Подкоды над цодполямд . . ... . . 343

14.8. Прямое произведение кодов и его свойства .... 345

14.9. Каскадные ко;*......... 354

Глава 15. Jlpyme основные методы кодирования и декодирования. 358

15.1. Коды Сривэставы - нещ1клические коды с алгебраическим алгоритмом декодирования , , . . . . .. 358

15.2. Вычетные коды.- хорошие коды с трудным декодированием 360

Оглавление 477

15.3. Коды Рида - Маллера - слабые коды с легким декодиро-ВЭ.НИ6М 369

15.4. Пороговое декодирование - лучший из известных алгорит

мов декодирования некоторых кодов .... 374

15.5. Ортогонализируемые коды, основанные на конечных геометриях .......

15.6. Сверточные коды - обзор . » яок Задачи • • • • . . i ! ! ! ; §1

Глава 16. Нумераторы весов........

16.1. Соотношения между нумераторами весов и вероятностью отказа от декодирования..... /q/

16.2. Уравнения Мак-Вильямс - Плесе для нумераторов весов дуальных кодов -....... . 407

16.3. Ограничения весов 43

16.4. Нумераторы весов Казами для некоторь1х подкодов РМ-копа второго порядка ....... 423

16.5. Нумераторы весов для кодов Рида - Соломона i ! ! 435

Приложение А.........

Приложение В.........

Литература ........

Именной указатель.........- 461

Предметный указателе......

УВАЖАЕМЫЙ ТОВАРИЩ!

Ваши замечания о содержании книги, ее оформлении качестве перевода и другие просим присылать по адресу. 129820 Москва, И 1-й Рижский пер., д. 2, издательство «Мир».

Э. БЕРЛЕКЭМП

Алгебраическая теория кодврованвя

Редактор Г. Цукерман Хщожввк А. Антонова ХудожествеянЫй рбда(<тор В. Шапвеалов Техвячеокий редактор Г. Алюяина

Сдано в набор 23/XI 1970 г. Подписано к печати 20/У 1971 г. Бувюга «н. журн. 60 х 90 i/ie= 15 бум. л. 30 веч. л.. Уч.-изд. л. 28.21 Изд. J« 1/5606 Цена 2 р. 77 к. Зак. 658

ИЗДАТЕШЬеТВО «МИР» Москва, 1-й Рижский вер., 2

Моа<овская тшкмфафвя М is

Главполвтрафорот Кошгг во аечатв , 1фи Совете Миввстрон СССР Москва, ТрхттШЛ пер., 9