Вычислительное устройство для поворота вектора Советский патент 1989 года по МПК G06F7/548 

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

Цель изобретения - повьппение быстродействия устройства.

На фиг.1 представлена структурная схема устройства} на фиг.2 - вариант выполнения блока управления.

Устройство содержит мультиплексоры 1-3, регистры 4-7, сдвигатели 8-13, блок 14 памяти, сумматоры-вычи- тателй 15-21, блок 22 управления, входы 23-28, выходы 29-31 устройства, входа 32-37, выходы 38-49 блока управления, формирователи 50 и 51 приращения номера итерации мультиплексоры 52-55, регистры 56-58, блок 59 памяти, схему 60 сравнения, сумматоры 61 и 62, элемент ИЛИ 63, элементы И 64-69, элементы ИСКЛЮЧАЮЩЕЕ ИЛИ 70-72, элемент НЕ 73.

Формирователи 50 и 51 приращения номера итерации представляют собой логические матрицы и могут быть вм- полнены на основе микросхем 556 РТ 1. В зависимости от разрядности чисел, обрабатьшаемых в устройстве, логические матрицы могут наращиваться по разрядности: младших - по 15 разрядов, всех последующих - по 14 разрядов. В соответствии с этим выбира-. ется коли-чество микросхем 556 РТ 1. Входа микросхем А2,...,А15 для младших разрядов, АЗ,...,А14 для старСП

го

о ел

,315205

ших - являются входами логической йатрицы. В таблице приведены логическая функция, которую вьтолняет микросхема для младших рязрядов после прожига. Микросхемы для старших разрядов на выходах В6,...,В1 содержат код, равный сумме кода для микросхемы младших разрядов и двоичного кода номера разряда входа A3 данной микро- JQ схемы.

Выход В8 имеет функциональное значение выхода переноса. Он поступает

114

на вход paзpJBшeния выборки РВ той же микросхемы и на вход А1 микросхемы старших разрядов. На вход А1 микросхемы, на которую поступают младшие разряды входного кода, подается сигнал низкого уровня. Выход В7 поступает на вход А2 микросхемы старших разрядов. По выходу все микросхемы объединены и значение устанавливается в соответствии с кодом, поступающим с микросхемы, у которой вход разрешения выборки РВ в состоянии низкого уровня.

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

Поворот вектора осуществляет по следующим зависимостям:

X,.yX;-K/,2--.Y.,

Y,., Y,K. X,.

.«s , .. V .) arctgZ-

.n .«;2:.,.2

Х..ш Х. ... . X., .,У,.Л,. V 1,, ... sign к-;

j j + m j .

Исходные данные для первого этапа: X о У - исходные координаты вектора; о( в - угол поворота, , для

К

,, -find .);

Vfi sign о/. ,

1 i + п. ,

(1)

где К,-Kg принимают значения ±1.

Коррекция длины вектора на величину е, где К вычисляется по формулам (1), производится по следующим зависимостям:

второго этапа в качестве исходных данных - результаты вычислений на первом этапе, В результате вычислений

сумматоры-вычитатели 15 и 17 производят вычисления значений .

ращения номера итерации п ,-,т : могут изменять свое значение от нуля до максимального значения количества итераций и вычисляются исходя из значения величин , Kj. Значение П),1П определяется как количество старших разрядов, совпадающих со знаковым разрядом величин о/ , К: соответственно. Значения d на первом этапе и к на втором этапе вычисляются со

к I ,, в соответствии с выражениями (1), сдвигатели 12 и 13 осуществляют сдвиг на величину (j п-), сумматоры-вычитатели 16 и. 18 вычисляют значения X., Y. в соответствии с

получают координаты вектора после поворота на угол ,

Зависимости (1) и (2) позволяют осуществить поворот вектора и коррекцию его длины по алгоритму Волде- ра с непосредственной проверкой сходимости Л2. При этом величины при(2). Кроме того, сумматоры-вычита- (0 тели 15 и 17 могут при соответствующем сигнале на управляющих входах пропускать без изменения сигналы с регистров 4 и 5 соответственно. Аналогично , сумма V -«ры-вычитатели 16 15 и 18 могут проп ;кать без изменений информацию с выхст лв сумматоров 15 и 17 соответственно. Такая ситуация встречается в том случае, когда сдвигом, аналогично алгоритмам Меджит- нужно не выполнять очередную итера- та Л2, что позволяет увеличить точ- 20 цию из выражений (V и (2) для сумма- ность, а также упрощает вычисления торов-вычитателей 1) и 17 - если ите- величин m . и п, .рации по вьфаженйю .О закончены, а

Кроме того, устройство позволяет по выражению (2) прслолжаются, для совместить по времени оба этапа вы- сумматоров 16 и 18 - если не выполня- числений. При этом необходимо обеспе- 25 ется неравенство (3), чить выполнение неравенстваС выходов сумматоров-вычитателей

значения X и Y через мультиплексоры

i + п : j + m . (3) 1 и 2 поступают на регистры 4 и 5.После этого аналогичным образом выполняКоррекция длины вектора по зависи- ЗО ется следующая итерация. Регистр 7 мостям (2) начинает производится,ког- хранит текущие значения d-, Сдвига- да значение коэффициента удлинения К еще точно не известно. Сходимость обеспечивается за счет того, что при- да на сумматоре-вычитателе 19 вычита- меняется метод непосредственной про- ,, ется величина верки сходимости. Кроме того, так как величины К на итерации в два раза больше, чем на итерации i - это обеспечивает высокую скорость сходимости.

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

На вход 26 подается сигнал запустель 11 сдвигает эти значения на

п разрядов влево, затем из этого ко. .. o-(

,-2 arctp2

которая поступает с первого выхода блока 14 памяти при подаче на его 4Q первый вход величины (i+n-) из блока управления. Регистр 6 хранит текущие значения величины К, из которых на сумматоре-вычитателе 20 вьтитается

величина 1/2 In (1+2 ) , посту- д5 пающая из блока 14 памяти, Сдвигака, которьш обнуляет регистры 56 и 57, хранящие номера итераций i и j соответственно, обнуляет регистр 6 числа К и открьшает мультиплексоры 1-3 на прием информации с входов 23-25 соответственно. При появлении

величина 1/2 In (1+2 ) , посту- д5 пающая из блока 14 памяти, Сдвигатель 10 осуществляет сдвиг вправо на та. разрядов, а на сумматоре-вычитателе из этой величины в соответствии с вьфажением (2) вычитается величина входе 28 устройства внешнего син- 50 1 1 X j )2 i , которая хроимпульса в регистры 4-6 записыва- поступает с второго выхода блока па- ются величины Х, Y,o(o, а в регистр мяти при передаче на его второй 58 - код операции, После этого уст- и третий входы величин (j + m :) и «f. ройство производит вычисления в соот- из блока управления соответственно. ветствии с выражениями (1), (2).При 5 РО того, сумматор-вычитатель 20

этом регистры 4 и 5 хранят текущие значения X и Y сдвигатели 8 и 9 производят арифметический сдвиг этих величин влево на (i + п ;) разрядов.

может пропускать на выход информацию с регистра 6, а сумматор-вычитатель 21 - число со сдвигателя 10 аналогично сумматорам 15, 17 и 16,18,

сумматоры-вычитатели 15 и 17 производят вычисления значений .

к I ,, в соответствии с выражениями (1), сдвигатели 12 и 13 осуществляют сдвиг на величину (j п-), сумматоры-вычитатели 16 и. 18 вычисляют значения X., Y. в соответствии с

(2). Кроме того, сумматоры-вычита- тели 15 и 17 могут при соответствующем сигнале на управляющих входах пропускать без изменения сигналы с регистров 4 и 5 соответственно. Аналогично , сумма V -«ры-вычитатели 16 и 18 могут проп ;кать без изменений информацию с выхст лв сумматоров 15 и 17 соответственно. Такая ситуация встречается в том случае, когда нужно не выполнять очередную итера- цию из выражений (V и (2) для сумма- торов-вычитателей 1) и 17 - если ите- рации по вьфаженйю .О закончены, а

ется следующая итерация. Регистр 7 хранит текущие значения d-, Сдвига- да на сумматоре-вычитателе 19 вычита- ется величина

тель 11 сдвигает эти значения на

п разрядов влево, затем из этого коется следующая итерация. Регистр 7 хранит текущие значения d-, Сдвига- да на сумматоре-вычитателе 19 вычита- ется величина

. .. o-(

,-2 arctp2

которая поступает с первого выхода блока 14 памяти при подаче на его первый вход величины (i+n-) из блока управления. Регистр 6 хранит текущие значения величины К, из которых на сумматоре-вычитателе 20 вьтитается

величина 1/2 In (1+2 ) , посту- пающая из блока 14 памяти, Сдвигатель 10 осуществляет сдвиг вправо на та. разрядов, а на сумматоре-вычитателе из этой величины в соответствии с вьфажением (2) вычитается величи 1 1 X j )2 i , которая поступает с второго выхода блока па- мяти при передаче на его второй и третий входы величин (j + m :) и «f. из блока управления соответственно. РО того, сумматор-вычитатель 20

тель 10 осуществляет сдвиг вправо на та. разрядов, а на сумматоре-вычитателе из этой величины в соответствии с вьфажением (2) вычитается величи 1 1 X j )2 i , которая поступает с второго выхода блока па- мяти при передаче на его второй и третий входы величин (j + m :) и «f. из блока управления соответственно. РО того, сумматор-вычитатель 20

может пропускать на выход информацию с регистра 6, а сумматор-вычитатель 21 - число со сдвигателя 10 аналогично сумматорам 15, 17 и 16,18,

Для вычисления значений mi и п. в блоке управления служат соответственно формирователи 51 и 50. Таблица истинности этих матриц приведена в таблице. При проведении вычислений по вьфажениям (1) и (2) величины п. и т- соответственно поступают через мультиплексоры 52 и 53 на накапливающие сумматоры, сос1:оящие из ре- гистра 56 и сумматора-вычитателя 61 для числа итераций i и регистра 57 и сумматора-вычитателя 62 для числа итераций j.

В период времени после окончания итераций и до прихода сигнала запуска для решения новой задачи, в момент загрузки исходных данных и выдачи результатов решения, в момент времени, когда итерации по выраже- нию (1) закончены, а итерации по выражению (2) еще продолжаются для сумматора fei числа i, а также для мо мента времени, когда не выполняется неравенство (3), т.е. не нужно вы- полнять итерации по вьфажению (2) дпя сумматора 62 числа j - управление накапливающими сумматорами производится блоком 59 памяти посредством подачи сигналов на управляющие входы умматоров 61 и 62, регистров 56 и 57, мультиплексоров 52 и 53 и на информационные входы мультиплексоров 52 и 53. Информация с блока памяти считывается в зависимости от величины сигнала о выполнении равенства (3), поступающих а на его входы с регистра 56 и злемента ИЛИ 63., Значения п , и m , с мультиплексоров 52 и 53 через выходы блока 46 и 45 поступают на управление сдвигатвля- ми 11 и 10, а значения (1+п) и (j+m ,) через выходь 47 и 48 - на управление сдвигателями 8,9,12,13 и блоком 14 памяти. Элементы И 64-66 и 68 в зависимости от состояния сигналов с блока 59 памяти пропускают сигналы внешней синхронизации через выходы блока 39-41 управления на регистры 4,5 и 7 и на регистр 56.

Управление регистром 57 может осу щюствляться как непосредственно блоком памяти при подаче на первьй вход элемента И 67 сигнала логического О, так и в зависимости от выполнения неравенства (3), которое анализируется схемой 60 сравнения при подаче на вход злемента П 67 с блока 5 памяти сигнала логической 1, Эле

5 О д

5

мент И .69 в зависимости от управляющего сигнала с элемента ИЛИ 63 пропускает на регистр 57 внешний синхроимпульс. Регистр кода операции 58 позволяет в зависимости от применяемой модификации алгоритма Волдера коммутировать в зависимости от конкретной модификации с входом первого формирователя 50 либо число /j ,либо YJ , определять из знака а , либо Y{, либо с помощью числа из блока 59 памяти с помощью мультиплексора 545 определять . как знак числа К, либо как число из блока 59 памяти с помощью мультиплексора 55 также изменять значения в выражении (1) с помощью элементов ИСК- ЛЮЧАЮЩЕ IfflH 70-72.

Формула изобретения

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

, tO 5 20 25 ЗО 40 д5 0

5

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

29

27