Вычислительное устройство для поворота вектора
Изобретение относится к цифровой вычислительной технике и может быть использовано для выполнения операции поворота вектора в вычислительных системах. Цель изобретения - повышение быстродействия устройства. Для этого в устройство введены блок памяти, сумматоры, вычитатели, три сдвигателя и третий мультиплексор, которые позволяют проводить процесс коррекции длины, не ожидая окончания операции поворота вектора. Блок памяти обеспечивает выдачу констант как для операции поворота вектора, так и для операции коррекции его длины. Блок управления обеспечивает выполнение обеих операций по алгоритму Воллера с непосредственной поверкой сходимости, что позволяет уменьшить число итераций. 1 з.п. ф-лы, 2 ил.
СОЮЗ СОВЕТСНИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИН
<50 4 С 06 F 7/548
ГОСУДАРСТВЕННЫЙ НОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И OTHPblTHRM
ПРИ ГКНТ СССР
1 ;
ОПИСАНИЕ ИЗОБРЕТЕНИЯ . (2 1) 4353523/24-24 (22) 31.12.87 (46) 07.11.89,Бюл. У 41 (72) Е,Ю.Яворский (53) 681.325(088.8) (56) Авторское свидетельство СССР
Ф 940155, кл. G 06 F 7/544, 1982. . Байков В.Д., Смолов В.Б. Специализированные процессоры. Итерационные алгоритмы и структуры. И.: Радио и связь, 1985, с.288.
Авторское свидетельство. СССР
М - 857979, кл. G 06 Г 7/544, 1981. (54) ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО ДЛЯ
ПОВОРОТА ВЕКТОРА (57) Изобретение относится к цифровой вычислительной технике и может быть
Изобретение относится к цифровой вычислительной технике и может быть использовано для выполнения операции поворота вектора в вычислительных системах.
Цель изобретения — повьппение быстродействия устройства.
На фиг.1 представлена структурная схема устройства на фиг.2 — вариант выполнения блока управления.
Устройство содержит мультиплексоры 1-3, регистры 4-7, сдвигатели
8-13, блок 14 памяти, сумматоры-вычитателй 15-21, блок 22 управления, входы 23-28, выходы 29-31 устройства, входы 32-37, выходы 38-49 блока управления, формирователи 50 и 51 приращения номера итерации мультиплек„„Я0„„1520511, А 1
2 использовано для выполнения операции поворота вектора в вычислительных системах. Цель изобретения — повышение быстродействия устройства. Для этого в устройство введены блок памяти, сумматоры, вычитатели, три сдвигателя и третий мультиплексор, которые позволяют проводить процесс коррекции длины, не ожидая окончания операции поворота вектора. Блок памяти обеспечивает выдачу констант как для операции поворота вектора, так и для операции коррекции его длины. Блок управления обеспечивает выполнение обеих операций по алгоритму Воллера с непосредственной поверкой сходимости, что позволяет уменьшить число итераций. 1 s.ë.ô-лы, 2 ил, 1 табл.
Вишь соры 52-55, регистры 56-58, блок 59 памяти, схему 60 сравнения, сумматоры
61 и 62, элемент ИПИ 63, элементы
И 64-69, элементы ИСЕЛЮЧАИЦЕЕ ИЛИ
70-72, элемент НЕ 73.
СД
Формирователи 50 и 51 приращения номера итерации представляют собой логические матрицы и могут быть выполнены на основе микросхем 556 РТ
В зависимости от разрядности чисел, обрабатываемых в устройстве, логические матрицы могут наращиваться по разрядности: младших - по 15 раз- и рядов, всех последующих — по 14 разрядов. В соответствии с этим выбирается количество микросхем 556 PT 1.
Входы микросхем А2,...,А15 для младших разрядов, АЗ,...,А14 для стар1520511 на вход разрешения выборки PB той же г I микросхемы и на вход А1 микросхемы старших разрядов. На вход А1 микросхемы, на которую поступают младшие разряды входного кода, подается сигнал низкого уровня. Выход
В7 поступает на вход А2 микросхемы старших разрядов. По выходу все микросхемы объединены и значение устанавливается в соответствии с кодом, поступаюпим с микросхемы, у которой вход разрешения выборки PB в состоянии низкого уровня. ших — являются входами логической
Матрицы. В таблице приведены логическая функция, которую выполняет микросхема для младших рязрядов после прожига. Иикросхемы для старших разрядов на выходах Вб,...,В1 содержат код, равный сумме кода для микросхемы младших разрядов и двоичного кода номера разряда входа АЗ данной микросхемы.
Выход В8 имеет функциональное значение выхода переноса. Он поступает
Входы
) ) Выходы
А7 А8 A9... А15 А1б 81 В2 ВЗ В4 Â5 Вб В7 В8
А1 А2 А3 А4 А5 Аб
Х Х
О Х
О О
0 0
О О
О О
О О
О
1 1
О }
О
0 1
0 О 0 О
1 1, 1 1
О О 0 О
1 1
О... ее о
О...
0 1 1 1 1 1
1 О 1 1 1
О О О О 0 О
} 0 О О О
О О О 1
О О О 1
О 0 О О
0 О 1 О
Поворот вектора осуществляет по следующим зависимостям:
1 . -(i t )
35 1 i 2
K+n. =К ° --1n {1+2 ) !
1; = segno(,.
-(1 И;)
Х. =*Х-К g 2 7
)+s )
+ n {1)
40 где K,— Ê принимают значения +1.
Коррекция длины вектора на величину е, где К вычисляется по формулам (1) производится по следующим
45 зависимостям:
-(i+@;1 ж ;+К ;2 ° Х(, 1 (1+ 1 ), -(сб П1)
2 Ы,, ° K Y(2 агс },2
Х..+ ta = Х.
1 i
+ш= + .2
111 J
KK) + m) = К). 2 - 1n (1 + а ;.- 2 () 3 ()» ) )
2 ; (2}
f3 = з Яп К;, j = j+mj.
1
Исходные данные для первого этапа: Х У - исходные координаты вектора; a(, — угол поворота; К0=0, для
I второго этапа s качестве исходных данных — результаты вычислений на первом этапе. В результате вычислений
1 Х Х Х
О О 1 Х
Х Х Х
0 0 О 1
О 1 1 0
О 0 О О
О 1 1 1
О 0 - О 0
0 1
О 0 О О
О 1 1 1
Х Х Х...
Х Х Х...
Х Х Х...
Х Х Х...
Х Х Х...
Х Х Х...
Х Х Х...
Х Х О
Х Х 1 .Х Х 1
Х Х 0
Х Х 0
Х Х 1
Х Х 1
0 О О
О 0 О
1 0 О
О О
О О
1 О О
1520511 получают координаты вектора после поворота на угол o(< .
Зависимости (1) и (2) позволяют осуществить поворот вектора и кор5 рекцию его длины по алгоритму Волдера с непосредственной проверкой сходимости LJI2 3. При этом величины приращения номера итерации n;,m могут изменять свое значение от нуля до )0 максимального значения количества итераций и вычисляются исходя иэ значения величин a ., К.. Значение п.,m .
1 определяется как количество старших разрядов, совпадающих со знаковым 15 разрядом величин,, К соответственно. Значения d на первом этапе и к на втором зтапе вычисляются со сдвигом, аналогично алгоритмам Кеджитта (JI2) что позволяет увеличить точ- 20 ность, а также упрощает вычисления величин m, и и)
Кроме того, устройство позволяет совместить по времени оба этапа вычислений. При этом необходимо обесне- 25 чить выполнение неравенства (3) + и ) j
Коррекция длины вектора по зависи- 30 мостям (2) начинает производится,когда значение коэффициента удлинения К еще точно не известно. Сходимость обеспечивается за счет того, что применяется метод непосредственной проверки сходимости. Кроме того, так как величины К на итерации 1= в два раза больше, чем на итерации . это обеспечивает высокую скорость сходимости. 40
Устройство работает следующим образом.
На вход 26 подается сигнал запуска, который обнуляет регистры 56 и
57, хранящие номера итераций i u j соответственно, обнуляет регистр 6 числа К и открывает мультиплексоры
1-3 на прием информации с входов
23-25 соответственко. При появлении .на входе 28 устройства внешнего синхроимпульса в регистры 4-6 записываются величины Х„ У, Ы„ а в регистр
58 — код операций. После этого устройство производит вычисления в соответствии с выражениями (1), (2).При этом регистры 4 и 5 хранят текущие значения Х и У, сдвигатели 8 и 9 производят арифметический сдвиг этих величин влево на (i + и;) разрядов, сумматоры-вычитатели 15 и 17 производят вычисления значений Х;,„
I и У;„, в соответствии с выражениями (1), сдвигатели 12 и 13 осуществляют сдвиг на величину (j + n ), сум) У маторы-вычитатели 16 и 18 вычисляют значения Х, У1 в соответствии с (2). Кроме того, сумматоры-вычитатели 15 и 17 могут при соответствующем сигнале на управляющих входах пропускать без изменения сигналы с регистров 4 и 5 соответственно. Лналогично, сумма. ры-вычитатели 16 и 18 могут прот кать беэ изменений информацию с выход..в сумматоров 15 и 17 соответственно, Такая ситуация встречается в том ох чае, когда нужно не выполнять чередную итерацию из выражений (1 и (2) для сумматоров-вычитателей i и 17 — если итерации по выражекию .1) закончены, а по выражению (2) прололжаются, для сумматоров 16 и 18 — если не выполняется неравенство (3
С выходов сумматоров-вычитателей значения Х и У через мультиплексоры
1 и 2 поступают на регистры 4 и 5.После этого аналогичным образом выполняется следующая итерация. Регистр 7 хранит текущие значения a(. Сдвигатель 11 сдвигает эти значения на и разрядов влево, затем из этого кода на сумматоре-вычитателе 19 вычитается величина (j+ь;) -(1В;)
, 2 arctg2 которая поступает с первого выхода блока 14 памяти при подаче на его первый вход величины (i+n;) из блока управления. Регистр 6 хранит текущие значения величины К, иэ которых на сумматоре-вычитателе 20 вычитается величина 1/2 1п (1+2 ), поступающая из блока 14 памяти. Сдвигатель 10 осуществляет сдвиг вправо на
m. разрядов, а ка сумматоре-вычита) теле из этой величины в соответствии с выражением (2) вычитается величина 1п (1+ (; 2 ) )2 1 )), которая поступает с второго выхода блока памяти при передаче на его второй и третий входы величин (j + m ) и
J из блока управления соответственно.
Кроме того, сумматор-вычитатель 20 может пропускать на выход информацию с регистра 6, а сумматор-вычитатель 21 — число со сдвкгателя 10 аналогично сумматорам 15, 17 и 16,18.
1520511
Для вычисления значений m и и, в блоке управления служат соответственно формирователи 51 и 50. Таблица истинности этих матриц приведена в таблице. При проведении вычислений по выражениям (1) и (2) величины и, и m соответственно поступают че1 1 рез мультиплексоры 52 и 53 на накапливающие сумматоры, состоящие из регистра 56 и сумматора-вычитателя 61 для числа итераций i и регистра 57 и сумматора-вычитателя 62 для числа итераций j, В период времени после окончания итераций и до прихода сигнала запуска для решения новой задачи, в момент загрузки исходных данных и выдачи результатов решения, в момент времени, когда итерации по выраже- 20 нию (1) закончены, а итерации по выражению (2) еще продолжаются для сумматора 61 числа i а также для моI мента времени, когда не выполняется неравенство (3), т.е. не нужно вы- 25 полнять итерации по выражению (2) для сумматора 62 числа j — управление накапливающими сумматорами производится блоком 59 памяти посредством подачи сигналов на управляющие 30 входы мматоров 61 и 62, регистров
56 и 57, мультиплексоров 52 и 53 и на информационные входы мультиплексоров 52 и 53. Информация с блока памяти считывается в зависимости от ве- „
35 личины сигнала о выголнении равенства (3), поступающ . о на его входы с регистра 56 и элемента ИЛИ 63.
Значения и и m 1 с мультиплексоров
52 и 53 через выходы блока 46 и 45 поступают на управление сдвигателями 11 и 10, а значения (i+n;) и (j+m ) через выходы 47 и 48 — на уп) равление сдвигателями 8,9,12,13 и блоком 14 памяти, Элементы И 64-66 и 68 в зависимости от состояния сиг/ налов с блока 59 памяти пропускают сигналы внешней синхронизации через выходы блока 39-41 управления на регистры 4,5 и 7 и на регистр 56.
Управление регистром 57 может осущюствляться как непосредственно блоком памяти при подаче на первый вход элемента И 67 сигнала логического
"0", так и в зависимости от выполнения неравенства (3), которое анализируется схемой 60 сравнения при подаче на вход элемента И 67 с блока 59 памяти сигнала логической "1". Элемент И,69 в зависимости от управляющего сигнала с элемента ИЛИ 63 пропускает на регистр 57 внешний синхроимпульс. Регистр кода операции 58 позволяет в зависимости от применяемой модификации алгоритма Волдера коммутировать в зависимости от конкретной модификации с входом первого формирователя 50 либо число d,,либо У,, определять из знака либо У> либо с помощью числа из блока 59 памяти с помощью мультиплексора 54, определять g. как знак
J числа К, либо как число из блока 59 памяти с помощью мультиплексора 55 также изменять значения К -К в вы1 3 ражении (1) с помощью элементов ИСКЛЮЧЛЮГ ЕЕ ИЛИ 70-72, Формула изобретения
Вычислительное устройство для поворота вектора, содержащее четыре регистра, два сумматора-вычитателя, два сдвигателя, два мультиплексора, причем первые информационные входы первого и второго мультиплексоров соединены с первым и вторым информационными входами устройства соответственно, выходы первого и второго регистров соединены с информационными входами одноименных сдвигателей, о т л и ч а ю щ е е с я тем, что, с целью повьппения быстродействия в него введены третий мультиплексор, блок памяти,с третьего по шестой сдвигатели, с третьего по седьмой сумматоры-вычитатели, блок управления, причем первый информационный вход третьего мультиплексора соединен с третьим информационным входом устройства, первый управляющий вход которого соединен с управляющими входами первого, второго и третьего мультиплексоров, первым управляющим входом третьего регистра и является первым входом блока управления, второй вход которого соединен с вторым управляющим входом устройства, а третий вход — с вторым управляющим входом третьего регистра и является третьим управляющим входом устройства, информационный вход третьего регистра соединен с выходом седьмого сумматора-вычитателя и четвертым входом блока управления, пятый вход которого соединен с выходом пятого сумматоравычитателя и вторым информационным
152051! входом третьего мультиплексора, второй информационный вход второго мультиплексора подключен к выходу четвертого сумматора вычитателя и яв5 ляется шестым входом блока управления, с первого по шестой, выходы которого соединены с управляющими входами соответственно седьмого сумматора-вычитателя, четвертого, второ- 1р го, первого регистров, третьего и первого сумматоров-вычитателей, седьмой выход блока управления подключен к первым управляющим входам .второго и четвертого сумматоров-вычитателей 15 и первым входом блока памяти, восьмой и девятый выходы блока управления соединены с управляющими входами соответственно третьего и четвертого сдвигателей, десятый выход блока уп- 20 равления соединен с управляющими входами первого и второго сдвигателей и вторым входом блока памяти,третий вход которого и управляющие входы пятого и шестого сдвигателей под- 25 ключены к одиннадцатому выходу блока управления, двенадцатьпi выход которого соединен с управляющим входом пятого сумматора-вычитателя, второй информационный вход первого мультиплек- щ сора соединен с выходом второго сумматора-вычитателя, выходы первого и второго мультиплексоров соединены с информационными входами первого и второго регистров соответственно, выход первого регистра соединен с первым информационным входом первого сумматора-вычитателя, с информационным входом пятого сдвигателя и является первым выходом устройства, выход вто- qp рого регистра соединен с первым информационным входом третьего сумматора-вычитателя, с информационным входом шестого сдвигателя и является вторым выходом устройства, выход третьего мультиплексора соединен с информационным входом четвертого регистра, выход которого подключен к информационному входу одноименного сдвигателя и является третьим выходом уст- 5g ройства, выходы первого и второго сдвигателей соединены с вторыми информационными входами соответственно третьего и первого сумматоров-вычитателей, выходы которых подключены к первым входам соответственно четвертого и второго сумматоров-вьгчитателей, вторые входы которых соединены с выходами соответственно шестого и пятого сдвигателей, первый, второй и третий выходы блока памяти соединены с первыми входами соответственно пятого, седьмого и шестого сумматоров-вычислителей, вторые входы которых подключены к выходам соответственно четвертого и третьего сдвигателей и третьего регистра, выход шестого сумматора-вычитателя соединен с информационным входом третьего сдвигателя.
2. Устройство по п.1, о т л и ч аю щ е е с я тем, что блок управления содержит два формирователя приращения номера итерации, четыре мультиплексора, три регистра, блок памяти, два сумматора, схему сравнения,элемент ИЛИ, шесть элементов И, элемент
НЕ, три элемента ИСКЛПЧЛЛ!!ЕЕ ИЛИ, причем первые управляющие входы первого, второго и третьего регистров объедичены и подключены к первому входу блока, выходы первого и второго формирователей приращения номера итерации соединены .с первыми информационными входами соответственно первого и второго мультиплексоров, выходы которых соединены с первыми информа-, ционными входами одноименных сумматоров и являются соответственно девятым и восьмым выходами блока, выход первого сумматора подключен к информационному входу первого регистра, первому входу схемы сравнения и является десятым выходом блока, выход второго сумматора соединен с информационным входом второго регистра, вторым входом схемы сравнения и является одиннадцатым выходом блока,пятый, шестой и двенадцатый выходы которого подключены к выходам соответственно первого, второго и третьего элементов исключающее ИЛИ, первые входы которых офъединены с управляющими входами третьего и четвертого мультиплексоров и подключены к выходу третьего регистра, информационный вход которого является шестым входом блока, а второй управляющий вход объединен с первыми ннформационными входами третьего и четвертого мультиплексоров, первыми входами элементов ИЛИ, с первого по пятый элементов И, вторыми информационными входами первого и второго мультиплексоров, управляющими входами первого и второго сумматоров, управляющими входами первого и второго мультиплексоров
1520511!
2, и подключены к выходу блока памяти,,выход третьего мультиплексора соеди нен с вторыми входами первого, вто"рого и третьего элементов ИСКЛЮЧАЮ.PgE ИЛИ и входом первого формировате5 ля приращения номера итерации, вход
;второго формирователя приращения номера итерации подключен к четвертому
;входу блока и к второму информацион- 1g
:ному входу четвертого мультиплексора, выход которого непосредственно и через элемент BE подключен соответственно к седьмому и первому выхо;дам блока, третий, второй и четвертый 15
;выходы которого являются выходами
;соответственно первого, второго и пя.:того элементов И, вторые входы которых и вторые входы третьего и шесто го элементов И объединены и соединены 20 с третьим входом блока, выходы третьего, четвертого и шестого элементов И подключены соответственно к второму управляющему входу первого регистра, к второму входу элемента ИЛИ и к второму управляющему входу второго регистра, выход которого соединен с вторым информационным входом второго сумматора, второй информационный вход первого сумматора соединен с выходом первого регистра и с первым входом блока памяти, второй вход которого соединен с выходом элемента ИЛИ и вторым входом шестого элемента И, второй вход четвертого элемента И подключен к выходу схемы сравнения, второй и третий информационные входы третьего мультиплексора являются соответственно вторым и пятым входами блока.
152051 1
Составитель Е.Яворский
Техред А.Кравчук Корректор Л.Патай
Редактор В.Данко
Заказ 6758/49 Тираж 668 Подписное
BHHHIIH Государственного комитета по изобретениям и открытиям при ГКНТ СССР
113035, Москва, Ж-35, Раушская наб., д. 4/5
Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101
