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

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

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИК

m 4- G 06 F 7/06

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

И АВТОРСНОМ У СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И OTHPbfTHRM

ПРИ ГКНТ СССР (21) 4308065/24-24 (22) 21.09.87 (46) 28.02.89. Вюл. У 8 (72) В.В.Иолошаг и А.П.Смирнов (53) 681.325(088.8) (56) Авторское свидетельство СССР

Ф 997029, кл. G 06 F 7/06, 1982.

Авторское свидетельство СССР

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

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

Устройство выполняет поиск заданного числа в упорядоченном массиве данных с предварительным автоматическим определением грубого шага поиска, что позволяет повысить его быстродействие. 1 з.п.ф-лы, 2 ил. 1462292

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

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

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

Устройство поиска заданного числа содержит регистры 1 и 2 числа,. регистры 3 и 4 адреса, схемы 5-7 срав-15 ения, элементы И 8-10, элемент 11 задержки, элементы ИЛИ 12 и 13, блок !

1!4 вычитания, блок 15 определения начального шага поиска, регистр 16 с1двига, элемент НЕ 17, группу элемен- 20 тов НЕ 18, триггер 19 > коммутатор 20, сумматоры 21 и 22„ 23 относи-,. т1ельного адреса, вход 24 тактовых импульсов, вход 25 начальной установки, выход 26 разрешения считывания устрой-25 тва, выход 27 конца поиска устройства, выход 28.наличия числа, входы

29 числа устройства, информационные выходы 30 устройства.

Блок 15 определения начального 30 щага поиска и-разрядного входного

Кода адреса содержит (n-1) элементов

И-НЕ 31 и элемент HE 32.

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

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

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

4 — адрес конца массива упорядоченных данных, Блок 14 вычитания(с группой инверторов по второй группе входов) формирует объем исследуемого массива, значение которого поступает на вход блока 15.определения начального

Шага поиска, причем выходы младших

I разрядов блока 14 вычитания поступают на вход старших разрядов блока 15 определения начального шага поиска, а выходы старших разрядов блока 14 вычитания поступают на вход младших разрядов блока 15 определения начального шага поиска. Вход "Перенос" блока 14 вычитания имеет единичное значение (не показан), вследствие чего начальный шаг поиска И будет принимать значения

054ы(И=2(W, где W — объем упорядоченного массива, в котором производится поиск; и — разрядность информационного выхода 30 устройства.

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

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

30 (адрес начала массива), и данное число записывается по входам 29 в регистр 1. Нулевое состояние триггера

19 устанавливает параллельный режим записи в .регистр 16. Далее при поступлении первого тактового импульса на вход 24 устройства производится запись начального шага поиска в регистр 16, а через некоторое время, определяемое элементом 11 задержки, триггер 19, устанавливается в единичное состояние, что определяет режим последовательного сдвига для регистра

16, а также производится запись относительного адреса в регистр 23. На выходе сумматора 22 формируется абсолютное значение адреса, по которому считывается значение второго числа . с последующей -записью в регистр 1..

В дальнейшем с приходом последующих импульсов направлением поиска управляет схема 5 сравнения. Если значение считываемого числа (регистр 1) меньше, чем значение числа,, которое требуется найти (регистр 2), то на первый управляющий вход коммутатора

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

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

21 практически выполняется операция вычитания. Таким образом, осуществля.5 ется модификация адреса в сторону уменьшения на величину шага в два ра" за меньше, чем в предыдущем цикле, После каждого такта считывания осуществляется анализ поступающих чисел в регистр 1, а также соблюдение границ поиска. При считывании числа из ячейки с адресоМ !начала массива, на выходе "Равно" схемы 7 формирует- 15 ся единичный сигнал. При этом, если считываемое число меньше, чем значение искомого числа, то на выходе элемента И 8 формируется единичный сигнал, который через элемент ИЛИ 12 поступает на выход 27 конца поиска.

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

Ф управления коммутатора 20 и на вход .

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

ИЛИ 12 единичным уровнем поступит на 45 выход 27 конца поиска. формула изобретения которой соединены с выходами разрядов второго регистра числа, информационные входы которого являются входами заданного числа устройства, выход

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

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

1462292

° ° °

В 4 °

Ф Ф 1

Составитель Е.Иванова

Техред Л.Олийнык Корректор С.Черни с

Редактор Ю.Середа

Заказ 712/46 Тираж 667 Подписное

ВЯИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101 входами блока определения начального шага поиска, выходы которого соединены с информационными входами регистра сдвига, выходы разрядов которого с

5 первого по п-,é соединены с информационными входами первой группы коммутатора и через соответствующие элемен= ты HE группы - с информационными входами второй группы коммутатора, первый управляющий вход которого подключен к выходу третьего элемента фГи через элемент НŠ— к второму управляющему входу коммутатора н входу переноса первого сумматора, входы 15 впервой группы которого соединены с выходами коммутатора, а выходы подключены к информационным входам реистра относительноro адреса, выходы азрядов которого подключены к входам 2п второй группы первого сумматора и входам первой группы второго сумматора, входы второй группы которого соединены с входами вычитаемого блока вычитания, а выходы являются информационными выходами устройства.

2. Устройство по п.1, о т л и ч аю щ е е с я тем, что блок определения начального шага поиска содержит (n-1) элементов И-HE и элемент НЕ,причем входы блока соединены с входом элемента НЕ и первыми входами элементов

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

i-го элемента И"HE соединен с (i+2)— ми входами элементов И-НЕ с (i+1)-ro по (n-1)-й и является i-ым выходом блока.