Введение
1. Комбинаторное декодирование линейных блоковых кодов 12
1.1. Декодирование по обобщенным информационным совокупностям 12
1.1.1. Понятие обобщенной информационной совокупности. Алгоритм декодирования 13
1.1.2. Построение т-покрытий из кодовых слов 17
1.1.3. Таблица декодеров по обобщенным информационным совокупностям 21
1.2. Табличное декодирование 24
1.2.1. Синдромное декодирование 25
1.2.2. Декодирование по информационным совокупностям 26
1.2.3. Декодирование в надкодах 28
1.2.4. Комбинирование алгоритмов декодирования 30
1.2.5. Декодирование кодов с большой группой симметрии 35
1.2.6. Декодирование квадратично-вычетных кодов 38
1.3. Асимптотика 43
1.3.1. Обзор алгоритмов декодирования линейных блоковых кодов для декодеров с жесткими решениями 43
1.3.2. Сложность декодирования линейных блоковых кодов 48
1.4. Выводы
2. Алгебраическое декодирование 59
2.1. Алгебраическое декодирование по обобщенным информационным совокупностям 59
2.1.1. Основные понятия и определения 60
2.1.2. Укорочения (Ь,д)-кодов 61
2.1.3. Применение декодирования укороченных (Ь5,#5)-кодов 64
2.2. "Генетическая" связь алгебраических методов декодирования 66
2.2.1. Основные понятия и определения 67
2.2.2. Алгоритм Гао 68
2.2.3. Оригинальный алгоритм Велча - Берлекэмпа 70
2.2.4. Интерпретация Чамберса 71
2.2.5. Алгоритм Велча - Берлекэмпа в частотной области 72
2.2.6. Вывод алгоритма Гао 72
2.2.7. Расширенный алгоритм Евклида 73
2.2.8. Корректность алгоритма Гао 74
2.2.9. Пример 78
2.2.10. Замечания к разделу 81
2.3. Декодирование в надкодах 82
2.3.1. Основные определения 82
2.3.2. Дополнительные тождества 84
2.3.3. Алгоритм исправления трех ошибок 85
2.3.4. Декодирование свыше конструктивного расстояния на основе надкодов 89
2.3.5. Пример 91
2.4. Выводы
3. Вычисление дискретного преобразования Фурье над конечным полем 95
3.1. Вычисление корней многочлена 95
3.1.1. Алгоритм быстрого поиска корней многочлена 97
3.1.2. Результаты моделирования 100
3.1.3. Специальные разложения многочленов 101
3.1.4. Гибридный метод 104
3.1.5. Аналитические методы вычисления корней многочленов степени до четырех 106
3.1.6. Сравнение методов вычисления корней многочлена 111
3.21 Циклотомический алгоритм 112
3.2.1. Основные понятия и определения 112
3.2.2. Быстрое вычисление преобразования Фурье 115
3.2.3. Пример 119
3.2.4. Сравнение сложности алгоритмов БПФ 124
3.3. Рекуррентный метод 124
3.3.1. Основные понятия и определения 126
3.3.2. Алгоритм Рейдера 128
3.3.3. Свойства матрицы эквивалентного преобразования 130
3.3.4. Упорядочение чисел из полной системы вычетов 134
3.3.5. Быстрое вычисление ДПФ 139
3.3.6. Примеры вычисления ДПФ 142
3.4. Вычисление синдрома 152
3.4.1. Вычисление неполного ДПФ с помощью циклотомического алгоритма 152
3.4.2. Вычисление неполного ДПФ с помощью рекуррентного метода 160
3.5. Выводы 165
4. Декодирование по кодовым решеткам 166
4.1. Представления кодов с заданной группой симметрии 166
4.1.1. Две конструкции кодов 166
4.1.2. Приведение матриц кода к квазициклическому представлению 1 4.2. Циклические замкнутые решетки 173
4.3. Звездные решетки
4.3.1. Представление кода Голея в виде звездной решетки 177
4.3.2. Декодирование кода Голея по звездной решетке 182
4.3.3. Замечания к разделу 184
4.4. Декодирование кодов Рида - Соломона по звездным
решеткам 184
4.4.1. Разложение Варди - Беэри 184
4.4.2. Метод декодирования 188
4.5. Выводы 190
5. Вопросы реализации 191
5.1. Приложение методов быстрого декодирования линейных блоковых кодов к системам связи 191
5.1.1. Многошаговое декодирование итеративных кодов Хэмминга 192
5.1.2. Результаты моделирования
5.2. Схема вычисления ДПФ 198
5.3. Реализация циклотомического алгоритма вычисления ДПФ на программируемой логической интегральной схеме 201
5.4. Выводы 206
Заключение 207
Библиографический список 209
