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

Изобретение относится к вычислительной технике и может быть использовано в качестве автономного блока ЭВМ при поиск э заданных чисел в упорядоченном массив э.

Цель изобретения - повышение быстродействия устройства.

На фиг.1 и 2 представлена схема пред- лагземого устройства.

Устройство содержит информационные входы 1 устройства, регистр 2, схему 3 срав- неьия, регистр 4, выход 5 наличия числа устюйства, элемент ИЛИ 6, выход 7 конца П01 ска устройства, элемент ИЛИ 8, элемент 9 з,держки, элемент И 10, выход 11 разре- считывания устройства, вход 12 запуска устройства, триггер 13, регистр 14, группу элементов-И 15, регистр 16, элемент

И 17, элемент И 18, группу элементов И 19, группу элементов И 20, элементы И 21 и 22, элемент 23 задержки, регистр 24 сдвига адреса, элементы И 25 - 27, вход 28 тактовых импульсов, триггер 29, сумматор 30, элемент ИЛИ-НЕ 31, формирователь 32 дополнительного кода, группу элементов ИЛИ 33, сумматор 34, регистр 35, информационные выходы 36 устройства, группу элементов И 37, группу элементов ИЛИ 38, группу элементов И 39, формирователь 40 дополнительного кода, регистр 41 сдвига, элемент 42 задержки, формирователь 43 импульсов, элемент ИЛИ 44, формирователь 45 импульсов, элемент 46 задержки, элемент ИЛИ 47 и элементы 48 и 49 задержки.

Устройство работает следующим образом.

О

00

о

4is СО

В исходном состоянии в регистр 4 заносится значение числа, которое требуется найти в упорядоченном по возрастанию массиве данных, в регистр 14 - адрес начала массива, а в регистр 16 - адрес конца массива упорядоченных данных. Адрес начала массива с выходов регистра 14 поступает на вход формирователя 40 дополнительного кода, с выхода которого дополнительный код адреса начала массива поступает на вторую группу входов сумматора 30, на первую группу входов которого подается адрес конца массива с выходов регистра 16. С выходов сумматора 30 относительный код адреса конца массива поступает на информационные входы регистра 24 сдвига адреса, На вход 12 устройства подается импульс запуска, который поступает на вход записи регистра 24 сдвига адреса и записывает в него относительный код адреса конца массива, устанавливает триггер 29 в единичное состояние, а триггер 13 - в нулевое состояние. С выхода триггера 29 единичный уровень поступает на второй вход элемента И 27, разрешая прохождение через него тактовых импульсов, которые подаются на его первый вход с входа 28 устройства. Тактовые импульсы с выхода элемента И 27 поступают на первые входы 26 и 25 элементов И. На второй вход элемента И 25 поступает запрещающий нулевой уровень с прямого выхода триггера 13, а на второй вход элемента И 26 поступает единичный уровень с его инверсного выхода, тем самым запрещая прохождение тактовых импульсов через элемент И 25 и разрешая их прохождение через элемент И 26 на регистр 41 сдвига. С первого выхода регистра 41 сдвига единичный уровень поступает на элемент 46 задержки и через формирователь 45 импульсов на второй вход элемента ИЛИ 44 в виде единичного импульса м на первые входы группы элементов И 39, разрешая прохождение адреса конца массива с выхода регистра 16 через группу элементов И 39 на вторую группу входов группы элементов ИЛИ 38, с выходов которой он поступает на входы регистра 35.

Единичный импульс с выхода элемента

ИЛИ 44 через элемент ИЛИ 47 поступает на вход записи регистра 35, записывая в него адрес конца массива, находящийся на его входах. Одновременно этот единичный им пульс поступает на второй вход элемента ИЛИ 8, с выхода которого через элемент 9 задержки (задержка осуществляется на время формирования адреса на сумматоре 34) и элемент И 10 поступает на выход 11 устройства как импульс считывания и на вход элемента 49 задержки (задержка осуществляется на время считывания числа из ЗУ ЭВМ). По адресу, сформированному на выходах сумматора 34, поступающему на выходы 36 устройства, из ЗУ ЭВМ считывается значение последнего числа, которое записывается по входам 1 устройства в регистр 2, С выхода элемента 49 задержки единичный импульс через элемент 48 задержки и элемент ИЛИ 47 поступает на вход записи 0 регистра 35 и на разрешающие входы группы элементов И 37, на информационные входы которой поступает адрес с выходов 36 устройства.

С выхода элемента 46 задержки (задер- 5 жка осуществляется на время формирования адреса на сумматоре 34, считывания числа из ЗУ ЭВМ и сравнения содержимого регистров 2 и 4 на схеме 3 сравнения) единичный уровень поступает на второй вход 0 элемента И 17, на первый вход которого подается сигнал с выхода Больше схемы 3 сравнения.

Если заданное число больше, чем любое в массиве, то на выходе Больше схемы 3 5 сравнения появится единичный уровень, проходящий через элемент И 17 на третий вход элемента ИЛИ 6, с прямого выхода которого он поступает на инверсный вхоД элемента И 10 и на выход 7 устройства - 0 конец поиска, а с инверсного - на вход сброса триггера 29, нулевой уровень на выходе которого запрещает прохождение тактовых импульсов на устройство. Если заданное число равно числу в массиве, то на выходе 35 Равенство схемы 3 сравнения появится единичный уровень, который поступает на выход 5 устройства - число найдено, и на первый вход элемента ИЛИ 6, с прямого выхода которого на выход 7 устройства - 40 конец поиска. Если заданное число меньше последнего числа в массиве, то с п-риходом второго тактового импульса на вход регистра 41 сдвига на его втором выходе появляется единичный логический уровень, 45 который поступает на элемент 42 задержки, и через формирователь 43 импульсов - на первый вход элемента ИЛИ 44 и на разрешающие входы группы элементов И 15, разрешая прохождение адреса начала массива 50 с выходов регистра 14 через группу элементов И 15 на первые входы группы элементов ИЛИ 38, с выходов которой этот адрес.поступает на,входы регистра 35. Единичный импульс с выхода элемента ИЛИ 44 посту- 55 пает на первый вход элемента ИЛИ 47 и с его выхода - на вход записи регистра 35, разрешая запись в него адреса начала массива. Одновременно этот единичный импульс поступает на второй вход элемента ИЛИ 8, с выхода которого через элемент 9

на ст

Mfcl

вь ля пр эл

ржки и элемент И 10 поступает на вы- 11 устройства как импульс считывания вход элемента 49 задержки. По адресу, мированному на выходах сумматора на первые входы которого поступает код а на вторые - адрес начала массива с вы)одов регистра 35, из запоминающего ус- ЭВМ считывается значение перво- и сла, которое записывается по входам 1 уст зойства в регистр 2.

С выхода элемента 42 задержки единич- уровень поступает на вход установки в регистра 41 сдвига, на вход установки в триггера 13 и на второй вход элемента И на первый вход которого поступает сиг- с выхода Меньше схемы 3 сравнения, и заданное число меньше, чем любое в то на выходе Меньше схемы 3 внения появится единичный уровень, через элемент И 22 на второй элемента ИЛИ 6, с прямого выхода KOitoporo он поступает на инверсный вход элемента И 10 и выход 7 устройства - конец I. С инверсного выхода элемента ИЛИ сигнал поступает на вход сброса в О irrepa 29, нулевой уровень на выходе ко- юго запрещает прохождение тактовых пульсов на устройство. Если заданное число больше первого :ла массива, то следующий тактовый им- выхода элемента И 27, поступающий первый вход элемента И 25. на второй вход которого подается открывающий поло- жиггельный уровень с прямого выхода триг- 13, поступает через него на вход 23 задержки (задержка осуществ- ляйтся на время считывания из запоминающе го устройства ЭВМ числа и сравнения его заданным). С выхода элемента И 25такто- импульс поступает из вход сдвига отно- гельно адреса в регистре 24 и сдвигает ) вправо, осуществляя тем самым цело- ;ленное деление его на два. С выходов истра 24 сдвига относительный адрес потает на информационные входы группы гментов И 19 и на входы формирователя дополнительного кода относительно ад- :а, с выходов которого относительный ад- Z в дополнительном коде поступает на информационные входы группы элементов |, С выхода элемента 23 задержки такто- импульс поступает соответственно на и второй входы элементов И 18 и 21, второй и первый входы которых соответ- поступают сигналы с выходов схе- 3 сравнения Больше и Меньше, На Больше схемы 3 сравнения появ- 1ТСЯ единичный уровень, разрешающий п охождение тактового импульса с выхода 1мента 23 задержки через элемент И 8

зад

ход

и Hit

сф9р

34.

нул|я

тройства:

Г0

НЫ1|1

О

1

22., на/ ECI

массиве, срг

проходящий вхсд

поиска.

6

тр1

TOf

им

ЧИ(

пульсе

на

rei)a эл(мента

выи

си

ег(

ЧИ(

ре

СТ| ЗЛ1

32

ре ре

и:ю

вь й первый

вь ходе

на третий вход элемента ИЛИ 8 и на разрешающие входы группы элементов И 19, разрешая прохождение через нее относительного адреса, который через группу злементов ИЛИ 33 поступает на первые входы сумматора 34, на вторые входы которого подается адрес начала массива с выходов регистра 35, записанный в него на предыдущем такте.

0 На выходе сумматора 34 формируется новый адрес, равный адресу начала массива плюс половина первоначального относительного адреса. Тактовый импульс с выхода элемента ИЛИ 8 поступает на вход

5 элемента 9 задержки, с выхода которого через элемент И 10 поступает на вход элемента 49 задержки и на выход 11 устройства - импульс считывания. Из запоминающего устройства ЭВМ считывается значение числа

0 по адресу, сформированному на выходах 36 устройства, которое записывается по входам 1 устройства в регистр 2.

С выхода элемента 49 задержки тактовый импульс поступает на разрешающие

5 входы группы элементов И 37. разрешая прохождение адреса с выхода 36 устройства на входы регистра 35. Одновременно этот тактовый импульс через элемент 48 задержки {задержка осуи1ествляется на время по0 явления адреса на входах регистра 35) и элемент ИЛИ 47 поступает на вход записи регистра 35, записывая в него этот адрес.

Если с выхода Меньше схемы 3 сравнения на первый вход элемента И 21 посту5 пает единичный уровень, то разрешается прохождение тактового импульса с выхода элемента 23 задержки на первый вход элемента ИЛИ 8 и на разрешающие входы группы элементов И 20, разрешая тем самым

0 прохождение дополнительного кода нового относительного адреса через группу зле- ментов И 20, поступающего с выходов формирователя 32 дополнительного кода адреса. Этот дополнительный код нового

5 относительного адреса через группу элементов ИЛИ 33 поступает на первые входы сумматора 34, на выходе которого формируется новый адрес, поступающий на выход 36 устройства.

0 Новый адрес равен предыдущему адресу минус половина предыдущего относительного адреса.

С приходом импульса считывания на выход 11 устройства из ЗУ ЭВМ считывается

5 значение первого числа, которое записывается по входам 1 устройства в регистр 2, а в регистр 35 записывается новый адрес. С приходом следующих тактовых импульсов, .в зависимости от того, на каком выходе Больше или Меньше схемы 3 сравнения

появляется единичный уровень, на выходе 36 устройства формируется новый адрес.

С каждым тактом все повторяется до тех пор, пока не будет найдено число, равное заданному, или до тех пор, пока на выходе регистра 24 сдвига адреса не появится относительный адрес, равный нулю, который поступает на элемент п ИЛИ-НЕ 31 (где п - максимальное количество разрядов в адресе), с выхода которого единичный уровень поступает на четвертый вход элемента ИЛИ 6. При этом на прямом выходе элемента ИЛИ 6 появляется единичный уровень, поступающий на инверсный вход элемента И 10, запрещая прохождение импульса считывания на выход 11 устройства и на выход 7 устройства - конец поиска. Одновременно с инверсного выхода элемента ИЛИ 6 нулевым уровнем, поступающим на вход сброса триггера 29, блокируется прохождение тактовых импульсов на устройство через элемент И 25.

Таким образом, за первые два такта устройство определяет, попадает заданное число в рамки массива или нет, если нет, то на выходе 7-устройства появляется единичный логический уровень, свидетельствующий об окончании анализа. Если попадает, то устройство максимум за 12 тактов найдет заданное число, при этом на выходах 5 и 11 устройства соответственно Число есть и Конец анализа появляются единичные уровни. Если числа в массиве нет, то через п тактов на выходе 7 устройства появляется единичный уровень, а на выходе 5 - отсутствует, что свидетельствует о том, что число не найдено и анализ окончен.

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

ключены к информационным входам соответствующих элементов И группы, управляющие входы которых обьединены, информационные входы третьего и четвер- того регистров являются соответственно входами адреса конца массива и адреса начала массива устройства, выход Меньше схемы сравнения подключен к первому входу второго элемента И, выход Больше схе- 0 мы сравнения подключен к первым входам третьего и четвертого элементов И, прямой выход триггера подключен к первому входу пятого элемента И, отличающееся тем, что, с целью повышения быстродействия, в 5 него введены пятый регистр, регистр сдвига, регистр сдвига адреса, два сумматора, четыре группы элементов И, две группы элементов ИЛИ, три элемента И, пять элементов задержки, два элемента ИЛИ, второй 0 триггер, элемент ИЛИ-НЕ, два формирователя дополнительного кода, два формирователя импульсов, причем тактовый вход устройства подключен к первому входу шестого элемента И, выход которого подклю- 5 чей к второму входу пятого элемента И и первому входу седьмого элемента И, второй вход которого соединен с инверсным выходом первого триггера, входы установки в О первого и в 1 второго триггера обьедине- 30 ны и соединены с входом запуска устройства и с входом установки в О регистра сдвига адреса, а вход установки в 1 перво- rq триггера подключен к входу сброса регистра сдвига адреса, к первому входу 35 восьмого элемента И, через второй элемент задержки к первому выходу регистра сдвига адреса, к управляющим входам элементов И первой группы и через первый формирователь импульсов к первому входу третьего 40 элемента ИЛИ, выход которого соединен с первым входом второго элемента ИЛИ, второй и третий входы которого подключены соответственно к выходам второго и третьего элементов И и к управляющим входам 45 элементов И второй и третьей групп, информационные входы элементов И второй груп- пы подключены к соответствующим выходам регистра сдвига адреса и входам формирователя дополнительного кода, вы- 50 ходы которого соединены с информационными входами элементов И третьей группы, выходы которых подключены к первым входам элемеь|тов ИЛИ первой группы, вторые входы которых подключены к выходам эле- 55 ментов И второй группы, а выходы - к входам первой группы сумматора, входы второй группы которого подключены к выходам разрядов пятого р.егистра, информационные входы которого подключены к выходам элементов ИЛИ второй группы.

nepetie, вторые и третьи входы которых со- един1}ны соответственно с выходами элементов И первой, четвертой и пятой групп, выходы разрядов четвертого регистра сое- дине 1ы с информационными входами элементов И четвертой группы и входами перв)й группы второго сумматора, входы второй группы которого через второй формирователь дополнительного кода соединены с выходами разрядов третьего регистра, выходы второго сумматора подключены к инфсрмационным входам регистра сдвига адре:а, вход сдвига которого соединен с выходом пятого элемента И и через третий элемент задержки с вторыми входами второго и третьего элементов И, выход Меньше ;хемы сравнения подключен к второму вход/ восьмого элемента И, выход которого подключен к второму входу первого элемента И ПИ, третий вход которого подключен к выхсду четвертого элемента И, второй вход кото эого через четвертый элемент задержки соединен с вторым выходом регистра сдвига адреса, с управляющими входами элементов И четвертой группы и через второй формирователь импульсов с вторым входом третьего элемента ИЛИ. выход которого соединен с первым входом четвертого элемента ИЛИ, выход которого соединен с

входом записи пятого регистра, а второй вход четвертого элемента И через пятый элемент задержки соединен с управляющими входами элементов И пятой группы и через шестой элемент задержки соединен с

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

адреса.

/

15

ч

гЗ

J

Изобретение относится к вычислительной технике и может быть использовано в качестве автономного блока ЭВМ при поиске заданного числа в упорядоченном массиве. Цель изобретения - повышение быстродействия устройства. Устройство содержит регистры, схему, сравнения, выход наличия числа устройства, элементы ИЛИ, выход конца поиска устройства, элемент задержки, элементы И, выход разрешения считывания устройства, вход запуска устройства, триггеры, группы элементов И, регистр сдвига адреса, вход тактовых импульсов, сумматор, элемент ИЛИ-НЕ, формирователи дополнительного кода, группы элементов ИЛИ, регистр сдвига, формирователи импульсов, элементы ИЛИ, информационные вход и выход устройства. 2 ил.

/

зг

FT

16

39