Разработка и исследование методов комбинаторного декодирования для каналов с непрерывным выходом

• Автор: Лазарева, Светлана Викторовна
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Санкт-Петербург
• Количество страниц: 130 с. : ил

Оглавление
ВВЕДЕНИЕ

ГЛАВА 1 Комбинаторное декодирование линейных блоковых кодов в дискретном канале

1.1 Основные определения и понятия

1.2 Алгоритм ЛевитинаХартмана

1.3 Декодирование по информационным совокупностям

1.3.1 Заранее выбранные покрывающие множества

1.3.2 ижние границы для числа покрывающих множеств

1.3.3 Метод случайного выбора множеств

1.4 Алгоритм, основанный на сортировке

1.5 Декодирование с помощью укорочений и надкодов

1.6 Выводы
ГЛАВА 2 Декодирование по информационным совокупностям в канале с
непрерывным в ыходом.
2.1 Переборные алгоритмы, использующие надежности
2.1.1 Алгоритмы, типа Чейза
2.1.2 Алгоритм декодирования Лина
2.1.3 Декодирование по обобщенной информационной совокупности
2.2 Почти оптимальные алгоритмы
2.2.1 Алгоритм Вигерби
2.2.2 Градиентный метод декодирования
2.2.3 Декодирование с помощью весовог о разбиения
2.3 Декодирование по информационной совокупности в канале с непрерывным
выходом
2.3.1 Декодирование по максимуму правдоподобия
2.3.2 Модификация алгоритма Думера для кодов конечной длины
2.3.3 Зависимый выбор информационной совокупности
2.3.4 Оценки сложности алгоритмов
2.3.4.1 Сложность алгоритма 1
2.3.4.2 Сложность алгоритма 2
2.3.4.3 Сложность алгоритма 3
2.3.5 Декодирование с помощью укорочений
2.4 Выводы
ГЛАВА 3 Кодирование на транспортном уровне сети передачи данных
3.1 Сеть с коммутацией пакетов. Основные допущения.
3.2 Избыточное кодирование как средство уменьшения задержки сообщения
3.3 Оценки эффективности кодирования на транспортном уровне при неэкспоненциальных моделях задержки.
3.3.1 Математическое введение. Основные определения и понятия.
3.3.2 Слабая сходимость для ктых экстремальных значений.
3.3.3 Скорость сходимости
3.3.4 Моменты распределения
3.3.5 Модели для зависимых случайных величин
3.3.6 Решение поставленной задачи при неизвестном исходном распределении задержки пакетов
3.3.7 Экспоненциальный тип распределения
3.4 Методика выбора оптимального кода
3.5 Выводы1
ЗАКЛЮЧЕНИЕ
Литература


Описываются алгоритмы декодирования по максимуму правдоподобия в полунепрерывном канале: декодирование по информационным совокупностям []; декодирование с помощью решетки []. Вводится понятие почти оптимального алгоритма, в качестве примера рассматривается алгоритм декодирования с помощью весового разбиения []. Основная часть данной главы посвящена построению конечных декодеров конкретных кодов. Предлагаются алгоритмы декодирования по информационным совокупностям для конкретных кодов, алгоритм декодирования с зависимым выбором информационной совокупности, а также алгоритм декодирования с помощью укорочений. Третья глава посвящена рассмотрению возможностей применения комбинаторного декодирования для сборки сообщений на транспортном уровне сети передачи данных с коммутацией пакетов. В настоящей главе приводится условие выгодности кодирования при произвольном распределении задержки пакетов, приводится методика выбора оптимального кода, в смысле минимизации задержки сообщения. В заключении приводятся основные результаты исследования. Глава 1. В этой главе вводятся основные определения и понятия теории кодирования, рассматриваются общие методы декодирования линейных кодов, т. Основные определения и понятия. Определение. Линейный код это подпространство в ОР"(я). Из теории линейных пространств известно, что любое множество базисных векторов может быть использовано в качестве строк для построения (кхп) - матрицы О, которая называется порождающей матрицей кода. Пространство строк матрицы О есть линейный код С, любое кодовое слово есть линейная комбинация строк из С. Множество с]' кодовых слов называется линейным (п,к)-кодом. Строки матрицы О линейно независимы, и число строк к равно размерности подпространства. Размерность всего пространства СРг,(с]) равна п. Всего существует цк кодовых слов, и цк различных к- последовательностей над ОГ(с]) могут быть отображены на множество кодовых слов. Поскольку С является подпространством, оно имеет ортогональное дополнение Сх, которое состоит из всех векторов, ортогональных к С. Ортогональное дополнение также является подпространством и, таким образом, может рассматриваться как код. Такой код С называется кодом дуальным к С. Ортогональное дополнение С1 имеет размерность п-к, и любой его базис также состоит из п-к векторов. Пусть Н-матрица со строками, являющимися этими базисными векторами. Тогда п-последовательность с является кодовым словом, когда она ортогональна каждой вектор - строке матрицы И, т. Нт = 0. Это равенство позволяет проверить, является ли данное слово кодовым. Матрица И называется проверочной матрицей кода. Нт =0 выполняется при подстановке вместо с любой строки матрицы в, то СНТ = 0. Предположим, что сообщение и=(и|,и2,. Л1к) закодировано в кодовое слово х=(Х|,Х2,. Под каналом подразумевается среда, по которой осуществляется передача сигналов от передатчика к приемнику. Пусть X- множество q входных сигналов и У з X множество выходных сигналов (возможно, конечное). Определение. Канал- это множество распределения вероятности на [х” х У"), п > 1, известное декодеру. Определение. Канал называется дискретным, если V- представляет собой дискретное множество. Определение. Мы предполагаем, что все сообщения (кодовые слова) равновероятны. Аддитивность означает Рг(у|х)=Рг(у-х), го есть в аддитивном канале вероятность ошибки не зависит от передаваемого сообщения. В дальнейшем, будем называть элементы X" и Уп векторами. Определение. Предположим, что У" может быть разбито на непересекающиеся подмножества УП=ЦУ;, где |У^| = ()а. Ра={^(ух)]. Определение. Так как канал с шумом, принятый вектор у=(уі,У2,У«) может отличаться от х. Декодер должен на основании у решить, какое сообщение и или какое кодовое слово х было передано. Пусть ф алгоритм декодирования, т. У" -> С. Декодирование по максимуму правдоподобия это такое отображение ф)(, что у -> с є С: Рг(ух) > Рг(у,с') Ус' є С. Так как кодовые слова равновероятны, мы можем сказать, что декодирование по максимуму правдоподобия находит такое с є С, что для всех с' е С, Рг(у|с)>Рг(у|с).