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

Оп ЙСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕПЛЬСТВУ Союз СоветскихСоциалистическихРеспублик и 1993250(Щ Заявлено 17,04. 81 (2) 3276775/18-24присоединейиемзвявки Иф РМ К з С 06 Г 7/06 ГосуяарсткеянцЯ квинтет СССР яе делаи нмбретеняЯ я еткрнтеЯ(54) УСТРОЙСТВО ДЛЯ ПОИСКА ЧИСЕЛ В ЗАДАННОМ ДИАПАЭОНЕИзобретение относится к вычислите. льной технике и может быть использовано в устройствах обработки циФ- ровой инФормации.Известно устройство для сортировки данных, содержащее ассоциатив- ный запоминающий, блок, блок управления, буферный запоминающий блок, " ключевые схем, блок записи 1.Недостатками этого устройства яв- ляются его низкое быстродействие, необходимость использования с ним специальной сложной аппаратуры сопряжения со схемой цифрового кнюпаеля или специапиэированной ЭВИ.Известно устройство для поиска чисел в заданном диайазоне, .содержащее регистры чисел, генератор тактовых сигналов, Формирователи такто вых сигналов, элементы И, ИЛИ, ЙЕ, триггеры, дешифратор ) 2.:Недостаток устройства - низкое быстродействие.Наиболее близким .техническим решением к предлагаемому является устройство для поиска чисел в заданном диапазоне, садержащее регистры, генератор тактовых сигналов, формирователи тактовых сигналов, - . элементы И, ИЛИ, .НЕ,-триггеры, дешифратор, сдвигающий регистр, сумматор 1 31.Недостатки устройства состоят внизком быстродействии .прн подачена вход регистров чисел последовательным кодом заданной частоты и необходимости определения знака сравниваеьих чисел до начала анализа, 1 О так как необходимо определить код.(прямой йли обратный, которым передается число на вход сумматора.Это вытекает из того, что если,оба числа имеют один и тотже знак,то .для вычислеьня разности междунима необходимо из одного числа,вычесть другое число, для чего навход сумматора должно быть подано.одно чисцо в прямом коде, а другоев обратном. Если же числа имеютразличные знаки, то для вычисленияразности между ними необходимосложить их коды, для чего иа входсумматора оба числа должны быть поданы в прямом коде. Это условие вустройстве-прототипе обеспечивается наличием регистров, состояниезнаковых разрядов которых определяютзнаки чисел. Однако для загрузкиэтих регистров затрачивается определенное время.ь тов И, единичный выход третьего5 триггера соединен с третьим входомчетвертого элемента И, а нулевойвыход - с входом четвертого элемекта НЕ, выход которого соединен стретьим входом пятого элемента И30 выход элемента ИЛИ соединен с входом пятого элемента НЕ, выход которого соединен с первым входом десятого элемента И, второй вход которого соединен с выходом узла Форми 35 рования такта разряда знака, входуправления второго сдвигающего регистра .соединен с шиной тактовых сигналов устройства, выход десятогоэлемента И является выходом устрой 4 О ства.Крсуе того, узел.формированйятакта разряда знака содержит .счетчик и дешифратор, причем вход узла соединен со счетным входом счетчика, выходы разрядов которого соеди 45 иены с входами дешифратора, выходкоторого является выходом узла.На чертеже представлена блок-схема устройства.Устройство содержит элемент 15 О равнозначности, элемент НЕ 2, сумматоры 3 и 4, сдвигающие регистры 5"и 6, элемент НЕ 7, элементы Й 812., триггеры 13 - 17, элементы НЕ18 и 19, элементы И 20 - 23, элемент . 55 ИЛИ 24, элемент НЕ 25, элемент И 26узел 27 формирования группировкитактов старших разрядов, узел 28выделения такта стЬршего разряда,узел 29 формирования такта разряда знака, вход запуска устройства30, информационные входы устройства31 и 32, шины тактового сигналов устройства 33, выход устройства 34Принцип работы устройства основан на методе сравнения вновь поЦель изобретения - повышение быстродействия устройства.Подавленная цель достигается тем, что в устройство, содержащее сумматор, сдвигающий регистр, элемент И, элемент ИЛИ элементы НЕ, триггер, узел формирования группи розки тактов старших разрядов, узел формирования такта старшего разряда, причем первый инФормационный вход устройства соединен с входом первого элемента НЕ, вход которого соединен с первым входом сумматора, второй информационный вход устройства соединен с вторым входом сумматора, выход младшего разряда сумки сумматора соединен с первым входом первого элемента И и входом вто-. рого элемента НЕ, выход которого соединен с первым входом второго элемента И, выход переноса сумматора соединен с входом сдвигающего регистра и первым входом третьего, элемента И, выходы элементов И с пер. вого на третий соединены с входами установки в единичное состояние три геров.с первого по третий соответственно, выход сдвигающего регистра соединен с третьим входом суммато ра, вторые входы первого и второго. элементов И соединены с выходом узла Формирования группировки тактов старших разрядов, второй вход третьего элемента И соединен с выходом узла формирования такта старшего разряда, входы установки в нулевое состояние триггеров с первого по третий соединены с входом запуска устройства, а единичные выходы первого и второго триггеров соединены с первыми входами четвертого. и пятого элементов И соответственно, выходы которых соединены с входами элемента ИЛИ, входы узла Формирования такта старшего разряда, узла формирования группировки Тактов стар ших разрядов и вход управления сдвигающего регистра соединены с шиной тактовых сигналов устройства, введены второй сумматор, второй сдвигающий регистр, элемент равнозначности, узел Формирования такта разряда знака, пять элементов И, три элемей" та НЕ, два триггера, причем первые входы элемента равнозначности и второго сумматора соединены с первым информационным входом устройства, .а вторые входы элемента равнозначности и второго .сумматора соединены с вторым информационным входом устройства, выход младшего разряда сумьн второго сумматора соединен с первым входом шестого элемента И, выход переноса второго сумматора соединен с входом второго сдвигаюЦего регистра и первым входом седьмого элемента И, выход второго сдвигающего регистра соединен с третьим входом второго сумматора, выходышестого и седьмого элементов И соединены с входами установки четвертого и пятого триггеров в единичноесостояние соответственно, единичныевыходы которых соединены с первымивходами восьмого.и девятого элементов И соответственно, выходы которыхсоединены с входами элемента ИЛИ,второй вход шестого элемента И соединен с выходом узла Формированиягруппировки тактов старших разрядов, второй вход седьмого элемента И соединен с выходом узла формирования такта старшего разряда,вход узла формярования такта разрядного знака и входы установки в нулевое сбстоякие четвертого и пятоготриггеров соединены с входом запуска устройства, выход элемента равнозначности соединен с вторыми вхо.ч 20 давя четвертого и пятого элементов И и с входом третьего элемента НЕ,;выход которого соединен с вторымивходами восьмого и девятого элеменЗнаки чисел раз- личные вввввв ввтвв Р 1 Овв Р. 0 Значения последовательного кода с выхода сувяаатора 4 Значения последовательного кода с хода сумматора 3ив вв ю тв вв Разность в прямом коде минус 1 Не анаЛнзируввется,так какразностьзаведомовелика Разностьв обратномкоде Разностьв прямомкоде ступившего числа с числами, хранящимися в блоке памяти, вычисления разности между этими числами и их корреляции, те. определения, кач кое из хранящихся в блоке памяти чисел подлежит обновлению, как изменившееся за истекший промежуток времениДпя вычисления разности между числами-координатами, подаваевввщ . на вход устройства, необходимо вычислить либо разность между этими числами, либо сумму этих чисел, в зависимости от их знаков и провести анализ полученных результатов. Вви ду того, что знаки входных чисел- координат в начале анализа неизвестны, так как числа на вход подаются мпадшими разрядами вперед, устройство производит одновременно и суммирование, и вычитание этих чисел.Устройство рабОтает следующим образом.На вход устройства подаются последовательные коды чисел,подлежа щих сравнению. При этом на первый информационный вход поступает, например, число, которое принимают за центр диапазона, в котором необходимо произвести поиск и найти, число, принадлежащее данному диапазону. На второй информационный вход поступают числа, хранящиеся в блоке памяти. Числа представлена в прямом коде, отрицательные числа имеют единицу в знаковом разряде. Последовательные коды чисел поступают, начиная с мпадших разрядов, по информационным входам 31 и 32 на входы сумматоров 3 и 4 и элемента равнозначности 1, причем первое число поступает на вход сумматора 4 через элемент НЕ 2. Сумматоры 3 и 4снабжены одноразрядными сдвигающимирегистрами 5 и б соответственнодпя обеспечения переноса. Эти сдвигаюцие регистры осуществляют задержку импульсов переноса на один такт. Частота тактовых импульсов, постЖ паюцих на вход тактовых импульсовустройства 33 соответствует частотепоступления разрядов. входных кодови служит дпя синхронизации работывсего устройства. Эти тактовые импульсы подаются на входы управлениясдвигаюцих регистров 5 и б а также на тактовые входы узла 27 форми-рования группировки тактов старшихразрядов, узла 28 формирования такта старшего разряда и узел формирования такта разряда знака. Каждыйиз этих узлов содержит счетчик идешифратор, причем вход узла соепинен со счетным входом счетчика, выходы разрядов которого подсоединенытаким образом к дешифратору, что навыходе его, являюцимся выходом узла, сигнал появляется в момент прихода определенного по номеру импульса или импульсов.Выход узла формирования тактовстаршего разряда 28 соединен с вхо дом элементов И 9 и 12, на которые.подается тактовый импульс в моментсуммирования старшего разряда чисел, через другие входы этих элементов И производится запись значений 10 единицы переноса в старшем разрядев триггеры 14 и 17 соответственно.Одновременно с процессами сувиирования и вычитания производитсяанапиз поступающих с выхода сумматоров 3 и 4 последовательных кодов.С выхода узла 27 формирования группировки тактов старших разрядов тактовые -импульсы в момент поступлениястарших разрядов поступают на один 2 О из входов элементов И 8, 10 и 11 и,если в .старших разрядах есть хотябы одна единица, т.е. поступаюцеечисло не принадлежит диапазону, тов соответствующие им триггеры 13, 25 15 и 1 б будет записана единица. Последовательный код с выхода сумматора 3 поступает на вход элемента И 8и представляет собой число, раэноесуыае двух исходных чисел, а пос-ледовательный код с выхода сумматора 4 поступает на вход элемента И 10и через элемент НЕ 7 на вход элемента И 11 и представляет собой число,которое с точностью до единицы равно разности двух исходных чисел.Значения, которые Могут приниматьпоследовательные коды с выходов сум,маторов 3 и 4, в зависимости от соотношения знаков входных чисел и отналичия переноса единиц в старшем 40 разряде (Р,) представлены в табли,це. Дпя получения ответа о принадлежности числа диапазону достаточно 65,проверить наличие единицы в старшихразрядах его суюаю или разности счислом-центром диапазона.Как видно из таблицы, для полу-,ения на выходе суммы или разностидвух чисел достаточно проанализировать знакИ кодов и наличие единицы переноса в старшем разряде и .использовать прямой код с выходасуммы сумматора 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 Формируется результат анализа входных чисел.Йо сигналу запуска все триггеры устройства устанавливаются в исходное состояние.Преимуществом предлагаемого устройства по сравнению с.устройством- прототипом является отсутствие необходимости в предварительной загрузке чисел в регистры. Это дает возможность повысить быстродействиеустройства.Формула изобретенияУстройство для поиска чисел в заданном диапазоне, содержащее сумматор, сдвигающий регистр, элементы И,30 элемент НЕ, элемент ИЛИ, триггер,узел формирования группировки тактов старших разрядов, узел формирования такта старшего разряда, причем первый информационный вход устрой ства соединен с входом первого элемента НЕ, вход которого соединен с первым входом сумматора, второй инФормационный вход устройства соединен с вторым входом сумматора, вы ход мпадшего разряда сумки сумматора соединен с первым входом первого элемента И и входом второго элемента НЕ, выход которого соединен с первым входом второго элемента И, вы ход переноса сумматора соединен .свходом сдвигающего регистра и первым входом третьего элемента И, выходы элементов И с первого на третий . соединены с входами установки в единичное состояние триггеров с первого по третий соответственно, выход ,сдвигающего регистра соединен с тре" тьим входом сумматора, вторые: входыпервого и второго элементов И соединены с выходом узла формирования группировки тактов старших разрядов, второй вход третьего элемента Й соединен с выходом узла Формирования такта старшего разряда, вхо.ды установки в нулевое состояние 6 О триггеров с первого по третий соединены с входом запуска устройства, а единичные выходы первого и второго триггеров соединены с первыми входами четвертого,и пятого элементов И 65 соответственно, выходы которых сое,динены с входами элемента ИЛИ;входыузла Формирования такта старше го разряда, узла Формирования группировки тактов старших разрядов.и вход управления сдвигающего регистра соединены с шиной тактовых сиг-налов устройства, от л н ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства, в него введены второй сумматор, второй сдвигающий регистр элемент равнозначности,узел Формирования такта разряда знака, пять элементов И, три элемента НЕ, два триггера, причем первые входы. элемента равнозначности и второго сумматора соединены с первым информационным входом устройства, вторые входы элемента равнозначности и второго сумматора .соединены с вторым информацмэниым входом устройства, выход мвадевго разряда суюсь второго сумматора соеди" нен с первым входом шестого элемен-та И, выход переноса второго сумматора соединен с входом второго сдвигающего регистра и первым входом седьмого элемента И, выход второго сдвигакщего регистра соединен.с третьям входом второго сумматора,. выходы шестого и седьмого элементов И соединены с входами установки четвертого и пятого триггеров в единич.ное состояние соответственно, единичные выходы которых соединены.с первыми входами восьмого и девятого элементов И соответственно, выходы которых соединены с входами элемен-.та ИЛИ, второй. вход шестого элемен.та И соединен с:выходом узла формирования группировки тактов старших , в ,:разрядов, второй вход седьмого эле-мента И соединен с выходом узла формирования такта старшего разряда,вход узла формирования такта разряда знака и входы установки в нулевоесостояние четвертого и пятого триггеров соединены с входом запуска устройства, выход элемента равнознач ности соединен с вторыми входамичетвертого и пятого элементов И нвходом третьего элемента НЕ, выходкоторого соединен с вторыми входами восьмого и девятого элементов 10 И, единичный выход третьего триггерасоединен с третьим входом четвертого элемента И, а нулевой выход - свходом Четвертого элемента НЕ, выход которого соединен с третьим вхо дом пятого элемента И, выход элемента ИЛИ соединен с входом пятого элемента НЕ, выход которого соединен спервым входом десятого элемента И,,второй вход которого соединен с вы-, 20 ходом узла формирования такта разряда знака, вход управления второгосдвигающего.регистра соединен с шиной тактовых сигналовустройства,а выход десятого .элемента И являет ся Выхядои устройства.2. Устройство по п. 1, о т л ич а ю щ е е с я тем, что узел Формирования такта разряда знака содержит счетчик и дешифратор,причемвход узла соединен со счетным входомсчетчика, выходы разрядов которогосоединены с входаьы дешифратора, выход которого является выходом узла.Источники информациипринятые во внимание при экспертизе1. Авторское свидетельство СССР9 486316, кл. 6 06 Г 7/Об; 1975.2. Авторское свидетельство СССРВ 486317, кл; 6 06 Р 7/06, 1975.993250 ставитель В. Гороховхред Т.фантаэ К рекзор А. Дзят едактор С. Юско Заказ 479/65 Тираж 704 ВНИИПИ Государственно по делам изобретен 113035, Москва, Ж, Р