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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИН 06 Г 15 31 В ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМПРИ ГКНТ СССРФ ОПИСАНИЕ ИЗ ОМУ СВИДЕТЕЛЬС(56) Авторское свидетепьство СССР Р 997039, кл, С ОЬ Г 15/31, 1983.Авторское свидетельство СССР У 4351529/24, кл, С 06 Р 15/31, 198 (54), УМНОЖИТЕЛЬ РАЗРЕЖЕННЫХ ПОЛИНОМ (57) Изобретение относится к вычислительной технике и может быть ис 1649564 пользовано в циФровых вычислительных комплексах и специализированныхустройствах, в частности в устройст-,вах циФровой обработки сигналов.Цель изобретения - повышение быстродействия умножителс. Данный умножитель реализует операцию умноженияполиномов, представленных в видесписка пар, состоящих из ненулевогокоэФФициента и соответствующего емупоказателя степени переменной. Умножитель разреженных полиномов содержит матрицу 1 сортирующих ячеек,Формирователь 2 импульсов и узел 5вывода полинома. 7 ил., 1 табл.(а 1), . 1е 1 еГ 11 С Изобретение Относится к вычислительной технике и может быть использовано в цифровых вычислительных манинах и специализированных устройствах,Депь изобретения - повышение быстродействия устройства.На фиг,1 представлена структурнаясхема умножителя разреженных полиномов; на Фиг.2 - схема сортирующейячейкиф на фиг.3-7 - алгоритм работыумножителя (для Е = 4); фиг,3 - первый шаг алгоритма - умножение коэффициентов; Фиг.4 - второй наг алгоритма - выполнение операции тасовки;Фиг,5 и 6 - третий шаг алгоритманечетный и четный шаги транспозитивной сортировки двойных столбцов массива; Фиг,5 и 7 - четвертый наг алгоритма - нечетный и четный шаги соответственно транспозитивной сортировки всего массива.В таблице приведена зависимостьвыходных сигналов блока управления от 25входных.Умножитель содержит матрицу 1 сортирующих ячеек, Формирователь 2 импульсов, включающий Формирователь 3коротких импульсов и генератор 4 так 30товык импульсов, и узел 5 вывода полинома, состоящий из элемента ИЛИ 6и регистра 7 сдвига.Сортирующая ячейка (Фиг.2) содержит три входных коммутатора 8, ре 35гистр 9 показателя степени, три выходных коммутатора 10, узел 11 умножения, сужатор 12, регистр 13коэффициента, три элемента И 14 триэлемента ИЛИ 15, две группы 16 элементов ИЛИ, группу 17 элементов И,схему 18 сравнения, блок 19 управления, входы 20-24 блока 19 управленияи выходы 25-32 блока 19 управления.При умножении двух разреженныхполиномов, представленных спискомпар находят произведения пар и распопагают их по величине показателей(по вторым компонентам пар). В пропессе сортировки происходит сложение50коэффициентов с Одинаковыми показателями. Для сортировки используют алгоритм МГЛСЕ, Таким Образом, умножитель работает по слепующем алгоритму:Умножение коэффициентов: Формирование в кажной процессорной ячейкепары вида 2. Перетасовка каждой строчкимассива 11 с, т.е. перестановка столбцов согласно полной перетасовке.3. Сортировка всех двойных столбцов, т,е, подмассивов Ех 2, в петле- образном порядке с использованием нечетно-четной транспозитивной сортировки. По ходу сортировки происходит сложение коэффициентов с одинаковыми показателями.4. Сортировка всего массива с использованием нечетно-четной транс- позитивной сортировки в петлеобразном порядке. По ходу сортировки происходит сложение коэффициентов с одинаковыми показателями.Схематически работа алгоритма показана на Фиг.3 - 7. Для выполнения первого нага алгоритма (фиг.3) необходим один такт работы. Второй шаг алгоритма - перетасовка. Операция перетасовки преобразует последователь ность 7. , 2,22 в полностьюиперетасованную последовательность7 и+е э 2 г, 2 врг, 2, 2, Эта операция может быть реализована за (п/2-1) шаг. На фиг,4 изображен порядок выполнения операции перетасовки для случая 1 с = 4. Двойные стрелки обозначают взаимный обмен между ячейками. Входная последовательность 2 ч, 227 б продвигается через матрицу в направлении снизу вверх, Выходная 1последовательность на выходе матрицы 2 й 21 7 д) б 2 7 и, 27 2 э 28Третий шаг работы алгоритма изображен на фиг.5 и 6. Петлеобразная сортировка двойных столбцов сверху вниз в возрастающемпорядке происходит на базе нечетно-четной сортировки. В нечетном (четном) понаговом алгоритме все элементы последовательности, имеющие нечетные (четные) записи, сравниваются со сВоими последующими элементами и меняются местами, если 1 с; ) Е,.ч , . = 1, л, чесианечетные шаги исполняются в чередующемся порядке, Если сравниваемые эле менты совпадают (по вторым компонентам), то происходит сложение первых компонент сравниваемых элементов, второй сравниваемый элемент (пара) при этом обозначается (0,0). Для реализации этого шага алгоритма необходимо 4,1 с шагов нечетно-четной транспозитивной сортировки. На Фиг.5 и 6 показаны соответственно нечетный и четный шаги транспозитивной сортиров.1 б 95 б7ры полиномов располагаются в матрице петлеобразно в. возвращающем порядке сверху вниз.5. Выгрузка данных построчно вниз. При совпадении на управляющих входах 22 и 21 логических единиц строка матрицы своими входными коммутаторами соединяется с предыдущей строкой матрицы, а выходными коммутаторами - с последующей строкой матрицы и по каж дому такту происходит сдвиг содержимого регистров 9 и 13 построчно вниз.По фронту каждого тактового импульса 2 в формирователе 3 формируется короткий одиночный импульс, кото рый поступает на оба управляющих входа регистра сдвига и разрешает ему параллельную запись пар полиномов нижней строки матрицы. Поступающие на синхронизирующий исход регистра 20 сдвига импульсы с частотой й(Е+1) производят сдвиг содержимого регист-, ра и последовательный его выход через элемент ИЛИ. Для изменения направления сдвига в формирователе 3 предусмотрен счетный триггер, который изменяет код на управляющих входах регистра. сдвига с частотой Г.Формула из обр етения 30Умножитель разреженных полиномов, содержащий формирователь импульсов и матрицу сортирующих ячеек, первый выход формирователя импульсов соединен с входами тактовых импульсов всех сортирующих ячеек матрицы, о тл и ч а ю щи й с я тем, что, с целью повышения быстродействия, в него введен узел вывода полинома, 40 выход которого является выходом умно- жителя, выходы показателя степени и коэффициента полинома и выходы управления регистрами (, )-й сортирующей ячейки матрицы, где д, 1 = 1,1 45- порядок полинома множимого и множителя), соединены соответственно с входами показателя степени и коэфФициента полинома и входами управления регистрами (1-1) 11 й Г(3 501) -й, (+1), Я-й и 1, (1 +1)1-й сортирующих ячеек матрицы, первые информационные входы сортирующих ячеек - й строки матрицы (з. = 1,1 с) соединены между собой и подключены к входу 1,-й пары первого полинома умно- жителя, вторые информационные входы сортирующих ячеек )-го столбца матрицы (1 - 1,.,с) соединены между собой и подключены к входу 3-й парывторого полинома умножителя, первыеи вторые управляющие входы сортирующих ячеек х-й строки матрицы соединены между с об ой и под ключ ены соотв етственно к управляющим входам первойи второй групп умножителя, третьии четвертые управляющие входы сортирующих ячеек 1-го столбца матрицысоединены между собой и подключенысоответственно к управляющим входамтретьей и четвертой групп умножителя,входы управления режимом работы всехсортирующих ячеек матрицы подключенык входу управления режимом работы умножителя, четвертый управляющий входх-й сортирующей ячейки соединен спятым управляющим входом (, 1+1)-йсортирующей ячейки матрицы, второй,третий и четвертый выходы формирователя импульсов подключены соответственно к тактовому и двум управляющимвходам узла вывода полинома, причемкаждая сортирующая ячейка матрицы содержит блок управления, группу элементов И. схему сравнения, три элемента И, три элемента ИЛИ, две группыэлементов ИЛИ, сумматор,. узел умножения, три входных коммутатора, тривыходных коммутатора, регистр показателя степени и регистр коэффициен"та, первый второй, третий, четвертыйи пятый управляющие входы ячейкисоединены соответственно с входами .блока управления, первый, второй итретий выходы которого соединены соответственно с первыми входами первого элемента ИЛИ, первого и второгоэлементов И, вторые входы которых соединены с четвертым выходом блокауправления, с первыми входами третьего элемента И, элементов И группыи второго элемента ИЛИ, второй входкоторого соединен с входом управлениярежимом работы ячейки, с блокирующимивходами узла умножения и первого, второго входных коммутаторов и первымвходом третьего элемента ИЛИ, выходкоторого подключен к управлющим входам регистров показателя степени икоэффициента, синхровходы которыхсоединены с синхровходом узла умножения и подключены к входу тактовыхимпульсов ячейки, выходы "Меньше","Больше" и "Равно" схемы сравненияподключены соответственно к третьимвходам первого и второго элементовИ и второму входу третьего элементаИ, выходы первого, второгои третьего1649564 1 О Таблица истинности ячейки Состояние входов ячейки остаянке выходов блоков управления Функция Урры ТХ Ха Т Те 1 2 Э 4 5 6 7 8 Унновение двух пар полинонов, Результат записать в регистры 4 и 13, Выполняется за 1 такт Тасовка, Обненинормацнейнаеду столбцами матрицы, выполняется за(и/2-1) такт. 1 1 1 1 О О О 1Р О1 Активный резан. Максинальноечисло передать в соседнкзе ячейку. Минимальное число принять нз соседней ячейки справа. Активный резин. Мииннальное число передать в соседнюю (справа) ячейку. Макскнальное числозаписать в регистр ячейки,1 О ОО 1 1 О1 О 1 1 О О О О Пассивный рахим.Число передать вячейку слева,О О элементов И подключены соответствен-, но к второму, третьему и четвертому входам первого элемента ИЛИ, выход которого соединен с вторым входом третьего элемента ИЛИ и с информационным входом первого выходного коммутатора, выход которого соединен с выходом управления регистрами ячейки, пятый выход блока управления сое динен с первыми управляющими входами1первого второго и третьего выходзных коммутаторов, вторые управляющие входы которых соединены с первыми управляющими входами первого, второго и третьего входных коммутаторов и с шестым выходом блока управления, седьмой выход которого соединен с вторыми управляющими входами первого, второго,и третьего входных коммутаторов, выходы которых подключены соответственно к первым входам элементов ИЛИ первой и второй групп и к третьему входу третьего элемента ИЛИ, четвертый вход которого соединен 25 с восьмым выходом блока управления, входы показателя степени и коэффициента полинома и входы управления регист рами ячейки соединены соответственно с информационными входами первого,второго и третьего входных кою угаторов, выход второго входного коммутатора соединен с первым входом сх; -мы сравнения, второй вход которой гр 1 единен с выходом регистра показателястепени и информационным входом второго выходного комутатора, выходкоторого соединен с выходом показателя степени ячейки, первый и второй информационные входы ячейки соединенысоответственно с входами узла умножения, выходы коэффициента и показателя степени которого подключены соответственно к вторым входам элементов ИЛИ первой и второй групп, выходы которого соединены соответственно с первым входом сумматора и информационным входом регистра показателя степени, выход регистра коэффициента соединен с вторыми входами элементов И группы, выходы которых подключены к второму входу сумматора,выход которого соединен с информационным входом регистра коэффициента,выход которого соединен с информационным входом третьего выходногокоммутатора, выход которого являетсявыходом коэффициента полинома ячейки,19 51 ПРОПОЛжЕ 1 ИЕ табЛИЦЫ Согояпие выходов блоков управления Состояние входов ячейки Функция О О О 1 ОО 1 О 1 1 1 О 1 О О 1 О 1. О О 1 1 1 О 1 О О О О О О О ОО 1 О О О О О 1 О О О О О О 1 1 О О 1 1 О О 77/7 а У) Выходы упоабленийРЕгиСп/РОМи Выходб/ПО/ГйЯОП/Е 7/./ПЕ/7 Р/уУ Входы ю 7 ррициею 7/а Активный ремни,Иаксимальиоечисло принятьиз соседней ячейки сверху,Актнвный ревоиМаксимальноечисло передатьв иимиюю ячейку. Пассивный реяни.Максимальное число передать внимиюю ячейку Пассивный ремни.Ивасиальное число принять сверхней ячейки,Сломеиие полиноиов с равныыипоказателяни степени,Выгрузкаданных построчно вниз ф х,УИ