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

границы, сумматор 3, реверсивный счетчик 4, регистр 5 ключа нижней границы, две схемы 6 и 7 сравнения, регистр 8 инфоома ции, блок 9 памяти, два элемента И 10 и 11, две группы элементов ИЛИ 12 и 13, первый 14, второй 15 и третий 1C элементы ИЛИ, выходной регистр 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 записи, блок 61 анализа адресный выход 62 блока анализа, вход 63 ключа Ьло- кэ анализа, адресные входы 64 и 65 верхней и нижней границ соответственно блока анализа, входы 66 и 67 ключей нижней и верхней границ соответственно блока анализа, первый выход 68управления блока анализа, первый вход 69 управления блока анализа, второй 70, третий 71, четвертый 72, пятый 73, шестой 74 и седьмой 75 выходы управления блока анализа

Блок 61 анализа содержит {фиг. 2) первый 76 и второй 77 триггеры управления, триггер 78 ни-кней границы, три :ср 79 верхней границы, первую 80 и втору о 81 схемы сравнения, первый 82 и второй 83 блоки элементов И, первый 44 второй 85. третий 86, четвертый 87 и пятый 3В элементы И элемент ИЛИ 89, шестой 90, седьмой 91, восьмой 92 и девятый 93 элементы И первый 94, второй 95. третий 96 и четвертый 97 элементы задержки.

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

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

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

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

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

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

Введем следующие обозначения: НГ0 - нижняя граница (адрес первой записи исходного массива); ВГ0 - верхняя граница (адрес последней записи исходного масси5 ва), PI - адрес блока памяти i-ro цикла устройства; Анг - адрес первой записи юдмассива; АВг - адрес последней записи подмассива, Кли - ключ исходной записи подмассива; Кл3 - ключ считанной записи из

0 блока памяти.

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

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

0Работа устройства в режиме поиска

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

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

5 триггеры 47, 45, 76 устанавливают в состояние 0 (не показано).

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

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

5 ключи которых лежат в заданном интервале. Единичным сигналом с инверсного выхода триггера46открыты элементы И 27, 31,32,34, а в блоке 61 анализа - элемент И 84.

Ксоме того, по импульсу с входа 55 в 61 устанавливаются в нулевое состояние триггер 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 устанавливается в состояние О, при этом

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Работа устройства на этапе предварительного анализа состоит в следующем

Так как блок элементов И 83 открыт по двук-; управляющим входам единичными сигналами с прямою выхода триггера 76 и инверсного выхода триггера 77, то адрес верхней границы с выхода регистра 1 через эгот блок элементов И 83 и МОНТАЖНОЕ ИЛИ поступает на адресный вход блока 9 памяти. Считанная информация поступает на адресный вход блока 9 памяти. Считанная информация - ключ ВГ0 с выходов блока 9 - поступает на первые входы схем 80 и 81 сравнения, на вторых входах которых находятся ключи нижней и верхней i раниц искомого подмассива соответственно.

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

1. КлВГо-КлНГ, что соответствует шестой строке табл. 1. При этом на выходе Равно схемы 80 сравнения формируется единичный сигнал, открывающий элемент И 92.

Чгрез некоторое время, определяемое элементом 94 задержки и равное времени переходных процессов в блоке 9 пямяти и схеме 80 сравнения, задержанным импульсом пуска через элемент И 92 и элемент ИЛИ 38 по синхровходу регистра 17 обеспечивается запись в него адреса 8I 0 с выходов блока элементов И 83 через МОНТАЖНОЕ ИЛИ л элементы ИЛИ 4i Б регистре 21 сохраняется знэчеш.-э адреса НГо

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

0 исключается воздействие задержанного импульса пуска с выхода элемента 95 задержки на состояние элементов схемы устройства с выходов 72, 83 и 75 блока 61 анализа.

52.КлВГ0 Кл И г, что соответствует седьмой строке табл. 1. При этом на выходе Меньше схемы 80 сравнения формируется единичный сигнал, открывающий элементы И 85 и 90. Задержанный импульс с выхода

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

53. КпВГо КлВГ, что соответствует

третьей, восьмой и одиннадцатой строкам таил. 1

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

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

4. Если же КлВГо КлВГ, то на выходе

0 Больше схемы 81 сравнения устанавливается нулевой сигнал, а триггер 79 при этом удерживается в единичном состоянии, что означает необходимость сохранения в регистре 21 адреса верхней границы (первая,

5 вторая, четвертая, пятая, шестая, девятая и десятая строки табл. 1).

С г.ыхода элемента 94 задержки, кроме тою, задержанным импульсом пуска устанавливается в единичное состояние триггер

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

5 когда при сравнении определен режим работы устройства по поиску верхней границы искомого подмассива.

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

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

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

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

При этом на выходе Равно схемы 81 сравнения формируется единичный сигнал, открывающий элемент И 93. Задержанным импульсом пуска с выхода элемента 95 задержки через время, равное времени переходных процессов в блоке 9 памяти и схеме 81 сравнения, через элемент ИЛИ 39 по синхровходу регистра 21 обеспечивается запись в него адреса НГ0 с выходов блока элементов И 82 через МОНТАЖНОЕ ИЛИ и элементы ИЛИ 13.

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

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

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

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

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

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

8.Если же КлНГо 5: КлНГ, то на выходе Меньше схемы 80 сравнения устанавливается нулевой сигнал, закрывающий элемент И 85, чем триггер 78 удерживается в единичном состоянии. Это означает, что нет необходимости поиска нижней границы, т. е. в регистре 17 сохраняется адрес нижней границы (первая,вторая и третья, девятая, де- сятая и одиннадцатые строки табл. 1).

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

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

В соответствии с табл. 2 завершение работы блока 61 производится следующим образом.

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

5Если только триггер 79 находится в единичном состоянии, то единичным сигналом с его единичного выхода блокируется по инверсному входу элемент И 32 для исключения влияния импульса с выхода

0 распределителя 18 и через МОНТАЖНОЕ ИЛИ с выходом схемы 44 сравнения открывается по второму входу элемент И 33. Это необходимо для того, чтобы после определения нижней границы и размещения ее в

5 регистре 17 завершить работу устройства, так как верхняя граница уже находится в регистре 21.

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

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

Если оба триггера 78 и 79 находятся в

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

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

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

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

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

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

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

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

В Г0 + Н Г0

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

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

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

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

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

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

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

Кроме того, по сигналу с выхода элемента И 35 через элементы И 23 код адреса ВГО из регистра 21 передается в регистр 1,

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

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

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

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

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

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

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

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

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

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

10г,В Г0 + Н Го

8 адрес Pi из сумма ора

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

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

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

Единичным сигналом с выхода Равно схемы 6 через элемент ИЛИ 16 открывается элемент И 31.

В очередном такте генератора 19 по импульсу на выходе распределителя 18 адрес Р1 принимается в регистр 17.

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

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

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

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

мированныи адрес Ра-s,

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

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

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

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

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

Так как КлНГ0 КлНГ (8 15), то по

завершении предварительного этапа триггер 78 оказывается в нулевом состоянии,

определяя тем самым режим поиска нижней

границы.

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

30

D1 +9

Р1 - - 5

Так как Кл3 Кли (16 15), то в счетчике 4 формируется значение Pi-1 , которое передается в регистр 1 в качестве адреса верхней границы.

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

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

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

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

D 3 +4 „.

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

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

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

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

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

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

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

значения PS

4+5

4 , сохраняя в

нем адрес Рл 5.

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

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

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

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

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

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

ТаккакКЛз Кли(16 21), то на выходе Меньше схемы 6 формируется единичный сигнал. При этом в счетчике 4 образуется адрес Pi 5+ 1 6.

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

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

Так как Кл3 Кли (20 21), то в счетчике

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

8 +9 В следующем цикле Рз -я- 8

Так как Кл3 Кли (), то в счетчике 4

формируется адрес Р3 -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, т. е. ключи границ подмассива больше ключа

8Го (фиг. За).

На этапе предварительного анализа при сравнении ключей нижней границы НГ0

исходного массива и ключа НГ искомого подмассива формируется единичный сигнал на выходе Меньше схемы 80 сравнения, так как ВГ0 НГ (24 25), открывающий элемент И 90, что обеспечивает передачу

импульса с выхода элемента 94 задержки через элемент ИЛИ 36 на выход 59 Отсутствие подмассива.

Пусть ключ НГ 6. ключ ВГ 7, т. е. ключи нижней и верхней границ подмассива

меньше ключа НГ0.

В данном случае на этапе предварительного анализа на выходе Больше схемы 81 сравнения формируется единичный сигнал, так как НГ0 ВГ (8 7), открывающий элемент И 91, что обеспечивает передачу импульса с выхода элемента 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 закрыт, чем блокируется воздействие им0 пульса пуска на элементы схемы блока 61.

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

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

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

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

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

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

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

. Н Г -I- Н Г иг адрес AI я НГ по которому

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

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

Так как элементы И 27 закрыты нулевым

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

5 которым открыт элемент И 10/ а в счетчике 4 разрешается режим сложения.

По третьему импульсу с выхода распределителя 18 в счетчике формируется код адреса А2 AI + 1, который поступает через элементы ИЛИ 12 в регистр 2 и через элементы И 24 в регистр 1. Прием в.регистр 2 этого адреса производится по четвертому импульсу с выхода распределителя 18, проходящему через элементы И 10 и ИЛИ 14 на синхровход регистра. В регистр 1 этот же 5 адрес принимается по тому же импульсу, проходящему через элемент И 28, элемент ИЛИ 15 на управляющие входы элементов И 24. При этом на выходе Меньше схемы 7 удерживается нулевой сигнал.10

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

Единичный сигнал с нулевого выхода 15 триггера 47 поступает на выход 5 и используется в качестве сигнала, разрешающего считывание записи с выхода 60.

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

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

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

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

Устройство для поиска данных по авт, св. № 1564646, отличающееся тем, что, с целью повышения быстродействия за 45 счет предварительного анализа соотношения ключей границ исходного массива и искомого подмассива, оно дополнительно содержит блок анализа, разряды адресного выхода которого соединены через МОН- 50 ТАЖНОЕ ИЛИ с одноименными разрядами выхода реверсивного счетчика, разряды ключа информационного выхода блока памяти подключены к одноименным разрядам входа ключа блока анализа, адресные входы 55 верхней и нижней границ которог о соединены с выходами регистров адреса верхней и нижней границ соответственно, выходы регистров ключей нижней и верхней границ подключены к входам ключей нижней и верхней границ соответственно блока анализа, первый выход управления которого соединен с инверсным входом третьего элемента И, первый, второй, третий и четвертый входы управления блока анализа соединены со- ответственно с инверсным выходом триггера режима, входом пуска устройства, входом поиска устройства и инверсным выходом триггера пуска, второй, третий, четвертый, пятый, шестой и седьмой выходы управления блока анализа подключены соответственно к выходу седьмого элемента И, к инверсному входу пятого элемента И и второму входу восьмого элемента И, к четвертому входу восьмого элемента ИЛИ, к третьему входу седьмого элемента ИЛИ, к третьему входу пятого элемента ИЛИ и к третьему входу шестого элемента ИЛИ, причем блок анализа содержит первую и вторую схемы сравнения, первые входы которых объединены и поключены к входу ключа блока анализа, а вторые входы являются входами ключей нижней и верхней границ соответственно блока анализа, девять элементов И, элемент ИЛИ, выход которого является четвертым выходом управления блока анализа, четыре элемента задержки, первый и второй блоки элементов И, выходы которых объединены и подключены к адресному выходу блока анализа, триггер нижней границы, триггер верхней границы, прямой выход которого является третьим выходом управления блока анализа, первый и второй триггеры управления, единичные и нулевые входы которых объединены и подключены к третьему входу управления блока анализа, прямой выход первого триггера управления является первым выходом управления блока анализа и подключен к первым управляющим входам первого и второго блоков элементов И, вторые управляющие входы которых соединены соответственно с прямым и инверсным выходами второго триггера управления, выход первого элемента И блока анализа соединен с единичными входами триггеров нижней и верхней границ и через первый элемент задержки - с первыми входами третьего, шестого и восьмого элементов И, с единичным входом второго триггера управления и входом второго элемента задержки, выход которого подключен к первым прямым входам второго, седьмого и девятого элементов И и к входу третьего элемента задержки, выход которого соединен с вторым входом четвертого элемента И, третьим входом пятого элемента И и через четвертый, элемент задержки - с нулевым входом первого триггера у правления, выход Меньше первой схемы сравнения блока анализа подключен к второму прямому входу второго элемента И и второму входу шестого элемента И, а выход Равно - к второму входу восьмого элемента И, выход Больше второй схемы сравнения блока анализа соединен с вторым входом третьего элемента И и вторым прямым входом седьмого элемента И, а выход Равно - с вторым прямым входом девятого элемента И, выход которого подключен к седьмому выходу управления блока анализа и персому входу элемента ИЛИ, второй вход которого соединен с выходом восьмого элемента И и с шестым выходом управления блока анализа, пятый выход управления которого соединен с выходом шестого элемента И, объединенным с выходом седьмого элемен - та И, инверсный вход которого соединен с четвертым входом управления блока анализа, инверсными входами девятого и второго

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

Таблица 1

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

Таблица2

Ф 1 Ф Ф Ф

& W 22 & tfp

О/. 18991

Фич 3