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

Изобретение относится к элементам Дискретной автоматизации и вычислительной техники и может быть использовано при реализации технических средств цифровых систем контроля и управления

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

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

/

Устройство содержит схему 1 срав- нения, реверсивный счетчик 2, формирователи 3 и 4 адреса, триггеры 5 и 6 элемент ИЛИ 7, элемент ИЛИ-НЕ 8, элементы И 9-11, элемент 12 задержки, мультиплексор 13, входы 14-20 и выхо- ды 21-23.

Каждый формирователь адреса состоит из счетчика 24, группы сумматоров 25 по модулю два, элемента ИЛИ-НЕ 26, элемента 27 задержки, элемента И 28, элемента ИЛИ 29, входов 30 установки начального кода и входов 31 установки конечного кода.

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

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

Например, для поиска ближайшего большего числа по отношению к заданному, которое поступает на входы 15, подается сигнал на вход 16 для под- готов ки элемента И 9 и соответственно реверсивного счетчика 2 к работе в режиме сложения. Затем .подается сигнал на вход 18, в результате чего заданное число переписывается в реверсивный счетчик 2, триггер 5 устанавливается в нулевое состояние, формирователи 3 и 4 адреса устанавливаются в исходное состояние. Исходное состояние формирователей 3 и 4 адреса должно быть таким, чтобы с прихо

дом тактовых импульсов на их входы

суммирования формирователь 3 адреса начинал выдавать адреса чисел, хранящихся в массиве информации, начиная с 1 и до п/2, а формирователь 4 адреса - с п/2 + 1 и до п (где п - количество чисел в массиве информации) . В случае нечетного количества чисел, хранящихся в массиве информа

Q

5 0

5

о

5

0

5

0

5

ции, последний адрес, выдаваемый формирователем 3, и первый адрес, выдаваемый формирователем 4, совпадают, т.е. формирователь 3 выдает адреса

n+1 д,

-я- , формирователь 4 с 1 и до п-И

и до п.

В каждом конкретном случае, в зависимости от количества чисел в мас- сиве информации, можно изменять количество адресов, выдаваемых формирователями 3 и 4 адреса, с помощью входов 30 установки начального кода и входов 31 установки конечного кода. При этом необходимо учитывать, что при подаче сигнала на установочные входы формирователей 3 и 4 адреса происходит запись в них чисел, характеризующих исходные состояния. Эти числа обусловлены сигнапом О с прямого выхода триггера 5, поступающего на младший разряд декрементирующего счетчика 24, и двоичным кодом, поступающим на остальные разряды с входов

30установки начального кода. Двоичный код, подаваемый на входы

31установки конечного кода, обусловливает последний адрес, выдаваемый формирователями 3 и 4. С выдачей последнего адреса формирователями 3

и 4 на выходе элемента ИЛИ-ИЕ 26 возникает сигнал 1, который через элеIз

мент 27 задержки за время у Т

(где Т - период тактового импульса) поступает на второй вход элемента И 28. С приходом очередного тактового импульса с входа 18 счетчик 24 выдает опять первый адрес, минуя исходное состояние. Это происходит потому, что при записи числа в счетчик 24 на вход младшего разряда подается сигнал 1 с прямого выхода триггера 5, который переходит в единичное состояние с началом работы устройства.

Команда на поиск числа поступает на вход 20 запуска, в результате которой триггер 5 переводится в единичное состояние и разрешает прохождение тактовых импульсов с входа 19 через триггер 6, элемент И 11 и элемент ИЛИ-НЕ 8. Сигнал 1 поступает также с прямого выхода триггера 5 на информационные входы формирователей 3 и 4 адреса. В качестве триггера 5 исполь,- зу.ется стандартный D-Tpnfrep с входами

установки в 1 и О, а вкачестве триггера б - D-триггер типа защелки.

С приходом положительного перепада первого тактового импульса формирователь 3 адреса переходит в очередное состояние и выдает свой первый адрес числа. Этот адрес, за счет того что в данный момент с выхода триггера 6 приходит сигнал 1 на управляющий вход мультиплексора 13, поступает на выходы 23 устройства; происходит считывание числа из массива информации о Считанное число поступает на входы 14 устройства и сравнивается с заданным числом в схеме 1 сравнения. Если сравнения не произошло, то с приходом отрицательного перепада первого импульса формирователь 4 адреса переходит в очередное состояние и выдает свой первый адрес числа. Этот адрес за счет того, что в данный момент с выхода триггера 6 приходит сигнал О на управляющий вход мультиплексора 13, поступает на выходы 23 устройства; происходит считывание очередного числа из массива информации. Это число также сравнивается с заданным. Таким образом, с приходом каждого тактового импульса происходит формирование двух адресов, считывание по ним чисел и последовательное сравнение их с заданным.числом. Поочередное подключение информационных выходов формирователей 3 и 4 адреса к выходам 23 устройства происходит за счет прихода сигналов на управляющий вход мультиплексора 13, а эти сигналы меняются в зависимости от прихода положительного или отрицательного потенциала очередного тактового импульса.

Если после сравнения всех чисел, хранящихся в массиве информации, нет решения, то с выхода переполнения формирователя 3 или 4 адреса (зависит от того, какой формирователь стал раньше выдавать адреса) прихо- дит сигнал в виде положительного перепада импульса переполнения на один из входов элемента ИЛИ 7 и происходит увеличение заданного числа на единицу, а затем процесс повторяется.

При сравнении чисел с выхода схемы . 1 сравнения поступает сигнал на вход синхронизации триггера 5 и он переводится в нулевое состояние. В результате этого запрещается прохождение

95316

тактовых импульсов на формирователи 3 и 4 адреса и мультиплексор 13, на выходе конца работы появляется сигнал, что число найдено, на выходах 22 - значение числа в двоичном оде, на выходах 23 - адрес, в котором хранилось число в массиве информации.

JQ Для поиска ближайшего меньшего числа по отношению к заданному сиг- нал подается на вход 17, в результате чего реверсивный счетчик 2 переводится в режим вычитания и на его выходе

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

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

20

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

5

0

5

0

5

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

2. Устройство по п. 1, отличающееся тем, что формирова

0

5

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

Изобретение относится к элементам дискретной автоматизации и вычислительной техники и может быть использовано при реализации технических средств цифровых систем контроля и управления. Цель изобретения - повышение быстродействия. Устройство поиска числа содержит схему сравнения 1, реверсивный счетчик 2, формирователи адреса 3,4, триггеры 5,6, элемент ИЛИ 7, первый элемент ИЛИ-ИЕ 8, элементы И 9, 10, 11, элемент задержки 12, мультиплексор 13. Каждый формирователь адреса 3, 4 содержит счетчик, группу сумматоров по модулю два, элемент ИЛИ-НЕ, элемент задержки, элемент И, элемент ИЛИ. С приходом положительного перепада тактового импульса адрес числа, хранящегося в массиве информации, выдает первый формирователь адреса 3, а с приходом отрицательного перепада второй формирователь адреса 4. Мультиплексор 13 по сигналам с тактового входа 19 устройства попеременно подключает к выходным шинам то выходы первого формирователя 3 адреса, то выходы второго формирователя 4 адреса. При этом за один тактовый импульс происходит формирование двух чисел, хранящихся в массиве ( информации, считывание этих чисел и последовательное их сравнение с задан- 3 ным числом. 1 з.п.ф-лы, 3 ил. о to 2 CD s

Фиг.2

ISftlW 18,

ubin.niPtn. 3

иич ew.. 4

twx AEPtn

4

a

гь

XDCIXIXIXZXIXIXIX:

Фиг. Ъ .