Содержание к диссертации
Введение
ГЛАВА 1. Обзор методов канального кодирования 10
1.1. Система цифровой связи 10
1.2. Виды канального кодирования 14
1.2.1. Канальный код 14
1.2.2. Классификация помехоустойчивых кодов 15
1.3. Сверточный код 18
1.3.1. Параметры сверточного кода 18
1.3.2. Способы задания сверточного кода 20
1.3.3. Передаточная функция 26
1.3.4. Катастрофический код 30
1.4. Перфорированный сверточный код (ПСК) 31
1.4.1. Параметры перфорированных сверточных кодов 33
1.4.2. Структура перфорированных сверточных кодов 36
1.4.3. Передаточная функция перфорированных сверточных кодов 42
1.5. Алгоритмы декодирования сверточного кода 42
1.5.1. Оптимальное декодирование сверточных кодов - алгоритм Витерби 43
1.5.2. Другие алгоритмы декодирования сверточных кодов 46
1.6. Граница вероятности битовой ошибки сверточных кодов 50
1.7. Применение сверточных кодов 52
Выводы к первой главе 53
ГЛАВА 2. Критерии поиска оптимальных сверточных кодов 54
2.1. Критерии поиска хороших сверточных кодов 54
2.1.1. Критерий поиска по максимальному свободному расстоянию (МСР) 54
2.1.2. Критерий поиска по профилю оптимального расстояния (ПОР) 57
2.1.3. Критерий поиска по спектру оптимального расстояния (СОР) 59
2.2. Сравнение эффективности сверточных кодов, выбранных по критериям МСР, ПОР и СОР 65
2.3. Поиск оптимальных перфорированных сверточных кодов 70
2.3.1. Поиск ПСК из материнских кодов, обладающих максимальным свободным расстоянием 71
2.3.2. Поиск ПСК из разных материнских кодов 74
2.3.3. Поиск совместимых по скорости ПСК 76
2.4. Оценка сверточных кодов по критерию СОР 77
Выводы ко второй главе 82
ГЛАВА 3. Алгоритмы и программы поиска оптимальных сверточных кодов и ПСК 83
3.1. Алгоритмы поиска оптимальных сверточных кодов и ПСК 83
3.2. Программы поиска оптимальных сверточных кодов по величине вероятности битовой ошибки с помощью симуляции 85
3.3. Программы поиска оптимальных сверточных кодов по верхней границе вероятности битовой ошибки 86
3.4. Программы поиска оптимальных ПСК методом машинного моделирования 87
3.5. База данных 88
3.6. Ускорение программы поиска оптимальных кодов 90
Выводы к третьей главе 92
ГЛАВА 4. Результаты поиска оптимальных сверточных кодов и ПСК 93
4.1. Результат поиска оптимальных сверточных кодов 93
4.1.1. Оптимальные сверточные коды, найденные с помощью симуляции 93
4.1.2. Результат поиска оптимальных сверточных кодов по верхней границе вероятности битовой ошибки 96
4.2. Результат поиска оптимальных ПСК, найденных с помощью симуляции 100
Выводы к четвертой главе 107
Заключение 108
Список литературы 110
- Классификация помехоустойчивых кодов
- Критерий поиска по максимальному свободному расстоянию (МСР)
- Программы поиска оптимальных сверточных кодов по величине вероятности битовой ошибки с помощью симуляции
- Результат поиска оптимальных сверточных кодов по верхней границе вероятности битовой ошибки
Классификация помехоустойчивых кодов
Когда передается последовательность информации в канале с шумом, что приводит к ошибкам и потерям информации. Чтобы противодействовать этим влияниям вводится избыточность способом, который называется канальным кодированием или помехоустойчивым кодированием. Благодаря избыточности можно обнаруживать и исправлять ошибки.
Отметим, что вводим избыточность в двоичную последовательность из k бит. В этом случае информационная последовательность k бит отображается последовательностью n бит. Кодер является устройством, реализующим это отображение.
Две главных стратегии используются при декодировании. Первая стратегия является обнаружением ошибки. Этот метод решает две задачи: обнаружение ошибок или автоматический запрос на повторение (ARQ). В случае обнаружения ошибок, декодер снабжает указание ситуации ошибок, зависимый от качества декодированной последовательности. В случае ARQ, выносит запрос для передатчика передать этот блок данных повторно, когда декодер обнаруживает ошибки, превышающих предел. Вторая стратегия называется прямым исправлением ошибок (FEC). Коды, использующие метод FEC, могут исправлять ошибки, возникающие при передаче информации. Однако этому методу нужно больше избыточность и сложнее алгоритм декодирования. Кроме того, в практике применяется метод гибрида FEC/ARQ. Какая выборная стратегия зависит от просьбы применения сложности система. В данной работе рассматривается стратегия FEC, чтобы оценить, найти хорошие коды и повысить эффективность при передаче информаций. Рассмотрим типы помехоустойчивых кодов.
В теории кодирования помехоустойчивые коды разделяются на линейные и нелинейные коды (рисунок 1.5). Однако на практике нелинейные коды почти не используются, поэтому рассмотрим линейные коды. Множество слов линейного кода образует линейное подпространство, в котором линейные комбинации кодовых слов создают кодовое слово [1], [34].
Линейные коды состоят из блоковых и непрерывных или древовидных кодов [2], [3], [13], [14], [26]. В данной работе рассматриваются непрерывные коды. По структуре построения, функциональному назначению и алгоритмам кодирования и декодирования в непрерывных кодах можно выделить свер-точные, турбокоды (два параллельных каскадных сверточных кода с переме-жителем), ПКСК (два последовательных каскадных сверточных кода с пере-межителем) [2], [3], [6], [13], [14], [26]. Кроме того, сверточные коды могут быть неперфорированными и перфорированными. Рисунок 1.5 - Классификация помехоустойчивых кодов
Кроме этой классификации помехоустойчивые коды также можно разбить на коды, исправляющие случайные или независимые ошибки, и коды, исправляющие пакеты ошибок. На практике в основном применяются коды, исправляющие случайные ошибки, поскольку для исправления пакетов ошибок часто оказывается легче использовать коды для исправления независимых ошибок вместе с устройствами перемежения и деперемежения. Первое из них осуществляет перемешивание порядка символов в закодированной последовательности перед передачей в канал, а второе - восстановление исходного порядка символов после приема. При правильном проектировании данных устройств можно считать, что образующиеся в канале пакеты ошибок перед декодированием будут преобразованы в случайные ошибки [15].
В настоящее время известно большое число помехоустойчивых кодов, которые можно классифицировать как по конструкции, так и по задачам, для решения которых они применяются. Основной задачей, для которой применяются помехоустойчивые коды, является обеспечение требуемой достоверности связи.
При проектировании цифровых систем связи разработчики стремятся к достижению следующих целей: - увеличению скорости передачи информации до максимально возможной; - минимизации вероятности ошибки на бит Pb ; - минимизации потребляемой мощности; - минимизации ширины полосы пропускания; - снижению сложности реализации и себестоимости системы.
Достижение всех этих целей одновременно практически невозможно, так они являются взаимосвязанными и противоречащими друг другу. При реализации конкретной системы связи необходимо выбирать компромисс между необходимой скоростью передачи информации при заданной полосе частот, допустимой вероятностью ошибки на бит при данном соотношении сигнал/шум и приемлемой сложностью реализации системы.
Кроме этого, необходимо учитывать теоретические ограничения, которые неизбежно влекут за собой компромиссы в любых системных требованиях: - пропускную способность канала связи, определяемую теоремой Шен нона [23]; - технологические ограничения (например, состояние современной элементной базы и комплектующих устройств). В теории кодирования известно большое число корректирующих кодов и соответствующих им алгоритмов декодирования. Однако при попытке реализации таких кодов в каналах с высокой вероятностью ошибки часто оказывается, что сложность кодека сводит на нет преимущества высокой исправляющей способности кода. Иными словами, они не позволяют достичь достаточной близости к пределу Шеннона и имеют ряд недостатков.
Как следует из теории информации, для наилучшего приближения к пропускной способности канала необходим случайный выбор кодовых комбинаций при их достаточно большой длине. Практической целью является поиск кодов с большой эквивалентной длиной блока и структурой, допускающей приемлемую физическую реализацию декодера. Поставленным условиям во многом удовлетворяет метод каскадного кодирования, обеспечивающий необходимый компромисс между исправляющей способностью и сложностью декодера.
Критерий поиска по максимальному свободному расстоянию (МСР)
Передаточная функция перфорированного сверточного кода имеет вид [25], [19], аналогичный формуле (1.18) для сверточного кода: СО T(D) = adDd , (1.27) d=dCB где dCB - свободное расстояние кода; d - расстояние Хемминга рассматриваемого пути от нулевого пути; ad - число путей с расстоянием d от нулевого пути; D - выходная последовательность.
Исследование передаточной и расширенной передаточной функции перфорированных сверточных кодов позволяет оценить эффективность кода. Алгоритмы декодирования сверточного кода Существуют три основных семейства алгоритмов декодирования сверточных кодов: последовательный алгоритм, алгоритм Витерби и алгоритм максимальной апостериорной вероятности (MAP) [13], [14].
В 1961 Возенкрафт (Wozencraft) и Рейффен (Reiffen) описали первый практический алгоритм декодирования сверточных кодов [49]. Алгоритм основывался на последовательном декодировании. Этот алгоритм является субоптимальным [7]. Несколько других алгоритмов были разработаны в работах Возенкрафта и Рейффена. В 1963 году Фано (Fano) ввел метрику Фано [22]. Метрика Фано стала типичной метрикой пути в последовательном декодировании. Первоначально метрика Фано использовалась в его последовательном алгоритме декодирования на кодовом дереве [22]. В 1965 Зигангиро-вым (Zigangirov) был предложен стек алгоритм, который ищет в кодовое дерево кодовые слова. В 1967 Витерби описал алгоритм декодирования, который носит его имя [48]. Вскоре Форни (Forney) доказал, что алгоритм Витерби - алгоритм максимального правдоподобия декодирования для сверточных кодов [18]. В 1989 г. Йоахим X. и Петр X. (Joachim Hagenauer и Peter Hoeher) [28] предложили модифицированный алгоритм Витерби с целью получения апостериорной вероятности на выходе, соответствующей каждому переходу состояний. Этот алгоритм известен как алгоритм Витерби с мягким выходом (алгоритм SOVA) и разработан для повышения достоверности вычисления апостериорной вероятности [28].
В 1973 Баль (Bahl) и другие [33] предложил алгоритм декодирования по максимальной апостериорной вероятности - MAP. По сравнению с Витер-би MAP обеспечивает маленькую вероятность битовой ошибки. Эти небольшие различия в производительности требуют примерно удвоения сложности алгоритма Витерби, делая MAP непривлекательным для практического декодирования сверточных кодов. Однако декодирование MAP крайне важно для декодирования турбокодов итерационной процедурой, чтобы вычислять априорные вероятности. Применения декодирования MAP к турбокодам, рассмотрены Берроу и Бенедетто в статьях [17], [42].
Рассмотрим самый эффективный алгоритм декодирования сверточных кодов - алгоритм Витерби. Оптимальное декодирование сверточных кодов - алгоритм Витер-би
Рассмотрим декодирование по методу максимального правдоподобия. Если все входные последовательности равновероятны, то минимальная вероятность ошибки получается при поиске максимальной условной вероятности. Условные вероятности называют функциями правдоподобия P(Z V), где Z это принятая кодовая последовательность, V - одна из возможных передан 44 ных последовательностей, V - последовательность, удовлетворяющая уравнению принципа максимального правдоподобия (1.28) [14], [15], [41] P(Z\V) = max P(Z\V). (1.28) по всем V Это формализация способа принятия решений, основанного на здравом смысле, когда имеются статистические данные о вероятностях. При рассмотрении двоичной демодуляции, предполагается передача только двух равновероятных сигналов sx(t), s2(t). Следовательно, принятие двоичного решения на основе принципа максимального правдоподобия, касающееся данного полученного сигнала, означает, что в качестве переданного сигнала выбирается sx(t), если p(z\s1(t)) p(z\s2(t)) .
Таким образом, применение принципа максимального правдоподобия при декодировании бит данных, закодированных сверточным кодом, осуществляется в контексте выбора наиболее вероятной последовательности, как показано в уравнении (1.28). Обычно имеется множество возможных переданных последовательностей двоичных символов. Что касается двоичного кода, то последовательность из L двоичных символов является членом набора из 2L возможных последовательностей. Следовательно, в контексте максимального правдоподобия можно сказать, что в качестве переданной последовательности выбирается V, если правдоподобие p(z\V) больше правдоподобия всех остальных возможно переданных последовательностей. Такой оптимальный декодер, минимизирующий вероятность ошибки (когда все переданные последовательности равновероятны), известен как декодер, работающий по принципу максимального правдоподобия.
Предположим, что канал без памяти - аддитивный белый гауссовский шум с нулевым средним, т.е. шум влияет на каждый символ кода независимо от остальных символов. При скорости кодирования сверточного кода равной 1/п, правдоподобие можно выразить следующим образом [14]:
Программы поиска оптимальных сверточных кодов по величине вероятности битовой ошибки с помощью симуляции
Проведенные расчеты показали что, критерий СОР преобладает других критерии. Кроме, того можем сравнить коды по вероятности битовой ошибки, полученной симуляцией. Рассмотрим сравнивание вероятности битовой ошибки кода С(1167,1545) по критерию МСР и кода С(1151,1753) по критерию СОР с ограничением К = 10; кода С(2335,3661) по критерию МСР и кода С(3345,3613) по критерию СОР с ограничением К = 11 (рисунок 2.3).
Сравнение вероятности битовой ошибки сверточных кодов по критериям МСР и СОР, полученной симуляцией На рисунке 2.4 приведены зависимости вероятности битовой ошибки кода С(51,71), оптимального по критерию ПОР, кода С(53,75) по критерию СОР сГ = б, и также кодовС(121,161) иС(133,171) с К = 7.
Сравнение вероятности битовой ошибки сверточных кодов по критериям ПОР и СОР, полученной симуляцией Сравнения этих зависимостей показывает, что коды удовлетворяющие критерию СОР являются лучшими среди рассматриваемых. Поиск оптимальных перфорированных сверточных кодов
Критерий СОР, как показано в разделе 2.2, является одним из лучших критериев для оценки сверточных кодов. Поэтому этот критерий используем для поиска перфорированных сверточных кодов.
Известно, что самый хороший материнский сверточный код не всегда создает лучшие перфорированные коды с разными скоростями [26],[5]. Следовательно, на практике поиск оптимальных перфорированных сверточных кодов ведется по трем направлениям: поиск перфорированных сверточных кодов с высокими скоростями из материнских кодов, имеющих максимальное свободное расстояние [50], поиск перфорированных сверточных кодов с высокими скоростями из разных материнских кодов [24] и поиск совместимых по скорости перфорированных сверточных кодов (RCPC) [29].
ПСК с высокими скоростями R создаются из одного материнского сверточного кода. Они широко применяются в разных системах, например DVB, VSAT, UMTS…
Рассмотрим ПСК, создающиеся из одного материнского сверточного кода со скоростью 1/2, как показано на рисунке 1.16. Оценка и выбор хороших ПСК основывается на dCB , cd и с d границы вероятности битовой ошибки где dCB - свободное расстояние кода; d - расстояние Хемминга рассматриваемого пути от нулевого пути; cd - число весовой ошибки для путей с расстоянием d; I - объм блока входных данных соответствующий вектору перфорирования В; Рк - вероятность выбора ошибочного пути при декодировании Ви терби. Результат поиска ПСК показан в таблицах 2.15, 2.16 по критерию СОР.
Чтобы подтвердить результат верхней границы используется вычисление вероятности битовой ошибки симуляцией для кодов C(51,77), C(53,75) в рисунке 2.6. В диапазоне отношения 4дБ Еь /N0 5,5 дБ код C(51,77) лучше, чем код C(53,75). Итак, критерий СОР пропускает хороший код.
Видно, что при отношении Eb/N0 7,65 дБ значения верхней границы кода С(2153,3705) всегда меньше значения границы кода С(3345,3613). А при отношении Eb/N0 7,65 дБ код С(3345,3613) обладает меньшими значениями вероятности битовой ошибки. Полученные зависимости для кодов С(2153,3705) и С(3345,3613) приведены на рисунке 2.7. Рисунок 2.7 - Сравнение вероятности битовой ошибки сверточных кодов С(2153,3705) и С(3345,3613), полученных симуляцией
Итак, с помощью вычисления верхней границы можно найти хорошие коды с кодовыми ограничениями К = 6, К = 11 из множества всех возможных кодов. Существуют два хороших кода С(51,77), С(53,75) с кодовым ограничением К = 6 и С(2153,3705), С(3345,3613) с кодовым ограничением к = 11.
На практике сверточные коды и ПСК используются в диапазоне отношений Еь/No при заданной достоверности декодирования (вероятности Рь). Например, критерий цифрового телевидения DVB - Вьетнамский стандарт цифровой телевидения DVB требует обеспечить вероятность декодирования Рь 2х10-\ а стандарт DVB - S2 Pb 2x10 7 [40]. Для европейского стандарта DVB требуется вероятность битовой ошибки Рь от 10"3 до 10"7 [20].
Следовательно, необходимо продолжить поиск кодов, удовлетворяющих требованиям практики. В этой диссертации рассмотрим метод поиска хороших сверточных кодов по границе вероятности битовой ошибки. Хорошие коды обладают малой вероятностью битовой ошибки.
Известно, что вычисление вероятности битовой ошибки требует больших временных затрат. Поэтому обычно вычисление вероятности битовой ошибки используется для оценки эффективности кодов. Однако с помощью алгоритмы реализованы в программном пакете MATLAB, специализированном симулированном программном продукте SIMULINK и особенно нового поколения компьютеров, которые позволяет провести поиск хороших свер-точных кодов быстро и эффективно.
Результат поиска оптимальных сверточных кодов по верхней границе вероятности битовой ошибки
Поиск оптимальных сверточных кодов производится в диапазоне вероятности битовой ошибки Ръ от 10-4 до 10-7, в котором должна работать цифровая информационная система, например DVB. Для поиска используется сканирование всего множества, включающего М сверточных кодов. Критерием оценки кодов является вероятность битовой ошибки декодирования Ви-терби с мягким решением. Чтобы повысить достоверность оценки, используется объм выборки 5.4х1010 до 5.4х1012 бит (см. приложение). Результаты поиска оптимальных сверточных кодов со скоростью 1/2 и 1/3, ограничением К показаны в таблице 4.1 и таблице 4.2.
Проведенные эксперименты подтвердили оптимальность ранее найденных кодов, например С(5,7), С(15,17), С(5,7,7) и др. Кроме того, машинное моделирование позволило найти новые сверточные коды, обеспечивающую меньшую вероятность битовой ошибки, чем известные. Определены диапазоны Е/Щ, в которых найденные коды эффективнее известных. Например, код С(51,77) с ограничением К = 6 или код С(225,367) с ограничением 1 = 8 и скоростью 1/2. Эти коды является лучшими при вероятности битовой ошибки в диапазоне 104… 10 7.
Для более детального сравнения построены зависимости вероятности битовой ошибки от отношения Eb/N0. На рисунке 4.1 для кодов со скоростью 1/2 и ограничением К= 8 и К = 9, а на рисунке 4.2 для кодов со скоростью 1/3 и ограничением К = 5 и К = 6. Из этих зависимостей видно, что найденные сверточные коды С(27,31,35), С(43,55,75), С(225,367), С(523,731) имеют выигрыш около 0.15 дБ по сравнению с известными. Рисунок 4.1 - Сравнение эффективности найденных кодов и известных кодов со скоростью 1/2, К = 8 и К = Рисунок 4.2 - Сравнение эффективности найденных кодов и известных кодов со скоростью 1/3, К = 5 и К = 6 4.1.2. Результат поиска оптимальных сверточных кодов по верхней границе вероятности битовой ошибки
Программа поиска оптимальных сверточных кодов реализуется вычислением и сравнением верхних границ вероятностей битовой ошибки возможных сверточных кодов определенного множества M. Это множество включает сочетания порождающих полиномов с ограничением K.
Результаты поиска оптимальных сверточных кодов по верхней вероятности битовой ошибки показаны в таблице 4.3 для скорости 1/2. Некоторые из найденных кодов совпадают с известными кодами, оптимальными по критериям МСР, ПОР, СОР [39], что подобные таблицы оптимальных сверточ-ных кодов со скоростями 1/3, 1/4 приведены в приложении диссертации.
Из полученных результатов следует, что при Eb/N0 6,9 дБ и скорости 1/2 верхняя граница вероятности битовой ошибки сверточного кода С(51,77) ниже верхней границы кода С(53,75), а при Eb/N0 6,9 дБ верхняя граница кода С(51,77) выше верхней границы кода С(53,75). Следовательно, при ко 97 довом ограничении К = 6 существуют два хороших сверточных кода с близкими характеристиками [12]. Аналогичные выводы справедливы для других скоростей и кодовых ограничений.
Сравним эффективности найденных и известных сверточных кодов. Общепринято сравнивать сверточные коды по вероятности битовой ошибки. Эффективность кода тем больше, чем меньше вероятность битовой ошибки рь.
Результаты сравнения и оценки кодов С(51,77) С(53,75) с ограничением К = 6 показаны на рисунках 2.5 и 2.6 [11], [12]. Кроме того, сравнивание эффективности сверточных кодов с известными кодами (выделенные серым фоном) приведены в таблице 4.4 для ограничений К = 9,10 и скорости 1/2. Аналогично в таблицах 4.5 и 4.6 показана эффективность сверточных кодов со скоростью 1/3 и 1/4.
Результаты поиска оптимальных сверточных кодов по верхней границе вероятности битовой ошибки совпадают с результатами поиска с помощью симуляции. Однако диапазон отношения Eb/N0 шире и охватывает все диапазоны отношения Eb/N0, важные для практики.
Обычно для перфорирования выбираются материнские сверточные коды с хорошими характеристиками по критерию максимального свободного расстояния или по критерию оптимального расстояния спектра [5]. Следовательно, исследуются ПСК, полученные из хороших материнских кодов и близких к ним.
Видно, что при ограничениях К = 3,4,5,8,9 найденные материнские коды С(5,7), С(15,17), С(23,35), С(247,371) и С(561,753) известны [50], несколько векторов перфорирования совпадают известным (в сером фоне). А с ограничениями К = 6 и К = 7 материнские коды С(51,73) и С(133,175) со скоростью 1/2 превосходят в создании хороших перфорированных кодов. Рассмотрим сравнение этих ПСК и известных ПСК С(53,75) С(133,171) (в сером фоне) в таблицах 4.9 - 4.12. Материнские коды С(53,75) С(133,171) являются лучшими по СОР.
Установлены диапазоны изменения отношения Eb/N0, в которых помехоустойчивость найденных кодов выше помехоустойчивости известных. Так, код С(27,31,35) имеет выигрыш в помехоустойчивости около 0,15 дБ по сравнению с известным кодом С(25,33,37).
Поиск оптимальных перфорированных сверточных кодов проведен для двух случаев: перфорированию подвергается один материнский код и в зависимости от требуемой скорости кода перфорируются разные материн ские коды.
В общих случаях найдены новые оптимальные ПСК. Так, при перфорировании найденного материнского кода С(51,73) для скоростей от 2/3 до 7/8 вероятность битовой ошибки меньше, чем при перфорировании известного кода С(53,75). Для кодового ограничения К = 5 и скоростей то 2/3 до 7/8 оптимальные сверточные коды получаются перфорированием разных материнских кодов С(23,35),С(25,31),С(31,33).
