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

)506 Р 15(40 НИ 4) УСТРОЙСТВО ДЛЯ7) Изобретение,отнтельной технике ильзовано в системах ИСКА ДАННЬ ится к вычисжет быть исуправления ба ССР 984М циф 3 тс. гистрП р М262 ГОСУДАРСТВЕННЫЙ НОМИТЕПО ИЗОБРЕТЕНИЯМ И ОТНРЫТПРИ ГКНТ СССР ОПИСАНИЕ ИЗОБРЕ Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(56) Авторское свидетельствоМ 1126972, кл. 6 06 Р 15/40,Папернов А.А. и Подымов В.тоды упорядочения информациировых системах. М,: Наука, 19с. 384,Овчаров Л.А. и Селетков С.томатизированные банки данныхФинансы и статистика, 1982, сАвторское свидетельство ССР 1228116, кл. С 06 Р 15/40,зами даннь 1 х, Цель изобретения - расширение функциональных возможностейустройства за счет возможности определения граничных адресов подмассива дан." в заданном интервале значений ключей записи, Это достигае ятем, что устройство содержит ре1 адресверхней границы, регисадреса нижней границы, сумматор 3,реверсивный 4 четчик, регистр 5ключа нижней границы, две схемы 6 и7 сравнения, регистр 8 информации,блок 9 памяти, два элемента И 10,20 вые входы которых соединены с инверсным выходом триггера управленияи с третьим входом четвертого элемента И выход которого соединен с перЭвым входом пятого элемента ИЛИ, выход которого подключен к синхровходу выходного регистра адреса нижнейграницы, Разряды информационноговхода которого соединены с выходамисоответствующих элементов ИЛИ третьей группы, первые входы которыхподключены к первым входам соответствующих элементов И четвертой группыи к соответствующим разрядам выходареверсивного счетчика, а вторыевходы являются соответствующими разрядами входа адреса нижней границыустройства, установочньй вход уст ройства соединен с первым входом деВятого элемента И, выход которогосоединен с синхровходами регистров.ключей нижней и верхней границ, снулевым входом триггера управления, 25 с вторым входом пятого элемента ИЛИи с первым Входом шестого элементаИЛИ, выход которого подключен к синхровходу выходного регистра адресаверхней границы, разряды выхода кото рого подключены к вторым входам соОтветствующих элементов И первойгруппы и к входам первого операндатретьей схемы сравнения соответственно, входы второго операнда которойсоединены с соответствующими разрядами выхода регистра адреса нижнейграницы и с соответствующими входамипервого операнда четвертой схемысравнения, входы второго операнда ко 19 15 б 4 б 48 Його счетчика и к второму входу Второго элемента И, о т л и ч а ю щ ес я тем, что, с целью расширения функциональных возможностей устройства за счет определения граничных адресов подмассива данных в заданном интервале значений ключей записей, стройство содержит регистр ключа ерхней границы, информационный вход оторого является входом ключа верхей границы устройства, выходной регистр адреса верхней границы, выход оторого является выходом адреса Верхей границы устройства, шесть элемен-ов И, элементы И с третьего по десятый, элементы ИЛИ с четвертого по восьмой, третью группу элементов ИЛИ, третью, четвертую и пятую схемы сравнения, триггер управления, триггер режима, входы сброса установки которого являются входами поиска и чтения устройства соответственно, и триггер пуска, инверсный выход которого является выходом готовности устройства, вход пуска которого подключен к единичному входу триггера пуска, прямой выход которого соединен с первым вхоом третьего элемента И, второй вход которого подключен к Выходу генератора импульсов, а выход - к входу распределителя импульсов, четвер,тый выход которого соединен с первыми входами четвертого и пятого элементов И и с первым входом шестого элемента И выход которого подключен к входу разрешения записи ре,версивного счетчика, второй вход шестого элемента И соединен с выходом 11Меньше первой схемы сравнения,.вы ход "Равно" которой соединен с первым входом. четвертого элемента ИЛИ, второй вход которого подключен к выходу "Равно" второй схемы сравнения и к ВтОРОму ВхОду ВтОРО 1 0 элемента 45 ИЛИ, выход которого соединен с вторым входом четвертого элемента И и первым входом седьмого элемента И, выход которого подключен к первому входу восьмого элемента И, первым 50 входам элементов И первой группы и к единичному входу триггера управления, прямой выход которого соединен с вторым входом пятого элемента И и с первыми входами элементов И второй группы, выходы которых подключены к входам первого операнда второй схемы сравнения соответственно и к выходам элементов И третьей группы, перторой подключены к соответствующим разрядам Выхода выходного регистра адреса нижней границы, выход"Больше" третьей схемы сравнения ивыход "Меньше" четвертой схемы сравнения соединены соответственно с первым и вторым входами седьмого элемента ИЛИ, выход которого подключен к входу признака отсутствия подмассива устройства и к первому входу восьмого элемента ИЛИ, выход которого соединен .с нулевым входом триггера пуска, выход первого элемента И соединенс первым входом десятого элемента И, Выход которого поцключен к второму входу третьего элемента ИЛИ ик второму входу восьмого элементаИЛИ, третий Вход которого подключенк выходу восьмого элемента И, второйвход которого соединен с выходом1564648 22 Йгеа,вг,1 ге: Составитель С.АверьяноваРедактор М.Келемеш Техред М.Ходанич Корректор М. Самборская Заказ 1162 Тираж 564НИИПИ Госу а Т ССС Подписноепо.изобретениям и открытиям при ГКН"Равно" пятой схемы сравнения, разряды входов первого и второго операн- дов которой подключены к вторым входам соответствующих элементов И тре 5 тьей и второй групп соответственно и к выходам разрядов регистров ключей нижней и верхней границ соответственно, инверсный выход триггера режима соединен с вторым входом девятого элемента И, четвертым входом четвертого элемента И и третьим входом пятого элемента И и первыми входами элементов И пятой группы, выходы которых подключены к соответствующим входам первого операнда второй схемы сравнения, прямой выход триггера режима соединен с вторым.входом десятого элемента И, выход четвертого элемента ИЛИ соединен с четвертым входом пятого элемента И, выход которого подключен к второму входу шестого элемента ИЛИ и второму входу восьмого элемента ИЛИ, первый выход распределителя импульсов 25 подключен к второму входу седьмогоэлемента И, выходы элементов ИЛИ второй группы соединены с соответствующими разрядами информационного входавыходного регистра адреса верхнейграницы, разряды выхода регистра ин-,формации подключены к вторым входамсоответствующих элементов И пятойгруппы и являются одноименными разрядами выхода записи устройства, разряды входа адреса верхней границы которого подключены к первым входамсоответствующих элементов И шестойгруппы, вторые входы которых соединены с соответствующими разрядами установочного входа устройства, выходтретьего элемента ИЛИ подключен квторым входам элементов И четвертой.группы, выходы которых соединены свыходами соответствующих элементов Ипервой и второй групп и подключенык соответствующим разрядам информационного входа регистра адреса верхней границы.1564648 25 30 35 40 45 50 55 11, две группы элементов ИЛИ 12, 13,первый 14, второй 15 и третий 16 элементы ИЛИ, выходной регистр 17 адреса нижней границы, распределитель18 импульсов, генератор 19 импульсов. Устройство также содержит регистр 20 ключа верхней границы, выходной регистр 21 адреса верхней границы, шесть групп элементов И 22-27, 10с третьего по десятый элементы И28-35, с четвертого по восьмой элементы ИЛИ 36-40, третью группу 41элементов ИЛИ, третью 42, четвертую43 и пятую 44 схемы сравнения, триг-15 Изобретение относится к вычислительной технике и может быть использовано в системах управления базами данных.Цель изобретения - расширение возможностей устройства за счет определения граничных адресов подмассива данных в заданном интервале значений ключей записей,На фиг, 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 адреса гер 45 управления, триггер 46 режима, Кроме того, в устройство входяттриггер 47 пуска, вход 48 ключа ниж.ней границы, выход 49 адреса нижнейграницы, вход 50 адреса нижней границы, вход 51 адоеса верхней границы, установочный 52 вход, вхор, 53к.:юча верхней границы, выход 54 адреса верхней границы, вход 55 поиска, вход 56 чтения, выход 57 готовности, вход 58 пуска, выход 59 приз;ака отсутствия подмассива, выходЫ записи, 2 ил. верхней границы, установочный вход52, вход 53 ключа верхней границы,выход 54 адреса верхней границы, вход55 поиска, вход 56 чтения, выход 57готовности, вход 58 пуска, выход 59признака отсутствия подмассива, выход60 записи.Устройство работает следующим образом,В блоке 9 памяти размещен массив,каждая ячейка которого состоит изслужебного и информационного полей.Служебное поле используется для указания кода ключа идентификатора),а информационное - для размещениясмыслового содержания идентифицируемой части записи, Записи набораданных отсортированы по возрастаниюзначений ключей. Это означает, что,если а-я запись размещена по 1-муадресу, то (1+1)-я запись хранитсяпо В+1)-му адресу, причем ключ(х+1)-й записи больше ключа х-й записи, т.е. функция адреса блока 9памяти линейно зависит от приращения, значений кода ключа,Задача состоит в определении граничных адресов подмассива записейУключи которых находятся в заданном интервале значений, Для нахождения граничных адресов подмассива используется дахотбмическнй поиск.вначале адреса нижней, а затем адреса верхней границы. При таком поиске размер области поиска в результате каждой проверки сокращается примерно вдвое.515Введем следующие обозначения:НГ - нижняя граница - адрес перовой записи исходного массива;ВГ - верхняя граница - адрес пооследней записи исходногомассива;Р - адрес блока памяти д-го цикла устройства;Аи, - адрес первой записи подмассива;А - адрес последней записи подбгмассива;Кл - ключ исходной записи подимассива;Кл - ключ считанной записи из5блока памяти,Устройство работает в двух режимах: поиска и чтения информации.Установка режима производится по входам 55 и 56. При подаче на вход 55импульса в устройстве устанавливает-,ся режим поиска данных. При необходимости чтения подмассива выделенныхзаписей по входу 56 подается импульс,Фустанавливающий триггер режима 46в единичное состояние,Работа устройства в режиме поискаподмассива требуемых записей состоитв следующем.В исходном состоянии распределитель 18 импульсов, регистры 8, 17 и21, триггеры 47 и 45 установлены всостояние "0", На входы 53 и 48 подаются коды ключей нижней и верхнейграниц искомого подмассива соответственно, На входы 51 и 50 поступаюткоды адресов верхней и нижней границисходного массива, По входу 55 поступает импульс, устанавливающийтриггер 46 в нулевое состояние, определяя режим поиска записей, ключи которых лежат в заданном интервале.Единичным сигналом с инверсного выхода триггера 46 открыт элемент И 34.После установки триггера 46 по входу52 подается импульс, по которому разрешается запись исходной информациив регистры 5 и 20, в регистр 1 - через открытые элементы И ВВ, в регистр2 - через элементы ИЛИ 12, и импульсна синхронизирующем входе через элемент ИЛИ 14 и аналогичным образомв регистры 17 и 21 через элементыИЛИ 41, ИЛИ 13 и элементы И 34 ИЛИ38 и ИЛИ 39 соответственно,Начало поиска записи инициируется подачей импульса пуска по646486 5 10 15 20 25 30 35 40 45 50 55 входу 58, устанавливающему триггер47 в единичное состояние. Единичнымсигналом с прямого выхода триггера47 открывается элемент И 30 по первому входу, в результате чего импульсы с генератора 19 подаются навход распределителя 18 импульсов, Импульсы с выходов распределителя 18подаются в различные точки устройства,Работа устройства состоит из двухэтапов, каждый из которых выполняется одинаково. Первый этап используется для определения адреса нижней(первой) границы подмассива, а навтором этапе обеспечивается нахождение верхней (последней) границы лодмассива Первый этап выполняется принулевом состоянии триггера 45. Призавершении первого этапа, т.е. послеопределения первой, нижнеи границыподмассива триггер 45 устанавливается в состояние "1", переводя устройство во второй этап работы.По окончании второго этапа триггер 47 устанавливается в состояние"0" г;ри этом на выходе 57 Формируется единичный сигнал, используемыйв качестве сигнала готовности уст"ройства к выдаче информации в заданном интервале значений ключей.В зависимости от соотношения ключей исходного массива н заданногоинтервала значения ключей подмассива в регистрах 17 и 21 Формируютсяграничные адреса искомого подмассива.1, Ключ НГ равен ключу НГ и ключВГ равен ключу ВГ . При этом в регистре 17 устанавливается адрес НГа в регистре 21 - адрес ВГ.2. Ключ НГ равен ключу НГ, аключ ВГ больше ключа ВГ . При этомв регистре 17 формируется адрес НГ,а в регистре 21 - адрес ВГ .3, Ключ НГ равен ключу НГ , аключ ВГ меньше ключа ВГ . В этомслучае в регистре 17 формируется адт.рес НГО, а в регистре 21 - адрес,меньший адреса последней границы массива с ключом ВГО.4, Ключ ВГ равен ключу ВГ , аключ НГ больше ключа НГ . При этом врегистре 17 формируется адрес НГ,лежащий внутри массива, а в регистре 21 - адрес ВГО .5Ключ ВГ меньше ключа ВГ , ноадрес с ключом ВГ лежит внутри мас-.сива, а ключ ВГ больше ключа ВГ, 1564648При этом в регистре 17 устанавливается адрес, лежащий внутри массива, ав регистре 21 формируется адрес ВГ, .6. Ключ ВГ равен ключу ВГ , аключ ВГ больше ключа ВГ. При этомв регистрах 17 и 21 устанавливается один и тот же адрес записи сключом ВГ7, Ключи НГ и ВГ больше ключа, ВГ . При этом в устройстве формируется сигнал Отсутствие подмассива",8. Ключ НГ меньше ключа НГ , а,ключ ВГ равен ключу В 1"о, При этом врегистре 17 формируется адрес НГа в регистре 21 - адрес ВГ.9. Ключ НГ меньше ключа НГ , аключ ВГ больше ключа ВГ . В данномслучае в регистре 17 устанавливаетсяадрес НГ , а в регистре 21 - адрес ВГп,10; Ключ НГ меньше ключа НГ , аключ ВГ меньше ключа ВГ, но больше,ключа НГ . При этом в регистре 17формируется адрес НГ , а в регистре 2521 - адрес записи, лежащей внутримассива.11. Ключ НГ меньше ключа НГ, аключ ВГ равен ключу НГО . В данномслучае в регистрах 17 и 21 устанавли,вается адрес НГ12. Ключи НГ и ВГ меньше ключаНГ. В этом случае в устройстве формируется сигнал "Отсутствие подмасИсива 35В любой из этих указанных ситуацийпоиск нижней границы выполняется следующим образом,С помощью сумматора 3 определяется сумма ВГ +НГ которая со сдвигом на один разряд вправо (в сторонумладших разрядов) заносится в счетчик4 по первому импульсу с выхода распределителя 18, Этот импульс поступает через открытый элемент И 29 по 45инверсному входу нулевым сигналом свыхода "Меньше" схемы 7 сравнения(так как адрес ВГ больше адреса НГ)на вход разрешения записи счетчика 4.Таким образом, в счетчике 4 фиксируется код адреса ВГ +НГоРо2где 1.х - ближайшее целое меньшее либо равное х. По этому адресу производится обращение в блок 9 памяти, и считаннаязапись с ключом Клв принимается в регистр 8 по второму имп;пьсу с выхода распределителя 18, поступающего на синхровход регистра 8.Так как триггер 45 находится в нулевом состоянии, то единичным сигналом с его инверсного выхода открыты э.ементы И 25, и код ключа НТ с выхо,ов регистра 5 поступает на второ,г вход схемы б сравнения, Первый вход этой схемы связан с выходом кода клюрегистра 8 через открытые в дан.ом режиме элементы И 27. Пссредством схемы 6 производится проверка соотношения Кл и ключа3 искомой границы. При этом возможны следующие ситуации.А, Коды ключей совпадают.В этом случае на выходе "Равно" схемы б формируется единичный сигнал, которым через элемент ИЛИ б открывается по четвертому входу элемент И 31, Так как этот элемент открыт также по первому входу единичным сигналом с инверсного выхода триггера 45, по второму входу - единичным сигналом с инверсного выхода триггера 46, то по очередному импульсу с выхода распределителя 18, поступающему через элементы И 3 и ИЛИ 38 на синхровход регистра 17, в него принимается адрес первой (нижней) границы подмассива из счетчика 4 через элементы ИЛИ 41, Затем по импульсу выхода распределителя 18 через открытый элемент 35 И единичным сигналом с выхода "Равно" схемы 6 триггер 45 устанавливается в единичное состояние. При этом нулевым сигналом с инверсного выхода триггера 45 закрываются элементы И 31 и 25, а открываются элементы И 32 и 26 единичным сигналом с прямого выхода этого триггера. Кроме того, по сигналу с выхода элемента И 35 через элементы И 23 код адреса ВГ иэ регистра 21 передается в регистр 1. Если же сигнал на выходе "Равно" схемы 6 сформировался на этапе поиска верхней границы, т.е, когда триггер 45 находился в единичном состоянии, то по импульсу с выхода распределителя 18 через открытый элемент И.32 и элемент ИЛИ 39 .адрес из счетчика 4 пере-, дается через элементы ИЛИ 13 в регистр 21 в качестве верхней (последнего адреса) границы подмассива. Од 1564648 10Р;, =Р;+1,которая через элементы ИЛИ группы 12поступает в регистр 2 в качестве очередной нижней границы поиска по им -пульсу с выхода распределителя 18.После этого поиск границы производится в очередном такте генератора 19.С. Код ключа считанной записибольше кода ключа искомой границы.В этом случае на выходе "Больше"схемы 6 формируется единичный сигнал,открывающий элемент И 11 и устанавливающий режим вычитания счетчика 4.По импульсу с выхода распределителя 18 в счетчике 4 формируется разность35 20 Р, =Р -1,нкоторая через элементы И 24 принимается в регистр 1 в качестве верхнейграницы для очередного цикла работы 40устройства, Прием адреса производится по импульсу с выхода распределителя 18, поступающего через элементыИ 1 1 и ИЛИ 15 на управляющие входыэлементов И 24. 45На первом этапе поиска нижнейграницы устройство работает следующимобразом,По импульсу с выхода распределителя 18 адрес Г вг.+нг, 1о о2 из сумматора 3 принимается в счетчик4 Это Обусловлено тем, что Вго Ъ НГО. 5поэтому на выходе "Меньше" схемы 7сравнения устанавливается нулевойсигнал, открывающий по инверсномувходу элемент И 29, выходом подклюновременно с этим по сигналу с выхода элемента И 32 через элемент ИЛИ 21 триггер 47 устанавливается в нулевое .состояние, Единичный сигнал с инверсного выхода триггера 47 поступает на выход 57 и используется в качестве сигнала готовности устройства к выдаче информации,В. Код ключа считанной записи 10 меньше кода ключа искомой границы.В данном случае на выходе "Меньше" схемы 6 формируется единичный сигнал. Данным сигналом открывается элемент И 10 и разрешается режим сложения в 15 счетчике 4. По импульсу с выхода распределителя 18 в счетчике 4 формируется сумма ченного к входу разрешения записисчетчика 4,По адресу Р производится обраще 1ние к блоку 9 памяти, и считанная запись принимается в регистр 8 по импульсу с выхода рас. ределителя 18,Код ключа считанной записи через открытые элементы И 27 подается на первый вход схемы 6 сравнения. На второй вход схемы 6 сравнения подаетсякод ключа нижней границы из регистра5 через открытые элементы И 25 единичным сигналом с инверсного выходатриггера 44,Если ключи совпадают, то на выходах "Меньше" и "Больше" схемы 6 устанавливаются нулевые сигналы, блокирующие элементы И 10, 11 и запрещающие операции сложения н вычитанияв счетчике 4. Поэтому импульсы с выхода распределителя 18 не изменяютсодержимое счетчика 4 и в нем сохраняется значение адреса Р, а импульсс выхода распределителя 18 не изменяет состояния регистров 2 и 1,Единичным сигналом с выхода "Равно" схемы 6 через элемент ИЛИ 16 открывается элемент И 31, В очередномтакте генератора 19 по импульсу навыхе распределителя 18 адрес Р,принимается в регистр 17. Так как врегистрах 2 и 1 информация не изменилась, то адрес Р, повторно такжепринимается в счетчик 4,По импульсу с выхода распределителя 18 триггер 45 переключается вединичное состояние, блокируя темсамым элемент И 31 по первому входуи открывая по первому входу элементИ 32. Кроме того, на второй вход схемы 6 через элементы И 26, открытыетеперь уже единичным сигналом с прямого выхода триггера 45, подаетсякод ключа верхней границы из регистра 20,Таким образом, после окончанияимпульса с выхода распределителя 18на первом входе схемы 6 присутствуеткод ключа считанной записи по адресу Р, а на втором входе - код ключа верхней границы. А так как ключНГ меньше ключа ВГ , то на выходе"Меньше" схемы 6 формируется единичный сигнал. И в дальнейшем в соответствии с рассмотренным выше ви. В в регистре 2 фиксируется код адреса Р+1 по импульсу с выхода распределителя 18,После этого снова появляется импульс на выходе распределителя 18, по которому сформированный адресгде НГ=Р, +1; ВГ=ВГпринимается в счетчик 4,В дальнейшем устройство работаетаналогично.Поиск нижней и верхней границ,когда ключи считанной записи и установленного значения не совпадают,производится следующим образом.Пусть в массиве с НГ=1 и ВГ=9необходимо определить нижнюю границу, начиная с которой ключи записейбольше заданного.На фиг, 2 а показана условнаяструктура массива с НГ=1 и ВГ=9, авнутри каждой ячейки указаны значения.ключей. Требуется определить адрес, начиная с которого все ключибольше Кл=15.В соответствии с описанным в первомцикле Так как КЛ р КЛ (16 ) 15), то всчетчике 4 формируется код Р=5-1= , =4, который передается в регистр 1 вкачестве адреса верхней границы.На втором цикле величинапередается в счетчик 4.Так как КЛ 1 Кли (10 с 15)р то В счетчике 4 формируется значение Р+.1=2+1=3, которое в качестве нижней границы передается в регистр 2.В третьем цикле величина передается в счетчик 4,Так как Кл сКл и (12 с 13), то всчетчике 4 образуется значение Р +1=-3 -1=3+1=4, которое в качестве нижнейграницы поступает в регистр 2,В течение этих трех циклов на выходе "Меньше" схемы 7 сравнения присутствует нулевой сигнал, которым элемент И 29 удерживается в открытом состоянии по инверсному входу,В третьем цикле НГ=ВГ, на выходе11 11Равно схемы,7 сравнения формируется единичный сигнал, открывающий через элемент ИЛИ 37 элемент И 32 почетвертому входу, Но так как триггер5 находится в нулевом состоянии,.р.емент И 32 заблокирован нулевымягналом с прямого выхода этоготриггера,В четвертом цикле формируется адрес Р = -- =415 который передается в счетчик 4.Так как Кл с Кл (14 15), то всчетчике 4 формируется значение адреса Р 1 +1=4+1=5, которое принимается в качестве нижней границы в регистр 2. При этом оказывается, что ВГ НГ (10 ( 16), и на выходе "Меньше" схемы 7 устанавливается единичный сигнал, Данный сигнал блокирует по 25 инверсному входу элемент И 29, запрещающий прием в счетчик 4 очередного значения сохраняя в нем адрес Р =5.Одновременно сигналом с выхода"Меньше" схемы 7 через элемент ЕЛИ16 открывается элемент И 31 по чет-.вертому входу. Так как этот элемент,кроме того, открыт по первому входуединичным сигналом с инверсного выхода триггера 45, а по второму -единичным сигналом с инверсного выл хода триггера 46 то по импульсу свыхода распределителя 18, поступающего через этот элемент И 31 и элемент ИЛИ 38 на синхровход регистра17, производится прием в него адре 45 са нижней границы подмассива Р =5.После этого триггер 45 переключается в единичное состояние, обеспечивая поиск адреса верхней границы.Одновременно с установкой в "1" триг 50,) гера 45 адрес ВГ =9 через элементыИ 23 йередается в регистр 1,Единичным сигналом с единичного выхода триггера 45 открь)ваются элементы И 26, и код ключа верхней границы поступает на второй вход схемы 6 сравнения. На первый вход схемы 6 после приема в регистр 8 по второму импульсу с выхода распределителя 186+91 Р=8,25 50 55 13 156464 записи из блока памяти 9 поступает код ключа Кл=16 через элементы И 27.Пусть требуется определить адрес верхней границы, ключ которой Кл=21 (фиг. 2 б).Так как Кл сКли (16 с 21), то на выходе "Меньше" схемы формируется единичный сигнал, При этом в счетчике 4 образуется адрес Р,=5+1=6. Этот адрес принимается в регистр 2 в качестве нижней границы.В очередном цикле Формируется ад- рес поступающий в счетчик 4,Так как Кл, с Кли (20 с 21), то всчетчике 4 формируется адрес Р+1= 20=7+1=8, передаваемый в регистр 2 вкачестве нижней границы.В следующем цикле Так как Кл р Кл (2221), то в счетчике 4 формируется адрес Рэ=8-1 7который поступает в регистр 1 в качестве верхней границы, При этом 30оказывается, что НГ=ВГ (7=7), в силу чего на выходе "Равно" схемы 7формируется единичный сигнал, которым через элемент ИЛИ 37 открываетсяпо четвертому входу элемент И 32.Этот элемент открыт по первому и второму входам единичными сигналами спрямого выхода триггера 45 и инверсного выхода триггера 46 соответственно. Импульсом с выхода распределителя 18, поступающим через открытый элемент И 32 и элемент ИЛИ 39 насннхровход регистра 21, адрес ВГ=7принимается в регистр 21 через элементы ИЛИ 13. Одновременно импульсомс выхода элемента И 32 через элементИЛИ 40.устанавливается в нулевое состояние триггер 47,1Таким образом, в регистрах 17 и21 установлены граничные адреса подмассива записей с ключами, лежащими в пределах от 9 до 15, т.е. А, =5, Аьг Если искомый подмассив данных отсутствует, что отражено в пп, 7 и 12, то на выходе 59 формируется скгнац "Отсутствие подмассива". 8 14Пусть клич НГ=25, ключ ВГ=26, т.е.ключи границ подмассива большие ключа ВГ (Фиг. 2 а).Определение нижней границы производится аналогично рассмотренному споследовательным формированием адресов Р =5, Р, =7, Р =8, Р 4 =9, заносимыми в качестве адреса нижней гра-,ницы в регистр 2. При НГ=9 Кл(Кл 1,(24 с 25), При этом в счетчике 4 формируется адрес Р +1=9+1=10, которыйпередается в регистр 2, Так как ВГв регистре 1 стала больше НГ в регистре 2 то на выходе "Больше" схемы 42 сравнения формируется единичный сигнал, поступающий на выход 59"Отсутствие подмассива" и устанавливающий через элемент ИЛИ 40 триггер47 в нулевое состояние,Пусть ключ НГ=б, ключ ВГ=7, т,е,ключи нижней и верхней границ подмассива меньше ключа НГ (фиг.2 г).оОпределение нижней границы выполняется аналогично рассмотренному споследовательным формированием адресов Р=б, Р=2 и Р =1, заносимых вкачестве адреса верхней границы врегистрВ третьем цикле адреса в регистрах 2 и 1 становятся равными (НГ=ВГ==1), и на выходе "Равно" схемы 7 формируется единичный сигнал. Однакоэтот сигнал не влияет на состояниерегистра 21, так как триггер 45 находится в нулевом состоянии, закрываяэлемент И 32. При ВГ=1 Кл) Кл и(86)При этом в счетчике 4 формируется адрес Р -1=1-1=0, которыйпередается в регистр 1, Так как ВГв регистре 1 стало меньше ВГ в регистре 2, то на выходе "Меньше" схемы 43 сравнения формируется единичныйсигнал, поступающий на выход 59 "Отсутствие подмассива" и устанавливающий триггер 47 в нулевое состояние. Если требуется определить адрес только одной записи, то в регистры 5 и 20 принимаются одинаковые ключи. При этом схема 44 сравнения формирует на выходе "Равно" единичный сигнал, по которому после определения адреса нижней границы одновременно с установкой в "1" триггера 45 сигналом с выхода элемента И 35 через открытый элемент И 33 и элемент ИЛИ 40 триггер 47 устанавливается в нулевое состояние.15 486Единичный сигнал с инверсного выходаэтого триггера, поступающий на выход57, используется в этом режиме в качестве сигнала готовности устройствак выдаче записи по сформированномУочередному адресу, В устройство вновьпоступает сигнал пуска по входу 58.В дальнейшем чтение информации и, соответственно, количество импульсовпуска определяется разностью значений адресов верхней и нижней границв регистрах 17 и 21. После чтения записи.по последнему адресу на выходе59 формируется сигнал "Отсутствиеподмассива", который в данном режимеозначает завершение выдачи всех записей подмассива,Чтение записей подмассива можетпроизводиться многократно с предварительной подготовкой устройства кработе в режиме чтения,Рассмотрим работу устройства в режиме чтения записей.После установки триггера 47 вединичное состояние открывается элемент И 30 и через некоторое время навыходе распределителя 18 появляетсяимпульс. По этому импульсу черезоткрытый по инверсному входу элементИ 29 нулевым сигналом с выхода "Меньше схемы 7 в счетчик 4 принимаетсяадрес НГ+НГА = --- =НГ 4 2 15646Таким образом, после окончания режима поиска в регистре 17 зафиксиро, ван адрес нижней границы подмассива,а в регистре 21 - адрес верхнейграницы.5Последующие обращения к записямнайденного подмассива организуетсяследующим образом,По входу 56 подается сигнал режимачтения, по которому триггер 46 устанавливается в единичное состояние,При этом блокируется воздействие сигнала начальной установки на состояния регистров 5, 20, 17 и 21 черезэлемент. - И 34. Кроме того, блокируется прохождение импульсов с выходараспределителя 18 для записи информации в регистры 17 и 21 через элемен ты И 31 и 32 соответственно, 20Нулевым сигналомс инверсного выхода триггера 46 также блокируетсяпрохождение кода ключа из регистра 8через элементы И 27 на первый входсхемы 6 сравнения. Это дает возможность при наличии информации в ре гистре 5 поддерживать отличный отнуля код ключа через элементы И 25 навтором входе схемы б сравнения, При,этом на выходе "Меньге" данной схемы 30постоянно на все время работы устройства в режиме чтения удерживается:единичный сигнал. По этому сигналусчетчик 4 формирует очередной адресчтения для блока 9 памяти, а через35,2 иэ счетчика 4. Этот же адрес передается и в регистр 1 по сигналу, поступающему через открытый элемент 4 ОИ 28 и элемент ИЛИ 15 на управляющиевходы элементов И 24,Чтение информации выполняетсяследующим образом.После подачи сигнала установки ре 45жима по входу 56 в устройство поступает сигнал начальной установки повходу 52. По этому сигналу адрес начала подмассива А нг(адрес нижней границы), предварительно считанный из 50регистра 17 по входу 49, по входам51 и 50 одновременно принимается врегистры 1 и 2 соответственно, Затемв устройство подается по входу 58сигнал пуска. По этому сигналу произ 55водится чтение записи из блока 9памяти, которая поступает из регистра 8 на выход 60. По окончании чтения.триггер 47 устанавливается в "0". по которому производится обращениек блоку 9 памяти.Затем по второму импульсу с выхода распределителя 18 считанная запись принимается в регистр 8, передаваемая на выход 60.Так как элементы И 27 закрыты нулевым сигналом с инверсного выходатриггера 46, то на первом входе схемы 6 нулевой код ключа, а на втором -отличный от нуля. Поэтому на выходе11 иМеньше схемы сравнения формируется единичный сигнал, которым открытэлемент И 10, а в счетчике 4 разрешается режим сложения,По третьему импульсу с выхода распределителя 18 в счетчике формируется код адреса А =А,+1, который посту"пает через элементы ИЛИ 12 в регистр2 и через элементы И 24 в регистр 1,Прием в регистр 2 этого адреса производится по четвертому импульсу свыхода распределителя 18, проходящему, 1715через элементы И 10 и ИЛИ 14 на синхровход .регистра. В регистр 1 этот жеадрес принимается по тому же импульсу, проходящему через элементИ 28, элемент ИЛИ 15 на управляющиевходы элементов И 24, При этом навыходе "Меньше" схемы 7 удерживается нулевой сигнал, По четвертому импульсу с выхода распределителя 18,кроме того, с выхода И 28 через элемент ИЛИ 40 триггер 47 устанавливается в нулевое состояние. Единичныйсигнал с нулевого выхода триггера 47поступает на выход.51 и используетсяв качестве сигнала, разрешающего счи-тывание записи с выхода 60.Чтение записи по очередному адресу производится по второму импульсу пуска, поступающему по входу58, Работа устройства не отличаетсяот описанной. Чтение записей .будет.производиться, пока текущий адрес нестанет на единицу больше адреса верхней границы А , находящегося в регистре 21.Так, когда адрес обращения, принятый в счетчик 4 по импульсу с первого выхода распределителя 18, станетравным Аг, а по импульсу с третьего выхода распространителя 18 увеличится на единицу и примется в регистры 2 и 1 по импульсу с выходараспределителя 18, то на выходе"Меньше" схемы 42 сформируется единичный сигнал, поступающий на выход59, Этот сигнал означает завершениесчитывания записей всего подмассива.Повторное обращение к записямблока 9 памяти организуется в соответствии с рассмотренным после предварительной подготовки устройства к режиму чтения.Таким образом, предложенное устройство обеспечивает определение адреса записи с заданным ключом, а также граничных адресов подмассива записей, ключи которых находятся втребуемом интервале записей. Формула изобретенияУстройство для поиска данных, содержащее регистр адреса верхней границы, регистр адреса нижней границы, сумматор, реверсивный счетчик, регистр ключа нижней границы, информационный вход которого является вхо" дом ключа нижней границы устройства, 64648 18 5 10 15 20 25 30 35 40 45 50 55 две схемы сравнения, регистр информации, блок памяти, два элемента И,две группы элементов ИЛИ, три элемента ИЛИ, выходной регистр адреса нижней границы, выход ко".орого являетсявыходом адреса нижн:. границы устройства, распределитель импульсов и генератор импульсов, причем выход регистра адреса верхней границы подключенк входу первого операнда первой схемы сравнения и входу первого слагаемого сумматора, вход второго слагаемого которого соединен с входом второго операнда первой схемы сравненияи выходом регистра адреса нижней границы, .разряды информационного входакоторого соединены с выходами соответствующих элементов ИЛ 1 первойгруппы, первые входы которых являютсясоответствующими разрядами входа адреса нижней границы устройства, 1.-йразряд выхода сумматора (=2,3и+1; и - разрядность адреса блока памяти) подключен к (-1)-му разряду информационного входа реверсивного счетчика, разряды выхода которого соединены с соответствующимиразрядами адресного входа блока памяти, с вторыми входами элементовИЛИ первой группы и первыми входамиэлементов ИЛИ второй группы, вторыевходы которых являются соответствукщими разрядами входа адреса верхнейграницы устройства, установочный входкоторого подключен к первому входупервого элемента ИЛИ, выход которогосоединен с синхровходом регистра адреса нижней границы, выход "Меньше"первой схемы сравнения соединен спервым входом второго элемента ИЛИ,первый выход распределителя импульсовсоединен с синхровходом регистра информации, информационный вход которого подключен к информационному выходу блока памяти, второй выход распределителя импульсов соединен сосчетным входом реверсивного счетчика,третий выход распределителя импульсовподключен к первым входам первого ивторого элементов И, выходы которыхсоединены с вторым входом первого ипервым входом третьего элементов ИЛИсоответственно, суммирующий вход реверсивного счетчика соединен с вторым входом первого элемента И и свыходом "Меньше" второй схемы сравнения, выход "Больше" которой подключен к вычитающему входу реверсив