Ташатов Н.Н.

Евразийский национальный университет им. Л.Н. Гумилева, г. Астана

систематическое кодирование кодов

рида – соломона с помощью (n – k)-разрядного регистра сдвига

Отображение элементов поля в базисные элементы, которое описывается уравнением

, (1)

можно показать с помощью схемы линейного регистра сдвига с обратной связью (linear feedback shift register – LFSR). Эта схема показана на рисунке 1.

Рисунок 1 – Отображение элементов поля в базисные элементы с помощью схемы линейного регистра сдвига с обратной связью, построенного на примитивном многочлене

При т = 3 схема генерирует 2^т – 1 ненулевых элементов поля. Как и в случае двоичных циклических кодов, обратная связь, показанная на рисунке 1, соответствует коэффициентам многочлена f(Х) = 1 +Х + Х³. Как показано на рисунке 2, кодирование последовательности из 3 символов в систематической форме на основе кода Рида-Соломона (7, 3), определяемого генератором g(X) из уравнения

, (2)

требует реализации регистра LFSR [1]. Видно, что элементы умножителя на рисунке 2, взятые справа налево, соответствуют коэффициентам многочлена в уравнении (2). Этот процесс кодирования является недвоичным аналогом циклического кодирования. Здесь, в соответствии с уравнением cверточных кодов Рида-Соломона (n, k), ненулевые кодовые слова образованы 2^m – 1 = 7 символами, и каждый символ состоит из m = 3 бит [1, 2].

Рисунок 2 – Кодер линейного регистра сдвига с обратной связью

LFSR для кода (7, 3)

Здесь приведен пример недвоичного кодирования, так что каждый разряд регистра сдвига, изображенного на рисунке 2, содержит 3-битовый символ. Т.к. каждый коэффициент является 3-битовым, то они могут принимать одно из 8 значений.

Недвоичные операции, осуществляемые кодером, показанным на рисунке 2, создают кодовые слова в систематической форме, так же как и в двоичном случае [3]. Эти операции определяются следующими шагами.

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

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

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

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

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

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

Крайний правый символ здесь является самым первым, и крайний правый бит также является самым первым. Последовательность действий в течение первых k = 3 сдвигов в цепи кодирования на рисунке 2 будет иметь следующий вид.

Таблица 1

Очередь ввода			Такт	Содержимое регистра				Обратная связь
			0	0	0	0	0
			1
			2		0
		-	3					-

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

,

(3)

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

Таблица 2. Таблица сложения для GF(8) при f(Х) = 1 + X + X³

	0
		0
			0
				0
					0
						0
							0

Таблица 3. Таблица умножения для GF(8) при f(Х) = 1 + X + X³

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

U(X) = m(X)g(X). (4)

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

.

Выполнив вычисления для разных корней, получим следующее:

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

СПИСОК ЛИТЕРАТУРЫ

1. Скляр Б. Цифровая связь. Теоретические основы и практическое применение. Изд. 2-е, испр.: Пер. с англ. – Издательский дом «Вильямс», 2004. – 1104 с. ил.

2. Садыков А.А., Ташатов Н.Н., Бекманова Г.Т. Корректирующее (восстанавливающее) кодирование информации. Коды Рида-Соломона и вероятность появления ошибок. // Вестник ЕНУ им. Л.Н. Гумилева. – 2007. - №2. – с.69-74.

3. Ташатов Н.Н. Кодирование циклических кодов в систематической форме. // Материалы II Международной научно-практической конференции «Научный прогресс на рубеже тысячелетий - 2007», 1-15 июня 2007г., Днепропетровск (Украина) – Белгород (Россия), т.12, с. 12-14.