УСТРОЙСТВО ДЛЯ ИНФОРМАЦИОННОГО ПОИСКА ПО ПРИЗНАКУ В ПАМЯТИ С ПРОИЗВОЛЬНЫМ ДОСТУПОМ Советский патент 1973 года по МПК G06F13/28 

1

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

Известно устройство для информационного поиска по признаку в памяти с произвольным доступом, содержащее п-разрядный входной регистр, ()-paзpядный и (п - k4-m)-pa3рядный регистры числа (где ), подключенные к соответствующим накопителям, связанным с (т4-1)-разрядньп1и регистрами адресов, которые нодсоединены к п-разрядному выходному регистру, блок анализа, подключенный к входному регистру и регистрам числа, и блок управления.

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

Описываемое устройство отличается от известного тем, что оно содержит т-разрядный регистр свободных ячеек, подключенный к разрядам с первого по ш-ый н с (k-fl)-ro по (m + k)-bHd (m + k)-разрядного регистра числа, а также к разрядам с первого но т-ый и с |п-k-f 1)-го по (п-k + m)-ный (п-k + m)-разрядиого регистра числа, разряды входного регистра с первого тю k-ый подключены к одпоименным разрядам (m + k)-разрядного регистра числа, разряды с третьего но (т-Ь2)-ой - к разрядам со второго по (т+1)-ый регистров адреса, разряды с (k+l)-ro по п-ый - к разрядам с первого по

(п-k)-bm (n-k + m)-разрядного регистра числа.

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

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

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

Устройство содержит входной п-разрядный регистр 1, входной канал 2, каналы 3 п 4 передачи информации из входного регистра / в регистры числа 5 и 6 разрядностью (k-f т) и (п-k+m) соответственно (где ), канал 7 передачи содержимого разрядов с 3 по (т + 2)-ой в.кодного регистра / в регистры адреса 8 п 9 разрядностью (ш + 1), подключенные к накопителям 10 и //, связанным с регистрами числа 5 и 6 каналами 12 и 13 соответственно, каналы 14 и 15 считывания информации из накопителей 10, 11 в регистры числа 5 и 5, регистр свободных ячеек 16, предназначенный для хранения адреса первой свободной ячейки списка свободных ячеек, канал 17 передачи адреса очередной свободной ячейки из регистра числа 6 в регистр свободных ячеек 16, канал 18 передачи адреса освободившейся ячейки из регистра адреса 8 в регистр свободных ячеек 16, каналы 19 и 20 передачи адреса свободной ячейки из регистра свободных ячеек 16 в регистры адреса 8, 9, каналы 21, 22, 23 передачи адреса свободной ячейки в соответствующие разряды регистра числа 6, каналы 24, 25, 26 передачи адреса свободной ячейки в соответстгвующие разряды регистра числа 5, канал 27 передачи информации из разрядов с (k-f 1)-го по (т+и)-ый регистра числа 5 в разряды с первого по т-ый регистра числа 6, канал 28 передачи информации из разрядов с первого по т-ый регистра числа 6 в разряды с (k-f 1)-го по (ш-fk)-ый регистра числа 5, блок анализа 29, каналы 30, 31, 32 передачи информации из соответствующих разрядов регистра числа 5 в блок анализа 29, каналы 33, 34 передачи информации из соответствующих разрядов регистра числа 6 в блок анализа 29, канал 35 передачи информации из (т-ЬЗ)-го по k-ый разрядов входного регистра / в блок анализа 29, канал 36 передачи информации из регистра свободных ячеек 16 в блок анализа 29, выходной регистр 37, канал 38 передачи информации из входного регистра 1 в выходной регистр 37, каналы 39, 40 передачи информации из регистров числа 5, 6 ъ выходной регистр 37, каналы 41, 42 передачи информации из регистров адреса 8, 9 в выходной регистр 37, канал 43 передачи информации в выходной регистр 37, канал 44 передачи -информации из выходного регистра 37 во входной регистр /, каналы 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, на которую поступает информация из входного регистра / по каналу передачи 35 и информация из регистра числа 5 по каналу 56 передачи информации из разрядов с (ш-ьЗ)-го по k-ый регистра числа 5 в бло-к анализа 29, схему сравнения 57, на которую поступает информация по каналам передачи 30, 31, 33, 34 из регистров числа 5, 6, схема сравнения 58, на которую поступает информация из регистра числа 5 по каналу передачи 32- и из регистра свободных ячеек 16 по каналу передачи 36, каналы 59, 60, 61, 62 передачи

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

Предложенное устройство работает в следующих режимах: а) режим приема кода;

б) режим стирания кода; в) режим обмена

-информацией с объектом, подключенным к каналу SC.

Коды, хранимые в памяти устройства,; по (ш-Ь2) разрядам k-разрядной признаковой

части объединены в группы (вет1ви).

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

ячеек должен храниться в регистре свободных ячеек 16.

В режиме приема -кода входной п-разрядный код поступает на входной регистр /. Его необходимо записать в ячейку накопителей 10

и У/ в следующей зависимости от k-разрядной

признаковой части информационного кода:

информация с одинаковой признаковой частью

записывается в одну ячейку накопителя 10, 11.

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

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

m-f 1-;-2т соответственно) должен быть записан адрес первого кода в группе. Первая признаковая часть кода указывает адрес ячейки накопителя 10 или 11, в которой должен быть записан адрес первого кода в группе. Первая признаковая часть, за исключением двух старших разрядов, из входного регистра 1 по каналу 7 поступает в регистр адреса 8 или 9. в зависимости от результата дешифрации старшего разряда признаковой части

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

группе хранятСЛ в на соаителях W, If в ячейках с )И I1U ( --1)-ую, то в сгаршии разряд регистра адреса записывается «1. Далее следует обращение иа чтение информации из накопителя W или 11 по адресу, записанному в регистре адреса 5 или 9.,

По результатам дешифрации 2-го разряда признаковой части входного кода определяется, в каких разрядах должен находиться адрес первого кода в группе. Если он был ранее записан, то необходимо по нему обратиться к ячейке, где находится код с одинаковой первой признаковой частью с выходным кодом. Если в П1 разрядах адрес не записан, значит ранее код с данной первой признаковой частью не поступал, следовательно, пришедший код HOBbiii и его необходимо записать в очередную свободную ячейку, а адрес, по которому он будет записан, - в ш разрядов данной ячейки, Для этого порвьш свободный адрес, находяш,ийся в регистре свободных ячеек 16, по каналам 22, или 23, или 25, или 26 передается в m разрядов регистра числа 5 или 6 в зависимости от результата дешифрации 1,2 разрядов признаковой части входного кода. Далее производится обращение на запись числа из регистра числа 5 или 6 в ячейку накопителя 10 или 11 по адресу, установленному в регистре адреса 8 или 9. По оконч ании записи производится гашение регистров адреса 5,9 и регистров числа 5, б и передается содержимое регистра свободных ячеек 16 (адрес, по которому должен быть записан новый код) по каналам 19, 20 в регистры адреса 5, 9. Информационный код должен храниться в ш ячейках с нулевой по (2 -1)-ую накопителей 10, 11, поэтому в старший разряд регистров адреса 8, 9 заносится «О, после чего производится обращение на чтение числа из ячейки накопителей 10, 1} иа регистры числа 5, 6 п гашение регистра свободных ячеек 16. В m разрядах накопителя // производится хранение списка свободных ячеек, поэтому адрес очередной свободной ячейки необходимо поместить в регистр свободных ячеек 16. Для этого, по окончании чтения, содержимое m разрядов регистра числа 6 но каналу 17 передается в регистр свободных ячеек 16. Одновременно признаковая часть числа, находяш.егося во входном регистре /, по каналу 3 поступает в разряды с первого по k-ый регистра числа 5, информационная часть числа с входного регистра поступает в разряды с первого по (п-К)-ый регистра числа 6, после чего производится обращение на запись числа из регистров числа 5, 6 в ячейки накопителей 10, 11. По окончании записи производится гашение регистров числа 5, 6 и регистров адреса 8, 9. Запись нового кода закончена.

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

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

адресом, по которому записан следующий код в группе кодов, объединенных по первой признаковой части. По окончании чтения в схеме сравнения 55 сравниваются вторые признаковые части кодов, находящихся во

входном регистре 1 и регистре числа 5, и производится анализ m разрядов регистра числа 5 в схеме сравнения 57. Если значения вторых признаковых частей совпали, значит в данной ячейКе записан код с той же признаковой

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

кода в группе, обращение производится к следующему коду и производится анализ вторых признаковых частей входного и хранящегося в накопителях кодов. Для этого сначала производит1ся обращение на запись информаНИИ из регистров числа.5 6 ъ накопители 10, 11, но окончании записи гасятся регистры адреса S, 9 и заносится в них информация в m разрядов регистра числа 5, являющихся адресом следующего кода в группе., через канал

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

ЕСЛИ значения вторых признаковых частей

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

.5, б..г;асятсд, после чего информация из регистра свободных-ячеек М (адрес, по которому должен .быт залисан .новый код) по канала-м педедаци 19, 20 поступает на регистры адреса 8, 9. Далее запись нового .кода в очередную сврбрднук) ячейку пр.рисхрд;ит, как былр указанр выше.

:Р режиме стир анияинфррмация, записанная до дан«р у1у адресу, стирается, а адрес следу щегр кода в грурпе, хранящегося в ст. .ячедке, записывается в ячейку пред адущего в .грулпе кода еа место, где ранее б}лл записан адрес стирае.мрй ячейки.

Для этого в старший разряд регистров адрес а S, 9 прризврдится запись «О.

Зате.м следует прризвести стирание информ.а.ц,ии в ячейке накрп телей 10, 11, сохранив п,рн этом адрес следующего крда в группе, записаннргр в данной ячейке со стираемым кодрм и первую признаковую часть для последу1рщегр отыскания адреса первого кода в .группе . Для этргр .производится обращение на чтение .инфррмации из ячейки накопителей 10, 11 в регистры числа 5, 6. Пр окончании чтения произврдится гащение регистра числа 6, после че.со инфор у1ация из регистра свободных ячеек 16 по .каналу 21 прс.тупаетв ш разрядов регистра числа Ь, затем пд)риз:водится обращение .на запВсь информации из регистра числа 6 в У/, гашери. ;регистр а свободных ячеек -/ и пе,редача ин$ррмадии из регистра адреса 8 по ка,налу,,/§ в свр.брднь1х ячеек 16. По ркрнчанщи запис и .-прриздо-дитея гашейие регистров адреса 8/:9 .и р;еги тра числа б, после ч.его первая .придн.акр.вая часть стираемого кода из регистра чдсда ;5-пр каналам передачи 52, 55ii dcjyn ae.TB pejpHCTjpbi адреса 8, 9. следует рбращеняе .по перврй призн а ковои ч а с,т.И;.к .iiep.Bpiyjy коду в группе, адреса которых з.а,пиеа|й в яче,$.|ках со вторай по ()-ую дакопи;1:елей 10, 11, .по.этрму в старшие разрядь1 регистров адреса .5, 9 записывается «1, а 1,2 разрядь признаковой части информации поступают в бл.ок управления 54 для дешифрации. Если адрес первого кода в группе записан э н-акраителе 10, то необходимо адрес следую,щехр крда в группе за .стираемым, находящйгрся в ш разрядах регистра числа 5, по каналу 46 передать в m разрядов регистра нисда 6 и прри.звести гашение регистра числа 5. Дддее следует обращение на чтение информации из яч.ейки накопителя 10 или // в регистр числа 5 или €, по окончании чтения прои.зврдится сравнение адреса первого кода в грулпе, ;зитаннргр из накопителя 10 или 11, с срдер жимьш регистра свободных ячеек М (.,м .(ггираемрго .кода) в схеме сра-внения 5в/.Цсди. ..значе вия срвпали, значит стирается первы.й .код в группе, поэтому следует адрес сд дуюшегР крда, нахрдящегося в m разрядах регистра 5 или ш разрядах чи#л.а 6, передать .в разряды с :первого по т-Ь1й,йд.И .с. (т4-1)-го,пр 2тгый ретисТра чисда 5 ,. с предВ: рительныМ -йх т.атением. Далее следует обращен-иена запись.

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

(адрес связи) записан адрес следующего кода в группе. Для этого в старшие разряды регистров адреса 8, 9 заносится «О, а содержимое с первого по ш-ый или с (т+1)-го по 2ш-ый регистра числа 5 или 6 по каналам 59

или 60, или б/, или 52 поступает в регистр адреса 8, затем, если адрес первого кода в группе б.ул записан в накопителе 11, производится гашение регистра числа 6 и передача информации из m разрядов регистра числа 5 по каналу 27 в ш разрядов регистра .числа 6, далее регистр числа 5 гасится.

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

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

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

числа 5 и т. д.

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

В режиме обмена информацией с объектом

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

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

1. Устройство для информационного поиск.а по признаку в памяти с произвольным досту,пом, содержащее п-разрядный входной регистр, (k-fm)-разрядный и (п-k-fm)-разрядный регистры числа (где ), подключенпМе к соответствующим накопителям, :Связа««ь м с (ш + 1)-разрядными регистрами .ац,ресов, KOTQipbie подсоединены к п-разрядному

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

10

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

2. Устройство по п. 1, отличающееся тем, что блок анализа состоит из трех схем сравнения, входы одной из которых соединены с разрядами с (m-f3)-ro по k-ый входного регистра и (m-f k)-разрядного регистра числа, входы другой - с разрядами с первого по ш-ый и с (m-t-l)-ro по 2т-ый обоих регистров числа, входы третьей - с разрядами с (k + 1)-го по (k-fш)-ый (m + k)-разрядного регистра числа и всеми разрядами регистра свободных ячеек, а выходы всех схем сравнения подключены к устройству управления.

{раг. 1

155

35

кЩ 30 |j/ JJJ 34

Н5 32 JJg

54 Фиг.