Вычислительное устройство для поворота вектора

(50 4 С 06 Р 7/548 ГОСУД АРСТ 8 ЕННЫИПО ИЗОБРЕТЕНИЯМ ИПРИ ГКНТСССР ИТЕТРЫТИЯМ ПИСАНИЕ ИЗОБРЕТЕНИ М Ю(54) ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО ДЛЯПОВОРОТА ВЕКТОРА(57) Изобретение относится к цифровойвычислительной технике и может быть Изобретение относится к цифровой вычислительной технике и может быть использовано для выполнения операции поворота вектора в вычислительных системах.Цель изобретения - повьппение быстродействия устройства.На фиг.1 представлена структурная схема устройства на фиг.2 - вариант выполнения блока управления.Устройство содержит мультиплексоры 1-3, регистры 4-7, сдвигатели 8-13, блок 14 памяти, сумматоры-вычитателй 15-21, блок 22 управления, вхо ды 23-28, выходы 29-31 устройства, входы 32-37, выходы 38-49 блока управления, формирователи 50 и 51 приращения номера итерации мультиплек 801520511 2использовано для выполнения операции поворота вектора в вычислительных системах. Цель изобретения - повышение быстродействия устройства, Для этого в устройство введены блок памяти, сумматоры, вычитатели, три сдвигателя и третий мультиплексор, которые позволяют проводить процесс коррекции длины, не ожидая окончания операции поворота вектора. Блок памяти обеспечивает выдачу констант как для операции поворота вектора, так и для операции коррекции его длины. Блок управления обеспечивает выполнение обеих операций по алгоритму Воллера с непосредственной поверкой сходимости, что позволяет уменьшить число итераций. 1 з.п.ф-лы, 2 ил, 1 табл. соры 52-55, регистры 56-58, блок 59 памяти, схему 60 сравнения, сумматоры 61 и 62, элемент ИПИ 63, элементы И 64-69, элементы ИСЮЮЧ(ИЦЕЕ ИЛИ 70-72, элемент НЕ 73.Формирователи 50 и 51 приращения номера итерации представляют собой логические матрицы и могут быть выполнены на основе микросхем 556 РТ В зависимости от разрядности чисел, обрабатываемых в устройстве, логические матрицы могут наращиваться по разрядности: младших - по 15 разрядов, всех последующих - по 14 разрядов. В соответствии с этим выбирается количество микросхем 556 РТ 1. Входы микросхем А 2 .А 15 для младших разрядов, (3(14 для стар1520511 на вход разрешения выборки РВ той же1 микросхемы и на вход А 1 микросхемы старших разрядов. На вход А 1 микросхемы, на которую поступают младшие разряды входного кода, подается сигнал низкого уровня. Выход В 7 поступает на вход А 2 микросхемы старших разрядов. По выходу все микросхемы объединены и значение устанавливается в соответствии с кодом, поступаюпщм с микросхемы, у которой вход разрешения выборки РВ в состоянии низкого уровня. ших - являются входами логическойМатрицы. В таблице приведены логическая функция, которую выполняет микросхема для младших рязрядов послепрожига. Иикросхемы для старших разрядов на выходах ВбВ 1 содержаткод, равный сумме кода для микросхемы младших разрядови двоичного коданомера разряда входа АЗ данной микро"схемы,Выход В 8 имеет функциональное значение выхода переноса. Он поступает Входы ВыходыА 7 А 8 А 9 А 15 А 1 б В 1 В 2 ВЗ В 4 В 5 Вб В 7 В 8 А 1 А 2 АЗ А 4 А 5 Аб Х Х Х 0 ХО 1 1 1 1 11 0 1 1 10 0 О 0 0 О1 0 0 0 0 0 0 О 1 0 0 0 1 О 0 0 0 0 0 1 О а а аЩВЭи Эщ ВПоворот вектора осуществляет по следующим зависимостям:+ и (1) 40где К,-К принимают значения +1.Коррекция длины вектора на величину е", где К вычисляется по формулам (1), производится по следующим 45зависимостям;(3 112(2) Т 3 = зп К;,3 =За+Пав1Исходные данные для первого этапа: ХУ - исходные координаты вектора; Ы, - угол поворота; КО=О, для второго этапа в качестве исходныхданных - результаты вычислений на первом этапе, В результате вычислений 1 Х Х Х 0 0 1 ХХ Х Х 0 О 0 1 О 1 1 0 0 О 0 О 0 1 1 1 О 0 0 0 0 10 О 0 0 0 1 1 1получают координаты вектора после поворота на угол еЗависимости (1) и (2) позволяютосуществить поворот вектора и кор 5рекцию его длины по алгоритму Волдера с непосредственной проверкой сходимости Л 2 3. При этом величины приращения номера итерации и;,ш могутизменять свое значение от нуля домаксимального значения количества итерации и вычисляются исходя иэ значения величин с., К . Значение и.,ш1определяется как количество старшихразрядов, совпадающих со знаковым 15разрядом величинК соответственно. Значения с( на первом этапеи к на втором этапе вычисляются сосдвигом, аналогично алгоритмам Кеджитта Л 2, что позволяет увеличить точность, а также упрощает вычислениявеличин ш, и и,Кроме того, устройство позволяетсовместить по времени оба этапа вы"числений, При этом необходимо обеснечить выполнение неравенстваКоррекция длины вектора по зависи мостям (2) начинает производится,когда значение коэффициента удлинения К еще точно не известно, Сходимость обеспечивается за счет того, что применяется метод непосредственной проверки сходимости, Кроме того, так как величины К на итерации : в два раза больше, чем на итерацииэто обеспечивает высокую скорость сходимости. 40Устройство работает следующим образом.На вход 26 подается сигнал запуска, который обнуляет регистры 56 и 57, хранящие номера итерацийи 1 соответственно, обнуляет регистр б числа К и открывает мультиплексоры 1-3 на прием информации с входов 23-25 соответственко, При появлении .на входе 28 устройства внешнего синхроимпульса в регистры 4-6 записываются величины Х У , Ы а в регистр 58 - код операций, После этого устройство производит вычисления в соответствии с выражениями (1), (2),При 55 этом регистры 4 и 5 хранят текущие значения Х и У+ сдвигатели 8 и 9 производят арифметический сдвиг этих величин влево на ( + и;) разрядов,сумматоры-вычитатели 15 и 17 производят вычисления значений Х;, и У;, в соответствии с выражекиями (1), сдвигатели 12 и 13 осуществляют сдвиг на величину (1 + ш ), сумК У маторы-вычитатели 16 и .18 вычисляют значения Х , У 1 в соответсТвии с (2), Кроме того, сумматоры-вычитатели 15 и 17 могут при соответствующем сигнале на управляющих входах пропускать без изменения сигналы с регистров 4 и 5 соответственно. Лналогично, сумма. ры-вычитатели 16 и 18 могут прот кать беэ изменений информацию с выход. в сумматоров 15 и 17 соответственно. Такая ситуация встречается в том схучае, когда нужно не выполнять чередную итерацию из выражений (1 и (2) для сумматоров-вычитателей 5 и 17 - если итерации по выражекию ,1) закончены, а по выражению (2) прололжаются, для сумматоров 16 и 18 - если не выполняется неравенство (3,С выходов сумматоров-вычитателей значения Х и У через мультиплексоры 1 и 2 поступают на регистры 4 и 5.После этого аналогичным образом выполняется следующая итерация. Регистр 7 хранит текущие значения Ы;. Сдвига- тель 11 сдвигает эти значения на и разрядов влево, затем из этого кода на сумматоре-вычитателе 19 вычитается величина(;ф;1 -( ф;1ф.,-2 агсср 2 которая поступает с первого выходаблока 14 памяти при подаче на егопервый вход величины (+и;) из блокауправления. Регистр 6 хранит текущиезначения величины К, иэ которых насумматоре-вычитателе 20 вычитаетсявеличина 1/2 1 и (1+2), поступающая из блока 14 памяти, Сдвигатель 10 осуществляет сдвиг вправо наи. разрядов, а ка сумматоре-вычитателе из этой величины в соответствиис выражением (2) вычитается величина 1 и (1+ ; 2 1 )2 1 1 , котораяпоступает с второго выхода блока памяти при передаче на его второйи третий входы величин (1 + щ ) ииз блока управления соответственно.Кроме того, сумматор-вычитатель 20может пропускать на выход информациюс регистра 6, а сумматор-вычитатель 21 - число со сдвкгателя 10 аналогично сумматорам 15, 17 и 16,18.Для вычисления значений щ и и,в блоке управления служат соответственно формирователи 51 и 50. Таблица истинности этих матриц приведенав таблице. При проведении вычисленийпо выражениям (1) и (2) величиныи, и ш соответственно поступают че 1рез мультиплексоры 52 и 53 на накапливающие сумматоры, состоящие из регистра 56 и сумматора-вычитателя 61для числа итераций 1 и регистра 57и сумматора-вычитателя 62 для числаитераций 1,В период времени после окончанияитераций и до прихода сигнала запуска для решения новой задачи, в момент загрузки исходных данных и выдачи результатов решения, в моментвремени, когда итерации по выражению (1) закончены, а итерации по выражению (2) еще продолжаются для сумматора 61 числа , а также для момента времени, когда не выполняетсянеравенство (3), т.е. не нужно выполнять итерации по выражению (2)для сумматора 62 числа 1 - управление накапливающими сумматорами производится блоком 59 памяти посредством подачи сигналов на управляющие 30входы мматоров 61 и 62, регистров56 и 57, мультиплексоров 52 и 53 ина информационные входы мультиплексо"ров 52 и 53, Информация с блока памяти считывается в зависимости от ве"35личины сигнала о выполнении равенства (3), поступающ. о на его входы с регистра 56 и элемента ИЛИ 63.Значения ии ш 1 с мультиплексоров52 и 53 через выходы блока 46 и 45поступают на управление сдвигателями 11 и 10, а значения (х+и;) и(+ш ) через выходы 47 и 48 - на управление сдвигателями 8,9,12,13 иблоком 14 памяти, Элементы И 64-66и 68 в зависимости от состояния сиг/налов с блока 59 памяти пропускаютсигналы внешней синхронизации черезвыходы блока 39-41 управления на регистры 4,5 и 7 и на регистр 56.50Управление регистром 57 может осущюствляться как непосредственно блоком памяти при подаче на первый входэлемента И 67 сигнала логического"0", так и в зависимости от выполнения неравенства (3), которое анализируется схемой 60 сравнения при подаче на вход элемента И 67 с блока 59памяти сигнала логической "1". Элемент И,69 в зависимости от управляющего сигнала с элемента ИЛИ 63 пропускает на регистр 57 внешний синхроимпульс, Регистр кода операции 58 позволяет в зависимости от применяемой модификации алгоритма Волдера коммутировать в зависимости от конкретной модификации с входом первого формирователя 50 либо число , ,либо У определятьиз знака либо У, либо с помощью числа из блока 59 памяти с помощью мультиплексора 54, определять . как знак/числа К, либо как число из блока 59 памяти с помощью мультиплексора 55 также изменять значения К -К в выражении (1) с помощью элементов ИСКЛЮЧЛЮГ 1 ЕЕ ИЛИ 70-72,Формула изобретенияВычислительное устройство для поворота вектора, содержащее четыре регистра, два сумматора-вычитателя, два сдвигателя, два мультиплексора, причем первые информационные входы первого и второго мультиплексоров соединены с первым и вторым информационными входами устройства соответственно, выходы первого и второго регистров соединены с информационными входами одноименных сдвигателей, о т л и ч а ю щ е е с я тем, что, с целью повьппения быстродействия в него введены третий мультиплексор, блок памяти,с третьего по шестой сдвигатели, с третьего по седьмой сумматоры-вычитатели, блок управления, причем первый информационный вход третьего мультиплексора соединен с третьим информационным входом устройства, первый управляющий вход которого соединен с управляющими входами первого, второго и третьего мультиплексоров, первым управляющим входом третьего регистра и является первым входом блока управления, второй вход которого соединен с вторым управляющим входом устройства, а третий вход - с вторым управляющим входом третьего регистра и является третьим управляющим входом устройства, информационный вход третьего регистра соединен с выходом седьмого сумматора-вычитателя и четвертым входом блока управления, пятый вход которого соединен с выходом пятого сумматоравычитателя и вторым информационнымвходом третьего мультиплексора, второй информационный вход второгомультиплексора подключен к выходу четвертого сумматора вычитателя и яв 5 ляется шестым входом блока управления, с первого по шестой, выходы которого соединены с управляющими входами соответственно седьмого сумматора-вычитателя, четвертого, второ О го, первого регистров, третьего и первого сумматоров-вычитателей, седьмой выход блока управления подключен к первым управляющим входам, второго и четвертого сумматоров-вычитателей 15 и первым входом блока памяти, восьмой и девятый выходы блока управления соединены с управляющими входами соответственно третьего и четвертого сдвигателей, десятый выход блока уп равления соединен с управляющими входами первого и второго сдвигателей и вторым входом блока памяти,третий вход которого и управляющие входы пятого и шестого сдвигателей под ключены к одиннадцатому выходу блока управления, двенадцатйй выход которого соединен с управляющим входом пятого сумматора-вычитателя, второй информационный вход первого мультиплек сора соединен с выходом второго сумматора-вычитателя, выходы первого и второго мультиплексоров соединены с информационными входами первого и второго регистров соответственно, выход первого регистра соединен с первым информационным входом первого сумматора-вычитателя, с информационным входом пятого сдвигателя и является первым выходом устройства, выход вто рого регистра соединен с первым информационным входом третьего сумматора-вычитателя, с информационным входом шестого сдвигателя и является вторым выходом устройства, выход третьего мультиплексора соединен с информационным входом четвертого регистра, выход которого подключен к информационному входу одноименного сдвигателя и является третьим выходом уст ройства, выходы первого и второго сдвигателей соединены с вторыми информационными входами соответственно третьего и первого сумматоров-вычитателей, выходы которых подключены к первым входам соответственно четвертого и второго сумматоров-вычитателей, вторые входы которых соединены с выходами соответственно шестого и пятого сдвигателей, первый, второйи третий выходы блока памяти соединены с первыми входами соответственно пятого, седьмого и шестого сумматоров-вычислителей, вторые входыкоторых подключены к выходам соответственно четвертого и третьегосдвигателей и третьего регистра, выход шестого сумматора-вычитателясоединен с информационным входом третьего сдвигателя,2. Устройство по п.1, о т л и ч аю щ е е с я тем, что блок управленияюсодержит два формирователя приращения номера итерации, четыре мультиплексора, три регистра, блок памяти,два сумматора, схему сравнения,элемент ИЛИ, шесть элементов И, элементНЕ, три элемента ИСКЛПЧЛК 1 ЕЕ ИЛИ,причем первые управляющие входы первого, второго и третьего регистровобъедичены и подключены к первомувходу блока, выходы первого и второгоформирователей приращения номера итерации соединены .с первыми информационными входами соответственно первого и второго мультиплексоров, выходыкоторых соединены с первыми инАорма-,ционными входами одноименных сумматоров и являются соответственно девятым и восьмым выходами блока, выходпервого сумматора подключен к информационному входу первого регистра,первому входу схемы сравнения и является десятым выходом блока, выходвторого сумматора соединен с информационным входом второго регистра,вторым входом схемы сравнения и является одиннадцатым выходом блока,пятый, шестой и двенадцатый выходы которого подключены к выходам соответственно первого, второго и третьегоэлементов исключающее ИЛИ, первыевходы которых офъединены с управляющими входами третьего и четвертогомультиплексоров и подключены к выходутретьего регистра, информационныйвход которого является шестым входомблока, а второй управляющий входобъединен с первыми ннформационнымивходами третьего и четвертого мультиплексоров, первыми входами элементов ИЛИ, с первого по пятый элементов И, вторыми информационными входами первого и второго мультиплексоров,управляющими входами первого и второго сумматоров, управляющими входамипервого и второго мультиплексоров,и подключены к выходу блока памяти, ,выход третьего мультиплексора соединен с вторыми входами первого, вто"рого и третьего элементов ИСКЛЮЧАЮ.Т(ЕЕ ИЛИ и входом первого формировате 5 ля приращения номера итерации, вход ;второго формирователя приращения номера итерации подключен к четвертому ;входу блока и к второму информацион :ному входу четвертого мультиплексора, выход которого непосредственно и через элемент НЕ подключен соответственно к седьмому и первому выхо,дам блока, третий, второй и четвертый 15 выходы которого являются выходами ;соответственно первого, второго и пя.того элементов И, вторые входы которых и вторые входы третьего и шестого элементов И объединены и соединены 20 с третьим входом блока, выходы третьего, четвертого и шестого элементов Иподключены соответственно к второмууправляющему входу первого регистра,к второму входу элемента ИЛИ и к второму управляющему входу второго регистра, выход которого соединен с вторым информационным входом второгосумматора, второй информационный входпервого сумматора соединен с выходомпервого регистра и с первым входомблока памяти, второй вход которогосоединен с выходом элемента ИЛИ и вторым входом шестого элемента И, второйвход четвертого элемента И подключенк выходу схемы сравнения, второй итретий информационные входы третьегомультиплексора являются соответственно вторым и пятым входами блока.1520511 Составитель Е.Яворскийедактор В,Данко Техред А,Кравчук Корректор Л.Патаю Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарин аказ 6758/4 НИИПИ Госуд Тираж 668 твенного комитета по и 113035, Москва, Ж, Подписноеретениям и открытиям при ГКНТ СССРущская наб., д. 4/5