Комбинаторное декодирование линейных блоковых кодов

• Автор: Крук, Евгений Аврамович
• Шифр специальности: 05.13.01
• Научная степень: Докторская
• Год защиты: 1999
• Место защиты: Санкт-Петербург
• Количество страниц: 343 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ $
1. КЛАССИЧЕСКИЕ АЛГОРИТМЫ И ИХ ОБОБЩЕНИЯ
1. 1 Декодирование по минимуму расстояния
1.2 Декодирование по информационным совокупностям
1.3 Перестановочное декодирование и декодирование с помощью покрывающих полиномов
1.4 Комбинированное декодирование по информационным совокупностям
1.5 Обобщения алгоритмов декодирования по информационным совокупностям
1.6 Выводы и замечания по разделу
2. СЛОЖНОСТЬ ДЕКОДИРОВАНИЯ ЛИНЕЙНЫХ БЛОКОВЫХ КОДОВ
2. 1 Оптимальные и подоптимальные методы декодирования..39 2. 2 Сложность декодирования по информационным
совокупностям
2.3 Сложность декодирования с использованием укорочений.
Применение сортировки
2. 4 Декодирование с использованием надкодов
2. 5 Выводы и замечания по разделу
3. ДЕКОДИРОВАНИЕ КВАЗИЦИКЛИЧЕСКИХ КОДОВ 8<
3. 1 Симметричные коды £2
3. 2 Существование "хороших" квазициклических кодов
3. 3 Декодирующие совокупности линейных кодов
3. 4 Декодирование по обобщенным информационным
'совокупностям
3.5 Построение т-покрытий из кодовых слов. Таблица декодеров по обобщенным информационным совокупностям.'108
3. 6 Декодирование с использованием надкодов. Табличные
алгоритмы
3.7 Декодирование кодов (24,12) и (48,24) {25
3.8 Выводы и замечания по разделу
4. КОДИРОВАНИЕ И ДЕКОДИРОВАНИЕ НА ТРАНСПОРТНОМ УРОВНЕ СЕТИ ПЕРЕДАЧИ ДАННЫХ 1М
4. 1 Сеть с коммутацией пакетов. Основные допущения
4.2 Избыточное кодирование как средство уменьшения задержки сообщений
4. 3 Бесприоритетная передача срочных сообщений
4.4 Анализ вероятности доставки сообщений в сети
с потерями
4. 5 Кодирование в сетях с ненадежными каналами
4.6 Оценки эффективности кодирования на транспортном
уровне при неэкспоненциальных моделях задержки
4. 7 Выводы и замечания по разделу
5. ДЕКОДИРОВАНИЕ В ЗВЕНЕ СЕТИ ПЕРЕДАЧИ ДАННЫХ 12С
5. 1 Постановка задачи кодирования в классе каналов
5.2 Расчет вероятности ошибки при декодировании
в метрике Хэмминга
5.3 Метрическое описание каналов с группированием ошибок.19$
5.4 Метрики для марковского канала
5. 5 Кодирование в марковской метрике
5. 6 Декодирование для класса каналов
5. 7 Выводы и замечания по разделу

6. ОБЕСПЕЧЕНИЕ ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ В СЕТИ
НА ОСНОВЕ ЗАДАЧИ ДЕКОДИРОВАНИЯ
6. 1 Криптография с открытым ключом и "трудно
разрешимые" задачи
6. 2 Декодирование линейных кодов и криптоанализ
кодовых криптосистем
6. 3 Кодовые криптосистемы на базе полного декодирования .26
6. 4 Задача аутентификации информации
6. 5 Выводы и замечания по разделу
ЗАКЛЮЧЕНИЕ
Литература
Приложения
Пример 1.7. Вновь рассмотрим декодирование двоичного кода (7,4)
с 6=3. Порождающая матрица С этого кода
'1 0 0 0 1 0 1' г 0 10 0 111 0 0 1 0 1 10 0 0 0
(1. 10)
Множество символов л = 10,1,2,4,} задает (4,3)- укороченный код
А(д1) с расстоянием 2 и порождаемый матрицей

Г/, Л
Б(л)- 0 0 ! !

(1. 11)
Декодируя этот код с обнаружением ошибки, мы определяем, что либо на позициях {0,1,2,4), либо на позициях {3,5,6} нет ошибок (если ошибка при декодировании А(л) не обнаружена, она находится на позициях {3,5,6}). В любом случае мы получаем три безошибочных информационных позиции и, следовательно, список, состоящий только из двух векторов-кандидатов, причем декодирование в коде Асл) - это просто вычисление проверки на четность.
Рассмотренный пример является, в основном, иллюстрацией подхода к декодированию на основе укорочений. Декодер, полученный нами, имеет сложность, мало отличающуюся от сложности декодеров, уже рассмотренных в этом разделе.
Заметим, что вместо 3 информационных совокупностей, необходимых для декодирования кода (7,4), оказывается достаточным использовать один 4-набор, которому соответствует, правда, список из двух векторов-кандидатов.
Сложность декодирования с использованием укорочений определяется двумя компонентами: числом декодирований укороченных кодов, которые надо произвести для исправления ошибок в