Патент ссср 200880
2ООЗЗО
ОПИСАНИЕ
ИЗОБРЕТЕН ИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
Ссаа Советскит
Социалистически1
Респуйлин
Зависимое от авт. свидетельства №вЂ”
Кл. 42m, 14
2 а1, 37 04
Заявлено 08. I I.1966 (№ 1054732/26-24) с присоединением заявки ¹
МПК 6 061
Н 031с
УДК 681,325.6(088.8) Приоритет
Опубликовано 15.VIII.1967. Бюллетень № 17
Комитет по делаю иаооретений и открытий при Совете Министров
СССР
Дата опуолинонания описания 2.Х.!967
I т ° т. -... от,. . у, ., ) ""f с" а он,! I
1 лвтор изобретения
Б. И. Перельман
Заявитель
УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЛОГИЧЕСКИХ ЗАДАЧ
Известны устройства для решения логических задач, содержагцие матричное устройство, состоящее из одной или более матриц, соответствующие ячейки которых соединены цепями связи, с дешифраторами управления, выходными индикаторами, горизонтальными и вертикальными регистрами, Предложенное устройство отличается тем, что в нем дополнительно установлены горизонтальные и вертикальные координатные преобразователи, объединенные входы управления которых соединены с дешифратором управления. Сигнальные входы этих преобразователей связаны с соответствующими выходами индикаторов, а сигнальные выходы, являющиеся выходами устройства, соединены со входами горизонтального и вертикального регистров. Это отличие позволяет снизить количество условных и циклических передач уп равления, число команд и операций, сократить число последовательных переборов всей информации, т. е. повысить производительность
3ВМ при решении ряда задач, например, связанных распознанием образов в виде букв, иероглифов, химических формул, данных аэрофотосъемки, радиолокационных изображениИ; задач, связанных с анализом текста при машинном переводе, автоматическом программировании, автоматическом управлении быстротечными процессами; задач, связанных с сопровождением большого количества целей (например, однотактное определение факта изменившейся ситуации на экране радиолокатора, подс: ет количества изображений на экране с сортировкой и анализом картографических материалов) .
На фиг. 1 изображена блок-схема предложенного устройства; на фиг. 2 — блок-схема координатного преобразователя; на фиг. 3— вариант исполнения координатного преобразователя вместе с относящимися к нему сигнальными и управляющими цепями; на фиг.
4 — пример реализации матриц ЗУ; на фиг.
5 — пример реализации элемента быстрого переноса в преобразователях; на фиг. 6— пример реализации логического многофункционального элемента, применяемого в преобразователях.
Блок-схема устройства содержит матричное логическое ЗУ 1, в которое входят блок 2 с генераторами-переключателями и генераторами считывания, соединенными с соответствующими вертикальными и горизонтальными шинами матриц 8, горизонтальные и вертикальные выходные индикаторы 4, дешифратор-преобразователь 5, горизонтальный и вертикальный входные регистры б, горизонтальный и вертикальный координатные преобра30 зователи 7. Цепи 8 соединяют устройство с
200880
Каждая ячейка памяти матрицы 8 содержит два трехдырочных сердечника 45 и 46.
Магнитопроводы, обозначенные индексом О, образуют основную, а обозначенные индексом
d — дополнительную матрицы. Магнитопроводы обеих матриц соединяются обмотками связи 47. Через малые отверстия сердечников в каждом разряде пропущены вертикальные шины 48 считывания. Через те же отверстия четных и нечетных сердечников пропущены двойные горизонтальные шины 49 и 50 считывания, на которые поступают сигналы с выходов генераторов 51 считывания блока 2. Через большие отверстия сердечников каждого разряда пропущены вертикальные шины 52 записи-стирания, к которым подключены выходы генераторов-переключателе" 58 блока 2.
Кроме того, через те же отверстия проходят вертикальные выходные шины 54. Аналогично, через большие отверстия сердечников каждой строки пропущены горизонтальные выходные шины 55, через четные сердечники пропущены
65 датчиком команд, например ЭВМ, а цепи 9, 10, и 9, 11 — с источником обрабатываемой информации. Цепь 8 подключена ко входу дешифратора 5, выходные шины которого соединены цепями 12, 18, 14 и 15 с шинами управления преобразователей 7, цепями 16 и 17 — со входами управления регистров 6, цепями 18, 19 — со входами управления блоков 2 и цепями 12, 20, 14 и 21 — со входами управления индикаторов 4.
Цепи 9, 10 и 9, 11 подключены ко входам регистров б, а выходы регистров соединены цепями 22 с сигHàëüíûìè входами блоков 2.
Выходы блоков 2 цепями 28 соединены с соответствующими шинами матриц 3. В свою очередь, выходные шины матриц соединены цепями 24 с индикаторами 4, в выходы индикаторов цепями 25 — с вертикальным или горизонтальным координатными преобразователями 7, где в соответствии с командой происходит логическая обработка данных, полученных с матриц 8. Выходные цепи 26 и 27 преобразователей 7 соединены с выходом устройства цепями 28 и 29, а с помощью цепей 30,—
81, 82, 88 — со входами регистров 6.
Цепи 25 соединяют сигнальные входы элементов 84 преобразователей с выходами индикаторов 4, а цепи 18 — объединенные входы управления элементов 84 с выходами дешифратора 5.
Дополнительные выходы 85 и дополнительные входы 86 рядом располо>кенных, а также первого и последнего элементов 84 соединены попарно. Элементы 87 быстрого переноса соединены цепями 88 и 89. Кроме того, элементы
34 дополнительно соединены попарно с помощью элементов 87 быстрого переноса с применением для этого цепей 40 и 41.
Выход 26 элемента 84 (фиг. 3) соединен цепями 42 и 48 с дополнительными выходами предыдущей и последующей строк, 44 — шины управления. шины выборки 56, а через нечетные сердечники — шины 57.
I1a фиг. 4 отдельно изобра>кен применяемый в матрицах сердечник 58 с основным магнитопроводом 59, дублирующим 60, магнитопроводом считывания 61, обмоткой связи 47, шиной заземления 62.
Элемент 87 (фиг. 5) содержит транзистор
68 выходного усилителя, транзисторы 64, 65, 66 в схеме ключа, входной трансформатор 67 усилителя, выходной трансформатор 68, трансформатор 69 ключа. Элемент имеет три входа 70, 71 и 72 и два выхода 78 и 74. Вход
70 соединен через отдельные разделительные диоды цепями 40 с выходами элементов 84 в данном, предыдущем и последующем разрядах. Входы 71 каждого элемента 37 данного разряда соединены цепями 88 и 89 с выходами 74 элементов в соседних разрядах, вход
72 — цепями 20 с дешифратором управления, а выход 78 цепями 4(— с обмотками записи сердечников элементов 34 данного, последующего и предыдущего разрядов. На выходе 74 получается сигнал сквозного переноса (для сигналов, поступающих из последующего разряда для переноса в обратном направлении,, входом является выход 74. В этом случае выходной сигнал получается на входе 71).
1 ранзисторы 64, 65 в отсутствие сигнала на входе 72 заперты, сигнал переноса через ключ не проходит, чему способствует открытый в это время транзистор бб. При поступлении разрешающего сигнала на вход 72 транзисторы 64 и 65 отпираются, а транзистор бб запирается, вследствие чего сигнал переноса проходит через ключ с незначительным ослаблением и задержкой. Наконец, транзистор 68 служит для того, чтобы снизить затухание и задержку в цепях переноса.
На фиг. 6 ферритовые сердечники 75 изображены в виде отрезков линий с индексами
Са, Сб и т. д. Цепи записи и стирания отдельных сердечников включаются с помощью транзисторных переключателей 76 — 79 в данном разряде и 80 — 87 — общих для всех элементов.
Трансформаторы 88 подключены и выходам элементов 87. Индекс М относится к рассматриваемому разряду, М вЂ” 1 к предыдущему и
М+1 — к последующему.
В элементе 84, выполненном на ферритовых сердечниках и транзисторах, применено импульсное питание.
В целом, преобразователь 7 пред тавляет собок> своего рода дешифратор с цепями быстрого двустороннего перечоса.
Питание ферритовых сердечников элемента 84 (фиг. 6) осуществляется двухтактными импульсами тока.
При поступлении команды соответствующая ло ическая операция выполняется включением базовой цепи того или иного триода. Коллекторная цепь последнего при этом замыкает цепь и".ïóëüñîâ, получающихся при перемаг200880
Н вып ческ и>ке приводится таблица части операций, олняемых в устройстве для решения логиих задач.
Продолжение
Таблиц а
Обозначение операции
Обозначение операции Ъ) о пп
PJoPfo пп
27 и
29 и
«Зп»
«Пк»
«Зп. Л г. Сл»
31 и
«Зп.Лг.Умн»
«Сч.Лг.Сл»
33 и
6и7
«Реп. на К.Вн.»
«Рсп. на К.Вв.»
36
«Сл.Лг. с Инв.»
«Сч.Инв.Со Стлб.»
«Сл.Ими.»
8 и 9
«Рсп. до Гр.Вв.»
«Рсп. до Гр.Вн.»
«Пк. по Нфк.»
«Иск.»
«Гр.»
«Вст.»
«Сл, 1»
41
«Гр. и Рсп. до
Гр. Вв.»
«Ст.»
«Рсп. 1 на К.Вн.»
14
42
«Гр. и Рсп. до
Гр.Вн.»
«Гр, и Реп. от
Слд, до Гр. Вв.»
16
«Рсп. 1 на К.Вв.»
«Рсп. 1 до Гр.Вв.»
«Гр. и Рсп. от слд. до Гр.Вв.»
«Рспст».
19 и
«Рсп. 2 до Гр.Вв.»
«Рсп. 2 до Гр.Вв.»
«Рсп. 2 до Гр.+
+ Вн.»
46
«Сл. 2»
«Х Сдв
«Инф.Иск.»
«П.Зп. ДО ..»
«П Зп. ОД ..»
«Сч.инв.»
«Рсп. на К.Ц.Вн.»
24
«Перенос 1»
«Рсп. на К.Ц.Вв.»
«Перенос 2»
В ц, когда за еимстолбца, напризапи воло мер начения основер, «Зп». Возы, в частности, ных мож ничивании сердечников. Тем самым исключается необходимость в источниках питания коллекторных цепей.
Наименование элементарной операции
Запись в произвольных разрядах строк
Ассоциативный опрос без разрушения информации
Запись в матрицу с логическим сложением хранимого кода п кода записываемого
То же с логическим умножением кодов
Одновременное считывание произвольной группы слов с получением результата в виде логическои стммы кодов
Поиск с распространением найденного признака на К сгрок вверх или вниз, когда находятся слова, равные опросному, а признак записывается в признаковую ячейку найденной строки и всех последующих (или предыдупнгх) К строк.
То же с распространением до строк с заданными признаками, т, е. до граничных отметок.
Исключение строк из всех операций на В тактов.
Проставление граничных отметок.
13. Восстановление исходного положения после пп. 10 и 11
Стирание
Распространение вниз на К строк с проставлением отметки только в К-й строке
То же вверх
Распространение от данной строки до границы с проставлением отметки только в граничной строке.
То же вниз
То же, что и в пп. 3 и 4 с зачеркивапием отметок в исходной строке (операция позволяет в частности непосредственную выборку одинаковых слов, удовлетворяющих критерию поиска, и их подсчет).
Получение информации об исключенных строках (одновременный опрос всех рабочих строк).
Считывание информации в инверсном коде.
Циклический перенос при распространении на К строк вниз с последней строки на первую
Получение сигнала о наличии такого переноса
То же, что в п. 23 вверх
Получение сигнала о таком переносе таблице приведены обоз групп операций, наприм ны варианты этой команд
Наименование элементарной операции
Аналогично пп. 8 н 9 с цnKлическим переносом
Аналогично пп. 15 и 16 с циклическим переносом
Аналогично nï. 17 н 18 с циклическим переносом
Аналогично пн. 19 и 20 с циклическим переносом
Логическое умножение записываемой информации с инверсным кодом хранимой в матрице и;формации
То же с логическим сложением
Считывание инверсной информации со столбцов.
Импликативное сложение записываемой и хранимой информации.
Поиск по группе признаков с нефиксированным местонахождением признаков.
Получение сигнала о наличии хотя бы одного искомого слова.
Проставление граничной от" метки с одновременным распространением признака вверх до границы
То же вниз.
Проставление граничной отметки с одновременным распространением от следующей строки вниз до граничной отметки.
То же вверх.
Получение сигнала о паличии распространения
Получение сигнала о наличии более одного искомого слова.
Группа операций: запись, считывание. логическая запись и т, п. со сдвигом входной информации во входном сдвиговом регистре вправо и влево
Группа операций: перезапись содержимого одной из дублирующих матриц на основную илн обратно с выполнением логических операций.
Аналогичный список операций, связанных с работой горизонтального, координатного преобразователя с распространением вправо (П) п влево (Л) сь в определенный столбе м «Зп» пишется номер, «Зп. 5».
«Рсп. до Гр.LI,.Ââ,»
«Рсп. до Гр.LI,.Âí.»
«Рсп. 1 на
К.Ц.Вв.»
«Рсп. 1 на
К.Ц. Вн.»
«Рсп, 1 до
Гр.П.Вв.»
«Рсп. 1 до
Гр.Ц.Вн.»
«Рсп. 2 до
Гр.LI,.Ââ.»
«Рсп. 2 до
Гр.LI,.Âí.»
«Умн.Лг. с Инв.»
200880
Команда «Проставление граничных отметок», приведенная в таблице, означает определение искомой строки в ЗУ с одновременным включением в координатном логическом преобразователе ячейки памяти, относящейся к данной строке. Эта ячейка во включенном состоянии определяег границу распространения сигнала в цепи быстрого переноса преобразователя.
Запись в матрицу рассмотренного устройства осуществляется следующим образом.
Код операции поступает на дешифратор 5.
В зависимости от команды на соответствующих выходах дешифратора появляются сигналы управления, подаваемые на управляемые входы регистров 6 и генераторов 2. При выполнении обычной или логической записи в строки или столбцы матриц на горизонтальный (или вертикальный) регистр 6 поступают входные данные, а на вертикальный (или горизонтальный) регистр — сигналы, определяющие выбираемую строку или столбец. Одновременно с сигналами, разрешающими запись на регистр 6, а затем считывание с него, с выходов этого регистра поступают сигналы на генераторы 2.
Сигналы с дешифратора 5 определяют вид включенных генераторов (считывания или записи) и режим их работы, например, соответствующий обычной записи или записи с логическим умножением и т. д. Сигналы с выходов генераторов на блоке 2 подаются на шины матриц и обеспечивают необходимую операцию.
При ассоциативном опросе с фиксацией найденных слов (записью отметок в найденных строках) код операции поступает на дешифратор 5. Одновременно код информации подается на регистр 6, а с последнего — на блок
2 генераторов, где вызывает срабатывание генераторов считывания. С выходов этих генераторов импульсы считывания проходят на шины считывания матриц 8. На выходных шинах матрицы, соответствующих строкам или столбцам, где хранимая информация совпадает с кодом опроса, появляется сигнал соответствия, поступа!ощий по цепям 24 на индикаторы 4. На управляемые входы этих индикаторов подаются с дешифратора 5 по цепям
20 или 21 сигнаlb! включения индикаторов.
С выходов индикаторов 4 сигналы следуют по цепям 25 на преобразователи 7, т. е. на сигнальные входы элементов 84. Одновременно на управляемые входы элементов 84 приходят сигналы управления по цепям 18 или
15, которые определяют режим работы элементов. В рассматриваемом случае эти элементы выполняют операцию «ДА», вследствие чего сигналы с выходов преобразователя 7 по цепям 26 или 27 поступают с заданной задержкой на входы регистров 6. Пришедшая тем временем следующая часть команды обеспечивает на выходах 16 или 17 дешифратора
5 сигналы управления, а это, в свою очередь, — г рием дBHHbfõ в регистр 6, с выходов
60 последнего — — на генераторы 2 и далее на соответствующие шины записи. Одновременно из ЭВ!Ч поступает сигнал на регистр 6, определяющий строку или столбец матриц, в которую записывается признак.
Подсчет идентичных слов или столбцов, записанных на матрицах, выполняется в следуюи(ем порядке.
1. Ассоциативный опрос матрицы по искомым признакам и проставлению граничных отметок, соответствующих найденным словам, в координатном преобразователе, Обозначение операции: «ПК+Гр».
При поступлении кода сигналов управления по цепям 18 и 15 па элементы 84 и 87 включаются транзисторные переключатели 80 и81, вследствие чего устанавливается цепь записи в сердечники 75 (¹ 1) для сигнала, поступаюц:,cIо по цепи 25 из матрицы. Далее при считывании с сердечника обеспечивается также перезапись в сердечники памяти 75 (ЯП 1) .
Б дальнейшем, в каждом такте работы элемента ка выходе сердечника 75 (Са) получается сигнал «грапичной отметки». Этот сигнал поступает на базу транзисторного переключателя 77, отпирает его, вследствие чего коллекторная цепь шунтирует вход 72 элемента 87. Те» самым разрывается цепь переноса в координатном преобразователе на все вреMÿ, пока «проставлена граничная отметка».
2. Распространение от нижней строки матрицы до первой «граничной отметки» с получением сигнала на выходе 26 в строке, соответствующей указанной отметке, и зачеркивание исходной отметки.
Обозначение операции: «Рсп. 1 до Гр. Вв».
На выходе 26 элемента 34 каждого разряда вырабатывается сигнал только в том случае, ссли в нем проставлена «граничная отметка» (см. п. 1 рассматриваемого примера) и если в элемент поступил сигнал переноса снизу по цепи 40 из разряда М вЂ” 1 на. выходную цепь 26 в данном разряде. В свою очередь, этот сигнал поступает с трансформатора 88, помещенного на выходе элемента 87 предшествующего разряда, если отсутствует
<гранич!!ая отметка» в предшествующем разряде, (т. е. при наличии сигнала на входе 72 элемента 87, поступающего по цепи 18, 15) и включен транзисторный переключатель 86.
Транзистор 86 включается сигналом, поступающим по шине, соединенной с его базой.
3. Повторение операции по п. 2 рассматриваемого примера до прекращения подачи сигкала о наличии распространения «Расп», раз. решающего сигналы управления по шинам, соединенным с базами триодов 86.
В остальных примерах ограничимся рассмогрением способов решения задач.
1. перебор и отсчет фигур на,!!агрице идоизводится слес) юшиа способом.
1. Считывание по всем разрядам с получением вертикальных проекций всех фигур и
65 проставлением граничных отметок в спроецированных точках.
Обозначение операций: «Инф. Иск. + Гр».
2а. Распространение по вертикали от начала координат до первой граничной отметки, названной 1 в, с получением выходного сигнала (и дальнейшим преобразованием этого cv. нала в импульс считывания) .
«Рсп. 1 до Гр.Вв»
2б. Считывание по строке, соответствующей точке Iв, с получением горизонтальной проекции Iг — Iг нижнего сечения фигуры и проставление граничных отметок в спроецированных точках.
«Сч. + Гр». а имеет вид: «Рсп. до
Общая команд
Гр.ea- -C +Гр».
3а. Распространение по горизонтали от Одо г.:ервой отметки 1г.
«Рсп. 1 до Гр. Вв + Зп».
Зб. Считывание по вертикали через первую отметку 1г., с получением вертикального сечения 1в — 1в и простазлением граничных от:.стои. Результат записывается в столбец, отведенный для признаков.
«Сч. + Гр» и «Рсп. до Гр. Вв»+«Зп».
4. Считывание со столбца признаков с получением сигналов в пределах 1в — Iв и получение при дальнейшем считывании соответствуюгцей горизонтальной проекции 2г — 2г.
Результат записывается в строку признаков.
5. Считывание со строки признаков и получение сигналов считывания в пределах 2г — 2г; получение проекции 2в — 2в и запись результа в столбец признаков.
«Сч»+ «Сч (2г — 2г)»+«Зп»
6. Считывание со столбца признаков и получение сигналов считывания в пределах 2в — 2в, фиксация проекции Зг — Зг с записью результата (проекции) в строку признаков:
«Сч» — «Сч (2в — 2в)»+ «Зп»
7. Считывание со строки признаков и получение сигналов считывания в пределах Зг — Зг с последующим получением проекции Зв — Зв.
«Сч»+ «Сч (Зг — Зг)».
8. Сравнение полученного результата с содержанием столбца признаков опроса по строкам в пределах найденной проекции Зв — Зв и фиксация сигнала «1» или «0» на выходе строки признаков. «1» указывает на совпадение полученной и первоначальной проекций фигуры, что позволяет перейти к следующей операции исключения строк вне проекции, а затем к п. 9.
9. Считывание в пределах полученной проекции, нахождение горизонтальной проекции и исключение столбцов вне этой проекции. («0» в и. 8 указывает на необходимость продолжения последовательного перебора горизонтальных и вертикальных проекций).
Таким образом, выбор первой и последуюших фигур при любых размерах таблицы, ко25
ЗО
50 л; честве фигур и конфигурации изображений требуется около 10 команд. Каждая команда выполняется за одно обращение.
1I. Индикаи,ггя вхождения и с с,гедуеагой точки в контур произвольной формгг выполгг>гется следую щгглг образолг.
1. Сечение по координате (строке) исследуемой точки. Запись в строку признаков.
2. Опрос по всем строкам от верхнего края матрицы до рассматриваемой строки с получением горизонтальной проекции отсеченной сверху фигуры и записью полученной при этом логической суммы во вторую строку признаков.
3. Распространение от проекции рассматриваемой точки до ближайших проекций сечения контура. (Выполняется распространением вправо и влево для первой строки признаков).
4. Опрос второй строки признаков полученным при выполнении и. 3 кодом. При успешном опросе ответ положителен.
III. Анализ и лодггу>икаггия коланд проера»гягы осуществляется, наггрилгер, как показано в приведеннолг ниже частном случае.
Последовательность команд куска программы вносится в матрицу. В ходе решения задачи:
1, При получении сигнала, указывающего, например, на изменение типа цели («не самолет», а «ракета:>), содер>кание определенного столбца матрицы логически сложить с «1» в каждой строке в диапазоне от команды с признаком A до команды с признаком М, (что будет означать, например, внесение в команду указания — брать данные из заданного массива памяти) при условии, что между этими командами отсутствует команда с признаком Н.
2. При получении сигнала о резком возрастании скорости цели, в часть команд, удовлетвор, ноших заданным условиям, внести указание:
«вместо сложения с данными таблицы констант — выполнять умножение на эти константы». Это достигается, например, логическим умножением информации соответствующего столбца на «1» и т. и.
Форма записи команд в матрицу ясна из предыдушего.
Предмет изобретения
Устройство для решения логических задач, содержащее матричное устройство с одной или более матрицами, соответствующие ячейки которых соединены цепями связи, с дешифраторо. г управления, выходными индикаторами, горизонтальным и вертикальным регистрами, отличающееся тем, что, с целью повышения быстродействия при обработке информации, в нем дополнительно установлены горизонтальные и вертикальные координатныепреобразователи, объединенные входы управления котовых соединены сдешифратором
200880
12 управления, сигнальные входы этих преобразователей связаны с соответствующими выходами индикаторов, а их сигнальные выходы, служащие выходами устройства, соединены со входами горизонтального и вертикального регистров.
20088О
Согтавптелв А. А. Соколов
Тедред Т. П. Курилко Корректоры: A. П. Татариице=".à . и Н. И. Быстрое .
Редактор Н, С, Коган
Типография, пр. Са..снова. 2
Заказ 3107/18 Тира и о ) 3 Подпис:п е
11НИИПИ Комитета по дела."я изобретений и открыгий ири Совете Министров СССР
Москва, Центр, пр. Серова, д. 4
