В учебное пособие, ориентированное на семестровый курс лекций, включе-
ны классические разделы теории кодирования: линейные коды, основы по-
строения и декодирования алгебраических кодов. Рассказывается о представ-
лении кодов решетками, о декодировании по максимуму правдоподобия. При-
ведены основы теории сверточных кодов, введение в каскадные коды,
модуляционные коды и турбо-коды. Отдельная глава посвящена низкоплотно-
стным кодам, находящим все более широкое применение в телекоммуникаци-
онных стандартах. Все необходимые математические сведения приведены
в виде приложений к главам учебного пособия. В книге много численных при-
меров, детальных алгоритмов, примеров программ MATLAB
Author(s): Кудряшов Б. Д.
Series: Учебная литература для вузов
Publisher: БХВ-Петербург
Year: 2016
Language: Russian
Pages: 400
City: СПб
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1 . В ведение . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1 . 1 . Постановка задачи помехоустойчивого кодирования . 5
1 .2. Обзор кодов для защиты информации от ошибок . . 19
В ыв оды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2
З адачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 3
Приложение. Биномиальное и полиномиальное распреде-
ления . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 6
2 . Линейные коды . . . . . . . . . . . . . . . . . . . . . . 32
2. 1 . Арифметика пространства двоичных
последовательностей . . . . . . . . . . . . . . . . . . . 32
2.2. Порождающая и проверочная матрицы . . . . . . . . 37
2.3. Вычисление расстояния по проверочной матрице . . . 42
2 . 4 . Примеры кодов . . . . . . . . . . . . . . . . . . . . . . . 44
2 . 5 . Синдромное декодирование . . . . . . . . . . . . . . . 48
2.6. Радиус покрытия и декодирование по
минимуму расстояния Хэмминга . . . . . . . . . . . 5 1
2 . 6 . 1 . Радиус покрытия . . . . . . . . . . . . . . . . . 52
2.6.2. Декодирование по соседям нулевого слова . . . 54
2.6.3. Декодирование по информационным
совокупностям . . . . . . . . . . . . . . . . . . . 5 7
В ыв оды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2
З адачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3
Приложение. Группы. Основные определения . . . . . . . . 67
IV Оглавление
3. Некоторые границы на характеристики кодов . . . 69
3 . 1 . Граница Хэмминга . . . . . . . . . . . . . . . . . . . . 70
3 . 2 . Граница Варшамова–Гилберта . . . . . . . . . . . . . . 71
3 . 3 . Граница Плоткина . . . . . . . . . . . . . . . . . . . . . 74
3 . 4 . Граница Грайсмера . . . . . . . . . . . . . . . . . . . . 77
3 . 5 . Другие границы . . . . . . . . . . . . . . . . . . . . . . 79
3.6. Спектр кода и оценки вероятности
ошибки . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 0
3.6. 1 . Граница вероятности ошибки через спектр ко-
да для ДС К . . . . . . . . . . . . . . . . . . . . 8 0
3.6.2. Граница вероятности ошибки для гауссовского
кан ал а . . . . . . . . . . . . . . . . . . . . . . . 8 3
3 . 6 . 3 . Нижняя граница Шеннона . . . . . . . . . . . . 87
З адачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 0
Приложение. Тождество Мак-Вильямс . . . . . . . . . . . . 93
4. Декодирование коротких кодов по максимуму
правдоподобия . . . . . . . . . . . . . . . . . . . . . . . 96
4. 1 . Декодирование по максимуму
правдоподобия . . . . . . . . . . . . . . . . . . . . . . . 9 6
4.2. Поиск кратчайшего пути в решетке.
Алгоритм Витерби . . . . . . . . . . . . . . . . . . . . 99
4. 3 . Минимальная решетка кода . . . . . . . . . . . . . . . 1 03
4.4. Построение решетки кода по порождающей матрице . 107
4.5. Построение решетки кода по проверочной матрице . . 1 12
4.6. Декодирование по максимуму апостериорной вероят-
ности с мягкими решениями. Алгоритм БКДР . . . . 1 14
4.7. Сложность решеток линейных кодов и сложность де-
кодирования по максимуму правдоподобия . . . . . . 124
4.7. 1 . Свойства минимальных решеток линейных
кодов . . . . . . . . . . . . . . . . . . . . . . . . 1 2 4
4. 7. 2 . Границы сложности решеток . . . . . . . . . . . 1 26
4.8. Практические алгоритмы декодирования . . . . . . . 129
4 . 8 . 1 . B EA S T . . . . . . . . . . . . . . . . . . . . . . . 1 3 0
4. 8 . 2 . Метод порядковых статистик . . . . . . . . . . 1 36
З адачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 3 9
Оглавление V
5 . Циклические коды . . . . . . . . . . . . . . . . . . . . 141
5. 1 . Порождающий и проверочный полиномы циклическо-
го кода . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 4 2
5 . 2 . Примеры циклических кодов . . . . . . . . . . . . . . 147
5 .3 . Кодирование и вычисление синдрома . . . . . . . . . . 153
З адачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 6 0
Приложение . Конечные поля . . . . . . . . . . . . . . . . . 1 6 1
Кольцо вычетов . . . . . . . . . . . . . . . . . . . . . . 1 6 1
Кольцо многочленов . . . . . . . . . . . . . . . . . . . 1 62
Мультипликативная группа поля Галуа . . . . . . . . 164
Минимальные многочлены . . . . . . . . . . . . . . . . 1 68
6. БЧХ-коды и Р С-коды . . . . . . . . . . . . . . . . . . 1 70
6 . 1 . Определение БЧХ-кода . . . . . . . . . . . . . . . . . . 1 71
6 . 2 . Построение БЧХ-кодов . Примеры . . . . . . . . . . . . 1 79
6 . 3 . Коды Рида–Соломона . . . . . . . . . . . . . . . . . . . 1 82
З адачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 8 4
7. Декодирование БЧХ- и РС-кодов . . . . . . . . . . . 187
7. 1 . Алгоритм Питерсона–Горенстейна–Цирлера . . . . . . 188
7. 2 . Алгоритм Берлекэмпа–Месси . . . . . . . . . . . . . . 1 9 1
7 . 3 . Алгоритм Ф орни . . . . . . . . . . . . . . . . . . . . . . 1 9 8
7.4. Исправление ошибок и стираний . . . . . . . . . . . . 20 1
7.5. Декодирование по минимуму обобщенного расстояния 206
З адачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 0 9
Приложение. Линейная сложность последовательностей . 21 1
8 . Сверточные коды . . . . . . . . . . . . . . . . . . . . . 2 1 8
8 . 1 . Представление сверточного кода . . . . . . . . . . . . 2 1 9
8.2. Свободное расстояние и спектр сверточного кода . . . 229
8 . 3 . Оценки вероятности ошибки . . . . . . . . . . . . . . . 236
8.4. Декодирование по максимуму правдоподобия . . . . 241
8 .4. 1 . Реализация алгоритма Витерби . . . . . . . . . 245
8.5. Высокоскоростные и переменные
сверточные коды . . . . . . . . . . . . . . . . . . . . . . 249
8.6. Построение блоковых кодов из сверточных . . . . . . 253
8 . 6 . 1 . Усеченные сверточные коды . . . . . . . . . . . 253
VI Оглавление
8.6.2. Циклически усеченные сверточные коды . . . 254
З адачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 5 9
9. Алгебраический подход к сверточным кодам . . . 268
9 . 1 . Кодер сверточного кода общего вида . . . . . . . . . . 268
9 . 2 . С митова форма . . . . . . . . . . . . . . . . . . . . . . 2 76
9.3. Минимальная базовая порождающая матрица . . . . 281
9 .4. Проверочная матрица и дуальный код . . . . . . . . . 285
В ыв оды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 8 8
Приложение. МАТЛАБ-программа декомпозиции Смита . 289
10. Длинные коды из коротких кодов . . . . . . . . . . 295
1 0 . 1 . Итеративные коды . . . . . . . . . . . . . . . . . . . . 296
10.2. Каскадные и обобщенные каскадные коды . . . . . . 300
1 0 . 3 . Турбо-коды . . . . . . . . . . . . . . . . . . . . . . . . 3 0 6
1 0 . 3 . 1 . Выбор компонентных кодов . . . . . . . . . . . 309
1 0 . 3 . 2 . Турбо-декодирование . . . . . . . . . . . . . . 3 1 0
1 0 . 3 . 3 . Практическая реализация . . . . . . . . . . . 3 1 3
1 0 .4 . Кодированная модуляция . . . . . . . . . . . . . . . . 3 1 7
1 0 . 4 . 1 . Коды и сигналы . . . . . . . . . . . . . . . . . 3 1 8
10 .4.2 . Сигнально-кодовые конструкции . . . . . . . . 327
10.4.3. Кодированная модуляция с перемешиванием
битов . . . . . . . . . . . . . . . . . . . . . . . . 3 3 3
З адачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 7
11. Коды с малой плотностью проверок на четность . 339
1 1 . 1 . Проверочная матрица МППЧ-кода . . . . . . . . . . 339
1 1 .2. Декодирование по принципу распространения доверия 343
1 1 .3. Графы Таннера и характеристики МППЧ-кодов . . . 350
1 1 .4 . Построение МППЧ-кодов . . . . . . . . . . . . . . . . 356
1 1 .4. 1 . Квазициклические МППЧ-коды . . . . . . . . 356
1 1 . 4 . 2 . Кодирование . . . . . . . . . . . . . . . . . . . 3 6 3
1 1 .4.3 . Обзор конструкций МППЧ-кодов . . . . . . . 365
1 1 .5. Коды для стандартов: результаты моделирования . . 372
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 76
Предметный указатель . . . . . . . . . . . . . . . . . . . . 388
