Патент ссср 376973
Патент 376973
Авторы
Классы МПК
Патент ссср 376973
Иллюстрации
Реферат
I аатент, ° . :х .: ° . ° ъэя
СПИ
К3ОБРЕТ ЕНИЯ
Союз Советских
Социалистических
Республик
К ПАТЕНТУ
Зависимый от патента №
Заявлено 28.1Ч.1967 (№ 1151919. 18-24) M. Кл. G 06k 9/00
Приоритет 28.IV.1966, № 59440, Франция
Иомнтет по делам изобретений и открыткб прн Совете тт1нкнстров
Опубликовано 05.1Ч.1973. Бюллетень № 17
УДК 681.3: 16(088.8) Дата опубликования описания 27 Ч11.1973
Автор изобретения
Иностранец
Жак Сован (Франция) Иностранная фирма
«Сосьете Насиональ д Этюд Э де Констрюксьон де Мотор д Авиасьон» (Франция) Заявитель
ПОИСКОВОЕ УСТРОЙСТВО ДЛЯ ВЫДЕЛЕНИЯ ИЗ ДВУХ
ЗАДАННЫХ ГРУПП ВЕКТОРОВ И ТОЧЕК АНАЛОГИЧНЫХ
ДРУГ ДРУГУ ПОДГРУПП
Известны поисковые устройства для выделения из двух заданных групп векторов и точек аналогичных друг другу подгрупп, содержащие программный блок с подключенными к нему блоком управления и индикатором.
Предложенное устройство отличается тем, что содержит квадратную матрицу логически.; схем для моделирования решетки систем отсчета сравниваемых групп векторов,и точек, управляющие входы которых соединены с выходами блока управления и индикатора; тем, что в нем каждая из логических схем содержит по одному элементу для моделирования узла решетки и по четыре однонаправленных элемента-вектора, входы которых соединены с выходами элемента для моделирования узла решетки той же логической схемы, а выходы подключены ко входам элементов для моделирования узлов рсшетки соответствующих логических схем матрицы; тем, что в ием каждый элемент для моделирования узлов решетки содержит по шестнадцать двухвходовых схем «И», сгруппированных в четыре линейки по четыре схемы «И» в каждой, причем первые входы схем «И» каждой линейки соединены с соответствующими рабочими входами элемента, вторые входы соответствующих схем «И» всех линеек подключены к четырем управляющим входам элемента, а выходы схем «И» каждой линейки соединены с выходами схем «И» соседних линеек со смеще5 нием на одну схему и подключены к соответствующим выходам элемента; тем, что в ием каждый элемент-вектор содержит последовательно включенные первый триггер, схему
«И» и второй триггер, установочный вход пер10 вого триггера соединен со входом элемента вектора, вход сброса иа нуль первого триггера, управляющий вход схемы «И» и входы второго триггера подключены к управляющим входам элемента-вектора, а выход второго
15 триггера соединен с выходом элемента-вектораа.
Это позволило упростить устройство и процесс поиска.
На фиг. 1 схематически изображена систе20 ма отсчета, образованная в двухмерном пространстве в виде квадратной решетки; на фиг. 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 — 270 .
Логическая схема (фиг. 3), с помощью которой можно реализовать решетку (матрицу), представленную на фиг. 1, образована элементами 18 —:17, соответствующими узлам 1, а также элементами 18 —:25, соответствующими векторам 2. Из каждого элемента 18 исходят в четырех направлениях ориентации через пары элементов 18 —:25. Причем каждая пара элементов представляет собой два возможных направления для соединения соседних узлов 1 (фиг. 1). Каждому началу или концу элементарных векторов 2 соответствует в каждом из элементов 18 —:17 (фиг. 3) выход S или вход Е.
Если в качестве исходной оси взять, например, ось положительных абсцисс, то у элемента 21, соответствующего вектору, параллельному этой исходной оси, и имеющего то же самое направление, конец соединится со входом Ео элемента 18, а его начало — с выходом Sp элемента 15. Элемент 24, соответствующий вектору, эквиполюсному (имеющему
25 зо
65 одинаковое направление) вектору, которому соответствует элемент 21, имеет начало, соединенное с выходом Sp элемента 18, и конец, соединенный со входом Ео элемента 17. Элемент 18, соответствующий вектору, находящемуся под углом 90 по отношению к вектору, которому соответствует элемент 24, соединен началом с выходом Sgp элемента 18, и концом — со входом Egp элемента 14, и т. д.
Схема каждого элемента, соответствующего узлам решетки, в данном случае образована 16-ю логическими двухвходовыми схемами
«И» 26, сгруппированными в четыре линейки по четыре схемы «И» — 26 в каждой.
По одному из входов схем «И» 26 первой линейки соединены со входом Ео, соответствующие входы схем «И» 26 других линеек соединены со входами Egp, Е оо и Е g,p, Вторые входы схем «И» 26 соединены вертикальными рядами с общими зажимами Со, Соо, С180 и С270. Эти зажимы предназначены для соединения с блоком управления.
Выходы «И» 26„26p, 26» и 26 4 соединяются с зажимом Sp, выходы логических схем
«И» 26, 26, 26 и 26 о — с зажимом Sgp, выходы схем «И» 26g, 2бо, 29о и 26 о — с зажимом Supp, а выходы схем «И» 26, 2бу, 2бц) и
26ig — с зажимом Sgyp.
Каждый элемент, соответствующий вектору решетки (фиг. 5), представлен цепью, имеющий вход Е, соответствующий началу вектора, и выход S, соответствующий концу этого вектора. Вход Е соединен с выходом S через два триггера 27 и 28 с двумя устойчивыми состояниями, разделенных логической схемой
«И» 29. Триггер 27 имеет вход для сброса на нуль. Второй вход схемы «И» 29 соединен с источником управляющих сигналов. Триггер
28 имеет два управляющих входа (установочный вход и вход для сброса на нуль, который может выполнять также функцию запрещающего входа).
Функциональная схема устройства (фиг. 6) включает квадратную матрицу логических схем 30, из которых каждая образована элементом 13, соответствующим узлу решетки (фиг. 3) и четырьмя элементами 18, 20, 22 и
24, соответствующими векторам, исходящим из этого узла. Таким образом, для каждой логической схемы 80 (фиг. 6) зажимы Sg Sgp, S>ap и $ о представляют выходы четырех элементов, соответствующих векторам, исходящим из элементарного узла решетки, а входы Ео, Egp, Eiap и Eïp являются входами этих элементов. Логические схемы 80 включают в себя также рабочие зажимы (обозначены стрелками) и «запрещающие» зажимы триггеров 28 (фиг. 5) элементов, соответствующих векторам решетки. Схемы 30 соединены с блоком управления 31, который выдает импульсы на триггеры 27 и 28, на схемы «И»
29 и 26.
С блоком управления 81 (фиг. 6) соединены входы и выходы программного блока 32, к которому подключен индикатор 88, соеди376973
15 ненный выходом с запрещающими входами логических схем 80.
Логическая схема части устройства (фиг. 7) включает в себя элемент 13, соответствующий узлу решетки, и один из элементов, например
24 (фиг. 3), соответствующий вектору, исходящему из этого узла, а также часть индикатора 88 (фиг. 6), соответствующую этому элементу, и блок управления 81.
Часть индикатора 83, показанная на схеме (фиг. 7), состоит из запоминающего элемента 84, вход которого соединен с выходом логической схемы «ИЛИ» 35, подключенной входами к выходам логических схем «И» 86 и
87. Входы схемы «И» 36 соединены с входными зажимами индикатора 88, два входа схемы «И» 87 соединены соответственно с выходом триггера 28 и с одним из входных зажимов индикатора 83. Выход запоминающего элемента 84 соединен со входом триггера 28 через инвертор 88, схему «И» 89 и схему «ИЛИ» 40. Второй вход схемы «И»
89 соединен через второй инвертор 41 с зажимом индикатора 38, подключенным к выходу программного блока 82 (фиг. 6). Второй вход схемы «ИЛИ» 40 соединен с зажимом для возврата в нулевое положение триггера 28 (фиг. 7) . Запоминающий элемент 34 имеет зажим 42 для подачи импульса сброса на нул ь.
С тремя другими элементами, соответствующими векторам решетки, выходы которых обозначены через So, Яви и Siqp, соединены аналогично идентичные элементы 88, При этом каждый триггер 28 указанных элементов может управляться запоминающим элементом 84.
Выходы 5,, Sq, Siqq и S -,о элементов, соответствующих векторам решетки, соединены со входами логической схемы «ИЛИ» 48, выход которой соединен с рабочим зажимом индикатора 88.
Блок управления 81 включает в себя четыре моностабильных мультивибратора 44l 444, включенные последовательно. Вход мультивибратора 44> соединен с выходом программного блока 82 через логическую схему «И»
45, а выход — со входом программного блока 82, со входом мультивибратора 44> и со входами четырех логических схем «И» 46 —:49.
Вторые входы схем «И» 4б —:49 соединены с выходами программного блока 82, а выходы этих схем соединены соответственно со входами Со, С90, С180 и С270 элемента 18, соответствующего узлу решетки.
Выход мультивибратора 44 соединен со входом мультивибратора 44З и со входами для сброса н а нуль триггеров 28.
Выход мультивибратора 44з соединен со входом мультивибратора 444 и с управляющим входом схемы «И» 29.
Выход мультивибратора 444 соединен со входом сброса на нуль триггеров 27 и со входом логической схемы «ИЛИ» 50, второй
65 вход которой соединен с зажимом 51 для пуска устройства, который соединен также с запоминающими входами триггеров 28.
Работа устройства может соответствовать случаям, когда сравниваемые структуры воспроизводятся точками или векторами.
1. Случай с группами векторов:
Ищется соответствие между группой векторов А (фиг. 8) и группой векторов В (фиг. 9), которая менее сложна.
Поиск ведется в два этапа. На начальном этапе процесса поиска убеждаются в том, что существует соответствие между этими двумя группами А и В. При необходимости на втором этапе отмечают совпадения между этими двумя группами.
А. Первый этап а) предварительные операции:
Первый этап начинается двумя предварительными независимыми операциями; операцией вписывания в решетку с помощью индикатора 33 (фиг. 6) последовательности векторов группы А,,и затем операцией записи группы В в программном блоке 82.
Вписывание в решетку группы А осуществляется «запрещением» всех элементов
18 —:25 (фиг. 3),решетки, которые не соответствуют векторам группы А. С этой целью индикатор 83 (фиг. 7) постоянно выдает сигнал запрета на входы триггеров 28 элементов, соответствуюших векторам решетки, которые не соответствуют векторам группы А. Этот сигнал запрета подается через запоминающий элемент 84 схемы «И» 36 и «ИЛИ» 85. Группа векторов А может быть вписана в индикатор 83 двумя способами.
Первый способ состоит в одновременном введении в индикатор 88 данных о группе векторов А: в этом случае индикатор 33 является просто промежуточным звеном, которое «переводит» все данные, подаваемые,на него в виде соответствующего сигнала. Например, если группа векторов А описывается перфокартой, то индикатор 83 может быть составлен из «мозаики» фотоэлементов, каждый из которых срабатывает при прохождении через перфорацию, т. е. при наличии вектора.
Второй способ состоит в запоминании в индикаторе 88 данных индикации, которые на него подаются последовательно для представления группы векторов А, чтобы параллельно подать все «запреты», как и в предыдущем случае.
Для удобства изложения в дальнейшем под последовательностью элементов-векторов
А будут пониматься все незапрещенные элементы 18=.25 (фиг. 3),,соответствующие группе векторов А.
Запись группы векторов В осуществляется с помощью программного блока 82 (фиг, 6), который управляет работой блока управления
81 так, чтобы можно было бы фиксировать моменты последовательного изменения ориентации, 3769733 в) Поиск:
Как только две предварительныс операции будут выполнены, начинается процесс поиска.
Он состоит в том, что одновременно из начала всех элементарных векторов А, а затем в ритме и в соответствии с индикацией сигналов, подаваемых с блока управления 81, производится постепенная разметка (показ) сигналов на элементах-векторах 18 —:25 и т. д.
С этой целью после пуска в ход поискового устройства (фиг. 7) через зажим 51 блока управления 31 переключают триггеры 28 элементов-векторов А (сигнал МЕМ на фиг. 10) ч, таким образом, периодически выдают последовательные серии из четырех сигналов Т2 (фиг. 10).
Первый сигнал Т2 (фиг. 10), указывающий изменение ориентации при переходе от одного вектора группы В к следующему вектору, выдается мультивибратором 441 (фиг. 7) и подается одновременно на один из двух входов каждой из четырех схем «И» 46 — 49 (фиг. 7) и на программный блок 82, который отбирает одну из схем «И» 46 — 49, соответствующую производимому изменению ориентации. Выходной сигнал с этой срабатывающей схемы «И» подается на соответствующий вход (Со, Сиь С18о или С о) всех элементов 13 (фиг. 3), соответствующих у1лам решетки.
Второй сигнал PAZ (фиг, 10), выдаваемый блоком управления 81 (фиг. 7), подается через мультивибратор 442 на входы сброса на нуль триггеров 28 всех элементов-векторов.
Третий сигнал Т, (фиг. 10) подается мультивибратором 44 на входы схем «И» 29 всех элементов-векторов.
И, наконец, четвертый сигнал RAZ (фиг. 10) выдается мультивибратором 444 (фиг. 7) и подается, с одной стороны, на входы сброса на нуль триггеров 27 и, с другой стороны, через схему «ИЛИ» 50 в логическую схему «И»
45, которая управляет новой последовательностью из четырех сигналов.
В рассмотренном примере (фиг. 8 и 9) поиск соответствия между группами векторов А и В осуществляется следующим образом: вектор 56ггруппы В, который означает первый шаг поиска, списывается сигналом МЕМ (фиг. 10), который запоминает все состояния триггеров
28 (фиг. 7) элементов векторов А. В этом случае находят концы каждого из векторов
52 —:55 (фиг. 8) . Эти концы векторов соответствуют входам (Eo или Еоо или Е180 или Eno) элементов, соответствующих узлам решетки (фиг. 4) . Теперь осуществляется первый цикл: первый сигнал Т2 (фиг. 10) этого цикла управляет изменением ориентации, соответствующим переходу от вектора 56 к вектору 57 группы В, т. е. управляет измене нием ориентации на 90 с помощью импульса, подаваемого на вход С о вертикального .ряда схем 26, 26;, 2б„и 26 4 (фиг. 4) и изменяет состояния триггеров 27 элементов, соответствующих векторам решетки (фиг. 5) .
Сигнал Т1 (фиг. 10) запоминает состояния
60 б5 триггеров 28 (фиг. 7) элементов-векторов группы Л, которые можно описать по каждому концу векторов 52 —:55 после осуществления поворота на 90 . Наконец, четвертый сигнал RAZ (фиг. 10) возвращает в нулевое положение все триггеры 27 (фиг. 7). Таким образом, с конца вектора 52 (фиг. 8) после изменения ориентации на 90" сип.ал переходит в элемент-вектор 58, который принадлежит к группе Л. Элемент-вектор, соответствующий вектору 58, запоминается. Запоминание предыдущего элемента-вектора стирается, поскольку оно не сохраняется сигналом, поступающим от предшествующего элемента-векора А. Во время того же самого цикла из четырех сигналов с конца элемента-вектора
58 осуществляется поиск под углом 90 элемента-вектора, который нс принадлежит к группе А и триггер 28 (фиг. 7) которого остается, следовательно, запрещенным (т. е. имеет место запрет действия импульса). С конца элемента-вектора 54 опять в течение того >ке самого цикла сигналов, под углом 90 встречают элемент-вектор 55, принадлежащий к группе А, и который затем запоминается. Запоминание предшествующего элемента-вектора 54 стирается, как и в предыдущем случае лля элемента-вектора 58.
После описания таким образом всей группы векторов В за последней последовательностью сигналов, выдаваемой блоком управления 81 (фиг. б), подается сигнал окончания поиска, поступающий с программного блока 82, который запирает схему «И» 45 блока управления 81 (фиг. 7).
В конце поиска в рабочих состояниях остаются только триггеры 28 элементов-векторов, соответствующих вектора м 58 и 55 (фиг. 8). Это указывает ня то, чтс группа векторов В была описана два раза в группе векторов Л; запоминаемые элементы-векторы, соответствующие векторам 58 и 55 (фиг 8), изображают последний вектор 57 группы векторов В (фиг. 9).
В. Второй этап: индикация
Сигнал окончания поиска, выдаваемый программным устройством 82 (фиг. 7), используется для пуска второго периода действия поискового устройства, а именно, этапа индикации или фиксации совпадений. Во время второго периода осуществляется поиск в обратном направлении из исходных точек, образованых двумя точками (концы векторов 58 и 55 на фиг. 8) окончания поиска, который был только что описан, Во время операции поиска с индикацией в обратном направлении, последовательность изменений ориентации, управляемых программным устройством 82, берется из последовательности, запрограммированной во время поиска. Это обеспечивается изменением порядка последовательности команд изменений ориентации на обратный, и изменением этих изменений таким образом, чтобы можно было внести новые результаты на основе предыду376973
10 щих, принимая во внимание дополнительный увеличенный угол в 180 .
Таким образом, во время второго периода при каждом шаге получают координаты точек совпадения между группами векторов А и В с помощью декодирующей матрицы, состоящей из ряда схем «ИЛИ» 48 (фиг. 7), С вЂ” Случай сложных групп:
Обычно с более сложными группами векторов А и В, чем те, которые представлены на фиг. 8 и 9, поступают так: а) если нет никакого элемента-вектора, запоминаемого в группе векторов А, записанной в решетке, то группа векторов В не является подгруппой группы векторов А; в) если есть запоминаемый элемент-вектор, то тогда группа векторов В существует один раз в группе векторов А и этот элемент-вектор соответствует последнему вектору группы векторов В; с) если остается несколько запоминаемых элементов-векторов, то группа векторов В существует несколько раз в группе А, и где элементы-векторы соответствуют каждый последнему вектору группы векторов В.
Д. Случай прерывных групп (обобщение).
Группы векторов А и В рассматривались до сих пор как непрерывная последовательность векторов. В действительности, эти условия не являются необходимыми; в противном случае достаточно в определенное время отсчета снять запрет с элементов-векторов исходной решетки для того, чтобы пропустить сигналы, представляющие фиктивные векторы, добавляемые к группе векторов В, II — Случай с группами точек:
Когда группы А и В не составлены из скопления или населения векторов, а состоят из населения точек, задача сводится к предыдущему случаю следующим образом: пусть (фиг. 11) имеется население А точек (58 — б4).
Это население точек преобразуется в группу векторов посредством разметки в исходной решетке всех элементов-векторов, у которых начало соответствует точке этого населения точек.
Так же население В (фиг. 12) менее сложное, чем население А, преобразуется в груп: пу последовательных векторов таким образом, чтобы все точки (б5 — б8) этого населения были началами векторов группы. На фиг. 13 показан другой способ реализации непрерывной последовательности векторов.
Для проверки существования последней точки группы В предусматривается дополнительный вектор. его выбирают препочтительно ориентированным под углом 180 по отношению к последнему вектору для того, чтобы не рисковать выйти из пределов исходной решетки, и у него начало является точкой, за10
15 гичных друг другу . подгрупп, содержащее
25
30 ходом элемента-вектора.
55 канчивающей последовательность векторов, которую строят. Эта группа В описывается так же, как и в,предыдущем случае, посредством снятия с помощью сигнала, поступающего с программного блока 82 (фиг. б), запрета с элементов-векторов исходной решетки во время циклов сигналов, соответствующих мнимым векторам группы В.
Предмет изобретения
1. Поисковое устройство для выделения из двух заданных групп векторов и точек аналопрограммный блок с подключенными к нему блоком управления и индикатором, отличаюигееся тем, что, с целью упрощения и ускорения процесса поиска, оно содержит квадратную матрицу логических схем для моделирования решетки систем отсчета сравниваемых групп векторов и точек, управляющие входы которых соединены с выходами блока управления и индикатора.
2. Устройство по п. 1, отличаюгиееся тем, что в нем каждая логическая схема содержит по одному элементу для моделирования узла решетки и по четыре однонаправленных элемента-вектора, входы которых соединены с выходами элемента для моделирования узла решетки той же логической схемы, а выходы подключены ко входам элементов для моделирования узлов решетки, соответствующих соседних логических схем матрицы.
3.. Устройство по пп. 1 и 2, от.гичающееся тем, что в нем каждый элемент для моделирования узлов решетки содержит по шестнадцать двухвходовых схем «И», сгруппированных в четыре линейки по четыре схемы «И» в каждой; причем первые входы схем «И» каждой линейки соединены с соответствующими рабочими входами элемента, вторые входы соответствующих схем «И» всех линеек подключены к четырем управляющим входам элемента, а выходы схем «И» каждой линейки соединены., c выходами схем «И» соседних линеек со смещением»а одну схему ..и подключены к соответствующим выходам элемента.
4. Устройство по пп. 1, 2, 3, отличаюигееся тем, что в нем каждый элемент-вектор содержит последовательно включенные первый триггер, схему «И» и второй триггер: установочный вход первого триггера соединен со входом элемента вектора, вход сброса на нуль первого триггера, управляющий вход схемы «И» и входы второго триггера подключены к управляющим входам элемента-вектора, а выход второго триггера соединен с вы57
Фиг 9 чем
"г
RAZ
Т(RAZ н
I — 4 м м н м н
1-1— н
I — I н и н н
I — Ч н м
В1
376973
Фиг.7, ю
55 ! !
I оа
1
I и
1 ( о
t
1
376973
0.. а
@up., И
Бб 58
67 фСоставитель А. Маслов
Техред Л. Грачева
Редактор Л. Утехина
Корректор А. Степанова
Типография, пр, Сапунова, 2
Заказ 2040/5,Изд. № 525 Тираж 647 Подписное
ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР
Москва, )К-35, Раушская наб., д. 4/5