Ташатов Н.Н.
Евразийский национальный университет им. Л.Н.
Гумилева, г. Астана
логическая схема для
реализации деления многочленов в циклических кодах
Важнейшее преимущество циклических кодов по
сравнению с другими методами кодирования заключается в простоте их технической
реализации. Использование в схемах кодеров и декодеров регистров сдвига с
обратными связями, позволяет просто и достаточно эффективно защищать от ошибок
информационные массивы большой длины. Процедура деления многочленов является
основной в кодерах и декодерах циклических кодов [1]. Пусть даны два
многочлена V(X) и g(X),
где
.
(1)
. (2)
причем
т > р. Схема
деления, приведенная на рисунке 1, выполняет деление многочлена V(X) на g(X),
определяя частное и остаток от деления
. (3)
Рисунок 1 – Логическая
схема для реализации деления многочленов
Разряды регистра в исходном состоянии содержат
нули. Коэффициенты V(X) поступают
и продвигаются по регистру сдвига по одному за такт,
начиная с коэффициентов более высокого порядка. Частное после р-го сдвига на выходе равно . Получаем слагаемое наивысшего порядка в
частном. Затем из
делимого для каждого коэффициента частного qi вычитаем
многочлен
. Это вычитание обеспечивает обратная связь,
показанная на рисунке 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. – № (в
печати).