Содержание к диссертации
Введение
1. Классификация алгоритмов декодирования двоичных сверточных кодов . 11
1.1. Алгебраические методы 25
1.1.1 Методы порогового декодирования с использованием обратной связи 25
1.1.2. Дефинитное декодирование 27
1.2. Вероятностные методы декодирования 29
1.2.1 Методы последовательного декодирования 30
1.2.1.1. Алгоритм Фано 30
1.2.1.2 Стек алгоритм 33
1.2.1.3 Крипер алгоритм 34
1.2.1.4 Адаптивные алгоритмы 34
1.3. Параллельные методы декодирования 35
1.3.1. Алгоритм Витерби 3 5
1.4. Гибридных методы 37
2. Адаптивный алгоритм декодирования двоичных сверточных кодов . 39
2.1. Алгоритм Фано 40
2.1.1. Цена пути 41
2.1.2. Определение порогов 44
2.1.3. Работа алгоритма Фано 44
2.2. Адаптивный алгоритм последовательного декодирования двоичных сверточных кодов 47
2.2.1. Верхняя граница необнаруживаемой ошибки декодирования 52
2.2.2. Критерий прямого перехода 55
2.2.3. Критерий обратного перехода 56
2.2.4. Синхронизация декодера 72
3. Расчет помехоустойчивости систем передачи информации использующих двоичные сверточные коды 82
3.1. Аналитические методы 85
3.2. Статистические методы (методы статистических испытаний) 85
3.3. Детерминированная имитационная модель 90
4. Имитационное моделирование системы передачи информации . 101
4.1. Методика детерминированного исследования помехоустойчивости алгоритмов последовательного декодирования сверточных кодов 101
4.2. Статистический метод исследования помехоустойчивости алгоритмов последовательного декодирования сверточных кодов . 104
4.3. Экспериментальное исследование адаптивного алгоритма последовательного декодирования сверточных кодов 109
4.3.1 .Выбор сверточного кода 109
4.3.2. Основные параметры адаптивного алгоритма последовательного декодирования при проведении экспериментального исследования 109
4.3.3. Программная реализация предложенной модели 110
4.3.4. Определение быстродействия адаптивного алгоритма декодирования сверточного кода 111
4.3.5. Результаты моделирования и их оценка 113
Заключение 120
Литература 124 Приложения 134
- Вероятностные методы декодирования
- Адаптивный алгоритм последовательного декодирования двоичных сверточных кодов
- Детерминированная имитационная модель
- Статистический метод исследования помехоустойчивости алгоритмов последовательного декодирования сверточных кодов
Введение к работе
Настоящая работа посвящена исследованию и разработке алгоритмов декодирования двоичных свёрточных кодов, а также методик оценки помехоустойчивости систем связи использующих двоичные свёрточные коды.
Всеобщий переход к цифровым системам передачи информации, широкое распространение цифрового телевидения и радиовещания, проекты глобальных спутниковых систем передачи информации обосновывают применение двоичных свёрточных кодов, обладающих высокими корректирующими способностями.
Свёрточные коды получили широкое распространение во многих радиосистемах передачи информации, таких как системы спутниковой и сотовой связи, системы цифрового телевидения и радиовещания (в том числе и спутниковые), системы радиосвязи с подвижными объектами и другие системы, основной особенностью которых является работа в каналах связи с низкими энергетическими характеристиками и энергетическими характеристиками, непостоянными во времени.
Проблема декодирования свёрточных кодов является одним из важнейших направлений современных научных исследований, поскольку от её решения, при прочих равных условиях, зависит достоверность передачи информации, что особенно актуально в системах передачи информации без использования обратного канала. Большое многообразие систем передачи информации использующих свёрточные коды, ставит вопрос о разработке методик сравнительной оценки их помехоустойчивости, максимально полно отражающих корректирующую способность системы.
Проектирование современных систем передачи информации с использованием однопроцессорной архитектуры ведет к дефициту машинного времени, снижение которого представляет собой отдельную, весьма актуальную проблему.
Целью работы является исследование и разработка алгоритмов декодирования двоичных сверточных кодов, обладающих меньшей вычислительной сложностью и адаптирующихся к изменению помеховой обстановки в канале связи, а также новых, более точных, методик оценки помехоустойчивости систем передачи информации использующих двоичные свёрточные коды.
В настоящей работе в результате проведенного анализа современного состояния исследований посвященных вопросам декодирования сверточных кодов, предложена новая, единая классификация алгоритмов декодирования сверточных кодов. Данная классификация дает возможность объективного анализа существующих алгоритмов и выбора наиболее эффективного способа декодирования сверточного кода при построении конкретной системы передачи информации. Разработанная классификация методов декодирования сверточных кодов имеет методическую ценность в преподавании специальных дисциплин по направлениям радиотехника и телекоммуникации.
Проведенный обзор и разработанная классификация методов декодирования сверточных кодов позволяют сделать вывод о том, что наиболее интересными для исследования являются методы адаптивного декодирования сверточных кодов.
Предложен адаптивный алгоритм декодирования сверточных кодов. Адаптивный алгоритм основан на модификации кодовой решетки и позволяет проводить интерпретацию двух и более кодовых кадров в качестве одного нового модифицированного кодового кадра увеличенного размера, обрабатывая который, декодер получает оценку сразу двух и более информационных символов. Данный подход позволяет осуществить снижение количества вычислительных операций, затрачиваемых на декодирование, а следовательно и времени получения оценки кодового символа, с незначительным ухудшением помехоустойчивости декодера.
Получена оценка верхней границы изменения вероятности появления не обнаруживаемой ошибки декодирования, при обработке кодового кадра увеличенной длинны.
В результате анализа базового алгоритма Фано разработаны критерии прямого и обратного перехода, позволяющие осуществлять изменение активной кодовой решетки адаптивного алгоритма декодирования на основании анализа поведения декодера. Исследована процедура самосинхронизации последовательного декодера, позволяющая осуществлять синхронизацию декодирующего устройства без использования дополнительного выделения пропускной способности канала связи.
Предложена детерминированная методика оценки помехоустойчивости системы связи путем получения основной характеристики системы связи -вероятности необнаруживаемой ошибки декодирования.
Основной особенностью методики является получение оценки за относительно короткое время и конечное число операций. За счет предложенного способа формирования тестовых последовательностей исследуются полная группа внутренних состояний кодера, в сочетании с полным перебором ошибок различной кратности, возникающих в канале связи.
Проведено экспериментальное исследование адаптивного алгоритма
декодирования сверточного кода. Для проведения эксперимента, с целью
подтверждения достоверности полученных в настоящей работе результатов,
разработаны алгоритмы и программное обеспечение, позволяющее
производить компьютерное моделирование адаптивного алгоритма
декодирования сверточного кода, а также расчет помехоустойчивости
системы передачи информации использующих сверточные коды, как с
использованием предложенной детерминированной методики, так и
статистическим методом. Получены результаты, подтверждающие
эффективность адаптивного алгоритма декодирования сверточного кода и
адекватность детерминированной методики исследования
8 помехоустойчивости систем связи использующих двоичные сверточные коды.
Научная новизна диссертационной работы состоит в следующем:
Проведен сравнительный анализ и разработана классификация алгоритмов декодирования двоичных свёрточных кодов.
Разработан новый адаптивный алгоритм декодирования двоичных свёрточных кодов.
Предложена методика оценки помехоустойчивости систем связи использующих двоичные сверточные коды.
Практическая ценность диссертационной работы заключается в том, что:
Разработан высокоэффективный адаптивный алгоритм последовательного декодирования двоичных свёрточных кодов.
Исследована процедура самосинхронизации последовательного декодера, основанная на анализе поведения алгоритма последовательного декодирования, позволяющая осуществлять синхронизацию декодирующего устройства без использования дополнительного выделения пропускной способности канала связи.
Разработана детерминированная методика исследования помехоустойчивости системы передачи информации использующей сверточные коды, инвариантная к методу декодирования сверточного кода, позволяющая исследовать полную группу внутренних состояний кодера, в сочетании с полным перебором ошибок различной кратности возникающих в канале связи.
Разработана модель и алгоритм детерминированной методики исследования помехоустойчивости систем передачи информации использующих двоичные сверточные коды.
Показано, что детерминированная методика исследования помехоустойчивости дает более высокую оценку исправляющей способности свёрточных кодов, по сравнению со статистическим методом исследования помехоустойчивости, при аналогичных моделях ошибок в канале связи.
Показано, что при применении адаптивного алгоритма декодирования двоичного свёрточного кода, при проигрыше в помехоустойчивости ~ на 0.1 дБ., количество операций, затрачиваемых на декодирование, уменьшается приблизительно в два раза, что позволяет перераспределять освободившееся машинное время на решение других задач.
Разработаны методики экспериментального исследования помехоустойчивости систем передачи информации использующих двоичные сверточные коды с применением предложенной детерминированной методики и статистического метода.
На защиту выносятся следующие положения:
Классификация методов декодирования двоичных свёрточных кодов;
Адаптивный алгоритм последовательного декодирования двоичных свёрточных кодов позволяющий при незначительном снижении помехоустойчивости существенно уменьшить число вычислительных операций затрачиваемых на декодирование.
Методика исследования помехоустойчивости систем передачи информации использующих двоичные сверточные коды, позволяющая исследовать полную группу внутренних состояний
10 кодера, в сочетании с полной группой ошибок произошедших в канале связи.
Вероятностные методы декодирования
Обладают более высокой сложностью, но по многим характеристикам превосходят алгебраические методы. Общий смысл вероятностного декодирования заключается в том, что на приемной стороне производится восстановление пути пройденной по кодовой решетке кодером, что позволяет достичь существенно меньшей вероятности ошибки декодирования, чем в алгебраических методах. К вероятностным методам декодирования относятся: последовательные и параллельные методы декодирования свёрточных кодов. были предложены Возенкрафтом [17], еще за некоторое время до появления методов порогового декодирования. К методам последовательного декодирования можно отнести: алгоритм Фано, стек алгоритм, крипер алгоритм, а также адаптивные алгоритмы декодирования свёрточных кодов., предложенный Р. Фано (1963) [18], как и любой последовательный алгоритм, по своей сути, является методом проб и ошибок. Работа данного алгоритма может быть представлена в виде набора определенных групп операций и сводится к сравнению полученного из канала набора кодовых символов (кодового кадра - г7), на выходе канала, с кодовыми кадрами соответствующим двум {v0(S0)f v}(So)) или более возможными путям на кодовой решетке, для текущего состояния декодера (Рис.11).
В результате сравнения декодер вычисляет расстояние между принятым кадром и кадрами, соответствующим исходящим ребрам текущего состояния кодовой решетки в метрике Хемминга - кодовое расстояние. Полученное кодовое расстояние ложится в основы определения цены исследуемого пути. Далее выполняются операции вычисления текущего значения порога, записи в память исследованных ребер, сравнение значения цены пути с текущим значением порога и выбор, в зависимости от результата сравнения, наиболее вероятного пути. Так продолжается до тех пор, пока уровень помех в канале не приведет к возникновению такой ошибки (группы ошибок), после которой декодер будет следовать по неверному пути. Через некоторое количество шагов, произойдет уменьшение значения цены пути ниже значения текущего порога, и данный факт будет расценен декодером как возникновение ошибки, в каком либо предыдущем узле.
Следующим принципиальным набором операций, являются операции, связанные с возвратом декодера в предыдущий узел, где производится исследование альтернативных путей, с возможным изменением текущего значения порога. Данные действия производятся до тех пор, пока декодер не выйдет на истинный путь кодовой решетки, по которому двигалось кодирующее устройство.
Достоинством алгоритма Фано, является работа декодера в реальном масштабе времени, в условиях низкого уровня помех в канале связи. При возрастании уровня помех, происходит увеличение времени затрачиваемого на декодирование одного символа (возникновение задержки декодирования), связанное с необходимостью возврата декодера к ранее не исследованным узлам. Увеличение времени, как и количества возвратов декодера, носит случайный характер и может привести к переполнению буфера декодера. Указанный алгоритм, как правило, является основой для построения адаптивных алгоритмов.
На рисунке 12 [19] показаны сравнительные характеристики алгоритма Витерби, для кодов с относительной скоростью R=l/2, и различными длинами кодовых ограничений, а также сравнительные характеристики алгоритма Витерби и алгоритма Фано (штрихпунктирная линия) для одинаковых длин кодовых ограничений и относительной скорости R. Кривая оценки помехоустойчивости алгоритма Фано получена в результате работы статистической модели, описанной в четвёртой главе настоящей работы. Из сравнительного анализа видно, что алгоритм Фано, в условиях низкого соотношения сигнал шум, при оптимальном подборе параметров алгоритма, может иметь характеристику помехоустойчивости, превосходящую аналогичную характеристику алгоритма Витерби.
На рисунке 13 [20] показаны сравнительные характеристики практически реализуемого алгоритма параллельного декодирования, при жесткой схеме принятия решения, и алгоритмов последовательного декодирования использующих значительную длину кодового ограничения. Низкие отношения сигнал шум в канале связи, определяют использование кодов, обладающих значительными длинами кодовых ограничений, при этом использование алгоритмов последовательного декодирования, становится одним из основных направлений повышения помехоустойчивости системы передачи информации, поскольку реализация параллельного декодера становится практически неприемлемой. . Зигангировым [21] и Джелинеком [22], независимо друг от друга, был предложен алгоритм последовательного декодирования, получивший название стек-алгоритм.
Рассматриваемый алгоритм использует метрику максимального правдоподобия, однако, с другой стороны, для любого алгоритма, не требующего для принятия решения исследования каждого возможного пути, а осуществляющего выбор среди путей различной длинны, использование указанной метрики приводит к появлению смещения, которое играет существенную роль для оптимизации алгоритма.
Алгоритм основан на стеке, образуемом путями переменной длинны, упорядоченными в порядки убываний значений их кодового расстояния [10]. На каждом шаге алгоритма, производится замена пути, находящегося на вершине стека, на новые пути, образуемые путём прибавления к существующему пути 2Ь новых ребер, располагаемых также в порядке убывания значений их кодовых расстояний. В случае если один из образованных новых путей совпадает с путём, присутствующим в стеке, путь
Адаптивный алгоритм последовательного декодирования двоичных сверточных кодов
Для полного понимания работы предложенного адаптивного алгоритма, рассмотрим основную идею [30, 31, 32] на примере сверточного (3,1,2) кода показанного на рисунке 18.
Изучая решетчатые диаграммы сверточных кодов, можно придти к выводу, что «хорошие» свёрточные коды построены таким образом, что обладают особой структурой распределения кодовых символов по исходящим ребрам кодовой решетки. Так для кодов имеющих скорость 1/п характерно максимальное расстояние Хемминга, для ветвей, исходящих из любого узла кодовой решетки. На рисунке 3 можно четко увидеть эту особенность. Например, из состояния S0 исходят две ветви, имеющие различия во всех трех разрядах присвоенных им кодовых символов (001 и 110), т.е. обладающие максимальным расстоянием Хемминга. Описанная закономерность характерна для всех узлов предложенной кодовой решетки.
На рисунке 19 показана решетчатая диаграмма сверточного кода для декодирования двух кадров кодовой последовательности.
Рассмотрим возможные пути следования декодера сверточного кода по кодовой решетке при обработке двух переданных кадров кодовой последовательности. Пусть начальное состояние декодера соответствует состоянию So. Из данного состояния возможен переход в состояния S0 И S2, а из указанных состояний в состояния So и S2, а также в S] и S3 соответственно. Таким образом, возможны следующие пути из состояния SQ: SQ, SO; SO, S2; S2, SI; S2, S3 и соответствующие им последовательности информационных символов: 11; 10; 01; 00 (рис.20.).
Рассматривая только начальное состояние и конечные состояния, становится очевидным, что из текущего состояния So, при обработке двух кодовых кадров, возможны переходы в любое из существующих состояний кодовой решетки, т.е. в состояния So, Si, S2, S3. (рис.21).Рис.21. Пути перехода декодера из начального состояния при обработке двухкадров кодовой последовательности.
Любому показанному на рис.21 переходу могут быть сопоставлены соответствующие информационные и кодовые символы, представляющие собой объединения информационных и кодовых символов соответствующие ребрам кодовой решетки при обработке одного кадра входной последовательности.
Используя показанный выше принцип, заполним модифицированную таблицу переходов (таблица 1) и построим модифицированную решетчатую диаграмму (рис.22) декодера сверточного кода.Уровнем кодовой решетки ( lr ) будем называть совокупность всех состояний кодовой решетки, находящихся на расстоянии 1Г - ребер от некоторого состояния, принятого за исходное.
Модифицированной кодовой решеткой будем называть кодовую решетку, двоичного сверточного кода, полученную путем исследования всех возможных путей из каждого состояния одного уровня, на глубину двух или более уровней, и заменой этих путей новыми путями, количество которых соответствует глубине проведенного исследования. Каждому ребру модифицированной кодовой решетке соответствует объединение информационных и кодовых символов входящих в них исследуемых ребер.
Очевидно, что для любой кодовой решетки двоичного сверточного кода (b, n, М), может быть получена модифицированная кодовая решетка путём исследования всех возможных путей исходящих из каждого состояния одного уровня на глубину двух или более уровней, поскольку, согласно определению, любое из состояний кодовой решетки содержит 2 исходящих и 2Ь входящих ребра. Модификация кодовой решетки позволяет проводить интерпретацию двух и более кодовых кадров в качестве одного нового модифицированного кадра, увеличенного размера, обрабатывая который, декодер получает оценку сразу двух и более информационных символов.Оценим изменение вероятности появления не обнаруживаемой ошибки в декодере, при обработке кодового кадра увеличенной длинны.
Рассмотрим исходящие ребра из каждого состояния сравниваемых кодовых решеток (не модифицированной - А и модифицированной - А ), как несовершенные двоичные блоковые коды A = [as,a2,...,aSi} и A = fa,a 2,...,a s ) спараметрами {bA,nA) и {bA.,nA.) соответственно (рис.23).Для множества кодов, принадлежащих сравниваемым кодовым решеткам, определим вектора минимальных кодовых расстояний в метрике
Детерминированная имитационная модель
Предлагаемая детерминированная имитационная модель системы передачи информации [31,46] (рис.40) позволяет в равных условиях, за конечное число операций, произвести сравнение систем передачи информации, основывающихся на использовании сверточного кода, путем получения основной характеристики системы передачи информации - вероятности не обнаруживаемой ошибки декодирования.
С целью получения адекватной имитационной модели, необходимо использовать входную информационную последовательность, равновероятно описывающую, все возможные внутренние состояния кодера. Использование сверточных кодов, в отличие от блоковых, накладывает определенные ограничения, в выборе данной последовательности, поскольку кодер сверточного кода обладает внутренней памятью. Очевидно, организация напрямую метода полного перебора состояний кодера, применяемого при имитационном моделировании кодеров блоковых кодов, не представляется возможным. по порождающим многочленам сформируем граф сверточного кода, представленный в виде таблиц переходов и выходов.
Алгоритм формирование таблиц переходов и выходов, показан на рис.41Результатом работы алгоритма, является формирование графа состояний сверточного кода, описанного в виде таблиц переходов и выходов.
Поиск информационной последовательности, обеспечивающей последовательное исследование всех внутренних состояний кодера (задача поиска Гамильтонова цикла), является решением задачи поиска пути на графе, описывающем внутренние состояния рабочего регистра сверточного кодера, однократно проходящего, через все возможные состояния. При этом начало и конец пути совпадают и эквивалентны исходному состоянию кодера.
Для построения предложенного пути, осуществим поиск Гамильтонова цикла в графе кодера, описанного в виде автомата Мура.
Гамильтоновым циклом связанного ориентированного графа кодера G(v,s) [47-51] называют цикл, т. е. замкнутый путь, содержащий все вершины графа, которые, кроме начальной Vo и конечной v„ взаимно различны.
До настоящего времени, какого либо простого критерия или алгебраического метода, позволяющий ответить на вопрос о существовании Гамильтонова цикла в произвольном графе, найдено не было. Существующие критерии являются слишком общими, имеют чисто теоретический интерес и зачастую непригодны для произвольных графов, встречающихся на практике.
Существуют три основных метода поиска Гамильтонова цикла(ов) в графах: алгебраический, метод Робертса и Флореса (перебор с возвратами) и мультицепной метод. Алгебраический метод приемлем только для графов количество вершин в которых не превышает несколько десятков, при этом на вычисления уходит значительный объем времени и памяти. Из представленных методов, для большинства кодов, целесообразно применять метод Робертса и Флореса, т.к. он не предъявляет чрезмерных требований к памяти компьютера. Время поиска в алгоритме увеличивается экспоненциально в зависимости от числа вершин в графе. Наилучшие временные характеристики имеет мультицепнои метод. Учитывая относительную сложность алгоритма реализующего мультицепнои метод, а также то, что вычисление Гамильтонова цикла в имитационной модели производится только один раз, практическая реализация мультицепного метода не оправдана.
Рассмотрим метод Робертса и Флореса. В отличие от алгебраических методов, с помощью которых пытаются найти сразу все Гамильтоновы циклы и при реализации которых приходится хранить в памяти все цепи, которые могут оказаться частями таких циклов, метод перебора имеет дело с одной цепью, непрерывно уточняемой вплоть до момента, когда, либо получается Гамильтонов цикл, либо станет очевидным невозможность осуществления поиска. В этом случае производится модификация цепи некоторым систематическим способом (гарантирующем, что, за конечное число шагов, будут исчерпаны все возможности), после чего продолжается поиск Гамильтонова цикла. В этом способе для поиска требуется очень небольшой объем памяти и за один раз находится один гамильтонов цикл.Построим (кхп)-матрицу М=[ту], где элемент ту есть і-я вершина (допустим xq), для которой в графе G(X,r) существует дуга (xj,xq). Вершины хчна множестве T(Xj) можно упорядочить произвольно, образовав элементы j-го столбца матрицы М. Число строк к матрицы М будет равно наибольшей полустепени исхода вершины.Метод состоит в следующем (рис.42). Выберем некоторую начальную вершину (например, Хі) в качестве отправной образующей первый элемент
Статистический метод исследования помехоустойчивости алгоритмов последовательного декодирования сверточных кодов
В основе статистического метода исследования систем передачи информации лежит модель, показанная на рис. 39. Для показанной модели разработан алгоритм представленный на рис. 44.
В блоке генерации информационного символа производится генерация входного информационного символа декодера. Данный символ кодируется кодером в соответствующий ему кодовый кадр с помощью блока генерации кодового кадра. Генерация информационного символа должна производиться таким образом, чтобы обеспечить равновероятность формирования путей по кодовой решетке свёрточного кода.
Блок генерации ошибки, служит для реализации необходимого закона распределения ошибок в канале связи. В настоящей работе блок генерации ошибок моделирует двоично-симметричный канал связи с аддитивным белым Гауссовским шумом. В блоке формируется последовательность псевдослучайных чисел распределенных по Нормальному закону (закону Гаусса) стандартная функция распределение которого имеет вид:отклонении о = 1.
Псевдослучайная последовательность преобразуется впоследовательность случайных событий, распределенных по Нормальному закону. Если элемент псевдослучайной последовательности с принадлежит интервалу (х,+ х ), считается, что случайное событие Y эквивалентное возникновению ошибки в канале связи (рис. 45) произошло, т.е.:
Рис.45. Генерация случайного события, распределенного по нормальномузакону.Величина х определяется в зависимости от используемой системы сигналов в конкретной системе передачи информации. В предложенной модели используются противоположные сигналы, для которых вероятность перехода определяется соотношением: где h- отношение сигнал шум в канале связи, таким образом:Выразив отношение сигнал шум Я в децибелах, получим:
Определение случайного события производится для каждого кодового символа сформированного кодового кадра.
В блоке декодирования производится декодирование кодового кадра, и получение соответствующего ему состояния на кодовой решетке сверточного кода. В случае удачного декодирования формируется следующий кодовый кадр и процесс повторяется. При неудачном декодировании, т.е. при обнаружении ошибки, производится инкремент счётчика ошибок, и декодер приводится в исходное состояние.
При достижении числа испытаний еАекоА (заданного количества ошибокдекодирования) установленной величины, рассчитывается вероятность ошибки на бит:где Кисп - общее количество декодированных кодовых символов (переданных по каналу связи бит) за еЛекЫ) испытаний.
Произведя расчет вероятности не обнаруживаемой ошибки декодирования, производится изменение отношения сигнал шум с заданным шагом, инициализация декодера, и описанный выше процесс повторяется до тех пор, пока не будет набрана статистика для всего спектра отношений сигнал шум.
Статистический метод исследования помехоустойчивости сверточных кодов является классическим методом исследования помехоустойчивости, однако обладает следующими основными недостатками: неопределенностью количества испытаний необходимого для накопления статистики, неопределенностью общего времени испытаний, особенно при высоком соотношении сигнал шум в канале связи, невозможностью однозначного
