376973

оофтеттт ,."-:х, ,я СПИИЗОБРЕТЕНИЯ Союз Советских Социалистических РеспубликК ПАТЕЯТУ ависимый от патентаЗаявлено 28.1 Ч.1967 ( 1151919,18-24. Кл. б 061 с 9/О риоритет 28.1 Ч.1966 ч"о 59440, Франци очнтет по лел обрегеккй и открытки бликовано 05.1 Ч.1973. Бюллетень1 УДК 681.3: 16(088 н Совете йнкнстров СССРага опубликования писания 27.И 1.1 Авторизобретения Иностранец Жак Сован(Франция) Иностранная ф Сосьете Насиональ дЭтюд Э де КонстрЗаявител ма ксь Мотор дАвиасьон ПОИСКОВОЕ УСТРОЙСТВО ДЛЯ ВЫДЕЛЕНИЯ ИЗ ДВУЗАДАННЫХ ГРУПП ВЕКТОРОВ И ТОЧЕК АНАЛОГИЧНЬ ДРУГ ДРУГУ ПОДГРУПП Известны поисковые устройства для выделения из двух заданных групп векторов и точек аналогичных друг другу подгрупп, содержащие программный блок с подключенными к нему блоком управления и индикатором.Предложенное устройство отличается тем, что содержит квалратцую матрицу логически.; схем для моделирования решетки систем отсчета сравниваемых групп векторов,и точек, управляющие входы которых соединены с выходами блока управления и индикатора; тем, что в нем каждая из логических схем содержит по одному элементу для моделирования узла решетки и по четыре однонаправленных элемента-вектора, входы которых соединены с выходами элемента для моделирования узла решетки той же логической схемы, а выходы подключены ко входам элементов для моделирования узлов рсшетки соответствующих логических схем матрицы; тем, что в цем каждый элемент для моделирования узлов решетки содержит по шестцалцать лвухвхоловых схем И, сгруппированных в четыре линейки по четыре схемы И в каждой, причем первые входы схем И каждой линейки соединены с соответствующими рабочими входами элемента, вторые входы соответствующих схем И всех линеек подключены к четырем управляющим входам элемента, а выходы схем И каждой линейки соединены с выходами схем И соседних линеек со смеще нием на одну схему и подключены к соответствующим выходам элемента; тем, что в ием каждый элемент-вектор содержит последовательно включенные первый триггер, схему И и второй триггер, установочный вход пер вого триггера соединен со входом элементавектора, вход сброса иа нуль первого триггера, управляющий вход схемы И и входы второго триггера подключены к управляющим входам элемента-вектора, а выход второго 15 триггера соединен с выходом элемецта-вектора.Это позволило упростить устройство и процесс поиска.На фиг, 1 схематически изображена систе ма отсчета, образованная в двухмерном пространстве в виде квадратной решетки; на фиг. 2 - последовательпость векторов, изоморфных конкретной структуре; иа фиг. 3 - логическая схема, с помощью которой можно 25 создать систему отсчета, представленную нафиг. 1.На фиг. 4 показана схема элемента, соот 376973ветствующего узлу решетки; на фиг. 5 - схема элемента, соответствующего вектору решетки; на фиг. 6 изображена функциональная схема устройства; на фиг. 7 - логическая схема части устройства, представленного на фиг. 6; на фиг, 8 и 9 изображены две группы А и В векторов, между которыми ищется соответствие; на фиг. 10 - диаграмма сигналов, управляющих последовательными описаниями траекторий, определяемых последовательностью векторов группы В.На фиг. 11 иллюстрируется представление скопления (населения) А точек группой векторов; на фит. 12 - представление скопления (населения) В точек группой векторов.На фиг. 13 показан вариант реализации группы В.Рассмотрим вначале принцип работы устройства.Система отсчета (фиг. 1) имеет форму правильного квадрата, определенного узлами 1 и парами векторов 2, соединяющих узлы 1. Каждый вектор 2 определяет направление, в котором нужно идти от одного узла 1 к соседнему узлу 1. Так, вектор 2 а направлен от узла 1 а к узлу 1 в, в то время как вектор 2 в направлен от узла 1 в к узлу 1 а,Принято, что все векторы любой из возможных последовательностей, например группы векторов 3 - :12 (фиг, 2), имеют одинаковый модуль и одно из четырех направлений ориентации, соответствующих четырем возможным направлениям ориентации векторов 2 решетки (фиг. 1) и образуют последовательность, определяющую непрерывную траекторию, идущую от начала вектора 3 до конца вектора 12. От вектора 3 к вектору 4 и от вектора 4 к вектору 5 переходят без изменения ориентации. Затем от вектора 5 к вектору б ориентацию изменяют на 90 и т. д.В конце счета последовательность изменений ориентаций следующая:0 - 0 - 90 - 0 - 180 - 90 - 0 - 270 - 2 О.Логическая схема (фиг. 3), с помощью которой можно реализовать решетку (матрицу), представленную на фиг. 1, образована элементами 13 - :17, соответствующими узлам 1, а также элементами 18 - :25, соответствующими векторам 2. Из каждого элемента 13 исходят в четырех направлениях ориентации через пары элементов 18 - :25. Причем каждая пара элементов представляет собой два вОзможных направления для соединения соседних узлов 1 (фиг. 1). Каждому началу или концу элементарных векторов 2 соответствует в каждом из элементов 13 - :17 (фиг. 3) выход 5 или вход Е.Если в качестве исходной оси взять, например, ось положительных абсцисс, то у элемента 21, соответствующего вектору, параллельному этой исходной оси, и имеющего то же самое направление, конец соединится со входом Е элемента 13, а его начало - с выходом 5, элемента 15. Элемент 24, соответствующий вектору, эквиполюсному (имеющему 5 10 15 20 25 30 35 40 45 50 55 60 65 одинаковое направление) вектору, которому соответствует элемент 21, имеет начало, соединенное с выходом 5 элемента 13, и конец, соединенный со входом Е, элемента 17. Элемент 18, соответствующий вектору, находящемуся под углом 90 по отношению к вектору, которому соответствует элемент 24, соединен началом с выходом 5 ы элемента 13, и концом - со входом Ед элемента 14, и т. д.Схема каждого элемента, соответствующего узлам решетки, в данном случае образована 16-ю логическими двухвходовыми схемами И 26, сгруппированными в четыре линейки по четыре схемы И - 26 в каждой.По одному из входов схем И 26 первой линейки соединены со входом Е, соответствующие входы схем И 26 других линеек соединены со входами Егю, Евю и Е гяВторые входы схем И 26 соединены вертикальными рядами с общими зажимами С, Соо, Си и Сгя. Эти зажимы предназначены для соединения с блоком управления.Выходы И 2 бь 26 26 и 264 соединяются с зажимом 5 выходы логических схем И 2 бг, 26, 26, и 26 - с зажимом 5,с, выходы схем И 2 бз, 2 бь 29 г и 2 бы - с зажимом 5 вс, а выходы схем И 264, 2 бг, 2 бы и 26 - с зажимом 5 г 7 д.Каждый элемент, соответствующий вектору решетки (фиг. 5), представлен цепью, имеющий вход Е, соответствующий началу вектора, и выход 5, соответствующий концу этого вектора. Вход Е соединен с выходом 5 через два триггера 27 и 28 с двумя устойчивыми состояниями, разделенных логической схемой И 29. Триггер 27 имеет вход для сброса на нуль, Второй вход схемы И 29 соединен с источником управляющих сигналов. Триггер 28 имеет два управляющих входа (установочный вход и вход для сброса на нуль, кото. рый может выполнять также функцию запрещающего входа).Функциональная схема устройства (фиг. 6) включает квадратную матрицу логических схем 30, из которых каждая образована элементом 13, соответствующим узлу решетки (фиг. 3) и четырьмя элементами 18, 20, 22 и 24, соответствующими векторам, исходящим из этого узла. Таким образом, для каждой логической схемы 30 (фиг. 6) зажимы 5 о, 5 го, 5 в и 5 гго представляют выходы четырех элементов, соответствующих векторам, исходящим из элементарного узла решетки, а входы Ео, Его, Евс и Его являются входами этих элементов. Логические схемы 30 включают в себя также рабочие зажимы (обозначены стрелками) и запрещающие зажимы триггеров 28 (фиг. 5) элементов, соответствующих векторам решетки. Схемы 30 соединены с блоком управления 31, который выдает импульсы на триггеры 27 и 28, на схемы И 29 и 26.С блоком управления 31 (фиг, 6) соединены входы и выходы программного блока 32, к которому подключен индикатор 33, соедиценный выходом с запрещающими входами логических схем 30.Логическая схема части устройства (фиг, 7) включает в себя элемент 13, соответствующий узлу решетки, и один из элементов, например 24 (фиг. 3), соответствующий вектору, исходящему из этого узла, а также часть индикатора 33 (фиг. 6), соответствующую этому элементу, и блок управления 31,Часть индикатора 33, показанная на схеме (фиг, 7), состоит из запоминающего элемента 34, вход которого соединен с выходом логической схемы ИЛИ 35, подключенной входами к выходам логических схем И 36 и 37. Входы схемы И 36 соединены с входными зажимами индикатора 33, два входа схемы И 37 соединены соответственно с выходом триггера 28 и с одним из входных зажимов индикатора 33. Выход запоминающего элемента 34 соединен со входом триггера 28 через ицвертор 38, схему И 39 и схему ИЛИ 40. Второй вход схемы И 39 соединен через второй ицвертор 41 с зажимом индикатора 33, подключенным к выходу программного блока 32 (фиг. 6). Второй вход схемы ИЛИ 40 соединен с зажимом для возврата в нулевое положение триггера 28 (фиг. 7). Запоминающий элемент 34 имеет зажим 42 для подачи импульса сброса на нул ь.С тремя другими элементами, соотнстству. ющими векторам решетки, выходы которых обозначены через 5 о, 5 оо и 5 во, соединены аналогично идентичные элементы 33, При этом каждый триггер 28 указанных элементов может управляться запоминающим элементом 34.Выходы 5 о, Яоо, 5 во и 52-,о элементов, соответствующих векторам решетки, соединены со входами логической схемы ИЛИ 43, выход Которой соединен с рабочим зажимом индикатора 33. Блок управления 31 включает в себя четыре моностабильных мультивибратора 44, 444, включенные последовательно. Вход мультивибратора 44, соединен с выходом программного блока 32 через логическую схему И 45, а выход - со входом программного блока 32, со входом мультивибратора 44, и со входами четырех логических схем И 46 - :49. Вторые входы схем И 46 - :49 соединены с выходами программного блока 32, а выходы этих схем соединены соответственно со входами Со, Соо, Сво и Сио элемента 13, соответствующего узлу решетки.Выход мультивибратора 44, соединен со входом мультивибратора 44 в и со входами для сброса на нуль триггеров 28.Выход мультивибратора 44, соединен со входом мультивибратора 444 и с управляющим входом схемы И 29.Выход мультивибратора 444 соединен со входом сброса на нуль триггеров 27 и со входом логической схемы ИЛИ 50, второй 20 25 30 35 40 45 50 55 60 65 вход которой соединен с зажимом 51 для пуска устройства, который соединен также с запоминающими входами триггеров 28.Работа устройства может соответствовать случаям, когда сравниваемые структуры воспроизводятся точками или векторами.1. Случай с группами векторов;Ищется соответствие между группой векторов А (фиг, 8) и группой векторов В (фиг. 9), которая менее сложна.Поиск ведется в два этапа. На начальном этапе процесса поиска убеждаются в том, что существует соответствие между этими двумя группами А и В. При необходимости на втором этапе отмечают совпадения между этими двумя группами. А,Первый этапа) предварительные операции;Первый этап начинается двумя предварительными независимыми операциями; операцией вписывания в решетку с помощью индикатора 33 (фиг. 6) последовательности векторов группы Аи затем операцией записи группы В в программном блоке 32.Вписывание в решетку группы А осуществляется запрещением всех элементов 18 - :25 (фиг. 3),решетки, которые не соответствуют векторам группы А. С этой целью индикатор 33 (фиг. 7) постоянно выдает сигнал запрета ца входы триггеров 28 элементов, соответствуюших векторам решетки, которые це соответствуют векторам группы А, Этот сигнал запрета подается через запоминающий элемент 34 схемы И 36 и ИЛИ 35. Группа векторов А может быть вписана в ицдика. тор 33 двумя способами,Первый способ состоит в одновременном введении в индикатор 33 данных о группе векторов А: в этом случае индикатор 33 является просто промежуточным звеном, которое переводит все данные, подаваемые,на него в виде соответствующего сигнала. Например, если группа векторов А описывается перфокартой, то индикатор 33 может быть составлен из мозаики фотоэлементов, каждый из которых срабатывает при прохождении через перфорацию, т. е. при наличии вектора,Второй способ состоит в запоминании в индикаторе 33 данных индикации, которые ца него подаются последовательно для представления группы векторов А, чтобы параллельно подать все запреты, как и в предыдущем случае.Для удобства изложения в дальнейшем под последовательностью элементов-векторов А будут пониматься все незапрещенные элементы 18 - :25 (фиг. 3)соответствующие группе векторов А.Запись группы векторов В осуществляется с помощью программного блока 32 (фиг, 6), который управляет работой блока управления 31 так, чтобы можно было бы фиксировать моменты последовательного изменения ориентации, 376973в) Поиск:Как только две предварительныс операции будут выполнены, начинается процесс поиска, Он состоит в том, что одновременно из начала всех элементарных векторов А, а затем в ритме и в соответствии с индикацией сигналов, подаваемых с блока управления 31, производится постепенная разметка (показ) сигналов на элементах-векторах 18 в : 25 и т. д,С этой целью после пуска в ход поискового устройства (фиг. 7) через зажим 51 блока управления 31 переключают триггеры 28 элементов-векторов А (сигнал МЕМ на фиг. 10) ч, таким образом, периодически выдают последовательные серии из четырех сигналов Тг (фиг. 10).Первый сигнал Т, (фиг. 10), указывающий изменение ориентации при переходе от одного вектора группы В к следующему вектору, выдается мультивибратором 44, (фиг. 7) и подается одновременно на один из двух входов каждой из четырех схем И 46 - 49 (фиг. 7) и на программный блок 32, который отбирает одну из схем И 46 - 49, соответствующую производимому изменению ориентации. Выходной сигнал с этой срабатывающей схемы И подается ца соответствующий вход (Со, Соо, С 1 во или Сгго) всех элементов 13 (фиг. 3), соответствующих уАлам решетки.Второй сигнал ЯАЛ (фиг, 1 О), выдаваемый блоком управления 31 (фиг. 7), подается через мультивибратор 44 г на входы сброса на нуль триггеров 28 всех элементов-векторов.Третий сигнал Т, (фиг, 10) подается мультивибратором 44 о а входы схем И 29 всех элементов-векторов.И, наконец, четвертый сигнал ЯА 7 (фиг. 10) выдается мультивибратором 444 (фиг. 7) и подается, с одной стороны, на входы сброса ца нуль триггеров 27 и, с другой стороны, через схему ИЛИ 50 в логическую схему И 45, которая управляет новой последовательностью из четырех сигналов.В рассмотренном примере (фиг. 8 и 9) поиск соответствия между группами векторов А и В осуществляется следующим образом: вектор 56 группы В, который означает первый шаг поиска, списывается сигналом МЕМ (фиг. 10), который запоминает все состояния триггеров 28 (фиг, 7) элементов векторов А. В этом случае находят концы каждого из векторов 52 - :55 (фиг. 8). Эти концы векторов соответствуют входам (Ео или Еоо или Е 1 оо или Ег 7 о) элементов, соответствующих узлам решетки (фиг. 4) . Теперь осуществляется первый цикл: первый сигнал Тг (фиг. 10) этого цикла управляетизменением ориентации, соответствующим переходу от вектора 56 к вектору 57 группы В, т. е, управляет изменением ориентации на 90 с помощью импульса, подаваемого на вход С вертикального ,ряда схем 2 бг, 26;, 2 би 264 (фиг. 4) и изменяет состояния триггеров 27 элементов, соответствующих векторам решетки (фиг. 5). Сигнал Т 1 (фиг, 10) запоминает состояния 5 10 15 20 25 30 35 40 45 50 55 60 б 5 триггеров 28 (фиг. 7) элементов-векторов группы Л, которые можно описать по каждому концу векторов 52 - :55 после осуществления поворота на 90. Наконец, четвертый сигнал ЯАЛ (фиг, 10) возвращает в нулевое положение все триггеры 27 (фиг. 7). Таким образом, с конца вектора 52 (фиг. 8) после изменения ориентации ца 90" сигнал переходит в элемент-вектор 53, который принадлежит к группе Л. Элемент-вектор, соответствующий вектору 53, запоминается. Запоминание предыдущего элемента-вектора стирается, поскольку оцо не сохраняется сигналом, поступающим от предшествующего элемента-век-ора А, Во время того же самого цикла из четырех сигналов с конца элемента-вектора 53 осугцсствляется поиск под углом 90 элемента-вектора, который цс принадлежит к группе А и триггер 28 (фиг. 7) которого остается, следовательно, запрещенным (т, е. имеет место запрет действия импульса), С конца элемента-вектора 54 опять в течение того же самого цикла сигналов, под углом 90 встречают элемент-вектор 55, принадлежащий к группе А, и который затем запоминается. Запоминание предшествующего элемента-вектора 54 стирается, как и в предыдущем случае для элемента-вектора 53.После описания таким образом всей группы векторов В за последней последовательностью сигналов, выдаваемой блоком управления 31 (фиг, б), подается сигнал окончания поиска, поступающий с программного блока 32, который запирает схему И 45 блока управления 31 (фиг. 7).В конце поиска в рабочих состояниях остаются только триггеры 28 элемецтов-векторов, соответствующих вектора м 53 и 55 (фиг. 8). Это указывает на то, чтс группа векторов В была описана два раза в группе векторов Л; запоминаемые элементы-векторы, соответствующие векторам 53 и 55 (фиг 8), изображают последний вектор 57 группы векторов В (фиг, 9).В. Второй этап: индикацияСигнал окончания поиска, выдаваемый программным устройством 32 (фиг. 7), используется для пуска второго периода действия поискового устройства, а именно, этапа индикации или фиксации совпадений. Во время второго периода осуществляется поиск в обратном направлении из исходных точек, образованых двумя точками (концы векто. ров 53 и 55 на фиг. 8) окончания поиска, который был только что описан,Во время операции поиска с индикацией в обратном направлении, последовательность изменений ориентации, управляемых программным устройством 32, берется из последовательности, запрограммированной во время поиска. Это обеспечивается изменением порядка последовательности команд изменений ориентации ца обратный, и изменением этих изменений таким образом, чтобы можно было внести новые результаты на основе предыдущих, принимая во внимание дополнительный увеличенный угол в 180.Таким образом, во время второго периода при каждом шаге получают координаты точек совпадения между группами векторов А и В с помогцью декодирующей матрицы, состоящей из ряда схем ИЛИ 48 (фиг. 7),С - Случай сложных групп:Обычно с более сложными группами векторов А и В, чем те, которые представлены на фиг. 8 и 9, поступают так:а) если цет никакого элемента-вектора, запоминаемого в группе векторов А, записанной в решетке, то группа векторов В не является подгруппой группы векторов А;в) если есть запоминаемый элемент-вектор, то тогда группа векторов В существует один раз в группе векторов А и этот элемент-вектор соответствует последнему вектору группы векторов В;с) если остается несколько запоминаемых элементов-векторов, то группа векторов В существует несколько раз в группе А, и где элементы-векторы соответствуют каждый последнему вектору группы векторов В,Д. Случай прерывных групп (обобщение) .Группы векторов А и В рассматривались до сих пор как непрерывная последовательность векторов. В действительности, эти условия це являются необходимыми; в противном случае достаточно в определенное время отсчета снять запрет с элемецтов-векторов исходной решетки для того, чтобы пропустить сигналы, представляющие фиктивные векторы, добавляемые к группе векторов В,11 - Случай с группами точек:Когда группы А и В не составлены из скопления или населения векторов, а состоят из населения точек, задача сводится к предыдущему случаю следующим образом: пусть (фиг, 11) имеется население А точек (58 - б 4), Это население точек преобразуется в группу векторов посредством разметки в исходнойрешетке всех элементов-векторов, у которых начало соответствует точке этого населения точек,Так же население В (фиг. 12) менее сложное, чем население А, преобразуется в груп: пу последовательных векторов таким образом, чтобы все точки (бб - б 8) этого населения были началами векторов группы. На фиг. 13 показан другой способ реализации непрерывной последовательности векторов,Для проверки существования последней точки группы В предусматривается дополнительный вектор. Его выбирают препочтительно ориентированным под углом 180 по отношению к последнему вектору для того, чтобы не рисковать выйти из пределов исходной решетки, и у него начало является точкой, за 10 15 гичных друг другу, подгрупп, содержащее 20 25 30 линейки соединены., е выходами схем И соседних линеек со смещением ца одну схему и подключены к соответствующим выходам элемента. 50 55 60 ходом элемента-вектора. 35 40 канчивающей последовательность векторов, которую строят. Эта группа В описывается так же, как и в,предыдущем случае, посредством снятия с помощью сигнала, поступающего с программного блока 32 (фиг, б), запрета с элементов-векторов исходной решетки во время циклов сигналов, соответствующих мнимым векторам группы В,Предмет изобретения 1. Поисковое устройство для выделения издвух заданных групп векторов и точек ацалопрограммный блок с подключенными к нему блоком управления и индикатором, отличаюигееся тем, что, с целью упрощения и ускорения процесса поиска, оцо содержит квадратную матрицу логических схем для моделирования решетки систем отсчета сравниваемых групп векторов и точек, управляющие входы которых соединены с выходами блока управления и индикатора.2, Устройство по п. 1, отличггюгцееся тем, что в нем каждая логическая схема содержит по одному элементу для моделирования узла решетки и по четыре однонаправленных элемента-вектора, входы которых соединены с выходами элемента для моделирования узла решетки той же логической схемы, а выходы подключены ко входам элементов для моделирования узлов решетки, соответствующих соседних логических схем матрицы. 3., Устройство по пп. 1 и 2, от.гичиющееся тем, что в нем каждый элемент для моделирования узлов решетки содержит по шестнадцать двухвходовых схем И, сгруппированных в четыре линейки по четыре схемы И в каждой; причем первые входы схем И каждой линейки соединены с соответствующими рабочими входами элемента, вторые входы соответствующих схем И всех линеек подключены к четырем управляющим входам элемента, а выходы схем И каждой 4. Устройство по пп. 1, 2, 3, отличаюш,ееся тем, что в нем каждый элемент-вектор содержит последовательно включенные первый триггер, схему И и второй триггер: установочный вход первого триггера соединен со входом элемента вектора, вход сброса на нуль первого триггера, управляющий вход схемы И и входы второго триггера подключены к управляющим входам элемента-вектора, а выход второго триггера соединен с выРедактор Л. Утехина Корректор А. Степанова Типография, пр, Сапунова, 2 Заказ 2040/5 ,Изд525 Тираж 647 ПодписноеЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССРМосква, Ж, Раушская наб., д. 4/5