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

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано в системах управления базами данных. Цель изобретения - повышение быстродействия за счет предварительного анализа соотношения ключей границ исходного массива и искомого подмассива. Новым в устройстве является использование блока анализа, содержащего четыре триггера , две схемы сравнения, два блока элементов И, девять элементов И, элемент ИЛИ и четыре элемента задержки, и его связей с остальными элементами схемы устройства. Устройство работает в режиме поиска адресов подмассива данных, записи которых лежат в заданном интервале значений идентификаторов (ключей) записей, и в режиме чтения найденных записей. Режим поИзобретение относится к автоматике и вычислительной технике, может быть использовано в системах управления базами данных и является усовершенствованием устройства по авт. св. № 1564648. Целью изобретения является повышение быстродействия устройства за счет предварительного анализа соотношения иска начинается с предварительного анализа соотношения ключей искомого подмассива и исходного массива. На основании сигналов соотношения этих ключей формируются граничные адреса подмассива либо сигнала об отсутствии записей, либо определяется режим поиска одной или обеих его границ. Поиск адресов производится делением области поиска в каждом цикле работы устройства примерно вдвое. Область поиска определяется на основе сравнения заданного и считанного ключей. При необходимости поиска обеих границ вначале определяется адрес первой записи (нижняя граница), а затем - адрес последней записи (верхняя граница) подмассива. При чтении информации предварительно в регистры адресов нижней и верхней границ массива заносится адрес записи подмассива из выходного регистра адреса нижней границы . По сигналам пуска производится обращение к памяти, чтение данных в регистр информации и формирование очередного адреса записи. Если этот адрес превышает адрес верхней границы подмассива, в устройстве формируется сигнал об отсутствии подмассива, по которому завершается считывание записей. 2 табл., 3 ил. ключей границ исходного массива и искомого подмассива. На фиг. 1 показана структурная схема устройства; на фиг. 2 - функциональная схема блока анализа; на фиг. 3 - примеры размещения массива информации в блоке памяти. Устройство содержит регистр 1 адреса верхней границы, регистр 2 адреса нижней Ј О ел 00 VI о ю

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

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

РЕСПУБЛИК (zg)s G 06 F 15/40

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

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

ПРИ ГКНТ СССР

50Е40

ПАТЕЯТл - Т

- -1БЛИ

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) 1564648 (21) 4711757/24 (22) 27.06.89 (46) 23,06.91. Бюл. М 23 (72) В,Г. Попов и С.А. Удинцев (53) 681.325 (088,8) (56) Авторское свидетельство СССР

М 1564648, кл. G 05 F 15/40, 15.08.88, (54) УСТРОЙСТВО ДЛЯ ПОИСКА ДАННЫХ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в системах управления базами данных, Цель изобретения — повышение быстродействия за счет предварительного анализа соотношения ключей границ исходного массива и искомого подмассива. Новым в устройстве является использование блока анализа, содержащего четыре триггера, двесхемы сравнения, два блока элементов И, девять элементов И, элемент ИЛИ и четыре элемента задержки, и его связей с остальными элементами схемы устройства.

Устройство работает в режиме поиска адресов подмассива данных, записи которых лежат в заданном интервале значений идентификаторов (ключей) записей, и в режиме чтения найденных записей. Режим поИзобретение относится к автоматике и вычислительной технике, может быть использовано в системах управления базами данных и является усовершенствованием устройства по авт. св. М 1564648.

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

„„Я „„1658170 А2 иска начинается с предварительного анализа соотношения ключей искомого подмассива и исходного массива. На основании сигналов соотношения этих ключей формируются граничные адреса подмассива либо сигнала об отсутствии записей, либо определяется режим поиска одной или обеих его границ. Поиск адресов производится делением области поиска в каждом цикле работы устройства примерно вдвое. Область поиска определяется на основе сравнения заданного и считанного ключей, При необходимости поиска обеих границ вначале определяется адрес первой записи (нижняя граница), а затем — адрес последней записи (верхняя граница) подмассива, При чтении информации предварительно в регистры адресов нижней и верхней границ массива заносится адрес записи подмассива из выходного регистра адреса нижней границы. По сигналам пуска производится обращение к памяти, чтение данных в регистр информации и формирование очередного адреса записи. Если этот адрес превышает адрес верхней границы подмассива, в устройстве формируется сигнал об отсутствии подмассива, по которому завершается считывание записей. 2 табл., 3 ил. ключей границ исходного массива и искомого подмассива, На фиг. 1 показана структурная схема устройства; на фиг. 2 — функциональная схема блока анализа; на фиг. 3 — примеры размещения массива информации в блоке памяти.

Устройство содержит регистр 1 адреса верхней границы, регистр 2 адреса нижней

1658170 границы, сумматор 3, реверсивный счетчик

4, регистр 5 ключа нижней границы, две схемы б и 7 сравнения, регистр 8 инфоома ции, блок 9 памяти, два элемента И 10 и 11, две группы элементов ИЛИ 12 и 13, первый

14, второй 15 и третий 16 элементы ИЛИ, выходной регистр 17 адреса нижней границы, распределитель 18 импульсов, г нератор 19 импульсов, регистр 20 ключа верхней границы, выходной регистр 21 адреса верхней границы, шесть групп элементов И 22

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

73, шестой 74 и седьмой 75 выходы управления блока анализа.

Блок 61 анализа содержит (фиг, 2) первый 76 и второй 77 три»еры управления, триггер 78 нижней границы, три<: ер 79 верхней границы, первую 80 и вторуго 81 схемы сравнения, первый 82 и второй 83 блоки элементов И, первый 84, второй 85, третий

86, че1верть«< 87 и пятый 38 элем"><ть< И, элемент ИЛИ 89, шестой 90, .едь><ой 91, восьмой 92 и девятыи 93 элементы И. первый 94, второй 95, 1регий 96 и <етвегрть<й 97 элементы задержки.

Рассмотрим принципы пес<роения и работу устройства.

В блоке 9 памяти разме<цен массив, каждая ячейка которого состоит из служебного и информационно о полей. Служебное поле используется длл указания кода ключа (идентифика< ора). а информациг<><><ое — для размещения смыслового содег.»:-<ния ицентифицируе>лой части записи. Зэ <> си набора данных отсортирова«ы по ><варя Tr >« â эна5

55 чений ключей, Это означает, что если i-я запись размещена по k-му адресу, то (I >

1) -я запись хранится по (k + 1)-му адресу, причем ключ (1 <- 1)-й записи больше ключа

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

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

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

При таком поиске размер области поиска в результате каждой проверки сокрацаетсь примерно вдвое.

Введем следующие обозначения: Нго— нижняя граница (адрес первой записи исходного массива); Вà — верхняя граница (адрес последней записи исходного массива); Р; — адрес блока памяти i — го цикла устройства; Л„, -- адрес первой записи

<од>лассива; A><> — адрес последней записи подмассива; Кл« -- ключ исходной записи подмассива; Кл, — ключ считанной записи иэ блока памяти.

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

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

В исходном состоянии распределитель

18 импульсов, регистры 8, 17, 21, счетчик 4, триггеры 47, 45, 76 устанавливают в состояние 0 (не показано).

На входы 48 и 53 подаются коды ключей нижней и верхней границ искомого подмассива соответственно, На входы 51 и 50 поступают коды адресов верхней и нижней границ исходного массива.

По входу 35 поступает импульс, по которому триггер 46 устанавливается в нулевое состояние, определяя режим поиска записей, ключи которых лежат в заданном интервале, Единичным сигналом с инверсного выхода

< риг ера 46 открыты элементы И 27, 31, 32, 34, а в блоке 61 анализа — элемент И 84.

Кроме того, по импульсу с входа 55 в бло е 61 устанавливаются в нулевое состо1658170

30

55 яние триггер 88, а в единичное — триггер 76, единичным сигналом с прямого выхода которого блокируется по инверсному входу элемент И 30 и открываются по первым управляющим входам блоки элементов И 82 и

83.

Нулевым сигналом с инверсного выхода триггера 47 блокируются элементы И 85, 91 и 93.

После установки триггеров 46 и 77 по входу 52 подается импульс, по которому разрешается поступление исходной информации в регистры 5 и 20, в триггер 1 через открытые элементы И 22, в регистр 2 через элемент ИЛИ 12 и по импульсу на синхровходе через элемент ИЛИ 14 и аналогичным образом в регистры 17 и 21 через элементы

ИЛИ 41 и 13 и элементы И 34, ИЛИ 38 и 39 соответственно.

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

Кроме того, импульс пуска через открытый элемент И 84 устанавливает в единичное состояние триггеры 78 и 79.

Единичное состояние триггера 76 Определяет вначале режим предварительного анализа соотношений ключей исходного массива и заданного интервала значений ключей подмассива, Этот режим необходим для исключения в ряде случаев непроизводительных затрат времени при Определении адресов блока памяти, где размещен искомый подмассив, В дальнейшем при необходимости Организуется работа устройства по отысканию одной либо обеих границ искомого подмассива, При отыскании обеих границ работа устройства состоит из двух этапов, каждый из которых выполняется одинаково.

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

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

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

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

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

3. Ключ НГ равен ключу НГ,, а ключ ВГ меньше ключа ВГо. В этом случае в регистре

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

5, Ключ НГ меньше ключа ВГо, но адрес с ключом ВГо лежит внутри массива, а ключ

ВГ больше ключа ВГо, При этом в регистре

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

В Го.

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

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

10. Ключ НГ меньше ключа НГо, а ключ

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

11, Ключ Н Г меньше ключа Н Го, а ключ

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

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

12. Ключ НГ меньше ключа НГо, а ключ

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

Н Го.

1658170

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

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

Из табл. 1 видно, что для определения режима поиска на этапе предварительного анализа необходимо производить дважды обращение к блоку 9 памяти. При первом . обращении по адресу НГо производится сравнение ключа к нижней границы исходного массива с искомым ключом первой записи подмассива, а при втором — сравнение ключа верхней границы по адресу ВГО с искомым ключом последней записи подмассива. Затем на основании совместного сопоставления результатов анализа в регистрах 17 и 21 устанавливаются адреса НГр, ВГо, либо производится назначение устройства для режима поиска соответс1вующих границ, либо формируется сигнал "Отсутс гвие подмассива".

Работа устройства на этапе предварительного анализа состоит в следующем, Так как блок элементов И 83 открыпг по двул; управляющим входам единичными сигналами - прямо о выхода триггера 76 и инверсного выхода триггера 77, то адрес верхней границы с выхода регистра 1 через этот блок элементов И 83 и МОНТАЖНОЕ

ИЛИ поступает на адресный вход блока 9 памяти. Считанная информация поступает на адресный вход блока 9 памяти. Считанная информация — ключ ВГ с выходов блока

9 — поступает на первые входы схем 80 и 81 сравнения, на вторых входах которых находятся ключи нижней и верхней границ искомого подмассива соответственно.

В зависимости от соотношения ключей на выходах схем 80 и 81 сравнения формируются сигналы, определяющие режим работы устройства при поиске верхней границы подмассива, 1, КлВГО=- КлНГ, что соответствует шестой строке табл, 1, При этом на выкоде "Равно" схемы 80 сравнения формируется единичный сигнал, открывающий элемент И

92.

Через некоторое время, определяемое элементом 94 задержки и равное времени переходных процессов в блоке 9 памяти и схеме 80 сравнения, задержанным импульсом пуска через элемент И 92 и элелент

ИЛИ 38 по синхровходу регистра 17 обеспечивается записЬ в него адреса В 1 > с выходов блока элементов И 83 через МОНТАЖНОЕ

ИЛИ и элементы ИЛИ 4 . В регистре 21 сохраняется значенье адреса ВГо.

Одновременно сигналом с выхода элемента И 92 через элементы ИЛИ 89 и 50 устанавливается в нулевое состояние триггер 47, единичный сигнал с инверсного выхода которого поступает на выход 57 в качестве сигнала готовности устройства к режиму считывания. Одновременно этим единичным сигналом по инверсным входам блокируются элементы И 85, 91 и 93, чем исключается воздействие задержанного импульса пуска с выхода элемента 95 задержки на состояние элементов схемы устройства с выходов 72, 83 и 75 блока 61 анализа.

2. Кл В Г, < Кл Н г, что соответствует седьмой строке табл, 1. При этом на выходе

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

И 85 и 90. Задержанный импульс с выхода элемента 95 задержки через открытый элемент И 90 и элементы ИЛИ 36 и 40 устанавливает триггер 47 в нулевое состояние и поступает на выход 59 устройства в качестве сигнала "Отсутствие подмассива".

3. КлВГ, > КлВГ, что соответствует третьей, восьмой и одиннадцатой строкам табл. 1.

Гри этом нэ выходе "Больше" схемы 81 формируется единичный сигнал, открывающий элементы И 86 и 91. Так как триггер 47 находится в единичном состоянии, то нулевым сигналом с его инверсного выхода элемент И 91 открыт также и по инверсному входу. Задержанным импульсом поиска с выхода элемента 94 задержки триггер 79 устанавливается в нулевое состояние через элемент И 86, что свидетельствует о необходимости поиска верхней границы.

4. Если же КлВГо КлВГ, то на выходе Больше" схемы 81 сравнения устанавливается нулевой сигнал, а триггер 79 при этом удерживается в единичном состоянии, что означает необходимость сохранения в регистре 21 адреса верхней границы (первая, вторая, четвертая, пятая, шестая, девятая и десятая строки табл. 1).

С r.ûõîäà элемента 94 задержки. кроме то о, задержанным импульсом пуска устанаьливэегся в единичное состояние триггер

: 7, определяя анализ соотношения ключей нижней границы исходного массива с ключал1и искомого подмассива, Результаты анализа будут учтены, если триггер 47 удерживается в единичном состоянии, т. е. когда при сравнении определен режим работы устройства по поиску верхней границы искомого подмассива, Установкой ь единичное состояние риггерэ 47 обеспечивается передача адрес: нижней границы массива с выхода реги1658170

10 стра 2 через открытый блок элементов И 82 и МОНТАЖНОЕ ИЛИ на адресный вход блока 9 памяти.

Считанная информация -- ключ НГ с выходов блока 9 памяти — поступает на первые входы схем 80 и 81 сравнения, на вторых входах которых находятся ключи нижней и верхней границ соответственно искомого подмассива.

В зависимости от соотношения ключей на входах схем 80 и 81 сравнения формируются сигналы, определяющие режим работы устройства при поиске нижней границы искомого подмассива, 5. КлНГО = КлВГ, что соответствует двенадцатой строке табл, 1.

При этом на выходе "Равно" схемы 81 сравнения формируется единичный сигнал, открывающий элемент И 93, Задержанным импульсом пуска с выхода элемента 95 задержки через время, равное времени переходных процессов в блоке 9 памяти и схеме

81 сравнения, через элемент ИЛИ 39 по синхровходу регистра 2 1 обеспечивается запись в него адреса НГо с выходов блока элементов И 82 через МОНТАЖНОЕ ИЛИ и элементы ИЛИ 13.

B регистре 17 сохраняется значение адреса НГО.

Одновременно этим же сигналом через элементы ИЛИ 89 и 40 устанавливается в нулевое состояние триггер 47, единичный сигнал с инверсного выхода которого поступает на выход 57 в качестве сигнала готовности устройства к режиму считывания.

6. КлНГО > КлВГ, что соответствует тринадцатой строке табл. 1.

При этом на выходе Больше" схемы 81 сравнения формируется единичный сигнал, открывающий элемент И 91, задержанным импульсом пуска с выхода элемента 95 задержки через открытый элемент И 91 и элементы ИЛИ 36 и 40 устанавливает триггер

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

7. КлНГо < КлНГ, что соответствует четвертой, пятой и восьмой строкам табл. 1.

При этом на выходе "Меньше" схемы 80 сравнения формируется единичный сигнал, открывающий элемент И 85, через который задержанным импульсом с выхода элемента 95 задержки устанавливается в нулевое состояние триггер 78, что свидетельствует о необходимости поиска нижней границы подмассива.

8. Если же Кл Н Г„ Кл Н Г, то на выходе

"Меньше" схемы 80 сравнения устанавливается нулевой сигнал, закрывающий элемент

И 85, чем триггер 78 удерживается в единичтриггере 47.

55 ном состоянии. Это означает, что нет необходимости поиска нижней границы, т. B. в регистре 17 сохраняется адрес нижней границы (первая, вторая и третья, девятая, десятая и одиннадцатье строки табл. 1).

В результате анализа соотношения ключей исходного массива и искомого подмассива триггеры 78 и 79 могут находиться либо в нулевых, либо в единичных состояниях, определяя в конечном итоге режимы работы устройства, что показано в табл. 2, В соответствии с табл. 2 завершение работы блока 61 производится следующим образом, Задержанным импульсом пуска с выхода элемента 96 задержки через открытый элемент И 87 единичным сигналом с единичного выхода триггера 78 и МОНТАЖНОЕ

ИЛИ триггер 45 устанавливается в единичное состояние. Это означает, что устройство принудительно переводится в режим поиска верхней границы, так как нижняя граница уже по результатам работы блока 61 находится в регистре 17, Если только триггер 79 находится в единичном состоянии, то единичным сигналом с его единичного выхода блокируется по инверсному входу элемент И 32 для исключения влияния импульса с выхода распределителя 18 и через МОНТАЖНОЕ

ИЛИ с выходом схемы 44 сравнения открывается по второму входу элемент И 33. Это необходимо для того, чтобы после определения нижней границы и размещения ее в регистре 17 завершить работу устройства, так как верхняя граница уже находится в регистре 21, Если оба триггера 78 и 79 находятся в единичном состоянии, означающем наличие нижней и верхней границ в регистрах 17 и 21 соответственно, то импульсом с выхода элемента 96 задержки через открытый элемент И BB и элементы ИЛИ 89 и 40 устанавливается в нулевое состояние триггер 47.

Время задержки элементом 96 задержки определяется временем переходных процессов в элементах И 85 (86) и триггерах 78 (79).

Если оба триггера 78 и 79 находятся в нулевых состояниях, то устройство обеспечивает вначале поиск нижней, а затем верхней границ, Кроме того, импульсом с выхода элемента 96 задержки через элемент 97 задержки устанавливается в нулевое состояние триггер 76.

Время задержки элемента 97 задержки определяется временем переходных процессов в элементах И 88, ИЛИ 89 и 40 и

1658170

После установки триггера 76 в нулевое состояние нулевым сигналом с его прямого выхода открывается по инверсному входу элемент И 30.

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

78 и 79 находятся в нулевых состояниях, 10

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

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

В Го + Н Го

1 2 25 где (Х) — ближайшее целое, меньшее либо равное Х, По э1ому адресу производится обращение в блок 9 памяти, и считанная запись с ключом Кл принимается в регистр 8 по ето- 30 рому импульсу с выхода распределителя 18, поступающему на синхровход регистра 8.

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

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

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

В этом случае на выходе "Равно" схемы б формируется единичный сигнал. которым через элемент ИЛИ 16 открывается по четвертому входу элемент И 31. Так как этоэлемент открыт также по первому входу еди- 50 ничным сигналом с инверсного выхода тригера 45 по второму входу единичным сигналом с инверсного выхода триггера 46, то по очередному импульсу с выхода распределителя 18, поступающему через эле- 55 менты И 31 и ИЛИ 38 на синхровход регистра

17, в него принимается адрес первой (нижней) границы подмассива из счетчика 4 через элемент ИЛИ 14. Затем по импульсу выхода распределителя 18 через открытый элемент И 35 единичным сигналом с выхода

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

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

ИЛИ 21 три гер 47 устанавливается в нулевое состояние. Единичный сигнал с инверсного выхода триггера 47 поступает на выход

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

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

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

18 в счетчике 4 формируется сумма

Р +1 = Р + 1, которая через элементы

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

После этого поиска границы производи1ся в очередном такте генератора 19, С. Код ключа считанной записи больше кода ключа искомой границы.

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

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

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

1658170

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

Вl +НГ

18 адрес Pl = — - из сумма. ора

3 принимается в счетчик 4. Это обусловлено тем, что ВГ > Hl n поэтому на выходе

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

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

Если ключи совпадают, то на выходах

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

8 очередном такте генератора 19 по импульсу на выходе распределителя 18 адрес

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

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

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

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

Таким образом, после окончания импульса с выхода распределителя 18 на первом входе схемы 6 присутствует код ключа считанной записи по адрес, Р1, а на втором входе — код ключа верхней границы, а так как ключ НГ меньше ключа ВГ, то на выходе

"Меньше" схемы 6 формируется единичный сигнал. И е дальнейш"M (в соответствии с рассмотренным пунктом В) в регистре 2 фиксируется код адреса Р1 + 1 по импульсу с выхода распределителя 18, После этого снова появляется импульс нэ выходе распределителя 18, по которому сфорНГ+ВГ мирова н н ы и адрес Pz—

5 где НГ = Pi + 1, ВГ = ВГр. принимается в счетчик 4.

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

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

Рассмотрим работу устройства, когда в

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

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

Так как КлНГО < КлНГ (8 < 15), то по завершении предварительного этапа триг25 гер 78 оказывается в нулевом состоянии, определяя тем самым режим поиска нижней

Границы.

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

30 1+9

Так как Клз > Кли (16 > 15), то в счетчике

4 формируется значение Р1-1 = 5 — 1 = 4, которое передается в регистр 1 в качестве

35 адреса верхней границы.

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

1 +4

Р2

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

Так как Клз < Кл„(10 < 15), то в счетчике

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

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

3+4

4, l 3 = 2 — = 3 передается в счетчик 4, Так как Кл < Кл (12 «15), то в счетчике 4 образуется значение Р,+1 = 3+ 1 = 4, которое в качестве нижней границы поступает в регистр 2.

50 В течение этих трех циклов на выходе

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

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

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

1658170

20 рован нулевым сигналом с прямого выхода этого триггера.

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

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

Р4 + 1 - 4 + 1 - 5, которое принимается в качестве нижней границы в регистр 2. При этом окаэы вается. что ВГ < НГ (10< 16) и на выходе "Меньше" схемы 7 устанавливается единичный сигнал. Данный сигнал блокирует по инверсному входу элемент И 29, запрещающий прием в счетчик 4 очередного

4+5 значения Ps—

4, сохраняя в нем адрес Р4 = 5.

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

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

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

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

Единичным сигналом с единичного выхода триггера 45 открываются элементы И

26, и код ключа верхней границы поступает на второй вход схемы 6 сравнения. На первый вход схемы 6 после приема в регистр 8 по второму импульсу с выхода распределителя 18 записи из блока памяти 9 поступает код ключа Kn3 = 16 через элементы И 27, Пусть /требуется определить адрес верхней границы, ключ которой Кл = 21 (фиг. Зб).

Так как КлВГ > КлВГ (24 > 21), то по завершении предварительного этапа триггер 79 оказывается в нулевом состоянии, определяя тем самым режим поиска верхней границы.

Так как КЛв< Кл (16 < 21), то на выходе

"Меньше" схемы 6 формируется единичный сигнал. При этом в счетчике 4 образуется адрес Р1- 5+ 1 = 6.

Этот адрес принимается в регистр 2 в качестве нижней границы.

В очередном цикле формируется ад6+9 рес Рр =

= 7 поступающий в счетчик 4, Так как Клз < Кл (20 < 21), то в счетчике

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

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

8+9

2 — 8

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

7 формируется единичный сигнал, которым через элемент ИЛИ 37 открывается по четвертому входу элемент И 32. Этот элемент открыт по первому и второму входам единичными сигналами с прямого выхода триггера 45 и инверсного выхода триггера 46 соответственно, а также по инверсному входу нулевым сигналом с единичного выхода триггера 79.

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

18, поступающим через открытый элемент И

32 и элемент ИЛИ 39 на синхровход регистра 21, адрес ВГ = 7 принимается в регистр

21 через элементы ИЛИ 13.

Одновременно импульсом с выхода элемента И 32 через элемент ИЛИ 40 устанавливается в нулевое состояние триггер 47.

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

9 до 15, т, е, Анг = 5, Авг = 7.

Если искомый подмассив данных отсутствует (пункты 7 и 13), то на выходе 59 формируется сигнал "Отсутствие подмассива".

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

ВГ (фиг. За).

На этапе предварительного анализа при сравнении ключей нижней границы НГО исходного массива и ключа НГ искомого подмассива формируется единичный сигнал на выходе "Меньше" схемы 80 сравнения, так как ВГО< НГ (24 < 25), открывающий элемент И 90, что обеспечивает передачу импульса с выхода элемента 94 задержки через элемент ИЛИ 36 на выход 59 "Отсутствие подмассива", Пусть ключ НГ = 6, ключ ВГ = 7, т. е. ключи нижней и верхней границ подмассива меньше ключа НГО.

В данном случае на этапе предварительного анализа на выходе "Больше" схемы 81 сравнения формируется единичный сигнал, так как НГО > ВГ (8 >7). открывающий элемент И 91, что обеспечивает переда17

1658170

18 чу импульса с выхода элемента 95 задержки через элемент ИЛИ 36 на выход 59 "Отсутствие подмассива", Если требуется определить адрес только одной записи, то в регистры 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 через элементы И 27 на первый вход схем 6 сравнения, Это дает воэможность при наличии информации в регистре 5 поддерживать отличный от нуля код ключа через элемент И 25 на втором входе схемы 6 сравнения. При этом на выходе "Меньше" данной схемы постоянно на все время работы устройства в режиме чтения удерживается единичный сигнал. По этому сигналу счетчик 4 формирует очередной адрес чтения блока 9 памяти, а через элементы И 10 и ИЛИ 14 обеспечивается запись очередного адреса в регистр 2 из счетчика 4. Этот же адрес передается и в регистр 1 по сигналу, поступающему через открытый элемент И 28 и элемент ИЛИ 15 на управляющие входы элемента И 24.

Чтение информации выполняется следующим образом, После подачи сигнала установки режима по входу 56 в устройство поступает сигнал начальной установки по входу 52, По этому сигналу адрес начала подмассива Анг (адрес нижней границы), предварительно считанный иэ регистра 17 по выходу 49, по входам 51 и 50 одновременно принимается в регистры 1 и 2 соответственно.

Затем в устройство подается по входу

58 сигнал пуска.

Так как после завершения предварительного этапа триггер 76 установлен в нулевое состояние, то элемент И 30 открыт по инверсному входу. После установки триггера 46 в единичное состояние нулевым сигналом с его инверсного выхода элемент И

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

По сигналу пуска производится чтение записи иэ блока 9 памяти, которая поступает из регистра 8 на выход 60. По окончании чтения триггер 47 устанавливается в "0".

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

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

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

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

"Меньше" схемы 7 в счетчик 4 принимается

НГ+НГ адрес А1—

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

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

60.

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

4 разрешается режим сложения.

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

19

10

25

35

45

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

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

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

И 24, При этом на выходе "Меньше" схемы

7 удерживается нулевой сигнал, По четвертому импульсу с выхода распределителя 18, кроме того, с выхода элемента И 28 через элемент ИЛИ 40 триггер

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

Единичный сигнал с нулевого выхода триггера 47 поступает на выход 5 и используется в качестве сигнала, разрешающего считывание записи с выхода 60, Чтение записи по очередному адресу производится по второму импульсу пуска, поступающему по входу 58, Работа устройства не отличается от описанной. Чтение записей будет производиться, пока текущий адрес не станет на единицу больше адреса верхней границы Asr, находящегося в регистре 21, Так, когда адрес обращения, принятой в счетчик 4 по импульсу с первого выхода распределителя 18, станет равным Aer, а по импульсу с третьего выхода распределителя

18 увеличится на единицу и принимается в регистры 2 и 1 по импульсу с выхода распределителя 18, то на выходе "Меньше" схемы

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

Повторное обращение к записям блока

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

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

Устройство для поиска данных по авт, св.ЛЬ1564648, отличающееся тем, что, с целью повышения быстродействия за счет предварительного анализа соотношения ключей границ исходного массива и искомого подмассива, оно дополнительно содержит блок анализа, разряды адресного выхода которого соединены через МОНТАЖНОЕ ИЛИ с одноименными разрядами выхода реверсивного счетчика, разряды ключа информационного выхода блока памяти подключены к одноименным разрядам входа ключа блока анализа, адресные входы верхней и нижней границ которого соединены с выходами регистров адреса верхней и нижней границ соответственно, выходы регистров ключей нижней и верхней границ подключены к входам ключей нижней и верхней границ соответственно блока анализа, первый выход управления которого соединен с инверсным входом третьего элемента

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

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

"Меньше" первой схемы сравнения блока анализа подключен к второму прямому вхо22

1658170

Таблица 1

Соотноюе>lt»(ключей вг, вг

Режим поиска

) (> (0 0 нг = нг„ вг - вг, 0 нг = нг„вг = вг, НГ = tlÃ, поиск ВГ

0 1 0 нг = вго, О 0 нг = нг,, нг = нг, 10 нг = нг, нг = нг > вга нг о

1З формирование сигнала

Нет данных

Таблица2 ду второго элемента И и второму входу шестого элемента И, а выход "Равно" — к второму входу восьмого элемента И, выход

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

Номер Соотноше»»и». ключей и/п НГ0 и нг элементов И, прямой выход триггера нижней границы, нулевой вход которого подключен к выходу второго элемента И, соединен с первым входом четвертого элемента И, выход которого является вторым выходом управления блока анализа, и с вторым входом пятого элемента И, первый вход которого подключен к и рямому выходу триггера верхней границы, нулевой вход которого соединен с выходом третьего элемента И, выход пятого элемента И подключен к третьему входу элемента ИЛИ, информационные входы элементов И первого и второго блоков подключены соответственно к адресным входам нижней и верхней границ блока анализа, в котором его первый и второй входы управления соединены соответственно с первым и вторым входами первого элемента И.

1 Поиск НГ, ВГ = Вга

0 Поиск НГ ВГ = ВГо»»pH КлНГ(Клвг

В(= ВГ, при КлНГ = КлВГо

НГ) Вà — формирование сигнала

"Нет данных" о Поиск НГ, поиск ВГ о вг = вг о вг = вг, поиск ВГ прн КлВГ ) Клнг

ВГ Нго при КлВГ = КлнГ

1658170

1658170

1658170

Hf 1

Р„= 4

Vo - 9

Составитель А. Мишин

Техред M,Ìîðãåíòàë Корректор М.Шароши

Редактор А. Пекарь

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

Заказ 1714 Тираж 417 Подписное

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

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