Функциональный преобразователь

 

O Il И C A H H Е „„924714

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советскин

Социалистические

Республик (6I ) Дополнительное к авт. саид-ву (51)М. Кл.

9 06F 15/31 (22}Заявлено 19.03.80 (2I ) 2923165/18-24 с присоединением заявки УЙ (23) Приоритет

3Ьоударотааиай комитет

СССР ао делам изобретений н отормткй

Опубликовано 30.04.82. Бюллетень № 16 (53) УИК681..3(088.8) Дата опубликования описания 30.04.82

A. М. Оранский и B. И. Лебедев (72). Авторы изобретения

Белорусский ордена Трудового Красного Знам гасударственный университет им. В. И. Лени (71) Заявитель (54) ФУНКЦИОНАЛЬНЫЙ ПРЕОБРАЗОВАТЕЛЬ

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

Известно цифровое устройство для решения уравнений вида 2 =>Р+Р 1 $ содержащее сумматор-вычитатель, регистр сдвига, блок анализа состояния сумматора, блок управления Ц

Данное устройство осуществляет вычисление расстояния на плоскости от точки до одной из концевых точек отрезка, заданных в декартовой системе координат, и не предназначено для вычисления расстояьия от точки до отрезка, т.е, для вычисления функций вида

АХо "о С

Z где хо, о — коодинвты точки; А, В и

С вЂ” коэффициенты уравнения отрезка

Ак+ 6 + С = О.

Наиболее близким к предлагаемому является арифметическое устройство для поворота вектора, работакщее по алгоритму Вслдера и содержвшее три сумматора-вычитателя, три сдвиговых регистра, два коммутирукщих блока, причем выходы первого сдвигакщего регистра соединены с первой группой одноименных входов первого коммутирукщего блока, выход которого соединен с первым входом пер1О вого сумматора-вычитателя, а выходы второго сдвигакщего регистра соединены с первой группой одноименных входов второго коммутирукщего блока, выход которого соединен с первым входом второ

f5 го сумматора-вычитателя, выход первого сумматора-вычнтателя соединен с первым выходом устройства и с входом второго сдвигвкщего регистра, выход второго сумматора-вычнтателя соединен с вторым выходом устройства и с входом первого сдвигакщего регистра, выход третьего сумматора-вычитвтеля соединен с третьим выходом устройства и входом тре3 9247 тьего сдвигающего регистра, старший разряд которого соединен с первым входом. третьего сумматора-вычитателя, а второй вход, третьего сумматора-вычитателя соединен с первой группой входов устройства, вторые группы входов первого и второго коммутирующих блоков соединены соответственно с второй группой входов устройства (21

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

Поставленная цель достигается тем, что функциональный преобразователь, содержащий первый блок поворота вектора, информационные входы которого являются первой группой входов преобразователя дополнительно введены второй и третий блоки поворота вектора, две группы элементов И, вычитатель, блок управления, содержащий вычитатель аргумента, счетчик, два триггера, пять элементов

И, два коммутатора, два компаратора, три элемента ИЛЕ и элемент НЕ, причем первый и второй управляющие входы

ЗО коммутаторов соединены с выходами первого и второго триггеров соответственно и входами первого элемента ИЛИ, выход которого соединен с первым входом первого элемента И, второй вход которого яв-

35 ляется входом тактовых импульсов преобразователя, выход первого элемента И соединен с входом счетчика, выходы разрядов которого через второй элемент И соединены с управляющим входом перво40 го и второго компараторов, первым входом второго триггера, и первым входом третьего элемента И, второй вход которого соединен с выходом переполнения счетчика, выход третьего элемента И

45 соединен с первым входом первого триг- . гера и первым входом второго элемента . ИЛИ, второй вход которого соединен с выходом третьего элемента ИЛИ, входы которого соединены с выходами четвертого и пятого элементов И, входы четвертого элемента И соединены с первыми выходами компараторов, входы пятого элемента И,соединены со вторыми выходами компараторов, выход третьего элемента ИЛИ через элемент НЕ соединен с вторым входом первого триггера, установочный вход которого соединеи с входом пуска перобразователя и установоч14 4 ным входом второго. триггера, выходы коммутаторов соединены с входами вычитателя аргументов, причем информационные входы второго и третьего блоков поворота вектора являются соответственно второй и третьей группами входов преобразователя, первая и вторая группы выходов первого блока поворота вектора соединены с входами первого коммутатора, первая и вторая группы выходов третьего блока поворота вектора соедиВеАм с первыми входами первого компаратора и второго коммутатора, вторые входы которых соединены с второй груп» пой выходов второго блока поворота вектора и первыми входами второго компаратора, вторые входы которого соединены с второй группой выходов первого блока поворота вектора, выход первого триггера является выходом преобразователя, выходы первого элемента И и вычитателя аргументов соединены соответственно с первыми и вторыми управлякяцими входами блоков поворота вектора, выход второго элемента ИЛИ соединен с управляющими входами элементов И первой и второй групп, вторые axoma элементов И которых соединены соответственно с вторыми выходами второго и третьего блоков повсрота векторов, выходы элементов И первой и второй групп соединены с первыми и вторыми входами вычитателя, выход которого является выходом преобразователя.

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

На фиг. 1 представлена бпок-схема преобразователя; на фиг. 2 и 3 — блоксхемы блока поворота вектора и блока упраВления; соответственно;

Функциональный преобразователь содержит блоки 1, 2 и 3 поворота век- {1+1) SS

5, 9247 тора, блок 4 управления, группы 5 и 6 элементов И, вычислитель 7, входы преобразователя 8-13, выходы преобразователя 14 и 15.

Ка кдый блок поворота вектора содержит регистры 16 и 17. сдвига, коммутаторы 18 и 19, сумматоры-вычитатели

20 и 21, управляющие входы 22 и 23.

Блок 4 управления содержит вычитатель 24 аргументов, коммутаторы 25 0 и 26, компараторы 27 и 28, счетчик

29, триггеры 30 и 31, элементы И

32-36, элементы ИЛИ 37 -39, элемент

НЕ 40, входы 41-47, выходы 48-51.

Елок поворота вектора работает сле- tS дукщим образом.

В исходнсм состоянии координаты

Х, 3п О точки выходов блока поворота ва п о вектора соответственно заносятся через коммутаторы 18 и. 19 в сдвиговые регистры 16 и 17 и сумматоры-вычитатели 20 и 21. Затем информация в регистрах 16 и 17 сдвигается в сторону младших разрядов по актовым импульсам, поступающим по управляющему входу 25 прерывания поворота векторов 22 из 9roка 4 управления. При этом схема сдвига содержимого регистров 1 и 2 обеспечиааег органиэапи р однотактного многорас рядного сдвига в соответствии с номером З0 итерационного шага (=1, 2, З,...,n )

C для образования очередных приращений координат точек Х„- и

-{ Ô1)

Щ11

-{i+4)

„ Ч . Сдвинутая информация

Ф из регистров 16 и 17 поступает соответственно на сумматоры-вычитатели 21 и 20, где производится ее суммирова40 ние или вычитание с предыдущим результатом. Знаком сумматоров-вычитателей управляет блок 4 управления по входу

23 управления. Результаты с сумматороввычитателей 20 и 21 поступают жа выходы блока поворота вектора и через коммутаторы 18 и 19 заносятся в сумматоры 20 и 21 и сдвиговые регистры 16 и

17. Процесс поворота вектора прерывается при отсутствии тактовых импульсов на входы 22.

Таким образом, блок поворота реализует алгоритм Волдера

-{1И)

"rn,1+ = ю,a-%thorn, 1 ь

14 6 где m — фиксировано и равно или О, или

l1èëè 2.

+м, );- 0;

Q =Bi(Pl

g.=Х . - Х„.; i =.О,п-1.

1 "1,,1 11f 1

Блок 4 управления вырабатывает следующие сигналы: управление знаками сумматоров-вычитателей блоков поворота векторов 1, 2, 3; прерывание процесса. поворота векторов; разрешение прохождения информации с выходов блоков поворота векторов на вычитатель 7; указатель, что вычисляется расстояние от точки до отрезка или до концевой точки отрезка.

Блок управления работает следукщим образом.

По сигналу "Пуск, поступакщему на вход 46, триггер 30 управления устанавливается в единичное состояние, а триггер 31 управления устанавливается в нулевое состояние, При этом координаты точек Мо, М и М 1заноОЯтсЯ в блоки поворота векторов. Триггер 30 управления разрешает прохождение синхроимпульсов с выхода 45 через элемент 32 на счет- чик шагов 29 и через выход 49 на вход прерывания процесса поворота векторов .блоков поворота векторов. Это приводит к возникновению интерационного процесса поворота векторов в блоках поворота векторов. Информация х ; и х„- с выходов.

1, соответствукщих блоков поворота векторов через входы 41 и 43 и коммутаторы

25 и 26, управляемые триггером 30, поступает на входы вычитателя 24, на выходе знакового разряда которого формируется сигнал управления (), ° знаком сумматоров-вычитателей блоков поворота векторов. После проведения rl итерационных шагов на элементе И 33 формируется сигнал, раэрешакщий прохождение информации 30 и 1 э 31 и .,- ° Jil и 1 через входы 42, 44 и 47 соответственно на компараторы 27 и 2 8. Этот же сигнал с выхода элемента 33 устанавливает в нулевое состояние триггер 30 управления.

Состоянии выходов компараторов 27 и 28- о и-1 1,п-1 О,п-1 >q,q 1

МО „ ) („ «(1 1 анализируются логическими элементами И 35, 36 и логическим элементом ИЛИ 38.

Если выполняется условие 1,1 МО-П ., Ъ. . то на выходе логическо го элемента.ИЛИ 38 формируется сигнал разрешакщий прохождение информации блок 4 управления вырабатывает сигнал, разрешающий прохождение информации „.и x „c выходов блоков поворота вектора 2 и 3 через группы логических элементов И 5 и 6 на входы вычитателя

7, где вычисляется расстояние (X«„-X „ от точки МО до отрезка М„М .

При всех остальных неравенствах блок

4 управления снимает сигнал прерывания процесса поворота векторов, в резуль тате чего в блоках поворота вектора 1, 2 и 3 начинается второй итерационный цикл, направленный на совмещение проекций точек М,> и М1 (или М ). При этом

15 оператор поворота с,„определяется знаком разности 1. = g 0,1

В качестве ачапьйых условий II „ и берутся те, что получены в конце первого итерационного цикла.

20 Окончание второго итерационного цикла определяется одним из неравенств

X „- i X . ) Хо„- . При этом блок 4 управлления вырабатывает сигнал прерывания поворота векторов и сигнал, разре25 шающий прохождение информации Х ° и о,i

Хо с выходов блоков поворота вектора

2 и 3 через группы логических элементов И 5 и 6 на входы вычитателя 7, на выходе 15 которого формируется вели-, ЗО чина расстояния 2,р)Х, — Х, -)от точки

01 Я,,1

Np до ближайшей из точек Й„ и М . При этом на выходе 14 устройства выдается сигнал, указывающий, что вычисляется расстояние от точки Мо по концевой точM ки отрезка N< М .

Поскольку в основу работы устройства положен принцип псевдовращения вектсров, следует учитывать эффект деформации их, а значит и измеряемого расстояния Z.. .Это учитывается соответствующим масштабом выходной величины вычитателя 7 введением заранее вычисленных коэффициентов деформации К„=

45 = П „+ I „, в,„,. K =П + ( ( для второго итерационного цикла.

В случае необходимости проведения второго итерационного цикла достаточно ограничиться вращением только двух векторов: ОМ<> и одного из. векторов, 0М ипи ON . . В отличие от известных устройств, вычисляющих расстояние между точками на плоскости по известным зависимостям, предлагаемое устройство, кроме указанной операции вычисляет кратчайшее расстояние от точки до отрезка, что существенно расширяет его функциональные

7 924714 8 через логический элемент ИЛИ 39 на вход вычитателя функционального преобразователя. Если условие 3 „Ъ .

1 оп- 7-Ч" е- е выполняется, To HB выходе элемента HE 40, формируется сигнал, устанавливающий триггер 31 управления в единичное состояние, сигнал в котором че ез выход 50 передается на выход функционального преобразователя, указывающий, что измеряется расстояние от точки до концевой точки отрезка. При этом открывается логический элемент И 32 и начинается второй итерационный процесс в блоках поворотаванторов. Информапия По н и

Э„. (j= и, 1п--1 ) с соответствующих

"1.3 выходов блоков пов рота векторов через входы 42 и 44 и коммутаторы 25 и

26 поступает на входы вычитатепя 23, где формируется сигнал управления знаком сумматоров-вычитателей блоков поворота векторов. Второй итерационный процесс заканчивается после того, как в счетчике 29 зафиксировано число 2 и итерационных шагов, При этом на выхо.

1 | де логического элемента И 33 формируется сигнал, разрешающий прохождение информации на входы вычитателя функционального преобразователя. Этот же . сигнал устанавливает в нулевое состояние триггер 31 управления, Устройство работает следующим образом.

Координаты концевых точек о". резка

М (Х„, J„) и Hg(Xq, 4y) поступают через входы 8, 9, 12 и 13 в блоки поворота вектбра 1 и 3 соответственно, а координаты точки о(ХО 1о) поступают через группы входов 10 и 11 в блок 2 поворота вектора. В блоках 1, 2 и 3 поворота вектора производится итерационный процесс одновременного поворота векторов

ОМ,, О М < и О М < на угол Ч, определяемый равенством проекции точек М„и М на одну из осей системы координат (например, на ось ОХ), по алгоритму Волде РВ.

Последняя итерация характеризуется минимальным значением ";сО, при достижении которого блок 4 управления вырабатывает сигнал прерывания процесса поворота векторов. При этом взаимное расположение проекций всех трех точек

М, М0, М ) на ось ОУ определяется одним из шести возможных неравенств.

« „,УО,,1;,р „; З,, ч,1. Эти неравенства анализируются в блоке 4 управления. Если имеет место одно из неравенств первой пары (,,, э2 ), то

9 924714 1О возможности. Кроме этого, предлагаемое устройство характеризуется повышенным быстродействием, позволяет не менее чем в два раза сократить время вычисления расстояний по сравнению с вычислением по известным формулам. Действительно, для случая параллельно-параллельной структуры вычислителя и организации однотактного многоразрядного сдвига информации в регистрах основное время . 10 падает на операцию корректировки полученного расстояния на величину коэффициента деформации К„р Е() . Однако введением некоторых дополнительных итерационных шагов коэффициент деформации можно приблизить к двум, что дает возможность операцию деления вычисленного значения tl на К, заменить операцией сдвига на один разряд в сторону младших разрядов. В результате максимальное время вычисления расстояния между точкой и отрезками и между двумя точками определяется соответственно зависимостями Г = Цп ЦТ;

1 с =(niq)T.

Г

В то же время для вычисления расстояния от точки до отрезка по известной зависимости х,+83 +C о

Гл Р с помощью вычислителя, содержащего умножители, делитель и устройство для извлечения квадратного корня необходимо затратить время „=4п7, а для

I вычисления расстояния между двумя точ-! ками i - 3 и Т

Следовательно, предлагаемое устройство позволяет повысить время вычисления расстояния не .менее, чем в два раза. При этом структура изобретения более проста и регулярна, чем структура устройства для непосредственного вычисления расстояний по известным формулам.

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

45 две группы элементов И, вычитатель, . блок управления, содержащий вычитатель аргумента, счетчик, два триггера, пять элементов И, два коммутатора, два компаратора, три элемента ИЛИ и элемент

НЕ, причем первый и второй управляющие входы коммутаторов соединены с выходами первого и второго триггеров соответственно и входами первого элемента ИЛИ, выход которого соединен с первым входом первого элемента И, второй вход которого является входом тактовых импульсов, преобразователя, выход первого элемента И соединен с входом счетчика, выходы разрядов которого через второй элемент И соединены с управляющим входом первого и второго компараторов, первым входом второго триггера и первым входом третьего элемента И, второй вход которого соединен с выходом переполнения счетчика; выход третьего элемента И соединен с первым входом первого триггера и первым входом второго элемента ИЛИ, второй вход которого соединен с выходом третьего элемента ИЛИ, входы которого соединены с выходами четвертого и пятого элементов И, входы четвертого элемента И соединены с первыми выходами компараторов, входы пятого элемента И соединены с вторыми выходами компараторов, выход третьего элемента ИЛИ через элемент HE соединен с вторым входом первого триггера, установочный вход которого соединен с входом пуска преобразователя и установочным входом второго триггера, выходы коммутаторов соединены с входами вычитателя аргументов, причем информационные входы второго и третьего блоков поворота вектора являются соответственно второй и третьей группами входов преобразователя, первая и вторая группы выходов первого блока поворота вектора соединены с входами первого коммутатора, первая и вторая группы выходов третьего блока поворота вектора соединены с первыми входами первого. компаратора и второго коммутатора, вторые входы которых соединены с второй группой выходов второго блока поворота вектора и первыми входами второго компаратора, вторые входы которого соединены с второй группой вьходов первого блока поворота вектора, выход первого триггера является выходом преобразователя, выходы первого элемента И и вычитателя аргументов со. единены соответственно с первыми и вторыми управля1ощими входами блоков поворота вектора, выход втопого элемента

11 9247

ИЛИ соединен с управляющими входами элементов И первой и второй групп, вторые входы элементов И которых соединены соответственно с вторыми выходажи второго и третьего блоков поворота вектора, выходы элементов И первой и второй групп соединены с первыми и вто- рыми входами вычитателя, выход которого является выходом преобразователя.

2. Преобразователь по п.l, о т л и - 10 ч а ю шийся тем, что каждый блок поворота вектора содержит два коммутатора, два регистра сдвига и два сумматора-вычитателя, причем первые входы коммутаторов являются информационными 1 входами блока поворота вектора, первый и второй управляющие входы которого соединены соответственно с управляющими входами регистров сдвига и входами

14 12 управления режимом cymarropos-вычитателей, выходы которых являются первой и второй группами выходов блоков. поворота вектора и соединены с вторыми входами соответствующих коммутаторов, выходы которых соединены с входами соответствующих регистров сдвига и первыми входами соответствукщих сумматоров-вычитателей, вторые входы которых соединены с выходами разноименньм регистров сдвига.

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР № 453697, кл. 4 06 F 15/32, 1977.

2. Авторское свидетельство СССР № 445042, кл. G 06F 7/38, 1973 (прототип) .

924714

Составитель А. Зорин

Редактор В. Пилипенко Техред И.Гайду Корректор М. Немчик

Заказ 5542 Тираж 732 Подписное

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

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

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4