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

29

9u.i

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

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

На фиг.I представлена блок-схема Предлагаемого устройства поиска за- ю данного числа; на фиг.2 - схема блока определения начального шага поиска.

Устройство поиска заданного числа содержит регистры 1 и 2 числа,

0,5 W И(, 2 W,

где W - объем упорядоченного массива в котором производится поиск; п - разрядность информационного

выхода 30 устройства. С выхода блока 1,5 определения начального шага поиска инверсный код поступает на информационные входы регистра 16 последовательного сдвига На вход 25 подается импульс начально установки, который устанавливает

регистры 3 и 4 адреса, схемы 5-7 срав-15 19, регистры 16 и 23 в нулевое состояние, и проходя через элемент ИЛИ 13, формирует сигнал 26. разрешения считывания, по которому считывается первое число из ячейки с адресом, сформированным на выходе 30 (адрес начала массива), и данное число записывается по входам 29 в регистр 1. Нулевое состояние триггер 19 устанавливает параллельный режим

йения, элементы И 8-Юр элемент 11 задержки, элементы ИЛИ 12 и 13, блок 14 вычитания, блок 15 определения 1|ачального шага поиска, регистр 16 с|двига, элемент НЕ 17, группу элемен-20 TJOB НЕ 18, триггер 19, коммутатор 20 4умматоры 21 и 22, регистр 23 относит. т ельного адреса, вход 24 тактовых им- 1|ульсов, вход 25. начальной установки.

вое состояние, и проходя через элемент ИЛИ 13, формирует сигнал 26. разрешения считывания, по которому считывается первое число из ячейки адресом, сформированным на выходе 30 (адрес начала массива), и данно число записывается по входам 29 в регистр 1. Нулевое состояние тригге 19 устанавливает параллельный режим

4ыход 26. разрешения считывания устроМЗ записи в-регистр ,16. Далее, при пос|тва, выход 27 конца поиска устрой- с|тва, выход 28, наличия числа, входы 2|9 числа устройства, информационные выходы 30 устройства.

Блок 15 определения начального щага поиска п-разряднрго входного йода адреса содержит (п-1) элементов Й-НЕ 31 и элемент НЕ 32.

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

30

35

ступлении первого тактового импульса на вход 24 устройства производит ся запись Ha4knbHoro шаг а поиска в регистр 16, а через некоторое время определяемое элементо м 11 задержки, триггер 19, устанавливается в единич ное со.стояние, что определяет режим последовательного сдвига для регист 16, а также производится запись относительного адреса в регист.р 23. Н выходе сумматора 2,2 формируется абсолютное значение адреса, по которо считывается значение второго числа с последующей :-записью в регистр 1.. В дальнейшем с приходом последующих импульсов направлением поиска управ ляет схема 5 сравнения. Если значе ние считываемого числа (регистр 1) меньше, чем значение числа,.которое требуется найти (регистр 2) ,, то на первый управляющий вход коммутатора 20 поступает единичный.уровень, что разрешает прохождение значение шаг поиска в прямом коде,на первую груп входов, сумматора 21., на вторую груп входов которого поступает предыдуще значение кода адреса. Тацсим обра-, зом, осуществляется модификация адр са в сторону увеличения на величину шага в два.раза меньше, чем в преды дущем цикле. Если значение считывае мого числа больше, чем значение искомого ,то на второй управляющ вход коммутатора 20 поступает еди

В исходном состоянии в регистр 2 Заносится значение числа, которое требуется найти в упорядоченном по возрастанию массиве данных, в регистр

3- адрес начала массива, а в регистр

4- адрес конца массива упорядоченных данных. Блок 14 вычитания(с группой инверторов по второ.й группе входов)

формирует объем исследуемого массива, значение которого поступает на вход (5лока 15-определения начального Шага поиска, причем выходы младших разрядов блока 14 вычитания поступают на вход старших разрядов блока 15 Определения начального шага поиска, а выходы старших разрядов блока 14 дачитания поступают на вход младших разрядов блока 15 определения начального шага поиска. Вход Перенос блока 14 вычитания имеет единичное Значение (не показан), вследствие чего начальный шаг поиска Ир будет принимать значения

0,5 W И(, 2 W,

где W - объем упорядоченного массива, в котором производится поиск; п - разрядность информационного

выхода 30 устройства. С выхода блока 1,5 определения начального шага поиска инверсный код поступает на информационные входы регистра 16 последовательного сдвига. На вход 25 подается импульс начальной установки, который устанавливает

19, регистры 16 и 23 в нулевое состояние, и проходя через элемент ИЛИ 13, формирует сигнал 26. разрешения считывания, по которому считывается первое число из ячейки с адресом, сформированным на выходе 30 (адрес начала массива), и данное число записывается по входам 29 в регистр 1. Нулевое состояние триггер 19 устанавливает параллельный режим

0

5

5

.,.

0

5

ступлении первого тактового импульса на вход 24 устройства производится запись Ha4knbHoro шаг а поиска в регистр 16, а через некоторое время, определяемое элементо м 11 задержки, триггер 19, устанавливается в единичное со.стояние, что определяет режим последовательного сдвига для регистра 16, а также производится запись относительного адреса в регист.р 23. На выходе сумматора 2,2 формируется абсолютное значение адреса, по которому считывается значение второго числа . с последующей :-записью в регистр 1.. В дальнейшем с приходом последующих импульсов направлением поиска управляет схема 5 сравнения. Если значе- ние считываемого числа (регистр 1) меньше, чем значение числа,.которое требуется найти (регистр 2) ,, то на первый управляющий вход коммутатора 20 поступает единичный.уровень, что разрешает прохождение значение шага поиска в прямом коде,на первую группу входов, сумматора 21., на вторую группу входов которого поступает предыдущее значение кода адреса. Тацсим обра-, зом, осуществляется модификация адреса в сторону увеличения на величину шага в два.раза меньше, чем в предып, дущем цикле. Если значение считывае-- мого числа больше, чем значение искомого ,то на второй управляющий вход коммутатора 20 поступает еди

3

ничный уровень, что разрешает прохождение инверсного кода шага поиск через коммутатор 20 и на сумматоре 21 практически выполняется операция вычитания. Таким образом, осуществлется модификация адреса в сторону уменьшения на величину шага в два рза меньше, чем в предыдущем цикле.

После каждого такта считывания осуществляется анализ поступающих чисел в регистр 1, а также соблюден границ поиска. При считывании числа из ячейки с адресом /начала массива на выхеде Равно схемы 7 формирует ся единичный сигнал. При этом, если считываемое число меньще, чем значе ние искомого числа, то на выходе элемента И 8 формируется единичный сигнал, который через элемент ИЛИ 1 поступает на выход 27 конца поиска.

При совпадении считываемого числ с искомым (единичный сигнал на выходе Равно схемы 5 сравнения) и соблюдении границ (единичный сигнал на выходе Меньше схемы 6 сравнени на выходе элемента И. 9 формируется единичный сигнал, который поступает на выход 28 наличия поиска и через элемент ИЛИ 12 на выход 27 конца .поиска.

При несоблюдении границ поиска н выходе Меньше схемы 6 сравнения формируется нулевой сигнал, который через элементы И 10, НЕ 17 поступае единичным уровнем на второй .вход управления коммутатора 20 и на вход Перенос сумматора 21, в результат чего осуществляется модификация адрса в сторону уменьшения.

При отсутствии искомого числа в упорядоченном массиве, после (п+1) циклов поиска с выхода 2-1 регистра 16 нулевой сигнал через элемент

0

0

5

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

разрядов первого и второго регистров

f

адресов подключены к входам первых 0 групп, второй и третьей схем сравнения, входы вторых групп которых соединены с информационными выходами устройства, отличающееся тем, что, с целью повыщения быстро- g действия, в него введены блок вычитания, блок определения начального шага поиска, регистр сдвига,группа элементов НЕ, коммутатор, два сумматора, регистр относительного адреса, элемент НЕ, причем вход начальной установки устройства подключен к входам установки в ноль регистра относительного адреса и регистра сдвига, выход (п+1)-го разряда кото0

Изобретение относится к вычислительной технике и может быть использовано в качестве автономного блока ЭВМ при поиске заданных чисел в упорядоченном массиве. Цель изобретения - повышение быстродействия. Устройство содержит регистры числа 1,2, регистры адреса 3,4, схемь сравнения 5,6,7, блок вычитания 14, блок 1 5 определения начального шага поиска, регистр сдви- га 16, триггер 19, коммутатор 20, сумматоры 21, 22, регистр 23 относительного адреса, элементы И, ИЛИ. Устройство выполняет поиск заданного числа в упорядоченном массиве данных с предварительным автоматическим определением грубого шага поиска, что позволяет повысить его быстродействие. 1 з.п.ф-лы, 2 ил.

ИЛИ 12 единичным уровнем поступит на 45 Р°го соединен с третьим входом пер- выход 27 конца поиска.

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

Формула изобретения

Р°го соединен с третьим входом пер-

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

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

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

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

разрядов которого подключены к входам 20 блока.

п

второй группы первого сумм-атора и входам первой группы второго сумматора, входы второй группы которого соединены с входами вычитаемого блока вычитания, а выходы являются информационными выходами устройства,

(п-1) элементов И-НЕ и элемент НЕ,причем входы блока соединены с входом элемента НЕ и первыми входами элементов И-НЕ, выход элемента НЕ является,

первым выходом .блока и соединен с

вторыми входами элементов И-НЕ, выход i-ro элемента И-НЕ соединен с (i+2)- ми входами элементов И-НЕ с (i+l)-ro по (п-1)-и и является i-ым выходом

П

П-Г