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

Союз Советских Социалистических РеспубликОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДИТИЛЬСТВУ нц 807280(22) Заявлено 201178 (21) 2687326/18-24 с присоединением заявки Нов(23) Приоритет -Государственный комитет СССР но делам изобретений и открытийДата опубликования описания 25.0281(72) Автор изобретения В. П. Воюн 71) Заявител а Ленина институт кибернетики ЛН Ук 4) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СУЮТ ПРОИЗВЕДЕНИ УПОРЯДОЧЕННЫХ ИАССИВОВ ЧИСЕЛ2 к вычисли-быть применеустройствах,ие системциальных ивычислениекоэААициентоив сигналов,ных данных са Изобретение относитсятельной технике и можетно в специализированныхориентированных на решеналгебраических, дифйеренинтегральных уравнений,.корреляционных Функций,Фурье, циФровую фильтрацобработку эксперименталь и т. п.Под упорядоченным массивом здесь понимается массив, в котором числа расположены в порядке возрастания и убывания их величины. Упорядоченные массивы довольно часто встречаются на практике, например массивы, полу ченные .в результате квантования и. дискретизации по времени процессов разгона двигателей, нагрева слитков в нагревательных колодцах, кривых расхода энергии и материалов, пройд ного пути и т. и. Неупорядоченные массивы могут быть упорядочены с по мощью специальных программ или уст ройств. В данном случае упорядоченным является один из массивов чисел а во втором массиве числа расположе ны в соответствии с номерами, под которыми расположены соответствуюнти им пары в первом массиве. Известны устройства для вычисления суммы произведений двух массивовчисел, содержащие блок памяти дляхранения массивов чисел и процессордля перемножения сомножителей и вычисления их суммы 11 .Недостатком таких устройств явля, ется их низкое быстродействие, обус О ловленное тем, что процессор в соответствии с программой последователь-но во времени Формирует адреса первого и второго сомножителей, выбираетпо ним сомножители из блока памяти,осуществляет их Перемножение, выби рает текущее значение суммы,.добавляет его к полученному проиэведениюи отсылает в рабочую ячейку памяти,после чего сравнивает текущие адречисел массива с концом массива и 20 переходит на начало программы.Известны устройства для вычисления,суммы.произведений двух массивов чисел, содержащие два блока памяти дляхранения массивов чисел,.множительное устройство и накапливающий сумматор 21 .Недостатком устройства являетсяего низкое быстродействие, обуслов-ленное темчто для вычисления про йэведения й пар чисел массивов треФыми по входам 1.2 и 13 производится апись чисел первого и второго масси- а в запоминающие блоки 1 и 2 соответтвенно. Оба массива упорядочены по ислам первого массива, т. е. числа а в первом массиве расположены в поядке возрастания их величины, а во тором массиве числа Ь записаны в оответствии с номерамй, под которыми расположены соответствующие им пары в первом. Наряду с записью чисел во второй запоминающий блок 2 производится их суммирование на сум-, маторе-вычитателе 8, на входы сложения которого под управлением .сигналов по третьему выходу схемы 11 управления поступают чнсла второго массива.После записи чисел обоих массивов в запоминающие блоки 1 и 2 и вычисления суммы чисел второго массива, которая остается в сумматоре-вычитателе 8, схема 11.управления по первому выходу управляет счетчиком 3 адреса, который формирует адрес первой ячейки. В соответствии с первым адресом иэ первого 1 и второго 2 запоминающих блока на регистры 4 и 5 числа считывается пара чисел аи Ь 4, причем число а является нименьшим числом в первом массиве вследствие его упорядоченности). После чего блок 11 управленияф по второму выходу производит выдачу тактовых импульсов, которые открывают группу элементов И 9 и осуществляют передачу содержимогоХЬ;) сумматора-вычитателя 8 в накайлйвающий сумматор 10. Счетчик 7 производит подсчет количества по- ступивших на него импульсов до момента равенства кода в счетчике 7 и содержимого регистра 4 числа, который определяется схемой б сравнения. При этом схема б сравнения выдает сигнал на блок 11 управления, в соответствии с которым блок 11 управления прекращает выдачу тактовйх импульсов на второй выход, а по третьему выходу управляет сумматором-вычитателем 8, который вычитает из своего содержимого число Ь 1, записанное. на втором регистре 5 чйсла. Затем под управлением по первому выходу схемы 11 управления счетчиком 3 адреса Формируется адрес второй ячейки запоминающих блоков 1 и 2, иэ которых считывается их содержимое на регистры 4 и 5 числа Число а, считанное с второй ячейки первого запоминающего блока 1, равно или больше числа, считанного ранее ввиду упорядоченности первого массива), Если числа равны, то происходит повторное срабатывание схемы б сравнения, которая через блок 11 управления, производит вычитание из содержимого сумматора-вычитателя второго, числа Ь, находящегося на регистре 5 числа. Если считанное второе число иэ первого массива больше буется выполнить М и сложений и . рйи сдвигов в множительном устрой- зстве где и - разрядность чисел мас- всивов), сЦель изобретения - повышение бы- чстродействия устройства за счет сокращения количества операций для вы- рчисления суммы парных произведений. вУказанная цель достигается тем, счто в устройство введены схема сравнения, счетчик и сумматор-вычитатель, 1причем первые и вторые входы схемысравчения соединены с выходами первого регистра числа и счетчика соответственно,. а выход ее соединен с входом блока управления, третий выходкоторого соединен с управляющим входом сумматора-вычитателя, входы сложения которого соединены с входамивторого запоминающего блока, входывычитания соединены с выходами второго регистра числа, а выходы суммато Ора-вычитателя соедийены с входамигруппы элементов И, счетный вход счетчика подключен к управляющим входамгруппы элементов И.На чертеже схематически представлено устройство.Устройство содержит первый 1 ивторой 2 запоминающие блоки, счетчик3 адреса, первый 4 и второй 5 регистры числа, схему б сравнения, счетчик. 7 сумматор-вычитатель 8, групу элементов И 9, накапливающий сумматор10, блок 11 управления. Первые 12 ивторые 1,3 входы устройства соединеныс входами первого 1 и второго 2 запоминающих блоков, адресные входы которых соединены с выходами счетчика3 адреса. Выходы первого 1 и второго2 запоминающих блоков соединены свходами регистров 4 и 5 числа Выхо- .ды первого регистра числа соединены 40с первыми входами схемы б сравнения,вторые входы которой соединены с выходами счетчика 7. Выходы второго. регистра 5 числа соединены с входамивычитания сумматора.-вычитателя 8,входы сложения которого соединены свходами второго запоминающего блока2, а выходы через группу элементовИ 9 соединены с входами накапливающего сумматора 10, выходы которогосоединены с выходами 14.устройства.Вход блока 11 управления соединен свыходом схемы б сравнения, первыйвыход ее соединен с входом счетчика3 адреса, второй выход соединен сосчетным входом счетчика 7 и управляю- Ыщим входом группы элементов И 9, атретий выход соединен с управляющимвходом .сумматора-вычитателя 8.Предлагаемое устройство работаетследующим образом. 60Под управлением первого выходаблока 11 управления счетчик 3 адресапоследовательно формирует адресаячеек первого 1 и второго 2 запоминающих блоков, в соответствии с кот- уФормула изобретения предыдущего числа, то сравнение егос кодом в счетчике 7 (в котором хранится .Фактически предыдущее число)не происходит и блок 11 управленияпроизводит выдачу тактовых импульсовпо второму выходу, которыеоткрываютгруппу элементов Й 9 и осуществляютпередачу нового содержимого ( Й Ь)сумматора.-вычитателя 8 в накаглйвавщий сумматор 10. Счетчик 7 производитдобавление постунающих на его входтактовых импульсов к ранее .заФиксированному в.нем коду, т. епервомучислу первого массива. В .момент равенства кода .в счетчике 7 с содержимым первого регистра 4 срабатывает.схема б сравнения, которая через блок11 управления производит вычитаниечисла Ь во втором регистре 5 числаиз содержимого сумматора-вычитателя8. Аналогично осуществляется обработка и всех остальных. чисел .массивов.Сравнение последнего ,максимального)числа в первом массиве с кодом всчетчике 7 приводит к вычитанщопоследнего числа второго массива из со-.держимого сумматора-вычитателя 8, врезультате чего он обнуляется, а внакапливанием сумматоре 10 к этомумоменту накапливается сумма произведений двух массивов чисел. Времявычисления суммы произведений двухмассивов чисел в предлагаемом устройстве слабо зависит от количества.присел массива и в большей степенизависит от разрядностичисел массива. Устройство для вычисления суммпроизведений упорядоченных массивовчисел, содержащее первый и второй,запоминанщие блоки, информационныевходы которых соединены с соответствующими входами устройства, первыйи второй регистры числа, входы кото-рых соединены с выходами соответственно первого и второго запоминающих блоков,.счетчик адреса, выходыкоторого соединены с адресными входами первого и второго запоминающих,блоков, группу элементов И, накапливающий сумматор и блок управления,первый выход которого соединен свходом счетчика адреса, второй вы 10 :ход - с управляющими входами элементов И группы, выходы которых соединены.с входами накапливающего сумматора, выходы которого являются выходами устройства, о т л и ч а ю щ е -35 е с я тем, что, с целью повышениябыстродействия, в устройство введенысхема сравнения, счетчик и суьматорвчитатель, входы сложения которогосоединеныс входами второго запоми 2 О нающего блока, входы вычитания - свыходами второго .регистра числа, авыходы - с инФормационными входамигруппы элементов И, первые и вторыевходы схемы сравнения соединены свьходами первого регистра числа исчетчика соответственно, а выход ее. подключен к входу блока управления,третий выход которого подключен куправляющему входу сумматора-зычитателя, счетный вход счетчика подклюЗО чен к управляющим входам группы элементов И.Источники информациипринятые во внимание при экспертизе1, Каган Б. Н. и Каневский М. М.З 5 ЦиФровые вычислительные машины и си, .стемы, М., "Энергия", 1973, с. 12-18.2. Семотюк М. В, и Боюн В. П. Операционные устройства для суммированияпарных произведений и перемножения40 комплексных чисел. - "Управляющиесистемы и машины", 1978, В Э, с. 8792, рГс. 1 (прототип),807280 тавитель Н. Измайловаред С, Мигунова Корректор И. Мус едактор Л. Кев 2/7 Филиал ППП "Патент", г. ужгород, ул. Проектн Тираж 756ВНИИПИ Государственн по делам изобрете3035, Москва, Ж,Подписноекомитета СССРй и открытийушская наб., д. 4/