Устройство для преобразования координат

 

Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислителях. Целью изобретения является повышение быстродействия. Устройство содержит регистры 1, 2 координат, регистр 3 угла, регистры 4, 5 младших разрядов, буферные регистры 6,7, счетчик циклов 8, блок 9 памяти, сумматоры 10, 11, мультиплексоры 12, 13, блок 14 управления и имеет вход 15 первой координаты, вход 16 второй координаты, вход 17 угла, выход 18 первой координаты, выход 19 второй координаты, вход 20 запуска. 1 з.п. ф-лы, 6 ил.

СОЮЗ СОВЕТСКИХ соцИАлистичесних

РЕСПУБЛИК

Л0„„1481751 (504 G 06F 7 548

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ПМПЬ7,::„.:;

Б. ЬЛ,4

К A BTOPCHOMY СВИДЕТЕЛЬСТВУ

Авторское свидетельство СССР № 1254475, кл. G 06 F 7/548, 1986. (21) 4268579/24-24 (22) 26.06.87 (46) 23.05.89. Бюл. № 19 (71) Саратовский политехнический институт (72) С. К. Дауров и В. И. Кнышев (53) 681.325 (088.8) (56) Авторское свидетельство СССР

¹ 734703, кл. G 06 F 7/548, 1978. (54) УСТРОЙСТВО ДЛЯ ПРЕОБРАЗОВАНИЯ КООРДИНАТ

2 (57) Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислителях. Целью изобретения является повышение быстродействия. Устройство содержит ре HcTpbl 1, 2 К0ординат, регистр 3 угла, регистры 4, 5 младших разрядов, буферные регистры 6, 7, счетчик циклов 8, блок 9 памяти, сумматоры 10, 11, мультиплексоры 12, 13, блок 14 управления и имеет вход 15 первой координаты, вход 16 второй координаты, в од 17 угла, выход 18 первой координаты, выход 19 второй координаты, вход 20 запуска. i з. п. ф-лы, 6 ил.

1481751

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

Целью изобретения является повышение быстродействия.

На фиг. 1 представлена функциональная схема устройства; на фиг. 2 — функциональная схема блока управления; на фиг. 3 — узел анализа знаков; на фиг. 4— шифратор режимов сумматоров; на фиг. 5— узел управления циклами; на фиг. 6 узел микропрограммного автомата.

Устройство содержит первый регистр 1 координат, второй регистр 2 координат, регистр 3 угла, первый регистр 4 младших разрядов, второй регистр 5 младших разрядов, первый буферный регистр 6, второй буферный регистр 7, счетчик 8 циклов, блок 9 памяти, первый сумматор 10, второй сумматор 11, первый мультиплексор 12, второй мультиплексор 13, блок 14 управления, вход

15 первой координаты, вход 16 второй координаты, вход 17 угла, выход 18 первой координаты, выход 19 второй координаты, вход 20 запуска.

Блок 14 управления содержит узел 21 микропрограммного автомата, узел 22 анализа знаков, узел 23 управления циклами, шифратор 24 режимов сумматоров.

Узел 22 анализа знаков содержит первый 25 и второй 26 мультиплексоры, первый 27, второй 28, третий 29, четвертый 30, пятый 31 и шестой 32 триггеры, первый ЗЗ и второй 34 элементы ИСКЛЮЧАЮШЕЕ

ИЛИ, первый 35, второй 36, третий 37, четвертый 38 элементы И, третий 39 и четвертый 40 мультиплексоры.

Шифратор режимов сумматоров содержит первый 41 и второй 42 дешифраторы, элементы ИЛИ 43 — 48 с первого по шестой.

Узел управления циклами содержит первый триггер 49, генератор 50 импульсов, первый элемент ИЛИ 51, первый счетчик 52, второй счетчик 53, первый элемент И 54, дешифратор 55, второй элемент ИЛИ 56, второй триггер 57.

Узел микропрограммного автомата содержит генератор 58 импульсов, первый счетчик 59, дешифратор 60, первый элемент И 61, второй элемент И 62, второй счетчик 63, блок 64 памяти, регистр 65, второй дешифратор 66, элемент НЕ 67, третий дешифрагор 68, элемент И-ИЛИ 69.

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

Устройство осуществляет преобразование прямоугольных координат на плоскости по алгоритму таблично-итерационного преобразования координат

Р-1

ХО+0=А {(Х! 2 Р) -cos (ср,)— со — (У!2 Р) - sin (ср;)5..2 р-I

Ус +0= ((У, 2 Р)- сов (ср,)+

+(Х, 2 Р) sin (ср;)(2 где P, M — количество отрезков разбиения соответственно кодов координат и угла; — номера соответственно вычислительного цикла и такта;

P, m — разрядность кодовых отрезков координат и угла.

Исходный алгоритм (1) табл ично-итерационного преобразования координат можно представить в следующем виде: д

ХО+и= — .Z Х -2 р; Y +0= Х К ;,;2 р, (2) с=о с О где К„;, К„; — i-e константы, считанные из пал мяти в j-ом цикле и численно равные содержимым в фигурных скобках выражения (1) .

Раскроем суммы в выражениях (2) и полученные выражения приведем к формуле

Горнера:

20

Х + = (...(К „р, ° 2 +К„р ) 2 + „+

+K„;) 2 Р+К„,;

У(1+!) ((y 2 — р+К ) 2 — р+ +

+К„;) ° 2 Р+К„„.

Пуск устройства осуществляется и ри подаче сигнала на вход 20 блока 14 управления. По этому сигналу начинает функционировать узел 21 микропрограммного авто.мата, который устанавливает мультиплексоры 12 и 13 в положение «1», затем, подавая сигналы записи на регистр 2 угла и буферные регистры 6, осуществляют запись исходных данных ср, Х и У, установленные предварительно на входах 17, 15 и 16.

40 Так как формирование констант функциональной таблицы, хранимой в блоке 9 памяти, осуществлялось без использования знаковых разрядов исходных данных, то возникает необходимость запоминания знаков исходных и промежуточных данных, которые бу4 дут использованы для определения квадранта результирующего вектора. Все эти действия выполняет узел 22 анализа знаков.

Значения знаковых разрядов Х(0) и Y (О) из буферных регистров 6 и 7 поступают на входы узла 22 анализа знаков. Так как триггер 27 находится в исходном (нулевом) состоянии, то нулевой сигнал с его выхода устанавливает мультиплексоры 39 и 40 в положение, при котором пропускаются сигналы Х(0), Y(0) на входы второго 28 и третьего 29 триггеров. Четвертый триггер 30 находится в нулевом состоянии и своим инверсным выходом устанавливает мультиплексоры 25 и 26 в положение «1», при

1481751

20

55 этом Х(0), Y(0) поступают на входы триггеров 31 и 32. Узел 21 микропрограммного автомата подает сигнал «Фиксация знаков», который записывает Х (О), Y (О) в указанные триггеры.

При необходимости перевода вектора в первый квадрант, выполняется перевод соответствующих кодов координат в прямую форму. Для увеличения быстродействия используется шифратор 24 режимов сумматоров. Узел 21 микропрограммного автомата получает сигнал з1дпХ;P signY, анализирует его и, еслй он равен О, то, управляя работой шифратора 24 режимов сумматоров, осуществляет перевод вектора в первый квадрант. При этом на выходах шифратора 24 режимов сумматоров появляются сигналы, в результате чего первый сумматор 10 устанавливается, например, в режим сложения, а второй сумматор 11 — в режим прохождения операнда через сумматор без изменения. Установив режимы первого этапа узел

21 микропрограммного автомата вырабатывает сигнал записи в буферные регистры 6 и 7, в которых записываются коды с выходов первого и второго сумматоров 10 и 11. Первый сумматор !О, находясь в режиме суммирования, складывает содержимое первого буферного регистра (исходная координата Х в дополнительном коде) и значения кода на выходе блока 9 памяти (код 11...1 при запрещенном блоке 9 памяти) . На втором этапе первый сумматор 10 устанавливается в режим инвертирования и исходная координата Х переводится в прямую форму, а координата Y остается без изменения.

После перевода вектора в первый квадрант узел 21 микропрограммного автомата переходит к анализу сигналов с выхода узла 22 анализа знаков. Если исходный вектор находился во втором или четвертом квадранте, то выполняется операция «Перемена». Для этого первый и второй мультиплексоры 12 и 13 устанавливаются в положение «3» и при подаче сигнала записи на буферные регистры 6 и 7 они обмениваются содержимыми. Факт выполнения операции «Перемена» фиксируется в узле 22 анализа знаков путем подачи импульса, под действием которого триггер 27 опрокидывается и устанавливает мультиплексоры 39 и 40 в положение «2», т. е. происходит подготовка для последующей смены знаков.

В начале следующего цикла значения Х(0), Y (О) будут просуммированы по модулю 2 в триггерах 28 и 29, но в обратной принадлежности. Таким образом в триггерах 27—

29 будут формироваться значения modzZH, signX u sign Y.

Вектор переведен в первый квадрант, выполнена операция «Перемена» и другие необходимые действия, поэтому следующей операцией узла 21 микропрограммного автомата является перезапись содержимых буферных регистров 6 и 7 в р.. 1 гры координат 1 и 2 соответственно и зап. ск узла 23 управления циклами. По сигналу «Запуск» триггер 49 устанавливается в единичное lloложение, одновременно этим же сигналом через логический элемент ИЛИ 51 сбрасывается двоичный счетчик 52, а также счетчик 53. Генератор 50 импульсов, разрешенный сигналом с прямого выхода триггера 49, подает на счетный вход двоичного счетчика 52 серию импульсов, под действием которых содержимое счетчика будет нарастать, в связи с чем на выходах дешифратора 55 будут последовательно появляться сигналы.

Сигнал с нулевого выхода дешифратора увеличивает счетчик 53 íà 1. Сигнал с первого выхода дешифратора 55 осуществляет запись младших кодовых отрезков координат Х, в р-разрядные регистрь.: 4 11 5 младп1.1õ раз,рядов соответственно. Следу «щие сигналы, начиная с второго и до (1п-, )-;o выходов дешифратора 55, объединяются 1oi ическим элементом ИЛИ 56 и поступ«1от на входы сдвига режимов координат 1 1 2 и оуферных регистров 6 и 7, вызывая сдвиг их содержимых на р-разрядов вправо. Сигнал е третьего выхода дешифратора 55 уе1анавливает триггер 57 в единичное положение, разрешая тем самым Bbioop пз блока 9 памяти констант по адресу, определяемым совокупностью кодовых отрезков координат X„Y l;одового отрезка угла q; и номера ц1;кла

Результаты на выход 1x перво;о и 1;торого сумматоров 10 H 11 через первый и второй мультиплексоры 12 и 13 поступают .:а входы буферных регистров 6 и 7, в кс горые записываются сигналом с седьмого выход;1 дешифратора 55. Сигнал с воеьмогг вых«да сбрасывает триггер 57, считыяа1111е пз блока памяти завершаегся. Сигнал е девятого выхода дешифратора 55 проверяет значен1 е ечегчика 53 тактов. Если значение счетчика не равно числу отрезков коорд.Ills 1 Р, то 1а его выходе отсутствует сигнал, что разреи1ае1 элемент И 54, и поэтому сигнал е давятoro выхода проходит через этот элемент, а также через элемент ИЛИ 51 на вход сброса счетчика 52. Таким образом выполHÿoòñÿ каждый вычислительный такт и начпнаетея следующий. Как только содержимое счетчика

53 станет равным Р, элемент И 54 будет запрещен и сигнал с девятого выхода дешнфратора 55 не произведет сброса счетчика 52, в связи с чем появится сигнал на девятом выходе дешифратора 55, который сбросит триггер 49 и заблокирует в целом узел 23 управления циклами, завершив тем самым вычислительный цикл.

Узел 21 микропрограммного автомата после окончания работы узла 24 управления циклами переходит к анализу содержимого счетчика 8 циклов и, если оно меньше величины (М вЂ” 1), увеличивает счетчик на 1, затем выполняет сдвиг влево на m разрядов регистра 3 угла и приступает к фикса1481751

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

55 ции знаков координат промежуточного вектора. В дальшейнем повторяются уже описанные действия в узле 22 анализа знаков, в частности, если вектор в результате выполнения цикла вышел за пределы первого квадранта, то его знаки фиксируются, а затем путем перевода соответствующих кодов координат в прямую форму вектор возвращается в первый квадрант и т. д.

Описанный вычислительный процесс повторяется до тех пор, пока содержимое счетчика 8 циклов не станет равным (М вЂ” 1).

В этом случае узел 21 микропрограммного автомата совместно с узлом 22 анализа знаков и шифратором 24 режимов сумматоров приступает к заключительной операции: определению квадранта результирующего вектора.

Процесс определения знаков результирующего вектора начинается с подачи узлом 21 микропрограммного автомата в узел 22 анализа знаков сигнала, под действием которого триггер 30 устанавливается в единичное состояние. Сигнал с прямого выхода триггера 30, совместно с сигналом signcp, с помощью элементов И 35 и 36 устанавливает соответствующий режим мультиплексоров 25 и 26. Логика обработки накопительных знаков для определения знаков результирующего вектора следует из следующих соотношений:

П Р= Х П Q sign(p;

Cр=ыgпф

Сигнал соответствует логической функции MT1 Q signy и реализуется логическим элементом ИСКЛЮЧАЮЩЕЕ ИЛИ 33. Узел

21 микропрограммного автомата анализирует значение этого сигнала и, если

ЯП Q signy=1, выполняется операция «Перемена». Значение С, или signq> определяет в какой режим необходимо установить мультиплексоры 25 и 26, чтобы выполнить соответствующие пересылки значений signX и sign Y из триггеров 28 и 29 в триггеры 31 и 32.

Заключительной операцией узла 21 микропрограммного автомата является перевод содержимых буферных регистров 6 и 7 в соответствующие формы. Эта операция выполняется с использованием шифратора режимов сумматоров в описанной последовательности.

1. Устройство для преобразования координат, содержагцее два регистра координат, регистр угла, два мультиплексора, два сумматора, счетчик циклов, блок памяти и блок управления, причем вход угла устройства соединен с информационным входом регистра угла, выход которого соединен с первым входом группы адресных входов блока памяти, второй вход группы адресных входов которого соединен с выходом счетчика цик5

10 !

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

2. Устройство по и. 1, отличающееся тем, что блок управления содержит узел микро1481751

10 кб,7 к 10 к11 к 1,2 кУ к4,Х к126 om 7 am ото программного авгомата, узел анализа знаков, узел управления циклами и шифратор режимов сумматоров, причем входы запуска и контроля циклов блока управления соединены с одноименными входами узла микропрограммного автомата, первый, второй и третий выходы которого соединены соответственно с вторым, седьмым и девятым выходами блока управления, четвертый выход узла микропрограммного автомата соединен с входом запуска узла управления циклами, выходы с первого по четвертый которого соединены соответственно с десятым, первым, четвертым и восьмым выходами блока управления, пятый выход узла управления циклами соединен с входом признака оконча- 15 ния цикла узла микропрограммного автомата, пятый, шестой, седьмой и восьмой выходы узла микропрограммного автомата соединены с входами признаков соответственно смены знаков, знака результата, сброса и фиксации знака узла анализа знаков, входы признаков знака угла, первой и второй координаты которого соединены соответственно с первым, вторым и третьим входами узла анализа знаков блока управления, первый и второй выходы узла анализа знаков соединены соответственно с йервым и вторым входами анализа положения вектора узла микропрограммного автомата, третий и четвертый выходы узла анализа знаков соединены с входами знака соответственно первой и второй координаты шифратора режимов сумматоров, первый и второй входы стробирования узла анализа знаков соединены с девятым и десятым выходами узла микропрограммного автомата.

1481751

1481754

Составитель С. Куликов

Редактор -I. Гратилло Техред И. Верес Корректор М. Самборская

Заказ 2690/49 Тираж 669 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям прн ГКНТ СССР

113035, Москва, Ж вЂ” 35, Раушская наб., д. 4/5

Г1роизводственно-издательский комбинат «Патент», г. Ужгород, у:l. Гагарина, 101