Методические указания к выполнению лабораторных ра

51

левее отображает решение декодера о номере ошибочного символа (все исследуемые в макете коды позволяют исправлять однократные ошибки).

Если синдром нулевой, то декодер выводит сообщение “ Ошибок нет”. Если синдром ненулевой, то по таблице синдромов декодер определяет номер ошибочного символа и выводит сообщение “ Ошибка в хр”, где р – номер ошибочного символа.

Таблица синдромов содержит только п синдромов, соответствующих п символам декодируемой кодовой комбинации. Число возможных синдромов равно 2n – k. Если n < 2n – k – 1, то в декодере может появиться синдром, которого нет в таблице синдромов. В этом случае декодер выдает сообщение “ Неизвестная ошибка”.

Если декодер определил номер ошибочного символа – сообщение “ Ошибка в хр”, то он инвертирует этот символ и удаляет n – k последних символов. Если же синдром нулевой или его нет в таблице синдромов, то декодер лишь удаляет n – k последних символов. На выходе декодера появляются принятые информационные символы.

7 Требования к отчету

7.1Название лабораторной работы.

7.2Цель лабораторной работы.

7.3Результаты выполнения домашнего задания.

7.4Результаты выполнения п. 5.2...5.9 лабораторного задания.

7.5Выводы по каждому пункту лабораторного задания, в которых дать анализ полученных результатов – совпадение данных лабораторного задания и данных домашнего задания.

7.6Дата, подпись студента, виза преподавателя с оценкой по 100балльной шкале.

52

Лабораторная работа 4.2 ИССЛЕДОВАНИЕ ПОМЕХОУСТОЙЧИВОСТИ

КОРРЕКТИРУЮЩИХ БЛОКОВЫХ КОДОВ 1 Цель работы

1.1Изучение алгоритмов декодирования блоковых корректирующих кодов (n, k) с исправлением ошибок.

1.2Экспериментальное исследование помехоустойчивости блоковых корректировочных кодов.

2 Ключевые положения

2.1 Блоковые коды. Наиболее распространенными среди блоковых кодов являются коды Боуза-Чоудхури-Хоквингема (БЧХ) – класс блоковых линейных систематических циклических кодов, которые исправляют кратные ошибки, т.е. две и больше (dmin ³ 5). Теоретически коды БЧХ могут исправлять произвольное количество ошибок, но при этом существенным образом увеличивается длина кодовых комбинаций, которая приводит к увеличению задержки передачи данных и усложнение алгоритма декодирования.

Если корректирующий код должен обеспечивать исправление ошибок кратности qис, то необходимое кодовое расстояние dmin блокового кода (n, k) определяется по формуле

dmin = 2qис + 1.	(1)
Основные параметры кода (n, k) связаны соотношением
k = n – m qис,	(2)

где m – наименьшее целое, удовлетворяющее условию 2m ≥ n.

2.2 Синдромное декодирование. Сегодня для блоковых корректирующих кодов (n, k) синдромное декодирование является основным для обнаружения и исправления ошибок. Синдромный метод исправления ошибок базируется на простом правиле: по синдрому кодовой комбинации определяется местоположение ошибочных символов. Поэтому под синдромом кодовой комбинации понимают результат вычисления декодером по определенным правилам числа s(s1, s2, …, sr), r = n – k, которое свидетельствует о наличии ошибочных символов и определяет их расположение (конфигурацию) в кодовой комбинации. В случае двоичных кодов синдром записывается в двоичной системе исчисления, т.е. его разряды s1, s2, …, sr принимают значения 0 и 1.

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

Если кратность ошибок q в декодируемой кодовой комбинации не превышает кратность исправляемых ошибок qис, q ≤ qис, то синдром однозначно

53

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

Если q > qис, то возможные две ситуации:

– полученный вычислением синдром соответствует определенной конфигурации ошибок, которая встречается при q ≤ qис, в этой ситуации декодер “ исправляет” ошибки, но исправление не верное, и, скорее всего, количество ошибочных символов в кодовой комбинации возрастает;

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

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

В схеме рис. 1 “ Анализатор синдрома” является наиболее сложным устройством. В нем по вычисленному синдрому устанавливается конфигурация ошибок, которая затем исправляется корректором ошибок. Сумматор по mod 2 (Å) – устройство исправления ошибок для двоичного кода. Поскольку синдром может быть вычисленным только на основе всего кодового слова (комбинации), то для исправления ошибок кодовое слово необходимо задержать на n символов – это осуществляется n-разрядным регистром сдвига. После установления анализатором конфигурации ошибок символы декодируемой кодовой комбинации последовательно "выталкиваются" из регистра сдвига, а из анализатора поступают символы "1" в те моменты времени, когда необходимо инвертировать ошибочные символы.

Вход
декодера
	Вычислитель
ˆ	синдрома
b
	s			Выход
		e	Корректор	декодера
	Анализатор
			ошибок
	синдрома		Å	â

n- разрядный регистр сдвига

Рисунок 1 – Структурная схема синдромного декодера блокового кода

2.3. Корректирующая способность помехоустойчивых кодов. Коррек-

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

54
qис ≤ (dmin – 1)/2	(3)
и величиной кратности гарантировано обнаруживаемых ошибок
qоб ≤ dmin – 1,	(4)

где dmin – кодовое расстояние кода.

Помехоустойчивость системы передачи с корректирующим кодом (так же, как и системы передачи без корректирующего кода) описывается зависимостью вероятности ошибки бита от отношения сигнал/шум на входе демодулятора. Под отношением сигнал/шум понимают hб2 = Еб N 0 – отношение энергии

сигнала, затрачиваемой на передачу одного бита, к удельной мощности шума. Используем обозначения: р – вероятность ошибки бита на выходе демодулятора; рд – вероятность ошибки бита на выходе декодера.

Пример зависимостей для системы передачи без помехоустойчивого кодирования р = f( hб2 ) и для системы передачи с кодом БЧХ (1023, 733) рд = f( hб2 ) приведен на рис. 2.

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

p =Q(				2Rкод hб )			,		(3)
где
		1		∞	t	2
Q(z)=				∫ exp(−			)dt	–	(4)
		2π z			2
гауссовская Q-функция; Rкод = k/n –				скорость кода.
При использовании корректирующего								кода	зависимость вероятности

ошибки символов на выходе декодера от вероятности ошибки на его входе следующая:

		dmin		n
	pд =			∑Cnq p q (1 − p)n − q .		(5)
		n
				q = qвип +1
	В сумме (5) для расчетов при р << 1 достаточно использовать только пер-
	вое слагаемое и исключить множитель (1 − p)n−q , который близок к единице:
		pд =		dmin	Cnqвип +1 pqвип +1 .	(6)
				n

2.4 Энергетический выигрыш кодирования. Обобщенной характери-

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

щего кода hб21 и с корректирующим кодом hб22 при одинаковой вероятности ошибки символов (рис. 2).

55

ЭВК = h2

–

h2 .

(7)

б1

б2

h2

h2

б2

б1

12 h2

0

1

2

3

4

5

6

7

8

9

10

11

, дБ

1

б

10– 1

10– 2

ЭВК

10– 3

10– 4

10– 5

рдоп

С кодом БЧХ

Без кода

10– 6

(1023,733)

рд

р

р

10– 7

Рисунок 2 –

Графики помехоустойчивости системы передачи

без корректирующего кода и с корректирующим кодом

Напоминаем, что отношение hб2 определяется как

56

h2	=	Eб	=	PsTб	=	Ps	,	(9)
б		N0		N0		N0 R

где Ps/N0 – отношение средней мощности сигнала к удельной мощности шума на входе демодулятора;

R – скорость цифрового сигнала на входе системы передачи.

ЭВК можно рассчитать теоретически или измерить экспериментально. Например, в системе передачи необходимо обеспечить вероятность ошибки бита pдоп = 10–5 . При отсутствии помехоустойчивого кодирования согласно рис. 2 заданная вероятность ошибки будет обеспечиваться при отношении сигнал/шум hб21 = 9,6 дБ, в то время как использование кода БЧХ (1023, 733) по-

зволяет снизить необходимое отношение сигнал/шум до hб22 = 6 дБ, то соответственно, ЭВК = 9,6 - 6 = 3,6 дБ.

Если код обеспечивает ЭВК > 0 (на рис. 2 при рдоп < 4 10–3 ), то такой корректирующий код позволяет уменьшить необходимое отношение сигнал/шум

на входе демодулятора. Если же ЭВК ≤ 0, то такой корректирующий код не позволяет уменьшить необходимое отношение сигнал/шум на входе демодулятора, его использование только ухудшает помехоустойчивость системы передачи.

Зависимости р =f ( hб2 ) и рд=f ( hб2 ) могут быть получены экспериментально

по методике, описанной в лабораторной работе 3.4.

2.5 Методы борьбы с пакетами ошибок. Необходимо заметить, что ко-

ды БЧХ способны эффективно бороться со статистически независимыми ошибками, т.е. такими, которые взаимно не зависимы и, в конечном счете, общее число ошибочных символов оказывается равномерно распределенным по всей последовательности переданных данных (рис. 3, а).

Если ошибки пакетируются (рис. 3, б), т.е. наблюдается появление сразу нескольких ошибок подряд, для эффективной борьбы с ними могут применяться коды БЧХ с перемежением или блоковые коды Рида-Соломона.

1	2	3	4	5	6	7	8		9	10	11	12	13	14	15	16
							а)												Верный символ
1	2	3	4	5	6	7	8		9	10	11	12	13	14	15	16			Ошибочный
							б)
																			символ
1	5	9	13	2	6	10	14		3	7	11	15	4	8	12	16
							в)

Рисунок 3 – Ошибки: а) равномерно распределенные, б) пакетированные, в) после перемежения последовательности б)

Перемежение представляет собой разброс бит в последовательности по определенному закону. Наиболее простым методом перемежения является матричное перемежение (рис. 4), при котором после кодера в буфер (матрицу размером (X× Y)) ведется запись символов по строкам и считывание по столбцам. В декодере наоборот: запись по столбцам, считывание по строкам (деперемеже-

57

ние). В результате перемежения и деперемежения две ошибки, которые расположены рядом в последовательности на выходе демодулятора оказываются разнесенными на величину размера буфера Х, т.е. ошибки не создают пакет. На рис. 3, в показан пример деперемежения последовательности, заданной на рис. 4, б, деперемежителем, изображенным на рис. 4.

	X
1	2	3	4
5	6	7	8
Y
9	10	11	12
13	14	15	16
	а)

1 2 3 4

5

6

7

8

9 10 11 12

13 14 15 16

б)

Рисунок 4 – Матричное перемежение

Робота с буфером при перемежении: а) порядок записи в буфер; б) порядок считывания из буфера.

Робота с буфером при деперемежении: б) порядок записи в буфер; а) порядок считывания из буфера.

Коды Рида-Соломона – недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодовых комбинаций являются не биты, а группы бит (блоки). Очень распространены коды Рида-Соломона, работающие с байтами. Код Рида-Соломона является отдельным случаем кода БЧХ.

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

новления в случае повреждений.

2.6 Справочные данные. В табл. 1 приведены параметры корректирующих кодов: n – длина кодового слова; k – количество информационных бит; qис – количество исправляемых ошибок; Cnq – число сочетаний из n по q; Rкод – скорость кода.

На рис. 5 приведена зависимости энергетического выигрыша при использовании циклических кодов в каналах с ФМ-2 в зависимости от длины блока n и скорости кода Rкод.

Таблица 1 – Характеристики циклических кодов

	n		k	qис	Cnqиc +1	Rкод	n	k	qис	Cnqиc +1	Rкод
7		4		1	21	0,57	127	120	1	8001	0,95
15		11		1	105	0,73		113	2	333375	0,89
		7		2	455	0,47		106	3	10334625	0,84
								99	4	2,54·108	0,78
31		26		1	465	0,84
		21		2	4495	0,68		92	5	5,17·109	0,72
		16		3	31465	0,52	255	239	2	2731135	0,94
		11		4	169911	0,35		231	3	1,72 108	0,91
								223	4	8,64·109	0,87
63		57		1	1953	0,90
								215	5	3,6·1011	0,84
		51		2	39711	0,81
								207	6	1,28·1013	0,81
		45		3	595665	0,71
							511	493	2	2,21·107	0,96
		39		4	7028847	0,62
		33		5	67945521	0,57		484	3	2,81·109	0,95

hб2 , изменяя

58

ЭВК, дБ

Рисунок 5 – Зависимость ЭВК от скорости кода Rкод для разных n

3 Ключевые вопросы

3.1Что такое синдром кодовой комбинации, и с какой целью он исполь-

зуется?

3.2Назовите преимущества корректирующего кода Рида-Соломона в сравнении с другими кодами.

3.3Какими параметрами корректирующего кода определяется зависимость вероятности ошибки символов на выходе декодера от вероятность ошибки на его входе?

3.4Каким образом исправляются ошибки в кодовых комбинациях корректирующего кода?

3.5Что определяет ЭВК корректирующего кода?

3.6От каких параметров корректирующего кода зависит ЭВК?

3.7Что такое пакеты ошибок?

3.8С какой целью в системах передачи может использоваться перемежи-

тель?

3.9Назовите известные Вам методы борьбы с пакетами ошибок.

4 Домашнее задание

4.1Изучить раздел «Помехоустойчивость блоковых корректирующих кодов» по конспекту лекций и литературе [3, с. 40...45].

4.2Распечатать или перечертить в рабочую тетрадь рис. 2.

4.3Рассчитать зависимость вероятности ошибки символов на выходе де-

кодера рд от отношения сигнал/шум на входе демодулятора ФМ-2 его от 6 дБ до 8 дБ с шагом 0,5 дБ. Код задан в табл. 2.

Для расчетов взять значение qис, Cnqи +1 и Rкод из табл. 1; расчеты провести по формулам (1), (3) и (6), воспользоваться аппроксимацией Q-функции:

Q(z) = 0,65exp(–0,44( z+0,75)2).

Результаты расчетов оформить таблицей и построить зависимость

рд = f ( hб2 ) на рис. 2.

59

4.4 Рассчитать ЭВК при допустимой вероятности ошибки на выходе декодера pдоп, которая задана в табл. 2.

Таблица 2 – К домашнему заданию

	Номер Вашей бригады	Код (n, k)		Допустимая вероятность ошибки
				на выходе декодера pдоп
	1 и 7	(255,	239)	10–5
	2 и 8	(127,	106)	10–5
	3 и 9	(63,	51)	10–6
	4 и 10	(511,	484)	10–4
	5 и 11	(255,	231)	10–5
	6 и 12	(127,	113)	10–5

4.5 Подготовиться к обсуждению по ключевым вопросам.

5 Лабораторное задание

5.1 Ознакомиться с виртуальным макетом на рабочем месте. Для этого запустить программу 4.2 Исследование помехоустойчивости корректирующих блоковых кодов, используя иконку Лабораторные работы на рабо-

чем столе, а затем папки ТЭС и Модуль 4. Изучить схему макета на дисплее компьютера, пользуясь разд. 6. Уточнить с преподавателем план выполнения лабораторного задания.

Запустить программу, записать block_encoding в командной строке и нажать клавишу Enter. Освоить методику проведения исследования корректирующей способности блокового кода (n, k), т.е. введением входных данных, запуском программы, считыванием результатов. Макет лабораторной работы изо-

бражен на рис. 6 и 7.

5.2 Построить график зависимости р = f (Eб/N0) без корректирующего кода. Для этого установить режим работы системы передачи «без кода». Другие установки должны быть такими: «Без перемежения», модуляция «ФМ-2», канал «с АБГШ». Изменять отношение сигнал/шум от 2 до 9 дБ с шагом 1 дБ, каждый раз нажимать «Передать» и при этом результаты каждого измерения прибавлять к «Архиву измерений». Зависимость р = f (Eб/N0) будет автоматически отображаться на графике. Длину сообщения L следует устанавливать в пре-

делах 105…10 7.

5.3 Исследовать экспериментально корректирующую способность кода Хемминга. Выбрать тип кода «Хемминга». Длину кодового слова взять из

домашнего задания. Изменить параметр «Серия измерений» в полях «Результаты измерений» и «Архив измерений». После этого повторить измерение п. 5.2. Установить pдоп согласно домашнему заданию. С помощью маркеров измерить отношение сигнал/шум в системе передачи «Без кода» и с кодом «Хемминга». Выписать значение ЭВК.

5.4 Исследовать экспериментально корректирующую способность кода БЧХ. Выбрать тип кода «БЧХ» и согласно домашнему заданию установить параметры кода (n, k). Изменить параметр «Серия измерений» в полях «Результаты измерений» и «Архив измерений». После этого повторить измере-

ние п. 5.2.

60

Установить pдоп согласно домашнему заданию. С помощью маркеров измерить отношение сигнал/шум в системе передачи «Без кода» и с кодом «БЧХ». Выписать значение ЭВК. Сравнить полученные зависимости с рассчитанными в домашнем задании и сделать вывод относительно правильности расчетов. Изобразить полученную зависимость вероятности ошибки символа на выходе декодера от отношения сигнал/шум рд = f (Eб/N0). Рисунок должен зани-

мать не менее чем одну страницу в тетради.

5.5 Исследовать свойства корректирующих кодов. Сравнить получен-

ные значения ЭВК в п. 5.3 и 5.4, сделать соответствующие выводы. Изменить параметр pдоп и сделать вывод относительно изменения значения выигрыша кодирования. Изменить параметры кода, не изменяя скорость кода. Сделать соответствующие выводы. Изменить скорость кода путем изменения одного из параметров кода. Сделать измерение ЭВК для четырех скоростей кода. По результатам измерений построить зависимость ЭВК от скорости кода для коррек-

тирующего кода БЧХ.

5.6 Исследовать помехоустойчивость блоковых кодов в канале с за-

мираниями. Для этого необходимо изменить тип канала на «Канал с АБГШ с замираниями». Изменить вид модуляции на «ОФМ-2». Повторить исследования п. 5.3...5.5. Дополнить схему перемежителем и деперемежителем. Сделать вывод относительно эффективности использования перемежения.

5.7 Исследовать экспериментально корректирующую способность кода Рида-Соломона. Выбрать тип кода «Рида-Соломона» и установить те же

параметры, которые были установлены при исследовании кода БЧХ. Повторить измерение п. 5.3. Зафиксировать значение ЭВК. Сделать вывод относительно эффективности использования кода Рида-Соломона в канале с замираниями.

6 Описание компьютерной программы для исследования помехоустойчивости

Макет выполнен в среде MatLab. Макет позволяет изменять параметры всех блоков системы передачи. Длина сообщения L является практически неограниченной. Кодек можно не использовать или выбирать из трех вариантов: код Хемминга, код БЧХ или код Рида-Соломона. Перемежитель также можно не использовать или выбрать матричный блоковый перемежитель (X, Y). Можно изменять метод модуляции и число уровней модулированного сигнала. Канал связи с аддитивным белом гауссовским шумом (АБГШ) с постоянными параметрами или с замиранием. Отношение сигнал/шум можно изменять от 2 до

9 дБ.

Макет позволяет построить график зависимости вероятности ошибки символов на выходе декодера от отношения сигнал/шум р = f (Eб/N0). С помощью маркеров можно определить энергетический выигрыш кодирования при допустимой вероятности ошибки на выходе декодера рдоп.

7 Требования к отчету

7.1Название лабораторной работы.

7.2Цель лабораторной работы.