Устройство для поиска данных

 

Изобретение относится к вычислительной технике и может быть использовано в системах управления базами данных. Цель изобретения - расширение функциональных возможностей устройства за счет возможности определения граничных адресов подмассива данных в заданном интервале значений ключей записи. Это достигается тем, что устройство содержит регистр 1 адреса верхней границы, регистр 2 адреса нижней границы, сумматор 3, реверсивный счетчик 4, регистр 5 ключа нижней границы, две схемы 6 и 7 сравнения, регистр 8 информации, блок 9 памяти, два элемента И 10,11, две группы элементов ИЛИ 12,13, первый 14, второй 15 и третий 16 элементы ИЛИ, выходной регистр 17 адреса нижней границы, распределитель 18 импульсов, генератор 19 импульсов. Устройство также содержит регистр 20 ключа верхней границы, выходной регистр 21 адреса верхней границы, шесть групп элементов И 22-27, с третьего по десятый элементы И 28-35, с четвертого по восьмой элементы ИЛИ 36-40, третью группу 41 элементов ИЛИ, третью 42, четвертую 43 и пятую 44 схемы сравнения, триггер 45 управления, триггер 46 режима, кроме того, в устройство входят триггер 47 пуска, вход 48 ключа нижней границы, выход 49 адреса нижней границы, вход 50 адреса нижней границы, вход 51 адреса верхней границы, установочный 52 вход, вход 53 ключа верхней границы, выход 54 адреса верхней границы, вход 55 поиска, вход 56 чтения, выход 57 готовности, вход 58 пуска, выход 59 признака отсутствия подмассива, выход 60 записи. 2 ил.

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

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

РЕСПУБЛИК (19) (11) (S>)S С 06 Р 15/40

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

Н А ВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ HOMHTET

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫ7ИЯМ

ПРИ ГКНТ СССР (21) 4473456/24-24 (22) 15.08.88 (4б) 15.05.90. Бюл. У 18 (72) В,Г.Попов, С,А.Удинцев и И.В.Ступин (53) 681.325(088.8) (56) Авторское свидетельство СССР

М 1126972, кл. G 06 F 15/40, 1984.

Папернов А.А. и Подымов В.Я. Методы упорядочения информации в цифровых системах. N. Наука, 1973, с. 384.

Овчаров Л.А. и Селетков С.Н. Автоматизированные банки данных. И.:

Финансы и статистика, 1982, с. 262, Авторское свидетельство СССР

1228116, кл. G 06 F 15/40, 1986.

2 (54) УСТР011СТВО ЛЛЯ ПОИСКА ДАНКЬ1Х (57) Изобретение, относится к вычислительной технике и может быть использовано в системах управления базами данных. Цель изобретения — расширение функциочальных возможностей устройства за счет возможности определения граничных адресов подмассива дан:..".:". в заданном интервале значений ключей записи, Это достигается тем, что устройство содержит регистр

1 адрес верхней границы, регистр 2 адреса нижней границы, сумматор 3, реверсивный 4 четчик, регистр 5 ключа нижней границы, две схемы 6 и

7 сравнения, регистр 8 информации, а блок 9 памяти, два элемента И 10, 1564648

11, две группы элементов ИЛИ )2, 13, первый 14, второй 15 и третий )6 элементы ИЛИ, выходной регистр 17 адреса нижней границы, распределитель

18 импульсов, генератор 19 импульсов. Устройство также содержит регистр 20 ключа верхней границы, выходной регистр 21 адреса верхней границы, шесть групп элементов И 22-27, 10 с третьего по десятый элементы И

28-35, с четвертого по восьмой элементы ИЛИ 36-40, третью группу 41 элементов ИЛИ, третью 42, четвертую

43 и пятую 44 схемы сравнения, триг- 15 верхнеи границы, установочныи вход

52, вход 53 ключа верхней границы, выход 54 адреса верхней границы, вход

55 поиска, вход 56 чтения, выход 57

25 готовности, вход 58 пуска, выход 59 признака отсутствия подмассива, выход

60 записи.

Устройство работает следующим образом.

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

Служебное поле используется для ука35 зания кода ключа (идентификатора), а информационное — для размещения смыслового содержания идентифицируемой части записи, Записи набора данных отсортированы по возрастанию

40 значений ключей. Это означает, что, если i-я запись размещена по k-му адресу, то (i+1)-я запись хранится по (k+1)-му адресу, причем ключ (i+1)-й записи больше ключа i-й за45 писи, т.е. функция адреса блока 9 памяти линейно зависит от приращения, значений кода ключа.

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

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

Изобретение относится к вычислительной технике и может быть использовано в системах управления базами данных.

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

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

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

11, две группы элементов ИЛИ 12 и 13, первый 14, второй 15 и третий 16 элементы ИЛИ, входной регистр 17 адреса нижней границы, распределитель

18 импульсов, генератор 19 импульсов, регистр 20 ключа верхней границы, выходной регистр 21 адреса верхней границы, шесть групп элементов

И 22-27, элементы И с третьего по десятый 28-35, элементы ИЛИ с четвертого по восьмой 36-40, третью группу 41 элементов ИЛИ, третью 42, четвертую 43 и пятую 44 схемы сравнения, триггер 45 управления, триггер 46 режима, триггер 47 пуска, вход . 48 ключа нижней границы, выход 49 адреса нижней границы, вход 50 адреса нижней границы, вход 51 адреса гер 45 управления, триггер 46 режима. Кроме того, в устройство входят триггер 47 пуска, вход 48 ключа ниж.ней границы, выход 49 адреса нижней границы, вход 50 адреса нижней грачицы, вход 5) адоеса верхней грани ..ы, установочный 52 вход, вход 53 к.:юча верхней границы, выход 54 адреса верхней границы, вход 55 поиска, вход 56 чтения, выход 57 готовности, вход 58 пуска, выход 59 приз: ака отсутствия подмассива, выход

Ы записи. 2 ил.

Введем следующие обозначения:

Нà — нижняя граница — адрес перо вой записи исходного массива;

Вà — верхняя граница — адрес поо следней записи исходного массива;

Р„ - адрес блока памяти i ro цикла устройства;

Ая,- — адрес первой записи подмассива;

А — адрес последней записи подSl массива;

Кл — ключ исходной записи поди массива;

Кл — ключ считанной записи из J блока памяти.

Устройство работает в двух режимах: поиска и чтения информации.

Установка режима производится IIQ входам 55 и 56. При подаче на вход 55 импульса в устройстве устанавливает-. ся режим поиска данных. При необходимости чтения подмассива выделенных записей по входу 56 подается импульс, Ф устанавливающий триггер режима 46 в единичное состояние, Работа устройства в режиме поиска подмассива требуемых записей состоит в следующем.

В исходном состоянии распределитель 18 импульсов, регистры 8, 17 и

21, триггеры 47 и 45 установлены в состояние "0", На входы 53 и 48 подаются коды ключей нижней и верхней границ искомого подмассива соответственно. На входы 51 и 50 поступают коды адресов верхней и нижней границ исходного массива. По входу 55 поступает импульс, устанавливающий триггер 46 в нулевое состояние, определяя режим поиска записей, ключи которых лежат в заданном интервале.

Единичным сигналом с инверсного выхода триггера 46 открыт элемент И 34.

После установки триггера 46 по входу

52 подается импульс, по которому разрешается запись исходной информации в регистры 5 и 20, в регистр 1 — через открытые элементы И ВВ, в регистр

2 — через элементы ИЛИ 12, и импульс на синхронизирующем входе через элемент ИЛИ 14 и аналогичным образом в регистры 17 и 21 через элементы

ИЛИ 41, ИЛИ 13 и элементы И 34,. ИЛИ

38 и ИЛИ 39 соответственно.

Начало поиска записи инициируется подачей импульса пуска по

64648

55 входу 58, устанавливающему триггер

47 в единичное состояние. Единичным сигналом с прямого выхода триггера

47 открывается элемент И 30 по первому входу, в результате чего импульсы с генератора ; 9 подаются на вход распределителя 18 импульсов, Импульсы с выходов распределителя 18 подаются в различные точки устройства.

Работа устройства состоит из двух этапов, каждый из которых выполняется одинаково. Первый этап используется для определения адреса нижней (первой) границы подмассива, а на втором этапе обеспечивается нахождение верхней (последней) границы лодмассива. Первый этап выполняется при нулевом состоянии триггера 45. При завершении первого этапа, т.е. после определения первой, нижнеи границы подмассива триггер 45 устанавливается в состояние "1", переводя устройство во второй этап работы.

По окончании второго этапа триггер 47 устанавливается в состояние

"0", ".ри этом на выходе 57 формируется единичный сигнал, используемый в качестве сигнала готовности устройства к выдаче информации в заданном интервале значений ключей.

В зависимости от соотношения ключей исходного массива н заданного интервала значения ключей подмассива в регистрах 17 и 21 формируются граничные адреса искомого подмассива.

1, Ключ НГ равен ключу НГ и ключ

ВГ равен ключу ВГ . При этом в регистре 17 устанавливается адрес НГ а в регистре 21 — адрес ВГ„.

2. Ключ НГ равен ключу НГ, а ключ ВГ больше ключа ВГ . При этом в регистре 17 формируется адрес НГ„, а в регистре 21 — адрес ВГ

3. Ключ НГ равен ключу НГ, а ключ ВГ меньше ключа ВГ . В этом случае в регистре 17 формируется ад." рес НГО, а в регистре 21 — адрес, меньший адреса последней границы массива с ключом ВГО.

4. Ключ ВГ равен ключу ВГ, а ключ НГ больше ключа НГ . При этом в регистре 17 формируется адрес НГ, лежащий внутри массива, а в регистре 21 — адрес ВГО .

5 ° Ключ ВГ меньше ключа ВГ, но адрес с ключом ВГ„ лежит внутри мас-. сива, а ключ ВГ больше ключа ВГ, 1564648

При этом в регистре 17 устанавливается адрес, лежащий внутри массива, а в регистре 21 формируется адрес ВГ, .

6 Ключ ВГ равен ключу ВГ., а 5 ключ ВГ больше ключа ВГ„. При этом в регистрах 17 и 21 устанавливается один и тот же адрес записи с ключом ВГ

7. Ключи НГ и ВГ больше ключа

, ВГ . При этом в устройстве формируется сигнал Отсутствие подмассива".

8. Ключ НГ меньше ключа НГ, а ,ключ ВГ равен ключу Bl"о, При этом в регистре 17 формируется адрес НГ а в регистре 21 — адрес ВГ

9. Ключ НГ меньше ключа НГ, а ! ключ ВГ больше ключа ВГ . В данном

: случае в регистре 17 устанавливается адрес НГ, а в регистре 21 — ад- 20 рес ВГО.

10 . Ключ НГ меньше ключа HI, а ключ ВГ меньше ключа ВГ„, но больше ,ключа НГ . При этом в регистре 17 формируется адрес НГ, а в регистре 25 21 — адрес записи, лежащей внутри массива. !

11. Ключ НГ меньше ключа НГ„, а . ключ ВГ равен ключу НГО . В данном случае в регистрах 17 и 21 устанавли- 30

:вается адрес НГ

12. Ключи НГ и ВГ меньше ключа

НГ„. В этом случае в устройстве формируется сигнал "Отсутствие подмасtt сида 35

В любой из этих указанных ситуаций поиск нижней границы выполняется следующим образом, С помощью сумматора 3 определяется сумма ВГ +НГ, которая со сдви- 40 гом на один разряд вправо (в сторону младших разрядов) заносится в счетчик

4 по первому импульсу с выхода распределителя 18, Этот импульс поступает через открытый элемент И 29 по инверсному входу нулевым сигналом с выхода "Меньше" схемы 7 сравнения (так как адрес ВГ больше адреса НГ„) на вход разрешения записи счетчика 4.

Таким образом, в счетчике 4 фиксируется код адреса

ВГ +НГО

Р о

< 2 где . (х) — ближайшее целое „меньшее либо равное х.

По этому адресу производится об ращение в блок 9 памяти, и считанная запись с ключом Клв принимается в регистр 8 по второму имп;:чьсу с выхода распределителя 18, поступающего на синхровход регистра 8.

Так как триггер 45 находится в нулевом состоянии, то единичным сигналом с его инверсного выхода открыты э. ементы И 25, и код ключа НТ с выхо,ов регистра 5 поступает на второл вход схемы 6 сравнения. Первый вход этой схемы связан с выходом кода клюрегистра 8 через открытые в дан.ом режиме элементы И 27.

Пссредством схемы 6 производится проверка соотношения Кл и ключа

3 искомой границы. При этом возможны следующие ситуации. .А, Коды ключей совпадают.

В этом случае на выходе "Равно" схемы 6 формируется единичный сигнал, которым через элемент ИЛИ !6 открывается по четвертому входу элемент

И 31. Так как этот элемент открыт также по первому входу единичным сигналом с инверсного выхода триггера

45, по второму входу — единичным сигналом с инверсного выхода триггера

46, то по очередному импульсу с выхода распределителя 18, поступающему через элементы И 31 и ИЛИ 38 на синхровход регистра 17, в него принимается адрес первой (нижней) границы подмассива из счетчика 4 через элементы ИЛИ 41. Затем по импульсу выхода распределителя 18 через открытый элемент 35 И единичным сигналом с выхода "Равно" схемы 6 триггер

45 устанавливается в единичное состояние. При этом нулевым сигналом с инверсного выхода триггера 45 закрываются элементы И 31 и 25, а открываются элементы И 32 и 26 единичным сигналом с прямого выхода этого триггера. Кроме того, по сигналу с выхода элемента И 35 через элементы

И 23 код адреса ВГ иэ регистра 21 передается в регистр 1. Если же сигнал на выходе "Равно" схемы 6 сформировался на этапе поиска верхней границы, т.е. когда триггер 45 находился в единичном состоянии, то по импульсу с выхода распределителя 18 через открытый элемент И 32 и элемент ИЛИ 39 .адрес из счетчика 4 пере-, дается через элементы ИЛИ 13 в регистр 21 в качестве верхней (последнего адреса) границы подмассива. Од1564648

10 новременно с этим по сигналу с выхода элемента И 32 через элемент ИЛИ 21 триггер 47 устанавливается в нулевое .состояние. Единичный сигнал с инверсного выхода триггера 47 поступает на выход 57 и используется в качестве сигнала готовности устройства к выдаче информации.

В. Код ключа считанной записи 10 меньше кода ключа искомой границы.

В данном случае на выходе "Меньше" схемы 6 формируется единичный сигнал.

Данным сигналом открывается элемент

И 10 и разрешается режим сложения s 15 счетчике 4. По импульсу с выхода распределителя 18 в счетчике 4 формируется сумма

1э

1и которая через элементы И 24 принимается в регистр 1 в качестве верхней границы для очередного цикла работы 40 устройства, Прием адреса производится по импульсу с выхода распределителя 18, поступающего через элементы

И l 1 и ИЛИ 15 на управляющие входы элементов И 24.

На первом этапе поиска нижней границы устройство работает следующим образом.

По импульсу с выхода распределителя 18 адрес

Г sr.+Hr. 1 о о

2 из сумматора 3 принимается в счетчик

4. Это обусловлено тем, что ВГО > НГ поэтому на выходе "Меньше схемы 7 сравнения устанавливается нулевой сигнал, открывающий по инверсному входу элемент И 29, выходом подклюР;, =Р;+l, которая через элементы ИЛИ группы 12 поступает в регистр 2 в качестве очередной нижней границы поиска по импульсу с выхода распределителя 18.

После этого поиск границы производит- 25 ся в очередном такте генератора )9.

С. Код ключа считанной записи больше кода ключа искомой границы.

В этом случае на выходе "Больше" схемы 6 формируется единичный сигнал, открывающий элемент И ll и устанавливающий режим вычитания счетчика 4.

По импульсу с выхода распределителя 18 в счетчике 4 формируется разность

35 ченного к входу разрешения записи счетчика 4.

По адресу P производится обраще1 ние к блоку 9 памяти, и считанная запись принимается в регистр 8 по импульсу с выхода распределителя 18, Код ключа считанной записи через открытые элементы И 27 подается на первый вход схемы 6 сравнения. На второй вход схемы 6 сравнения подается код ключа нижней границы из регистра

5 через открьггые элементы И ?5 единичным сигналом с инверсного выхода триггера 44.

Если ключи совпадают, то на выходах "Меньше" и "Больше" схемы 6 устанавливаются нулевые сигналы, блокирующие элементы И 10, 11 и запрещающие операции сложения н вычитания в счетчике 4. Поэтому импульсы с выхода распределителя 18 не изменяют содержимое счетчика 4 и в нем сохраняется значение адреса Р, а импульс с выхода распределителя 18 не изменяет состояния регистров 2 и 1, Единичным сигналом с выхода "Равно" схемы 6 через элемент ИЛИ 16 открывается элемент И 31. В очередном такте генератора 19 по импульсу на

abrx,.:e распределителя 18 адрес Р, принимается в регистр 17. Так как в регистрах 2 и 1 информация не изменилась, o адрес Р, повторно также принимается в счетчик 4.

По импульсу с выхода распределителя 18 триггер 45 переключается в единичное состояние, блокируя тем самым элемент И 31 по первому входу и открывая по первому входу элемент

И 32. Кроме того, на второй вход схемы 6 через элементы И 26, открытые теперь уже единичным сигналом с прямого выхода триггера 45, подается код ключа верхней границы из регистра 20, Таким образом, после окончания импульса с выхода распределителя 18 на первом входе схемы 6 присутствует код ключа считанной записи по адресу Р, а на втором входе — код ключа верхней границы. А так как ключ

НГ меньше ключа ВГ, то на выходе

"Меньше" схемы 6 формируется единичный сигнал. И в дальнейшем в соответствии с рассмотренным выше в и. В в регистре 2 фиксируется код адреса Р +1 по импульсу с выхода распределителя 18.

12 р» с

Р= — — =41

30 (1+1 t

ГЗ+4

Р= — — =3 (2

После этого снова появляется импульс на выходе распределителя 18, .IIo которому сформированный адрес где НГ=Р, +1 ВГ=ВГО, 1 принимается в счетчик 4.

В дальнейшем устройство .работает аналогично.

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

Пусть в массиве с НГ=1 и ВГ=9 необходимо определить нижнюю границу, начиная с которой ключи записей больше заданного.

На фиг, 2а показана условная структура массива с НГ=1 и ВГ=9, а внутри каждой ячейки указаны значения.ключей. Требуется определить адрес, начиная с которого все ключи больше Кл„=15.

В соответствии с описанным в первом цикле

Так как КЛ р КЛд (16 0 15), то:в ..счетчике 4 формируется код Р„-1=5--1= ,,=4, который передается в регистр 1 в качестве адреса верхней границы.

На втором цикле величина передается в счетчик 4.

Так как Кл 1)у Кл,„(10 <15), то в счетчике 4 формируется значение

P2+.1=2+1=3, которое в качестве нижней границы передается в регистр 2.

В третьем цикле величина передается в счетчик 4, Так как Кл аКл д (12 < 13), то в счетчике 4 образуется значение Р +1=

-з—

3+1=4, которое в качестве нижней границы поступает в регистр 2.

В течение этих трех циклов на выходе "Меньше" схемы 7 сравнения присутствует нулевой сигнал, которым элемент И 29 удерживается в открытом состоянии по инверсному входу.

В третьем цикле НГ=ВГ, на выходе

11 11

Равно схемы .7 сравнения формируется единичный сигнал, открывающий через элемент ИЛИ 37 элемент И 32 по четвертому входу. Но так как триггер 5 находится в нулевом состоянии, 1 емеНт И 32 заблокирован нулевым сигналом с прямого выхода этого триггера.

В четвертом цикле формируется адрес

Р= — — =4

15 который передается в счетчик 4.

Так как Кл i Кл „(14 415), то в счетчике 4 формируется значение адреса Р +1=4+1=5, которое принимается в качестве нижней границы в регистр

2. При этом оказывается, что ВГа НГ (10 (16), и на выходе "Меньше" схемы 7 устанавливается единичный сигнал, Данный сигнал блокирует по

25 инверсному входу элемент И 29, запрещающий прием в счетчик 4 очередного значения сохраняя в нем адрес Р„ =5.

Одновременно сигналом с выхода

"Меньше" схемы 7 через элемент ЕЛИ

16 открывается элемент И 31 по чет-. вертому входу. Так как этот элемент, кроме того, открыт по первому входу единичным сигналом с инверсного выхода триггера 45, а по второму— единичным сигналом с инверсного выл хода триггера 46„ то по импульсу с выхода распределителя IS поступающего через этот элемент И 3-1 и элемент ИЛИ 38 на синхровход регистра

17, производится прием в него адре45 са нижней границы подмассива Р+ =5.

После этого триггер 45 переключается в единичное состояние, обеспечивая поиск адреса верхней границы.

Одновременно с установкой в "1" триг50,1 гера 45 адрес ВГ„ =9 через элементы И 23 йередается в регистр 1.

Единичным сигналом с единичного выхода триггера 45 открь)ваются элементы И 26, и код ключа верхней границы поступает на второй вход схемы

6 сравнения. На первый вход схемы 6 после приема в регистр 8 по второму импульсу с выхода распределителя 18

Р (1=8.

)3 156464 записи из блока памяти 9 поступает код ключа Кл =)6 через элементы И 27.

Пусть требуется определить адрес верхней границы, ключ которой Кл=21 (фиг. 2б).

Так как Кл (Кл,„(16 (21), то на выходе "Меньше" схемы формируется единичный сигнал. При этом в счетчике 4 образуется адрес P,=5+)=6. Этот адрес принимается в регистр 2 в качестве нижней границы.

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

Так как Кл, с Кли (20 <21), то s счетчике 4 формируется адрес Р +1= 20

=7+1=8, передаваемый в регистр 2 в качестве нижней границы.

В следующем цикле

Так как Клр Кл), (22> 2)), то в счетчике 4 формируется адрес Рэ-)=8-1 7 ° который поступает в регистр 1 в качестве верхней границы. При этом 30 оказывается, что НГ=ВГ (7=7), в силу чего на выходе "Равно" схемы 7 формируется единичный сигнал, которым через элемент ИЛИ 37 открывается по четвертому входу элемент И 32. 35

Этот элемент открыт по первому и второму входам единичными сигналами с прямого выхода триггера 45 и инверсного выхода триггера 46 соответственно. Импульсом с выхода распреде- 40 лителя 18, поступающим через открытый элемент И 32 и элемент ИЛИ 39 на сннхровход регистра 21, адрес ВГ=7 принимается в регистр 21 через элементы ИЛИ 13. Одновременно импульсом с выхода элемента И 32 через элемент

ИЛИ 40.устанавливается в нулевое состояние триггер 47.

Таким образом, в регистрах 17 и

: 21 установлены граничные адреса под массива записей с ключами, лежащими в пределах от 9 до 15, т.е. А, =5, A sr

Если искомый подмассив данных отсутствует, что отражено в пп. 7 и

)2, то на выходе 59 формируется сигнал "Отсутствие подмассива".

8 14

Пусть клич НГ=25, ключ ВГ=26, т.е. ключи границ подмассива большие ключа ВГ (фиг. 2а).

Определение нижней границы производится аналогично рассмотренному с последовательным формированием адресов Р =5, Р<=7, Р =8, Р =9, заносимыми в качестве адреса нижней гра-, ницы в регистр 2. При НГ=9 Кл (Кл (24 (25). При этом в счетчике 4 формируется адрес Р +1=9+1=10, который передается в регистр 2. Так как ВГ в регистре 1 стала больше НГ в регистре 2 то на выходе "Больше" схемы 42 сравнения формируется единичный сигнал, поступающий на выход 59

"Отсутствие подмассива" и устанавливакщий через элемент ИЛИ 40 триггер

47 в нулевое состояние.

Пусть ключ НГ=б, ключ ВГ=7, т.е. ключи нижней и верхней границ подмассива меньше ключа НГ (фиг.2г). о

Определение нижней границы выполняется аналогично рассмотренному с последовательным формированием адреносимых качестве адреса верхней границы в регистр

В третьем цикле адреса в регистрах 2 и 1 становятся равными (НГ=ВГ=

=1), и на выходе "Равно" схемы 7 формируется единичный сигнал. Однако этот сигнал не влияет на состояние регистра 21, так как триггер 45 находится в нулевом состоянии, закрывая элемент И 32. При ВГ=1 Кл ) Кл и (8 6) ° При этом в счетчике 4 формируется адрес Р -1=1-1=0, который передается в регистр 1, Так как ВГ в регистре 1 стало меньше ВГ в регистре 2, то на выходе Меньше" схемы 43 сравнения формируется единичный сигнал, поступающий на выход 59 "Отсутствие подмассива" и устанавливающий триггер 47 в нулевое состояние.

Если требуется определить адрес только одной записи, то в регистры

5 и 20 принимаются одинаковые ключи.

При этом схема 44 сравнения формирует на выходе "Равно" единичный сигнал, по которому после определения адреса нижней границы одновременно с установкой в "1" триггера 45 сигналом с выхода элемента И 35 через открытый элемент И 33 и элемент ИЛИ 40 триггер 47 устанавливается в нулевое состояние.

64648 !

НГ+НГ

А = — — — =НГ

Таким образом, после окончания режима поиска в регистре 17 зафиксиро(, ван адрес нижней границы подмассива, а в регистре 21 — адрес верхней границы.

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

По входу 56 подается сигнал режима чтения, по которому триггер 46 устанавливается в единичное состояние, При этом блокируется воздействие сигнала начальной установки на состояния регистров 5, 20, 17 и 21 через элемент. — И 34. Кроме того, блокируется прохождение импульсов с выхода распределителя 18 для записи информации в регистры 17 и 21 через элемен ты И 31 и 32 соответственно, !

Нулевым сигналом с инверсного вы хода триггера 46 также блокируется прохождение кода ключа из регистра 8

,÷åðåç элементы И 27 на первый вход схемы 6 сравнения. Это дает возмож-! ность при наличии информации в ре гистре 5 поддерживать отличный от нуля код ключа через элементы И 25 на втором входе схемы 6 сравнения. При этом на выходе "Меньге" данной схемы постоянно на все время работы уст ройства в режиме чтения удерживается ,единичный сигнал. По этому сигналу счетчик 4 формирует очередной адрес чтения для блока 9 памяти, а через

,элементы И 10 и ИЛИ 14 обеспечивается

,запись очередного адреса в регистр ,:2 из счетчика 4. Этот же адрес пере дается и в регистр 1 по сигналу, поступающему через открытый элемент И 28 и элемент ИЛИ 15 на управляющие входы элементов И 24, Чтение информации выполняется следующим образом.

После подачи сигнала установки ре.жима по входу 56 в устройство поступает сигнал начальной установки по .входу 52. По этому сигналу адрес начала подмассива А „ (адрес нижней границы), предварительно считанный из регистра 17 по входу 49, по входам

51 и 50 одновременно принимается в регистры 1 и 2 соответственно. Затем в устройство подается по входу 58 сигнал пуска. По этому сигналу производится чтение записи из блока 9 памяти, которая поступает из регистра 8 на выход 60, По окончании чтения триггер 47 устанавливается в "0", Единичный сигнал с инверсного выхода этого триггера, поступающий на выход

57, используется в этом режиме в качестве сигнала готовности устройства к выдаче записи по сформированному очередному адресу. В устройство вновь поступает сигнал пуска по входу 58, В дальнейшем чтение информации и, соответственно, количество импульсов пуска определяется разностью значений адресов верхней и нижней границ в регистрах 17 и 21. После чтения записи по последнему адресу на выходе

59 формируется сигнал "Отсутствие подмассива", который в данном режиме означает завершение выдачи всех записей подмассива.

Чтение записей подмассива может производиться многократно с предварительной подготовкой устройства к работе в режиме чтения.

Рассмотрим работу устройства в режиме чтения записей.

После установки триггера 47 в единичное состояние открывается элемент И 30 и через некоторое время на выходе распределителя 18 появляется импульс. По этому импульсу через открытый по инверсному входу элемент

И 29 нулевым сигналом с выхода "МеньII ше схемы 7 в счетчик 4 принимается адрес по которому производится обращение к блоку 9 памяти.

Затем по второму импульсу с выхода распределителя 18 считанная запись принимается в регистр 8, передаваемая на выход 60.

Так как элементы И 27 закрыты нулевым сигналом с инверсного выхода триггера 46, то на первом входе схемы 6 нулевой код ключа, а на втором— отличный от нуля. Поэтому на выходе

t1 и

Меньше схемы сравнения формируется единичный сигнал, которым открыт элемент И 10, а в счетчике 4 разрешается режим сложения.

По третьему импульсу с выхода распределителя 18 в счетчике формируется код адреса А =А,+1, который поступает через элементы ИЛИ 12 в регистр

2 и через элементы .И 24:в регистр 1, Прием в регистр 2 этого адреса производится по четвертому импульсу с выхода распределителя 18, проходящему, 17

15 через элементы И 10 и ИЛИ 14 на синхровход .регистра. В регистр 1 этот же адрес принимается по тому же импульсу, проходящему через элемент

И 28, элемент ИЛИ 15 на управляющие входы элементов И 24. При этом на выходе "Меньше" схемы 7 удерживается нулевой сигнал, По четвертому импульсу с выхода распределителя 18, кроме того, с выхода И 28 через элемент ИЛИ 40 триггер 47 устанавливается. в нулевое состояние. Единичный сигнал с нулевого выхода триггера 47 . поступает на выход.51 и используется в качестве сигнала, разрешающего счи- тывание записи с выхода 60.

Чтение записи по очередному адресу производится по второму импульсу пуска, поступающему по входу

58. Работа устройства не отличается от описанной. Чтение записей .будет. производиться, пока текущий адрес не станет на единицу больше адреса верхней границы А>, находящегося в регистре 21.

Так, когда адрес обращения, принятый в счетчик 4 по импульсу с первого выхода распределителя 18, станет равным Азг, а по импульсу с третьегр выхода распространителя 18 увеличится на единицу и примется в регистры 2 и 1 по импульсу с выхода распределителя 18, то на выходе

"Меньше" схемы 42 сформируется единичный сигнал, поступающий на выход

59. Этот сигнал означает завершение считывания записей всего подмассива.

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

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

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

Устройство для поиска данных, содержащее регистр адреса верхней границы, регистр адреса нижней границы, сумматор, реверсивный счетчик, регистр ключа нижней границы, информационный вход которого является входом ключа нижней границы устройства, 64648 18

55 две схемы сравнения, регистр информации, блок памяти, два элемента И, две группы элементов ИЛИ, три элемента ИЛИ, выходной регистр адреса нижней границы, выход ко".орого является выходом адреса нижн=.: границы устройства, распределитель импульсов и генератор импульсов, причем выход регистра адреса верхней границы подключен к входу первого операнда первой схемы сравнения и входу первого слагаемого сумматора, вход второго слагаемого которого соединен с входом второго операнда первой схемы сравнения и выходом регистра адреса нижней границы, .разряды информационного входа которого соединены с выходами соответствующих элементов ИЛ1 первой группы, первые входы которых являются соответствующими разрядами входа адреса нижней границы устройства, i-й разряд выхода сумматора (i=2 3,..., и+1; n — разрядность адреса блока памяти) подключен к (1-1)-му разряду информационного входа реверсивного счетчика, разряды выхода ко-. торого соединены с соответствующими разрядами адресного входа блока памяти, с вторыми входами элементов

ИЛИ первой группы и первыми входами элементов ИЛИ второй группы, вторые входы которых являются соответствукщими разрядами входа адреса верхней границы устройства, установочный вход которого подключен к первому входу первого элемента ИЛИ, выход которого соединен с синхровходом регистра адреса нижней границы, выход "Меньше" первой схемы сравнения соединен с первым входом второго элемента ИЛИ, первый выход распределителя импульсов соединен с синхровходом регистра информации, информационный вход которого подключен к информационному выходу блока памяти, второй выход распределителя импульсов соединен со счетным входом реверсивного счетчика, третий выход распределителя импульсов подключен к первым входам первого и второго элементов И, выходы которых соединены с вторым входом первого и первым входом третьего элементов ИЛИ соответственно, суммирующий вход реверсивного счетчика соединен с вторым входом первого элемента И и с выходом "Меньше" второй схемы сравнения, выход "Больше" которой подключен к вычитающему входу реверсив20 вые входы которых соединены с инверсным выходом триггера управления и с третьим входом четвертого элемен5 та И выход которого соединен с перЭ вым входом пятого элемента ИЛИ, abr ход которого подключен к синхровходу выходного регистра адреса нижней границы, разряды информационного входа которого соединены с выходами соответствующих элементов ИЛИ третьей группы, первые входы которых подключены к первым входам соответствующих элементов И четвертой группы и к соответствующим разрядам выхода реверсивного счетчика, а вторые входы являются соответствующими разрядами входа адреса нижней границы устройства, установочньй вход уст20 ройства соединен с первым входом девятого элемента И, выход которого соединен с синхровходами регистров. ключей нижней и верхней границ, с нулевым входом триггера управления, 25 с вторым входом пятого элемента ИЛИ и с первым входом шестого элемента

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

19 1564648

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

"Меньше" первой схемы сравнения, выход "Равно" которой. соединен с первым входом. четвертого элемента ИЛИ, второй вход которого подключен к выходу "Равно" второй схемы сравнения и к второму входу второго элемента 45

ИЛИ, выход которого соединен с вторым входом четвертого элемента И и первым входом седьмого элемента И, выход которого подключен к первому входу восьмого элемента И, первым 50 входам элементов И первой группы и к единичному входу триггера управления, прямой выход которого соединен с вторым входом пятого элемента И и с первыми входами элементов И второй группы, выходы которых подключены к входам первого операнда второй схемы сравнения соответственно и к выходам элементов И третьей группы, перторой подключены к соответствующим разрядам выхода выходного регистра адреса нижней границы, выход

"Больше" третьей схемы сравнения и выход Меньше" четвертой схемы сравнения соединены соответственно с первым и вторым входами седьмого элемента ИЛИ, выход которого подключен к входу признака отсутствия подмассива устройства и к первому входу восьмого элемента ИЛИ, выход которого соединен с нулевым входом триггера пуска, выход первого элемента И соединен с первым входом десятого элемента И, выход которого подключен к второму входу третьего элемента ИЛИ и к второму входу восьмого элемента

ИЛИ, третий вход которого подключен к выходу восьмого элемента И, второй вход которого соединен с выходом

1564648

22. Р4*НГ,-I

Р, ° е

III ° ° а,. 6

° Ie: 9

Фмс е

Составитель С.Аверьянова

Редактор М.Келемеш Техред М.Ходанич . Корректор М. Самборская

Заказ 1162 Тираж 564 Подписно е

ВНИИПИ Государственного комитета по.изобретенням и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г.Ужгород, ул. Гагарина,101

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