Устройство поиска заданного числа

идете 06 Р ения, о т л и ющеесяовышения быстроем, что ействия елью в негоадреса,четверть введены триггер, лемент 2 И-ИЛИ,пятый элемен- И, причем выход хемы сравнения му входу элемент счет третийты И, эл"Меньше" менты ИЛпервой одключе п ОСУДАРСТВЕННЫЙ НОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ(54) (57) УСТРОЙСТВО ПОИСКА ЗАДАННОГО ЧИСЛА, содержащее регистры схемы сравнения, два элемента И, элемент задержки, группу элементовИ, причем информационные входы устройства подключены к соответствующимвходам первого регистра, выходы которого соединены с первой группойвходов первой схемы сравнения, вторая группа входов которой соединенас выходами второго регистра, входыкоторого являются входами заданно-.го числа устройства, выход "Меньше"первой схемы сравнения соединен спервым входом первого элемента И,выход Больше" первой схемы сравне"ния подключен к первому входу второго элемента И, выходы третьегои четвертого регистров соединеныс первыми группами входов соответственно второй и третьей схем срав 2 И-ИЛИ и входу установки в единичное состояние триггера, прямой выходкоторого соединен с первым входомтретьего элемента И, второй входкоторого соединен с выходом "Больше"первой схемы сравнения и первымвходом четвертого элемента И, выход которого соединен с первымвходом первого элемента ИЛИ и суммирующим входом счетчика адреса,выходы которого являются информационными выходами устройства иподключены к вторым группам входоввторой и третьей схем сравнения,а установочные входы соединены свыходами элементов И группы, информационные входы которых соединеныс выходами соответствующих разрядовчетвертого регистра, а управляющие.входы подключены к входу запускаустройства, подключенному также квходу установки в ноль триггера ивторому входу первого элемента И,третий вход которого соединен с вьюходом элемента 2 И-ИЛИ и вычитающим входом счетчика адреса, а выходчерез элемент задержки подключенк первому входу пятого элемента И,выход которого является выходом разрешения считывания устройства,выход равенства первой схемы срав- .нения является выходом наличиячисла устройства и соединен с первым входом второго элемента ИЛИ, второй, третий и четвертый входы которого подключены к выходам соответственно первого, второго и третьегоэлементов И, прямой выход элементаИЛИ является выходом конца поискаустройства, а инверсный выход под-.1183955 ключен к вторым входам четвертогоэлемента И и элемента 2 И-ИЛИ, выход равенства второй схемы сравнениясоединен с вторым входом второгоэлемента ИЛИ, выход "Меньше" второйсхемы сравнения подключен к третьему входу четвертого элемента И, выход "Больше" второй схемы сравнения соединен с вторым инверсным Изобретение. относится к вычислительной технике и может быть использовано в качестве автономного блока ЭВМ при поиске заданных чисел вупорядоченнбм массиве. 5Цель изобретения - повышениебыстродействия устройства.На чертеже представлена схемапредлагаемого устройства.Устройство содержит регистр 1-4,счетчик 5 адреса, схемы 6-8 сравнения, триггер 9, группу элементовИ 10, элемент 2 И-ИЛИ 1" элементыИ 12-16, элементы ИЛИ 17 и 18, элемент 19 задержки, информационные15входы 20, вход 21 тактовых импульсов, вход 22 запуска, выходы 23-26.Устройство работает следующимобразом.В исходном состоянии в регистр 2заносится значение числа, котороетребуется найти в упорядоченном .по возрастанию массиве данных,в регистр 3 - адрес начала массива,а в регистр 4 - адрес конца массиваупорядоченных данных, На вход 2подается импульс запуска которыйустанавливает триггер 9 .в нулевоесостояние, открывает группу элементтов И 10, чере.з которую адрес начала ЗОмассива данных записывается в счетчик 5, и проходит через элементИЛИ 18, элемент задержки 9, элемент И 16 на выход 25, При появлении импульса считывания на выходе З25 из ЗУ ЭВМ по адресу, сформированному на выходах 26, считываетсязначение первого числа, которое запи.сывается по вхоцам 20 в регистр 1,В4 ОЕсли значение заданного числаменьше чем любое число в массиве,входом пятого элемента И и третьимвходом элемента 2 И-ИЛИ, четвертыйвход которого соединен с выходомнеравенства третьей схемы сравнения,выход равенства которой соединен свторым входом первого элемента И,вход тактовых импульсов устройстваподключен к объединенным информационным входам элемента 2 И-ИЛИ,то на первом выходе схемы 6 сравнения появится единичный сигнал, который установит в единичное состоя-.ние триггер 9 и поступит на входэлемента И 13, на второй вход которого поступает единичный сигнал спервого выхода схемы 7 сравнения,так как содержимое счетчика 5 ирегистра 3 равны. Элемент И 13 открыти единичный сигнал поступает навыход 24 через элемент ИЛИ 17 изапрещает с инверсного выхода элемента ИЛИ 17 прохождение тактовыхимпульсов через элементы И 15 и2 И-ИЛИ 11. Появление высокого потенциала на выходе 24 при отсутствииединичного сигнала на выходе 23означает, что в массиве нет заданного числа.Если значение заданного числабольше, чем любое число массива,то при записи первого числа в регистр 1 на втором выходе схемы 6сравнения будет единичный сигнал,который поступает на входы элементов И 12, 14 и 15. Элемент И 15открыт, так как на входы поступаютединичные сигналы с инверсноговыхода элемента ИЛИ 17 и второговыхода схемы 8 сравнения. Тактовыйимпульс поступает через элементИ 15 на суммирующий вход счетчика5 и через элементы ИЛИ 18, задержки 19 и И 16 на выход 25. Суммирующий вход счетчика 5 является суммирующим входом К -разряда,где К= -" +1 (Д оС- есть целаячасть числа с; и - разрядность счетчика. Для восьмиразрядного счетчика суммирующий вход подключен кпятому разряду, т.е, содержимое его.увеличивается при поступлении такфГтового импульса ца 2 = 16 грубый,счет). Второе считанное число, которое запишется в регистр 1, длярассматриваемого случая будет попорядковому номеру 17-м. Так как искомое число больше, то состояниесхем б и 8 сравнения не изменитсяи устройство выберет очередное число.Это состояние сохранится до тех пор,пока адрес счетчика 5 не станетравным или большим, чем адрес последнего числа массива,Если адрес счетчика 5 станет, равным адресу последнего числа массив,то с первого выхода схемы 8 сравнения высокий потенциал поступит навход элемента И 12. Так как считанное последнее число массива будетменьше, то на втором выходе схемысравнения останется высокий потенциал, элемент И 12 откроется и единичный сигнал появится на выходе24, что сигнализирует об окончаниианализа.Если адрес счетчика 5 при поступлении импульса на суммирующий вход станет больше адреса последнего числа, то единичный сигнал с третьего выхода схемы 8 сравнения поступит на шестой вход элемента 2 И-ИЛИ 11 и на инверсный вход элемента И 16, запрещая тем самым выборку числа за пределами зоны массива. Очередной тактовый импульс поступает через элемент 2 И-ИЛИ 11 на вычитающий вход счетчика 5 и содержимое счетчика уменьшается на единицу (точныйл счет) . До тех пор, пока адрес на выходе счетчика 5 не равен адресу последнего числа, записанному в регистре 4, состояние схемы 8 сравнения не меняется и импульс на выход 25 не поступает. Тактовые импульсы поступают на вычитающий вход счетчика 5 до тех пар, пока его содержимое не станет равным адресу последнего числа массива.Как только содержимое счетчика 5 и содержимое регистра 4 будут равны, на первом выходе схемы 8 сравнения появится единичный сигналУкоторый поступит на вход элемента И 12, одновременно исчезнет сигнал на инверсном входе элемента И 16 и последнее число массива запишется в регистр 1. Так как схема б сравнения не изменит своего состояция, то едицичцый сигнал с выходэлемента И 12 через элемент ИЛИ 17поступит на выход 24 устройства,Поиск числа ца этом заканчивается. Если значение заданного числаесть в массиве чисел, то после записи первого числа в регистр 1 возможно следующее: если заданное числсравно первому числу массива, топоявится сигнал на третьем выходесхемы б сравнения, который поступитна выход 23 устройства, сигнализируя о том, что данцое число естьв массиве и оно записано в ЗУ ЭВИпо адресу, сФормированному на выходах 26, и через элемент ИЛИ 17на выход 24, сигнализируя об окончании работы устройства, а такжес инверсного выхода элемента ИЛИ 17 20низкий потенциал запретит дальнейшее поступление тактовых импульсовчерез элементы И 15 и 2 И-ИЛИ 11;если значение числа в регистре 1меньше, чем значение заданного числа в регистре 2, то со второго выхода схемы 6 сравнения единичныйсигнал поступит на вход элемента И 15через который тактовые импульсыбудут поступать на суммирующий входсчетчика 5 и, проидя элементы ИЛИ 18,задержки 19 и И 16, на выход 25, Прлпоявлении импульса считывания навыходе 25 из ЗУ ЭВИ по адресу, Формируемому счетчиком 5 на выходах 35 26, считывается очередное число,которое записывается по входам 20 врегистр 1. Если очередное числоменьше заданного числа, то устройство работает аналогична описанномуи т,д. Если очередное поступившеечисло больше заданного числа, то спервого выхода схемы 6 сравненияединичный сигнал установит триггер 9в единичное. состояние и разрешитпоступление тактового импульса свхода 21 через элемент 2 И-ИЛИ 11на вычитающий вход счетчика 5 и одновременно через элементы ИЛИ 18,задержки 19 и И 16 на выход 25 устройства. При появлении импульсовсчитывания на выходе 25 из ЗУ ЭВИпо адресу, формируемоМу счетчиком5 на выходах 26, считывается число,которое записывается по входам 2055 в регистр 1. Тактовые импульсы поступают на вычитающий вход счетчика 5 сдо тех пор, пака в регистр 1не запишется число, равное или мень"1183955 ВНИИПИ Заказ 6271/48 Тираж 709 Подписное нал ППП "Патент", г.ужгород, ул.Проектная, 4 шее заданного числа. Если в регистр1 поступит. число, равное заданномучислу, то единичный сигнал с третьего восхода схемы б. сравнений поступит на выход 23 и через элементИЛИ 17 на выходи одновременнос инверсного выхода элемента ИЛИ 17низкий потенциал запретит дальнейшее поступление тактовых импульсовчерез элементы. И 15 и 2 И-ИЛИ 11.Наличие единичных сигналов на выходух 23 и 24 означает, что процесспоисКа закончен и по адресу, рфорьированному на. выходах 26, в Зу ЭВМзаписано число, равное заданному.Если в регистр 1 поступит число,меньшее заданного, то высокий потенциал с второго выхода схемы 6 сравнения через открытый элемент И 14(триггер 9 в единичном состоянии)поступит через элемент ИЛИ 17 навыход 24 и с инверсного выхода элемента ИЛИ 17 низкий потенциал запретит поступление тактовых импульсов.Наличие единичного сигнала на вы ходе 24 при его отсутствии на выходе 23 означает, что поиск закончен,но заданного числа в массиве нет.В случае отсутствия заданногочисла на выходах 26 формируется 15 адрес числа, ближайшего к заданному,что позволяет использовать предла"гаемое устройство для поиска чисел,ближайших к заданному.