Вероятность ошибки при декодировании по алгоритму Витерби жёстких решений

 

Рассмотрим качество алгоритма Витерби декодирования СК в двоичном симметричном канале. При этом полагаем жёсткие решения детектора и метрики Хемминга, которые определяют расстояния между принимаемой последовательностью и 2 ^{k ( K -1)} выжившими последовательностями в каждом узле решётки.

Пусть передается последовательность пути из одних нулей.

Начнем с расчета вероятности первого парного ошибочного события выбора нулевого пути, заключающегося в том, что в некотором узле «a» путь, который сравнивается с путём из одних нулей, имеет расстояние d относительно нулевого пути.

При d нечётном нулевой путь будет выбран без ошибок, если число ошибок в принимаемой последовательности меньше, чем (d +1)/2; в противном случае будет выбран другой неправильный путь. Следовательно, вероятность выбора неправильного пути из указанной выше пары равна

                         (3.64)

где р — вероятность ошибочного приема символа в двоичном симметричном канале.

При d чётном неправильный путь выбирается, когда число ошибок превышает d /2. Если число ошибок равно d /2, то имеется связь между метриками двух путей, которую можно разрешить случайным выбором одного из путей. При этом ошибка возникнет в половине случаев. Следовательно, вероятность выбора неправильного пути равна

  (3.65)

Ранее отмечалось, что имеется много возможных путей с различными расстояниями d, которые сливаются в данном узле с путём из одних нулей.

Следовательно, вероятность (3.65) первого парного ошибочного события не является точной. Однако, можно определить верхнюю границу вероятности путем суммирования парных ошибок Р₂(d) по всем возможным путям, которые сливаются в данном узле с путём из одних нулей.

Таким образом, получим объединенную верхнюю границу для вероятности ошибки декодирования СК по алгоритму Витерби:

                             (3.66)

где { a_d } – коэффициенты, представляющие число путей, соответствующих набору расстояний { d }. Эти коэффициенты являются коэффициентами (3.55) в выражении (3.54) передаточной функции T (D) или T (D, N,J).

    Известны оптимальные СК, имеющие наибольшее d _св при заданных скорости кода (k / n) и кодовом ограничении К, которые даются в таблицах. В них даны d _св и порождающие полиномы g генераторов СК, например, в таблице 3.4 при k =1, n =2 [3], по которым можно построить структуру сверточного кодера.

 

Таблица 3.4. Максимальное расстояние d_св кодов со скоростью 1/2

Кодовое			Порождающие	полиномы	dсв	Верхняя граница
ограничение К			в восьмеричной записи ззаписи)			dсв
	3		5	7	5	5
	4		15	17	6	6
	5		23	35	7	8
	6		53	75	8	8
	7		133	171	10	10
	8		247	371	10	11
	9		561	753	12	12
	10		1.167	1.545	12	13
	11		2.335	3.661	14	14
	12		4.335	5.723	15	15
	13		10.533	17.661	16	16
	14		21.675	27.123	16	17

 

Пример. Построить схему кодера оптимального СК со скоростью 1 /n =1/2 согласно таблице 3.4 при кодовом ограничении кода К =4 и порождающих полиномах в восьмеричной записи g₁ =15₈ , g₂ =17₈ .

Решение.

Переводим g_i  в двоичную форму: g₁ =15₈ =001.101, g₂ =17₈=001.111.

При К =4 берем 4 ячейки РС, два сумматора (n =2) с подключением к ячейкам РС согласно дв. коду g_i (0 -нет подключения), рис.3.21.

                                          g₁                                                                 

                                                                                                            

 

 

   вход

 

                                                   g₂

 

Рис. 3.21. Свёрточный кодер со скоростью 1/2 (К = 4, k = 1, n = 2 ).

Задачи к разделу 3

1. Составить таблицы сложения и умножения для элементов поля GF(7).

 

2. Линейный блоковый (n. k) код Хемминга (7,4) задан порождающей матрицей кодера в систематической форме:

                      

Входное информационное слово кодера =[х _{m 1} , х _{m 2} , х _{m 3} , х _{m 4} ].

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

 

3. Линейный двоичный блоковый (n, k) код (7,3) задан порождающей матрицей кодера:

,

   а входное кодовое слово информационной последовательности              =[101]. Привести к систематической форме.

а) Показать, что выходное кодовое слово принадлежит множеству разрешенных выходных слов кодера.

б) Построить проверочную матрицу расширенного (n +1, k) кода и порождающую матрицу укороченного (n -1, k -1) кода, найти d_min  для всех кодов и сравнить.

 

4. Кодер ЦК задан порождающим полиномом g (p) = p ³ + p ² +1.

Построить порождающую, проверочную матрицы и вычислить значение синдрома декодирования ЦК для входного слова декодера [101 1 011] с ошибкой в четвертой позиции. Результат сравнить с синдромом табл.3.3.

 

5.  Циклический код (7,4) задан порождающим полиномом

g (p) = p ³ + p ² +1.

а) Построить схему кодера и найти порождающую и проверочную матрицы.

б) Найти порождающую матрицу в систематической форме кода (7,3), дуального коду (7,4), по полиному h (p)=(p +1) ∙(p ³ + p ² +1) и сравнить ее с проверочной матрицей кода (7.4), сделать выводы. Найти d_min для кода (7,3) и кратность исправления ошибок.

 

6. Двоичный ЦК Хемминга (15,11) задан порождающим полиномом

g (p)= = p ⁴ + p +1.

а) Построить структуру кодера, порождающую и проверочную матрицы в систематической форме.

б) Построить: порождающую матрицу кода (15,4), дуального коду (15,11); порождающую матрицу укороченного кода (8,4), полученного из кода (15,11) и найти d_min.

 

7. При передаче в направлении «ПО-БС» используется помехоустойчивый ЦК:

а) код Хемминга (7,4);

б) код т -последовательности, т =5;

в) код БЧХ (n =15, k =5, t =3);

г) код Голея (23,12)

и ортогональный в усиленном смысле сигнал ОФМ. На БС реализуется разнесенный прием при АБГШ на М=2 антенн с алгоритмом комбинирования сигналов ветвей разнесения:

д) экстремального автовыбора ветви;

е) когерентного сложением сигналов ветвей по Бреннану.

Замирания огибающей сигнала в ветвях независимые общие:

ж) по закону Релея;

и) по закону Накагами.

Найти значение средней вероятности ошибки декодирования кодового слова при среднем по общим замираниям значении ОСШ=10 (по мощности) и автокорреляционном приеме результирующего сигнала ОФМ. Вариант задачи определяется персонально, например, вариант: [а)-е)-ж)].

 

8. При передаче в направлении «ПО-БС» используется помехоустойчивый ЦК:

а) код Хемминга (7,4);

б) код т -последовательности, т =5;

в) код БЧХ (n =15, k =5, t =3);

г) код Голея (23,12)

и ортогональный в усиленном смысле сигнал ОФМ. На БС реализуется разнесенный прием при АБГШ на М=2 антенн с алгоритмом комбинирования сигналов ветвей разнесения:

д) экстремального автовыбора ветви;

е) когерентного сложением сигналов ветвей по Бреннану.

Замирания огибающей сигнала в ветвях независимые общие:

ж) по закону Релея;

и) по закону Накагами.

Найти значение среднего по общим замираниям ОСШ (по мощности), необходимое для декодирования кодового слова с вероятностью ошибки 10^-2 при автокорреляционном приеме результирующего сигнала ОФМ. Вариант задачи задается персонально, например, вариант: [а)-е)-ж)].

 

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

K =5 и скоростью 1/2 согласно табл.3.4 по порождающим полиномам в восьмеричной записи g ₁ = 23₈,   g ₂ = 35₈.

 

10. Вероятность поражения канала связи станционной помехой P_СП=0,2. В присутствии помех приёма нет. При отсутствии помех вероятность поэлементного приёма p _ЧТ=0,005. Число элементов равно 100. Допускается 1% ошибок в телеграмме. Определить вероятность приёма телеграммы при однократной, двукратной и трёхкратной передаче с разнесением по времени или частоте.

 

11. Детектором жестких решений формируется на входе декодера принимаемая последовательность бит { 110 101 101 } CК со скоростью 1/3 (K =3, k =1, n =3), который имеет решетчатую диаграмму (рис. 3.20) с двумя сливающимися и выходящими ветвями для каждого узла. Детектор МП вычисляет для каждого узла метрики двух путей, например, путей с тремя ветвями, начинающихся в узле «а» и заканчивающихся после трех тактов в узле «а». Обозначим: i =0 путь из одних нулей, i =1 – второй путь, а p ≤0,5 – вероятность ошибки приема бита. Найти путь, выбранный декодером МП в качестве выжившего. Сравнить полученное решение с решением, принимаемым по минимуму расстояния Хемминга.

 

12. Передаточная функция CК со скоростью 1/3 (K =3, k =1, n =3) равна:

Т(D) = D ⁶ +2 D ⁸ +4 D ¹⁰ +8 D ¹² + …=,

где, число путей с расстоянием Хемминга d равно

a_d =;

На вход декодера СК поступают жесткие решения принимаемой последовательности СК. Найти верхнюю границу вероятности ошибки декодирования СК, учитывая только пути с расстоянием Хемминга d =6 и d =8, при вероятности ошибки приема символа p =0,1.

 

13. Определить вероятность ошибки приема элемента сигнала ЧТ со скоростью 500 бод в канале АБГШ, если при скорости 50 бод вероятность ошибки Р_ош=0,01. Что необходимо сделать, чтобы значение Р_ош=0,01 оставалось неизменным.

 

14. Найти вероятность приема сообщения из 10 знаков пятиэлементного безизбыточного кода, если элементы независимы и вероятность ошибки приема элемента Р_ош=0,01.

 

Заключение

В пособии даны теоретические сведения, необходимые для решения задач анализа, синтеза оптимальных алгоритмов и практической реализации приёмных устройств по разделам курса «Основы теории систем связи с подвижными объектами», посвященным:

- изучению вопросов синтеза оптимальных алгоритмов демодуляции и детектирования ФМ и  ЧМ радиосигналов;

- знакомству с основами построения и практической реализацией схем тактовой и высокочастотной синхронизации в когерентных приёмниках ФМ-ЧМ сигналов;

- изучению методов и средств разнесённого приёма сигналов;

- изучения основ помехоустойчивого кодирования, в том числе, и практической реализации кодеров и декодеров циклических и свёрточных кодов. 

Как показала практика использования первой части учебного пособия в учебном процессе кафедры «Средства связи и информационная безопасность» ОмГТУ, приведенные примеры синтеза систем оптимального приема широкополосных сигналов на фоне помех способствуют хорошему усвоению материала студентами как очной, так и заочной форм обучения. Большинство приведенных примеров взято из области синтеза реальных сигналов и устройств. При написании второй части учебного пособия авторы использовали такие же принципы и подходы изложения материала.

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

Библиографический список

 

1. Галкин В.А. Цифровая мобильная радиосвязь / В.А. Галкин–М.: Горячая линия - Телеком, 2007. –432с.

2. Майстренко В.А. Статистические методы приема и обработки сигналов в системах радиосвязи. Руководство к решению задач / В.А. Майстренко, В.Ф. Попов. – Учебное пособие. – Омск: издательство ОМГТУ, 2008–102с.

3. Прокис, Дж. Цифровая связь / Пер. с англ. под ред. Д.Д. Кловского. – М.: Радио и связь, 2000. –797с.

4. Рыжков А.В. Синтезаторы частот в технике радиосвязи /А.В. Рыжков, В.Н. Попов. – М.: Радио и связь, 1991. –265с.

5. Феер, К. Беспроводная цифровая связь / Пер. с англ. под ред. В.И. Журавлева. – М.: Радио и связь, 2000. –520с.

6. Маковеева М.М. Системы связи с подвижными объектами / М.М. Маковеева, Ю.С. Шинаков – М.: Радио и связь, 2002. –440с.

7. Коржик В.И. Расчет помехоустойчивости систем передачи дискретных сообщений / В.И. Коржик, Л.М. Финк, К.Н. Щелкунов – М.: Радио и связь, 1981. –232с.

8. Уильям К.Ли. Техника подвижных систем связи / Пер. с англ. под ред. И. М. Пышкина. – М.: Радио и связь, 1985. –392с.

9. Ionospheric Souder Operation/ http://www/tcibr/com.

10. Лавор А.Н. Адаптивный обнаружитель зондирующего ВЧ сигнала с линейно-частотной модуляцией /А.Н. Лавор, И.Г. Наливайко, В.Ф. Попов. Техника радиосвязи, вып.9, 2004. –15с.

11. Попов В.Ф. Эффективность двух алгоритмов радиолинии с частотной адаптацией / В.Ф. Попов. Техника радиосвязи, серия ТСС, вып.10, 1983. – 8с.

12. Попов В.Ф. Эффективность одного алгоритма выбора рабочих частот в радиолинии с частотно-временными сигналами / В.Ф. Попов. Техника средств связи, серия ТРС, вып.10,1984. –9с.

 

 

Приложение 1

Законы распределений

 Таблица 1.1

 

№	Закон распределения	Случайная величина и область её изменения	Аналитическое выражение закона распределения	Определяющие параметры	График закона распределения	Характеристическая функция q1(u)
1	Биномиальный (Бернулли)	k = 0, 1, 2,…n		n, p		[1+p(eju - 1)]n
2	Пуассона	k = 0, 1, 2,…		l

112

 

№	Закон   распре- деления	Область значений случайной величины	Аналитическое выражение плотности вероятности W1 (x)	Опреде- ляющиепара-метры	График плотности вероятности	Аналитическое выражение функции распределения F1 (x)	График функции распределения F1 (x)	Характеристическая функция q1(u)
3	Равномер- ный (прямо-угольный)	a < x < b		a, b
4	Нормаль ный (Гаусса)	- ¥ < x < ¥		m, s
5	Логариф-мический нормаль- ный	0 < x < ¥		m, s

 

 

113

                                                                                                                                                                                              Таблица 1. 2

 

 

Продолжение Табл. 1.2

 

114

6	Хи-квадрат распреде- ление	0 < x < ¥	где y i- независимые СВ по закону (4) с т= 0	n, σ σ=1
7	Гамма- распреде- ление	0 < x < ¥		a, b, a > - 1, b > 0
8	Рэлея	0 < x < ¥		s

 

W^* (∙)-табулированный интеграл вероятности от комплексного аргумента

Продолжение Табл.1.2

9

Райса

0 < x < ¥

a, s

115

10	m -распре-деление (Накагами)	0 < x < ¥		m, Ω Ω=M[x2] = =σ2
11	Вейбулла	0 < x < ¥		c > 0, a > 0
12	Экспонен-циальный	0 < x < ¥		l

* - D _-ν (z) - функция параболического цилиндра [6] (3.384.9).

Приложение 2

Интегралы

 

1. >0;   – функция Крампа;

2.       

3.

4.   , – целое;

 

5.;

6.                           

7.;;

;

8. – неполная гамма-функция

9.

10. – бета-функция.

11.

где – функция параболического цилиндра

(3.384.9).

12.

 

где функция Уиттекера (9.224) равна:

 (9.220.2)

.(9.215.1)

13. (3.382.)

14.            (3.354.5)

15.

16.

СОДЕРЖАНИЕ

Введение ……………………………………………………………………..…...3

1.       ДЕМОДУЛЯЦИЯ И ДЕТЕКТИРОВАНИЕ ФМ И ЧМ СИГНАЛОВ.

 ТАКТОВАЯ И ВЫСОКОЧАСТОТНАЯ СИНХРОНИЗАЦИЯ В

ПРИЕМНИКАХ. РЕАЛИЗАЦИЯ КОГЕРЕНТНЫХ ПРИЕМНИКОВ... 4

1.1. Тактовая синхронизация …………………………………………….…....4

1.1.1 Синхронизация по сигналу тактовой частоты передатчика ……....5

1.1.2 Синхронизация по информационному цифровому сигналу ….......9

1.1.3 Синтез оптимального алгоритма совместного принятия решений и тактовой синхронизации (синхронизированный детектор)………11

1.2. Высокочастотная синхронизация. Синтез оптимального когерентного     демодулятора для сигналов с угловой модуляцией………………….….…14

1.2.1 ВЧ синхронизация по немодулированному сигналу………….…..16

1.2.2 ВЧ синхронизация по модулированному сигналу, фазовые шумы, реализация когерентных приемников ФМ, ЧМ сигналов……………...20

1.2.3 Синтез оптимального алгоритма совместной ВЧ синхронизации и демодуляции сигналов с угловой модуляцией………                      …...37

Задачи к разделу 1………………………………………………………….....42

2. C ИСТЕМЫ СВЯЗИ С РАЗНЕСЕННОЙ ПЕРЕДАЧЕЙ,

ПРИЕМОМ СИГНАЛОВ ………………………………………………..........45

2.1. Методы разнесения………………………………………………………46

2.2. Методы комбинирования принимаемых сигналов…………………….47

2.3. Влияние корреляции сигналов при разнесении………………………..57

2.4. Примеры  реализации  приемников разнесенного  приема  с

когерентным сложением ветвей разнесения………………………………..58

Задачи к разделу 2……………………………………………………………....62