636_Nosov_V.I._Seti_radiodostupa_CH.1_

Таблица 4.7 Некоторые примитивные полиномы

m				f ( X )		m				f ( X )
3	1	X X 3				14	1	X X 6		X 10	X 14
4	1	X	X 4			15	1	X	X 15
5	1 X 2		X 5			16	1 X X 3			X 12	X 16
6	1	X X 6				17	1	X 3	X 17
7	1	X 3	X 7			18	1	X 7	X 18
8	1	X 2	X 3	X 4	X 8	19	1	X X 2		X 5	X 19
9	1	X 4	X 9			20	1	X 3	X 20
10	1	X 3	X 10			21	1	X 2	X 21
11	1	X 2	X 11			22	1	X	X 22
12	1	X X 4		X 6	X 12	23	1	X 5	X 23
13	1	X X 3		X 4	X 13	24	1	X X 2		X 7	X 24

Таким образом, из (4.33) и (4.34) следует, что 3 представляется в виде
взвешенной суммы всех	- членов более низкого порядка. Фактически так

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

элементов поля	4 , 5 ,	6 через	значения		0 ,	1,	3 .	Результаты	таких
представлений приведены ниже. С учетом уравнения (4.34) получим
		4	3	(1	)		2.		(4.35,а)
Используя результаты уравнения (4.35,а) определим
		5	4	(	2 )	2	3.		(4.35,б)
Из уравнений (4.34) и (4.35) получаем
			5	1	2.				(4.35,в)
Используя результат уравнения (4.35,в), получим
	6	5	(1	2 )		2	3	1 2.	(4.35,г)
А теперь из уравнения (4.35.г) вычисляем
	7	6		(1 2 )		3	1	0.	(4.35,д)

131

Так как, в соответствии с (4.35,д)	7	0 , то восемью элементами
конечного поля GF(23) будут
0, o , 1, 2 ,	3 ,	4 , 5 , 6 .	(4.36)

Отображение элементов поля в базисные элементы, которое описывается уравнением (4.31), можно проиллюстрировать с помощью схемы линейного регистра сдвига с обратной связью (Linear Feedback Shift Register — LFSR) (рис. 4.14). Схема генерирует (при m = 3) 2m -1 ненулевых элементов поля и, таким образом, обобщает процедуры, описанные в уравнениях (4.35)-(4.36). Следует отметить, что показанная на рис. 4.14 обратная связь соответствует коэффициентам полинома f (X ) 1 X X 3 , как и в случае двоичных циклических кодов.

Пусть вначале схема находится в некотором состоянии, например, 100. При выполнении правого сдвига на один такт можно убедиться, что каждый из элементов поля (за исключением нулевого), показанных на рис. 4.13, циклически будет появляться в разрядах регистра сдвига. На данном конечном поле GF(23) можно определить две арифметические операции – сложение и умножение. В таблице 4.8 показана операция сложения, а в табл. 4.9 – операция умножения, но только для ненулевых элементов. Правила суммирования следуют из уравнений (4.34) и (4.35); и их можно доказать, обратившись к рисунку 4.13, поскольку сумму двух элементов поля можно рассчитать путем сложения (по модулю 2) соответствующих коэффициентов их базисных элементов. Правила умножения, указанные в таблице 4.9, следуют из обычной процедуры, в которой произведение элементов поля вычисляется путем сложения по модулю (2m - 1) их показателей степеней или, для данного случая, по модулю 7.

X0

X1

X2

X3

T1

T2

T3

Рис. 3.18 Отображение элементов поля Галуа в базисные элементы

132

Таблица 3.6 Операция сложения для GF(8) при f (X )							1	X		X 3
		0	1	2	3	4			5		6
	0	0	3	6	1	5			4		2
	1	3	0	4	0	2			6		5
	2	6	4	0	5	1			3		0
	3	1	0	5	0	6			2		4
	4	5	2	1	6	0			0		3
	5	4	6	3	2	0			0		1
	6	2	5	0	4	3			1		0
Таблица 3.7 Операция умножения для GF(8) при f (X )							1		X	X 3
		0	1	2	3	4			5		6
	0	0	1	2	3	4			5		6
	1	1	2	3	4	5			6		0
	2	2	3	4	5	6			0		1
	3	3	4	5	6	0			1		2
	4	4	5	6	0	1			2		3
	5	5	6	0	1	2			3		4
	6	6	0	1	2	3			4		5

4.6.2 Кодирование Рида-Соломона

В уравнении (3.32) представлена наиболее распространенная форма

записи кодов Рида-Cоломона через параметры n,k,t		и	некоторое
положительное число m >2
(n,k) (2m	1,2m 1 2t).		(4.37)
Здесь n k 2t – число контрольных	символов, а t	—	количество

ошибочных битов в символе, которые может исправить код. Генерирующий полином для кода Рида-Соломона имеет следующий вид

P(X ) A	A X	A X 2	... A	X 2t 1	X 2t .	(4.38)
0	1	2	2t 1

Степень полиномиального генератора равна числу контрольных символов. Коды Рида-Соломона являются подмножеством кодов БХЧ, которые обсуждались выше и показаны в таблице 4.5. Поэтому связь между степенью полиномиального генератора и числом контрольных символов, как и в кодах БХЧ, не должна оказаться неожиданностью. В этом можно убедиться, подвергнув проверке любой генератор из таблицы 4.7. Поскольку

133

, 2 ,...,

полиномиальный генератор имеет порядок 2t, мы должны иметь в точности 2t последовательные степени , которые являются корнями полинома. Обозначим корни Р(X) как 2t . Нет необходимости начинать именно с корня это

можно сделать с помощью любой степени .

Возьмем к примеру код (7, 3) с возможностью коррекции двухсимвольных ошибок. Мы выразим полиномиальный генератор через 2t = п - k = 4 корня следующим образом

P( X ) ( X )( X			2 )( X	3 )( X	4 )
( X 2	(	2 ) X	3 )( X 2	( 3	4 ) X	7 )
( X 2	4 X	3 )( X 2	6 X	0 )		(4.39)
X 4	( 4	6 ) X 3 ( 3		10 0 ) X 2 ( 4		9 ) X 3
X 4	3 X 3	0 X 2	1 X	3.

Поменяв порядок расположения членов полинома на обратный и заменив знаки "минус" на "плюс", так как над двоичным полем +1 = -1, полиномиальный генератор Р(X) можно будет представить следующим образом

P(X ) 3 1X 0 X 2 3 X 3 X 4.

(4.40)

Кодирование в систематической форме.

Так как код Рида-Соломона является циклическим, кодирование в систематической форме аналогично процедуре двоичного кодирования, разработанной в разделе, посвященном циклическим кодам. Мы можем осуществить сдвиг полинома сообщения D(Х) в крайние правые k разряды регистра кодового слова и произвести последующее прибавление полинома четности (или остатка от деления) R(Х) в крайние левые n-k разряды. Поэтому мы умножаем D(Х) на X n k , проделав алгебраическую операцию таким образом, что D(Х) оказывается сдвинутым вправо на п - k позиций. В разделе посвященном циклическому кодированию это показано на примере двоичного кодирования. Далее мы делим X n k D(X) на полиномиальный генератор Р(X), что можно записать следующим образом

	X n k D( X )	Q( X )	R( X )	, или
	P( X )		P( X )

(4.41)

X n k D( X ) Q( X )P( X ) R( X ).

134

Здесь Q(X) и R(Х) — это частное и остаток от полиномиального деления. Как и в случае двоичного кодирования, остаток будет четным. Уравнение (4.41) можно переписать следующим образом

R(X ) X n k D(X ) по модулю P(X ).

(4.42)

Результирующий полином кодового слова T(X), с учетом уравнений (4.41) и (4.42), можно переписать следующим образом

T (X ) R(X ) X n k D(X ).

(4.43)

Продемонстрируем шаги, подразумеваемые уравнениями (4.42) и (4.43), закодировав в соответствии с рисунком 4.13 сообщение из трех символов

010	010	010	(4.44)
1	3	5

с помощью кода Рида-Соломона (7,3), генератор которого определяется уравнением (4.40).

Сначала мы

умножаем

(сдвиг

вверх)

полином

сообщения

D(X )

1X 0

3 X

5 X 2

на

X n k

X 4 ,

что

дает

X n k D(X )

1X 4

3 X 5

5 X 6 .

Далее поделим

такой

сдвинутый

вверх

полином

сообщения

на

полиномиальный

генератор

из

уравнения

(4.40),

P(X )

3

1X

0 X 2

3 X 3

X 4 .

Полиномиальное

деление

недвоичных

коэффициентов – это еще более утомительная процедура, чем ее двоичный аналог (см. пример в подразделе по циклическому кодированию), поскольку операции сложения (вычитания) и умножения (деления) для них выполняются согласно таблиц 4.8 и 4.9. Для рассматриваемого случая полиномиальное деление даст в результате следующий полиномиальный остаток (полином четности):

R(X ) 0 2 X 4 X 2 6 X 3.

(4.45)

Затем, из уравнения (4.43), полином кодового слова можно записать следующим образом

T(X ) 0 2 X 4 X 2 6 X 3 1X 4 3 X 5 5 X 6. (4.46)

Систематическое кодирование с помощью (n-k) разрядного регистра сдвига.

135

Как показано на рисунке 4.15, кодирование последовательности из 3-х символов в систематической форме на основе кода Рида-Соломона (7, 3), определяемого генератором Р(X) из уравнения (4.40), требует реализации регистра сдвига с обратными связями (LFSR). Нетрудно убедиться, что элементы умножителя на рис. 4.15, взятые справа налево, соответствуют коэффициентам полинома в уравнении (4.40). Этот процесс кодирования является недвоичным аналогом циклического кодирования, которое описывалось выше. Здесь, в соответствии с алгоритмом кодирования для кода Рида-Соломона ненулевые

кодовые слова образованы 2m		1	7 символами,	и каждый символ состоит из т
= 3 бит.
X0	X1	X2	X3 2	X4
			1	П1

								2	Выходная
									П2 последователь
Входная последовательность символов сообщения									ность кодовых
								1	символов
0	1	0	0	1	0	0	1	0

Рис. 4.15 Кодер для кода (7, 3) Рида-Соломона

Следует отметить сходство между рисунками 4.15 и 4.7. В том и другом случаях количество разрядов в регистре равно п - k. Рисунок 4.7 для циклического кодирования отображает пример двоичного кодирования, где каждый разряд содержит 1 бит. В данном разделе приведен пример недвоичного кодирования, так что каждый разряд регистра сдвига, изображенного на рис. 4.15, содержит 3-битовый символ. На рис. 4.7 коэффициенты, обозначенные А1, А2, ..., являются двоичными. Поэтому они принимают одно из значений 0 или 1, просто указывая на наличие или отсутствие связи в LFSR. На рис. 4.15 каждый коэффициент является 3- битовым, так что они могут принимать одно из 8 значений.

Недвоичные операции, осуществляемые кодером, показанным на рис, 4.15, создают кодовые слова в систематической форме, так же как и в двоичном случае.

Эти операции определяются следующими шагами:

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

136

2.В течение первых k m тактовых импульсов переключатель 2 находится в положении 1, что обеспечивает одновременную передачу всех символов сообщения непосредственно на регистр выхода (на рис. 3.19 не показан);

3.После передачи k - го символа на регистр выхода, переключатели 1 и 2, переходят в положение 2;

4.Остальные (n - k) m тактовых импульсов очищают контрольные символы, содержащиеся в регистре, подавая их на регистр выхода;

5.Общее число тактовых импульсов равно n m, и содержимое регистра

выхода является полиномом кодового слова R(X ) X n k D(X ) , где

R(X) представляет собой кодовые символы, а D(Х) – символы сообщения в полиномиальной форме.

Для проверки возьмем ту же последовательность символов, что и в выражении (3.53).

Здесь крайний правый символ является самым первым и крайний правый бит также является самым первым. Последовательность действий в течение первых k = 3 m тактовых сдвигов в цепи кодирования на рис. 4.15 будет иметь вид, представленный в таблице 4.10.

Таблица 4.10 Последовательность действий в кодере, представленном на рисунке 4.15

	Очередь ввода					Такт			Содержимое регистра					Обратная
														связь
1		3		5		0		0		0	0		0	5
		1		3		1		1		6	5		1	0
				1		2		3		0	2		2	4
				–		3		0		2	4		6	–
	Как можно видеть, после третьего такта регистр содержит четыре
контрольных символа,					0 , 2 , 4 и			6. Затем переключатели 1 и 2 переходят в

положение 2, и контрольные символы, содержащиеся в регистре, подаются на выход. Поэтому выходное кодовое слово, записанное в полиномиальной форме, можно представить в следующем виде:

	6	X n ,
T ( X )	t
	n
	n 0
T ( X )	0	2 X	4 X 2	6 X 3 1 X 4 3 X 5	5 X 6	(4.47)
(100)	(001) X		(011) X 2	(101) X 3 (010) X 4	(110) X 5	(111) X 6.

137

Процесс проверки содержимого регистра во время разных тактов несколько сложнее, чем в случае бинарного кодирования. Здесь сложение и умножение элементов поля должны выполняться согласно табл. 4.8 и 4.9.

Корни полиномиального генератора Р(X) должны быть и корнями кодового слова, генерируемого Р(X), поскольку правильное кодовое слово имеет следующий вид:

T (X ) D(X ) P(X ).

(4.48)

Следовательно, произвольное кодовое слово, выражаемое через корень генератора Р(X), должно давать нуль. Представляется интересным, действительно ли полином кодового слова в уравнении (4.47) дает нуль, когда он выражается через какой-либо из четырех корней Р(X). Иными словами, это означает проверку следующего:

T( ) T( 2 ) T( 3 )	T( 4 ) 0.	(4.49)
Подставим в (4.47) вместо Х значения	i из (4.49) и независимо выполнив

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

T (	)	0	3	6	9	5		8	11
	0	3	6	2	5	1		4
	1	0	6	4	3	3	0.
T ( 2 )		0	4	8	12		9	13	17
	0	4	1	5	2	6		3
	5	6	0	3	1	1	0.
T (	3 )	0	5	10	15		13	18	23
	0	5	3	1	6	4		2
	4	0	3	2	5	5	0.
T (	4 )	0	6	12	18		17	23	29
	0	6	5	4	3	2		1
	2	0	5	1	6	6	0.

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

4.6.3 Декодирование Рида-Соломона

138

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

	6
E( X )	E X n .		(4.50)
		n
	n 0
Пусть двухсимвольная ошибка будет такой, что
E( X ) 0 0X 0X 2 2 X 3	5 X 4	0X 5 0X 6
			(4.51)
(000) (000) X (000) X 2 (001) X 3		(111) X 4 (000) X 5	(000) X 6.

Другими словами, один контрольный символ искажен 1-битовой ошибкой (представленной как 2 ), а один символ сообщения – 3-битовой ошибкой (представленной как 5). В данном случае принятый полином поврежденного кодового слова Z(Х) представляется в виде суммы полинома переданного кодового слова и полинома модели ошибки

Z(X ) T (X ) E(X ).

(4.52)

Следуя уравнению (4.52), мы суммируем Т(X) из уравнения (4.47) и Е(Х) из уравнения (4.51) и имеем следующее

Z ( X ) (100)	(001) X	(011) X 2	(100) X 3	(101) X 4 (110) X 5 (111) X 6
				(4.53)
0	2 X 4 X 2	0 X 3	6 X 4	3 X 5 5 X 6.

В данном примере исправления 2-символьной ошибки (т.е. исправления ошибок в двух символах) имеется четыре неизвестных – два относятся к расположению ошибки, а два касаются ошибочных значений. Отметим важное различие между недвоичным декодированием Z(Х), которое представлено в уравнении (4.53), и двоичным. При двоичном декодировании декодеру нужно знать лишь расположение ошибки. Если известно, где находится ошибка, бит нужно поменять с 1 на 0 или наоборот. Но здесь недвоичные символы требуют, чтобы мы не только узнали расположение ошибки, но и определили правильное значение символа, расположенного на этой позиции. Поскольку в данном

139

примере у нас имеется четыре неизвестных, нам нужно четыре уравнения, чтобы найти их.

Вычисление синдрома.

Напомним, что синдром – это результат проверки четности, выполняемой над Z, чтобы определить, принадлежит ли Z набору кодовых слов. Если Z является членом набора, то синдром S имеет значение, равное 0. Любое ненулевое значение S означает наличие ошибок. Точно так же, как и в двоичном случае, синдром S состоит из n - k символов, {Si,} (i = 1, ..., n - k). Таким образом, для нашего кода (7, 3) имеется по четыре символа в каждом векторе синдрома; их значения можно рассчитать из принятого полинома Z(Х). Заметим, как облегчаются вычисления благодаря самой структуре кода, определяемой уравнением (4.48).

T (X ) D(X ) P(X ).

(4.54)

Из этой структуры можно видеть, что каждый правильный полином кодового слова T(X) является кратным полиномиальному генератору P(X). Следовательно, корни P(X) также должны быть корнями T(X). Поскольку Z(Х) = T(X) + E(Х), то Z(Х), вычисляемый с каждым корнем P(X), должен давать нуль, только если Z(Х) будет правильным кодовым словом. Любые ошибки приведут в итоге к ненулевому результату в одном (или более) случае. Вычисления символов синдрома можно записать следующим образом

S Z(X )			i Z( i ), i 1,...,n k.	(4.55)
i		X

В рассматриваемом примере, как было показано в уравнении (4.53), Z(Х) содержит 2-символьные ошибки. Если Z(Х) окажется правильным кодовым словом, то это приведет к тому, что все символы синдрома Si, будут равны нулю. В данном примере четыре символа синдрома находятся следующим образом

		S1	Z ( )		0	3	6	3	10	8	11
											(4.56)
			0	3	6	3	3	1	4	3 ,
S		2	Z ( 2 )		0	4	8	6	14	13	17
											(4.57)
			0	4	1	6	0	6	3	5 ,
S	3		Z (	3 )	0	5	10	9	18	18	23
											(4.58)
		0		5	3	2	4	4	2	6 ,

140