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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН (51)4 G 06 F 7 06

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ABTOPCHOMV СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3724413/24-24 (22) 11.04.84 (46) 07 ° t0 ° 85. Бюл, №- 37 (72) Н.И..Крылов, В.N. Полищук и Н.Н. Шубина (53) 681.325(088.8) (56) Авторское свидетельство СССР

¹ 732858, кл. С 06 F 7/06, 1978.

Авторское свидетельство СССР № 997029, кл. G 06 F 7/06, 1978. (54) (57) УСТРОЙСТВО ПОИСКА ЗАДАННОГО ЧИСЛА, содержащее регистры схемы сравнения, два элемента И, элемент задержки, группу элементов

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

"Меньше" первой схемы сравнения подключен к первому входу элемента

„„SU„„1183955

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

ИЛИ является выходом конца поиска устройства, а инверсный выход под-..

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

Изобретение. относится к вычислительной технике и может быть использовано в качестве автономного блока ЭВМ при поиске заданных чисел в упорядоченнбм массиве. 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 является суммирующим входом К -разряда, где К=J -" + (— есть целая часть числа ; и — разрядность счетчика. Для восьмиразрядного счетчика суммирующий вход подключен к пятому разряду, т.е. содержимое его.

1183955 увеличивается при поступлении такф тового импульса на 2 = 16 грубый, счет) . Второе считанное число, которое запишется в регистр 1, для рассматриваемого случая будет по порядковому номеру 17-м. Так как искомое число больше, то состояние схем 6 и 8 сравнения не изменится и устройство выберет очередное число.

Это состояние сохранится до тех пор, пока адрес счетчика 5 не станет равным или большим, чем адрес последнего числа массива.

Если адрес счетчика 5 станет, равным адресу последнего числа массив», то с первого выхода схемы 8 сравнения высокий потенциал поступит на вход элемента И 12. Так как считанное последнее число массива будет меньше, то на втором выходе схемы сравнения останется высокий потенциал, элемент И 12 откроется и единичный сигнал появится на выходе

24, что сигнализирует об окан:ании анализа.

Если адрес счетчика 5 при поступлении импульса на суммирующий вход станет больше адреса последнего числа, то единичный сигнал с третьего выхода схемы 8 сравнения поступит на шестой вход элемента 2 И-ИЛИ 11 и на инверсный вход элемента И 16

S запрещая тем самым выборку числа за пределами зоны массива. Очередной тактовый импульс поступает через элемент 2 И-ИЛИ 11 на вычитающий вход счетчика 5 и содержимое счетчика уменьшается на единицу (точныйл счет) . До тех пор, пока адрес на выходе счетчика S не равен адресу последнего числа, записанному в регистре 4, состояние схемы

8 сравнения не меняется и импульс на выход 25 не поступает. Тактовые импульсы поступают на вычитающий вход счетчика 5 до тех пар, пока его содержимое не станет равным адресу последнего числа массива.

Как только содержимое счетчика 5 и содержимое регистра 4 будут равны, на первом выходе схемы 8 сравнения появится единичный сигнал

t который поступит на вход элемента

И 12, одновременно исчезнет сигнал на инверсном входе элемента И 16 и последнее число массива запишется в регистр 1. Так как схема 6 сравнения не изменит своего состояния, то един1лчный сигнал с выход» элемента И 12 через элемент ИЛИ 17 поступит на выход 24 устройства.

Поиск числа на этом заканчивается.

Если значение заданного числа есть в массиве чисел, то после записи первого числа в регистр 1 возможно следующее: если заданное числс равно первому числу массива, то появится сигнал на третьем выходе схемы 6 сравнения, который поступит на выход 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 уст50 ройства. При появлении импульсов считывания на выходе 25 из ЗУ ЭВИ по адресу, формируемому счетчиком

5 на выходах 26, считывается число, которое записывается по входам 20

55 в регистр 1. Тактовые импульсы поступают на вычитающий вход счетчи< ка 5сдо тех пор, пака в регистр 1 не запишется число, равное или мень1183955

ВНИИПИ Заказ 6271/48 Тираж 709 Подписное

Филиал ППП Патент, г.ужгород, ул.Проектная, 4 шее заданного числа. Если в регистр

1 поступит. число, равное заданному числу, то единичный сигнал с третьего восхода схемы б сравнений поступит на выход 23. и через элемент

ИЛИ 17 на выход -24 и одновременно с инверсного выхода элемента ИЛИ 17 .низкий потенциал запретит дальнейшее поступление тактовых импульсов через элементы И 15 и 2 И-ИЛИ 11 .

Наличие единичных сигналов на выхо< дах 23 и 24 означает, что процесс поисКа закончен ° и по адресу, рфорь|ированному на. выходах 26, в Зу ЗВМ записано число, равное заданному.

Если в регистр 1 поступит число, меньшее заданного, то высокий потенциал с второго выхода схемы 6 сравнения через открытый элемент И 14 (триггер 9 в единичном состоянии) поступит через элемент ИЛИ 17 на выход 24 и с инверсного выхода элемента ИЛИ 17 низкий потенциал запретит поступление тактовых импульсов.

Наличие единичного сигнала на вы10 ходе 24 при его отсутствии на выходе 23 означает, что поиск закончен, но заданного числа в массиве нет.

В случае отсутствия заданного числа на выходах 26 формируется

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