Умножитель разреженных полиномов Советский патент 1991 года по МПК G06F15/31 

А

А-/ л

(Л

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

О Јь

СО

ел

о

4ь

|

d

I юбретение. относится к вычислительной технике и может быть использовано в цифровых вычислительных машинах и специализированных устройст- вах.

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

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

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

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

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

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

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

(а Ь; , i ,- q;), i, г 1 ,k .

0

5

0

5

0

45

50

55

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

Схематически работа алгоритма показана на фиг.З - 7. Для выполнения первого шага алгоритма (фиг.З) необходим один такт работы. Второй шаг алгоритма - перетасовка. Операция перетасовки преобразует последователь ность Z,, Z2,...,ZЈn в полностью перетасованную последовательность

Zl Zn-M Г ги-г. -zn Zrh. Эта операция может быть реализована за (п/2-1) шаг. На фиг.4 изображен порядок выполнения операции перетасовки для случая k 4. Двойные стрелки обозначают взаимный обмен между ячейками. Входная последовательность Z., Z,,..ZB продвигается через матрицу в направлении снизу вверх. Выходная последовательность на выходе матрицы Z,, Zf, Z, Z6, 7,г, Z7, Z, Zg. Третий шаг работы алгоритма изображен на фиг о 5 и 6. Петлеобразная сортировка двойных столбцов сверху вниз в возрастающем i порядке происходит на базе нечетно-четной сортировки. В нечетном (четном) пошаговом алгоритме все элементы последовательности, имеющие нечетные (четные) записи, сравниваются со своими последующими элементами и меняются местами, если Јz; Z,4, , i 1, n-1j, четно- нечетные шаги исполняются в чередующемся порядке. Если сравниваемые элементы совпадают (по вторым компонентам) , то происходит сложение первых компонент сравниваемых элементов, второй сравниваемый элемент (пара) при этом обозначается (0,0). Для реализации этого шага алгоритма необходимо 4ok шагов нечетно-четной транспозитивной сортировки. На фиг.5 и 6 показаны соответственно нечетный и четный шаги транспозитивной сортиров

51

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

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

На первые входы (а) узлов 11 с входов умножителя поступают коэффициенты полинома, заданные в виде списка пар ненулевых коэффициентов и соответствующих показателей степеней. Пары коэффициентов второго полинома поступают на вторые входы узлов 11. На вход управления режимом работы подан сигнал логической единицы, блокирующий входные и выходные коммутаторы и разрешающий работу узла 11, регистра показателя степени и регистра коэффициента. В узле 11 реализуется умножение пар коэффициентов, т.е. узел 11 состоит из двух- входового умножителя двух чисел и суматора. При этом сумматор реализует сложение показателей степеней соответствующих двух пар. Результаты умножения пар полиномов записываются в регистры 9 - показатель степени t и в регистр 13 - коэффициент. Умноже

ние происходит за один такт. На следу-35 рещающий прохождение сигналов со схеющем такте на вход управления режимом работы подают сигнал логического нуля, который обнуляет узел 11 и разблокирует входные и выходные коммутаторы 8 и 10, ячейки переходят в режим сортировки. В зависимости от состояния входов 20-24 блока 19 управления

(Yl|n-0 x

Y,, Y) каждая ячейка может находиться в следующих режимах:

0

5

0

5

0

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

5

0 5

мы сравнения. Входными и выходными коммутаторами -в этом режиме управляет сигнал на выходе 20, а регистрами 9 и 13 - сигнал, поступающий с входов управления регистром. Оба эти сигналы формируются в соседней ячейке.

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

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

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

Умножитель разреженных полиномов, содержащий формирователь импульсов и матрицу сортирующих ячеек, первый выход формирователя импульсов соединен с входами тактовых импульсов всех сортирующих ячеек матрицы, о т- личающ ийся тем, что, с целью повышения быстродействия, в него введен узел вывода полинома, выход которого является выходом умножителя, выходы показателя степени и коэффициента полинома и выходы управления регистрами (i, j)-u сортирующей ячейки матрицы, где i, j 1,k (k - порядок полинома множимого и множителя), соединены соответственно с входами показателя степени и коэффициента полинома и входами управления регистрами .(i-1), , Qi,(j- 1)-й, (i+1), fj-й и Ч, (j -И)-и сортирующих ячеек матрицы, первые информационные входы сортирующих ячеек i-й строки матрицы (i 1,...k) соединены между собой и подключены к входу t-й пары первого полинома умножителя, вторые информационные входы сортирующих j-ro столбца матрицы (i - 1,,.., соединены между

15

. 5 10.

вя 30

649564й

собой и подключены к входу j-й пары второго полинома умножителя, первые и вторые управляющие входы сортирующих ячеек i-й строки матрицы соединены между собой и подключены соответственно к управляющим входам первой и второй групп умножителя, третьи и четвертые управляющие входы сортирующих ячеек j-ro столбца матрицы соединены между собой и подключены соответственно к управляющим входам третьей и четвертой групп умножителя, входы управления режимом работы всех сортирующих ячеек матрицы подключены к входу управления режимом работы умножителя, четвертый управляющий вход i-й сортирующей ячейки соединен с пятым управляющим входом (i, j + D-й сортирующей ячейки матрицы, второй, третий и четвертый выходы формирователя импульсов подключены соответственно к тактовому и двум управляющим входам узла вывода полинома, причем каждая сортирующая ячейка матрицы содержит блок управления, группу элементов И. схему сравнения, три элемента И, три элемента ИЛИ, две группы элементов ИЛИ, сумматор, узел умножения, три входных коммутатора, три выходных коммутатора, регистр показателя степени и регистр коэффициен20

25

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

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

управления, с первыми входами третьего элемента И, элементов К группы и второго элемента ИЛИ, второй вход которого соединен с входом управления

режимом работы ячейки, с блокирующими входами узла умножения и первого, второго входных Коммутаторов и первым входом третьего элемента ИЛИ, выход которого подключен к управляющим вхоДам регистров показателя степени и коэффициента, синхровходы которых соединены с синхровходом узла умножения и подключены к входу тактовых импульсов ячейки, выходы Меньше,

Больше и Равно схемы сравнения подключены соответственно к третьим входам первого и второго элементов И и второму входу третьего элемента И, выходы первого, второго и третьего

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

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

Умножение двух пар полиномов. Результат записать в регистры 4 и 13. Выполняется за I такт

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

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

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

Пассивный режим. Число передать в ячейку слева.

5

Q 5 0

0

второго и третьего входных Krwvra- торов, выход второго входного комму татора соединен с первым входом г.чч - мы сравнения, второй вход которой соединен с выходом регистра показателя степени и информационным входом второго выходного коммутатора, выход которого соединен с выходом показателя степени ячейки, первый и второй информационные входы ячейки соединены соответственно с в-ходами узла умножения, выходы коэффициента и показателя степени которого подключены соответственно к вторым входам элементов ИЛИ первой и второй групп, выходы которого соединены соответственно с первым входом сумматора и информационным входом регистра показателя степени, выход регистра коэффициента соединен с. вторыми входами элементов И группы, выходы которых подключены к второму входу сумматора, выход которого соединен с информационным входом регистра коэффициента, выход которого соединен с информационным входом третьего выходного коммутатора, выход которого является выходом коэффициента полинома ячейки.

Активный режим. Максимальное число принять иэ соседней ячейки сверху.

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

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

Пассивный режим. Максимальное число принять с верхней ячейки.

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

10101011

0000

00)0

I О О

О 1

101001 11010

01010

00000

1100

А&

г22

хгл15

9Ы&-

Входы

управленца

регистрами

Входы

показателя

степени

Входы коэффициента

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

О 1

01010

00000

1100

#(1)

Выходы упоадления

регистрами

Выходы

показа/пело

степени

Выходы коэффициента

ТЧ

kbibkb

°г -: -Ъ -Ъ ° .ЖЗ

Zl Z5 г ZS 23 27 Itj Z3

2т 1r

21 2г 23 2b Z5 Zff 27 2e ФигЛ

№ ,

ОО

яоо оо

X

УХХ) СЮ J3OO ОО

Фиг. 5

ь

3

Фиг.3

Ч,0

О О

/2 7 угО

tfo ою°

Фиг. 7