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

(5)5 0 06 Е 15/40 ГОСУДАРСТВЕННЫЙПО ИЗОБРЕТЕНИЯМПРИ ГКНТ СССР ОМИТЕТОТКР ЬП ИЯМ 6 Ж ВТЕЙТНй 1 БЛ ИСАНИЕ ИЗОБРЕТЕН ВТОРС СВИДЕТЕЛЬСТВУ(56) Авторское свидетельство СССРМ 1564648, кл. 6 05 Г 15/40, 15.08,88(54) УСТРОЙСТВО ДЛЯ ПОИСКА ДАННЫХ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в системах управления базами данных, Цель изобретения - повышение быстродействия за счет предварительного анализа соотношения ключей границ исходного массива и искомого подмассива. Новым в устройстве является использование блока анализа, содержащего четыре триггера, двесхемы сравнения, два блока элементов И, девять элементов И, элемент ИЛИ и четыре элемента задержки, и его связей с остальными элементами схемы устройства, Устройство работает в режиме поиска адресов подмассива данных, записи которых лежат в заданном интервале значений идентификаторов (ключей) записей, и в режиме чтения найденных записей. Режим поИзобретение относится к автоматике и вычислительной технике, может быть использовано в системах управления базами данных и является усовершенствованием устройства по авт, св. М 1564648.Целью изобретения является повышение быстродействия устройства за счет предварительного анализа соотношения иска начинается с предварительного анализа соотношения ключей искомого подмассива и исходного массива. На основании сигналов соотношения этих ключей формируются граничные адреса подмассива либо сигнала об отсутствии записей, либо определяется режим поиска одной или обеих его границ. Поиск адресов производится делением области поиска в каждом цикле работы устройства примерно вдвое. Область поиска определяется на основе сравнения заданного и считанного ключей, При необходимости поиска обеих границ вначале определяется адрес первой записи (нижняя граница), а затем - адрес последней записи (верхняя граница) подмассива, При чтении информации предварительно в регистры адресов нижней и верхней границ массива заносится адрес записи подмассива из выходного регистра адреса нижней границы. По сигналам пуска производится обращение к памяти, чтение данных в регистр информации и формирование очередного адреса записи. Если этот адрес превышает адрес верхней границы подмассива, в устройстве формируется сигнал об отсутствии подмассива, по которому завершается считывание записей. 2 табл 3 ил. ключей границ исходного массива и искомого подмассива,На фиг. 1 показана структурная схема устройства; на фиг. 2 - функциональная схема блока анализа; на фиг. 3 - примеры размещения массива информации в блоке памяти.Устройство содержит регистр 1 адреса верхней границы, регистр 2 адреса нижнейменты И 24 в регистр 1, Прием в регистр 2этого адреса производится по четвертомуимпульсу с выхода распределителя 18, проходящему через элементы И 10 и ИЛИ 14 наСинхровход регистра. В регистр 1 этот жеадрес принимается по тому же импульсу,проходящему через элемент И 28, элементИЛИ 15 на управляющие входы элементовИ 24, При этом на выходе "Меньше" схемы7 удерживается нулевой сигнал,По четвертому импульсу с выхода распределителя 18, кроме того, с выхода элемента И 28 через элемент ИЛИ 40 триггер47 устанавливается в нулевое состояние.Единичный сигнал с нулевого выходатриггера 47 поступает на выход 5 и используется в качестве сигнала, разрешающегосчитывание записи с выхода 60,Чтение записи по очередному адресупроизводится по второму импульсу пуска,поступающему по входу 58, Работа устройства не отличается от описанной. Чтениезаписей будет производиться, пока текущийадрес не станет на единицу больше адресаверхней границы Авг, находящегося в регистре 21,Так, когда адрес обращения, принятойв счетчик 4 по импульсу с первого выходараспределителя 18, станет равным Аг, а поимпульсу с третьего выхода распределителя18 увеличится на единицу и принимается врегистры 2 и 1 по импульсу с выхода распределителя 18, то на выходе "Меньше" схемы42 сформируется единичный сигнал, поступающий на выход 59 "Отсутствие подмассива". Этот сигнал означает завершениесчитывания записей всего подмассива.Повторное обращение к записям блока9 памяти организуется в соответствии с рассмотренным после предварительной подготовки устройства к режиму чтения.Формула изобретенияУстройство для поиска данных по авт,св. ЛЬ 1564648, отличающееся тем,что, с целью повышения быстродействия засчет предварительного анализа соотношения ключей границ исходного массива и искомого подмассива, оно дополнительноф содержит блок анализа, разряды адресноговыхода которого соединены через МОНТАЖНОЕ ИЛИ с одноименными разрядамивыхода реверсивного счетчика, разрядыключа информационного выхода блока памяти подключены к одноименным разрядамвхода ключа блока анализа, адресные входыверхней и нижней границ которого соединены с выходами регистров адреса верхней инижней границ соответственно, выходы регистров ключей нижней и верхней границподключены к входам ключей нижней и вер 50 55 1015 202530354045 хней границ соответственно блока анализа,первый выход управления которого соединен с инверсным входом третьего элемента И, первый, второй, третий и четвертый входы управления блока анализа соединены соответственно с инверсным выходом триггера режима, входом пуска устройства,входом поиска устройства и инверсным выходом триггера пуска, второй, третий, четвертый, пятый, шестой и седьмой выходы управления блока анализа подключены соответственно к выходу седьмого элемента И, к инверсному входу пятого элемента И и второму входу восьмого элемента И, к четвертому входу восьмого элемента ИЛИ, к третьему входу седьмого элемента ИЛИ, к третьему входу пятого элемента ИЛИ и к третьему входу шестого элемента ИЛИ, причем блок анализа содержит первую и вторую схемы сравнения, первые входы которых объединены и поключены к входу ключа блока анализа, а вторые входы являются входами ключей нижней и верхней границ соответственно блока анализа, девять элементов И. элемент ИЛИ, выход которого является четвертым выходом управления блока анализа, четыре элемента задержки,первый и второй блоки элементов И, выходы которых объединены и подключены к адресному выходу блока анализа, триггер нижней границы, триггер верхней границы, прямой выход которого является третьим выходом управления блока анализа, первый и второй триггеры управления, единичные и нулевые входы которых объединены и подключены к третьему входу управления блока анализа,прямой выход первого триггера управления является первым выходом управления блока анализа и подключен к первым управляющим входам первого и второго блоков элементов И, вторые управляющие входы которых соединены соответственно с прямым и инверсным выходами второго триггера управления, выход первого элемента И блока анализа соединен с единичными входами триггеров нижней и верхней границ и через первый элемент задержки - с первыми входами третьего, шестого и восьмого элементов И, с единичным входом второго триггера управления и входом второго элемента задержки, выход которого подключен к первым прямым входам второго, седьмого и девятого элементов И и к входу третьего элемента задержки, выход которого соединен с вторым входом четвертого элемента И, третьим входом пятого элемента И и через четвертый элемент задержки - с нулевымвходом первого триггера управления, выход "Меньше" первой схемы сравнения блока анализа подключен к второму прямому вхо"Нет данных" Таблица 2 ду второго элемента И и второму входу шестого элемента И, а выход "Равно" - к второму входу восьмого элемента И, выход "Больше" второй схемы сравнения блока анализа соединен с вторым входом третьего элемента И и вторым прямым входом седьмого элемента И, а выход "Равно" - с вторым прямым входом девятого элемента И, выход которого подключен к седьмому выходу управления блока анализа и первому входу элемента ИЛИ, второй вход которого соединен с выходом восьмого элемента И и с шестым выходом управления блока анализа, пятый выход управления которого соединен с выходом шестого элемента И, объединенным с выходом седьмого элемен. та И, инверсный вход которого соединен с четвертым входом управления блока анализа, инверсными входами девятого и второго Номер Соотношение ключейи/п элементов И, прямой выход триггера нижней границы, нулевой вход которого подключен к выходу второго элемента И, соединен с первым входом четвертого элемента И, выход которого является вторым выходом управления блока анализа, и с вторым входом пятого элемента И, первый вход которого подключен к и рямому выходу триггера верхней границы, нулевой вход которого соединен с выходом третьего элемента И, выход пятого элемента И подключен к третьему входу элемента ИЛИ, информационные входы элементов И первого и второго блоков подключены соответственно к адресным входам нижней и верхней границ блока анализа, в котором его первый и второй входы управления соединены соответственно с первым и вторым входами первого элемента И. 1 Поиск НГ, ВГ = ВгаО Поиск НГ ВГ ВГо нрн КлНГ( Клвга В = ВГ, при КлНГ = КлВГо НГ) ВГ - формирование сигналао Поиск Н Г, поиск ВГо вг = вговг = вгпоиск ВГ прн КлВГ ) КлНГВГНго при КлВГ = КлнГ/о= 9 н А. Пекарь Ре ектор М,Ш ш аказ 1714 Тираж 417 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ С 113035, Москва. Ж, Раушская наб., 4/5 Р,= йграницы, сумматор 3, реверсивный счетчик 4, регистр 5 ключа нижней границы, две схемы б и 7 сравнения, регистр 8 инфоома ции, блок 9 памяти, два элемента И 10 и 11, две группы элементов ИЛИ 12 и 13, первый 14, второй 15 и третий 16 элементы ИЛИ, выходной регистр 17 адреса нижней границы, распределитель 18 импульсов, генератор 19 импульсов, регистр 20 ключа верхней границы, выходной регистр 21 адреса верхней границы, шесть групп элементов И 22 27, с третьего по десятый элементы И 28-35, с четвертого по восьмой элементы ИЛИ 36- 40, третью группу 41 элементов ИЛИ, 1 ретью 42, четвертую 43 и пятую 44 схемы сравнения, триггер 45 управления, григгер 46 режима, триггер 47 пуска, вход 48 ключа нижней границы, выход 49 адреса нижней границы, вход 50 адреса нижней границы. вход 51 адреса верхней границы, установочный вход 52, вход 53 ключа верхней границы, выход 54 адреса верхней гра. ницы, вход 55 поиска и третий вход управления блока анализа, вход 56 чтения, выход 57 готовности и четвертый вход управления блока анализа, вход 58 пуска и второй вход управления блока анализа, выход 59 признака отсутствия подмассива, выход 60 записи, блок 61 анализа, адресный выход 62 блока анализа, вход 63 клю гэ блока анализа, адресные входы 64 и 65 верхней и нижней границ соответственно блока анализа, входы бб и 67 ключей нижней и верхней границ соответственно блока анализа, первый выход 68 управления блока анализа, первый вход 69 управления блока анализа, второй 70, третий 71, четвертый 72, пятый 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 памяти размещен массив, каждая ячейка которого состоит из служебного и информационноо полей. Служебное поле используется для указания кода ключа (идентифика 1 ора). а информационное - для размещения смыслового содерч:эния ицентифицируеглой части записи Зэч си набора данных отсортированы по возрос танию эна 5 10 15 20 25 30 35 40 45 50 55 чений ключей, Это означает, что если 1-язапись размещена по К-му адресу, то ( +1) я запись хранится по ( + 1)-му адресу,причем ключ (1)-й записи больше ключа1-й записи, т, е. функция адреса блока 9памяти линеино зависит от приращениязначений кода ключа,Задача состоит в определении граничных эдресов подмассива записей, ключи которых находятся в заданном интервалезначений.Для нахождения граничных адресовподмассива сначала осуществляется анализсоотношения ключей границ исходного массива и искомого подмассива, а затем осуществляется поиск необходимых адресовгран:лц, используя дихотомический поиск.При таком поиске размер области поиска в результате каждой проверки сокращаетсь примерно вдвое,Введем следующие обозначения: НГ, -нижняя граница (адрес первой записи исходного массива); ВГО - верхняя граница(адрес последней записи исходного массива); Р; - адрес блока памяти- го цикла устройства; Л, - ацрес первой записи1 одмассива; Аг - адрес последней записиподмассива; Кли - ключ исходной записиподмассива; Кл - ключ считанной записи иэблока памяти.Устройство работает в двух режимах;поиска и чтения информации, Установка режима производится по входам 55 и 56, Приподаче на вход 55 импульса в устройствоустанавливается режим поиска данных, Принеобходимости чтения подмассива выделенных записей по входу 56 подается импульс, усганавливающий триггер 46 режимав единичное состояние.Работа устройства в режиме поискаподмассива требуемых записей состоит вследующем.В исходном состоянии распределитель8 импульсов, регистры 8, 17, 21, счетчик 4,триггеры 47, 45, 76 устанавливают в состояние0" (не показано).На входы 48 и 53 подаются коды ключейнижней и верхней границ искомого подмассива соответственно, На входы 51 и 50 поступают коды адресов верхней и нижнейграниц исходного массива.По входу 35 поступает импульс, по которому триггер 46 устанавливается в нулевоесостояние, определяя режим поиска записей,ключи которых лежат в заданном интервале,Единичным сигналом с инверсного выхода1 риг ера 46 открыты элементы И 27, 31, 32, 34,а в блоке 61 анализа - элемент И 84,Кроме того, по импульсу с входа 55 вблоке 61 устанавливаются в нулевое состо 165811051015 20 25 30 35 40 45 50 55 яние триггер 88, а в единичное - триггер 16, единичным сигналом с прямого выхода которого блокируется по инверсному входу элемент И 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, устанавливающего триггер 41 в единичное состояние, Единичным сигналом с прямого выхода триггера 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 устанавливается адрес Н Го.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сохраняется значенье адреса ВГо5 10 15 20 25 30 35 40 45 50 55 Одновременно сигналом с выхода элемента И 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).С выхода элемента 94 задержки. крометоо, задержанным импульсом пуска устанаьливэегся в единичное состояние триггер77, определяя анализ соотношения ключейнижней границы исходного массива с ключал 1 и искомого подмассива, Результаты анализа будут учтены, если триггер 47удерживается в единичном состоянии, т. е.когда при сравнении определен режим работы устройства по поиску верхней границыискомого подмассива,Установкой ь единичное состояниериггерэ 47 обеспечивается передача адрес: нижней границы массива с выхода реги 1658170стра 2 через открытый блок элементов И 82 и МОНТАЖНОЕ ИЛИ на адресный вход блока 9 памяти.Считанная информацияключ НГ с выходов блока 9 памяти - поступает на первые входы схем 80 и 81 сравнения, на вторых входах которых находятся ключи нижней и верхней границ соответственно искомого подмассива.В зависимости от соотношения ключей на входах схем 80 и 81 сравнения формируются сигналы, определяющие режим работы устройства при поиске нижней границы искомого подмассива,5. Кл Н Г = Кл В Г, что соответствует двенадцатой строке табл, 1.При этом на выходе "Равно" схемы 81 сравнения формируется единичный сигнал, открывающий элемент И 93, Задержанным импульсом пуска с выхода элемента 95 задержки через время, равное времени переходных процессов в блоке 9 памяти и схеме 81 сравнения, через элемент ИЛИ 39 по синхровходу регистра 2 1 обеспечивается запись в него адреса НГ 0 с выходов блока элементов И 82 через МОНТАЖНОЕ ИЛИ и элементы ИЛИ 13.В регистре 17 сохраняется значение адреса НГ.Одновременно этим же сигналом через элементы ИЛИ 89 и 40 устанавливается в нулевое состояние триггер 47, единичный сигнал с инверсного выхода которого поступает на выход 51 в качестве сигнала готовности устройства к режиму считывания,6. КлНГ 0КлВГ, что соответствует тринадцатой строке табл. 1.При этом на выходе "Больше" схемы 81 сравнения формируется единичный сигнал, открывающий элемент И 91, задержанным импульсом пуска с выхода элемента 95 задержки через открытый элемент И 91 и элементы ИЛИ 36 и 40 устанавливает триггер 47 в нулевое состояние и поступает на выход 59 устройства в качестве сигнала "Отсутствие подмассива".7. КлНГоКлНГ, что соответствует четвертой, пятой и восьмой строкам табл. 1.При этом на выходе "Меньше" схемы 80 сравнения формируется единичный сигнал, открывающий элемент И 85, через который задержанным импульсом с выхода элемента 95 задержки устанавливается в нулевое состояние триггер 78, что свидетельствует о необходимости поиска нижней границы подмассива.8. Если же КлНГКлНГ, то на выходе "Меньше" схемы 80 сравнения устанавливается нулевой сигнал, закрывающий элемент И 85, чем триггер 78 удерживается в единич триггере 47,10 152025 303540455055 ном состоянии, Это означает, что нет необходимости поиска нижней границы, т. е. в регистре 11 сохраняется адрес нижней границы (первая, вторая и третья, девятая, десятая и одиннадцатъе строки табл. 1).В результате анализа соотношения ключей исходного массива и искомого подмассива триггеры 78 и 79 могут находиться либо в нулевых, либо в единичных состояниях, определяя в конечном итоге режимы работы устройства, что показано в табл, 2,В соответствии с табл. 2 завершение работы блока 61 производится следующим образом,Задержанным импульсом пуска с выхода элемента 96 задержки через открытыйэлемент И 87 единичным сигналом с единичного выхода триггера 78 и МОНТАЖНОЕ ИЛИ триггер 45 устанавливается в единичное состояние. Это означает, что устройство принудительно переводится в режим поиска верхней границы, так как нижняя граница уже гто результатам работы блока 61 находится в регистре 17,Если только триггер 79 находится в единичном состоянии, то единичным сигналом с его единичного выхода блокируется по инверсному входу элемент И 32 для исключения влияния импульса с выхода распределителя 18 и через МОНТАЖНОЕ ИЛИ с выходом схемы 44 сравнения открывается по второму входу элемент И 33. Это необходимо для того, чтобы после определения нижней границы и размещения ее врегистре 17 завершить работу устройства, так как верхняя граница уже находится врегистре 21,Если оба триггера 78 и 19 находятся в единичном состоянии, означающем наличие нижней и верхней границ в регистрах 17 и 21 соответственно, то импульсом с выходаэлемента 96 задержки через открытый элемент И 88 и элементы ИЛИ 89 и 40 устанавливается в нулевое состояние триггер 47.Время задержки элементом 96 задержки определяется временем переходных процессов в элементах И 85 (86) и триггерах 78 (79).Если оба триггера 78 и 79 находятся внулевых состояниях, то устройство обеспечивает вначале поиск нижней, а затем верхней границ,Кроме того, импульсом с выхода элемента 96 задержки через элемент 97 задержки устанавливается в нулевое состояние триггер 76,Время задержки элемента 91 задержки определяется временем переходных процессов в элементах И 88, ИЛИ 89 и 40 иПосле установки триггера 76 в нулевоесостояние нулевым сигналом с его прямоговыхода открывается по инверсному входуэлемент И 30.Как указывалось, устройство обеспечивает поиск нижней и верхней границ одинаковым образом,Рассмотрим работу устройства при поиске обеих границ, т. е, когда оба триггера78 и 79 находятся в нулевых состояниях, 10При поиске нижней границы с помощьюсумматора 3 определяется сумма ВГоНГО,которая со сдвигом на один разряд вправо(в сторону младших разрядов) заносится вс летчик 4 по первому импульсу с выхода 15распределителя 18. Этот импульс поступаетчерез открытый элемент И 29 по инверсному входу нулевым сигналом с выхода "Меньше" схемы 7 сравнения (так как адрес ВГ,больше адреса НГо) на вход разрешения 20записи счетчика 4,Таким образом, в счетчике 4 фиксируется код адресаВГ +НГ2 25где Х) - ближайшее целое, меньшее либоравное Х,По э 1 ому адресу производится обращение в блок 9 памяти, и считанная запись сключом Клз принимается в регистр 8 по еторому импульсу с выхода распределителя 18,поступающему на синхровход регистра 8,Так как триггер 45 находится в нулевомсостоянии, то единичным сигналом с егоинверсного выхода открыты элементы И 25, 35и код ключа НГ с выходов регистра 5 поступает на второй вход схемы б сравнения,Первый вход этой схемы связан с выходомкода ключа регистра 8 через открылгые вданном режиме элементы И 27, 40Посредством схемы б производитсяпроверка соотношения Кл и ключа искомойграницы. При эгом возможны следующиеситуации,А. Коды ключей совпадают, 45В этом случае на выходе "Равно" схемыб формируется единичный сигнал. которымчерез элемент ИЛИ 16 открывается по четвертому входу элемент И 31, Так как этоэлемент открыт также по первому входу единичным сигналом с инверсного выхода триггера 45 по второму входу единичнымсигналом с инверсного выхода триггера 46,то по очередному импульсу с выхода распределителя 18, поступающему через элементы И 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 и используется в качестве сигнала готовносги устройства к выдаче информации,В. Код ключа считанной записи меньше кода ключей искомой границы,При этом на выходе "Меньше" схемы б формируется единичный сигнал, Данным сигналом открывается элемент И 10 и разрешается режим сложения в счетчике 4.По импульсу с выхода распределителя 18 в счетчике 4 формируется сумма Р+1 = Р + 1, которая через элементы ИЛИ группы 12 поступает в регистр 2 в качестве очередной нижней границы поиска по импульсу с выхода распределителя 18.После этого поиска границы производи 1 ся в очередном такте генератора 19,С, Код ключа считанной записи больше кода ключа искомой границы.В этом случае на выходе "Больше" схемы б формируется единичный сигнал, открывающий элемент И 11 и устанавливающий режим вычитания счетчика 4. По импульсу с выхода распределителя 18 в счетчике 4 формируется разностьР 1 = Р; - 1, которая через элементы И 24принимается в регистр 1 в качестве верхней границы для очередного цикла работы устройства. Прием адресапроизвод.тся по импульсу с выхода распределителя 18, поступающему через элементы И 11 и ИЛИ 15 на управляющие входыэлеметов И 24,На первом этапе поиска нижней границы устройство работает следующим образом,По импульсу с выхода распределителяВГ +НГ18 адрес Р 1 = -из сумма. ора23 принимается в счетчик 4, Это обусловлено тем, что ВГНГ, поэтому на выходе "Меньше" схемы 7 сравненич устанавливается нулевой сигнал, открывающий по инверсному входу элемент И 29, выходом подключенный к входу разрешения записи счетчика 4,По адресу Р 1 производится обращение к блоку 9 памяти, и считанная запись принимается в регистр 8 по импульсу с выхода распределителя 18. Код ключа считанной записи через открытые элементы И 27 подается на первый вход схемы б сравнения НЪ второй вход схемы б сравнения подается код ключа нижней границы из регистра 5 через открытые элементы И 25 единичным сигналом с инверсного выхода триггера 45,Если ключи совпадают, то на выходах "Меньше" и "Больше" схемы б устанавливаются нулевые сигналы, блокирующие эл менты И 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. Кроме того, на второй вход схемы б через элементы И 26, открытые теперь же единичным сигналом с прямого выхода триггера 45, подается код ключа верхней грзчицы из регис ра 20.Таким образом, после окончания импульса с выхода распределителя 18 на первом входе схемы б присутствует код ключа считанной записи по адрес, Р 1, а на втором входе - код ключа верхней границы, а так как ключ НГ меньше ключа ВГ, то на выходе "Меньше" схемы 6 формируется единичный сигнал. И е дальнейшем (в соответствии с рассмотренным пунктом В) в регистре 2 фиксируется код адреса Р 1+ 1 по импульсу с выхода распределителя 18,После этого снова появляется импульс нэвыходе распределителя 18, по которому сфорНГ+ВГмированный адрес Р 2 -25 где НГ = Р 1 + 1, ВГ = ВГО, принимается всчетчик 4,В дальнейшем устройство работает аналогично описанному.После завершения поиска верхней гра 10 ницы фиксацией ее в регистре 21 импульсомс выхода элемента И 32 устанавливается внулевое состояние триггер 46 и через элемент ИЛИ 40 гасится триггер 47,Рассмотрим работу устройства, когда в15 массиве с НГ=1, ВГ=9 необходимо определить нижнюю границу, начиная с которойключи записей больше заданного.На фиг, За показана условная структурамассива с НГ=1, ВГ=9, а внутри каждой ячей 20 ки указаны значения ключей, Требуется определить адрес, начиная с которого всеключи больше Кл=15,Так как КлНГоКлНГ (815), то позавершении предварительного этапа триг 25 гер 78 оказывается в нулевом состоянии,определяя тем самым режим поиска нижнейграницы,В соответствии с описанным значение впервом цикле30 1+92Так как КлзКли (1615), то в счетчике4 формируется значение Р 1-1 = 5 - 1 = 4,которое передается в регистр 1 в качестве35 адреса верхней границы.На втором цикле величина1+4Р 22- 2 передается в счетчик 4,Так как КлзКл(1015), то в счетчике40 4 формируется значение Р 2 + 1 = 2 + 1 = 3,которое в качестве нижней границы поступает в регистр 2.8 третьем цикле величина3+445 Рз = 2 - = 3 передается в счетчик 4,Так как КлКл (12 :15), то в счетчике 4образуется значение Р,+1 = 3+ 1 = 4, котороев качестве нижней границы поступает в регистр 2,50 В течение этих трех циклов на выходе"Меньше" схемы 7 сравнения присутствуетнулевой сигнал, которым элемент И 29удерживается в открытом состоянии по инверсному входу.55 8 третьем цикле НГ = ВГ, на выходе"Равно" схемы 7 сравнения формируетсяединичный сигнал, открывающий через элемент ИЛИ 37 элемент И 32 по четвертомувходу. Однак:1 тэк как триггер 45 находитсяв нулевом состоянии, элемент И 32 заблоки10 15 20 рован нулевым сигналом с прямого выходаэтого триггера.В четвертом цикле формируется адрескоторый передается в счетчик 4.Так как КлзКли (1415), то всчетчике 4 формируется значение адресаР 4 + 1 - 4 + 1 - 5, которое принимается вкачестве нижней границы в регистр 2. При этом оказывается,что ВГНГ (10 16) и на выходе "Меньше" схемы 1 устанавливается единичныйсигнал. Данный сигнал блокирует по инверсному входу элемент И 29, запрещающий прием в счетчик 4 очередного4+5значения Р 5 -2-4, сохраняя внем адрес Р 4 = 5.Одновременно с сигналом с выхода"Меньше" схемы 7 через элемент ИЛИ 16открывается элемент И 31 по четвертомувходу. Так как этот элемент, кроме того,открыт по первому входу единичным сигналом с инверсного выхода триггера 46, а повторому - единичным сигналом с инверсного выхода триггера 45, то по импульсу свыхода распределителя 18, поступающемучерез этот элемент И 31 и элемент ИЛИ 30на синхровход регистра 17, производитсяприем в него адреса нижней границы подмассива Р 4- 5.После этого переключается триггер 45 вединичное состояние, обеспечивая поискадреса верхней границы.Одновременно с установкой в "1" триггера 45 адрес ВГо = 9 через элемент И 23передается в регистр 1,Единичным сигналом с единичного выхода триггера 45 открываются элементы И26, и код ключа верхней границы поступаетна второй вход схемы 6 сравнения. На первый вход схемы б после приема в регистр 8по второму импульсу с выхода распределителя 18 записи из блока памяти 9 поступаеткод ключа Клз = 16 через элементы И 27,Пусть /требуется определить адресверхней границы, ключ которой Кли = 21(фиг. Зб).Так как КлВГКлВГ (2421), то позавершении предварительного этапа триггер 79 оказывается в нулевом состоянии,определяя тем самым режим поиска верхней границы.Так как КЛзКли(1621), то на выходе"Меньше" схемы 6 формируется единичныйсигнал. При этом в счетчике 4 образуетсяадрес Р 1- 5+ 1 = 6,Этот адрес принимается в регистр 2 вкачестве нижней границы. 25 30 35 40 45 50 55 В очередном цикле формируется ад 6+9рес Р 2 =2=1 поступающий в счетчик 4,Так как КлзКли (2021), то в счетчике4 формируется адрес Р 2 + 1 = 7 + 1 = 8,передаваемый в регистр 2 в качестве нижней границы.В следующем цикле Рз -8+92- 8Так как КлзКли (2221), то в счетчике 4 формируется адрес Рз -1 = 8-1 =1, который поступает в регистр 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 сравнения, так как ВГо НГ (2425), открывающий элемент И 90, что обеспечивает передачу импульса с выхода элемента 94 задержки через элемент ИЛИ 36 на выход 59 "Отсутствие подмассива",Пусть ключ НГ = 6, ключ ВГ = 7, т. е. ключи нижней и верхней границ подмассива меньше ключа НГоВ данном случае на этапе предварительного анализа на выходе "Больше" схемы 81 сравнения формируется единичный сигнал, так как НГоВГ (8 7), открывающий элемент И 91, что обеспечивает переда5 10 15 20 25 30 35 40 45 50 55 чу импульса с выхода элемента 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 разрешается режим сложения.По третьему импульсу с выхода распределителя 18 в счетчике формируется код адреса А 2 - А 1 + 1, который поступает через элементы ИЛИ 12 в регистр 2 и через эле