Устройство для поиска информации в памяти

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

-РЕСПУБЛИК сю 4 G 06 F 15 40

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ASTOPCHOMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTKPblTVM (21) 4148880/24-24 (22) 18.11.86 (46) 30.04.88. Бюл. № 16 (71) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) М. Зеебауэр, В. И. Корнейчук и А. П. Марковский (53) 681.325(088.8) (56) Авторское свидетельство СССР № 809206, кл. G 06 F 15/40, 1979.

Авторское свидетельство СССР № 1309041, кл. G 06 F 15/40, 1985.

„„SU„„1392579 A1 (54) УСТРОЙСТВО ДЛЯ ПОИСКА ИНФОРМАЦИИ В ПАМЯТИ (57) Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных и информационно-поисковых системах, выполненных на узлах с большой степенью интеграции. Цель изобретения — повышение эффективности использования объема памяти. С этой целью в устройство, содержащее регистр 3 признака опроса, формирователь 4 адреса, блоки 2 памяти, схемы 6 сравнения, шифратор ll,,регистр 12, элемент ИЛИ 10 и блок 16 управления, введены группы 9, 14 элементов И, дешифратор 15 и мультиплексор 7 с соответствующими связями. 5 ил.

1392579

10

1!зобретение относится к вычисли гель<ой технике и мо кст быть использовано в циф ровых вычислительных и информационнопоисковых системах, выполненных на узлах с болыпoй степенью инTcãðации.

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

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

Устройство содержит накопитель 1, блоки 2 памяти, регистр 3 признака опроса, формирователь 4 адреса, блок 5 сравнения, схемы 6 сравнения, мультиплексор 7, выход 8 устройства, группу 9 элементов И, элемент

ИЛИ 10, шифратор 1, регистр 12, выход 13 устройсгва, гp>,lilt>, 14 элементов И, дешифратор 15, блок 16 управления с выходами 17 21, выходы 22 24 устройства, вход

25 устройства, вход 26 блока управления, входы 27 -30 устройства, вход, 31 формирователя 4 адреса, комбинационный сумматор:32, счетчики 33, 34, элемент ИЛИ 35, элементы И 36- 38, элемент НЕ 39, элемент

40 задержки, элементы И 41, 42, элемент

НЕ 43, элемент 44 задержки, элемент И 45, элемент ИЛИ 46, элемент ИЛИ-НЕ 47. 11одклк>чсние вxoäoâ 3! формирователя 4 к входам сумматора 32 может выполняться различным способом. На фиг. 3 а — г показаны варианты подключении входов 23 к входам сумматора 32. T;Il, в варианте, представленHoм на фиг. 3

В 83pH3HT< ., Ilp<,l<. TBB:lt I, I é паре входов сумматора 32 подсоединены

I-й и (+i) -й Itx<> tl>I 31. В другом вариан гс (фиг. 3«) реализовано подключение, обсспечивак>щее суммирование троек входов 31, и в схеме, представленной на фиг. 3,. показан вариант»одклк)чепия входов 31 к су мматору 32 по четыре. Сумматор 32 может быть выполнен с цепями переноса и без них. Iак, в про<. тейll><. м с. I v÷3< сх<. ма, (I ре,<стtl и 3< и >Iа>f на фиг., 3,, содержит > чстыр<. хвходон<.<х

Н сумматоров Ilo модулю 2, образук>щих суMматор 32. Выбор варианта конструкции сумматора 32 и его связей с входами 31 обусловлен величиной eundo<."If< накопителя. T;II, при небольшом объеме накопителя прс « 15

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

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

В режиме записи (фиг. 5а) на вход 25 устройства поступает информационное слово, а на вход 27 потенциал единичного уровня

С <подачей сигнала пуска на вход 30 блок 16 управления формирует сигнал единичного уровня на своих выходах 17, 18, по которым прои>води>ся прием кода с входов 25 на регистр 3 признака опроса, суммирование разрядов упомянутого кода сумматора 33 с приемом суммы на счетчик 33 (второй счетчик 34 обнуляется) формирователя 4, с выхода 24 котороп> код адреса поступает на адресные входы всех блоков 2 памяти, считывание содержимого ячейки (адрес которой определяется кодом на выходе 24 формирователя 4)

fIcev блоков 2 на входы соответствующих схем 6 сравнения. Одновременно на выходе

19 блока 16 управления формируется потенциал нулевого уровня, поступающий на входы всех элементов И группы 9. Соответственно, на вторые входы всех схем 6 поступает код, сос)оящий из нулей, так что единичные сигналы будут сформированы на выходах тех схем 6, которые соответствуют блокам 2, в которых по адресу, формируемому на выходе 24 формирователя 4, отсутствуют записи (в ячейках по указанному адресу записаны нули) . Если сигнал совпадения будет сформирован на выходе хотя бы одной из схем 6, то на выходах шифратора 11 появится код наименьшего номера из зафиксировавших совпадение, а на выходе элемента

ИЛИ 10 (входе 26 блока 16 управления)— сигнал единичного уровня. Если по адресу, фиксируемому на выходе 24 формирователя 4, во всех блоках 2 ячейки заняты, то на выходе элемента ИЛИ 10 формируется сигнал нулевого уровня и блоком 16 будет инициировано появление единичного сигнала на выходе 20, который, поступая на счетный вход счетчиков 33, 34, увеличивает их содержимое на единицу. Вновь по сигналу с выхода !8 блока 16 управления производится считывание информации из блоков 2 и сравнение ее с нулевым кодом. Если совпадения не будут выявлены, то по описанному выше <.Ilo<.ut)y производится у величение на единицу содержимого счетчиков 33, 34 и считывание o сравнением до тех flop, пока не будет выявлена свободная ячейка в одном из блоков 2 или сформирован сигнал переполнения на выходе 23 второго счетчика 34, свидетельствующий об отсутствии свободных ячеек в блоках 2, т. е. о невозможности

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

В режиме информационного поиска на вход 26 устройства поступает информационное слово, а на вход 28 потенциал единичного уровня (фиг. 5б). С подачей сигнала на вход 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, код номера которого формируется на выходе шифратора 11, фиксируется на регистре 12 и поступает на входы мультиплексора 7, коммутируя ячейку, содержимое которой совпадает с признаком опроса, на выход 8, причем младшие разряды адреса указанной ячейки фиксируются на выходах 24, а старшие — на выходах 13 устройства. Одновременно с выхода элемента

ИЛИ 10 снимается сигнал единичного уровня, который, поступая на вход 26 блока !6 управления, иннцпиру T выдачу последним сигнала конца операции с выхоъа 22.

Режим lloHcKd информации со стирани м (фиг. 5в) отличается от описанного Bbllllc режима поиска информации без стирания тем, что в исходном состоянии единичный потенциал подается на вход 29 устройства и тогда после формирования единичного сигнала на выходе элемента ИЛИ 10 добавляется такт записи нулей в разряды найденной ячейки, что осуществляется выдачей единичного сигнала с выхода 21 и нулевого с выхода 19 блока 16 управления, которыми соответственно открываются элементы И группы 14 и закрываются элементы И груп-!

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

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

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

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

1 1 1 1 1 1 l 1

О О О О О О 0 1

О О О О О О О О

1 1 О 0 О О О О

О О О О О О О 0

О l О 1 0 1 О 0

О О О 1 О 1 О

О О О О О О 1

О О 0 О О О О О

1 1 1 О О 1 О 1

О О 1 1 1 1 О

О О 1 1 О О 0 О

40 О О О О О О О О

1 О 1 1 1 l 1 1

О О 1 О О О О О

1 1 1 О О 1 1 1

И пусть далее сумматор 32 построен по схеме, 45 показанной на фиг. Зг, т. е, младший разряд адреса формируется суммированием по модулю 2 нечетных разрядов информационного слова, а старший четных. Тогда при записи слова 10010000 на выходе 24 формирователя 4 зафиксируется адрес ll. Так как

50 ячейки с указанным адресом заняты во всех блоках 2, то на выходе элемента ИЛ И 10 появится сигнал нулевого уровня и блок 16 управления сигналом с выхода 20 увеличит на единицу содержимое счетчиков 33, 34 (они зафиксируют коды соответственно 00 и 01). Считывание и сравнение с нулевым кодом ячеек блоков 2 с адресом 00 выявит, что свободны указанные ячейки во 2, 3 и 4-м блоках 2, что вызовет формирование на вы1392579

Формула изобретения ходе шифратора 11 и запись в регистр 12 кода 01. Сигнал на втором выходе дешифтора 14 инициирует запись поступившего слова в первую ячейку второго блока 2.

Временная диаграмма описанного процесса приведена на фиг. 5.

При поиске слова 10111111 на выходах 24 формирователя 4 зафиксируется код Ol.

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

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

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

1О

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

2. Устройство по п. 1, отличающееся тем, что блок управления содержит элемент ИЛИ

НЕ, элементы И, ИЛИ, элемент НЕ и элементы задержки, причем первый вход первого элемента ИЛИ соединен с входом пуска и выходом разрешения приема блока, выход первого элемента ИЛИ соединен с первыми входами первого, второго и третьего элементов И и с выходом разрешения считывания блока, второй вход первого элемента И является входом задания записи блока, второй вход второго элемента И и вход первого элемента HE соединены с входом признака наличия свободной ячейки памяти блока, выход первого элемента НЕ соединен с вторым входом третьего элемента И, выход которого соединен с выходом приращения адреса блока и через первый элемент задержки — с вторым входом первого элемента

ИЛИ, выход второго элемента И соединен с первыми входами четвертого и пятого элементов И, вход задания поиска блока соединен с вторым входом четвертого элемента И и через второй элемент НŠ— с вторым входом пятого элемента И, выход которого через второй элемент задержки соединен с выходом разрешения записи блока и с первыми входами второго элемента ИЛИ и шестого элемента И, выход которого соединен с первым входом элемента ИЛИ-НЕ, выход которого является выходом разрешения передачи блока, выход четвертого элемента ИЛИ соединен с вторым входом второго элемента

ИЛИ, выход которого является выходом сигнала конца операции блока, второй вход шестого элемента И является входом задания поиска со стиранием блока, выход первого элемента И соединен с вторым входом элемента ИЛИ-HE.

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

1392579

f7 Ю биг. г

Т +1

1 щ

«2

gag т-1 т — +!

IP

-у-+Я

2т

2т

-у-+

2m г

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

4 — +1 т

+2

4

m г — +1

m г

«+2 т г

Юlп — +1

4 — 2

1392579

27 26

77

UZ7

Ug

Uz0

UzZ

Uzg

М!

392579 ИВ

Ьо

U26

V22

0 20

Ь фиг. b и ааа

4 иг 7

В Н И И П И 3 а к а з 809/54 Тираж 704 Подписное

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4