Устройство для информационного поиска по признаку в памяти с произвольным доступом

 

,. с а

l

ОЛ ИСАНИЕ

ИЗОБРЕТЕН ИЯ

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

4O73l5

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

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

Республик

Зависимое от авт. свидетельства Л вЂ”

Заявлено 16.XI.1971 (№ 1714811/18-24)

c рисоединением заявки ¹â€”

Приоритет—

Опубликовано 21.XI.1973. Бюллетень № 46 .Дата опубликования описания 29.Ч11.1974

М.Кл. С 06f 13/00

Государственный хамитei

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

УДК 681.327.2(088.8) Авторы изобретения

Л. Н. Горячева, В. Ф. Киреева и В. А. Тугбаев

Заявитель

УСТРОЙСТВО ДЛЯ ИНФОРМАЦИОННОГО ПОИСКА

ПО ПРИЗНАКУ В ПАМЯТИ С ПРОИЗВОЛЬНЫМ ДОСТУПОМ

Настоящее изобретение относится к области вычислительной техники.

Известно устройство для информационного поиск» по признаку в памяти с произвольным доступом, содержащее п-разрядный входной регистр, (k+m) -разрядный и (и — k + m)-разрядный регистры числа (где m

Недостатками известного устройства являются невысокое быстродействие и большос количество оборудования.

Описыв»емос устройство отличается от известного тем, что оно содержит m-разрядный регистр свободных ячеек, подключенный к разрядам с первого по m-ый и с (k+1)-ro vo (m+1<)-ый (m+1<)-ра рядного регистра числа, а т»кжс к разрядам с первого по m-ый и с (п--!<+1)-го по (n — 1<+m)-ный (и — -k+m)-разрядного регистра числа, разряды входного рсгl!oTp» с первого 1!о 1<-ый подк7!o !c!II>! !< 0$поименным разрядам (m-+1<)-разрядного регистра числя, разряды с третьего но (m+2) -ой — к разрядам со второго по (m+1) -ый регистров адреса, разряды с (1<+1)-го по п-ый — к разрядам с первого по

2 (и — k+ m) -разрядного регистра (n — k) -ый числа.

При этом блок анализа целесообразно выполнить состоящим из трех схем сравнения, входы одной из которых соединены с разрядами с (m+3)-го по k-ый входного регистра и (m+k)-разрядного регистра числа, входы другой — с разрядами с первого по m-ый и с (m+ l ) -ro по 2 m-ый обоих регистров числа, входы третьей — с разрядами с (k+1)-го по

l k+ m) -ый (m+ k) -разрядного регистра числа и всеми разрядами регистра свободных ячеек, а выходы всех схем сравнения подключены к устройству управления.

Указанные отличия позволяют упростить устройство и повысить его быстродействие.

На фиг. 1 изображена структурная схема устройства, я па фиг. 2 — -схема блока анализа.

20 Устройство содержит входной и-разрядный регистр 1, входной канал 2, каналы 8 и 4 передачи информации из входного регистра 1 в регистры числа 5 и б разрядностью (k+m) и (и--k+m) соответственно (где m

3 мации из накопителей 10, 11 в регистры числа

5 и б, регистр свободных ячеек 16, предназначенный для хранения адреса первой свободной ячейки списка свободных ячеек, канал 17 передачи адреса очередной свободной ячейки из регистра числа б в регистр свободных ячеек 16, канал 18 передачи адреса освободившейся ячейки из регистра адреса 8 в регистр свободных ячеек 16, каналы 19 и 20 передачи адреса свободной ячейки из регистра свободных ячеек 16 в регистры адреса 8, 9, каналы

21, 22, 28 передачи адреса свободной ячейки в соответствующие разряды регистра числа 6, каналы 24, 25, 26 передачи адреса свободной ячейки в соответствующие разряды регистра числа 5, канал 27 передачи информации из разрядов с (k+1)-го по (m+k)-ый регистра числа 5 в разряды с первого по m-ый регистра числа б, канал 28 передачи информации из разрядов с первого по m-ый регистра числа б в разряды с (k+1)-го по (m+k)-ый регистра числа 5, блок анализа 29, каналы 30, 81, 82 передачи информации из соответствующих разрядов регистра числа 5 в блок анализа 29, каналы 88, 84 передачи информации из соответствующих разрядов регистра числа б в блок анализа 29, канал 85 передачи информации из (m+3)-го по k-ый разрядов входного регистра 1 в блок анализа 29, канал 86 передачи информации из регистра свободных ячеек 16 в блок анализа 29, выходной регистр 87, канал 88 передачи информации из входного регистра 1 в выходной регистр 87, каналы 89, 40 передачи информации из регистров числа

5, б в выходной регистр 87, каналы 41, 42 передачи информации из регистров адреса 8, 9 в выходной регистр 87, канал 48 передачи информации в выходной регистр 37, канал 44 передачи информации из выходного регистра

87 во входной регистр 1, каналы 45, 46 передачи информации из выходного регистра 87 в регистры числа 5, 6, каналы 47, 48 передачи информации из выходного регистра 87 в регистры адреса 8, 9, канал 49 передачи информации из выходного регистра 87 на регистр свободных ячеек 16, канал передачи информации 50 из выходного регистра 87, канал 51 передачи адреса связи между кодами внутри группы из регистра числа 5 в регистр адреса 8, каналы

52, 58 передачи информации из разрядов со

2-гоно (2+m)-ый регистра числа 5 в регистры адреса 8, 9, блок управления 54, схему сравнения 55, на которую поступает информация из входного регистра 1 по каналу передачи 35 и информация из регистра числа 5 по каналу

56 передачи информации из разрядов с (m+3)-ro no k-ый регистра числа 5 в блок анализа 29, схему сравнения 57, на которую поступает информация по каналам передачи

30, 81, 83, 84 из регистров числа 5, 6, схема сравнения 58, на которую поступает информация из регистра числа 5 по каналу передачи

82 и из регистра свободных ячеек 16 по каналу передачи 86, каналы 59, 60, 61, 62 передачи

4 информации из m-ых разрядов регйстров числа 5, б в регистры адреса 8, 9.

Предложенное устройство работает в следующих режимах: а) режим, приема кода; б) режим стирания кода; в) режим обмена .информацией с объектом, подключенным к каналу 50, Коды, хранимые в памяти устройства,. по (m+2) разрядам k-разрядной признаковой о части объединены в группы (ветви).

Внутри ветви между кодами имеется связь.

Адреса первых кодов в ветви помещены в накопитель корней: с 2 -ой по (2 + — 1)-ую ячейки накопителей 10, 11. Коды вместе с ад15 ресами связи, осуществляющими связь внутри ветви, запоминаются в информационной ,части накопителей 10 и 11 (ячейки с нулевой по (2 — 1) -ую) . Перед началом работы устройства производится запись списка свободgo ных ячеек в накопитель 11, Список свободных ячеек организован таким образом, что в каждой предыдущей свободной ячейке записан адрес следующей свободной ячейки. Адрес первой свободной ячейки списка свободных ячеек должен храниться в регистре свободных ячеек 16.

В режиме приема кода входной и-разрядный код поступает на входной регистр 1. Его необходимо записать в ячейку накопителей 10 зо и 11 в следующей зависимости от k-разрядной признаковой части информационного кода: информация с одинаковой признаковой частью записывается в одну ячейку накопителя 10, 11.

Для этого необходимо найти ячейку, в коз5 торой записана информация с данной признаковой частью. Признаковая часть кода разделена на две части. Коды с одинаковой первой (m+1)-разрядной признаковой частью объединены в группы. Поэтому, прежде чем найти

4о код с данной признаковой частью, необходимо сначала отььскать группу кодов с данной первой признаковой частью. Адреса первых кодов в группе хранятся в накопителях 10, 11 в ячейках с 2 -ой по (2 + — 1)-ую. Информа45 ция из 1, 2 разрядов входного регистра 1 (1,2 разряд первой признаковой части) пересылается в блок управления 54 для дешифрации «О» или «1» в старшем разряде указывает на то, в каком накопителе 10 или 11 соот5о ветственно должен быть записан адрес первого кода в группе с первой п ризнаковой частью, равной первой признаковой части пришедшего кода. «О» или «)» во втором разряде указывает на то в каких разрядах (1 —:m или

55 m+1 —;2m соответственно) должен быть записан адрес первого кода в группе. Первая признаковая часть кода указывает адрес ячейки накопителя 10 или 11, в которой должен быть записан адрес первого кода в груп60 пе. Первая признаковая часть, за исключением двух старших разрядов, из входного регистра

1 по каналу 7 поступает в регистр адреса 8 или 9. в зависимости от результата дешифрации старшего разряда признаковой части

65 входного кода. Так как адреса первых кодов в

4О7З15

5 групп-.;р; ках с 2" -ой но (2 ": ---1)-уK), fo и сгарший разряд рсгистpcl адреса записывается « ». Далее следует обращение иа чтение информации из накопителя 10 или 11 по адресу, записан, ому в регистре адреса 8 или 9.

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

Если в m разрядах адрсс не записан, значит ранее код с данной первой признаковой частью не поступал, следовательно, пришедший код новый и его необходимо записать в очередную свободную ячейку, а адрес, по которому он будет записан, — в m разрядов данной ячейки, Для этого первый свободный адрес, находящийся в регистре свободных ячеек 16, по каналам 22, или 28, или 25, или 26 передается в

m разрядов регистра числа 5 или 6 в зависимости от результата дешифрации 1, 2 разрядов признаковой части входного кода. Далее производится обращение на запись числа из регистра числа 5 или 6 в ячейку накопителя 10 или il по адресу, установленному в регистре адреса 8 или 9. По окончании записи производится гашение регистров адреса 8,9 и регистров числа 5, 6 и передается содержимое регистра свободных ячеек 16 (адрес, по которому должен быть записан новый код) по каналам 19, 20 в регистры адреса 8, 9. Информационный код должен храниться в m ячейках с нулевой по (2 — 1)-ую накопител и 10, 11, поэтому в старший разряд регистров адреса

8, 9 заносится «0», после чего производится обращение на чтение числа из ячейки накопителей 10, 11 на регистры числа 5, 6 и гашение регистра свободных ячеек 16. В m разрядах накойителя 11 производится хранение списка свободных ячеек, поэтому адрес очередной свободной ячейки необходимо поместить в регистр свободных ячеек 16. Для этого, по окончании чтения, содержимое m разрядов регистра числа 6 по каналу 17 передается в регистр свободных ячеек 16. Одновременно признаковая часть числа, находящегося во входном регистре 1, по каналу 8 поступает в разряды с первого по k-ый регистра числа 5, информационная часть числа с входного регистра 1 поступает в разряды с первого по (и — 1;)-ый регистра числа 6, после чего производится обращение на запись числа из регистров числа 5, 6 в ячейки накопителей 10, 11.

По окончании записи производится гашение регистров числа 5, 6 и регистров адреса 8, 9.

Запись нового кода закончена.

Если в накопителях 10, 11 был ранее записан код с одинаковой первой признаковой частью с входным кодом, то после обращения к накопителям 10, 11 по первой признаковой части входной информации в m разрядах регистра числа 5 или 6 будет записан адрес

Ь

6 первого кода в группе. Признаковую часть код.i, записанного по этому адресу, необходимо сравнить с признаковой частью входного кода, а адреса первых кодов в группе, находящихся в регистре числа 5 или 6, сохранить. Для этого содержимое регистра числа 5 или 6 записывается в накопители 10 или 11. По окончании записи производится гашение регистров адреса 8, 9, затем адрес первого кода в группе, записанного в регистре числа 5 или 6, по каналам 59 или 60, или 61, или 62 подается в регистры адреса 8, 9. Так как признаковая часть информационного кода находится в ячейках с нулевой по (2" — 1)-ую накопителя 10, в старший разряд регистров адреса 8, 9 заносится

«0». Далее производится обращение на чтение информации из ячейки накопителей 10, 11 на регистры числа 5, 6; m разрядов кода, находящегося в регистре числа 5, являются адресом, по которому записан следующий код в группе кодов, объединенных по первой признаковой части. По окончании чтения в схеме сравнения 55 сравниваются вторые признаковые части кодов, находящихся во входном регистре 1 и регистре числа 5, и производится анализ m разрядов регистра числа

5 в схеме сравнения 57. Если значения вторых признаковых частей совпали, значит в данной ячейке записан код с той же признаковой частью, что и входной код. При несовпадении значений вторых признаковых частей кодов, находящихся во входном регистре 1 и регистре числа 5, и при условии, что-в m разрядах регистра числа 5 записан адрес следующего кода в группе, обращение производится к следующему коду и производится анализ вторых признаковых частей входного и хранящегося в накопителях кодов. Для этого сначала производится обращение на запись информации из регистров числа.5, 6 в накопители 10, П, по окончании записи гасятся регистры ад реса 8, 9 и заносится в них информация в m разрядов регистра числа 5, являющихся адресом следующего кода в группе., через канал передачи 51, затем производится гашение числа 5, 6, после чего следует обращение на чтение информации из .накопителей 10, 11 на регистры числа 5, 6 по новому адресу, записанному в регистрах адреса 8, 9. Далее производится анализ вторых признаковых частей входного и хранимого в накопителях кодов и

m разрядов хранимого кода, являющихся адресом следующего кода в группе и т.д.

Если значения вторых признаковых частей входного и хранимого в накопителях кодов не совпали и при условии отсутствия информации в m разрядах регистра числа 5, ясно, что входной код новый, его следует записать в очередную свободную ячейку. Для этого содержимое регистра свободных ячеек 16 по каналу передачи 24 поступает в m разрядов регистра числа 5. Далее производится обращение на запись информации из регистров числа 5, 6 в ячейку накопителей 10, 11. По окончании записи регистры адреса 8, 9 и регистры числа

40731 5

5, б гасятся, после чего и нформация из регистра свободных ячеек 16 (адрес, по которому должен быть записан новый код) по каналам передачи 19, 20 поступает на регистры адреса

8, 9. Далее запись нового кода в очередную свободную .ячейку происходит, как было указан,о выше.

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

Ддя этого в старший разряд регистров адреса 8, 9 производится запись «0».

Затем следует произвести стирание информации в ячейке накопителей 10, 11, сохранив при этом адрес следующего кода в группе, записанного в данной ячейке со стираемым кодом и первую признаковую часть для последующего отыскания адреса первого кода в ,группе. Для этого производится обращение на чтение информации из ячейки накопителей 10, 11 в регистры числа 5, б. По окончании чтения производится гашение регистра числа 6, после чего информация из регистра свободных ячеек

16 по каналу 21 поступает. в m разрядов регистра числа 6, затем производится обращение на запись информации из регистра числа 6 в

1l, гашение регистра свободных ячеек 16 и передача информации из регистра адреса 8 по каналу, 18 в регистр свободных ячеек 16. По окончании записи .производится гашение регистров адреса 8, 9 и регистра числа 6, после чего цервая призна ковая часть стнраемого кода из регистра числа 5 по каналам передачи

52, 58 йостуйает в регистры адреса 8, 9. Далее следует обращение по первой признаковой «асти к первому коду в групйе, адреса которых записайы в ячейках со второй по (2 " -1)-ую накопителей 10, 11, поэтому в старшие разряды регистров адреса 8, 9 записывается «1», а

1,2 разряды признаковой части информации поступают в блок управления 54 для дешифрации.,Если адрес первого кода в группе записан в накопителе 10, то необходимо адрес следующего кОда в группе за стираемым, находя1цегося в m разрядах регистра числа 5, по каналу 46 передать в m разрядов .регистра числа 6 и произвести гашение регистра числа

5. Далее следует обращение на чтение информации из ячейки накопителя 10 или 11 в регистр числа 5 или б, по окончании чтения про.изводится сравнение адреса первого кода в группе, считанного из накопителя 10 или 11, с содержимым регистра свободных ячеек И (адресом стираемого,кода) в схеме сравнения

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

m-ый,11лИ с (m+1)-ro,ïî 2гп=ый регистра чис,ла -5 или,б с предварительным .их -гашением. Далее следует обращение на запись. этих разрядах. Для этого производится запись информации из регистра числа 5 или б в на5 . копитель 10 или 11. По окончании записи про10 занным с (m+1) -разрядными регистрами .ад-65 ресов, которые подсоединены к п-разрядному

25 а0

as

50 55

Если значения не совпали, следует обращение к накопителю по адресу, записанному в изводится гашение регистров адреса 8, 9. После этого следует обращение к накопителю по адресу -первого кода в группе, где вместе с признаковой частью информации в m разрядах (адрес связи) записан адрес следующего кода в группе. Для этого в старшие разряды регистров адреса 8, 9 заносится «0», а содержимое с первого по m-ый или с (m+ 1) -го по

2m-ый регистра числа 5 или б по .каналам 59 или 60, или 61, или62поступаетв регистр адре са 8, затем, если адрес первого кода в группе бцл записан в накопителе 11, производится гашение регистра числа б и передача информации из m разрядов регистра числа 5 по каналу 27 в m разрядов регистра числа б, далее регистр числа 5 гасится.

Затем производится обращение на чтение информации из накопителя 10 в регистр ч исла

5. По окончании чтения производ ится сравнение адреса следующего кода в группе, находящегося в m разрядах регистра числа 5 с адресом стираемого кода, находящегося в регистре свободных ячеек 16, в схеме сравнения 58. Если значения совпали, то содержимое m разрядов регистра числа 5 гасится и в них поступает информация из m разрядов регистра числа

6 по каналу передачи 28, далее следует обращение на запись информации из регистра числа 5 в накопитель 10.

Если значения не совпали, то производится обращение на запись информации из регистра числа 5 в накопитсль 10, следует обращение к следующему коду в группе, адрес которого находится в m разрядах регистра числа

5. Для этого производится гашение регистра адреса 8 и передача информации из m разря.дов регистра числа 5 в регистр адреса 8 по каналу 51, далее следует обращение на чтение информации из накопителя 10 в регистр числа 5 и т. д.

По окончании стирания устаревшего кода производится гашение регистров числа 5, 6 н регистров адреса 8, 9.

В режиме обмена информацией с объектом производится обмен информацией между объктом и регистрами числа 5, б регистрами адреса 8, 9, регистром свободных ячеек 16 и входным регистром 1 через выходной регистр

87.

Предмет изобретения

1. Устройство для информационного поиска по признаку в памяти с произвольным доступом, содержащее и-разрядный входной регистр, (k+ m) -разрядный и (п — k+ m) -разрядный регистры числа (где m(k(n), подключенные к соответствующим накопителям,.свя4073l5

9 выходному регистру, блок анализа, подключенный к входному регистру и регистрам числа, и блок управления, отличающееся тем, что, с целью упрощения и повышения быстродействия устройства, оно содержит m-разрядный регистр свободных ячеек, подключенный к разрядам с первого по m-ый и с (k+1)-го по (m+k)-ый (m+k)-разрядного регистра числа, а также к разрядам с первого по m-ый и с (и — k+1)-го пэ (и — k+m)-ый (и — k+m)-разрядного регистра числа, разряды входного регистра с первого по k-ый подключены к одноименным разрядам (m+k)-разрядного регистра числа, разряды с третьего по (m+2)-ой — к разрядам со второго по (m+1) -ый регистров

10 адреса, разряды с (k+1)-го по и-ый — к разрядам с первого по (и — k)-ый (и — k+m)-разрядного регистра числа.

2. Устройство по п. 1, отличающееся тем, s что блок анализа состоит из трех схем сравнения, входы одной из которых соединены с разрядами с (m+3)-го по k-ый входного регистра и (m+k) -разрядного регистра числа, входы другой — с разрядами с первого по m-ый и с

1и (m+1) -го по 2m-ый обоих регистров числа, входы третьей — с разрядами с (k+1)-го по (k+m)-ый (m+k)-разрядного регистра числа и всеми разрядами регистра свободных ячеек, а выходы всех схем сравнения подключены к

1ь устройству управления, 407315

Составители В. Рудаков

Текре11 T. Ускова Корректор И. Познаковскаи

Рс,1актор Л. Цветкова

За горек:IH типо! ра(авиа

1::ки.з 17(17 11зд. ¹ 1130 Тирам< 621 По иисиюе

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

Москва, 7К-35, Раушскаи наб., д. 4/5