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

11:1ОЛ ИСАНИЕИЗОБРЕТЕН ИЯК АВТОе" СКОМУ СВИДЕТЕЛЬСТВУ 4 О 7315 Союз Советских Социалистических Республикависимое от авт. сви тельства-л. С 06 13/О Заявлено 16.Х 1.1971 ( 1714811/18-24с рисоединением заявки М -Государственный камитеСовета Министрав СССРвв делам изобретенийи открытии Приорите ДК 681.327.2(08 ликовано 21,Х 1,1973, Бюллетень46 Дата опубликования описания 29.Ч 11,19 Авторыизобретения Горячева, В, Ф, Киреев гбае Заявитель ИНФОРМАЦИОННОГО ПОИСКАЯТИ С ПРОИЗВОЛЬНЫМ ДОСТУПОМ ТРОЙСТВО РИЗНАКУ В(п - 1)-ый (п - 1+пт)-разрядного регистрачисла,При этом блок анализа цел полнить состоящим из трех сх входы одной из которых соеди. ми с (тп+3)-го по К-ый входно (тп+1) -разрядного регистра чи гой - с разрядами с первого (тп+1) -го по 2 гп-ый обоих ре входы третьей - с разрядами (1;+пт) -ый (гп+1 с) -разрядного и всеми разрядами регистра св а выходы всех схем сравнения устройству управления.Указанные отличия позвол устройство и повысить его бысНа фиг. 1 изображена стру устройства, а па фиг. 2 - -схем за. есообразно выем сравнения, гены с разрядаго регистра исла, входы друпо тп-ый и с гистров числа, с (1+1)-го по регистра числа ободных ячеек, подключены к яют упростить тродействие. ктурная схема а блока анали 20 Ъ стронство содерж регистр 1, входной ка редачи информации и регистры числа б и б(тп+2)-ой входного ре реса 8 и 9 разрядност ныс к накопителям 10 гистрами числа 5 и б 30 ветственно, каналы 14Настоящее изобретение относится к области вычислительной техники.Известно устройство для информационного поиска по признаку в памяти с произвольным доступом, содержащее гг-разрядны входной регистр, (к+пт) -разрядный и (п - к + тп) -разрядный регистры числа (где птснап), подклоченные к соответствующим накопителям, связанным с (гп+1) -разрядными регистрами адресов, которые подсоединены к и-разрядному выходному регистру, блок анализа, подклочснный к входному регистру и регистрам числа, и блок управления.Недостатками известного устройства являются невысокое быстродействие и большос количество оборудования.Описываемос устройство отличается от известного тем, что оно содержгт гп-разрядный регистр свободных ячеек, подклоченыт к разрядам с первого по п 1-ьп, и с (1+1)-го по (и+1 с) -ый (и+1 -разрядного регисра числа, а такжс к ргЗрДгм с первого Го П 1-ый и с (пс+1) -го по (п - 1+пт) -ный (и - -1+тп)- -разрядного регистра числа, разряды входного регистра с первого о 1:.-ы подклочсь к одноименным разрядам (гп+1) -разрядного регистра числа, разряды с третьсго но (тп+2) -ой - к разрядам со второго по (гп+ 1).ый регистров адреса, разряды с (1+1)-го по п.ый - к разрядам с первого по ит входной п-разрядный нал 2, каналы д и 4 пез входного регистра 1 в разрядностью (1+тп) и нно (где птСК(п), каимого разрядов с 3 по гистра 1 в регистры адью (тп+1), подключени 11, связанным с реканалами 12 и И соот. и 15 считывания инфор407315 3мации из накопителей 10, 11 в регистры числа 5 и б, регистр свободных ячеек 16, предназначенный для хранения адреса первой свободной ячейки списка свободных ячеек, канал 17 передачи адреса очередной свободной ячейки из регистра числа б в регистр свободных ячеек 16, канал 18 передачи адреса освободившейся ячейки из регистра адреса 8 в регистр свободных ячеек 16, каналы 19 и 20 передачи адреса свободной ячейки из регистра свободных ячеек 16 в регистры адреса 8, 9, каналы 21, 22, 23 передачи адреса свободной ячейки в соответствующие разряды регистра числа 6, каналы 24, 25, 26 передачи адреса свободной ячейки в соответствующие разряды регистра числа 5, канал 27 передачи информации из разрядов с (1+1)-го по (гп+1 с)-ый регистра числа 5 в разряды с первого по т-ый регистра числа б, канал 28 передачи информации из разрядов с первого по гп-ый регистра числа б в разряды с (1 с+1)-го по (гп+1 с)-ый регистра числа 5, блок анализа 29, каналы ЗО, 31, 32 передачи информации из соответствующих разрядов регистра числа 5 в блок анализа 29, каналы 33, 34 передачи информации из соответствующих разрядов регистра числа б в блок анализа 29, канал 35 передачи информации из (гп+3)-го по 1 с-ый разрядов входного регистра 1 в блок анализа 29, канал Зб передачи информации из регистра свободных ячеек 16 в блок анализа 29, выходной регистр 37, канал 38 передачи информации из входного регистра 1 в выходной регистр 37, каналы 39, 40 передачи информации из регистров числа 5, б в выходной регистр 37, каналы 41, 42 передачи информации из регистров адреса 8, 9 в выходной регистр 37, канал 43 передачи информации в выходной регистр 37, канал 44 передачи информации из выходного регистра 37 во входной регистр 1, каналы 45, 46 передачи информации из выходного регистра 37 в регистры числа 5, 6, каналы 47, 48 передачи информации из выходного регистра 37 в регистры адреса 8, 9, канал 49 передачи информации из выходного регистра 37 на регистр свободных ячеек 16, канал передачи информации 50 из выходного регистра 37, канал 51 передачи адреса связи между кодами внутри группы из регистра числа 5 в регистр адреса 8, каналы 52, 53 передачи информации из разрядов со 2-гоно (2+гп)-ый регистра числа 5 в регистры адреса 8, 9, блок управления 54, схему сравнения 55, на которую поступает информация из входного регистра 1 по каналу передачи 35 и информация из регистра числа 5 по каналу 56 передачи информации из разрядов с (гп+3)-го по 1-ый регистра числа 5 в блок анализа 29, схему сравнения 57, на которую поступает информация по каналам передачи 30, 31, 33, 34 из регистров числа 5, 6, схема сравнения 58, на которую поступает информация из регистра числа 5 по каналу передачи 32 и из регистра свободных ячеек 16 по каналу передачи 36, каналы 59, 60, 61, 62 передачи 4информации из гп-ых разряДов регИСтров чИСла 5, б в регистры адреса 8, 9,Предложенное устройство работает в следующих режимах: а) режим, приема кода;5 б) режим стирания кода; в) режим обмена(т+2) разрядам 1-разрядной признаковой10 части объединены в группы (ветви).Внутри ветви между кодами имеется связь.Адреса первых кодов в ветви помещены в накопитель корней: с 2 П -ой по (2 П+ - 1)-уюячейки накопителей 10, 11. Коды вместе с ад 15 ресами связи, осуществляющими связь внутри ветви, запоминаются в информационной,части накопителей 10 и 11 (ячейки с нулевойпо (2- 1) -ую) . Перед началом работы устройства производится запись списка свобод 20 ных ячеек в накопитель 11, Список свободныхячеек организован таким образом, что в каждой предыдущей свободной ячейке записанадрес следующей свободной ячейки. Адреспервой свободной ячейки списка свободныхячеек должен храниться в регистре свободныхячеек 16.В режиме приема кода входной и-разрядный код поступает на входной регистр 1. Егонеобходимо записать в ячейку накопителей 1050 и 11 в следующей зависимости от Е-разряднойпризнаковой части информационного кода:информация с одинаковой признаковой частьюзаписывается в одну ячейку накопителя 10, 11.Для этого необходимо найти ячейку, в коЗ 5 торой записана информация с данной признаковой частью. Признаковая часть кода разделена на две части. Коды с одинаковой первой(гп+ 1)-разрядной признаковой частью объединены в группы. Поэтому, прежде чем найти40 код с данной признаковой частью, необходимосначала отыскать группу кодов с данной первой признаковой частью, Адреса первых кодов в группе хранятся в накопителях 10, 11 вячейках с 2 -ой по (2 П+ - 1)-ую. Информа 45 ция из 1, 2 разрядов входного регистра 1(1,2 разряд первой признаковой части) пересылается в блок управления 54 для дешифрации О или 1 в старшем разряде указывает на то, в каком накопителе 10 или 11 соот 50 ветственно должен быть записан адрес первого кода в группе с первой признаковой частью,равной первой признаковой части пришедшегокода, О или 1 во втором разряде указывает на то в каких разрядах (1 в ; т или55 п 1+1 - ;2 в соответственно) должен быть записан адрес первого кода в группе. Перваяпризнаковая часть кода указывает адресячейки накопителя 10 или 11, в которой должен быть записан адрес первого кода в груп 50 пе, Первая признаковая часть, за исключениемдвух старших разрядов, из входного регистра1 по каналу 7 поступает в регистр адреса 8или 9. в зависимости от результата дешифрации старшего разряда признаковой части65 входного кода. Так как адреса первых кодов в5Г 1 уппг ;11 аняс в накопителях 10, 11 в ячейках с 2"- й но (2"- 1)-ук, то и сгашарий разряд регистра адреса заннсывастся 1. Далее следует обращение иа чтение информации из накопителя 10 или 11 по адресу, записанному в регистре адреса 8 или 9.По результатам дешифрации 2-го разряда признаковой части входного кода определяется, в каких разрядах должен находиться адрес первого кода в группе. Если он был ранее записан, то необходимо по нему обратиться к ячейке, где находится код с одинаковой первой прнзнаковой частью с выходным кодом. Если в ш разрядах адрсс не записан, значит ранее код с данной первой признаковой частью не поступал, следовательно, пришедший код новый и его необходимо записать в очередную свободную ячейку, а адрес, по которому он будет записан, - в гп разрядов данной ячейки, Для этого первый свободный адрес, находящийся в регистре свободных ячеек 16, по каналам 22, или 23, или 2 б, или 26 передается в т разрядов регистра числа 5 или 6 в зависимости от результата дешифрации 1, 2 разрядов признаковой части входного кода. Далее производится обращение на запись числа из регистра числа б или 6 в ячейку накопителя 10 или 11 по адресу, установленному в регистре адреса 8 или 9. По окончании записи производится гашение регистров адреса 8, 9 и регистров числа б, 6 и передается содержимое регистра свободных ячеек 16 (адрес, по которому должен быть записан новый код) по каналам 19, 20 в регистры адреса 8, 9. Информационный код должен храниться в гп ячейках с нулевой по (2 п - 1)-ую накопител й 10, 11, поэтому в старший разряд регистров адреса 8, 9 заносится О, после чего производится обращение на чтение числа из ячейки накопителей 10, 11 на регистры числа 5, 6 и гашение регистра свободных ячеек 16. В гп разрядах накойителя 11 производится хранение списка свободных ячеек, поэтому адрес очередной свободной ячейки необходимо поместить в регистр свободных ячеек 6. Для этого, по окончании чтения, содержимое т разрядов регистра числа 6 по каналу 17 передается в регистр свободных ячеек 16, Одновременно признаковая часть числа, находящегося во входном регистре 1, по каналу 3 поступает в разряды с первого по 1-ый регистра числа б, информационная часть числа с входного регистра 1 поступает в разряды с первого по (и - 1;)-ый регистра числа 6, после чего производится обращение на запись числа из регистров числа 5, 6 в ячейки накопителей 10, 11. По окончании записи производится гашение регистров числа 5, 6 и регистров адреса 8, 9, Запись нового кода закончена,Если в накопителях 10, 11 был ранее записан код с одинаковой первой признаковой частью с входным кодом, то после обращения к накопителям 10, 11 до первой признаковой части входной информации в гп разрядах регистра числа 5 или 6 будет записан адресЬ 10 15 20 25 30 35 40 45 50 55 60 65 6первого кода в группе, Признаковую часть кода, записанного по этому адресу, необходимо сравнить с признаковой частью входного кода, а адреса первых кодов в группе, находящихся в регистре числа 5 или 6, сохранить. Для этого содержимое регистра числа 5 или 6 записывается в накопители 10 или 11. По окончании записи производится гашение регистров адреса 8, 9, затем адрес первого кода в группе, записанного в регистре числа б или 6, по каналам 59 или 60, или 61, или 62 подается в регистры адреса 8, 9, Так как признаковая часть информационного кода находится в ячейках с нулевой по (2 ф - 1)-ую накопителя 10, в старший разряд регистров адреса 8, 9 заносится О. Далее производится обращение на чтение информации из ячейки накопителей 10, 11 на регистры числа б, 6; т разрядов кода, находящегося в регистре числа 5, являются адресом, по которому записан следующий код в группе кодов, объединенных по первой признаковой части. По окончании чтения в схеме сравнения 55 сравниваются вторые признаковые части кодов, находящихся во входном регистре 1 и регистре числа 5, и производится анализ т разрядов регистра числа 5 в схеме сравнения 57. Если значения вторых признаковых частей совпали, значит в данной ячейке записан код с той же признаковой частью, что и входной код. При несовпадении значений вторых признаковых частен кодов, находящихся во входном регистре 1 и регистре числа б, и при условии, что в гп разрядах регистра числа б записан адрес следующего кода в группе, обращение производится к следующему коду и производится анализ вторых признаковых частей входного и хранящегося в накопителях кодов. Для этого сначала производится обращение на запись информации из регистров числа.б, 6 в накопители 10, П, по окончании записи гасятся регистры ад- реса 8, 9 и заносится в них информация в гп разрядов регистра числа б, являющихся адресом следующего кода в группе., через канал передачи 51, затем производится гашение числа 5, 6, после чего следует обращение на чтение информации из накопителей 10, 11 на регистры числа 5, 6 по новому адресу, записанному в регистрах адреса 8, 9. Далее производится анализ вторых признаковых частей входного и хранимого в накопителях кодов и т разрядов хранимого кода, являющихся адресом следующего кода в группе и т.д.Если значения вторых признаковых частей входного и хранимого в накопителях кодов не совпали и при условии отсутствия информации в т разрядах регистра числа 5, ясно, что входной код новый, его следует записать в очередную свободную ячейку. Для этого содержимое регистра свободных ячеек 16 по каналу передачи 24 поступает в т разрядов регистра числа 5, Далее производится обращение на запись информации из регистров числа б, 6 в ячейку накопителей 10, 11, По окончании записи регистры адреса 8, 9 и регистры числа75, б гасятся, после чего информация из регистра свободных ячеек 16 (адрес, по которому должен быть записан новый код) по каналам передачи 19, 20 поступает на регистры адреса 8, 9. Далее запись нового кода в очередную свободную ячейку происходит, как было указано выше.В режиме стирания информация, записанная по данному адресу, стирается, а адрес следурщегд кода в группе, хранящегося в стираемой ячейке, записывается в ячейку и редь 1 дущего в группе кода яа место, где ранее был записан адрес стираемой ячейки.Ддя этого в старший разряд регистров адреса 8, 9 производится запись 0.Затем следует произвести стирание информации в ячейке накопителей 10, 11, сохранив при этом адрес следующего кода в группе, записанного в данной ячейке со стираемым кодом и первую признаковую часть для последующего отыскания адреса первого кода в ,группе, Для этого производится обращение на чтение информации из ячейки накопителей 10, 11 в регистры числа 5, б, По окончании чтения производится гашение регистра числа 6, после чего информация из регистра свободных ячеек 16 по каналу 21 поступает в пт разрядов регистра числа б, затем производится обращение на запись информации из регистра числа б в 11, гашение регистра свободных ячеек 16 и передача информации из регистра адреса 8 по каналу,18 в регистр свободных ячеек 16. По окончании записи производится гашение регистров адреса 8, 9 и регистра числа 6, после чего цервая признаковая часть стнраемого кода из регистра числа 5 по каналам передачи 52, 58 йостуйает в регистры адреса 8, 9. Далее следует обращение по первой признаковой части к первому коду в групйе, адреса которых записайы в ячейках со второй по (2 " -1)-ую .накопителей 10, 11, поэтому в старшие разряды регистров адреса 8, 9 записывается 1, а 1,2 разряды признаковой части информации поступают в блок управления 54 для дешифрации.,Если адрес первого кода в группе записан в накопителе 10, то необходимо адрес еле. дующего кода в группе за .стираемым, находя 1 цегося в гп разрядах регистра числа 5, по каналу 46 передать в т разрядов .регистра числа 6 и произвести гашение регистра числа 5, Далее следует обращение на чтение информации из ячейки накопителя 10 или 11 в регистр числа 5 или б, по окончании чтения производится сравнение адреса первого кода в .группе, считанного из накопителя 10 или 11, с содержимым регистра свободных ячеек И (адресом стираемого,кода) в схеме сравнения 58.Если значения совпали, значит стирается первый код. в группе, поэтому следует адрес следующего кода, находящегося в в разрядах .регистра числа 5 или т разрядах регистра .числа б, передать в разряды с нерэого по 1 п,-ый,.11 лИ с (т+1) -го,по 2 гп-ый региетра чис,ла 5 или,б с предварительным их .гашением, Далее следует обращение на запись, этих разрядах. Для этого производится запись информации из регистра числа 5 или б в на . копитель 10 или 11. По окончании записи про 1 О 15 занным с (ш+1) -разрядными регистрами .адресов, которые подсоединены к п-разрядному 20 25 ЗЬ зв 40 45 50 55 8Если значения не совпали, следует обращение к накопителю по адресу, записанному в изводится гашение регистров адреса 8, 9. После этого следует обращение к накопителю по адресу первого кода в группе, где вместе с признаковой частью информации в т разрядах (адрес связи) записан адрес следующего кода в группе. Для этого в старшие разряды регистров адреса 8, 9 заносится О, а содержимое с первого по гп-ый или с (в+1) -го по 2 п-ый регистра числа 5 или б по .каналам 59 или 60, или 61, или 62 поступаетв регистр адре са 8, затем, если адрес первого кода в группе бцл записан в накопителе 11, производится гашение регистра числа б и передача информации из т разрядов регистра числа 5 по каналу 27 в т разрядов регистра числа б, далее регистр числа 5 гасится.Затем производится обращение на чтение информации из накопителя 10 в регистр числа 5. По окончании чтения производится сравнение адреса следующего кода в группе, находя. щегося в т разрядах регистра числа 5 с адресом стираемого кода, находящегося в регистре свободных ячеек 16, в схеме сравнения 58. Если значения совпали, то содержимое гп разря. дов регистра числа 5 гасится и в них поступает информация из т разрядов регистра числа б по каналу передачи 28, далее следует обращение на запись информации из регистра числа 5 в накопитель 10.Если значения не совпали, то производится обращение на запись информации из регистра числа 5 в накопитель 10, следует обращение к следующему коду в группе, адрес которого находится в в разрядах регистра числа 5. Для этого производится гашение регистра адреса 8 и передача информации из т разрядов регистра числа 5 в регистр адреса 8 по каналу 51, далее следует обращение на чтение информации из накопителя 10 в регистрчисла 5 и т.д.По окончании стирания устаревшего кода производится гашение регистров числа 5, 6 н регистров адреса 8, 9.В режиме обмена информацией с объектом производится обмен информацией между объ.ктом и регистрами числа 5, б регистрами адреса 8, 9, регистром свободных ячеек 16 и входным регистром 1 через выходной регистр 37. Предмет изобретения 1. Устройство для информационного поиска по признаку в памяти с произвольным досту.пом, содержащее и-разрядный входной регистр, (1+т) -разрядный и (и - 1 с+т) -разрядный регистры числа (где т(1 п), подключвнные к соответствующим накопителям,.свя9выходному регистру, блок анализа, подключенный к входному регистру и регистрам числа, и блок управления, отличающееся тем, что, с целью упрощения и повышения быстродействия устройства, оно содержит т-разрядный регистр свободных ячеек, подключенный к разрядам с первого по ги-ый и с (К+1)-го по (ги+1) -ый (в+1) -разрядного регистра числа, а также к разрядам с первого по тп-ый и с (и - 1 с+1)-го пэ (и - 1+из)-ый (и - 1 с+тп)-разрядного регистра числа, разряды входного регистра с первого по 1-ый подключены к одноименным разрядам (ги+1) -разрядного регистра числа, разряды с третьего по (ги+2)-ой - к разрядам со второго по (гп+ 1)-ый регистров.10адреса, разряды с (1+1)-го по п-ый - к разрядам с первого по (и - К) -ый (и - 1 с+ гп) -разрядного регистра числа.2. Устройство по п. 1, отличающееся тем,5 что блок анализа состоит из трех схем сравнения, входы одной из которых соединены с разрядами с (т+3)-го по 1-ый входного регистра и (т+1) -разрядного регистра числа, входыдругой - с разрядами с первого по т-ый и сО (ги+1) -го по 2 т-ый обоих регистров числа,входы третьей - с разрядами с (1+1) -го по(К+ гп) -ый (т+ Е) -разрядного регистра числаи всеми разрядами регистра свободных ячеек,а выходы всех схем сравнения подключены к15 устройству управления,407315 Состаппгегп. В. Рудаковсдактор Л, Цветкова Текред Т, Ускова корректор наковскаи 30 Тирам 62ого когиптста Совета Мипистизобретений и открытий35, Раушскаи наб., д. 415 о писпю зд. Мсударствен по дела Москва, )К