книги / Теория электрической связи. Помехоустойчивое кодирование в телекоммуникационных системах

20

На рис. 1.13 приведен пример декодера для кода с постоянным весом (n = 3, W = 2). Вектор ошибки равен 0, поэтому индицируется правильная передача сообщения М1, при этом сигнал стирания Erase = 0.

Рис. 1.13. Пример кодера для кода с постоянным весом (n = 3, W = 2)

Этап 5. Промоделировать работу кодирующих и декодирующих устройств на примере кодовых комбинаций, вычисленных в расчетной части лабораторной работы.

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

Для выполнения отчета и защиты необходимо воспользоваться тре-

бованиями пункта «Содержание отчета и защита лабораторных работ».

21

2.Применение групповых систематических кодов

втелекоммуникационных системах

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

2.1.Общие сведения из теории

2.1.1.Групповые систематические коды

Групповым кодом называется векторное подпространство векторного пространства всех последовательностей длины n. Групповые коды являются линейными алгебраическими кодами, для которых справедливо соотношение dmin =Wmin , т.е. минимальное кодовое расстояние равно ми-

нимальному весу кодовой комбинации. Действительно, по определению кодового расстояния dmin =W (Vi V j ), где Vi и V j V . Но согласно аксиоме замкнутости линейная комбинация Vi V j =Vµ V . Следовательно,

справедливо сформулированное выше утверждение. Поэтому если известен спектр весов кодовых векторов группового кода, то однозначно можно определить линейное кодовое расстояние и, следовательно, корректирующую способность кода. Заметим, что линейные алгебраические коды обозначаются как (n, m, d)-коды, где n, m и d – соответственно длина кодовых векторов, число информационных символов и минимальное кодовое расстояние.

Кодовые векторы группового систематического кода (ГСК) имеют формат вида

(a1, a2 ,..., ai ,..., am ,c1,...,c j ,...,ck ) = (a1,..., am , am+1, am+2 ,..., an )

(2.1)

т.е. на первых слева подряд идущих m позициях располагаются информационные символы кода, а на последующих подряд идущих k позициях − избыточные символы кода. Информационные символы кода будем обо-

значать через {ai }, i =1, m , а избыточные символы – через {c j }, j =1, k . В общем случае, как видно из (2.1),

ai(i=m+1,n) = c j( j=1,k ) .

ГСК нашел широкое применение на практике по ряду причин:

22

1.Сохраняется в неизменном виде исходная, т.е. кодируемая в неизбыточном (первичном) коде, информационная часть.

2.С меньшими задержками, т.е. существенно проще реализуются операции кодирования и декодирования информации.

Порождающая матрица G группового систематического кода имеет приведенно-ступенчатую форму:

	1	0 ...					0	p				p		...	p
								11				12			1k
	0	1 ...					0	p21				p22 ...			p2k		(2.2)
G =[I m P]=																,
... ... ... ... ...												... ...			...
0		0 0					1	pm1				p2m ...			pmk
где Im – единичная матрица размерности [ m ×m ];													P – кодирующая мат-
рица размерности [ m ×k ].
В этом случае операция кодирования в ГСК может быть представле-
на как умножение информационного вектора									u	= (a1 , a2 ,..., am ) на G:
			u
				G =V		.											(2.3)
В координатной форме данное уравнение имеет вид
(a1, a2 ,..., ai ,..., am ) [Im P]= (a1, a2 ,..., ai ,..., am , c1,..., c j ,..., ck ),																	(2.3, а)
				m
		c j = ∑ai pij , j =1, k.
				i=1

Выражения вида (2.3, а) для вычисления избыточных разрядов ГСК по известным информационным разрядам называют операторами кодиро-

вания.

Проверочная матрица ГСК

					H =[PT Ik ],					(2.4)
	где PT – транспонированная кодирующая матрица P;						Ik	– единичная мат-
	рица размерности [ k ×k ].
	Пример 2.1. Построим порождающую и проверочную матрицы ГСК
	(5, 3, 2):
	1	0	0	1	0	1	1	0	1	0
	G =[I3P]= 0 1 0 1 1 ; H = [PT I2
						]=	1	1	0	.
						0				1
		0	1	0
	0				1

23

Из (2.3) следует, что u = (a1 , a2 , a3 ) [I3 P]=V = (a1 , a2 , a3 , c1 , c2 ) .

Тогда операторы кодирования имеют следующий вид:

c1 = a1 a2 , c2 = a2 a3.

Из (2.3) и (2.3, а) V H T = 0, т.е. (a1, a2 , a3, c1, c2 ) [PT I2 ] = (0,0) . Сле-

довательно, справедливо, что

a a		c = 0;	отсюда	c	= a	a	;
1	2	1		1	1	2
a2 a3 c2 = 0,				c2 = a2 a3.

Отметим, что благодаря приведенно-ступенчатой форме матриц G и H получается система из k алгебраических уравнений, в каждом из которых содержится по одной переменной, и упрощаются процедуры кодирования и декодирования в ГСК. Любые линейные алгебраические коды, исправляющие однократные ошибки, т.е. коды с dmin = 3 и dmin = 4, называются кодами Хемминга. Тогда синдром ГСК Хемминга совпадает со столбцом проверочной матрицы Н, номер которого соответствует номеру ошибочной позиции. Для кодов Хемминга иногда выбирают другую форму представления кодовых векторов, при которой избыточные разряды расположены на позициях кодового слова, номера которых равны степеням двойки. В этом случае синдром представляет собой двоичное число, указывающее номер пораженной позиции. В данном разделе ГСК Хемминга будут рассматриваться как частный случай ГСК с форматом (2.1).

2.1.2. Техника построения группового систематического кода

Блок-схема алгоритма построения ГСК представлена на рис. 2.1. Приведенный обобщенный алгоритм синтеза операторов кодирова-

ния пригоден для любого алгебраического кода с точностью до раскрытия ряда операторов. Ниже алгоритм рассматривается для ГСК и оговариваются некоторые особенности его применения для других типов кодов:

1. Исходные данные. Ими являются:

–число информационных символов кода (m) либо множество передаваемых сообщений (М);

–модель канала связи;

–допустимая вероятность правильной передачи (или вероятность трансформации).

Пусть задан канал связи с независимыми ошибками, описываемый биномиальным распределением ошибок с вероятностью ошибки на символ, равной (p).

24

2. Выбор типа кода, оптимального для заданной модели канала связи. Для каналов связи с независимыми ошибками оптимальными являются групповые коды и циклические (БЧХ) коды. Если бы канал описывался моделью канала с памятью, то необходимо было бы выбрать коды, оптимальные в каналах с пакетирующими ошибками, например циклические коды Файра, Абрамсона, перемежающиеся и др. Итак, мы выбрали ГСК.

1.Исходные

данные

2.Выбор типа кода

3.S = 0

4.S = S + 1

5.Выбор параметров кода

Нет	Да
	pпр. > [pд]

6. Выбор ближайшего табл. кода

7. Выбор укороченного кода

8. Построение операторов кодирования

Рис. 2.1. Обобщенная блок-схема алгоритма построения алгебраического (ГСК) кода

3. На данном шаге алгоритма реализуются операторы 3, 4 и 5, связанные с выбором методом перебора параметров кода: корректирующей

25

способности (s), числа избыточных символов (k), которые обеспечивают требуемые характеристики достоверности передачи информации. Для ГСК выбор параметров кода осуществляется с помощью верхней границы Хемминга. Для БЧХ-кодов аналогичная задача решается с помощью границы существования кода БЧХ. Итак, из границы Хемминга для фиксированных значений m и последовательно перебираемых значений s определяются длины кодовых слов n = m + k. Для каждых n и s находится вероятность правильной передачи сообщения Pпр = P(m):

s	n		− p)n−i .	(2.5)
P(m) = ∑		pi (1
i=0
	i

Далее значение Pпр сравнивается с [Pд], допустимой вероятностью правильной передачи кодового слова (сообщения). Если Pпр < [Pд], то кратность исправляемых ошибок увеличивается на единицу и расчет повторяется, иначе переходим к оператору 6.

4.Выбор ближайшего табличного кода. Граница Хемминга не является границей существования кода и потому не гарантирует существования ГСК с параметрами, определенными на предыдущих шагах алгоритма.

Поэтому обращаемся к табличным ГСК и находим ближайший код (nT, mT, dT), удовлетворяющий условию dT ≥ d, т.е. sT ≥ s, mT ≥ m .

5.Выбор укороченного кода. Отыскиваем число i = mТ −m , на кото-

рое укорачиваем число информационных символов кода, т.е. реализуем переход от параметров табличного кода к укороченному коду: (nТ, mТ, dТ) i →(nT −i, mT −i, d ) = (n, m, d) . Найденный укороченный код и является искомым кодом, т. к. удовлетворяет всем исходным данным. В принципе после этого шага можно уточнить значение P(m) (5), которое должно измениться за счет уменьшения длины кода на величину i .

6. Построение операторов кодирования. Операторы кодирования (2.3, а) табличных кодов приводятся в стандартных таблицах ГСК. Для построения операторов кодирования укороченного ГСК необходимо в операторах кодирования табличных кодов зачеркнуть i первых информационных символов (a1 , a2 ,..., ai ) .

Пример 2.2. Проиллюстрируем приведенный алгоритм на примере построения ГСК, исправляющего однократную ошибку, т.е. кода Хеммин-

га с dmin = 3 и dmin = 4. Выберем в качестве исходных данных m = 4, s = 1. Следует отметить, что в данном примере из методических соображений

опущена переборная часть алгоритма, связанная с анализом логического условия, так как это чисто вычислительная процедура, загромождающая пример. Напомним, что из границы Хемминга отыскиваются параметры кодов с нечетным кодовым расстоянием. Далее будет показано, как пере-

26

ходить от кодов с нечетным кодовым расстоянием dH, исправляющих ошибку кратности s, к кодам с ближайшим большим четным кодовым расстоянием (dЧ = dH + 1), исправляющим s-кратные ошибки и обнаруживающим ошибки кратности r = s +1.

С учетом изложенного в данном примере отыскиваем операторы ко-

	дирования для ГСК Хемминга с dmin = 3 и m = 4:
	2m ≤	2n	; 24 ≤	2n		.
		1 + n		1 + n

Перебором устанавливаем параметры кода: n = 7, m = 4, k = 3, т.е. (7, 4, 3)-код. Такой код существует, и операторы кодирования можно выписать из стандартной кодовой таблицы ГСК. Ниже покажем, как можно самостоятельно строить операторы кодирования по проверочной матрице ГСК. Для этого рассмотрим построение проверочной матрицы Н. Несложно показать, что столбцами матрицы являются k-разрядные ненулевые

двоичные	векторы, образующие линейно-независимые множества из
r = d −1	векторов. Данное утверждение основано на следующем. Если

ГСК обнаруживает ошибки кратности r и меньше, то синдром должен быть ненулевым при умножении вектора ошибки веса r и меньше на Н.

Для построения матрицы Н размерности [k ×n] ГСК Хемминга дос-

таточно в качестве n столбцов выписать различные k-разрядные ненулевые двоичные векторы. В рассматриваемом примере построим проверочную

матрицу H′ размерности [3 ×7]:
0	0	0	1	1	1	1
H ′ = 0 1 1			0	0	1	1 .
	0	1	0	1	0
1						1

Далее с помощью эквивалентного преобразования (перестановка столбцов) приведем матрицу H′ в приведенно-ступенчатую форму Н

(2.4):

1	1	0	1	1	0	0
H = 1 1 1			0	0	1 0 .
	0	1	1	0	0
1						1

Из (2.3) и (2.3, а) следует

								27
(a , a		, a , a		, c , c			, c )			hT		= 0 , (i =		j =
	2		4			2							1,7;		1,3),
1		3		1			3			ij
откуда и получаются искомые операторы кодирования:
					c1 = a1 a2 a4 ;
					c2 = a1 a2 a4 ;												(2.6)

c3 = a1 a3 a4.

Пусть u = (a1 , a2 , a3 , a4 ) = (1101) , тогда с учетом (2.6)

V = (a1 , a2 , a3 , a4 , c1 , c2 , c3 ) = (1101100) .

Пусть потребовалось укоротить построенный код (7, 4, 3) на i = 2 информационных символа, т.е. перейти к укороченному коду (5, 2, 3):

(7, 4,3) i =2→(5, 2,3). Тогда операторы кодирования (5, 2, 3)-кода можно

построить по операторам кодирования (2.6), используя правило, сформулированное в п. 6 алгоритма:

c1 = a4 ;
c2	= a3;	(2.6, а)
c3	= a3 a4.

Вектор укороченного (5, 2, 3)-кода имеет вид

V = (a3 ,a4 ,c1,c2 ,c3 ) = = (01101).

Рассмотрим переход от кода с нечетным кодовым расстоянием dH к коду с ближайшим четным кодовым расстоянием dЧ = dH + 1. Для такого перехода достаточно ввести еще один дополнительный избыточный разряд ck+1, значение которого определяется из общей проверки на четность:

m	k
ck +1 = ∑ai ∑c j .		(2.7)
i=1	j =1

Таким образом, если параметры исходного кода (n, m, dH), то параметры кода с dЧ = dH + 1 таковы: n+1, m, dЧ, т.е. число информационных символов сохранилось, а число избыточных символов увеличилось на один.

Пример 2.3. Для кода (7, 4, 3) из примера 2.2 код (8, 4, 4) будет кодом с ближайшим большим четным кодовым расстоянием. При этом дополнительный избыточный разряд общей проверки на четность

	28
4	3
c4 = ∑ai ∑c j .
i=1	j =1

Если в (2.7) подставить выражения для cj из (2.3, а), то уравнение (2.7) упростится. Можно предложить следующее правило вычисления сk+1 через информационные символы исходного (n, m, dH)-кода.

Правило. Если информационный символ входит четное число раз в операторы кодирования (n, m, dH)-кода (2.3, а), то он сохраняется в (2.7), если же информационный символ входит нечетное число раз, то он не сохраняется в выражении (2.7).

С учетом сформулированного правила и операторов кодирования кода (7, 4, 3) в выражении (2.6) уравнение для c4 имеет следующий вид: c4 = a2 a3 a4. Тогда вектор кода (8, 4, 4)

V = (a1,a2 ,a3 ,a4 ,c1,c2 ,c3 ,c4 ) = (11011000).

2.1.3.Декодирование группового систематического кода

Декодер ГСК реализует синдромное декодирование, суть которого основана на вычислении синдрома в соответствии с уравнениями синдрома. Итак, синдромное декодирование состоит из следующих этапов:

1. По принятому кодовому вектору V ′=V e находим синдром

S= (s1, s2 ,..., s j ,..., sk ).

2.По вычисленному значению синдрома однозначно отыскиваем вектор ошибок e = (e1,e2 ,...,e j ,...,en ).

3.Производим исправление ошибок и выдачу скорректированного кодового слова (сообщения) получателю: V =V ′ e, либо стирание полу-

ченного кодового слова, если кратность ошибок в кодовом слове s′ удовлетворяет соотношению s < s′ ≤ r, где r − кратность обнаруживаемых ошибок.

Пример 2.4. Проиллюстрируем синдромное декодирование на примере кода (8, 4, 4) из примера 2.3. В процессе данного примера будет сделан ряд замечаний общего характера, связанных с реализацией корректирующих возможностей кода с четным кодовым расстоянием. Итак, для кода (8, 4, 4) уравнение синдрома с учетом (1.6) имеет вид

s1 = a1′ a2′				a4′	'
					c1;
s2 = a1′ a2′				a3′
					c2' ; (7,4,3)
		′	′	′	'				(2.8)
								(8,4,4)
s3 = a1			a3	a4	c3	;
s		4		4
	4	= ∑a′		∑c′.
			i	j
		i=1		j =1

29
Отметим, что (2.8) можно записать	и через вектор ошибок:
e = (e1,e2 ,e3,e4 ,e5,e6 ,e7 ,e8 ) . Синдром кода (8,	4, 4) − это четырехразряд-

ный вектор s = (s1, s2 , s3 , s4 ) , у которого первые три разряда (в общем слу-

чае k-разрядов) вычисляются согласно уравнениям кода (7, 4, 3) (в общем случае (n, m, dH)), а последний разряд s4 (в общем случае (k+1)-й разряд) − согласно общей проверке на четность,

S		m	k +1	(2.9)
	k +1	= ∑a′ ∑c′ .
		i	j
		i=1	j =1

При этом минимизация выражения (2.9) недопустима. Таким образом, общая структура синдрома кода (n + 1, m, dЧ = dH + 1) такова: S = (s1,..., s j ,..., sk , sk +1). При этом первые k-разрядов вычисляются по урав-

нениям для кода (n, m, dH), а последний (k + 1)-й разряд – по (2.9) для кода (n + 1, m, dЧ). При декодировании кода Хемминга с dmin = 4, исправляющего одну и обнаруживающего две ошибки, анализ кратности ошибок в кодовом векторе V ′ на входе декодера производится в соответствии с табл. 2.1.

			Таблица 2.1
№	S1, S2,…, Sj,…, Sk	Sk+1	Кратность ошибок в векторе V		′
п/п
1	0	0	Ошибок нет
2	≠0	1	Ошибки нечетной кратности, в частно-
			сти однократная ошибка
3	≠0	0	Ошибки четной кратности, в частности
			двукратная ошибка
4	0	1	Ошибки в символе c
			k+1

Вданной таблице символ «0» означает, что все координаты вектора нулевые; символ «≠0» показывает, что хотя бы одна координата вектора ненулевая.

Таким образом, декодер исправляет однократную ошибку в ситуациях 2 и 4 и стирает сообщение при двукратной ошибке (ситуация 3).

Врассматриваемом примере для кода (8, 4, 4) при исправлении однократной ошибки таблица соответствия значений синдрома и места ошиб-

ки − это табл. 2.2.

Значения (S1, S2, S3) совпадают с соответствующим столбцом матрицы Н кода (7, 4, 3) в примере 2.2.