636_Nosov_V.I._Seti_radiodostupa_CH.1_

23 D(X)

X6 + + X4

X3 + X2 + 1

P(X)

X6 + X5 +

X3

X3 + X2 + 1

Q(X)

X5 + X4 + X3

X5 + X4 +

X2

X3 + X2

X3 + X2

+ 1

1

R(X)

Рис. 4.9 Получение остатка от деления на порождающий полином

Z(X)

X6

X3 + X2 + 1

P(X)

X6 + X5 +

X3

X3 + X2 + 1

Q(X) + B(X)

X5 + + X3

X5 + X4		+	X2
	X4	+ X3 + X2
	X4 + X3 +			X
			X2	+ X			S(X)

Рис. 4.10 Получение синдрома ошибки

Таким образом, значение синдрома для рассматриваемого случая S = 110. Остальные значения синдрома, приведенные в таблице 4.4 б, вычисляются аналогично.

Теперь предположим, что на приемной стороне был получен блок

1101101,

или Z(X ) X 6

X 5 X 3 X 2

1. Используя

уравнение (4.19),

получим значение синдрома рисунок 4.11.

Z(X)

X6

+ X5 +

X3 + X2 + 1

X3 + X2 + 1

P(X)

X6

+ X5 +

X3

X3 + X2 + 1

B(X)

X2 + 1

S(X)

Рис. 4. 11 Получение синдрома из Z(X)

Следовательно, значение синдрома S = 101. Используя данные таблицы

4.4 б, получим Е = 0001000. Тогда T 1101101 0001000 1100101. Поэтому,

согласно таблице 4.4 а, был передан блок данных 1100.

4.4 Код Голея

121

Код Голея - это двоичный линейный код (23, 12) с dmin = 7.

Одним из наиболее практичных блочных кодов является расширенный двоичный линейный код Голея (24, 12) с dmin=8 получается из кода Голея путем добавления ко всем кодовым комбинациям проверочного символа.

Таблица 4.4 Циклический код (7, 4) с коррекцией однобитовых ошибок

а) Таблица используемых кодовых слов
Блок данных		Кодовое слово
0000	0000000
0001	0001101
0010	0010111
0011	0011010
0100	0100011
0101	0101110
0110	0110100
0111	0111001
1000	1000110
1001	1001011
1010	1010001
1011	1011100
1100	1100101
1101	1101000
1110	1110010
1111	1111111
б) Таблица синдромов, соответствующих однобитовым ошибкам
Ошибочная комбинация		Синдром
0000001		001
0000010		010
0000100		100
0001000		101
0010000		111
0100000		011
1000000		110

Использование расширенного кода Голея (24, 12) дает скорость

кодирования R	1	, реализовать которую проще (с точки зрения
c	2

использования двоичной логики), чем обычный код Голея (23, 12) со скоростью

кодирования Rc	12	23	. Расширенный код Голея значительно мощнее

рассмотренного ранее кода Хэмминга. Цена, которую приходится платить за повышение эффективности кода, заключается в более сложном декодере и,

122

соответственно, более высокой скорости передачи и более широкой полосе, занимаемой сигналом. Для расширенного кода Голея dmin 8 , поэтому, исходя

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

Линейный код Голея (23, 12) можно генерировать посредством порождающего полинома

P(X ) X11 X 9 X 7 X 6 X 5 X 1.

4.5 Коды БЧХ

Коды Боуза-Чоудхури-Хоквенгема (Bose-Chadhuri-Hocquenghem — ВСН, БЧХ) являются результатом обобщения кодов Хэмминга, которое позволяет исправлять множественные ошибки. Они составляют мощный класс циклических кодов, который обеспечивает достаточную свободу выбора длины блока, степени кодирования, размеров алфавита и возможностей коррекции ошибок.. Коды БЧХ очень важны, поскольку при блоках, длина которых равна порядка несколько сотен бит, коды БЧХ превосходят своими качествами все другие блочные коды с той же длиной блока и степенью кодирования. В наиболее часто применяемых кодах БЧХ используется двоичный алфавит и блок кодового слова

Длина блока	n = 2m -1
Количество контрольных битов	n – k	mt
Минимальное расстояние	dmin	2t +1

С помощью такого кода можно исправить все слова, содержащие t (или менее) ошибок. Порождающий многочлен кода БЧХ можно создать в

соответствии с (3.24) и (3.25) из множителей полинома (X 2m 1 1) .
В таблице 4.5 приведены параметры кодов БЧХ (n, k, t) для 7 n			255.
В таблице 4.6 приводятся наиболее часто употребляемые при создании
кодов БЧХ генераторные (производящие) полиномы P( X ) с разными
значениями n,k и t	для блоков длиной до 255.	Коэффициенты полиномов
P( X ) представлены	многочленом, двоичными и	восьмеричными	числами.

Восьмеричные числа оформленными так, что при преобразовании их в двоичные символы крайние правые разряды отвечают коэффициенту нулевой степени в P( X ) . С помощью таблицы 4.5 можно легко проверить свойство

циклического кода – генераторный полином имеет порядок (п – k)

123

Так, коэффициентами порождающего полинома для кода (15, 5, 3) в восьмеричной форме является число 2467, что соответствует двоичной форме 10 100 110 111. В результате перехода от записи двоичной формы

представления порождающего полинома к записи многочлена получим

					X (P) X10		X 8	X 5	X 4	X 2	X 1.
	Таблица 4.5 Параметры кодов БЧХ
n	k	t		n	k	t	n	k	t	n	k	t	n	k	t
7	4	1	63		30	6	127	64	10	255	207	6	255	99	23
15	11	1			24	7		57	11		199	7		91	25
	7	2			18	10		50	13		191	8		87	26
	5	3			16	11		43	14		187	9		79	27
31	26	1			10	13		36	15		179	10		71	29
	21	2			7	15		29	21		171	11		63	30
	16	3	127		120	1		22	23		163	12		55	31
	11	5			113	2		15	27		155	13		47	42
	6	7			106	3		8	31		147	14		45	43
63	57	1			99	4	255	247	1		139	15		37	45
	51	2			92	5		239	2		131	18		29	47
	45	3			85	6		231	3		123	19		21	55
	39	4			78	7		223	4		115	21		13	59
	36	5			71	9		215	5		107	22		9	63

Таблица 4.6 Порождающие многочлены кодов БЧХ

							Порождающий полином
n	k	t			многочлен					Двоичный код	Восьмеричный
											код
7	4	1	X 3	X	1					1011	13
15	11	1	X 4	X	1					10011	23
15	7	2	X 8	X 7	X 6	X 4	1			111010001	721
15	5	3	X 10	X 8	X 5	X 4	X 2	X	1	10100110111	2467
31	26	1	X 5	X 2	1					100101	45
31	21	2	X 10	X 9	X 8	X 6	X 5	X 3	1	11101101001	3551
31	16	3									107657
31	11	5									5423325
31	6	7									313365047
63	57	1	X 6	X	1					1000011	103
63	51	1									12471

Более полный список порождающих полиномов для кодов БЧХ можно найти в [20].

124

Для декодирования сигналов кода БЧХ можно использовать поиск в таблицах разрешенных кодовых слов и синдромов ошибок (подобных таблице 4.4 для циклического кода (7, 4)). На настоящее время разработано достаточно большое количество алгоритмов, требующих меньше памяти, чем прямой поиск в таблице. Однако сложность этих алгоритмов увеличивается как квадрат количества ошибок, которые нужно исправить.

4.6 Коды Рида-Соломона

Коды Рида-Соломона (Reed-Solomon codes – RS codes) – это широко используемый подкласс недвоичных кодов БЧХ.

Длина символа	m бит
Длина блока	n = (2m -1) символов = m(2m -1) бит
Длина блока данных	k символов
Размер контрольного кода	n – k = 2t символов = m(2t) бит
Минимальное расстояние	dmin = (2t + 1) символов

При использовании кодов Рида-Соломона данные обрабатываются порциями по m бит, именуемыми символами. Код (n, k) характеризуется следующими параметрами

Таким образом, алгоритм кодирования расширяет блок k символов до размера n , добавляя (n – k) избыточных контрольных символов. Как правило, m > 1 является степенью 2, широко используется значение m = 8.

Коды Рида-Соломона удобны для исправления пакетов ошибок. Данный тип кодов характеризуется высокоэффективным использованием избыточности, длина блоков и размеры символов могут легко приспосабливаться под сообщения разных размеров. Кроме того, для таких кодов существуют эффективные методы кодирования.

Коды Рида-Соломона (n, k) определены на m-битовых символах при всех n и k , для которых

0 k n 2m 2,

(4.22)

Где k число информационных бито, подлежащих кодированию, а n – число бит в закодированном блоке. Для большинства кодов Рида-Соломона (n, k)

(n,k) (2m 1,2m 1 2t),

(4.23)

125

где t – количество ошибочных бит в символе, которые может исправить код, а n

–k = 2t – число контрольных символов. Расширенный код Рида-Соломона можно получить только при n = 2m или n = 2m + 1.

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

dmin n k 1.

(4.24)

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

t	dmin 1		n k	.	(4.25)
	2		2

Здесь x означает наибольшее целое, не превышающее х. Из (4.25) видно, что

коды Рида-Соломона, исправляющие t символьных ошибок, требуют не более 2t контрольных символов. Следовательно, декодер имеет n – k «используемых» избыточных символов, количество которых вдвое превышает количество исправляемых ошибок. Для каждой ошибки один избыточный символ используется для обнаружения ошибки и один для определения правильного значения.

Преимущества недвоичных кодов, подобных кодам Рида-Соломона, можно показать следующим образом. Рассмотрим двоичный код (n, k) = (7, 3). Полное количество кодовых слов в нем равно 2n = 27 = 128, из которых 2k = 23 = 8 (или 1/16 часть всех кодовых слов) являются разрешенными кодовыми словами.

Теперь рассмотрим недвоичный код (n, k) = (7,3), где каждый символ состоит из m =3 бит. Полное количество кодовых слов в таком коде равно 2nm = 221 = 2 097 152 , из которых 2km =29 = 512 (или 1/4096 часть всех кодовых слов, т.е очень небольшая часть) являются разрешенными кодовыми словами.

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

Рассмотрим на примере способность кода Рида-Соломона исправлять пакеты ошибок, которые могут быть вызваны либо импульсными помехами, либо глубокими замираниями сигнала в радиотракте. [18].

Возьмем для примера код (n, k) = (255,247), в котором каждый символ состоит из т = 8 бит (такие символы принято называть байтами). Поскольку п - k= 8, из уравнений (4.24) и (4.25) можно видеть, что этот код может исправлять любые 4-символьные ошибки в блоке длиной до 255

126

символов. Пусть блок длительностью 25 бит в ходе передачи поражается помехами, как показано на рисунке 4.12. В этом примере импульсная помеха или глубокое замирание сигнала попадает на 25 последовательных битов и исказит точно 4 символа. Декодер для кода (255, 247) исправит любые 4-символьные ошибки без учета характера повреждений, причиненных символу. Другими словами, если декодер исправляет байт (заменяет неправильный правильным), то ошибка может быть вызвана искажением одного или всех восьми битов. Поэтому, если символ неправильный, он может быть искажен на всех двоичных позициях.

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

25-битовый пакет ошибок

Символ	Символ	Символ	Символ	Символ	Символ
1	2	3	4	5	6
Норма	Искажен	Искажен	Искажен	Искажен	Норма

Рис. 4.12 Блок данных, искаженный 25-битовым пакетом ошибок

В этом примере, если будет наблюдаться воздействие аддитивного белого гауссовского шума, 25-битовая случайная ошибка может исказить более чем 4 символа (искаженными могут оказаться до 25 символов). Конечно, исправление такого числа ошибочных символов окажется вне возможностей кода (255, 247).

4.6.1 Конечные поля

Для понимания принципов кодирования и декодирования недвоичных кодов, таких как коды Рида-Соломона, нужно сделать экскурс в понятие конечных полей, известных как поля Галу a (Galois fields — GF). Для любого простого числа р существует конечное поле, которое обозначается GF(p) и содержит р элементов. Понятие GF(p) можно обобщить на поле из рт элементов, именуемое полем расширения GF(p); это поле обозначается GF(pm), где m — положительное целое число. Заметим, что GF(pm) содержит в качестве подмножества все элементы GF(p). Символы из поля расширения GF(2m) используются при построении кодов Рида-Соломона.

Двоичное поле GF(2) является подполем поля расширения GF(2m), точно так же как поле вещественных чисел является подполем поля комплексных чисел. Кроме чисел 0 и 1, в поле расширения существуют дополнительные однозначные элементы, которые будут представлены новым символом . Каждый ненулевой элемент в GF(2m) можно представить как степень . Бесконечное множество элементов, F, образуется из стартового множества

127

{0,1,	} и генерируется	дополнительными		элементами	путем
последовательного умножения последней записи на .
	F 0,1, , 2 ,...,	j ,...	0, 0 , 1,	2 ,..., j ,... .	(4. 26)

Для вычисления из F конечного множества элементов GF(2m) на F нужно наложить условия: оно может содержать только 2m элемента и быть замкнутым относительно операции умножения. Условие замыкания множества элементов поля по отношению к операции умножения имеет вид нередуцируемого полинома

(2m	1)	1	0
или, что то же самое			(4.27)
(2m 1)		1	0 .

С помощью полиномиального ограничения любой элемент со степенью, большей или равной 2m-1, можно следующим образом понизить до элемента со степенью, меньшей 2m-1:

(2m n)

(2m 1) n 1

n 1.

(4.28)

Таким образом, как показано ниже, уравнение (4.27) можно использовать для формирования конечной последовательности F* из бесконечной последовательности

F.

F	0,1,	1, 2 ,...,	2m 2 ,	2m 1,	2m ,...	(4.29)
	0,	0 , 1, 2 ,...,	2m 2 ,,...
Следовательно, из уравнения (4.29) можно видеть, что элементы
конечного поля GF(2m) даются следующим выражением:
GF (2m )		0, 0 , 1,	2 ,...,	2m 2	.	(4.30)

Операция сложения в поле расширения GF(2m).

Каждый из 2т элементов конечного поля GF(2m) можно представить как отдельный полином степени (т - 1) или меньше. Степенью полинома называется степень члена максимального порядка. Обозначим каждый ненулевой элемент

128

GF(2m) полиномом аi(Х), в котором по крайней мере т коэффициентов аi (Х) ненулевые. Для i = 0, 1, 2, ..., 2 m - 2 получим

i	a (X )	a	a	X	a	X 2 ...	a	X m 1.	(4 . 31)
	i	i,0	i,1		i,2		i,m 1
Рассмотрим случай с m = 3, в котором конечное поле обозначается GF(23). На
рисунке 4.13 показано отображение семи элементов {							i} и нулевого элемента в
слагаемые базисных элементов {Х0, X1, X2}, описываемых уравнением (4.31).
Поскольку из уравнения (3.36)		0	7 , в этом поле имеется семь ненулевых

элементов или всего восемь элементов. Каждая строка на рис. 4.13 содержит последовательность двоичных величин, представляющих коэффициенты ai,0 ,ai,1,ai,2 из уравнения (4.31).

Одним из преимуществ использования элементов { i} поля расширения, вместо двоичных элементов, является компактность записи, что оказывается удобным при математическом описании процессов недвоичного кодирования и декодирования. Сложение двух элементов конечного поля, следовательно, определяется как суммирование по модулю 2 всех коэффициентов при элементах одинаковых степеней.

i

j (a

a

j,0

)

(a

a

j,1

)X

... (a

a

j,m 1

)X m 1. (4.32)

i,0

i,1

i,m 1

Описание конечного поля с помощью примитивного полинома.

Класс полиномов, называемых примитивными полиномами, интересует нас, поскольку такие объекты определяют конечные поля GF(2m), которые, в свою очередь, нужны для описания кодов Рида-Соломона. Следующее утверждение является необходимым и достаточным условием примитивности полинома. Нередуцируемый полином f(X) порядка т будет примитивным, если наименьшим положительным целым числом n, для которого Xm + 1 делится на f(X), будет п = 2т- 1. Заметим, что нередуцируемый полином – это такой полином, который нельзя представить в виде произведения полиномов меньшего порядка; делимость А на В означает, что А делится на В с нулевым остатком и ненулевым частным.

Поле расширения GF(23).

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

там полиномов, f (X ) 1 X X 3 , который определяет конечное поле GF(2m), где степень полинома равна m = 3. Таким образом, в поле, определяемом полиномом f ( X ) , имеется 2m 23 8 элементов.

129

Поиск корней полинома f ( X )		–	это поиск таких значений Х, при которых
f ( X )	0 . Привычные нам двоичные элементы 0 и 1 не подходят полиному
f (X )	1 X X 3 (они не являются его корнями), поскольку f(1) = 0 f(0) = 1 (в
рамках операций по модулю 2).
		Образующие
		элементы
		X0	X1	X2
	0	0	0	0
	Э	1	0	0
	л
	е	0	1	0
	м
	е	0	0	1
	н
	т	1	1	0
	ы
		0	1	1
	п
	о	1	1	1
	л
	я	1	0	1
		1	0	0

Рис. 4. 13 Отображение элементов поля в базисные элементы GF(8) с помощью f(X) = 1 + X + X2

Кроме того, основная теорема алгебры утверждает, что полином порядка m должен иметь в точности m корней. Следовательно, в этом примере выражение f ( X ) должно иметь три корня. Возникает определенная проблема,

поскольку 3 корня не лежат в том же конечном поле, что и коэффициенты f ( X ) . Исходя из сказанного, для рассматриваемого примера можно записать

f ( ) 0

1	3	0	(4.33)

3 1

Поскольку при операциях над двоичным полем +1 = -1, то 3 можно представить следующим образом

3	1 .	(4.34)

130