Теоретический анализ вероятностей битовых и пакетных ошибок для сверточных кодов в рэлеевском канале связи с независимыми замираниями

Теория и техника телекоммуникаций Вестник Нижегородского университета им. Н.И. Лобачевского, 2011, № 5 (3), с. 263-269

УДК 621.391

ТЕОРЕТИЧЕСКИЙ АНАЛИЗ ВЕРОЯТНОСТЕЙ БИТОВЫХ И ПАКЕТНЫХ ОШИБОК ДЛЯ СВЕРТОЧНЫХ КОДОВ В РЭЛЕЕВСКОМ КАНАЛЕ СВЯЗИ С НЕЗАВИСИМЫМИ ЗАМИРАНИЯМИ

© 2011 г. А.А. Ломаев, А.А. Мальцев

Нижегородский госуниверситет им. Н.И. Лобачевского

artyom. lomayev@gmail .com

Поступила в редакцию 11.03.2011

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

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

Введение

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

Современные стандарты связи предусматривают широкий диапазон скоростей передачи данных, что достигается путем использования различных темпов кодирования и модуляционных созвездий. Для получения необходимых темпов кодирования применяют так называемую технику выкалывания. При этом высокие темпы кодирования достигаются путем отбрасывания части бит кодовой последовательности базового сверточного кода с низким темпом кодирования [1]. В данной работе в качестве исследуемого базового был выбран код с порождающими полиномами {133, 171}8 и темпом кодирования 1/2 [2]. В настоящее время указанный код используется в таких стандартах связи, как IEEE 802.11a Wi-Fi и IEEE 802.16 WiMAX. В качестве модуляции была рассмотрена двоичная фазовая модуляция (ДФМ).

Оптимальное декодирование сверточных кодов осуществляется с помощью алгоритма Ви-терби. Различают декодирование с «жесткими» и «мягкими» решениями. Данные схемы отличаются представлением данных, которые поступают с выхода демодулятора на вход деко-

дера. В случае схемы декодирования с «мягкими» решениями на вход декодера поступает последовательность логарифмов отношения правдоподобия (Log Likelihood Ratio). Данная последовательность вычисляется демодулятором на основе евклидового расстояния между принятым сигналом и точками сигнального созвездия. В случае схемы декодирования с «жесткими» решениями на вход декодера поступает оценка последовательности бит данных. Схема декодирования с «мягкими» решениями в полной мере использует информацию, полученную декодером, и поэтому даёт выигрыш по сравнению с «жесткой» схемой порядка 2 дБ

[2]. Следует отметить, что декодирование с «мягкими» решениями требует большой вычислительной сложности, особенно для модуляций высокого порядка. Однако существуют подходы

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

В настоящей работе выполнен теоретический анализ помехоустойчивости сверточных кодов для алгоритма декодирования Витерби с «мягкой» схемой принятия решений. Рассмотрена модель рэлеевского канала связи с независимыми замираниями. В результате проведенного анализа получены аналитические выражения зависимости вероятности битовых и пакетных ошибок от отношения сигнал/шум.

1. Постановка задачи

Модель системы. На рис. 1 представлена обобщенная модель цифровой системы связи. Рассмотрим цепочку преобразований при пере-

Рис. 1. Обобщенная схема цифровой системы передачи данных

даче информационного сообщения в такой системе. На передающей стороне информационная последовательность длиной Ь бит поступает на вход сверточного кодера с базовым темпом кодирования 1/2 и длиной кодового ограничения, равной 7. Выходная кодовая последовательность модулируется, при этом используется ДФМ.

Сигнальные точки модуляционного созвездия передаются через канал связи, который имеет рэлеевскую статистику [2]. Принятые символы для модели рэлеевского канала с независимыми замираниями представляются в следующем виде:

гЩ = Сск

где Ос^(г) - независимые комплексные коэффициенты канала, амплитуды которых имеют рэ-леевское распределение, а[г] - переданные символы модуляционного созвездия, п[г] - независимые отсчеты комплексного аддитивного белого гауссова шума с нулевым средним и дисперсией 2оп2.

На приемной стороне демодулятор с «мягкими» решениями преобразует последовательность принятых символов г[г] в последовательность «мягких» бит [3], которая в свою очередь используется декодером Витерби для отыскания оптимального пути в кодовой решетке. Оптимальным называется путь, которому соответствует наименьшее значение метрики. Метрика пути есть величина, показывающая меру близости между принятой и возможной переданной кодовой последовательностью (путем в кодовой решетке). Информационная последовательность, соответствующая оптимальному пути в кодовой решетке, принимается за оценку переданного сообщения.

2. Анализ вероятностей битовых и пакетных ошибок

Теоретические оценки вероятностей битовых и пакетных ошибок. Вычисление точных выражений для вероятностей битовых и пакетных ошибок - это весьма сложная задача даже для простейших кодов. Традиционный подход к анализу сверточных кодов основан на построении теоретических оценок помехоустойчивости [4]. В данной работе используется граница объединения, которая является асимптотически точной для высоких значений отношения сигнал/шум. Для вычисления подобных оценок необходимо исследовать дистанционный спектр кода и рассчитать вероятность выбора ошибочной последовательности с заданным весом. Вероятность выбора ошибочной последовательности зависит от типа используемой модуляции и рассматриваемой модели канала связи.

Оценка для вероятности битовых ошибок (BER - Bit Error Rate) имеет вид [4]:

BER < ^b

d =dfee

где dfree - свободное расстояние кода, b(d) -суммарный вес всех информационных последовательностей, соответствующих всем ошибочным кодовым последовательностям с весом d, P(d) - вероятность выбора ошибочной последовательности с весом d. Вероятность P(d) быстро убывает с ростом d, поэтому начиная с некоторого значения d > nd оставшимися слагаемыми в сумме (2) можно пренебречь. Значение nd зависит от отношения сигнал/шум и может быть вычислено.

темп кодирования 1/2

темп кодирования 2/3

1O

ТЗ 1O

§ 2 го 1O

O

1O

1O

е 1O 2?

§ 2 го 1O

O

1O

О a

і о

С) с )

о d) d) a( b(

і - с ^ с )  С) )

^ с о )

б б 7 В d

1O

ТЗ 1O 2?

§ 2 ГО 1O

O

1O 11 12 1З 1i

d

б темп кодирования 3/4

1O

ТЗ 1O

§ 2 го 1O

1O

О d) d) a( b(

^ с 7 С) )

с 5 -

б 7 В 9 1O d

б темп кодирования 4/5

0 a

' с ^ с ) с )

с ) )

н б б 7 d

н

н

9

в

Рис. 2. Дистанционный спектр сверточного кода

Первое предположение, которое использовалось при выводе выражения (2), заключается в следующем. В силу линейности сверточных кодов вероятность ошибки при декодировании не зависит от переданного кодового слова. Следовательно, без потери общности можно предположить, что была передана нулевая кодовая последовательность. Такой выбор упрощает анализ возникающих ошибок. Ошибочные пути - это все пути в кодовой решетке, начинающиеся и заканчивающиеся в нулевом состоянии, но отличные от нулевой кодовой последовательности. Следовательно, вес любого ошибочного пути равен числу бит, в которых отличаются ошибочная и переданная кодовые последовательности.

Второе предположение состоит в том, что вероятность выбора ошибочной последовательности не зависит от самой последовательности, а зависит лишь от ее веса. Данное предположение справедливо для модели канала, рассматриваемой в данной статье.

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

Оценка для вероятности ошибки в единицу времени имеет вид [4]:

Pe < £a

d = dJ-ee

где a(d) - число ошибочных кодовых последовательностей с весом d, P(d) - вероятность выбора ошибочной последовательности с весом d. Выражение (3) получено с использованием тех же предположений, что и оценка (2).

Для разработчиков систем связи, в которых используется пакетный режим передачи данных, наибольший интерес представляет вероятность пакетной ошибки. Будем считать, что пакет был передан с ошибкой, если хотя бы один бит информационного сообщения был изменен в процессе декодирования. Оценку для вероятности пакетной ошибки (PER - Packet Error Rate) можно выразить через вероятность ошибки в единицу времени:

PER= 1 -

где L длина - информационной последовательности.

Анализ структуры кода. Ключевую роль при анализе производительности сверточных кодов играет распределение весов ошибочных кодовых последовательностей, также называемое дистанционным спектром кода. Дистанционный спектр кода описывается набором коэффициентов {a(d), b(d)}, введенных выше. Весовое распределение для конкретного кода можно получить на основе его передаточной функции [5].

Для определения передаточной функции кода используют диаграмму состояний. Она представляет собой граф, узлы которого есть состояния, в которых может находиться сверточный кодер, а ребра отражают возможные переходы между этими состояниями. С ростом числа состояний процедура расчета дистанционного спектра должна быть реализована программно. В статьях [1, 5] проведен компьютерный анализ структуры для различных кодов с разными темпами кодирования. В результате исследования составлены таблицы значений коэффициентов {а(ё), Ь(ё)}. На рис. 2 представлен дистанционный спектр {133, 171}8 сверточного кода для скоростей кодирования 1/2, 2/3, 3/4 и 4/5.

тельность с весом ё=5, ей соответствует метрика пути Мег. Декодер Витерби сравнивает метрики М0 и Мег. Если Мег < М0, то будет выбрана ошибочная кодовая последовательность, что приведет к ошибкам в ё битах.

При передаче кодированного пакета все сиг-

Переданная кодовая последовательность

00

м„

00

00

\ Ошибочная кодовая последовательность с 11.і"'

\ весом (і = 5 \ М

• Чч • V •

01

Расчет вероятности выбора ошибочной последовательности веса d. Для построения теоретических оценок вероятностей битовых и пакетных ошибок необходимо рассчитать вероятность выбора ошибочной последовательности веса ё. Для понимания дальнейших рассуждений коротко поясним работу декодера Витерби. Принятую последовательность (1) можно представить в плоскости модуляции набором сигнальных точек, каждой из которых соответствует пара евклидовых расстояний (ёе°, ёе1) между принятой сигнальной точкой и символами ДФМ созвездия (см. рис. 3) [3]. Декодер Витерби, работающий по принципу максимального правдоподобия, выбирает такую последовательность, для которой сумма евклидовых расстояний минимальна.

На рис. 4 представлен фрагмент кодовой решетки с четырьмя состояниями. Сплошной линией изображена переданная кодовая последовательность, ей соответствует метрика пути М0, пунктиром - ошибочная кодовая последова-

• • • •

Рис. 4. Описание процесса декодирования с помощью кодовой решетки

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

Метрики М0 и Мег в случае идеальной оценки канала имеют вид [3]:

Мо = 2 гИ - векО'Кг I2,

^ 2

Мег = 2 /[/]- Оек (/'Кг 1,

г

где - переданные символы, а аег - ошибочные символы ДФМ созвездия. Определим случайную величину М как разность:

М = Мег - Мо,

тогда вероятность выбора ошибочной последовательности есть вероятность, что М < 0. Подставим (1) в (5) и проведем элементарные упрощения, тогда выражение для случайной величины М перепишется в виде: й

М = 2 век

г =1

где П [/] - независимые отсчеты комплексного аддитивного белого гауссова шума с нулевым средним и дисперсией 2а'п [/] = 2о„ /\Ос^(г)\ . Проводя дальнейшее упрощение выражения (7), получим:

й

М = 2°ек (О^п^И х

г=1

Х <АГ -аег ) + (а1г -аег )2}.

Таким образом, при фиксированных значениях коэффициентов канала Ос^(г) случайная величина М имеет гауссово распределение. Вероятность выбора ошибочной последовательности для переданного символа щг есть 0-функция [6] следующего аргумента:

Р^ (М < 0\6н) = 0

Г < м А

V стм )

СТМ = 4(а,-аег )2 а2 ^\ОсЬ (І)\2.

І=1

(М < 01^) = 6

К-аег| ^ \6н (01 2 І=1

Р(М < 0\0Л) = 0

(0\

І=1

а„

у = .

<\ 6ск (і)аіг \ 2 > 1

(І)аГ

N

Р(М < 0\6сн) = 0

2У^ \6н (І)\

где <М> - среднее значение, а оМ - дисперсия случайной величины М. Найдем ее среднее значение и дисперсию:

Для модели рэлеевского канала с независимыми замираниями полученную вероятность (14) необходимо усреднить по статистике Осн'.

Р

где Р(Осъ) - функция плотности вероятности (ФПВ) случайной величины Ос^. Для вычисления интеграла (15) удобнее перейти к переменной интегрирования х, имеющей центральное хи-квадрат распределение с 2ё степенями свободы [4] и представляющей собой сумму независимых гауссовых случайных величин с нулевыми средними и одинаковыми 2

дисперсиями ох :

Подставляя (10) в (9) и проводя элементарные преобразования, выражение для вероятности выбора ошибочной последовательности веса ё при фиксированных значениях коэффициентов канала для переданного символа а^ представим в виде:

* = Ё \°сН (І)\ 2.

І=1

ФПВ случайной величины х имеет вид [4]:

р( *)=-

1

-Xі 1 ехр

х > 0,

а2хй 2й Г(й) 1 " 7 '

где Г(ё) - гамма-функция. С учетом описанной замены интеграл (15) представляется в виде:

.

р(і) = } 0(л/2^) >

1

Из приведенного выражения видно, что вероятность выбора ошибочной последовательности не зависит от переданного символа ДФМ созвездия, поскольку |аг - аег| = 2 для любого аг Отсюда следует, что средняя вероятность ошибки имеет вид:

а2і 2і Г

Xі 1 ехр

V 2аX у

іх.

Далее перейдем к переменной интегрирования у = у[х / ах, тогда выражение (18) перепишется следующим образом:

1

Р(і) =

-.і-1

Г(і )2'

ТО

10^>Дуа хУ) У 2-1

ехр

іу.

Воспользуемся табличным интегралом для 0-функции [6]:

Исходя из рассмотренной ранее модели системы связи определим отношение сигнал/шум, предполагая, что реальная и мнимая компоненты комплексных амплитуд канала - нормированные величины:

а Ух 2п-‘еТ т I ‘к=

(п - 1)!Г

где 2Ло - спектральная плотность мощности комплексного аддитивного белого гауссова шума п[і]. Выразим дисперсию о„2 через введенное отношение сигнал/шум и подставим в (12):

^Т

к=0 I

После несложных преобразований получаем выражение для вероятности выбора ошибочной последовательности с весом ё:

2

і=1

V

У

2

І=1

і

0

X

>

X

2

X

0

0

п

X

2

к

• Экпериментапьная оценка, Р = 1/2 . Экпериментапьная оценка, Р = 2/3

• Экпериментапьная оценка, Р = 3/4 . Экспериментальная оценка, Р = 4/5 - Теоретическая оценка, Р = 1/2

. Теоретическая оценка, Р = 2/3 . Теоретическая оценка, Р = 3/4 . Теоретическая оценка, Р = 4/5

Рис. 5. Графики зависимости вероятностей битовых ошибок от отношения сигнал/шум для различных темпов кодирования

Экпериментапьная оценка, Р = 1/2 Экпериментапьная оценка, Р = 2/3 Экпериментапьная оценка, Р = 3/4 Экпериментапьная оценка, Р = 4/5 Теоретическая оценка, Р = 1/2 Теоретическая оценка, Р = 2/3 Теоретическая оценка, Р = 3/4 Теоретическая оценка, Р = 4/5

ОСШ, дБ

Рис. 6. Графики зависимости вероятностей пакетных ошибок от отношения сигнал/шум для различных темпов кодирования

р(і )=^ х

Г(і) х (1 + 2а! У)-к

к=0 ( ( 1 -

2і+кк!

-1/2\

і-к

2а! У

+1

3. Результаты численного моделирования

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

системы была реализована в среде технических вычислений МА^АВ.

Были исследованы характеристики помехоустойчивости сверточного кода с порождающими полиномами {133, 171}8 для модели рэле-евского канала с независимыми замираниями. При передаче кодированных сообщений использовалась ДФМ, длина передаваемых пакетов была выбрана равной 1000 байт. При моделировании производилось идеальное оценивание коэффициентов канала.

На рис. 5 и 6 представлены экспериментальные кривые и теоретические оценки зависимости вероятности битовых и пакетных ошибок от отношения сигнал/шум, выраженного в децибе-

1

лах. Указанные кривые построены для темпов кодирования R = 1/2, 2/3, 3/4, 4/5.

Оценка для вероятности битовых ошибок, представленная в виде границы объединения (2), асимптотически сходится с экспериментальной кривой начиная со значений вероятностей ошибок порядка 10-2. Оценка для вероятности пакетных ошибок прогнозируется с высокой точностью во всем диапазоне ОСШ, поскольку считается, что пакет был передан с ошибкой, если хотя бы один бит информационного сообщения был изменен в процессе декодирования. При этом не имеет значения, сколько бит информационного сообщения оказались ошибочными. Отметим, что кривые, показывающие зависимость вероятностей ошибок от отношения сигнал/шум для модели рэлеевского канала с независимыми замираниями, имеют разный наклон для разных темпов кодирования. Подобное поведение обусловлено тем, что вероятность ошибки представляется степенной функцией отношения сигнал/шум, а показатель степени есть свободное расстояние кода. Свободное расстояние кода убывает с ростом темпа кодирования, что приводит к изменению наклона кривых.

Заключение

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

Список литературы

1. Begin G., Haccoun D., Paquin C. // Proc. IEEE transaction on communications. Nov. 1990. Vol. 38. Р. 1922-1928.

2. Скляр Б. Цифровая связь. М.: Издательский дом «Вильямс», 2003.

3. Tosato F. and Bisaglia P. // Proc. IEEE Transaction on Communications. Apr. 2002. Vol. 2. Р. 664-668.

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

5. Conan J. // Proc. IEEE Transaction on Communications. Sep. 1984. Vol. 32. Р. 1050-1053.

6. Verdu S. Multiuser detection. Cambridge University Press, New York, 1998.

THEORETICAL ANALYSIS OF BIT AND PACKET ERROR PROBABILITIES FOR CONVOLUTIONAL CODES OVER MEMORYLESS RAYLEIGH FADING CHANNEL

A.A. Lomayev, A.A. Maltsev

Theoretical analysis of the bit and packet error probabilities for convolutional codes has been carried out. The model of memoryless Rayleigh-fading channel has been considered. The analytical equations for the bit and packet error probabilities for binary phase shift keying modulation have been obtained.

Keywords: convolutional codes, Rayleigh fading channel, bit error rate, bit error probability, packet error probability, binary phase shift keying modulation.