Исследование методов поиска оптимальных сверточных и перфорированных сверточных кодов тема диссертации и автореферата по ВАК РФ 05.12.04, кандидат наук Данг Ким Нгок

• Данг Ким Нгок
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Данг Ким Нгок

СОДЕРЖАНИЕ

СПИСОК УСЛОВНЫХ СОКРАЩЕНИЙ И СИМВОЛОВ

ВВЕДЕНИЕ

ГЛАВА 1. ОБЗОР МЕТОДОВ КАНАЛЬНОГО КОДИРОВАНИЯ

1.1. Система цифровой связи

1.2. Виды канального кодирования

1.2.1. Канальный код

1.2.2. Классификация помехоустойчивых кодов

1.3. Сверточный код

1.3.1. Параметры сверточного кода

1.3.2. Способы задания сверточного кода

1.3.3. Передаточная функция

1.3.4. Катастрофический код

1.4. Перфорированный сверточный код (ПСК)

1.4.1. Параметры перфорированных сверточных кодов

1.4.2. Структура перфорированных сверточных кодов

1.4.3. Передаточная функция перфорированных сверточных кодов

1.5. Алгоритмы декодирования сверточного кода

1.5.1. Оптимальное декодирование сверточных кодов - алгоритм Витерби

1.5.2. Другие алгоритмы декодирования сверточных кодов

1.6. Граница вероятности битовой ошибки сверточных кодов

1.7. Применение сверточных кодов

Выводы к первой главе

ГЛАВА 2. КРИТЕРИИ ПОИСКА ОПТИМАЛЬНЫХ СВЕРТОЧНЫХ КОДОВ

2.1. Критерии поиска хороших сверточных кодов

2.1.1. Критерий поиска по максимальному свободному расстоянию (МСР)

2.1.2. Критерий поиска по профилю оптимального расстояния (ПОР)

2.1.3. Критерий поиска по спектру оптимального расстояния (СОР)

2.2. Сравнение эффективности сверточных кодов, выбранных по критериям МСР, ПОР и СОР

2.3. Поиск оптимальных перфорированных сверточных кодов

2.3.1. Поиск ПСК из материнских кодов, обладающих максимальным свободным расстоянием

2.3.2. Поиск ПСК из разных материнских кодов

2.3.3. Поиск совместимых по скорости ПСК

2.4. Оценка сверточных кодов по критерию СОР

Выводы ко второй главе

ГЛАВА 3. АЛГОРИТМЫ И ПРОГРАММЫ ПОИСКА ОПТИМАЛЬНЫХ СВЕРТОЧНЫХ КОДОВ И ПСК

3.1. Алгоритмы поиска оптимальных сверточных кодов и ПСК

3.2. Программы поиска оптимальных сверточных кодов по величине вероятности битовой ошибки с помощью симуляции

3.3. Программы поиска оптимальных сверточных кодов по верхней границе вероятности битовой ошибки

3.4. Программы поиска оптимальных ПСК методом машинного моделирования

3.5. База данных

3.6. Ускорение программы поиска оптимальных кодов

Выводы к третьей главе

ГЛАВА 4. РЕЗУЛЬТАТЫ ПОИСКА ОПТИМАЛЬНЫХ СВЕРТОЧНЫХ КОДОВ И ПСК

4.1. Результат поиска оптимальных сверточных кодов

4.1.1. Оптимальные сверточные коды, найденные с помощью симуляции

4.1.2. Результат поиска оптимальных сверточных кодов по верхней

границе вероятности битовой ошибки

4.2. Результат поиска оптимальных ПСК, найденных с помощью

симуляции

Выводы к четвертой главе

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ

Список условных сокращений и символов

Перечень сокращений

АБГШ Аддитивный белый гауссовский шум

ДСК Двоичный симметричный канал

ФПВ Функция плотности вероятности

MCP Максимальное свободное расстояние

ПОР Профиль оптимального расстояния

пек Перфорированный сверточный код

СОР Спектр оптимального расстояния

осш Отношение сигнал-шум

пкек Последовательный каскадный сверточный код

ARQ Автоматический запрос на повторение (Automatic Repeat request)

ATSC Комитет по перспективным телевизионным системам (Advanced Television Systems Committee standards)

DVB Стандарт цифрового телевидения (Digital Video Broadcasting)

FEC Прямое исправление ошибок (Forward Error Correction)

LTE Долгосрочное развитие (Long Term Evolution standard)

MLD Максимальное правдоподобие (Maximum Likekihood Detection)

MAP Максимальная апостериорная вероятность (Maximum A Posteriori Probability)

RCPC Совместимый по скорости перфорированный сверточный код (Rate-Compatible Punctured Convolutional Code)

VSAT Терминал с очень малой апертурой (Very Small Aperture Terminal)

UMTS Универсальная система мобильной телекоммуникации (Universal Mobile Telecommunications System)

Перечень основных символов

А Равно по определению

К Множество действительных чисел

Рь Вероятность битовой ошибки

^св Свободное расстояние кода

Еь/М0 Отношение энергии бита к спектральной плотности мощности шума

ЬуС Учитываемые слагаемые передаточной функции

И Округление числа до целого в меньшую сторону. [л] - это наибольшее целое число, меньшее или равное х.

ф Сложение по модулю два (исключающее ИЛИ - ХОК)

м Метрика Хемминга

мф Метрика Фано

Введение диссертации (часть автореферата) на тему «Исследование методов поиска оптимальных сверточных и перфорированных сверточных кодов»

ВВЕДЕНИЕ

Актуальность работы. Помехоустойчивое кодирование является очень важной функцией цифровых систем связи. Высокое качество передачи информации обеспечивается за счет коррекции ошибок, возникающих в канале связи из-за помех. Сверточные коды обладают высокой помехоустойчивостью и быстрым декодированием. Они широко используются в мобильных системах связи, в системах спутниковой связи, в цифровом телевидении DVB и т.д. Поэтому поиск оптимальных сверточных кодов является потребностью практики.

В зависимости от требуемой эффективности коррекции ошибок применяются сверточные коды с разными скоростями и кодовыми ограничениями. Существует несколько методов поиска сверточных кодов по разным критериям МСР, ПОР, СОР и вероятности битовой ошибки. Для сравнения и оценки качества сверточных кодов используется вероятность битовой ошибки. Эффективность кода тем выше, чем меньше эта вероятность. Актуальным является исследование методов поиска оптимальных сверточных и перфорированных сверточных кодов.

Методы исследования: теоретические исследования осуществлялись с использованием методов машинного моделирования алгоритмов декодирования.

Целью диссертационной работы является поиск оптимальных сверточных и перфорированных сверточных кодов, обладающих высокой помехоустойчивостью. Для достижения заявленной цели в работе решаются следующие задачи:

- анализ существующих методов поиска оптимальных сверточных и перфорированных сверточных кодов;

- построение алгоритмов и программ поиска оптимальных сверточных и перфорированных сверточных кодов;

- поиск оптимальных сверточных кодов по вероятности битовой ошибки, определяемой с помощью симуляции;

- поиск оптимальных сверточных кодов по верхней границе вероятности битовой ошибки на основе усечённой передаточной функции;

- поиск оптимальных перфорированных сверточных кодов с помощью симуляции.

Научная новизна работы заключается в следующем:

Найдены новые оптимальные сверточные и перфорированные сверточ-ные коды, обладающие высокой помехоустойчивостью. Определены диапазоны отношения сигнал/шум, в которых новые коды превосходят известные.

Практическая значимость:

1. Расширен список оптимальных сверточных и перфорированных сверточных кодов, что позволит строить цифровые системы связи, адаптируемые к условиям передачи.

2. Созданы и отлажены программы оценки эффективности производных сверточных и перфорированных сверточных кодов.

Научные положения, выносимые на защиту:

1. Оценка вероятности битовой ошибки является основным инструментом при поиске оптимальных сверточных и перфорированных сверточных кодов.

2. Верхняя граница вероятности битовой ошибки позволяет с высокой достоверностью определять помехоустойчивость сверточных кодов.

Апробация работы. Результаты работы докладывались и обсуждались на 67-69-й научных сессиях, посвященных Дню радио (СПб, 2012, 2013, 2014); на 67-й конференции профессорско-преподавательского состава СПбГЭТУ «ЛЭТИ» (СПб, 2014); на научно-технической школе-семенаре «Инфокоммуникационные технологии в цифровом мире» СПбГЭТУ «ЛЭТИ» (СПб, 2012).

Достоверность результатов исследования. Достоверность результатов диссертационной работы подтверждается применением машинного моделирования при достаточно больших объёмах выборок.

Публикации. Основные теоретические и практические результаты диссертации опубликованы в 8-ми работах, из которых 3 работы - в ведущих рецензируемых изданиях, рекомендуемых в действующем Перечне ВАК, 5 работ - в материалах научно-технических конференций.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав с выводами по каждой из них, заключения, списка литературы, включающего 51 наименование. Основная часть работы изложена на 124 страницах машинописного текста. Работа содержит 38 рисунков, 41 таблицу и приложение общим объемом 9 страниц.

Глава 1. ОБЗОР МЕТОДОВ КАНАЛЬНОГО КОДИРОВАНИЯ

Системы цифровой связи широко распространены, так как обеспечивают высокое качество передачи. Незаменимая часть любой системы цифровой связи являются канальным кодером. Цель канального кодирования состоит в противодействии помехам, которые вызывают ошибки при передаче информации в канале.

1.1. Система цифровой связи

Место канального кодирования в блок-схеме типичной системы цифровой связи [1], [4], [13], [14] показано на рисунке 1.1.

Рисунок 1.1 - Блок-схема типичной системы цифровой связи

Битовый поток от источника информации кодируется кодером, создающим последовательность, после модулятора поступает в канал. В результате воздействия шума, помех на входы демодулятора поступает искаженный кодированный битовый поток. На приемной стороне сигнал демодулируется, и данные поступают в декодер. Через корректирование, полученные данные изменяются по сравнению оригинальных данных. Отметим, что модуляция и демодуляция являются линейными и идеальными. Соединяем модуляцию,

демодуляцию и физический канал в дискретный канал. Следовательно, ошибка зависит не только от кода, метода декодирования, но и от помех. Рассмотрим модели дискретного канала, обычно используемого в исследованиях.

Дискретный канал является частным случаем более общего канала с дискретным входом и дискретным выходом. Он характеризуется входным

набором д-ичных символов ={уру2,...,у9} , выходным набором <9-ичные

символы 2={г]={гх,гг,...,гд] где j = \,2,...q, / = 1,2,...0, б>2?. Матрицей переходных вероятностей канала Р, /• = [/>,,], р., = является условной вероятностью получения Zi при условии, что передавался у,-. Такой канал называются дискретным каналом без памяти, тогда условные вероятности описываются [31]:

(1.1)

На рисунке 1.2 показан граф дискретного канала без памяти.

Рисунок 1.2 - Граф дискретного канала без памяти

Отрезок со стрелкой показывает преобразование входного символа в выходной с соответствующей условной вероятностью. Если входом является последовательность из п символов у1;,у2Я...,у„у, выбираемых из алфавита V, и

соответствующим выходом является последовательность 21],2г),...,гп1 символов из алфавита 2, то совместные условные вероятности определяются так [31]:

к=\

Модель двоичного симметричного канала (ДСК) является самой простой. Рассмотрим канал с аддитивным шумом, и пусть модулятор, демодулятор включены, как части канала. Если модулятор применяет двоичные сигналы и демодулятор делает жесткие решения, то двоичный симметричный канал характеризуется набором Г = {0,1} возможных входных символов, набором X = {0,1} выходных и набором условных вероятностей.

Матрица переходных вероятностей будет иметь вид

Рк

Л1 Рхг

\_Рг\ Рц J

(1.3)

Если канальный шум и другие нарушения вызывают независимые

ошибки с вероятностью р, тогда:

рп=рг1=Р(2 = 0\У = \) = Р{2 = \\У = 0) = р, Ри=р22=Р& = 1\Г = 1) = Р(г = 0\У = 0) = \-р.

Граф двоичного симметричного канала показан на рисунке 1.3.

1-р

(1.4)

Рисунок 1.3 - Граф двоичного симметричного канала

Модель дискретного канала особенно ДСК, очень удобна, чтобы оценить качество канального кода.

Предполагается, что

г = ¥ + Е, (1.5)

где Е = (е1,е2,ег,...,еп)~ вектор искажения, вектор ошибок, компоненты е, - независимые случайные величины.

Модель канала (1.5) используется для построения и исследования помехоустойчивых кодов. Для этой модели легко вычисляется вероятность появления в канале ошибки веса t [1], [13]:

Рь^СЛХ-рГ, (1.6)

где С'п - число сочетаний из п по

Формула (1.5) показывает, что в ДСК наиболее вероятны ошибки Е малого веса (кратности). Это свойство ДСК учитывается при построении помехоустойчивых кодов. Коды строятся так, чтобы в первую очередь обнаруживать и исправлять ошибки малой кратности. Так как ошибка, случайно совпавшая с ненулевым кодовым словом, не может быть обнаружена, то желательно, чтобы в коде было немного слов малого веса.

Для модели канала с мягким решением (8 уровней квантования), набор входных символов V = {0,1}, набор выходных символов 2 = {0,1,2,3,4,5,6,7},

соответствующих набору двоичных значений {ООО, 001, 010, 011, 100, 101, 110,111}. Тогда граф канала имеет вид, показанный на рисунке 1.4.

Эта модель мягкого решения восьмиуровневого квантования используется в разделе «Алгоритмы декодирования сверточного кода», в разделе «Граница вероятности битовой ошибки сверточных кодов» и в модели симуляции.

О

О

1

б

• 7

Рисунок 1.4 - Граф дискретного канала с мягким решением (8 уровней квантования)

1.2. Виды канального кодирования 1.2.1. Канальный код

Когда передается последовательность информации в канале с шумом, что приводит к ошибкам и потерям информации. Чтобы противодействовать этим влияниям вводится избыточность способом, который называется канальным кодированием или помехоустойчивым кодированием. Благодаря избыточности можно обнаруживать и исправлять ошибки.

Отметим, что вводим избыточность в двоичную последовательность из к бит. В этом случае информационная последовательность к бит отображается последовательностью п бит. Кодер является устройством, реализующим это отображение.

Две главных стратегии используются при декодировании. Первая стратегия является обнаружением ошибки. Этот метод решает две задачи: обнаружение ошибок или автоматический запрос на повторение (АЯС)). В случае обнаружения ошибок, декодер снабжает указание ситуации ошибок, зависимый от качества декодированной последовательности. В случае АИС), выно-

сит запрос для передатчика передать этот блок данных повторно, когда декодер обнаруживает ошибки, превышающих предел. Вторая стратегия называется прямым исправлением ошибок (РЕС). Коды, использующие метод БЕС, могут исправлять ошибки, возникающие при передаче информации. Однако этому методу нужно больше избыточность и сложнее алгоритм декодирования. Кроме того, в практике применяется метод гибрида РЕС/АШ^. Какая выборная стратегия зависит от просьбы применения сложности система. В данной работе рассматривается стратегия РЕС, чтобы оценить, найти хорошие коды и повысить эффективность при передаче информации. Рассмотрим типы помехоустойчивых кодов.

1.2.2. Классификация помехоустойчивых кодов

В теории кодирования помехоустойчивые коды разделяются на линейные и нелинейные коды (рисунок 1.5). Однако на практике нелинейные коды почти не используются, поэтому рассмотрим линейные коды. Множество слов линейного кода образует линейное подпространство, в котором линейные комбинации кодовых слов создают кодовое слово [1], [34].

Линейные коды состоят из блоковых и непрерывных или древовидных кодов [2], [3], [13], [14], [26]. В данной работе рассматриваются непрерывные коды. По структуре построения, функциональному назначению и алгоритмам кодирования и декодирования в непрерывных кодах можно выделить свер-точные, турбокоды (два параллельных каскадных сверточных кода с переме-жителем), ПКСК (два последовательных каскадных сверточных кода с пере-межителем) [2], [3], [6], [13], [14], [26]. Кроме того, сверточные коды могут быть неперфорированными и перфорированными.

Рисунок 1.5 - Классификация помехоустойчивых кодов

Кроме этой классификации помехоустойчивые коды также можно разбить на коды, исправляющие случайные или независимые ошибки, и коды, исправляющие пакеты ошибок. На практике в основном применяются коды, исправляющие случайные ошибки, поскольку для исправления пакетов ошибок часто оказывается легче использовать коды для исправления независимых ошибок вместе с устройствами перемежения и деперемежения. Первое из них осуществляет перемешивание порядка символов в закодированной последовательности перед передачей в канал, а второе - восстановление исходного порядка символов после приема. При правильном проектировании

данных устройств можно считать, что образующиеся в канале пакеты ошибок перед декодированием будут преобразованы в случайные ошибки [15].

В настоящее время известно большое число помехоустойчивых кодов, которые можно классифицировать как по конструкции, так и по задачам, для решения которых они применяются. Основной задачей, для которой применяются помехоустойчивые коды, является обеспечение требуемой достоверности связи.

При проектировании цифровых систем связи разработчики стремятся к достижению следующих целей:

- увеличению скорости передачи информации до максимально возможной;

- минимизации вероятности ошибки на бит Ръ;

- минимизации потребляемой мощности;

- минимизации ширины полосы пропускания;

- снижению сложности реализации и себестоимости системы.

Достижение всех этих целей одновременно практически невозможно,

так они являются взаимосвязанными и противоречащими друг другу. При реализации конкретной системы связи необходимо выбирать компромисс между необходимой скоростью передачи информации при заданной полосе частот, допустимой вероятностью ошибки на бит при данном соотношении сигнал/шум и приемлемой сложностью реализации системы.

Кроме этого, необходимо учитывать теоретические ограничения, которые неизбежно влекут за собой компромиссы в любых системных требованиях:

- пропускную способность канала связи, определяемую теоремой Шеннона [23];

- технологические ограничения (например, состояние современной элементной базы и комплектующих устройств).

В теории кодирования известно большое число корректирующих кодов и соответствующих им алгоритмов декодирования. Однако при попытке реализации таких кодов в каналах с высокой вероятностью ошибки часто оказывается, что сложность кодека сводит на нет преимущества высокой исправляющей способности кода. Иными словами, они не позволяют достичь достаточной близости к пределу Шеннона и имеют ряд недостатков.

Как следует из теории информации, для наилучшего приближения к пропускной способности канала необходим случайный выбор кодовых комбинаций при их достаточно большой длине. Практической целью является поиск кодов с большой эквивалентной длиной блока и структурой, допускающей приемлемую физическую реализацию декодера. Поставленным условиям во многом удовлетворяет метод каскадного кодирования, обеспечивающий необходимый компромисс между исправляющей способностью и сложностью декодера.

В следующем разделе рассматриваются сверточные коды, основные представители непрерывных кодов.

1.3. Сверточный код

1.3.1. Параметры сверточного кода

Слово сверточного кода создается при прохождении передаваемой информационной последовательности через линейный сдвигающий регистр с конечным числом разрядов. В общем случае регистр сдвига состоит из К ячеек (каждая ячейка состоит из к разрядов) и линейного преобразователя, состоящего из п вычислителей алгебраических функций (рисунок 1.6).

1-ые ячейки 2-ые ячейки ... АГ-ые ячейки

Рисунок 1.6- Сверточный кодер

Входные данные продвигаются к кодеру по к битов каждый раз. Число выходных битов для каждой к битовой входной последовательности равно п.

к

Следовательно, кодовая скорость 7? = — . Параметр К называется кодовым ог-

п

раничением сверточного кода. Обычно используются к = 1, и п = 2, п = 3,

п = 4. Тогда скорость сверточного кода Д = Л = - и Л =

2 3 4

Сверточный код задается порождающими полиномами (брС^../?,,) в

полиномиальном представлении, в двоичном представлении или в восьмеричном представлении. Например, на рисунке 1.7. представлен кодер несистематического сверточного кода с порождающей матрицей (\+X2 X+в

полиномиальном представлении или С(101,111) в двоичном представлении и С(5,1) в восьмеричном представлении. Входная информационная последовательность и = и13и2,- и выходная последовательность ^ = у1ру12>у2ру22"'>у11>у12>"" вычисляется кодером, скорость сверточного кода = 1/2, кодовое ограничение К = 3.

Рисунок 1.7 - Схема кодера сверточного кода С(5,7)

Свободное расстояние сверточного кода - с1Св одно из важного параметра сверточного кода определяется минимальным расстоянием Хемминга между двумя кодовыми словами. Свободное расстояние характеризует способность кода исправлять ошибки определенной кратности. Так, если йсв = 5, то

кратность исправляемых ошибок [14]: t<

¿сд"1

= 2. Так как сверточный код

линеен, расстояние Хемминга между двумя кодовыми словами определяется весом их суммы по модулю 2. Передаточной функции или кодовой решеткой определяется свободное расстояние, рассматриваемое в следующих разделах.

1.3.2. Способы задания сверточного кода

Способы задания сверточного кода есть способы задания линейного подпространства. Чаще всего используются порождающая матрица и графические способы задания.

Кодовое слово (выходная последовательность) кодера сверточного кода может высчитываться по формуле [1], [14]:

У = т, (1.7)

!

где (7 - порождающая матрица сверточного кода, и - информационная входная последовательность. В случае сверточного кода со скоростью 1/и порождающая матрица [14]:

G = [GvG2,...,Gn], (1.8)

где Gj - порождающий многочлен с двоичными коэффициентами gjv8j2>->EjK> К - кодовое ограничение. Элементы выходной последовательности Vy вычисляются:

vv = uigjX © wMgy2 ©...е щ_к%}к. (1.9)

В общем случае, сверточный код со скоростью k/п имеет порождающую матрицу

Gl2 • " Gln-

Ga G22 • ■■ G2„ ? (1.10)

Gtl Gk2 ■• Gkn.

где - порождающая подматрица г = 1..1,у = 1..л,

ёг}\,8цг>-'£г}К ~ значения «О» или «1». Элементы выходной последовательности уу вычисляются [14]:

© "1-182л © «,-*-282у2 © - © и!-к-к-г8\у*® ^ 11 ^

© © и,-гк8цг © -®и>-к-2к8цк-

Например, сверточный код С(5,7) имеет С =[101,111]. Тогда ^ = 101, <^2=111 или gu=\, й2=0, йз=1, Шг1= 1, &2=1> ^23 = 1 • Допустим, что входная последовательность 1010.... Тогда из (1.9) символы кодового слова

=и18и®ио812®и-18п =1 И у12 = Щ8и © Щ822 © "-1^23 =1 • Для входных 6итов м, =1010..., выходная последовательность у^ равна 11010001...

Выходная последовательность может быть вычислена по полиному. Сверточный код С(5,7) имеет С1(Х) = 1+Х2 и С2(Х) = 1+Х+Х2. Допустим, что входная последовательность и = 10100, тогда и(Х) = \+Х2. Элементы выходной последовательности У(Х) вычисляются У1(Х) = ЩХ)С1(Х) и У2(Х) = и(Х)в2(Х). Итак

F,(X) = (1 + X2)(l + X2) = 1+X4,

F2(X) = (1 + X2)(1 + X + X2) = 1+X + X3+X4 или

Vl (X) = 1 + OX + OX2 + OX3 + X4

F2(X) = 1 + X + 0X2+X3+X4.

Таким образом

F(X) = (1,1) + (0,1)X + (0,0)X2 + (0,1)X3 + (1,1)X4 V = 11 01 00 01 11. Следовательно, выходная последовательность V = 1101000111. Граф сверточного кода похож на дерево. Поэтому сверточный код называется древовидным кодом. Дерево сверточного кода С(5,7) показано на рисунке 1.8. Самый левый узел является корнем. Из этого узла есть 2 пути, соответствующие входным символом вверх «0» и вниз «1». Каждая ветвь обозначена двумя двоичными символами, соответствующими выходам кодера. Последовательность 1010...по графу кодируется в 11010001...

[с

I'

Рисунок 1.8 - Граф кода С(5,7)

Сверточный кодер, как автомат с конечным числом состояний, может быть описан диаграммой состояний. Диаграмма представляет собой направленный граф и описывает все возможные переходы кодера из одного состояния в другое. Текущее состояние и следующее состояние определяются однозначно предыдущим состоянием и текущим входным битом. Кодер из каждого состояния переходит в другое состояние при поступлении бита на его

вход. Диаграмма состояний вместе с текущими входными данными показана на рисунке 1.9. Диаграмма состояний кодера позволяет определить данные на его выходе.

1/01

Рисунок 1.9 - Диаграмма состояний

Состояниями кодера являются S^OO, ^ =10, 5*2=01 и =11. Из каждого состояния выходят два пути перехода в другое состояние, соответствующие двум возможным значениям входного бита и четырём возможным значениям выходных битов:

с 0/00 с с 1/11 ч с г. 0/10 v с ^ 1/01 v с с 0/11 v е с 1/01. г<

о0-о0 о, о2-г>2-

0/01 QI ГГ 1/10. ГТ

о3->о2, о3-

где а—",/v"v" > (3 обозначает переход из состояния а в состояние Д uf/vuv2i-соответствуют возможным значениям входного бита и, , выходные биты vy,v2, кодера.

Разверткой диаграммы состояний во времени является решетчатая диаграмма, которая была введена Форни [18]. Пример решетчатой диаграммы для кода С(5,7) показан на рисунке 1.10. Решетчатая диаграмма дает наглядное представление всех разрешенных путей, по которым может продвигаться кодер при кодировании.

Узлы диаграммы отображают состояния кодера, а ребра (или ветви), соединяющие узлы, переходы между состояниями. Кодовое слово соответствует пути по кодовой решетке и наоборот. Поэтому в дальнейшем эти терми-/ ны (слово и путь) используются как синонимы.

Построение решетки производится на основе диаграммы состояний. Если исходное состояние Б0 кодера 00, то с поступлением очередного символа 0 или 1 возможны переходы в состояния 00 или 10. Обозначение 00 или 11 ребер, соединяющих начальное состояние 00 с последующими (00 или 10), являются элементарными блоками кодового слова. Следует отметить, что через три шага очередной фрагмент решетки будет повторяться.

00

00

00

00

00

00

Б, 10

БгО!

Б3 11

Рисунок 1.10 - Решетчатая диаграмма сверточного кода

Кодовая решетка для рассматриваемого примера и путь, соответствующий входной последовательности 11001... (жирная линия), показаны на рисунке 1.10. Кодовое слово получается путем считывания обозначений ре-

бер, входящих в путь. Так, входным битам 11001... соответствует кодовое слово 1110101111...

Используя решетчатую диаграмму, можно определить свободное расстояние сверточного кода с1св как минимальное расстояние между двумя различными путями по кодовой решетке, начинающимися и заканчивающимися в нулевом состоянии,

где с1я - расстояние Хемминга между кодовыми словами V и V'.

Например, из рисунка 1.11. следует, что свободное расстояние рассматриваемого кода равно 5, так как в самый короткий путь с переходами из состояния 00 до состояния 00 (V и V'): 00->10-»01 ->00 входят ребра, соответствующие слову 110111, вес равно 5.

00 у 00 00 00 00

Рисунок 1.11- Решетчатая диаграмма сверточного кода

1.3.3. Передаточная функция

Для сверточного кода, ветви из состояния нуля, сначала входят в диаграмму состояния заканчиваются состояние нуль, устраняемую петлю в состоянии, определенные дистанционный спектр сверточного кода. Это изображение называется «весовой перечислитель» (enumerator) или передаточной функцией [47], [13]. Посмотрим подробно случай сверточного кода

С(5,7), со скоростью 1/2 и диаграммой, изображенной на рисунке 1.9. Собственные петли у узла нуля можно исключить, поскольку они ничего не вносят в дистанционные свойства кодовой последовательности относительно кодовой последовательности из одних нулей. Дальше, узел нуля расщепляется на два узла, один из них представляет вход, а другой выход диаграммы состояний. Пометим ветви на диаграмме состояний как = 1,1) или I)2, где И обозначает выходную последовательность, показатель у £> соответствует весу ветви. Тогда диаграмма состояний кодера показана на рисунке 1.12.

Обозначаем Тф) - функция весов. ЦП) также называется весовым перечислением или передаточной функцией. Используем эту диаграмму легче создать систему уравнений состояния.

Отметим, что и £ являются промежуточными множителями, изображающие веса всех ветвей из состояния входа до состояния выхода на рисунке 1.12. Тогда есть линейная система уравнений:

В

Рисунок 1.12 - Диаграмма состояний кодера С(5,7)

6 =&+Л2

(1.13)

и Г(£>) = .

(1.14)

1 0 -1 -D 1-D О -D -D 1

с \ (£)2^

Систему уравнений (1.13) можно переписать в другой форме:

£

у

О

О

v У

(1.15)

Используя правило Крамера, получим:

f л г, г~> 2 Л

det

£ =

1 О D2 -D 1-D О -D -D О

V

У _

' 1 О -Г det -D \-D О -D -D 1 , = Г>3/(1 -2D).

Подставляя (1.16) в (1.14), получим передаточную функцию:

D5

(1.16)

T(D) =

1-2 D

= D5 + 2D6 + 4D7 +... + 2* D5+k

(1.17)

Первое слагаемое в выражении (1.17) указывает на свободное расстояние dCB = 5, другие слагаемые 2, 4, 8,.... Это значит, что код С(5,7) имеет одно кодовое слово с весом 5, 2 кодовых слов с весом 6, 4 кодовых слов с весом 7... Другому слову код С(5,7) имеет один путь с расстоянием Хемминга 5 от нулевого пути, 2 пути с расстоянием 6,4 пути с расстоянием 7 и т.д.

В общем случае передаточную функцию можно представить в виде

T(D)=±adD", (1.18)

d=dr.

где «я, - число путей с расстоянием (1.

Передаточную функцию можно использовать для получения более детальной информации, чем только расстояния различных путей. Введём множитель N для всех переходов ветвей, вызванных входным битом 1. Тогда, поскольку каждая ветвь пересекается, совокупный показатель N увеличивается

на единицу только тогда, когда переход ветви обусловлен входным битом 1. Далее вводим множитель Ь для каждой ветви диаграммы состояний так, что показатель Ь будет служить счётной величиной, указывающей число ветвей для любого данного пути от узла входа к узлу выхода. Для свёрточного кода со скоростью 1/2 в нашем примере расширенная диаграмма состояний, которая объединяет суммируемые множители I и Ы, показана на рисунке 1.13.

ШЫ

Е?иV

00

00

Рисунок 1.13 - Диаграмма расширенного состояния кодера С(5,7) Из диаграммы можно написать линейную систему уравнения:

' 1 0

-вьы \-DLN 0 = 0

1 , 0 \ /

(1.19)

и Г(Д1,А0 = £>2££. (1.20)

Решаем (1.19) и заменяем (1.20). Тогда расширенная передаточная функция кода С (5,7)

Т( Д1,А0 = -

= £>5£3ЛГ + Я6!4 (1 + ¿Ж2 + (1 + Ь)2Ыг +... + + 0$+к13+к(1 + Ь)кЫм +...

(1.21)

Расширенная передаточная функция не только зависит от свободного расстояния, других дистанционных характеристик кода, но и от входных информационных весов. Поэтому расширенная передаточная функция отражает свойства сверточного кода полнее, чем передаточная функция. Основываясь на расширенной передаточной функции можно определить верхнюю границу вероятности битовой ошибки сверточного кода, которая обсуждается во второй главе.

1.3.4. Катастрофический код

Сверточный код, например С(5,7) имеет передаточную функцию (1.17), тогда и только тогда 2D< 1 или D< 1/2. Однако это не всегда правильно для всех сверточных кодов. Рассмотрим особенный пример сверточного кода С(5,6) схема кодера которого показана на рисунке 1.14, а на рисунке 1.15 -диаграмма состояний.

Рисунок 1.14 - Схема кодера сверточного кода С(5,6)

Список литературы диссертационного исследования кандидат наук Данг Ким Нгок, 2014 год

СПИСОК ЛИТЕРАТУРЫ

1. Афанасьева В. Б. Мир связи - Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. М.: 2005. 319с.

2. Берлекэмп Э. Р. Техника кодирования с исправлением ошибок. ТИИЭР. 1980. Т.68, №5, С. 24-58.

3. Блейхут. Р. Э. Теория и практика кодов, контролирующих ошибки. М.: 1986. 576с.

4. Волков JI.H., Немировский М.С., Шинаков Ю.С. Системы цифровой радиосвязи. М.: Экотрендз, 2005. 390с.

5. Данг Ким Нгок. Поиск лучших перфорированных сверточных кодов с высокими скоростями. // Изв. Вузов России. Радиоэлектроника. 2013. Вып. 4. С. 9-12.

6. Данг Ким Нгок, Нгуен Ван Нам, Нгуен Хоанг Фыонг, Смирнов В.Н. Комбинированный перемежитель для турбокода. // Изв. Вузов России. Радиоэлектроника. 2013. Вып. 1. С. 17-21.

7. Данг Ким Нгок. Оценка числа дополнительных символов при последовательном декодировании сверточных кодов. // 67-я Научно-техническая конференция, посвященная Дню радио, СПбГЭТУ «ЛЭТИ», 2012. С. 36-37.

8. Данг Ким Нгок. Анализ методов перфорирования сверточных кодов. // Научно-технической школы-семенара «Инфокоммуникационные технологии в цифровом мире», СПбГЭТУ «ЛЭТИ», 2012. С. 43-44.

9. Данг Ким Нгок. Оценка помехоустойчивости перфорированных сверточных кодов. // 68-я Научно-техническая конференция, посвященная Дню радио, СПбГЭТУ «ЛЭТИ» 2013. С. 32-33.

10. Данг Ким Нгок. Перфорирование сверточных кодов. // 67-я Научно-техническая конференция профессорско-преподавательского состава СПбГЭТУ «ЛЭТИ» 2014. С. 3-4.

11. Данг Ким Нгок. Сравнение сверточных кодов по верхней границе вероятности битовой ошибки. // 69-я Научно-техническая конференция СПб НТО РЭС, посвященная Дню радио, СПбГЭТУ «ЛЭТИ». 2014. С. 34-35.

12. Данг Ким Нгок. Исследование верхней границы вероятности битовой ошибки для поиска хороших сверточных кодов. // Изв. Вузов России. Радиоэлектроника. 2014. Вып. 1. С. 21-24.

13. Прокис Дж. Цифровая связь. М.: Радио и связь, 2000. 798с.

14. Скляр. Б. Цифровая связь - теоретические основы и практическое применение // Пер с англ. М.: 2003. 1104с.

15. Та Вьет Хунг, Разработка и оценка эффективности алгоритмов декодирования каскадных сверточных кодов // 2006.

16. 3GPP Organisational Partners, Technical Specification 3rd Generation Partnership Project; Technical Specification Group Radio Access Network; Multiplexing and channel coding (FDD) // Release 7, Mar- 2006, P. 15-16.

17. C. Berrou, A. Glavieux, and P. Thitimajshima, Near Shannon limit error correcting coding and decoding: Turbo-codes // Proc. Int. Conf. Communication, May 1993, P. 1064-1070.

18. David F. G., The Viterbi Algorithm // proceedings of the IEEE, March 1973, P. 268-277.

19. David Haccoun, Guy Begin. High rate Punctured convolutional codes for Viterbi and Sequential decoding. // IEEE Transactions on Communications, VOL. 37, No. 11 November 1989. P. 1113-1125.

20. ETR 290 European Broadcasting Union. Digital Video Broadcasting (DVB). Measurement guidelines for DVB systems. May 1997. // http://www.etsi.org/deliver/etsi_etr/200_299/290/01_60/etr_290e01p.pdf

21. ETSI 3rd Generation Partnership, Project Technical Specification LTE; Evolved Universal Terrestrial Radio Access (E-UTRA); Multiplexing and channel coding // 3GPP TS 36.212 version 10.6.0 Release 10, Jul. 2012, P. 11-12.

22. Fano R. M., A heuristic discussion of probabilistic decoding // IEEE Trans. Inform. Theory, Vol. IT-9, No.2, April 1963. P. 64-73.

23. Gallager, R. G. Information Theory and Reliable Communication //New York, 1968, 306 p.

24. Hiroshi Sasano, Sen Moriya. A construction of high rate punctured con-volutional codes //ISITA2012, Hololulu, Hawaii, USA, October 2012. // http://www.deepdyve.com/lp/institute-of-electrical-and-electronics-engineers/a-construction-of-high-rate-punctured-convolutional-codes-nTOaiOOEsL

25. Irina E. Bocharova and Boris D. Kydryashov, Rational rate punctured convolutional codes for soft-decision Viterbi decoding. // IEEE Transactions on informations theory, Vol 43, No. 4, July 1997. P. 1035-1313.

26. J. Bibb Cain, George C. Clark, and John M. Geist, Punctured Convolutional Codes of Rate (n-l)/n and Simplified Maximum Likelihood Decoding // IEEE Trans, theory, Vol. IT-25, No. 1, JAN. 1979. P 97-100.

27. Jean Conan. The weight spectra of some short low rate convolutional codes. // IEEE Transactions on communications, Vol. COM-32, No. 9, September 1984. P. 1050-1053.

28. Joachim H., Peter H. A Viterbi algorithm with soft-decision outputs and its applications // IEEE Global Telecommunications Conference Vol.3. Nov. 1989, P.1680-1686.

29. Joachim Hagenauer, Rate-Compatible Punctured Convolutional Codes (RCPC Codes) and their Applications // IEEE Transactions on communications, Vol. 36, No. 4, April 1988, P. 389-400.

30. Johannesson R. Robustly optimal rate one-half binary convolutional codes. // IEEE Transactions on informations theory, July 1975, P. 464-468.

31. John G. Proakis, Masoud Salehi, Digital Communication, fifth edition, 2007, 928p.

32. Knud J. Larsen, Short Convolutional Codes With Maximal Free Distance for Rates 1/2, 1/3, and 1/4. //IEEE Transactions on informations theory, May 1973, P. 371-372.

33. L. R. Bahl, J. Cocke, F. Jelinek, and J. Raviv, Optimal decoding of linear codes for minimizing symbol error rate // IEEE Trans. Inform. Theory Vol. 20, March 1974, P. 248-287.

34. Linear code.// http://en.wikipedia.org/wiki/Linear_code

35. Mats Cedervall, Roll Johannesson and Kamil SH. Zigangirov. A new upper bound on the first-event error probability for maximum-likelihood decoding of fixed binary convolutional codes. // IEEE Trans, on information theory, VOL. IT-30, No. 5, September 1984. P. 762-766

36. Miguel Griot, Wen-Yen Weng, Richard D. Wesel. A tighter Bhattacha-ryya bound for decoding error probability. // IEEE Communications letters, VOL. 11, No. 4, APRIL 2007, P. 1-2.

37. Nguyen Binh Minh. Nghiên curu xây dung ma xoàn theo tiêu chuân xâc suât lôi (Исследование построения сверточного кода по критерии вероятности ошибки). // Диссертация на соискание ученой степени кандидата технических наук. Университет Ле Куй Дон, Ханой 2006. // http ://luanan.nlv.gov.vn/luanan?a=cl&cl=CL 1 &sp:=TTbGGSfFQhj С

38. Odenwalder, J. P. Optimal Decoding of Convolutional codes // Ph.D. Dissertation, University of California, Los Angeles. 1970

39. Pal Frenger, Pal Orten and Tony Ottosson. Convolutional codes with Optimum Distance Spectrum //IEEE Communications letters, Vol. 3 No. 11, November 1999, P. 317-319.

40. QCVN. National technical regulation on the signal of DVB-S and DVB-S2 satellite digital television at Point of Receiver Location. 2013. BTTTT. //http://mic.gov.vn/Attach%20file/D%E1%BB%B1%20th%E1%BA%A3o%20QC VN/update%20ng%C3%A0y%2002-05-2013/QCVN-DVBS-

s2(l 0.12)_%20 V3 .doc.

41. Robert H. Morelos-Zaragoza, The art of error correcting coding // SONY Computer Science Laboratories, Inc. JAPAN, Copyright 2002 by John Wiley & Sons, Ltd, 221 p.

42. S. Benedetto, D. Divsalar, G. Montorsi, and F. Pollara, A softinput sof-toutput APP module for the iterative decoding of concatenated codes // IEEE Commun. Letter, Vol. 1 No.l, Jan. 1997, P. 22-24.

43. Shannon, C.E. A mathematical theory of communications // Bell Sys. Tech. j., vol. 27,1948, P. 379-423 and P. 623-656.

44. Shu Lin, Daniel J. Costello, Jr Error control coding: Fundamentals and applications. // Frentice-Hall series in computer applications in electrical enginering 1987, 603p.

45. Tang Hung-Hua, Lin Mao-Chao, Bartolomeu F. U. F. Minimal trellis modules and equivalent convolutional codes // IEEE Trans, on information theory, Vol. IT-52, No 8, 2006, P. 3738-3746.

46. Van de Meeberg A Tightened upper bound on the error probability of binary convolutional codes with Viterbi decoding, // IEEE Transactions on information theory, Vol. 20, May 1974, P. 389-391.

47. Viterbi A. J. Convolutional Codes and Their Performance in Communication Systems // IEEE Transactions on communications technology, Vol. Com-19, No. 5, Oct 1971, P. 751-771

48. Viterbi A. J. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm // IEEE. Trans. On Inform. Theory, Vol 13, Apr. 1967, P. 260 - 269.

49. Wozencraft and B. Reiffen, Sequential Decoding, MIT Press. Cambridge, Mass., 1961, 79p.

50. Yutaka Yasuda, Kanshiro Kashiki and Yasuo Hirata High Rate Punctured Convolutional Codes for Soft Decision Viterbi Decoding // IEEE Transactions on communications, Vol. COM-32, No 3, March 1984, P. 315-319.

51. Zhengqiang Sun, Shigetomo Kimura, Yoshihiko Ebihara. Structured properties of punctured convolutional codes and their applications. // IEICE Trans. Commun. Vol. E82-B, No. 9, September 1999, P. 1432-1438