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

 

Изобретение относится к вычислительной технике и может быть использовано в качестве автономного блока ЭВМ при поиске заданных чисел в упорядоченном массиве. Целью изобретения является повышение быстродействия. Устройство содержит регистры 1-5, схемы сравнения 6,7, распределители импульсов 8,9, элементы И 10, 11, 12, 16-20, группы 13, 14, 15 элементов, сумматор 21, счетчик адреса 22, элементы ИЛИ 23, 25, 26, 27, 30, ГРУППЫ 24, 28, 29 ЭЛЕМЕНТОВ ИЛИ, триггеры 31, 32, элементы задержки 33, 34, 35. Устройство определяет: попадает искомое число в рамки массива или нет. Если искомое число попадает в рамки массива, то за счет реализации в устройстве метода половинного деления для поиска заданного числа достигается увеличение быстродействия. 2 ил.

СОЮЗ СОВЕТСКИХ . СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК

09> (11) (59 4 G 06 F 7/06

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

- М11 !,,; r - Д н дато СкОМ г СНИДГПЛьСтвМ

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

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

ПРИ ГКНТ СССР

1 (21) 4425147/24-24 (22) 12.05.88 (46) 30.12 ° 89. Бюл. У 48 (71) Киевский политехнический инсти- тут им. 50-летия Великой Октябрьской социалистической революции (72) А.Г. Горбунов, С.M. Баронов, Н.Г. Попович, P.Ñ. Кабаченко и В.А. Сидоров (53) 681.325(088.8) (56) Авторское свидетельство СССР

В 997029, кл. G 06 F 7/06, 1978.

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

Р 1183955, кл. G 06 F 7/06, 1985о (54) УСТРОЙСТВО ДЛЯ ПОИСКА ЗАДАННОГО

ЧИСЛА (57) Изобретение относится к вычислительной технике и может быть использовано в качестве автономного блока

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

ЭВМ при поиске заданных чисел в óïîрядоченном массиве.

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

На фиг.l изображена блок-схема устройства; на фиг. 2 — временные диаграммы работы устройства.

Устройство содержит регистры 1-5, схемы 6 и 7 сравнения, распределители 8 и 9 импульсов, элементы И 10-12, группы элементов 13-15 И, элементы И

16-20, сумматор 21, счетчик 22 адре. са,.элемент ИЛИ 23, группу 24 элементов ИЛИ, элементы ИЛИ.25-27, группы

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

1-5, схемы сравнения 6,7, распределители импульсов 8,9, элементы И 10,11, 12, 16-20, группы 13, 14, 15 элементов И, сумматор 21, счетчик адреса

22, элементы ИЛИ 23, 25, 26, 27, 30, группы 24, 28, 29 элементов ИЛИ, триггеры 31, 32, элементы задержки

33, 34, 35. Устройство определяет: попадает искомое число в рамки массива или нет. Если искомое число попадает в рамки массива, то за счет реализации в устройстве метода поло-! винного деления для поиска заданного числа достигается увеличение быстро,действия, 2 ил. с Меаб

28 и 29 элементов ИЛИ, элемент ИЛИ

30, триггеры 31 и 32, элементы 33-35 . задержки, информационные входы устрой. ства 36, выход 37 "Число найдена", выход 38 "Адрес устройства", выход 39 С©

"Считывание", вход 40 тактовых импульсов, вход 41 "Запись", вход 42 "За- . 4йЬ пуск",вход 43 "Адрес конца массива чиcesI" вход 44 "Адрес начала массива чи сел", выход 45 "Конец поиска" .Позициями

46-48 обозначены выходы распределителя 9 импульсов, позициями 49-52.— выходы распределителя 8 импульсов, . позициями 53-55 — выходы "Больше", "Меньше" и "Равно" схемы б сравне,ния соответственно.

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

1532914

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

"Запись" с входа 41 устройства про" ходит через элементы ИЛИ 26 и 27 на стробкруощие входы регистров 3 и 4, записывая в нкх адрес конца массива чисел, поступающих с входов 43 и 44 устройства через группы 28 и 29 элементов ИЛИ.

Поиск числа начинается по кмпуль-у "Запуск" с входа 42 устройства, который устанавливает триггер 32 в единичное состояние, а триггер 31 в нулевое. Тактовые импульсы с, входа 40 устройства поступают через элемент И !9, открытый сигналом с прямого выхода тригrepa 32 и через элемент И 18, открытый сигналом с инверсного выхода триггера 31, на вход распределителя 9 импульсов (распределители Я к 9 импульсов могут быть выполнены на элементах задержки, обеспечкваюшкх синхронизацию работы устройства ). Тактовые импульсы через элемент И 12 на вход распределителя Я импульсов не поступают, так как эле.мент И 12 закрыт нулевым логическим уровнем с прямого выхода триггера 31.

Первый импульс с выхода 4б распределителя 9 импульсов разрешает про, хождение адреса конца массива с выхо, дов регистра 3 через группу 14 элементов И, который через группу 2ч с 35 элементов ИЛИ поступает на вход регистра 5.к записывается в него по сигналу с выхода 46 распределителя 9

1 импульсов, поступающего через элемент ИЛИ 23 на. его стробируюпций вход, а через элемент задержки 33 — на выход 39 "Импульс считывания", По этому кмпульсу кз ЗУ ЭВМ считывается последнее число массива (верхняя гра45 нкца — ВГ), которое поступает на информационные входы 36 устройства и записывается в регистр 1. После сравнения последнего числа в массиве с искомым на схеме б сравнения в завкси50 мости от состояния ее выходов возможны три варианта работы устройства, На выходе 55 "Равно" схемы б сравненкя появляется сигнал 1 . В этом случае он поступает на выход 37 устройсгва "Число найдено", а через эле- " мент ИЛИ 30 на вход установки в "0 триггера 32, сигнал с прямого выхода которого запрещает прохождение в устройство тактовых импульсов с его входа 40, а сигнал с обратного выхода триггера 32 поступает на,выход 45, "Конец поиска", Это означает, что число найдено и поиск окончен. На выходе "Меньше" 54 схемы б сравнения появляется сигнал "1", он проходит через первый элемент И 10, открытый сигналом с выхода 46 распределителя

9 импульсов, задержанного на элементе 34 задержки (задержка осуществляется на время выборки числа из памяти и сравнения чисел на схеме сравнения 6,1, а также через элемент ИЛИ

25, элемент И, открытый сигналом с обратного выхода триггера 31, и элемент ИЛИ 30 на вход установки в "О" триггера 32, который сигналом со своего прямого выхода запрещает прохождение в устройство тактовых импульсов с вхо,да 40 устройства, а сигнал с обратного его выхода поступает на выход 45 "Конец поиска". Это значит, что искомого числа в массиве нет и поиск окончен. На выходе 53

"Больше" схемы 6 сравнения появляется сигнал "1". Б этом случае искомое число меньше последнего числа в массиве чисел и работа устройства продолжается.

Аналогично описанному второй имг пульс с выхода 47 распределителя импульсов 9 обеспечивает выдачу на вы- . ход 38 "Адрес устройства." адреса начала массива, а на выход 39 "Импульс считывания" — импульса считывания.

После сравнения первого числа в массиве (нкжняя граница — НГ) с искомым тоже возможны три варианта работы устройства. Б первом случае, если числа равны, работа устройства ана" логична описанному,,Если первое число массива больше искомого числа, то сигнал с выхода 53 "Больше" схемы 6 сравнения через открытый элемент

И 11 (на второй вход его поступает разрешающий импульс с выхода 47 распределителя 9 импульсов, задержанный на элементе 35 задержки) поступает аналогично описанному на выход 45

"Конец поиска", Б этом случае искомого числа в массиве нет и поиск окончен. Если искомое число больше пер" вого числа в массиве, то это значит, что число может быть в массиве и работа устройства продолжается, С выхода 48 распределителя 9 импульсов импульс поступает на вход

5 153291 установки в "1" триггера 31, который сигналом со своего обратного выхода запрещает прохождение тактовых импульсов через элемент И 18.на вход распределителя 9 импульсов, а сигналом .со своего прямого выхода разрешает прохождение тактовых импульсов через элемент И 12 на вход распределителя 8 импульсов. Первый импульс появляется на выходе 49 распределителя 8. Этот импульс разрешает запись информации в счетчик 22, в результате чего сумма НГ и ВГ с выходов сумматора 21 со сдвигом на один разряд в сторону младших разрядов заносится в счетчик 22. Этот адрес является первой (в последующем — очередной) границей. Таким образом, первая граница Г определяется следующим об- 20 разом:

Г - 1(НГ+ВГ) /2), где (Х вЂ” ближайшее целое, меньшее или равное Х.

После этого появляется импульс на 25 выходе 50 распределителя 8, по которому разрешается прохождение границы через группу элементов И 15 и группу элементов ИЛИ 24 на вход регис1ра 5, Она записывается в него по импульсу 30 с выхода 50 распределителя 8, поступающего на его стробирующий вход че" рез элемент ИЛИ 23, а также через элемент 33 задержки на выход 39 "Импульс считывания", По этому импульсу из ЗУ ЭВМ считывается число с адресом

Г и записывается в регистр с информационных входов устройства 36 ° Первая схема сравнения осуществляет сравнение искомого числа, находящегося в регистре 2, с числом, считанным в первый регистр 1. При этом возможны три варианта работы устройства, Считанное число равно искомому.

В, этом случае появляется сигнал Рав- 45 но" на выходе 55 схемы 6 сравнения, по которому, аналогично описанному на выходах 37 и 45 появляются единичные сигналы.

Считанное число меньше искомого.

В этом случае появляется сигнал "Меньше" на выходе 54 схемы 6 сравнения.

Этим сигналом задается суммирующий режим счетчика 22 и открывается элемент И 17 °

Считанное число больше искомого.

В этом случае появляется сигнал "Больme" на выходе 53 схемы 6 сравнения, по которому задается вычитающий режим, 4 б счетчика 22 и открывается элемент

И 16.

По импульсу на выходе 51 распределителя 8 содержимое счетчика 22 увеличивается или уменьшается на единицу в зависимости от заданного режима работы. После этого появляется импульс на выходе 52 распределителя 8, который прохрдит либо через элемент И 16, либо через элемент И 17 и стробирует запись нового адреса либо в регистр

3, либо в регистр 4. В резупьтате этого в один из регистров 3 или 4 осуществляется запись адреса, сформированного в счетчике 22, Таким образом, если число, считанное из ЗУ ЭВМ, меньше искомого числа (т.е. в первой половине массива чисел искомого числа нет), то к первой границе прибавляется единица и полученный адрес записывается в регистр 4 в качестве адреса нижней границы нового массива чисел, содержащего искомое число, если же число, считанное из ЗУ ЭВМ, больше искомого числа (т,е. во второй половине массива чисел искомого числа нет), то из первой границы вычитается единица и полученный адрес записывается в регистр 3 в качестве адреса верхней границы нового массива чисел, содержащего искомое число. Следовательно после выборки числа по адресу первой границы и его анализе, размер массива чисел уменьшается вдвое. После этого снова появляется импульс на выходе 49 распределителя 8, по которому формируется вторая граница по тому же правилу.

Г = (Нг+ВГ)/2, только одна из НГ или ВГ не равна соответствующему адресу при формировании первой гранипы.

В дальнейшем устройство работает аналогично описанному.

Если искомое число в массиве отсутствует, то наступает такой момент„ когда ВГ становится меньше НГ (на единицу). Эту ситуацию фиксирует схема 7 сравнения, выдавая сигнал на своем выходе, когда содержимое регистра 3 меньше содержимого регистра 4.

Этот сигнал через элемент ИЛИ 30 поступает на вход установки в "0" триггера 32 и на вход устройства 45.

Триггер 32 сигналом со своего прямого выхода закрывает седьмой элемент И

19, запрещая прохождение в устройство тактовых импульсов с его входа 4П.

7 !5329!4

Таким образом, sa первые два такта устройство определяет, попадает искомое число в рамки массива или нет.

Если нет, то на выходе устройства 45 появляется единичный логический уро5 вень, а на 37 единичный логический уровень отсутствует, что свидетельствует о том, что число не найдено и анализ окончен, Если искомое число г опадает в рамки массива, то устройство максимум за и тактов найдет это исло, при этом на выходе устройства 38 находится его адрес, а на выхо" дах 37 и 45 появляются единичные 15 ровни, свидетельствующие, что число айдено и анализ окончен, Если числа массиве нет, то через и тактов на выходе устройства 45 появляется вди" ичный уровень, а на 37 единичный

«1равень отсутствует, что свидетельстует о том, что число не найдено и нализ окончен.

За счет реализации в устройстве метода половинного деления для отыскивания заданного числа достигается увеличение быстродействия в результате уменьшения количества обращений к ЗУ ЗБМ при поиске заданного числа.

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

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

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

И, выход которого соединен с первым входом второго элемента ИЛИ, выход меньше первой схемы сравнения соединен с первым входом третьего элемента И, выходы разрядов третьего регистра соединены с первой группой входов второй схемы сравнения, вход "Запуск" устройства соединен с входом установки в "О" триггера, прямой выход которого соединен с первым входом четвертого элемента И, о т л и ч а ю щ е ес я тем, что, с целью повышения быстродействия, в него введены пятый регистр, два распределителя импульсов, сумматор, вторая и третья группы эле" ментов И,,второй триггер, шестой, седьмой и восьмой элементы И, третий, четвертый и пятый элементы ИЛИ; три группы элементов ИЛИ, второй и третий элементы задержки, причем вход тактовых импульсов устройства соединен с первым входом пятого элемента И, второй вход которого соединен с прямым выходом второго триггера, а выход соединен с первым входом шестого эле-, мента И и вторым входом четвертого элемента И, выход которого соединен с входом первого распределителя импульсов, второй вход шестого элемента И соединен с инверсным выходом первого триггера и первым входом седьмого элемента И, а выход соединен с входом второго распределителя импульсов, первый выход которого соединен с первым входом третьего элемента ИЛИ, с управляющими входами элементов И первой группы и через первый элемент задержки с вторым входом третьего элемента И, второй выход второго распределителя импульсов соединен с вторым входом третьего элемента ИЛИ, с управляющими входами элементов И второй группы и через второй элемент задержки с вторым входом первого элемента И, выход которого соединен с первым входом четвертого элемента ИЛИ, второй вход которого соединен с выходом третьего элемен»: та И, а выход соединен с вторым входом седьмого элемента И, выход которого соединен с вторым входом первого элемента ИЛИ, третий вход которого подключен к выходу второй схемы сравнения, а выход, соединен с входом установки в "О" второго триггера, инверсный выход которого является выходом "Конец поиска" устройства, а вход установки в "l" подключен к входу "Запуск" устройства, третий выход второго распределителя импульсов соединен с входом установки в "1" первого триггера, первый выход первого распределителя импульсов соединен с входом разрешения записи счетчика

9 i53291 адреса, информационные входы которого соединены с выходами разрядов сумматора, первая группа входов которого подключена к выходам разрядов третьего регистра и к информационным вхо5 дам элементов И первой группы, выходы которых соединены с первыми входами соответствующих элементов ИЛИ группы,выходы которых соединены с информационными входами четвертого регистра, выходы разрядов которого являются выходами адреса устройства, а управляющий вход подключен к выходу третьего элемента ИЛИ и через третий элемент задержки соединен с выходом "Разрешение считывания" устройства, второй выход первого распределителя импульсов соединен с третьим входом третьего элемента ИЛИ, с управляющими входа-ъо ми элементов И третьей группы, информационные входы которых подключены K выходам разрядов счетчика адреса и к первым входам соответствующих элементов ИЛИ второй и третьей групп, вторые25 входы которых являются соответственно адресами конца и начала массива устройства, а выходы соединены соответственно с информац юнными входами!

О третьего и пятого регистров, выходы разрядов которого соединены с вторыми группами входов сумматора, второй схемы сравнения и информационными входами элементов И второй группы, выходы которых соединены с вторыми входами соответствующих элементов ИЛИ первой группы, третьи входы которых соединены с выходами соответствующих элементов И третьей группы, выход

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

1532914

Редактор Л. Пчолинская

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101

Эаказ 8IOO/53

ВНИИПИ Государственного

113035, Составитель А. Козлов

Техред Л, Олийнык Корректор М. Кучерявая

Тираж 668 Подписное. комитета по изобретениям и открытиям при ГКНТ СССР

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