Устройство для реализации алгоритма волдера

(191 (11) 3(59 С 06 Е 7/5 ОПИСАНИЕ ИЗОБРЕТЕНК АВТОРСКОМУ СВИДЕТЕЛЪСТВУ нным входом третьетателя, установочныеорого и третьего вторым информациго сумматора-вычвходы первого,триггеров соеди ны с нулевыми входа шестого триг ми четвертого, пятогогеров, единичные входыиены с информационными оторьм соедиходами соотго, второго и треть иничные выходы четветственно первго регистров, едвертого, пятогосоединены с первходами соответвого и третьегоинформационныего коммутаторов и шестого триггеров ыми информационными твенно второго, перкоммутаторов, вторые ходы первого и второ соединены с выходом ОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(56) 1. Оранский А.М. "Аппаратные методы в цифровой вычислительной технике". Минск, 1977, БГУ, с. 132, рис. 5. 19.2. Авторское свидетельство СССР 1( 813423, кл, С 06 Г 7/548, 1981 (прототип).(54)(57) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ АЛГОРИТМА ВОЛДЕРА, содержащее и последовательно соединенных ячеек, где и разрядность устройства, каждая из которых содержит первый, второй и третий регистры, первый, второй и третий сумматоры-вычитатели, первый, второй и третий коммутаторы, причем выходы младших разрядов первого,второго и третьего регистров соединены с первыми информационными входами соответственно первого, второго и третьего сумматоров-вычитателей, выходы первого и второго. коммутаторов соединены с вторыми информационными входами соответственно первого и второго сумматоров-вычитателей, выходы первого, второго и третьего сумматоров-вычитателей ( -й ячейки (где= 1, 2, 3, ,и) соединены с информационными входами соответственно первого, второго и третьего регистров (1+1)-й ячейки, входы первого, второго и третьего регистров первой ячейки соединены соответственно с первым, вторым и третьим входами записи операндов устройства, информационные выходы первого и второго сумматоров-вычитателей и-й ячейки соедицецы соотцетствецно с первым и вторым выходамирезультата устройства, о т л и ч а ющ е е с я тем, что, с целью сокращения затрат оборудования, устройствосодержит блок управления, каждаяячейка содержит кольцевой регистр,с первого по шестой триггеры, причемединичные входы первого, второго итретьего триггеров соединецы с выходами переноса соответственно первого,второго и третьего сумматоров-вычитателей, управляющие входы которыхсоединены с информационным выходомтретьего коммутатора, третьи информационные входы первого, второго и третьего сумматоров-вычитателей соединены с единичными выходами соответственно первого, второго и третьеготриггеров, единичные входы которыхсоединены с управляющими входами первого, второго регистров и кольцевого регистра, информационный входкоторого соединен с выходом младшего разряда кольцевого регистра и(1 +1) -го разряда соответственно вто рого и первого регистров, первыйуправляющий вход второго коммутатоФра соединен с вторым управляющимвходом первого коммутатора, первый управляющий вход которого соединен с вторым управляющим входом второго коммутатора, второй информационный вход третьего коммутатора соединен с выходом пятого триггера, причем блок управления содержит генератор тактовых импульсов, триггер, элемент НЕ, сдвиговый регистр и элемент И, причем управляющий вход генератора тактовых импульсов соединен с входом запуска устройства и вторым устано - вочным входом сдвигового регистра, первый установочный вход которого соединен с выходом первого разряда сдвигового регистра, инверсный выход первого разряда которого соединен с первым входом элемента И, второй вход которого соединен с выходом генератора тактовых импульсов и входом элемента НЕ, выход которого соединен с синхронизирующим входом сдвигового регистра, информационный вход триггера соединен с входом выбора операции устройства, инверсный выход триггера соединен с вторым управляющим входом третьего коммутатора 1 -й ячейки, прямой выход триггера блока управления соединен с первым управляющим входом третьего коммутатора1-й ячейки, причем управляющие входь,всех регистров и единичные входы первого, второго и третьего триггеров1-й ячейки соединены с выходом генератора тактовых импульсов блока управления, первый и второй управляющие входы третьего коммутатора 1 -йячейки соединены соответственно спрямым и инверсным выходами триггера кода операций блока управления,первый управляющий вход первого коммутатора и второй управляющий входвторого коммутатора 1-й ячейки соединены с прямым выходом 1 -го разря-да сдвигового регистра блока управления, инверсный выход 1 -го разрядакоторого соединен с вторым управляющим входом первого коммутатора и первым управляющим входом второгокоммутатора д-й ячейки, вход(и)-го разряда сдвигового регистра блока управления соединен с источником сигнала 1" и с первым и вторым управляющими входамисоответственно второго и первого коммутаторов первой ячейки, а второй ипервый управляющие входы второго ипервого коммутаторов первой ячейки подключены к шияе нулевого потенциала,информационный выход третьего сумматоравычитателя и-й ячейки соединен с третьим выходом результата устройства.Изобретение относится к вычислительной технике и может быть использовано в вычислительных системах для вычисления элементарных функций, преобразования координат, для выполнения операций поворота вектора.Известен вычислитель параллельно- последовательной структуры, содержащий три сумматора, четыре регистра, два сдвигающих регистра, постоянное запоминающее устройство, выполняющий преобразования по методу Волдера, который заключается в итеративном процессе, состоящем из шагов 111.Недостатком устройства является низкое быстродействие при обработке количества данных, так как новое данное можно начать обрабатывать только после того, как закончена обработка предыдущего.Наиболее близким по техническойсущности к предлагаемому является вычислительное устройство для реализации алгоритма Волдера, содержащееи последовательно соединенных ячеек,.причем каждая из (п) первых ячеексодержит три сумматора, три регистра 1 р и три сдвигателя, а и-я ячейка содер.жит два сумматора, три регистра идва сдвигателя, Устройство работаетпо конвейерному принципу. В каждойего ячейке, являющейся ступенью кон вейера, реализуется одна итерацияалгоритма Волдера, При обработкемассивов чисел быстродействие устрой.стиа достигает времени1 г.м ф 1 кмис рг,где 1, Ткм - задержка информациисоответственно и разрядным сумматором и 5коммутатором;1- время записи информации в регистр. Затраты оборудования,на устройство составляют10 1" )г (" )сн (п )кмгде первое, второе и третье слагаемые - соответственно число триггеров,одноразрядных сумматоров и коммута 15торов.В устройстве производится обработка данных, представленных полнораэрядным кодами, Во многих случаяхэти данные поступают в цифровое утс 20ройство поразрядно, что позволяетпроизводить их переэарядную обработку Г 21.Недостатком устройства является25большие затраты оборудования при по -разрядном поступлении обрабатываемыхданных.Цель изобретения - сокращениезатрат оборудования,Поставленная цель достигается темчто в устройство для реализации алгоритма Волдера, содержащее и после -довательно соединенных ячеек, гдеП разрядность устройства, каждая изкоторых содержит первый, второй и 35третий регистры, первый, второй итретий сумматоры-вычитатели, первый,второй и третий коммутаторы, причемвыходы младших разрядов первого, второго и третьего регистров соединены 40с первыми информационными входамисоответственно первого, второго итретьего сумматоров-вычитателей, выходы первого и второго коммутаторовсоединены с вторыми информационными 45входами соответственно первого и второго сумматоров-вычитателей, выходыпервого, второго и третьего сумматоров-вычитателей д-й ячейки (где1, 2, 3, , и) соединены с информационными входами соответственно первого, второго и третьего регистров(1+1)-1 ячейки, входы первого, второго регистров первой ячейки соединенысоответственно с первым, вторым и 55третьим входами записи операндовустройства, информационные выходыпервого и второго сумматоров-вычитателей и-й ячейки соединены соответственно с первым .и вторым выходами результата устройства, введен блок управления, каждая ячейка содержит кольцевой регистр, с первого по шестой триггеры, причем единичные входы первого, второго и третьего триггеров соединены с выходами перекоса соответственно первого, второго и третьего сумматоров-вычитателей, управляющие входы которых соединены с информационным выходом третьего коммутатора, третьи информационные входы первого, второго и третьего сумматоров-вычитателей соединены с )единичными выходами соответственно первого, второго и третьего триггеров, единичные входы которых соединены с управляющими входами первого,второго регистров и кольцевого регистра, информационный вход которого соединен с выходом младшего разряда кольцевого регистра и вторым информационным входом третьего сумматоравычитателя, установочные входы первого, второго и третьего триггеров соединены с нулевыми входами четвертого, пятого и шестого триггеров, единичные входы которых соединены с информационными входами соответственно первого, второго и третьего регистров, единичные выходы четвертого, пятого и шестого триггеров соединены с первыми информационными входами соответственно второго, первого и третьего коммутаторов, вторые информационные входы первого и второго коммутаторов соединены с выходом ( +1)-го разряда соответственно второго и первого регистров, первый управляющий вход второго коммутатора соединен с вторым управляющим входом первого коммутатора, первый управляющий вход которого соединен с вторымуправляющим входом второго коммутатора, второй информационный вход третьего коммутатора соединен с выходом пятого триггера, причем блок управления содержит генератор тактовых импульсов, триггер, элемент НЕ, сдвиговый регистр и элемент И, причем управляющий вход генератора тактовых импульсов соединен с входом запуска устройства и вторым установочным входом сдвигового регистра, первый установочный вход которого соединен с выходом первого разряда сдвигового регистра, инверсный выход первогоразряда которого соединен с первым входом элемента И, второй вход которого соединен с выходом генератора тактовых импульсов и входом элемента НЕ, выход которого соединен с, 5 синхрониэирующим входом сдвигового регистра, информационный вход триггера соединен с входом выбора операции устройства, инверсный выход триг. гера соединен с вторым управляющим10 входом третьего коммутатора -й ячейки, прямой выход триггера блока управления соединен с первым управляющим входом третьего коммутатора 1-й ячейки, причем управляющие входы 15 всех регистров и единичные входы первого, второго и третьего триггеров 1-й ячейки соединены с выходом генератора тактовых импульсов блока управления, первый и второй управляю. 20 щие входы третьего коммутатора 1-й ячейки соединены соответственно с прямым и инверсным выходами триггера кода операций блока управления, первый управляющий вход первого коммута тора и второй управляющий вход второго коммутатора 1-й ячейки соединены с прямым выходом -го разряда сдвигового регистра блока управления, инверсный выход -го разряда которого ЗО соединен с вторым управляющим входом первого коммутатора и первым управляющим входом второго коммутатора 1-й ячейки, вход (и)-го разряда сдвигового регистра блока управления соединем с источником сигнала "1" и с первым и вторым управляющими входами соответственно второго и первого коммутаторов первой ячейки, а второй и первый управляющие входы второго и первого коммутаторов первой ячейки подключены к шине нулевого потенциала, информационный выход третьего сумматора-вычитателя и-й ячейки соединен с третьим выходом результата устройства.На фиг. 1 представлена блок-схема устройства для реализации алгоритма Волдера; на фиг. 2 - функциональная схема -й ячейки устройства; на фиг. 3 - функциональная схема блока управления; на фиг, 4 - временная диаграмма работы устройства,Устройство (фиг. 1).содержит ипоследовательно соединенных ячеек 1с входами 2-10, выходами 11-13, блок14 управления с входами 15 и 16. Каждая ячейка 1 ус тройс тва (фиг, 2) содержит сумматоры-вычитатели 17-19, триггеры 20-251 слвигоньн регистры 26-28, кольцев й регистр 29, коммутаторы 30-32.Блок 14 управления (фиг. 3) содержит генератор 33 тактовых импульсов, элемент НЕ, инвертор 34, сдвиговый регистр 35, триггер 36 кода операции, элемент И 37.Входы 6 - 8 первой ячейки 1 соединены с входами устройства, выходы 11 - 13 каждой предыдущей ячейки соединены соответственно с входами 6 - 8 каждой последующей ячейки, входы 6 - 8 каждой ячейки соединены с входамп соответственно триггера 23 и регистра 26, триггера 24 и регистра 27, триггера 25 и регистра 28, выходы регистров 26 - 28 соединены соответственно с первыми входами сумматоров 17 - 19, третьи входы которых соеди - иены с выходами триггеров 20 - 22, входы которых соединены с выходами данных сумматоров, вторые входы сумматоров, вторые входы сумматоров 17 и 18 соединены с выходами соответственно коммутаторов 30 и 31, первые информационных входы которых соединены с выходами триггеров 24 и 23, а вторые - с выходами 1-х разрядов регистров 26 и 27, первые и вторые управляющие входы коммутаторов 3 1 и 30 соединены соответственно с входами 10, а коммутаторы 30 и 31 с входами 9 ячейки, выходы триггеров 24 и 25 соединены с вторым и первым информационными входами коммутатора 32, выход которого соединен с управляющими входами сумматоров 17 - 19, второй вход сумматора 19 соединен с выходом и входом кольцевого регистра, управляющие входы триггеров 20-22 и регистров 26-29 соединены с входом ячейки 2, управляющие входы триггеров 23-25 соедииены с входом ячейки 5 и с входамисбросов триггеров 20-22, первый и второй управляющие входы коммутатора 32 соединенны с входами ячеек 4-3, выходы данных сумматороо 17 - 19 соединены с выходами ячеек 11 - 13, выход генератора 33 тактовых импульсов соединен с входами 2 всех ячеек 1 устройства, с входом схемы 37 И и с входом инвертора 34, выход которого соединен с входом синхронизации сдвигового регистра 35, прямой1115049 40 ния первой итерации алгоритма Волдера. При этом значение константы с,предварительно записано в регистр 29и поступает младшими разрядами вперед на сумматор 19 с циклическим 5сдвигом в каждом такте.После поступления в устройство2 и импульсов результаты первой ите.рации над первыми операндами будутнаходиться в регистрах 26 - 28 вто.рой ячейки 1, а в регистрах первойячейки будут находиться вторые операнды. Во второй ячейке над первымиоперациями поразрядно будет выполняться вторая итерация, аналогичнопервой, с тем отличием, что последние разряды значений хи у будутсуммироваться соответственно со знаковыми разрядами уи х. Это объясняется сдвигом приращения на разрядвправо. Знаковые разряды поступаютна сумматоры 17 и 18 через коммутаторы 30 и 31 по сигналу 10 (фиг. 4).В регистре 29 второй ячейки записанавторая константа. Поскольку данныйрегистр является кольцевым, то послепоступления импульсов разряды константы в нем займут прежнее положение,В это время в первой ячейке над вторыми операциями выполняется первая ЗОитерация, результаты которой поразрядно поступают во вторую ячейку, накоторой результаты второй итерациинад первыми операндами поразряднопоступают в третью ячейку. 35После поступления 3 и импульсовв третьей ячейке будет выполнятьсятретья итерация над вторыми операндами, а в первой ячейке - перваяитерация над третьими операндами,При этом в регистре третьей ячейкизаписана третья константа, а двапоследних разряда значений регистров27 и 26 суммируются с содержимымсоответственно триггеров 24 и 23, 45в которые записаны по сигналам знаковые разряды значений у и х соответственно поступающим по шине 5(фиг. 4),1В дальнейшем после поступлениякаждых последующих импульсов результаты из предыдущей ячейки 1 переписываются в последующую ячейку 1.,Приэтом в каждой -й ячейке 29 записанах-я константа, а последниеразрядов (1=0,1, ,и) регистров 26и 27 суммируются соответственно ссодержимым триггеров 24 и 23. 10Для исключения влияния переносов, хранимых в триггерах 20-22, на резуль - таты сложения последующих операндов по шине 5 производится их сброс каждым и-м импульсов.После поступления и импульсов на выходе устройства появляются младшие разряды результатов обработки первых операндов, а в дальнейшем в каждом такте будут появляться следую. щие разряды результатов.В блоке 14 управления после поступления и импульсов происходит сброс регистра 35, что позволяет на его выходах получать периодические сигналы.Сигнал записи, поступающий по шине 5, формируется схемой 37 И, через которую сигналом 10 разрешается прохождение каждого Р -го тактового импульса.Такт работы устройства определяется временемсикм 1. г,гдесм - время сложения на одноразрядном сумматоре;задержка информации коммутатора;время записи информации врегистр.Быстродействие устройства равноТ= п 1,Затраты оборудования на устройство определяются по соотношениюЯ=(4 п б н) рг ф(Зп)см + Оп 1 км,Как видим, на предлагаемое устройство требуется меньше одноразрядных сумматоров и в и раз меньше одноразрядных коммутаторов и лишь на1/4 увеличивается число одноразрядных регистров. Причем, следует заметить, что все регистры 29 ячеек устройства,можно заменить одним блокомпостоянной памяти, имеющей высокуюстепень интеграции.Пусть и=32, т. е. обработке подлежат массивы 32 разрядных чисел. Для реализации известного устройства на элементах 155 серии потребуется 768 микросхем 155 ТМ 8, 768 микросхем 155 ИПЗ, 288 микросхем 155 ИП 4, 1536 микросхем 155 ЛР 1; всего 3360 микросхем.Для реализации предлагаемого устройства на той же элементной базе ипри 7 ой же разрядности потребуется 816 микросхем 155 ТМ 8, 48 микросхем 155 ИПЗ, 48 микросхем 155 ЛР 1, 8 микросхем 155 РЕЗ, для хранения констант; всего 920 микросхем.Как видно, имеется выигрыш по оборудованию в 3,65 раза,Высокая однородность структуры устройства и очень малое число внеш них связей делают его перспективный для изготовления в виде БИС.Эффективность изобретения заключается в сокращении оборудования за счет поразрядной обработки в процессе времени.1115049П Составитель В.ВенцельРедактор Е,Лушникова Техред С Легеза ректор Г, Решет ник каз 67 лиал ППП "Патент", г.Ужгород) ул.Проектная, 4 35ВНИИХИ Госудпо делам и113035) Иоск Тираж б 98 Подписноерственного комитета СССРобретений и открытийа, Ж) Раушская наб., д. 4/5 9 л. Оп.9 пОл