- •Помехоустойчивое кодирование в системах телекоммуникаций
- •Пояснительная записка
- •Лабораторная работа 1 Исследование эффективных кодов на примере кода Хаффмена
- •1. Цель работы:
- •2. Литература:
- •3. Подготовка к работе:
- •4. Основное оборудование:
- •5. Задание:
- •6. Порядок выполнения работы:
- •7. Содержание отчета:
- •8. Контрольные вопросы:
- •9. Методические указания:
- •9.2. Основы эффективного кодирования
- •9.3. Методы эффективного кодирования при известной статистике сообщений
- •9.4. Методы эффективного кодирования при неизвестной статистике сообщений
- •9.5. Метод Хаффмена
- •9.6 Описание лабораторной работы
- •Лабораторная работа 2 Исследование эффективности линейных блоковых кодов
- •6.2. Исследование системы передачи данных с двоичным симметричным каналом связи при использовании кода Хэмминга.
- •7. Содержание отчета:
- •8. Контрольные вопросы:
- •Лабораторная работа 3 Исследование эффективности циклических кодов
- •7. Содержание отчета:
- •8. Контрольные вопросы:
- •9. Методические указания:
- •8.2 Инструкция по пользованию практической части программы
- •8.3 Инструкция по использованию тестирующей части программы
- •Лабораторная работа 4 Исследование алгоритма Витерби
- •6.2 Экспериментальной части программы
- •6.3 Инструкция по использованию тестирующей части программы
- •9.2 Представление сверточного кода порождающими многочленами
- •9.3. Кодовое дерево сверточного кода и решетчатая диаграмма
- •9.4 Свободное расстояние. Спектр.
- •9.5 Катастрофические кодеры
- •9.6 Декодирование сверточных кодов по максимуму правдоподобия. Алгоритм Витерби
- •9.7 Поиск кратчайшего пути на графе по принципу динамического программирования
- •9.8 Алгоритм Витерби
- •Лабораторные работы 5,6 Исследование схем кодеров и декодеров с обнаружением ошибок
- •6. Порядок выполнения работы:
- •6.2. Исследование системы передачи данных с кодами рс при использование канала с Гауссовскими помехами.
- •7. Содержание отчета:
- •8. Контрольные вопросы:
- •Лабораторные работы 7,8 Исследование схем кодеров и декодеров с исправлением ошибок
- •6. Порядок выполнения работы:
- •7. Содержание отчета:
- •8. Контрольные вопросы:
9.2 Представление сверточного кода порождающими многочленами
Схема кодера двоичного сверточного кода в общем виде представлена на рисунок 7. Кодер содержит k двоичных регистров сдвига длин m1,…,mk. Входами регистров сдвига являются информационные символы. Выходы ячеек регистров соединены с сумматорами по модулю 2. Всего сумматоров n .
Рисунок 7 - Общая структурная схема кодера сверточного кода со скоростью k/n
На каждом такте работы кодера на его вход поступает блок k из информационных символов. Эти символы и символы, хранящиеся в данный момент в регистрах кодера, поступают на входы тех сумматоров, которые подключены к соответствующим ячейкам. Результаты сложения по модулю два поступают на выход схемы. После этого в каждом из регистров происходит сдвиг, новые информационные символы записываются в первые ячейки, а содержимое остальных ячеек сдвигается на один разряд. Содержимое ячеек регистров сдвига в каждый конкретный момент времени называется текущим состоянием кодера. Предположим, что в начальный момент времени кодер находится в некотором заранее известном состоянии. Примем для определенности это начальное состояние нулевым.
Рассмотрим процесс кодирования полубесконечной информационной последовательности.
Выходы сумматоров на каждом такте работы называются кодовыми символами сверточного кода. Полубесконечная последовательность кодовых символов называется кодовым словом сверточного кода. Множество всевозможных кодовых слов образует сверточный код.На каждом такте работы кодера k информационного символа используются для формирования n кодовых символов.
(1)
Отношение называется скоростью сверточного кода. Примеры кодеров сверточных кодов приведены на рисунке 8. Суммарная длина регистров сверточного кодера называется длиной кодового ограничения кода, а максимальная длина регистров называется задержкой кодера. Для кодов со скоростью память и кодовое ограничение совпадают.
Рисунок 8 - Примеры сверточных кодеров
Рассматриваемые схемы кодеров сверточных кодов полностью описываются связями ячеек регистров сдвига с выходными сумматорами. Существует несколько общепринятых форм представления этих связей. Начнем с кодов со скоростью 1/n. Связи каждого из n сумматоров с ячейками одного регистра длины записываются в виде двоичного вектора , . Ноль означает отсутствие связи, единица - наличие. Векторы gi называют порождающими. В таблицах кодов порождающие векторы приводят в восьмеричной форме. Например, генератор будет записан как (125). Другие примеры показаны на рисунке 8 Порождающие векторы записывают также в виде полиномов формальной переменной D. Например, порождающие полиномы кодера, показанного на рисунке 8а, имеют вид
(2)
Эту совокупность полиномов можно также записать в виде матричного порождающего полинома
(3)
Полиномиальное и матричное полиномиальное представление кодера удобно тем, что оно позволяет записать процесс кодирования в виде умножения и полиномов формальной переменной D. Предположим, что на вход кодера подается информационная последовательность . Эта последовательность может быть записана в виде полинома
(4)
Нетрудно убедиться в том, что на выходах сумматоров будут наблюдаться кодовые последовательности
(5)
Матричная запись имеет вид
(6)
Следовательно, на выходе кодера будет сформировано кодовое слово
.
В этом примере был рассмотрен код со скоростью 1/2. В случае кода со скоростью k/n схема кодера содержит k регистров сдвига. Обозначим через m максимальную длину регистра. Связи ячеек, имеющих одинаковый номер I с n выходными сумматорами, по-прежнему описываются матрицами , однако, поскольку таких ячеек теперь, размерность каждой из матриц будет равна k*n Кодер будет описан порождающим полиномом
(7)
Входная последовательность кодера будет представлена векторным полиномом
(8)
в котором подпоследовательности , имеют размерность 1*k. Кодирование представляется как умножение полиномов
(9)
Пример сверточного кода со скоростью 2/3 приведен на рисунке 8б.
Порождающая матрица сверточного кода. Из описания кодера или из формулы (9) непосредственно следует, что сверточный код является линейным. Это означает, что множество кодовых слов образует линейное пространство полубесконечных двоичных последовательностей.
Удобной формой представления блоковых линейных кодов является описание с помощью порождающей матрицы кода, строками которой, как известно, служат базисные векторы кода.
Хотя размерность пространства кодовых слов сверточного кода бесконечна, его регулярная структура позволяет в явном виде указать базис пространства и выписать порождающую матрицу сверточного кода. Рассмотрим сначала коды со скоростью 1/n .Заметим, что информационные последовательности вида
(10)
образуют в совокупности базис линейного пространства входных последовательностей кодера, поскольку любая информационная последовательность может быть представлена в виде линейной комбинации ui , Каждой линейной комбинации информационных последовательностей ui соответствует кодовая последовательность, равная линейной комбинации кодовых слов, соответствующих ui. Отсюда следует, что кодовые слова, соответствующие этим информационным последовательностям, образуют базис в пространстве кодовых слов. Из (1) следует, что порождающая матрица сверточного кода может быть записана в виде:
(11)
где через 0 обозначена нулевая матрица размерности 1*n . В случае кодов со скоростью k/n формула (1.11) для порождающей матрицы сверточного кода также верна, но размерность составляющих подматриц будет k*n .