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

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

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

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

Устройство содержит регистры 1-5, схемы 6 и 7 сравнения, распределители 8 и 9 импульсов, элементы И 10-12, группы элементов 13-15 И, элементы И 16-20, сумматор 21, счетчик 22 адреса, элемент ИЛИ 23, группу 24 элементов ИЛИ, элементы ИЛИ 25-27, группы

28 и 29 элементов ИЛИ, элемент ИЛИ 30, триггеры 31 и 32, элементы 33-35 задержки, информационные входы устройства 36, выход 37 Число найдено, выход 38 Адрес устройства, выход 39 Считывание, вход 40 тактовых импульсов, вход 41 Запись, вход 42 Запуск , вход 43 Адрес конца массива чисел, вход 44 Адрес начала массива чи- t сел, выход 45 Конец поиска . Позициями 46-48 обозначены выходы распределителя 9 импульсов, позициями 49-52 - выходы распределителя 8 импульсов, позициями 53-55 - выходы Больпе, Меньше и Равно схемы 6 сравнения соответственно.

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

сд

со 1C

со

3153

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

Поиск числа начинается по импульсу Запуск11 с входа 42 устройства, который устанавливает триггер 32 в единичное состояние, а триггер 31 в нулевое. Тактовые импульсы с входа 40 устройства поступают через элемент И i9, открытый сигналом с прямого выхода триггера 32 и через элемент и 1 8 9 открытый сигналом с инверсного выхода триггера 31, на вход распределителя 9 импульсов распределители 8 и 9 импульсов могут быть выполнены на элементах задержки, обес- печивакицих синхронизацию работы устройства). Тактовые импульсы через элемент И 12 на вход распределителя 8 импульсов не поступают, так как эле- мент И 12 закрыт нулевым логическим уровнем с прямого выхода триггера 31 Первый импульс с выхода 46 распре™ делителя 9 импульсов разрешаем прохождение адреса конца массива с выходов регистра 3 через группу 14 элементов И, который через группу 24 элементов ИЛИ поступает на вход регистра 5 и записывается в него по сигналу с выхода 46 распределителя 9 импульсов, поступающего через элемент ИЛИ 23 на его стробирующий вход, а через элемент задержки 33 - на выход 39 Импульс считывания, Чо этому импульсу из ЗУ ЭВМ считывается последнее число массива (верхняя граница, - ВГ), которое поступает на информационные входы 36 устройства и записывается в регистр 1. После сравнения последнего числа в массиве с ис комым на схеме 6 сравнения в зависимости от состояния ее выходов возможны три варианта работы устройства„ На выходе 55 Равно схемы 6 сравнения появляется сигнал 1. В этом случае он поступает на выход 37 устройства Число найдено, а через элемент ИПИ 30 на вход установки в О триггера 32, сигнал с прямого выхода которого запрещает прохождение в уст

0

5

0

5

0

0

5

ройство тактовых импульсов с его входа 40, а сигнал с обратного выхода триггера 32 поступает на,выход 45. Конец поиска. Это означает, что число найдено и поиск окончен. На выходе Меньше 54 схемы 6 сравнения появляется сигнал 1, он проходит через первый элемент И 10, открытый сигналом с выхода 46 распределителя 9 импульсов, задержанного на элементе 34 задержки (задержка осуществляется на время выборки числа из памяти и сравнения чисел на схеме сравнения 6), а также через элемент ИЛИ 25, элемент И, открытый сигналом с обратного выхода триггера 31, и эле мент ИЛИ 30 на вход установки в О триггера 32, который сигналом со своего прямого выхода запрещает прохождение в устройство тактовых импульсов с входа 40 устройства, а сигнал с обратного его выхода поступает на выход 45 Конец поиска. Это значит, что искомого числа в массиве нет и поиск окончен. На выходе 53 Больше схемы 6 сравнения появляется сигнал 1. В этом случае искомое число меньше последнего числа в массиве чисел и работа устройства продолжается.

Аналогично описанному второй имг пульс с выхода 47 распределителя импульсов 9 обеспечивает выдачу на выход 38 Адрес устройства адреса начала массива, а на выход 39 Импуяьс считывания - импульса считывания. После сравнения первого числа в массиве (нижняя граница - НГ) с искомым тоже возможны три варианта работы устройства. В первом случае, если числа равны, работа устройства аналогична описанному. Если первое число массива больше искомого числа, то сигнал с выхода 53 Больше схемы 6 сравнения через открытый элемент И 11 (на второй вход его поступает разрешающий импульс с выхода 47 распределителя 9 импульсов,, задержанный на элементе 35 задержки) поступает аналогично описанному на выход 45 Конец поиска, В этом случае искомого числа в массиве нет и поиск окончен Если искомое число больше вого числа в массиве, то это значит, что число может быть в массиве и работа устройства продолжается;,

С выхода 48 распределителя 9 импульсов импульс поступает на вход

515

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

Г4(НГ+ВГ)/2,

где ХЗ - ближайшее целое, меньшее или равное X.

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

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

Считанное число меньше искомого. В этом случае появляется сигнал Меньше на выходе 54 схемы 6 сравнения. Этим сигналом задается суммирующий режим счетчика 22 и открывается элемент И 17.

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

4п $ 20

25 30 «

д

5

5

46

счетчика 22 и открывается элемент И 16.

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

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

Г4 (НГ+ВГ)/2 ,

только одна из НГ или ВГ не равна соответствующему адресу при формировании первой границы.

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

Если искомое число в массиве отсутствует, то наступает такой момент когда ВГ становится меньше НГ (на единицу). Эту ситуацию фиксирует схема 7 сравнения, выдавая сигнал на своем выходе, когда содержимое регистра 3 меньше содержимого регистра 4. Этот сигнал через элемент ИЛИ 30 поступает на вход установки в О триггера 32 и на вход устройства 45. Триггер 32 сигналом со своего прямого выхода закрывает седьмой элемент И 19, запрещая прохождение в устройство тактовых импульсов с его входа 40.

71532

Таким образом, за первые два такта устройство определяет, попадает искомое число в рамки массива или нет. Если нет, то на выходе устройства 45 появляется единичный логический уровень , а на 37 единичный логический Уровень отсутствует, что свидетельствует о том, что число не найдено и а,кализ окончен. Если искомое число г|опадает в рамки массива, то устройство максимум за п тактов найдет это исло, при этом на выходе устройства 38 находится его адрес, а на выходах 37 и 45 появляются единичные Дровни, свидетельствующие, что число цайдено и анализ окончен Если числа в массиве нет, то через п тактов на н|ыходе устройства 45 появляется еди- 1{ичный уровень, а на 37 единичный вровень отсутствует, что свидетельст- ijyeT о том, что число не найдено и Анализ окончен.

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

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

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

8

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

/з

V5

Изобретение относится к вычислительной технике и может быть использовано в качестве автономного блока ЭВМ при поиске заданных чисел в упорядоченном массиве. Целью изобретения является повышение быстродействия. Устройство содержит регистры 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 ил.

Фиг.1