Устройство для поиска данных Советский патент 1990 года по МПК G06F15/40 

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

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

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

Устройство содержит регистр 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 записи.

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

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

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

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

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

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

адрес блока памяти 1-го цикла устройства; адрес первой записи подмас- сива;

адрес последней записи под- массива;

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

ключ считанной записи из

блока памяти

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

Работа устройства в режиме поиска подмассива требуемых записей состоит в следующем.

В исходном состоянии распределитель 18 импульсов, регистры 8, 17 и 21, триггеры 47 и 45 установлены в состояние О. На входы 53 и 48 подаются коды ключей нижней и верхней границ искомого подмассива соответственно. На входы 51 и 50 поступают коды адресов верхней и нижней границ исходного массива. По входу 55 поступает импульс, устанавливающий триггер 46 в нулевое состояние, определяя режим поиска записей, ключи которых лежат в заданном интервале. Единичным сигналом с инверсного выхода триггера 46 открыт элемент И 34. После установки триггера 46 по входу 52 подается импульс, по которому разрешается запись исходной информации в регистры 5 и 20, в регистр 1 - через открытые элементы И ВВ, в регистр 2 - через элементы ИЛИ 12, и импульс на синхронизирующем входе через элемент ИЛИ 14 и аналогичным образом в регистры 17 и 21 через элементы ИЛИ 41, ИЛИ 13 и элементы И 34, ИЛИ 38 и ИЛИ 39 соответственно.

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

10

5646486

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

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

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

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

15

20

25

30

35

0

5

0

5

1.Ключ НГ равен ключу НГ0 и ключ ВГ равен ключу ВГ0. При этом в регистре 17 устанавливается адрес НГ0, а в регистре 21 - адрес ВГ0.

2.Ключ НГ равен ключу НГ0, а ключ ВГ больше ключа ВГ0. При этом

в регистре 17 формируется адрес НГ0, а в регистре 21 - адрес ВГ0.

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

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

5.Ключ ВГ меньше ключа ВГ0 адрес с ключом ВГ.

1о, но лежит внутри массива, а ключ ВГ больше ключа ВГ

о

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

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

7.Ключи НГ и ВГ больше ключа ВГ0. При этом в устройстве формируется сигнал Отсутствие подмассива.

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

а. в регистре 21 - адрес ВГ0 . | 9. Ключ НГ меньше ключа НГ0, а ключ ВГ больше ключа ВГ0. В данном случае в регистре 17 устанавливается адрес НГ0 , а в регистре 21 - адрес ВГ0 .

10.Ключ НГ меньше ключа НГ0, а ключ ВГ меньше ключа ВГ0, но больше ключа НГ0. При этом в регистре 17

iформируется адрес НГ0 , а в регистре 21 - адрес записи, лежащей внутри массива.

11.Ключ НГ меньше ключа НГ0, а ключ ВГ равен ключу НГ0 . В данном

10

15

20

25

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

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

i регистра 8 через открытые в дан- iM режиме элементы И 27.

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

А. Коды ключей совпадают.

В этом случае на выходе Равно схемы 6 формируется единичный сигнал которым через элемент ИЛИ 16 открывается по четвертому входу элемент И 31. Так как этот элемент открыт также по первому входу единичным си налом с инверсного выхода триггера 45, по второму входу - единичным си налом с инверсного выхода триггера

случае в регистрах 17 и 21 устанавли- 30 6 то по очередному имлульсу с выхода распределителя 18, поступающему через элементы И 3I и ИЛИ 38 на синхровход регистра 17, в него прини мается адрес первой (нижней) границы подмассива из счетчика 4 через элементы ИЛИ 41. Затем по импульсу выхода распределителя 18 через открытый элемент 35 И единичным сигналом с выхода Равно схемы 6 триггер 45 устанавливается в единичное состояние. При этом нулевым сигналом с инверсного выхода триггера 45 закрываются элементы И 31 и 25, а открываются элементы И 32 и 26 единичным сигналом с прямого выхода этого триггера. Кроме того, по сигналу с выхода элемента И 35 через элементы И 23 код адреса ВГ0 из регистра 23 передается в регистр 1. Если же сигнал на выходе Равно схемы 6 сформировался на этапе поиска верхней границы, т„е. когда триггер 45 находился в единичном состоянии, то по импульсу с выхода распределителя 18 через открытый элемент и элемент ИЛИ 39 адрес из счетчика 4 nepe дается через элементы ИЛИ 13 в регистр 21 в качестве верхней (последнего адреса) границы подмассива. Одвается адрес НГ0.

12. Ключи НГ и ВГ меньше ключа НГ0. В этом случае в устройстве формируется сигнал Отсутствие подмассива.

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

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

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

Гвг«+нг0

р г; I - «.л.™--,-

2

где - ближайшее целое, меньшее

либо равное х.

По этому адресу производится обращение в блок 9 памяти, и считанная

5

0

5

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

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

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

А. Коды ключей совпадают.

В этом случае на выходе Равно схемы 6 формируется единичный сигнал, которым через элемент ИЛИ 16 открывается по четвертому входу элемент И 31. Так как этот элемент открыт также по первому входу единичным сигналом с инверсного выхода триггера 45, по второму входу - единичным сигналом с инверсного выхода триггера

0 6 то по очередному имлульсу с вы5

0

5

0

5

хода распределителя 18, поступающему через элементы И 3I и ИЛИ 38 на синхровход регистра 17, в него принимается адрес первой (нижней) границы подмассива из счетчика 4 через элементы ИЛИ 41. Затем по импульсу выхода распределителя 18 через открытый элемент 35 И единичным сигналом с выхода Равно схемы 6 триггер 45 устанавливается в единичное состояние. При этом нулевым сигналом с инверсного выхода триггера 45 закрываются элементы И 31 и 25, а открываются элементы И 32 и 26 единичным сигналом с прямого выхода этого триггера. Кроме того, по сигналу с выхода элемента И 35 через элементы И 23 код адреса ВГ0 из регистра 23 передается в регистр 1. Если же сигнал на выходе Равно схемы 6 сформировался на этапе поиска верхней границы, т„е. когда триггер 45 находился в единичном состоянии, то по импульсу с выхода распределителя 18 через открытый элемент и элемент ИЛИ 39 адрес из счетчика 4 nepe-j дается через элементы ИЛИ 13 в регистр 21 в качестве верхней (последнего адреса) границы подмассива. Одновременно с этим по сигналу с выхода элемента И 32 через элемент ИЛИ 21 триггер 47 устанавливается в нулевое состояние . Единичный сигнал с инверс- ного выхода триггера 47 поступает на выход 57 и используется в качестве сигнала готовности устройства к выдаче информации.

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

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

HI

Р;+1,

которая через элементы ИЛИ группы 12 поступает в регистр 2 в качестве очередной нижней границы поиска по им - пульсу с выхода распределителя 18. После этого поиск границы производит- ся в очередном такте генератора 19.

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

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

Р,

iti

-Р.-1.

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

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

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

,- 2-г°-Р-

из сумматора 3 принимается в счетчик 4. Это обусловлено тем, что , поэтому на выходе Меньше схемы 7 сравнения устанавливается нулевой сигнал, открывающий по инверсному входу элемент И 29, выходом подклюг

ю

15

20

25

зо

35

дд 45

0

„

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

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

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

Единичным сигналом с выхода Равно гхемы 6 через элемент ИЛИ 16 открывается элемент И 31. В очередном такте генератора 19 по импульсу на выхо е распределителя 18 адрес Р, принимается в регистр 17. Так как в регистрах 2 и 1 информация не изменилась, то адрес Р повторно также принимается в счетчик 4.

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

Таким образом, после окончания импульса с выхода распределителя 18 на первом входе схемы 6 присутствует код ключа считанной записи по адресу Р , а на втором входе - код ключа верхней границы. А так как ключ НГ меньше ключа ВГ0, то на выходе Меньше схемы 6 формируется единичный сигнал. И в дальнейшем в соответствии с рассмотренным выше в п. В в регистре 2 фиксируется код адреса Р + 1 по импульсу с выхода распределителя 18.

После этого снова появляется импульс на выходе распределителя 18, по которому сформированной адрес

ГНГ+ВГ 1

где ,+1; , принимается в счетчик 4.

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

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

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

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

больше Кл 15.

п

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

.

L L J

Так как КЛ ъ КПИ (16 15), то в счетчике 4 формируется код 4, который передается в регистр 1 в качестве адреса верхней границы.

На втором цикле величина

v Ґ передается в счетчик 4.

Так как Кл, Кли (10 15), то в счетчике 4 формируется значение , которое в качестве нижней границы передается в регистр 2.

В третьем цикле величина

v№

передается в счетчик 4.

Так как (), то в счетчике 4 образуется значение Pa+J , которое в качестве нижней границы поступает в регистр 2.

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

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

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

т, Г4- ,

P4,rJ,4

0

5

0

5

0

0

5

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

Так как Кл Кл fl (14 15), то в счетчике 4 формируется значение адреса которое принимается в качестве нижней границы в регистр 2. При этом оказывается, что (), и на выходе Меньше схемы 7 устанавливается единичный сигнал „ Данный сигнал блокирует по инверсному вхоцу элемент И 29, запрещающий прием в счетчик 4 очередного значения

Р . 4 5 L 2 J

сохраняя в нем адрес .5.

Одновременно сигналом с выхода Меньше схемы 7 через эле-мент ИЛИ 16 открывается элемент И 31 по четвертому входу. Так как этот элемент, кроме того, открыт по первому входу единичным сигналом с инверсного выхода триггера 45, а по второму - единичным сигналом с инверсного выхода триггера 46, то по импульсу с выхода распределителя 18, поступающего через этот элемент И 3-1 и элемент ИЛИ 38 на синхровход регистра 17, производится прием в него адреса нижней границы подмассива Р. 5.

После этого триггер 45 переключается в единичное состояние, обеспечивая поиск адреса верхней границы. Одновременно с установкой в 1 триг- Iгера 45 адрес ВГ0 9 через элементы И 23 передается в регистр 1.

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

13

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

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

Так как (), то на выходе Меньше схемы формируется единичный сигнал. При этом в счетчике 4 образуется адрес Р,. Этот адрес принимается в регистр 2 в качестве нижней границы.

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

v т

15

7,

поступающий в счетчик 4.

(20521), то

V , передаваемый в регистр 2 в

качестве нижней границы. В следующем цикле

Так как Кгц Кли счетчике 4 формируется адрес Pxi + l

-8 L-2-J-8.

Так как (), то в счетчике 4 формируется адрес P-J-1 8-1 7, оторый поступает в регистр 1 в качестве верхней границы. При этом оказывается, что (), в сиу чего на выходе Равно схемы 7 ормируется единичный сигнал, которым через элемент ИЛИ 37 открывается по четвертому входу элемент И 32. Этот элемент открыт по первому и второму входам единичными сигналами с прямого выхода триггера 45 и инверсного выхода триггера 46 соответственно. Импульсом с выхода распределителя 18, поступающим через открытый элемент И 32 и элемент ИЛИ 39 на синхровход регистра 21, адрес принимается в регистр 21 через элементы ИЛИ 13. Одновременно импульсом с выхода элемента И 32 через элемент ИЛИ 40 устанавливается в нулевое сосояние триггер 47.

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

в пределах от 9 А

до 15, т.е. А 5,

нг

.

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

64648

10

15

20

25

30

35

40

45

14

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

Определение нижней границы производится аналогично рассмотренному с последовательным формированием адресов Р,,5, , , , заносимыми в качестве адреса нижней границы в регистр 2. При (). При этом в счетчике 4 формируется адрес , который передается в регистр 2. Так как ВГ в регистре 1 стала больше НГ в регистре 2, то на выходе Больше схемы 42 сравнения формируется единичный сигнал, поступающий на выход 59 Отсутствие подмассива и устанавливающий через элемент ИЛИ 40 триггер 47 в нулевое состояние.

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

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

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

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

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

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

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

Нулевым сигналом с инверсного выхода триггера 46 также блокируется прохождение кода ключа из регистра 8 iчерез элементы И 27 на первый вход 1 схемы 6 сравнения. Это дает возмож- jность при наличии информации в регистре 5 поддерживать отличный от нуля код ключа через элементы И 25 н втором входе схемы 6 сравнения. При этом на выходе Меньгс данной схемы постоянно на все время работы устройства в режиме чтения удерживается единичный сигнал. По этому сигналу счетчик 4 формирует очередной адрес чтения для блока 9 памяти, а через элементы И 10 и ИЛИ 14 обеспечиваетс запись очередного адреса в регистр 2 из счетчика 4. Этот же адрес передается и в регистр 1 по сигналу, поступающему через открытый элемент И 28 и элемент ИЛИ 15 на управляющие входы элементов И 24.

Чтение информации выполняется следующим образом.

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

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

Чтение записей подмассива может

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

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

5 После установки триггера 47 в

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

0 открытый по инверсному входу элемент И 29 нулевым сигналом с выхода Меньше схемы 7 в счетчик 4 принимается адрес

35

А

нг+нг

нг,

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

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

Так как элементы И 27 закрыты нулевым сигналом с инверсного выхода

Изобретение относится к вычислительной технике и может быть использовано в системах управления базами данных. Цель изобретения - расширение функциональных возможностей устройства за счет возможности определения граничных адресов подмассива данных в заданном интервале значений ключей записи. Это достигается тем, что устройство содержит регистр 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 ил.

После подачи сигнала установки ре- 45 триггера 46, то на первом входе схежима по входу 56 в устройство поступает сигнал начальной установки по входу 52. По этому сигналу адрес начала подмассива Анг(адрес нижней границы) , предварительно считанный из 50 регистра 17 по входу 49, по входам 51 и 50 одновременно принимается в регистры 1 и 2 соответственно. Затем в устройство подается по входу 58 сигнал пуска. По этому сигналу произ- 55 водится чтение записи из блока 9 памяти, которая поступает из регистра 8 на выход 60. По окончании чтения триггер 47 устанавливается в О.

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

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

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

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

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

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

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

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

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

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

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

0

5

0

5

0

5

0

5

0

5

две схемы сравнения, регистр информации, блок памяти, два элемента И, две группы элементов ЮТ-1, три элемента ИЛИ, выходной регистр адреса нижней границы, выход которого является выходом адреса нижие. границы устройства, распределитель импульсов и генератор импульсов, причем выход регистра адреса верхней границы подключен к входу первого операнда первой схемы сравнения и входу первого слагаемого сумматора, вход второго слагаемого которого соединен с входом второго операнда первой схемы сравнения и выходом регистра адреса нижней границы, разряды информационного входа которого соединены с выходами соответствующих элементов ИЛИ первой группы, первые входы которых являются соответствующими разрядами входа адреса нижней границы устройства, 1-й разряд выхода сумматора (,3,..., n+1; n - разрядность адреса блока памяти) подключен к (1-1)-му разряду информационного входа реверсивного счетчика, разряды выхода которого соединены с соответствующими разрядами адресного входа блока памяти, с вторыми входами элементов ИЛИ первой группы и первыми входами элементов ИЛИ второй группы, вторые входы которых являются соответству- ющими разрядами входа адреса верхней границы устройства, установочный вход которого подключен к первому входу первого элемента ИЛИ, выход которого соединен с синхровходом регистра адреса нижней границы, выход Меньше первой схемы сравнения соединен с первым входом второго элемента ИЛИ, первый выход распределителя импульсов соединен с синхровходом регистра информации, информационный вход которого подключен к информационному выходу блока памяти, второй выход распределителя импульсов соединен со счетным входом реверсивного счетчика, третий выход распределителя импульсов подключен к первым входам первого и второго элементов И, выходы которых соединены с вторым входом первого и первым входом третьего элементов ИЛИ соответственно, суммирующий вход реверсивного счетчика соединен с вторым входом первого элемента И и с выходом Меньше второй схемы сравнения, выход Больше которой подключен к вычитающему входу реверсив-

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

5

0

5

0

5

0

5

0

5

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

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

ИГ., 1

Р.

Р4.3

N4

V 5

t

Г

&

(Г, 9

)

О

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

t)

)