Умножитель разреженных полиномов

 

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных комплексах и специализированных устройствах, в частности в устройствах цифровой обработки сигналов. Цель изобретения - повышение быстродействия умножителя. Данный умножитель реализует операцию умножения .полиномов, представленных в виде списка пар, состоящих из ненулевого коэффициента и соответствующего ему показателя степени переменной. Умножитель разреженных полиномов содержит матрицу 1 сортирующих ячеек, формирователь 2 импульсов и узел 5 вывода полинома. 7 ил., 1 табл.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТЬН=СНИХ

РЕСПУБЛИН (51}5 С 06 F 15/31

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н A BT0PCHGMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР (21) 4634424/24 (22) 09.01.89 (46) 15.05.91. Бюл. ь. 18 (71) физико-механический институт им. Г.В. Карпенко (72) А.Е. Батюк, В,В. Грицык, В.П. Кожан и С.П. Стрямец (53) 681.32 (088.8) (56) Авторское свидетепьство СССР

Р 997039, кл. G 06 Г 15/31, 1983.

Авторское свидетельство СССР

У 4351529/24, кл. С 06 F 15/31, 1988. (54). УМНОЖИТЕЛЬ РАЗРЕЖЕННЫХ ПОЛИНОМОВ (57) Изобретение относится к вычислительной технике и может быть ис„„SU„„1649564 д 1 пользовано в цифровых вычислительных комплексах и специализироваHHbLx устройствах, в частности в устройст-. вах цифровой обработки сигналов.

Цель изобретения — повьппение быстродействия умножителя. Данный умножитель реализует операцию умножения полиномов, представленных в виде списка пар, состоящих из ненулевого коэффициента и соответствующего ему показателя степени переменной. Умножитель разреженных полиномов содержит матрицу 1 сортирующих ячеек, формирователь 2 импульсов и узел 5 . вывода полинома. 7 ил., 1 табл.

1649564 (а„b, .

+q), i,г=1,k

Из обреTi" HHP. ОтнОситсЯ K вычислительной технике и может быть использовано н цифровых вычислительных машинах н специализированных устройствах.

Цепь изобретения — повышение быстродействия устройства.

Па фиг.1 представлена структурная схема умножителя разреженных полиномов; на фиг.2 — схема сортирующей ячейки, на фиг.3-7 — алгоритм работы умножителя (для k = 4); фиг.3 — первый шаг алгоритма — умножение коэффициентов; фиг.4 — второй шаг алгоритма — выполнение операции тасовки; фиг.5 и 6 — третий шаг алгоритма нечетный и четный шаги транспозитивной сортировки двойных столбцов массива; фиг.5 и 7 — четвертый шаг алгоритма - нечетный и четный шаги соответственно транспозитивной сортировки всего массива.

В таблице приведена зависимость выходных сигналов блока управления от 25 входных.

Умножитель содержит матрицу 1 сортирующих ячеек, формирователь 2 импульсов, включающий формирователь 3

I коротких импульсов и генератор 4 так30 товых импульсов, и узел 5 вывода полинома, состоящий из элемента ИЛИ 6 и регистра 7 сдвига.

Сортирующая ячейка (фиг.2) содержит три входных коммутатора 8, ре35 гистр 9 показателя степени, три выходных коммутатора 10, узел 11 умножения, суж атор 12, регистр 13 коэффициента, три элемента II 14, три элемента ИЛИ 15, две группы 16 элементов ИЛИ, группу 17 элементов И, схему 18 сравнения, блок 19 управле ния, входы 20-24 блока 19 управления и выходы 25-32 блока 19 управления.

При умножении двух разреженных полиномов, представленных списком пар, находят произведения пар и располагают их по величине показателей (по вторым компонентам пар). В пропессе сортировки происходит сложение

50 коэффициентов с одинаковыми показатеJIHMH, Для сортировки используют алгоритм МГКСЕ. Таким образом, умножитель работает но следующем алгоритму:

Умножение коэффициентов: формирование в кажной процессорной ячейке пары вида

2. Перетасовка каждой строчки массива kxk, т.е. перестановка столбцов согласно полной перетасовке.

3. Сортировка всех двойных столбцов, т.е. подмассивов kx2, в петлеобразном порядке с использованием нечетно-четной транспозитивной сортировки. По .ходу сортировки происходит сложение коэффициентов с одинаковыми показателями.

4. Сортировка всего массива с использованием нечетно-четной транспозитивной сортировки в петлеобразном порядке. По ходу сортировки происходит сложение коэффициентов с одинаковыми показателями. !

Схематически работа алгоритма показана на фиг.3 — 7. Для выполнения первого шага алгоритма (фиг.3) необходим один такт работы. Второй шаг алгоритма — перетасовка. Операция перетасовки преобразует последователь нОсть Z 1> Z е Z 2 в полнОстью и перетасованную последовательность

Е»уЕрЕг,Ен я,...ЕнуЕр,Эта операция может быть реализована за (п/2-1) шаг. На фиг.4 изображен порядок выполнения операции перетасовки для случая k = 4. Двойные стрелки обозначают взаимный обмен между ячейками. Входная последовательность Z1, ZZ» 7б продвигается через матрицу в направлении снизу вверх. Выходная

1 последовательность на выходе матрицы 2 „, Zg б, Яз, Е.р, Zq> Zg

Третий шаг работы алгоритма изображен на фиг.5 и 6. Петлеобразная сортировка двойных столбцов сверху вниз в возрастающем порядке происходит на базе нечетно-четной сортировки.

В нечетном (четном) пошаговом алгоритме все элементы последовательности, имеющие нечетные (четные) записи, сравниваются со своими последующими элементами и меняются местами, если (2;) 2,.„, i = 1, п-11, чегнанечетные шаги исполняются в чередующемся порядке. Если сравниваемые эле" менты совпадают (по вторым компонентам), то происходит сложение первых компонент сравниваемых элементов, BTQ рой сравниваемый элемент (пара) при этом обозначается (0,0). Для реализации этого шага алгоритма необходимо 4.k шагов нечетно-четной транспозитивной сортировки. На фиг.5 и 6 показаны соответственно нечетный и четный шаги транспозитивной сортиров1649564

5 ки двух двойных столбцов 4х2 массива элементов 4х4, стрелка показывает направление передачи максимального иэ двух сравниваемых чисел. Для реализации четвертого шага алгоритма также пот- 5 ребуется 4k шагов нечетно-четной транспозитивной сортировки. Нечетный и четный шаги сортировки показаны на фиг.5 и 7 соответственно для массива элементов 4 4.

Умножитель работает следующим образом.

На первые входы (а) узлов 11 с входов умножителя поступают коэффи-. циенты полинома, заданные в виде

15 списка пар ненулевык коэффициентов и соответствующих показателей степеней. Пары коэффициентов второго полинома поступают на вторые входы узлов 11. На вход управления режимом работы подан сигнал логической единицы, блокирующий входные и выходкые коммутаторы и разрешающий работу узла 11, регистра показателя степени и регистра коэффициента. В узле 11 реализуется умножение пар коэффициентов, т.е. узел 11 состоит из дцухвходового умножителя двух чисел и сумматора. При этом сумматор реализует сложение показателей степеней соответствующих двух пар. Результаты умножения пар полиномов записываются в регистры 9 — показатель степени и в регистр 13 — коэффициент. Умножение происходит за один такт. На следу-35 ющем такте на вход управления режимом работы подают сигнал логического нуля, который обнуляет узел 11 и разблокирует входные и выходные коммутаторы 8 и 10 ячейки переходят 40 в режим сортировки. В зависимости от состояния входов 20-24 блока 19 упРавления (У» д,), Х», Х, У», У ) каждая ячейка может находиться в следующих режимах: 45

1. Режим тасовки (фиг.4). На управляющие входы 24 и 23 столбца Z подаются сигналы логической единицы.

С выхода 25 блока управления поступает сигнал, разрешающий обмен данны- 50 ми между регистрами 9 и 18 ячеек столбца Z+ и регистрами 9 и 13 соответствующих ячеек столбца .Z -. На вы9 ходах 30, 31 и 30, 29 блока управления установлены коды входных и вы- 55 ходных коммутаторов ячейки. На втором такте тасонки управляющие сигналы 24 и 23 подают на столбцы Z и Z на третьем — на столбцы Е, Е»., Z6. о

2. Активный режим. На управляя|и:к« входы 24 и 21 блока управления поданы сигналы логической единицы. В активном режиме с ныхода 28 блока управления поступает сиг:.ал, разрешающий прохождение управляющих сигналов со схемы 18 сравнения, которая сравнивает показатель степени, записанный в регистр 9 данной ячейки, с показателем степени, поступающим из соседней ячейки. В зависимости от входных сигналов 23 и 22 ка выходах

26 и 27 блока управления формируются сигналы< разрешающие передачу в соседнюю ячейку коэффициента с боль-. шим илименьшим показателем степени и, в свою очередь, принять из соседней ячейки коэффициент с меньшим нлп большим показателем степени.

Управляющий вход 24 активизирует все ячейки в столбце матрицы. Управляющий вход 21 активизирует ячейки в матрице построчно, Управляющий вход 22 определяет направление передачи коэффициента с большим показателем степени в строке матрицы. Управляющий вход 23 определяет направление передачи коэффициента с большим показателем степени н столбце матрицы °

3. Пассивный режим. H«" управляющие входы 24 и 21 поданы сигналы логического куля ° На выходе 28 блока управления формируется сигнал, запрещающий прохождение сигналов со схемы сравнения. Входными и выходными коммутаторами в этом режиме управляет сигнал на выходе 20, а регистрами 9 и 13 — сигнал, поступающий с входов управления регистром. Оба эти сигналы формируются в соседней ячейке.

4. Сложение коэффициентов в парах с равными показателями степени проис-ходит во всех активных режимах с приоритетом. При этом сигнал логической единицы с выхода "Равно" схемы сравнения поступают иа элемент И, разрешая прохождение коэффициента, записанного в регистр 13, на сумматор 12, в котором происходит его сложение с коэффициентом, поступающим из соседней ячейки. В регистр 9 записывается показатель степени, поступающий из соседней ячейки без изменения. Этим же сигналом блокируются выходные коммутаторы ячейки, обнуляя содержимое регистров 9 и 13 соседней ячейки. По окончании цикла сортирон:;.и и

16«956

7 ры полиномов располагаются в матрице петлеобразно в. возвращающем порядке сверху вниз.

5. Выгрузка данных построчно вниз.

При совпадении на управляющих входах

22 и 21 логических единиц строка матрицы своими входными коммутаторами соединяется с предыдущей строкой матрицы, а выходными коммутаторами — с последующей строкой матрицы и по каж- 10 дому такту происходит сдвиг содержимого регистров 9 и 13 построчно вниз.

По фронту каждого тактового импульса f в формирователе 3 формируется короткий одиночный импульс, кото- 15 рый поступает на оба управляющих входа регистра сдвига и разрешает ему параллельную запись пар полиномов нижней строки матрицы. Поступающие на синхронизирующий исход регистра 20 сдвига импульсы с частотой f(k+1) производят сдвиг содержимого регист-. ра и последовательный его выход через элемент ИЛИ. Для изменения направления сдвига в формирователе 3 предусмотрен счетный триггер, который изменяет код на управляющих входах регистра сдвига с частотой f.

Формула изобретения30

Умножитель разреженных полиномов, содержащий формирователь импульсов и матрицу сортирующих ячеек, первый выход формирователя импульсов соединен с входами тактовых импульсов всех сортирующих ячеек матрицы, о тл и ч а ю шийся тем, что, с целью повышения быстродействия, в него введен узел вывода полинома, 40 выход которого является выходом умножителя, выходы показателя степени и коэффициента полинома и выходы управления регистрами (i, j)-й сортирующей ячейки матрицы, где i, j = 1 k 45 (k — порядок полинома множимого и множителя), соединены соответственно с входами показателя степени и коэффициента полинома и входами управления регистрами ((i-1), jj-й, Гi (j 50

1)) -й, ((i+1), j) и и pi, (j +1))-й сортирующих ячеек матрицы, первые информационные входы сортирующих ячеек - и строки матрицы (i = 1,...k) соединены между собой и подключены к входу 1.-й пары первого полинома умножителя, вторые информационные входы сортирующих ячеек j-го столбца матрицы (j =- 1,...,k) соединены между собой и подключены к входу j é пары второго полинома умножителя, первые и вторые управляющие входы сортирующих ячеек i-й строки матрицы соединены между собой и подключены соответственно к управляющим входам первой и второй групп умножителя, третьи и четвертые управляющие входы сортирующих ячеек j-ro столбца матрицы соединены между собой и подключены соответственно к управляющим входам третьей и четвертой групп умножителя, входы управления режимом работы всех сортирующих ячеек матрицы подключены к входу управления режимом работы умножителя, четвертый управляющий вход

i-й сортирующей ячейки соединен с пятым управляющим входом (i, j+1)-й сортирующей ячейки матрицы, второй, третий и четвертый выходы формирователя импульсов подключены соответственно к тактовому и двум управляющим входам узла вывода полинома, причем каждая сортирующая ячейка матрицы содержит блок управления, группу элементов И. схему сравнения, три элемента И, три элемента ИЛИ, две группы элементов ИЛИ, сумматор,. узел умножения, три входных коммутатора, три выходных коммутатора, регистр показателя степени и регистр коэффициента, первый, второй, третий, четвертый и пятый управляющие входы ячейки соединены соответственно с входами блока управления, первый, второй и третий выходы которого соединены соответственно с первыми входами первого элемента ИЛИ, первого и второго элементов И, вторые входы которых соединены с четвертым выходом блока управления, с первыми входами третьего элемента И, элементов И группы и второго элемента ИЛИ, второй вход которого соединен с входом управления режимом работы ячейки, с блокирующими входами узла умножения и первого, второго входных коммутаторов и первым входом третьего элемента ИЛИ, выход которого подключен к управляющим входам регистров показателя степени и коэффициента, синхровходы которых соединены с синхровходом узла умножения и подключены к входу тактовых импульсов ячейки, выходы "Меньше", "Больше" и "Равно" схемы сравнения подключены соответственно к третьим входам первого и второго элементов

И и второму входу третьего элемента

И, выходы первого, второго и третьего

1649564

Таблица истинности ячейки

Состояние входов ячейки остаянке выходов блоков управления

Функция

Y Y!1„, X! Х У! Yе 1 2 3 4 5 6 7 8

Унновение двух пар полинонов.

Результат записать в регистры 4 и 13. Выполняется за 1 такт

Тасовка. Обмен информацией наяду столбцами матрицы, выполняется за (и/2-1) такт.

1 1 1

1 0 0 0 t 1 f 0 1 1

Активный ренин.

Максиналъное число передать в соседнкзе ячейку. Минимальное число принять нз соседней ячейки справа.

Активный резин.

Мииннальное число передать в соседнюю (справа) ячейку. Макскналъное число записать в регистр ячейки.

1 0 0 1 0 1 0 1 1

0 1 1 0 0 0 0

Пассивный ренин.

Число передать в ячейку слева, 0 0 элементов И подключены соответствен-. но к второму, третьему и четвертому входам первого элемента ИЛИ, выход которого соединен с вторым входом третьего элемента ИЛИ и с информационным входом первого выходного коммутатора, выход которого соединен с выходом управления регистрами ячейки, пятый выход блока управления сое- 1(3 динен с первыми управляющими входами

1 первого второго и третьего выходt ных коммутаторов, вторые управляющие входы которых соединены с первыми управляющими входами IIpp13GI 0, второ

ro и третьего входных коммутаторов и с шестым выходом блока управления, седьмой выход которого соединен с вторыми управляющими входами первого, второго,и третьего входных коммутаторов, выходы которых подключены соответственно к первым входам элементов ИЛИ первой и второй групп и к третьему входу третьего элемента

ИЛИ, четвертый вход которого соединен 25 с восьмым выходом блока управления, входы показателя степени и коэффициента полинома и входы управления регист рами ячейки соединены соответственно с информационными входами первого, второго и третьего входных к«;!муrаторов, выход второго входного комму татора соединен с первым входом сх:— мы сравнения, второй вход которой г<1— единен с выходом регистра показателя степени и информационным входом Bto рого выходного коммутатора, выход которого соединен с выходом показателя степени ячейки, первый и второй информационные входы ячейки соединены соответственно с входами узла умножения, выходы коэффициента и показателя степени которого подключены соответственно к вторым входам элементов ИЛИ первой и второй групп, выходы которого соединены соответственно с первым входом сумматора и информационным входом регистра показателя степени, выход регистра коэффициента соединен с вторыми входами элементов И группы, выходы которых подключены к второму входу сумматора, выход которого соединен с информационным входом регистра коэффициента, выход которого соединен с информационным входом третьего выходного коммутатора, выход которого является выходом коэффициента полинома ячейки.

1671 9 564

Продолжение таблицы

Согтояине выходов блоков управления

Состояние входов ячейки

У» ее У!!я-»! Х Х» У, Ут

Функция

Г L(I

0 0

0 0 0 0

0 0

0 1 0 1 0

0 0

0 0 1 0

0 0 0 0 0

1 1 0 0

1 1 0 0

7(да1) Входы юярqual uei ma

Активный ремни.

Иаксииальиое число принять из соседней ячейки сверху.

Активный ремо!и, Максимальное число передать в иимиюк> ячейку.

Пассивный ремни.

Максимальное число передать в нимиюю ячейку

Пассивный ремни.

Иаксиееальное число принять с верхней ячейки.

Сломеиие полиноиов с равиыыи показателяии степени, Выгрузка данных построчно вниз

Входы

gnpcrlriewu

peeucmpcrwu

Входы

ЛОКПЮП7РЛ!7

Cmei7ew! 2 3 4 5 6 7 6

0 0 0 1 0 0 0 1 1 1 0 1

1 0 1- 0 0 1 1 1 0 1 0

Выходы упоа8ления регис юрами

Выходы пог суаяе Ф

ЯПЕПРНУ

Bbixudbi юз о оиЦиРРЮ70 ! 6ч9564

1 с) 49.) 6,4

Составитепь Л. Лигачева

Редактор А. Огар 1 ехрел А,Кравчук Корректор Л Патай

Заказ 3428 Тираж 389 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113015, Посква, Ж вЂ” 35, Раушскал наб., д. 4/5

Производственно †издательск комбинат "Патент", г, Уягород, ул. Гагарина, 101