Ташатов Н.Н.

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

логическая схема для реализации деления многочленов в циклических кодах

Важнейшее преимущество циклических кодов по сравнению с другими методами кодирования заключается в простоте их технической реализации. Использование в схемах кодеров и декодеров регистров сдвига с обратными связями, позволяет просто и достаточно эффективно защищать от ошибок информационные массивы большой длины. Процедура деления многочленов является основной в кодерах и декодерах циклических кодов [1]. Пусть даны два многочлена V(X) и g(X), где

. (1)

. (2)

причем т > р. Схема деления, приведенная на рисунке 1, выполняет деление многочлена V(X) на g(X), определяя частное и остаток от деления

. (3)

Рисунок 1 – Логическая схема для реализации деления многочленов

Разряды регистра в исходном состоянии содержат нули. Коэффициенты V(X) поступают и продвигаются по регистру сдвига по одному за такт, начиная с коэффициентов более высокого порядка. Частное после р-го сдвига на выходе равно . Получаем слагаемое наивысшего порядка в частном. Затем из делимого для каждого коэффициента частного q_i вычитаем многочлен . Это вычитание обеспечивает обратная связь, показанная на рисунке 2. В делимом остается разность крайних слева р слагаемых, а слагаемое обратной связи формируется при каждом сдвиге схемы и отображается в виде содержимого регистра. При каждом сдвиге регистра разность смещается на один разряд. Слагаемое наивысшего порядка, которое по построению схемы равно нулю, удаляется, в то время как следующий значащий коэффициент в V(X) перемещается на его место. После всех m + 1 сдвигов регистра, на выход последовательно выдается частное, а остаток остается в регистре [2, 3].

Рассмотрим схему деления многочленов, используя рисунок 1. Пусть , т.е. V = 0001011, и . Разделим V(X) на g(X). Схема деления должна выполнить следующее действие

. (4)

Необходимый регистр сдвига с обратной связью показан на рисунке 2.

Рисунок 2 – Схема деления для примера

Пусть первоначально регистр содержит нули. Схема выполнит следующие шаги.

Входная очередь	Номер сдвига	Содержимое регистра	Выход и обратная связь
0001011	0	000	-
000101	1	100	0
00010	2	110	0
0001	3	011	0
000	4	011	1
00	5	111	1
0	6	101	1
-	7	100	1

После четвертого сдвига коэффициенты частного , которые последовательно поступали с выхода, равны 1111. Тогда многочлен частного имеет следующий вид . Коэффициенты остатка имеют вид 100, т.е. многочлен остатка имеет вид p(X) = 1. Схема выполнила следующее вычисления [1, 2]

. (5)

Прямое деление многочленов дает тот же результат.

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

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

2. Вернер М. Основы кодирования. Москва: Техносфера, 2004. – 288 с.

3. Березюк Н.Т., Андрущенко А.Г., Мощицкий С.С. Кодирование информации (двоичные коды). Харьков, издательское объединение «Вища школа», 1978, 252 с.

4. Ташатов Н.Н. Систематические линейные блочные коды с контролем четности. // Вестник ПГУ им. С.М. Торайгырова. – 2007. – № (в печати).