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

 

0flHCAHNE

ИЗОБРЕТЕНИЯ .. К АВТОРСКОМУ СВИДИИЛЬСТВУ

Союз Советских

Социалистических

Республик

<1993250 (ЬЦ Дополнительное к.ввт. саид-яу (22) Заявлено17.:04. 81 (2>) 3276775/18-24 г

«присоединейием заявки Ие (и) м.кп.

G 06 F 7/06

Госуяарсткеяний квинтет.СССР яе делаи нмбретеня1 я еткрнтий (23) Приоритет

Опубликовано 30,01. 83, Бюллетень ЙЯ 4 е

Дата ойублйкоевиия описания 30.01. 83 (ЩУК 681.325.66 (088.8) (72) Автор изобретения

Н=.Г. Иванов (71 ) Заявитель (54) УСТРОЙСТВО ДЛЯ ПОИСКА ЧИСЕЛ

В ЗАДАННОМ ДИАПАЭОНЕ

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

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

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

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

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

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

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

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

993250

s„ boa И, единичный выход третьего

25 триггера соединен с третьим входом четвертого элемента И, а нулевой выход - с входом четвертого элемента НЕ, выход которого соединен с третьим входом пятого элемента И,-, 30 выход элемента ИЛИ соединен с входом пятого элемента НЕ, выход которого соединен с первым входом десятого элемента И, второй вход которого соединен с выходом узла формн35 рования такта разряда знака, вход управления BTopox сдвигающего регистра соединен с шиной тактовых сигналов устройства, выход десятого элемента И является выходом устрой4О ства.

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

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

Устройство содержит элемент 1 равнозначности, элемент НЕ 2, сумматоры 3 и 4, сдвигающие регистры 5

-"и 6, элемент HE 7, элементы Й 8

12, триггеры 13 - 17, элементы HE

18 и 19, элементы И 20 - 23, элемент . 55 ИЛИ 24, элемент НЕ 25, элемент И 26 узел 27 формирования группировки тактов старших разрядов, узел 28 выделения такта стЬршего разряда, узел 29 формирования такта разряда знака, вход запуска устройства

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

31 и 32, шины тактового сигналов уст. ройства 33, выход устройства 34 °

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

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

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

20 давя четвертого и пятого элементов

И и с входом третьего элемента НЕ,. выход которого соединен с вторыми входами восьмого и девятого элемен993250

Знаки чисел оди-. наковые

3 наки чисел р азличные

° Э»

P 1

Рст 1 сс

Рст 0

Значения последовательного кода с выхода cyima opa 4

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

Разность в прямом коде минус 1

Не аналиэируется, ° так как разность заведомо велика

Разность в обрат ном коде

Разность в прямом коде

55 ступившего числа с числами, хранящимися в блоке памяти, вычисления разности между этими числами и их корреляции, т ° е. определения, ка» кое из хранящихся в блоке памяти чисел подлежит обновлению, как изменившееся за истекший промежуток времени °

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

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

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

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

Частота тактовых импульсов, постЯ паюцих на вход тактовых импульсов устройства 33 соответствует частоте поступления разрядов. входных кодов и служит для синхронизации работы всего устройства. Эти тактовые импульсы подаются на входы управления сдвигаюцих регистров 5 и б а также на тактовые входы узла 27 форми. — . рования группировки тактов старших разрядов, узла 28 формирования такта старшего разряда и узел формирования такта разряда знака. Каждый из этих узлов содержит счетчик и дешифратор, причем вход узла сое3р нен со счетным входом счетчика, выходы разрядов которого подсоединены таким образом к дешифратору, что на выходе его, являюцвмся выходом узла, сигнал появляется в момент прихода определенного по номеру импульса (или импульсов».

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

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

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

Одновременно с процессами сувиирования и вычитания производится анализ поступающих с выхода сумматоров 3 и 4 последовательных кодов.

С выхода узла 27 формирования группировки тактов старших разрядов тактовые -импульсы в момент поступления старших разрядов поступают на один

2-О из входов элементов И 8, 10 и 11 и, если s .старших разрядах .есть хотя бы одна единица, т.е. поступаюцее число не принадлежит диапазону, то в соответствующие им триггеры 13, 25 15 и 15 будет записана единица. Последовательный код с выхода сумматора 3 поступает на вход элемента И 8 и представляет собой число, раэное суююе двух исходных чисел, а пос- ледовательный код с выхода сумматора 4 поступает на вход элемента И 10 и через элемент НЕ 7 на вход элемента И 11 и представляет собой число, которое с точностью до единицы равно разности двух исходных чисел.

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

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

Для получения ответа о принадлежности числа диапазону достаточно

65,проверить наличие единицы в старших

993250

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

Как видно из таблицы, для полу-. гения на выходе суммы или разности двух чисел достаточно проанализировать знакИ кодов и наличие единицы переноса в старшем разряде и .использовать прямой код с выхода суммы сумматора 3, или использовать прямой, либо инверсный код с выхода суммы сумматора 4 ° Этот анализ производится с помощью элемента 1 равнозначности, который формирует сигнал только в том случае, если входные знаки одинаковы. Этот сигнал поступает.на входы элементов И

22 и 23 и через элемент НЕ 18 на вхо. ды элементов И 20 и 21.

Наличие единиц в старших разрядах кода суммы и кода разности ripoверяется элементами И 8, 10 и 11, на входы которых;также поступают тактовые импульсы старших разрядов

8 узла 27. Поскольку до конца операций суммирования и вычитания неизвестно в каком (прямом или обратном коде) будет представлена разность, то анализируются все три варианта прямой и обратный коды разности и прямой код суммы.

При наличии в старших разрядах суммы или разности хотя бы одной единицы соответствующий им триггер

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

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

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

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

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

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

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

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

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

Формула изобретения устройство для поиска чисел в за данном диапазоне, содержащее сумматор, сдвигающий регистр, элементы И, >

ЗО элемент НЕ, элемент ИЛИ, триггер, узел формирования группировки тактов старших разрядов, узел формирования такта старшего разряда, причем первый информационный вход устрой35 ства соединен с входом первого элемента НЕ, вход которого соединен с первым входом сумматора, второй информационный вход устройства соединен с вторым входом сумматора, вы4ц ход мпа) шего разряда суван сумматора соединен с первым входом первого элемента И и входом второго элемента НЕ, выход которого соединен с первым входом второго элемента И, вы45 ход пеРеноса сумматоРа соединен .с входом сдвигающего регистра и первым входом третьего элемента И, выходы элементов И с первого на третий . соединены с входами установки в едино ничное состояние триггеров с первого по третий соответственно, выход

;сдвигающего регистра соединен с тре". .:тьим входом сумматора, вторые: входы первого и второго элементов И соединены с выходом узла формирования группировки тактов старших разрядов, второй вход третьего элемента Й соединен с выходом узла формирования такта старшего разряда, входы установки в нулевое состояние

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

65 соответственно, выходы которых сое10

993250

9 ,динены с входами элемента ИЛИ; вхо ды узла формирования такта старше» го разряда, узла формирования группировки тактов старших разрядов.и вход управления сдвигающего регистра соединены с шиной тактовых сиг- налов устройства, о-..т л н ч а ю щ е. е с я тем, что, с целью повышения быстродействия устройства, в неговведены второй сумматор, второй сдвигающий регистр элемент равнозначности, узел формирования такта разряда знака, пять элементов И, три элемента НЕ, два триггера, причем первые входы. элемента равнозначности и второго сумматора соединены с первым информационным входом устройства, вторые входы элемента равнозначности и второго сумматора .соединены с вторым информацмэнным входом устройства, выход мяаежго. разряда суюсь второго сумматора соеди нен с первым входом шестого элемен- та И, выход переноса второго сумматора соединен. с входом второго сдвигающего регистра и первым входом седьмого элемента И, выход второго сдвигакщего регистра соединен.с -третьим входом второго сумматора,. выходы шестого и седьмого элементовИ соединены с входами установки -четвертого и пятого триггеров в единич.ное состояние соответственно, единичные выходы которых соединены.с первыми входами восьмого и девятого элементов И соответственно, выходы которых соединены с входами элемен-. та ИЛИ, второй. вход шестого элемен.та И соединен c:âíõoäîì узла формирования группировки тактов старших . вЂ,:разрядов, второй вход седьмого эле- мента И соединен с выходом узла формирования такта старшего разряда, вход узла формирования такта разряда знака и входы установки в нулевое состояние четвертого и пятого триггеров соединены с входом запуска уст ройства, выход элемента равнознач5 ности соединен с вторыми входами четвертого и пятого элементов И н входом третьего элемента НЕ, выход которого. соединен с вторыми входами восьмого и девятого элементов

10 И, единичный выход третьего триггера соединен с третьим входом четвертого элемента И, а нулевой выход — с входом Четвертого элемента НЕ, вы ход которого соединен с третьим вхо 5 дом пятого элемента И, выход элемента ИЛИ соединен с входом-пятого элемента НЕ, выход которого соединен с первым входом десятого элемента И,, второй вход которого соединен с вы-;

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

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

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

В 486316, кл. 6 06 F 7/Об; 1975.

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

9 486317, кл; 6 06 Р 7/06, 1975. .3. Авторское свидетельство СССР

40.9 822179, кл. G 06 F 7/06, 1981 (прототип).

Составитель В. Горохов

Редактор С. Юско Техред Т.Фанта. = Корректор А. Дзятко

Заказ 479/65 Тираж 704 Подписное

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

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

Филиал ППП "Патент", г.ужгород, ул. Проектная, 4