Функциональный преобразователь Советский патент 1982 года по МПК G06F17/10 

(54) ФУНКЦИОНАЛЬНЫЙ ПРЕОБРАЗОВАТЕЛЬ

1

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

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

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

.с

V.eгде XQ , Ъо - коодинаты точки; А, В и С - коэффициенты уравнения отрезка Ax + 0.

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

20 выходом устройства и с входом первого сдвигающего регистра, выход третьего сумматора-вйчитателя соединен с третьим выходом устройства и входом третьего сдаигающего регистра, старший разряд KOTopoio соединен с первым входо третьего сумматора-вычитатепя, а второй вход, третьего сумматора-вычитателя соединен с первой группой входов устройства, вторые грутшы входов первого и второго коммутирующих блоков соединены соответственно с второй группой входов устройства Г2 . Однако в известном устройстве отсутствует возможность вычисления расстояния от точки до отрезка прямой на плоскости. Цель изобретения - расширение фу1:Ж циональных возможностей за счет дополнительного вычислениЯ расстояния от точ ки до отрезка пр$;мой на плоскости. Поставленная цель достигается тем, что функциональный преобразователь, содержащий первый блок поворота вектора, информационные входы которого являются первой группой входов преобразователя дополнительно введены второй и тре тий блоки поворота вектора, две группы элементов И, вычитатель, блок управления, содержащий вычитатель аргумента, счетчик, два триггера, пять элементов И, два коммутатора, два компаратора, три элемента ИЛИ и элемент НЕ, причем первый и второй управляющие входы коммутаторов соединены с выходами первого, иВторого триггеров соответственно и входами первого элемента ИЛИ., вькод которого соединен с первым входом перв го элемента И, второй вход которого является входом тактовых импульсов преоб разователя, выход первого элемента И соединен с входом счетчика, выходы разрядов которого через второй элемент И соединены с управляющим входом первого и второго компараторов, первым входом второго триггера, и перзым входом третьего элемента И, второй вход которого соединен с выходом переполнения счетчика, выход третьего элемента И соединен с первым входом первого триггера и первым входом второго элемента ИЛИ, второй вход которого соединен с выходом третьего элемеггга ИЛИ, входы которо,го соединены с выходами четвертого и пятого элементов И, входы четвертого элемента И соединены с первыми вькодами jcoMnapaTopoB, входы пято-, го элемента И ;оединены со вторыми выходами компараторов, выход третьего элемента ИЛИ через элемент НЕ соединен с вторым входом первого триггера установочный вход которого соединен с Входом пуска перофазователя и установо ным входом ВТОРОГО триггера, выходы коммутаторов соединены с входами вычитателя аргументов, причем информационные входы второго и третье.го блоков поворота вектора являются соответственно второй и третьей группами входов преобразователя, первая и вторая группы вьпсодов первого блока поворота вектора соединены с входами первого KOMNiyTaroра, первая и вторая группы выходов третьего блока поворота вектора соединейы с первыми входами первого компаратора и второго коммутатора, вторые входы которых соединены с второй ггуп пой выходов второго блока поворота вектора и первыми входами второго компаратора, вторые входы которого соединены с второй.группой выходов первого блока поворота вектора, вь1ход первого триггера является выходом преобразователя, выходы первого элемента И и вычитателя аргументов соединены соответственно с первыми и вторыми управляющими входами блоков поворота вектора, выход второго элемента ИЛИ соединен с управляющими входами элементов И первой и второй групп, вторые входы элементов И которых соединены соответственно с вторыми выходами второго и третьего блоков поволрота векторов, выходы элементов И первой и второй групп соединены с первыми и вторыми входами вычитателя, выход которого является выходом преобразсйвателя. Каждый блок поворота вектора содержит два регистра сдвига и два сумматора вычитателя, причем первые входы коммутаторов являются информационными входами блока поворота вектора, первый и второй управляющие входы которого соединены соответственно с управляющими входами регистров сдвига и входами управления режимом сумматоров-вычитателей, вькоды которых являются первой и второй группами выходов блока поворота вектора и соединены с вторыми входами соответствующих комк утаторов, . выходы которых соединены с входами соответствующих регистров сдвига и первыми входами соответствующих сумматоров-вычитателей, вторые входы .которых соединены с выходами разноименных регистров сдвига. На фиг. 1 представлена бпок-схема преобразователя; на фиг, 2 и 3 - блоксхемы блока поворота вектора и блока управления , соответственно. Функциональный преобразователь содержит блоки 1, 2 и 3 поворота вектора, блок 4 управления, группы 5 и 6 элементов И, вычислитель 7, входы преобразователя 8-13, выходы преобразователя 14 и 15. Кецкдый блок поворота вектора содержит регистры 16 и 17 сдвига, коммута торы 18 и 19, сумматоры-вычигатели 2О и 21, управляющие входы 22 и 23. Блок 4 упр 1вления содержит вычитатель 24 аргументов, коммутаторам 25 и 26, компараторы 27 и 28, счетчик 29, триггеры ЗО и 31, элементы И 32-36, элементы ИЛИ 37 -39, элемен НЕ 40, входы 41-47, выходы 48-51. Блок поворота вектора работает еледующим образом. ..В исходном состоянии координаты Х. - i Q точки выходов блока поворот Beieropa соответственно заносятся через коммутаторы 18 и. 19 в сдвиговые регистры 16 и 17 и сумматоры-вьгчитатели 2О и 21. Затем информация в регист рах 16 и 17 сдвигается в сторону млад ших разрядов по тактовым импульсам, поступающим по управляющему входу прерьюання поворота векторов 22 из бло ка 4 управления. При этом схема сдвига содержимого регистров 1 и 2 обеспечивает организад1К5р однотактного многораэ ряднопо сдвига в соответсгвии с номеро иге рационного шага ( i 1, 2, 3,...,п ) для образования очередных приращений ..г-(я координат точек X N .-«I Сдвинутая информация W.1 ИЗ регистров 16 и 17 поступает соответственно на сумматоры-вьгчитатели 21 и 2О, где производится ее суммирование или вычитание с предыдущим результатом. 3 1аком сумматоров-вычитателей управляет блок 4 управления по входу 23 управления. Результаты с сумматоров вычитателей 20 и 21 поступают яа выхошл блока поворота вектора и через ком мутаторы 18 и 19 заносятся в суммато ры 20 и 21 и сдвиговые регистры 16и 17. Процесс поворота вектора прерывается при отсутствии тактовых импульсов на входы 22. Таким образом, блок поворота реализует алгоритм Волдера , ти г ш.лП, «1, i,. гдеm - фиксировано и равно или О, или 1, или 2. . Vrsiq т. l-.Ti i 0,n--l ffi 4i4i Блок 4 управления вырабатывает следующие сигналы; управление знаками сумматоров-вычктателей блоков поворота векторов 1, 2, 3; прерывание процесса поворота векторов; разрешение прохождения информации с выходов блоков поворота векторов на вычктатель 7; указатель, что вычисляется расстояние от точки до отрезка или до кошювой точки отрезка. Блок управления работает следующим образе. По сигналу TlycK, поступающему на вход 46, триггер ЗО управления устанавливается в единичное состояние, а триггер 31 управления устанавливается в нулевое состояние. При этом коорд1шаты точек MQ , М и (2 заноЬятся в блоки поворота векторов. Триггер ЗО управления разрешает прохождение синхроимпульсов с выхода 45 через элемент 32 на шагов 29 и через выход 49 на вход прерывания процесса поворота векторов блоков поворота векторов. Это приводит к возникнсжению интерашюнного процесса поворота векторов в блоках поворота векторов. Информация Х(их. с выходов соответствующих блоков поворота векторов через входы 41 и 43 и коммутаторы 25 и 26, управпяемью триггером 30, поступает на входы вычитателн 24, на выходе знакового разряда которого формируется сигнал управления Я, знаком сумматоров-вычитателей блоков поворота векторов. После проведения п итерационных шагов на элементе И 33 формируется сигнал, разрешаюций прохождение информации оп. ; , «,, ,n-i через входы 42, 44 и 47 соответственно на компараторы 27 и 28. Этот же сигнал с выхода элемента 33 устанавливает в нулевое состояние триггер ЗО управления. Состояния выходов компараторов 27 й-28: о,,„., ;Уо,, О.и-d an-i .n.a.tl-. анализируются логическими элементами И 35, 36 и логическим элементом ИЛИ 38. Если выполняется условие t.n--il:%n-i 7. . t -ТО на выходе логического элемента. ИЛИ 38 формируется сигнал ра эешающий прохождение информации через логический элемент ИЛИ 39 на .вход вычитатоля функционального преоб пазователя. условие 5f у Л i.0 п-1 1 «--1 - вьшолня€.тся, то на выходе элемента НЕ 40, формируется сигнал, устанавливакщий триггер 31 управления в единичное состояние, сигнал в котором чепез выход 50 передается на выход фушщионального преобразователя, указывающий, что измеряет ся расстояние от точки до концевой точки отрезка. При этом открывается логический элемент И 32 и начинается второй итерационный процесс в блоках поворота векторов. Информация Уд д и -liij П,1п--1 ) с соответс вукщих выходов блоков поворота векторов через входы 42 и 44 и коммутаторы 25 и 26 поступает на входы вычитателя 23, где формируется сигнал управления знаком сумматоров-вычитателей блоков поворота векторов. Второй итерационный процесс заканчивается после того, как в счетчике 29 зафиксирова:но число 2 п итерационных шагов. При этом на выходе логического элемента И 33 формируе ся сигнал, разрешакяций прохождение информации на входы вычитателя функционального преобразователя. Этот же сигнал устанавливает в нулевое состояние триггер 31 управления. Устройство работает следу юци-м образом. Координаты концевых точек m резка W(X,U) и М(1(Х(2,(1) поступают чере входы 8, 9, 12 и 13 в блоки поворота вектора 1 и 3 соответственно, а коорди наты точки AQ(XQ, 0 через группы входов 10 и 11 в блок 2 поворо та вектора. В блоках 1, 2 и 3 поворота вектора производится итерационный процесс одаювреме ного поворота векторов ОМ , ОМд и угол /, определяемый равенством проекции точек fA и на одну из осей системы координат (на пример, на ось ОХ), по алгоритму Волде ра.. , Последняя итерация характеризуется минимальным значением у.-лО, при достижении которого блок 4 управления вырабатывает сигнал прерывания процесса поворота векторов. При этом взаимное расположение лроекций всех трех точек М , на «ось ОУ определяется одним из шести возможных неравенств: (о7д д , - f 7. / . Эти неравенства анализируются в блоке 4 управления. Если имеет место одно из неравенств первой пары (); блок 4 управления вырабатывает сигнал, разрешающий прохождение информации выходов блоков поворота вектора 2 и 3 через группы логических элементов И 5 и б на входы вычитателя 7, где вычисляется расстояние (-Х„.|зт точки Мд до отрезка М М. При всех ост1альных неравенствах блок 4 управления снимает сигнал прерывания процесса поворота векторов, в результате чего в блоках поворота, вектора 1, 2 и 3 начинается второй итерационный цикл, направленный на совмещение проекций точек MQ и М (или MIJ ). При этом оператор поворота с.,- определяется знаком разности j . ( - у .. В качестве начальных условий и ff д берутся те, что получены в конце первого итерационного цикла. Окончание второго итерационного цикла определяется одним из неравенств Xr.iX При этом блок 4 управления вырабатывает сигнал прерывания поворота векторов и сигнал, разре ш-ающий прохождение информации X.Q и XQ i выходов блоков поворота вектора 2 и 3 через группы логических элементов И 5 и 6 на входы вычитателя 7, на выходе 15 которого формируется вели- . чина расстояния 2 . |от точки MO до ближайшей из точек и . При этом на выходе 14 устройства выдается сигнал, указывающий, что вычисляется расстояние от точки MO до концевой точки отрезка М.М. Поскольку в основу работы устройства положен принцип псевдовращения векторов, следует учитывать эффект деформации их, а значит и измеряемого расстояния Z . Это учитывается соответствующим масштабом выходной величины вычитателя 7 введением заранее вычисленных коэффициентов деформации К кг§() Нп ) для первого для второго итерационного цикла. В случае необходимости проведения второго итерационного цикла достаточно ограничиться вращением только двух векторов: ОМд и одного из- векторов. ОМ или ОМ. В отличие от известных устройств, вычисляющих расстояние между точками на Плоскости по известным зависимостям, предлагаемое устройство, кроме указанной операции вычисляет кратчайшее расстояние от точки до отрезка, что сушественно расширяет его функциональные 9 возможности. Кроме этого, предлагаемо устройство характеризуется повышенным быстродействием, позволяет не менее чем в два раза сократить время вычисления расстояний по сравнению с вычиспением по извecтньпv форк-сулам. Действи тельно, для случая параллельно-параллел ной структуры вычислителя и организаци однотактного многоразрядного сдвига ин формации в регистрах основное время падает на операцию корректировки полученного расстояния на величину коэффициенту деформации K(iJ. Однако введением некоторых дополнительных итерационных шагов коэффициент деформадии можно приблизить к двум, что дает возможность операцию деления вычисленного значения li на К заменить операцией сдвига на один разряд в сторону младших разрядов. В результате максимальное время вычисления расстояния между точкой и отрезками и между двумя точками определяется соответственно зависимостями T riVDT; cr.). в то же время для вычисления расстояТО же время известной отрезка по ния от TO4ifH до зависимости + С с помощью вычислителя, содержащего умножители, делитель и устройство для извлечения квадратного корня необходимо затратить время 1 г:4пТ а для вычисления расстояния между двумя точ ками . Следовательно, предлагаемое устройство позволяет повысить время вычисления расстояния не .менее, чем в два раза. При этом структура изобретения бол проста и регулярна, чем структура устройства для непосредственного вычислениярасстояний по известным формулам. Формула изобретения 1. Функциональный преобразователь, содержащий первый блок поворота векто информационные входы которого являютс первой группой входов преобразователя, отличающийся тем, что, с це пью расширения функциональных воа ожностей за счет дополнительного вычисле ния расстояния от точки до отрезка пря мой на плоскости, в него введены вто. рой и третий блоки поворота вектора. 14 две группы элементов И, вычитатель, . блок управления, содержащий вычитатель аргумента, счетчик, два триггера, пять элементов И, два коммутатора, два компаратора, три элемента ИЛИ и элемент НЕ, причем первый и второй управляющие входы коммутаторов соеотпнены с выходами первого и второго триггеров-соответственно и входами первого элемента ИЛИ, выход которого соединен с первым входом первого элемента И, второй вход которого является входом тактовых импульсов, преобразователя, выход первого элемента И соединен с входом счетчика, выходы разрядов которого через второй элемент И соединены с управляющим входом первого и второго компараторов, первым входом второго триггера и первым входом третьего элемента И, второй вход которого соединен с выходом переполнения счетчика, выход третьего элемента И соединен с первым входсял первого триггера и первым входом второго элемента ИЛИ, второй вход которого соединен с выходом третьего элемента ИЛИ, входы которого соединены с выходами четвертого и пятого элементов И, входы четвертого элемента И соединены с первыми выходами компараторов, входы пятого элемента И соединены с вторыми выходами компараторов, выход трютьего элемента ИЛИ через элемент НЕ соединен с вторь1м входом первого трштгера, установочный вход которого соединен с входом пуска преобразователя и установочным входом второго триггера, выходы коммутаторов соединены с входами вьгштателя аргументов, причем информационные входы второго и третьего блоков поворота вектора являются соответственно второй и третьей группами входов преобразователя, первая и вторая группы выходов первого блока поворота вектора соединены с входами первого коммутатора, первая и вторая группы выходов третьего блока поворота вектора соединены с первыми входами первого компаратора и второго коммутатора, вторые входы которых соединены с второй группой выходов второго блока поворота вектора и первыми входами второго компаратора, вторые входы которого соединены с второй группой вь;ходов первого блока поворота вектора, выход первого триггера является выходом преобразователя, выходы первого элемента И и вычитателя аргументов соединены соответственно с первыми и вторыми управляйлцнми входами блоков поворота вектора, выход второго элемента

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

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

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

Источники информации, принятые во внимание при эвспертизе Авторское свидетельство СССР 453697, кл. Q 06F 15/32, 1977.

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