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

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

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

Недостатками этого устройства являются его низкое быстродействие необхрда1мость использования с ним специальной сложноЙ аппарату сопряжения со схемой ци ового кнюппеля или специализированной ЭВМ.

Известно устройство для поиска rtHc&i в заданном диапазонеf.содержащее регистры чисел, генератор тактовых сигналов, формирователи тактовых сигналов, элементы И, ИЛИ, НЕ триггеры, дешифратор 2.

Недостаток устройства - низкое быстродействие.

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

Недостатки уйтройства состоят в низком (стродействии при подаче на вход регистров чисел последовательным кодам заданной частота и не- . обходимОсти определения знака сравниваемых чисел до начала анализа, так как необходимо определить код

10 ( или обратный, которым передается число на вход сумматора. Это вытекает из того, что если, оба числа имеют один и тот же знак, то для выщ1слеьия разности между

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

20 различите знаки, то для вычисления разности между ними необходимо сложить их коды, для чего на вход сумматора оба числа должны быть поданы в прямом коде. Это условие в 25 устройстве-щ ототнпе обеспечивается наличием регистров, состояние знаковых разрядов которых определяют знаки чисел. Однако для загрузкн этих регистров затрачивается опре30деленное время.

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

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

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

того, узел формирования такта разряда знака содержит счетчик и даиифратор, причем вход узла соединен со счетным входом счетчика, выходы разрядов которого соединены с входами дешифратора, выход которого является выхрдом узла.

На чертеже представлена блок-схема устройства.

Устройство содержит элемент 1 равнозначности, элемент НЕ 2/ сумматоры 3 и 4, сдвигающие регистры 5 и 6, элемент НЕ 7, элементы И 8 12, триггеры 13 - 17, элементы НЕ 18 и 19, элементы И 20 - 23, элемент ЛИ 24, элемент НЕ 25, элемент И 26. зел 27 формирования группировки тактов старших разрядов, узел 28 выделения такта старшего разряда, зел 29 формирования такта разряа знака, вход запуска устройства 30, информационные входы устройства 31 и 32, шины тактового сигналов устойства 33, выход устройства 34.

Принцип работы устройства основан на методе сравнения вновь поступившего числа с числами, хранящимися в блоке памяти, шлчисления разности между этими числами и их кoppeJ|Iяции, т.е. определения, кое из хранящихся в блоке памяти чисел подлежит обновлению, как изменившееся за истекший промежуток времени.

Для вычисления ,раэности между числами-координатами, лодаваемлф на вход устройства, необходимо шачислить либо разность между этими числами, либо сумь этих чисел, в зависимости от их знаков и провести анализ полученных результатов. Ввиду того, что знаки входных чиселкоординат в начале анализа неизвестны, так как, числа на вход подгиотся мпгцфшми разрядами вперед/ устройство производит одновременно и суммирование, и вычитание этих чисел.

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

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

Последовательные коды чисел-поступают, начиная с мпадишх разрядов, по информахшонным входам 31 и 32 на входы сумматоров 3 и 4 и элемента равнозначности 1, причём первое число поступает на вход сумматора 4 через элемент НЕ 2. Сумматоры 3 и 4 снабжены одноразрядными сдвигающими регистрёши 5 и 6 соответственно для обеспечения переноса. Эти сдвигающие регистры осуществляют задержку импульсов переноса на один такт.

Частота тактовых импульсов nocr пающих на вход тактовых импульсов устройства 33 соответствует частоте поступления разрядов вход1К1х кодов и служит для синхронизгщии работы всего устройства. Эти тактовые импульсы подаются на входы упргшления сдвигающих регистров 5 и б . а также на тактовые входы узла 7 форм1грования группировки тактов разрядов, узла 28 форьшрования такта старшего разряда и узел формирования такта разряда знака. Каждый ик этих узлов содержит счетчик и дешифратор, причем вход узла соединен со счетным входом счетчика, выходы разрядов которого подсоединены таким образом к дешифратору, что на выходе его, являющимся выходом узла, сигнёш появляется в момент щ)Ихода определенного по номеру импульса импульсов j|.

Выход узла формирования тактов старшего разряда 28 соединен с входом элементов И 9 и 12, на которые подается тактовый импульс в момент суммирования старшего разряда чисел, через другие входы этих элементов И производится запись значений

единицы переноса в старшем разряде в триггеры 14 и 17 соответственно.

Одновременно с процессами суммирования и вычитания производится анализ поступающих с выхода сумматоров 3 и 4 последовательных кодов. С выхода узла 27 формирования группировки тактов старших разрядов тактовые импульсы в момент поступления старших рг1зрядов поступают на один из входов элементов И 8,10 и 11 и, если в старших разрядах «сть хотя бы одна единица, т.е. поступгиощее число не принадлежит диапазону, то в соответствующие им триггеры 13, .

15 и 1 будет записана единица. Последовательный ход с выхода сумматора 3 поступает на вход элемента И 8 и представляет собой число, равное сумме двух исходных чисел, а последовательный код с выхода сумматора 4 поступает на вход элемента И 10 и элемент НЕ 7 на вход элемента И 11 и представляет собой число, которое с точностью до единицы равно разности двух исходных чисел.

Значения, которые Могут принимать последовательные коды с выходов сумматоров 3 и 4, в зависимости от соотношення знаков входных чисел и от налнчня переноса единиц в старшем .

разряде (Pyf) представлены в табли це. ,

Знаки чисел одиЗнаки чисел раз наковые личные

e:Ll i:--

ct Q PcT:X

Значения последоЗначения последо0вательного кода с вательного кода с выхода сумматовыхода сумматора 4 ра 3

55

60

Для получения ответа о принадлежности числа диапазону достаточно 65, проверить наличие единицы в старши

разрядах его сумлм или разности с числом-центром диапазона.

Как видно из таблицы, длЯ получения на выходе суммы или разности двух чисел достаточно проанализировать знаки кодов и наличие единицы переноса в старшем разряде и .использовать пр51мой код с выхода суммы сумматора 3, или использовать прямой, либо инверсный код с выхода суммы сумматора 4. Этот анализ производится с помощью элемента 1 равнозначности, который формирует сигнал только в том случае, если входные знаки одинаковы. Этот сигнал поступает-на входы элементов И 22 и 23 и через элемент НЕ 18 на входы элементов И 20 и 21.

Наличие единиц в старших разрядах кода суммы и кода разности проверяется элементами И 8, 10 и 11, на вхойы которых;также .поступают тактовые импульсы старших разрядов 8 узла 27. Поскодьку до конца операций суммирования и вычитания неизвестно в каком (прямом или обратном коде) будет представлена разность, то анализируются все три варианта прямой и обратный коды разности и прямой код сум№з.

При наличии в старших разрядах суммы или разности хотя бы одной единицы соответствующий им триггер 13, 15 или 16 устанавливается в единичное состояние. По окончании суммирования элемент 1 равнозначности выдае на элементы И 20 - 23 сигнал, который определяет, с какого триггера должен считываться результат анализа.

Рассмотрим работу устройства при различных вариантах.

В а р-и ант 1. Знаки чисел. Ьдинаковы, в старшем разряде есть (единица переноса. Тогда, если триггер 15 установлен в единичное состояние, т.е. в старших разрядах разнос. ти есть хотя бы одна единица, сигнал с его единичного выхода через элемент И 22 поступает на вход элемента ИЛИ 24, сигнализируя, что число диапазону не принадлежит.

Вариант 2. Знаки чисел различны, в старшем разряде единица переноса отсутствует. В этом случае открывается элемент И 23 и результат анализа зависит от состояния триггера 16.

Вариант 3. Знаки чисел раз личны, в старшем разряде есть единица переноса. В этом случае разность чисел заведомо велика и, значит, число диапазону не принадлежит

Вариант 4. Знаки чисел различны, в старшем разряде единица переноса отсутствует. В этом схпучае результат анализа зависит от состояния триггера 13.

Таким образом, если число не принадлежит диапазону, на выходе элемента ИЛИ 24 пр исутствует сигнал, означающий, что число за пределами диапазона. Этот сигнал че рез элемент НЕ 25 поступает на вход элемента 26, №а второй вход которого поступает сигнал с выхода узла 28 формирования такта разряда знака, который формируется в мрмент поступления на вход устройства раз ряда знака чисел, и на шлходе устройства 34 формируется результат анализа входных чисел.

По сигналу запуска все триггеры устройства устанавливаются в исходное состояние.

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

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

Устройство для поиска чисел в за данном диапазоне, содержащее сумматор , сдвигающий регистр, элементы И, элемент НЕ, элемент ИЛИ, триггер, узел формирования группировки тактов старших разрядов, узел фс мирования такта старшего разряда, причем первый информационный вход устройства соединен с входом первого элемеята НЕ, вход которого соеданен с первым входом сукшатсч а, второй информационный вход устройства соединен с вторым входом сумматора, выход Mnajpiero: разряда сумми. сумматора соединен с первым входе первого элемента И и входом вт( элемента НЕ, выход которого соединен с первым входом второго элемента И, выход переноса сумматора соединен с входом сдвигающего регистра и первым входом третьего элемента И, выходы элементов И с первого на третий соединены с входами установки в единичное состояние триггеров с первого по третий соответственно, выход : сдвигающего регистра соединен с входом сумматора, вторые входы первого и второго элементов И соединены с выходом узла формирования группировки тактов старших разрядов, второй вход третьего элемента И соединен с выходом узла формирования такта разряда, входы установки в нулевое состояние триггеров с первого по третий соединены с входом запуска устройГства, а единичные выходы первого и второго триггеров соединены с первыми входами четвертого, и пятого элементов И соответственно, захода которых сое.динёны с входами элемента ИЛИ, входа Узла формирований такта старшего разряда, узла фармярования группировки тактов старших разрядов и вход управления сдвигающего регистра соединены с цшной тактовых сигнглов устройства, о.т л и ч а ю щ евся тем, что, с целью повышения быстродействия устройства, в него введены второй сумматор, второй сдвигающий регистр, элемент равнозначности, узел ф мирования такта разряда знака, пять элементов И, три элемента НЕ, два триггера, причем первые BXOJKI элемента равнозначности и второго сумматора соедонены с первдлм информационным входом устройства, вторые входы элемента равнозначности и второго сумматора соединешя с вторым внформацяовным laxoдом устройства, выход мягмивего разряда суммы второго сумматора соеди-ней с первым вхоя/ом шестого элемента И, выход переноса второго сумматора соединен.с входом второго сдвигающего регистра и первым входсм седьмого элемента И, выход второго одвигсиощего регистра соединен, с третьим входом второго сумматора, выходы шестого и седьмого элементов И соединены с входами установки четвертого и пятого триггеров в едщничное состояние соответственно, единичные выходы КОТОРЫХ соединены с первыми входами восьмого и девятого элементов И соответственно, выхода которцх соединены с входами элемента ИЛИ второй вход шестого элемента И соединен с выходом узла форлдарования группировки тактов старших . разрядов, второй вход седьмого элемента И соединен с выходом узла фор 4ирования ТёИста ставшего разряда.

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

o И, единичный выход третьего триггера соединен с третьим входом четвертого элемента И, а нулевой выход - с входом Четвертого элемента НЕ, ю ход KOTORpro соединен с третьим вхо5дсм пятого элемента И, выход элемента ИЛИ соединен с входом пятого злемента НЕ, выход которого соединен с перШЕМ входом десятого элемента И, /второй вход которого соединен с вы-, ходом узла .фop 4иpoвaния такта разря

0 да знака, вход управления второго сдвигающего.регистра соединен с шиной тактовых сигналов устройства, а выход десятого элемента И являет5 ся выходом устройства.

2. Устр ЛсТво по п. 1, о т л и чающееся тем, что узел формирования такта разряда знака содержит счетчик и д0ан4фатор,причем вход уз)1а соединен со счетным входсм«1

0 счетчика, выходы разрядов которого соединены с входами дешифратора, выход котсфк го является выходом узла.

Источники информации, принятые во внимание при экспертизе

5

1.Авторское свидетельство СССР 486316, кл. е 06 F 7/06; 1975.

2.Авторское свидетельство СССР 486317, кл. G 06 F 7/06, 1975.

3.Авторское свидетельство СССР 0 822179, кл. G 06 F 7/06, 1981

(прототип).