Устройство поиска заданного числа Советский патент 1985 года по МПК G06F7/06 

ключей к вторым входам четвертого элемента И и элемента 2 И-ИЛИ, выход равенства второй схемы сравнения соединен с вторым входом второго элемента ИЛИ, выход Меньше второй схемы сравнения подключен к третьему входу четвертого элемента И, выход Больше второй схемы сравнения соединен с вторым инверсным

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

УСТРОЙСТВО ПОИСКА ЗАДАННОГО ЧИСЛА, содержащее регистры схемы сравнения, два элемента И, элемент задержки, группу элементов И, причем информационные входы устройства подключены к соответствующим входам первого регистра, выходы которого соединены с первой группой входов первой схемы сравнения, вторая группа входов которой соединена с выходами второго регистра, входы которого являются входами заданного числа устройства, выход Меньше первой схемы сравнения соединен с первым ВХОДОМпервого элемента И, вькод .Больше первой схемы сравнения подключен к первому входу второго элемента И, выходы третьего и четвертого регистров соединены с первыми группами входов соответственно второй и третьей схем сравнения, отличающееся тем, что, с целью повышения быстродействия, в него введены триггер, счетчик адреса, элемент 2 И-ИЛИ, третий, четвертый, пятый элементы И, элементы ИЛИ, причем выход Меньше первой схемы сравнения подключен к первому входу элемента tlfiT r. Tf .S-Jf;..,...73 ,, /а, Вй4 2 И-ИЛИ и входу установки в единичное состояние триггера, прямой выход которого соединен с первым входом третьего элемента И, второй вход которого соединен с выходом Больше первой схемы сравнения и первым входом четвертого элемента И, выход которого соединен с первым входом первого элемента ИЛИ и суммирующим входом счетчика адресе, ВЫХОДЫ которого являются информационными выходами устройства и подключены к вторым группам входов второй и третьей схем сравнения, i а установочные входы соединены с выходами элементов И группы, инфор(Л мационные входы которых соединены с выходами соответствующих разрядов четвертого регистра, а управляющие входы подключены к входу запуска устройства, подключенному также к, входу установки в ноль триггера и второму входу первого элемента И, 00 третий вход которого соединен с высо со ходом элемента 2 И-ИЛИ и вычитающим входом счетчика адреса, а выход СД 01 через элемент задержки подключен к первому входу пятого элемента И, выход которого является выходом разрешения считьшания устройства, выход равенства первой схемы сравнения является выходом наличия числа устройства и соединен с первым входом второго элемента ИЛИ, второй, третий и четвертый входы которого подключены к выходам соответственно первого, второго и третьего элементов И, прямой выход элемента ИЛИ является выходом конца поиска устройства, а инверсный выход под-..

Изобретение относится к вычислительной технике и может быть исполь зовано в качестве автономного блока ЭВМ при поиске заданных чисел в упорядоченном массиве. Цель изобретения - повышение быстродействия устройства. На чертеже представлена схема предлагаемого устройства. Устройство содержит регистр 1-4 счетчик 5 адреса, схемы 6-8 сравнения, триггер 9, группу элементов И 10, элемент 2 И-ИЛИ 11, элементы И 12-16, элементы ИЛИ 17 и 18, элемент 19 задержки, информационн1 е входы 20, вход 21 тактовых импульсов, вход 22 запуска, выходы 23-26 Устройства работает следующим образом. В исходном состоянии в регистр заносится значение числа, которое требуется найти в упорядоченном . по возрастанию массиве данных, в регистр 3 - адрес начала массива а в регистр 4 - адрес конца массив упорядоченных данных. На вход 22 подается импульс запуска, который устанавливает триггер 9 в нулевое состояние, открывает группу элемен тов И 10, через которую адрес нача массива данных записывается в счет чик 5, и проходит через элемент ИЛИ 18, элемент задержки 19, элемент И 16 на выход 25. При появлении импульса считывания на выходе 25 из ЗУ ЭВМ по адресу, сформирова ному на выходах 26, считьшается значение первого числа, которое за сывается по входам 20 в регистр 1, Если значение заданного чис.ла меньше, чем любое число в массиве, то на первом выходе схемы 6 сравнения появится единичный сигнал, которьй установит в единичное состоя-, ние триггер 9 и поступит на вход элемента И 13, на второй вход которого поступает единичный сигнал с первого выхода схемы 7 сравнения, так как содержимое счетчика 5 и регистра 3 равны. Элемент И 13 открыт и единичный сигнал поступает на выход 24 через элемент ИЛИ 17 и запрещает с инверсного выхода элемента ИЛИ 17 прохождение тактовых импульсов через элементы И 15 и . 2 И-ИЛИ 11. Появление высокого потенциала на выходе 24 при отсутствии единичного сигнала на выходе 23 означает, что в марсиве нет заданного числа. Если значение заданного числа больше, чем любое число массива, то при записи первого числа в регистр 1 на втрром выходе схемы 6 сравнения будет единичный сигнал, который поступает на входы элементов И 12, 14 и 15. Элемент И 15 открыт, так как на входы поступают единичные сигналы с инверсного выхода элемента ИЛИ 17 и второго выхода схемы 8 сравнения. Тактовый импульс поступает через элемент И 15 на су.ммируюш 1й вход счетчика 5 и через элементы ИЛИ 18, задержки 19 и И 16 на выход 25. Суммирующий вход счетчика 5 является суммирующим входом К-разряда, где ij (3 oi есть целая часть числа csi ; п - разрядность счетчика. Для восьмиразрядного счетчика суммируюцийвход подключен к пятому разряду, т.е. содержимое его. 3 увеличивается при поступлении тактового импульса на 2 16 (грубьм ,счет). Второе считанное число, которое запишется в регистр 1, для рассматриваемого случая будет по порядковому номеру 17-м. Так как и комое число больше, то состояние схем 6 и 8 сравнения не изменится и устройство выберет очередное чис Это состояние сохранится до тех по пока адрес счетчика 5 не станет равным или больимм, чем адрес последнего числа массива. Если адрес счетчика 5 станет: равным адресу последнего числа масси то с первого выхода схемы 8 сравне ния высокий потенциал поступит на вход элемента И 12. Так как считан ное последнее число массива будет меньше, то на втором выходе схемы сравнения останется высокий потенциал, элемент И 12 откроется и еди ничный .сигнал появится на выходе 24, что сигнализирует об окончании анализа. Если адрес счетчика 5 при посту лении импульса на суммирующий вход станет больше адреса последнего числа, то единичный сигнал с треть го выхода схемы 8 сравнения поступ на шестой вход элемента 2 И-И1Ш 11 на инверсньй вход элемента И 16, запрещая тем самым выборку числа за пределами зоны массива. Очередной тактовый импульс поступает через элемент 2 И-ИЛИ 11 на вычита щий вход счетчика 5 и содержимое счетчика уменьшается на единицу (точный счет). До тех пор, пока . адрес на выходе счетчика 5 не раве адресу последнего числа, записанному в регистре 4, состояние схемы 8 сравнения не меняется и импульс на выход 25 не поступает. Тактовые импульсы поступают на вычитающий вход счетчика 5 до тех пор, пока его содержимое не станет равным адресу последнего числа массива. Как только содержимое счетчика 5 и содержимое регистра 4 будут равны, на первом выходе схемы 8 сравнения появится единичный сигнал, которьй поступит на вход элемента И 12, одновременно исчезнет сигнал на инверсном входе элемента И 16 и последнее число массива запишется в регистр 1. Так как схема 6 сравнения не изменит своего состоя 54 ния, то единичны) сигнал с выхода элемента И 12 через элемент SUIH 17 поступит на выход 24 устройства. Поиск числа на этом заканчивается. Если значение заданного числа есть в массиве чисел, то после записи первого числа в регистр 1 возможно следующее: если заданное числе равно первому числу массива, то появится сигнал на третьем выходе схемы 6 сравнения, которьй поступит на выход 23 устройства, сигнализируя о том, что данное число есть в массиве и оно записано в ЗУ ЭВМ по адресу, сформированному на выходах 26, и через элемент ИЛИ 17 на выход 24, сигнализируя об окончании работы устройства, а также с инверсного выхода элемента ИЛИ 17 низкий потенциал запретит дальнейшее поступление тактовых импульсов через элементы И 15 и 2 И-ИЛИ 11, если значение числа в регистре 1 меньше, чем значение заданного числа в регистре 2, то со второго выхода схемы 6 сравнения единичньй сигнал поступит на вход элемента И 15 через который тактовые импульсы будут поступать на суммирующий вход счетчика 5 и, пройдя элементы ИЛИ 18, задержки 19 и И 16, на выход 25. При появлении импульса считьгоания на выходе 25 из ЗУ ЭВМ по адресу, форьшруемому счетчиком 5 на выходах 26, считывается очередное число,которое записывается по входам 20 в регистр 1. Если очередное число меньше заданного числа, то устройство работает аналогично описанному и т.д. Если очередное поступившее число больше заданного числа, то с первого выхода схемы 6 сравнения единичный сигнал установит триггер 9 в единичное,состояние и разрешит поступление тактового импульса с входа 21 через элемент 2 И-ИЛИ 11 на вычитающий вход счетчика 5 и одновременно через элементы 1-ШИ 18, задержки 19 и И 16 на выход 25 устройства. При появлении импульсов считьшания на выходе 25 из ЗУ ЭВМ 110 адресу, формируемому счетчиком 5 на выходах 26, считывается число, которое записывается по входам 20 в регистр1. Тактовые импульсы поступают на вычитающий вход счетчиа Зйдо тех пор, пока в регистр 1 не запишется число, равное или меньшее заданного числа. Если в регистр 1 поступит число, равное заданному 11ислу, то единичньй сигнал с третьего вЬкода схекш 6. сравнений поступит на выход 23 и через элемент ИЛИ 17 на выход 24 и одновременно с инверсноговыхода элемента.ИЛИ 17 низкий потенциал запретит дальней,, л . . -,

шер поступление тактовых импульсов череа элементы. И 15 и 2 И-ШШ 11. Наличие единичных сигналов на выхоД4Х 23 и 24 означает, что процесс поиска закончен и по адресу, рформированному на, вькорах 26, в зУ ЭВМ записано число, равное заданному. Если в регис р 1 поступит число, , меньшее заданного, то вьюЪкИй потенциал с второго выхода схемы 6 сравнения через открытый элемент И 14 (триггер 9 в единичном состоянии)

поступит через элемент ИЛИ 17 на выход 24 и с инверсного вькода элемента ИЛИ 17 низкий потенциал запретит поступление тактовьк импульсов. Наличие единичного сигнала на выходе 24 при его отсутствии на выходе 23 означает, что поиск закончен, ,но заданного числа в массиве нет. В случае отсутствия заданного числа на выходах 26 формируется

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