Устройство для вычисления суммпроизведений упорядоченных массивовчисел

 

Союз Советских

Социалистических

Республик

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДИТИЛЬСТВУ

<п>807280 (61) Дополнительное к авт. свид-ву— р )м. кл

G 06 F 7/52 (22) Заявлено 201178 (21) 2687326/18-24 с присоединением заявки ¹â€” (23) Приоритет—

Государственный комитет

СССР но делам изобретений и открытий

Опубликовано 230281„бюллетень Й9 7 (53) УДК 681.325 (088.88) Дата опубликования описания 25.0281 (72) Автор изобретения

В. П. Воюн (71) Заявитель

Ордена Ленина институт кибернетики ЛН Ук (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СУММ ПРОИЗВЕДЕНИЙ, УПОРЯДОЧЕННЫХ ИАССИВОВ ЧИСЕЛ

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

Фурье, цифровую фильтрацию сигналов, обработку экспериментальных данных и т. п.

Под упорядоченным массивом здесь понимается массив, в котором числа расположены в порядке возрастания или убывания их величины. Упорядоченные массивы довольно часто встречаются на практике, например массивы, полу.ченные .в результате квантования и. дискретизации по времени процессов разгона двигателей, нагрева слитков в нагревательных колодцах, кривых 20 расхода энергии и материалов, пройденного пути и т. и. Неупорядоченные массивы могут быть упорядочены с помощью специальных программ или устройств. В данном случае упорядоченным является один из массивов чисел, а во втором массиве числа расположены в соответствии с номерами, под которыми расположены соответствующие им пары в первом массиве. 30

Известны устройства для вычисления суммы произведений двух массивов чисел, содержащие блок памяти для хранения массивов чисел и процессор для перемножения сомножителей и вычисления их суммы (11 .

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

Известны устройства для вычисления ,суммы.произведений двух массивов чисел, содержащие два блока памяти для хранения массивов чисел,.множительное устройство и накапливающий сумматор (2 .

Недостатком устройства является его низкое быстродействие, обуслов- ленное тем,.что для вычисления пройэведения N пар чисел массивов тре807280

ыми по входам 1.2 и 13 производится апись чисел первого и второго массиа в запоминающие блоки 1 и 2 соответтвенно. Оба массива упорядочены по ислам первого массива, т. е. числа а„ в первом массиве расположены в поядке возрастания их величины, а во тором массиве числа b„ записаны в оответствии. с номерамй, под которыми расположены соответствующие им пары в первом. Наряду с записью чисел во второй запоминающий блок 2 производится их суммирование на сум-, маторе-вычитателе 8, на входы сложения которого под управлением .сигналов по третьему выходу схемы 11 управления поступают чнсла второго массива.

После записи чисел обоих массивов в запоминающие блоки 1 и 2 и вычисления суммы чисел второго массива, которая остается в сумматоре-вычитателе 8, схема 11.управления по первому выходу управляет счетчиком 3 адреса, который формирует адрес первой ячейки. В соответствии с первым адресом иэ первого 1 и второго 2 запоминающих блока на регистры 4 и 5 числа считывается пара чисел а и Ьл, причем число а является и игленьшим числом в первом массиве вследствие

его упорядоченности). После чего блок

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

И 9 и осуществляют передачу содержимого (Х„Ь;) сумматора-вычитателя 8 в накайлйвающий сумматор 10. Счетчик

7 производит подсчет количества поступивших на него импульсов до момента равенства кода в счетчике 7 и содержимого регистра 4 числа, который определяется схемой б сравнения. При этом схема б сравнения выдает сигнал на блок 11 управления, в соответствии с которым блок 11 управления прекращает выдачу тактовйх импульсов на второй выход, а по третьему выходу управляет сумматором-вычитателем 8, который вычитает из своего содержимого число Ь 1, записанное. на втором регистре 5 чйсла. Затем под управлением по первому выходу схемы 11 управления счетчиком 3 адреса формируется адрес второй ячейки запоминающих блоков 1 и 2, иэ которых считывается их содержимое на регистры 4 и 5 числа.: Число а, считанное с второй ячейки первого запоминающего блока 1, равно или больше числа, считанного ранее ввиду упорядоченности первого массива). Если числа равны, то происходит повторное срабатывание схемы б сравнения, которая через блок

11 управления, производит вычитание из содержимого сумматора-вычитателя второго. числа Ь, находящегося на регистре 5 числа. Если считанное второе число иэ первого массива больше буется выполнить N и сложений и . р и n сдвигов в множительном устрой- з стве где n — разрядность чисел мас- в сивов). с

Цель изобретения — повышение бы- ч стродействия устройства за счет сокращения количества операций для вы- р числения суммы парных произведений. в

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

На чертеже схематически представлено устройство.

Устройство содержит первый 1 и. второй 2 запоминающие блоки, счетчик

3 адреса, первый 4 и второй 5 регистры числа, схему б сравнения, счетчик . 7 сумматор-вычитатель 8, группу элементов И 9, накапливающий сумматор

10, блок 11 управления. Первые 12 и вторые 13 входы устройства соединены с входами первого 1 и второго 2 запоминающих блоков, адресные входы которых соединены с выходами счетчика

3 адреса. Выходы первого 1 и второго

2 запоминающих блоков соединены с входами регистров 4 и 5 числа.. Выхо- . ды первого регистра числа соединены 4Q с первыми входами схемы б сравнения, вторые входы которой соединены с выходами счетчика 7. Выходы второго . регистра 5 числа соединены с входами вычитания сумматора.-вычитателя 8, входы сложения которого соединены с входами второго запоминающего блока

2, а выходы через группу элементов

И 9 соединены с входами накапливающего сумматора 10, выходы которого О соединены с выходами 14.устройства.

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

3 адреса, второй выход соединен со счетным входом счетчика 7 и управляю- Ы щим входом группы элементов И 9, а третий выход соединен с управляющим входом.суюлатора-вычитателя 8.

Предлагаемое устройство работает следующим образом. 60

Под управлением первого выхода блока 11 управления счетчик 3 адреса последовательно формирует адреса ячеек первого 1 и второго 2 запоминающих блоков, в соответствии с ко - у

807280

Формула изобретения предыдущего числа, то сравнение его с кодом в счетчике 7 (в котором хранится .фактически предыдущее число) не происходит и блок 11 управления производит выдачу тактовых импульсов по второму выходу, которые открывают группу элементов Й 9 и осуществляют передачу нового содержимого (ф Ь ) сумматора.-вычитателя 8 в накаI;:JiHHBF)» щий сумматор 10. Счетчик 7 производит добавление постунающих на его вход тактовых импульсов к ранее .зафиксированному в нем коду, т. е. первому числу первого массива. В .момент равенства кода .в счетчике 7 с содержимым первого регистра 4 срабатывает. схема б сравнения, которая через блок

11 управления производит вычитание числа bg во втором регистре 5 числа из содержимого сумматора-вычитателя

8. Аналогично осуществляется обработка и всех остальных. чисел .массивов.

Сравнение последнего (максимального) числа в первом массиве с кодом в счетчике 7 приводит к вычитанюо последнего числа второго массива из со-. держимого сумматора-вычитателя 8, в результате чего он обнуляется, а в накапливанием сумматоре 10 к этому моменту накапливается сумма произведений двух массивов чисел. Время вычисления суммы произведений двух массивов чисел в предлагаемом уст.:ройстве слабо зависит от количества чисел массива и в большей степени зависит от разрядности чисел массива.

Устройство для вычисления сумм произведений упорядоченных массивов чисел, содержащее первый и второй ,запоминанщие блоки, информационные входы которых соединены с соответствующими входами устройства, первый и второй регистры числа, входы кото- рых соединены с выходами соответст венно первого и второго запоминающих блоков, счетчик адреса, выходы которого соединены с адресными входами первого и второго запоминающих ,блоков, группу элементов И, накапливающий сумматор и блок управления, первый выход которого соединен с входом счетчика адреса, второй вы1О :ход — с управляющими входами элементов И группы, выходы которых соедине.ны с входами накапливающего сумматора, выходы которого являются выходами устройства, о т л и ч а ю щ е—

35 е с я тем, что, с целью повышения быстродействия, в устройство введены схема сравнения, счетчик и сумкаторв читатель, входы сложения которого соединены с входами второго запомищ нающего блока, входы вычитания — с выходами второго .регистра числа, а выходы - c информационными входами группы элементов И, первые и вторые входы схемы сравнения соединены с вьходами первого регистра числа и счетчика соответственно, а выход ее . подключен к входу блока управления, третий выход которого подключен к управляющему входу сумматора-зычитателя, счетный вход счетчика подклюЗО чен к управляющим входам группы элементов И.

Источники информации, принятые во внимание при экспертизе

1. Каган Б. Н. и Каневский И. И.

Цифровые вычислительные машины и си,:стемы. M., "Энергия", 1973, с. 12-18.

2. Семотюк M. В. и Боюн. В. П. Операционные устройства для суммирования парных произведений и перемножения

Щ комплексных чисел. - "Управляющие системы и машины", 1978, В Э, с. 8792, pic. 1 (прототип).

807280

Тираж 756 Подписное

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

113035, Москва, Ж-35, Раушская наб., д. 4/5

Заказ 292/73

Филиал ППП "Патент", r. ужгород, ул. Проектная, 4

Составитель Н. Измайлова

Редактор Л. Кеви Техред С. Мигунова Корректор И. Муска