Устройство для поиска информации в памяти Советский патент 1988 года по МПК G06F17/30 

(Л

со со

ND СД

СО

1Ъ

Изобретение относится к вычислите.лы1ОЙ технике и может быть исполь.човано в циф ровых вычис.чительных и информационно- поисковых системах, выполненных на узлах с большой стеиенью интеграции.

Це;1ью изобретения является повышение эффективности использования об1)ема намят и.

На фиг. 1 нредставлена схе.ма устройства; на фиг. 2 - схема формировате.тя ал- реса; на фиг. 3 - возможные варианты нод- ключения выходов регистра признака онроса по входам комбинационного сумматора; на фиг. 4 - схема блока уп)авления; на фи. 5 7 временные диаграммы рабо1Ы устройства в режимах записи информации, поиска информации, поиска информации со стиранием соответственно.

Устройство содержит накопитель 1, блоки 2 памяти, регистр 3 признака опроса, формирователь 4 адреса, блок 5 сравнения, схемы 6 сравнения, мультиплексор 7, выход 8 устройства, гругшу 9 элементов И, элеме 1т ИЛИ К), нифратор 11, регистр 12, выход 13 устройства, rpyiHiy 14 элементов И, дешифратор 15, блок 16 управления с выхода- .1И 17 21, выходы 22-24 устройства, вход 25 устройства, вход 26 блока управления, входы 27 -30 устройства, вход 31 формирователя 4 адреса, комбинационный сумматор 32, счетчики 33, 34, элемент ИЛИ 35, элементы И 36- 38, элемент НЕ 39, элемент 40 задержки, элементы И 41, 42, элемент НЕ 43, э. 1емент 44 задержки, элемент И 45, элемент ИЛИ 4(), элемент ИЛИ-НЕ 47. Подключение входов 31 формировате.чя 4 к входам .мат(фа 32 может вьпюлняться различным способом. На (|)иг. 3 а-г показаны варианты подключения входов 23 к входам сум.матора 32. Так, в варианте, представленном на фиг. За к /-и паре входов сумматора 32 (, у,ти - разрядность регистра 3)

подключены /-и и (гп-/-|-1)-й входы 31. В варианте, представле1{но.м на фиг. 36, к /-Й паре входов суммаюра 32 подсоединены

г -й и ( вх(;ды 31. В другом вариа1Г1е

(фиг. Зв) реализовано подключение, обеспечивающее суммирование троек входов 31, а в схеме, нредставленной на фиг. 3с , показан вариант нодключения входов 31 к сум.ма- тору 32 по четыре. Сумматор 32 .может быть выпо;1нен с цепя.ми переноса и без них. Гак, в г1ростеЙ1пем С-лучае схема, представленная

Fia фи|-. 3t , содержит четырехвходовых

сумматоров цо модулю 2, образующих сумматор 32. Выбор варианта конструкции сумматора 32 и его связей с входами 31 обусловлен величиной емкосги накопителя. Так, при небольц ом объеме накопителя предпоч0

5

0

5

0

5

0

5

0

5

тителен вариант, показанный на фиг. Зг, а при числе ячеек накопителя, сравнимом с ве;1ичиной 2, предпочтительна схема, представленная на фиг. За.

Устройство может работать в одном из трех режимов; записи информации, поиска информации, поиска информации со стиранием. Исфядок функционирования устройства в упомянутых режимах иллюстрируются временными диаграммами.

В режиме записи (фиг. 5а) на вход 25 устройства поступает информационное слове), а на вход 27 - потенциал единичного уровня. С подачей сигнала пуска на вход 30 блок 16 управления формирует сигнал единичного уровня на своих выходах 17, 18, по которым производится прием кода с входов 25 на регистр 3 признака опроса, суммирование разрядов упомянутого кода сумматора 33 с приемом суммы на счетчик 33 (второй счетчик 34 обнуляется) формирователя 4, с выхода 24 которого код адреса поступает на адресные входы всех блоков 2 памяти, считывание содержимого ячейки (адрес которой определяется кодо.м на выходе 24 формирователя 4) всех блоков 2 на входы соответствующих схем 6 сравнения. Одновременно на выходе 19 блока 16 управления формируется потенциал нулевого уровня, поступающий на входы всех элементов И группы 9. Соответственно, на вторые входы всех схем 6 поступает код, сос1ояп1ий из нулей, так что единичные сигналы будут сформированы на выходах тех схем 6, которые соответствуют блокам 2, в которых по адресу, формируемому на выходе 24 формирователя 4, отсутствуют записи (в ячейках по указанному адресу записаны нули). Если сигнал совпадения будет сформирован на выходе хотя бы одной из схем 6, то на выходах шифратора 11 появится код наименьщего номера из зафиксировавших совпадение, а на выходе элемента ИЛИ 10 (входе 26 блока 16 управления) - сигнал единичного уровня. Если по адресу, фиксируемому на выходе 24 формировате- .|я 4, во всех блоках 2 ячейки заняты, то на выходе элемента ИЛИ 10 формируется сигнал нулевого уровня и блоком 16 будет инициировано появление единичного сигнала на выходе 20, который, поступая на счетный вход счетчиков 33, 34, увеличивает их содержимое на единицу. Вновь по сигналу с выхода 18 блока 16 управления производится считывание информации из блоков 2 и сравнение ее с нулевым кодом. Если совпадения не будут выявлены, то по описанному выше способу производится увеличение на е.чиницу содержимого счетчиков 33, 34 и считывание со сравнением до тех пор, пока не будет выявлена свободная ячейка в одном из блоков 2 или сформирован сигнал переполнения на выходе 23 второго счетчика 34, свидете;1ьствую1ций об отсутствии свободных ячеек в блоках 2, т. е. о невозможности

записи поступившего на входы 25 информационного слова. В первом из упомянутых случаев на регистре 12 зафиксируется код номера блока 2, в котором выявлена свободная ячейка, а на выходе элемента ИЛИ 10 появится единичный сигнал, который инициирует формирование единичного сигнала на выходе 21 блока 16 управления, которым открываются элементы И группы 14 для прохождения кода номера блока 2, в который должна быть произведена запись, на входы дешифратора 15, который формирует единичный сигнал на входе записи упомянутого блока 2, в ячейку с адресом на выходе 24 формирователя 4 которого производится запись кода информационного слова с регистра 3 (элементы И группы открыты единичным сигналом с выхода 19 блока 16 управления). Блок 16 управления формирует на выходе 22 сигнал конца операции записи.

В режиме информационного поиска на вход 26 устройства поступает информационное слово, а на вход 28 - потенциал единичного уровня (фиг. 56). С подачей сигнала на вход 30 блок 16 управления формирует потенциалы единичного уровня на выходах 17-19. Соответственно осуществляется прием кода с входа 25 на регистр 3 признака опроса, суммирование разрядов упомянутого кода сумматором 32 с фиксацией суммы на счетчике 33, установка в нуль разрядов счетчика 34, считывание содержимого одноименной ячейки (адрес которой определяется кодом на выходе 24 формирователя 4) всех блоков 2 на входы соответствующих схем 6, на вторые входы которых через открытые элементы И группы 9 поступает код признака опроса. При отсутствии сигналов совпадения со схем 6 блок 16 управления выдает единичный сигнал с выхода 20, по которому производится приращение содержимого счетчиков 33, 34. Вновь производится (сигналом с выхода 18 блока 16 управления) считывание и сравнение с признаком опроса содержимого одноименных ячеек блоков 2. При отсутствии сигналов совпадения схем 6 описанный выще цикл повторяется до появления сигнала переполнения счетчика 34 (при переполнении счетчик 33 устанавливается в нуль и продолжает счет), который свидетельствует об отсутствии в блоках 2 искомой информации, или до появления сигнала совпадения на выходе одной из схем 6, код Номера которого формируется на выходе шифратора II, фиксируется на регистре 12 и поступает на входы мультиплексора 7, коммутируя ячейку, содержимое которой совпадает с признаком опроса, на выход 8, причем младшие разряды адреса указанной ячейки фиксируются на выходах 24, а старшие - на выходах 13 устройства. Одновременно с выхода элемента ИЛИ 10 снимается сигнал единичного уровня, который, поступая на вход 26 блока 16

0

5

0

5

управления, инициирует выдачу иос.юдним сигнала конца операции с выхода 22.

Режим поиска информации со стиранием (фиг. 5в) отличается от описанного выи1е режима поиска информации без стирания тем, что в исходном состоянии единичный потенциал подается на вход 29 устройства и тогда после формирования единичного сигнала на выходе элемента ИЛИ 10 добавляется такт записи нулей в разряды найденной ячейки, что осуществляется выдачей единичного сигнала с выхода 21 и нулевого с выхода 19 блока 16 управления, которыми соответственно открываются элементы И группы 14 и закрываются элементы И группы 9. С регистра 12 через элементы И группы 14 и дешифратор 15 на вход записи блока 2, содержащего найденную ячейку (ее адрес в блоке 2 фиксируется на выходах 24 формирователя 4 адреса) подается единичный сигнал, инициирующий запись в найденную ячейку кода, состоящего из нулей, подаваемого на информационные входы блоков 2 с выходов элементов И группы 9. Блок 16 управления формирует на своем выходе 22 сигнал конца операции.

Функционирование устройства иллюстрируется следующи.м примером.

Пусть, накопитель 1 объемом 16X8 бит состоит из 4 боков 2 объемом 4X8 бит и содержит следующую информацию:

30

35

40

5

0

5

И пусть далее сумматор 32 построен по схеме показанной на фиг. Зг, т. е. младший разряд адреса формируется суммированием по модулю 2 нечетных разрядов информационного слова, а старщий - четных. Тогда при записи слова 10010000 на выходе 24 формирователя 4 зафиксируется адрес 11. Так как ячейки с указанным адресом заняты во всех блоках 2, то на выходе элемента ИЛИ 10 появится сигнал нулевого уровня и блок 16 управления сигналом с выхода 20 увеличит на единицу содержимое счетчиков 33, 34 (они зафиксируют коды соответственно 00 и 01). Считывание и сравнение с нулевым кодом ячеек блоков 2 с адресом 00 выявит, что свободны указанные ячейки во 2, 3 и 4-м блоках 2, что вызовет формирование на выходе шифратора 11 и запись в регистр 12 кода 01. Сигнал на втором выходе дешиф- тора 14 инициирует запись поступившего слова в первую ячейку второго блока 2. Временная диаграмма описанного процесса приведена на фиг. 5.

При поиске слова 10111111 на выходах 24 формирователя 4 зафиксируется код 01. Считывание и сравнение с информационным словом всех вторых ячеек блоков 2 выявит совпадение с четвертой схемой 6. На регистре 12 и выходе 13 зафиксируется код 11 (старшие разряды адреса искомого слова), а на выходе 24 - код 01 (младшие разряды адреса искомого слова.

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

Формула изобретения

I. Устройство для поиска информации в памяти, содержащее регистр признака опроса, формирователь адреса, блоки памяти, схемы сравнения по числу блоков памяти, щифратор, регистр, элемент ИЛИ и блок управления, выход разрешения приема которого соединен с входом записи регистра признака опроса, информационный вход которого является информационным входом устройства, выход каждого блока памяти соединен с первым входом соответствующей схемы сравнения, выход разрешения считывания блока управления соединен с входами считывания блоков памяти, выход приращения адреса блока управления соединен с входом увеличения на единицу адреса формирователя адреса, отличающееся тем, что, с целью повышения эффективности использования объема памяти, в него введены две группы элементов И, дешифратор и мультиплексор, выход которого является информационным выходом устройства, информационный выход формирователя адреса соединен с адресным входом каждого блока памяти и выходом младших разрядов адреса устройства, выходы блоков памяти соединены с информационными входами мультиплексора соответственно, выход регистра признака опроса соединен с информационным входом формирователя адреса и первыми входами элементов И первой группы, вторые входы которых соединены с выходом разрешения передачи блока управления, а выходы соединены с информационными входами блоков памяти и вторыми входами схем сравнения, выходы которых соединены с входами шифратора и элемента ИЛИ, выход которого соединен с входом признака наличия свободной ячейки памяти блока управления, выход шифратора соединен с уп0

5

0

5

0

5

0

5

0

5

равляющим входом коммутации мультиплексора и информационным входом регистра, выход которого соединен с выходом старших разрядов адреса устройства и первыми входами элементов И второй группы, вторые входы которых соединены с выходом разре- щения записи блока управления, а выходы соединены с входом дешифратора, выходы которого соединены с входами записи соответствующих блоков памяти, установочный вход формирователя адреса соединен с выходом разрешения приема блока управления выход сигнала отсутствия свободных ячеек формирователя адреса является выходом признака отсутствия свободных ячеек устройства, вход записи регистра соединен с выходом разрешения считывания блока управления, вход пуска которого и входы задания записи, задания поиска, задания поиска со стиранием являются управляющими входами устройства, выход сигнала конца операции блока управления является выходом сигнала окончания работы устройства.

2.Устройство по п. 1, отличающееся тем, что блок управления содержит элемент ИЛИ НЕ, элементы И, ИЛИ, элемент НЕ и элементы задержки, причем первый вход первого элемента ИЛИ соединен с входом пуска и выходом разрешения приема блока, выход первого элемента ИЛИ соединен с первыми входами первого, второго и третьего элементов И и с выходом разрешения считывания блока, второй вход первого элемента И является входом задания записи блока, второй вход второго элемента И и вход первого элемента НЕ соединены с входом признака наличия свободной ячейки памяти блока, выход первого элемента НЕ соединен с вторым входом третьего элемента И, выход которого соединен с выходом приращения адреса блока и через первый элемент задержки - с вторым входом первого элемента ИЛИ, выход второго элемента И соединен с первыми входами четвертого и пятого элементов И, вход задания поиска блока соединен с вторым входом четвертого элемента И и через второй элемент НЕ - с вторым входом пятого элемента И, выход которого через второй элемент задержки соединен с выходом разрешения записи блока и с первыми входами второго элемента ИЛИ и шестого элемента И, выход которого соединен с первым входом элемента ИЛИ-НЕ, выход которого является выходом разрешения передачи блока, выход четвертого элемента ИЛИ соединен с вторым входом второго элемента ИЛИ, выход которого является выходом сигнала конца операции блока, второй вход шестого элемента И является входом задания поиска со стиранием блока, выход первого элемента И соединен с вторым входом элемента ИЛИ-НЕ.

3.Устройство по п. 1, отличающееся тем, что формирователь адреса содержит два счетчика и комбинационный сумматор, вход

которого является информационным входом формирователя, а выход соединен с информационным входом первого счетчика, выход которого является информационным выходом формирователя, выход переполнения второго счетчика является выходом сигнала

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

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных и информационно-поисковых системах, выполненных на узлах с большой степенью интеграции. Цель изобретения - повышение эффективности использования объема памяти. С этой целью в устройство, содержашее регистр 3 признака опроса, формирователь 4 адреса, блоки 2 памяти, схемы 6 сравнения, шифратор 11, ,регистр 12, элемент ИЛИ 10 и блок 16 управления, введены группы 9, 14 элементов И, дешифратор 15 и мультиплексор 7 с соот- ветствуюшими связями. 5 ил.

зп

Фиг.З

Фиг. 2

31

24

27 26

28

фиг. 5

29

28 I О

о

/71

АЛ

ZA

о

АЛ АЛ АЛ АЛ

26k

О U22

о

U20

о jj

АЛ АЛ АЛ

о

У

АЛ

:

г г /- г

/1

АЛ

фиг. 6

л

/1