Устройство для сравнения чисел

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистическихРеспублик 960799(51) М.Кл.з с присоединением заявки ЙоС 06 Е 7/04 Государственный комитет СССР по делам изобретений и открытий(23) ПриоритетОпубликовано 23,0982, Бюллетень Мо 35 1 ЩУДК 681.325,5 (088. 8) Дата опубликования описания 23. 09. 82 РАВНЕНИЯ ЧИСЕ 4 УСТРОЙСТВО чи-.оичИзобретение относится к автоматике и вычислительной технике и можетбыть использовано, в частности, приреализации технических средств длявыделения локально-максимальныхсел из множества сравниваемых двных чисел,Известно устройство для определения экстремально двоичного числа намножестве двоичных чисел, содержащеетриггеры, счетчики, логические схемы,позволяющие отыскивать. экстремальноезначение, ближайшее к нему значениечисла и разность между ними. Поискэкстремумов производится последовательным прибавлением ко всем числампо единице до переполнения (первымпереполняется регистр с максимальнымчислом), число восстанавлйвается вычитанием содержимого счетчика, изме-.няется содержимое регистров и.циклповторяется 1).Недостатком этого устройства является малое быстродействие.Наиболее близким техническим решением к предложенному является устройство для выделения экстремальногоиэ и щ-разрядных двоичных чисел, которое содержит и в-разрядных регистров на триггерах, выходы триггера каждого 1-го разряда 1-го регистра. (где 1 = 1,2, , щ; 3 = 1,2, ,и)соединены с информационными входами 5 . (1 х 3)-го Узла анализа, Узел анализа состоит иэ трех элементов И, причем .первые входы первого и второго элементов И соединены с первым управляющим входом узла, а их вторые входы " с информационными входами узла. Выход первого элемента И подключен к первому входу узла, выход второго элемента. И соединен с первым входом третьего элемента И исо вторым выходом узла, второй и третий входы третьего элемента И подключены ко второму и третьему управляющим входам узла, а выход третьего элемента И соединен с третьим выходом узла, первый выход .каждого (з. х 3)-го узла анализа соединен с 3-ым входом 1-го элемента. ИЛИ первой группы, второй выход каждого (1 х 3)-го узла анализа подключен к 3-ому входу 1-го элемента ИЛИ второй группы. В устрой-, ство также входят и дополнительных триггеров, группы элементов И-НЕ, И, группа элементов ИЛИ, причем выход каждого 1-го эЛемента ИЛИ первой группы соединен с первым входом З 0.,т,-го элемента И-НЕ группы, с 1-ыминформационным выходом устройства и:с первым управляющим входом 1-ыхузлов анализа, Выход каждого 1-гоэлемента ИЛИ второй группы подключенко второму входу 1-го элемента И-НЕгруппы, третий выход каждого (1 х 1)-.гоузла анализа соединен с 1-ым входом1-го элемента ИЛИ третьей группы,выход каждого 1-го элемента ИЛИ,третьей .группы подключен ко входуустановки в нулевое состояние -годополнительного триггера, прямойвыход каждого -го дополнительноготриггера соединен с 1;ым выходомуправления устройства и со вторымуправляющим входом 1-х узлов анализа, выход каждого -го элемента И-НЕгруппы подключен к первому входух-го элемента И группы, выход каждого из которых соединен с третьим управляющим входом (з. + 1).-ых узлов.,анализа и со вторым входом (х+1)-гоэлемента И группы, вход управленияустройства подключен ко второму входу первого элемента И группы итретьим управляющим входам узлованализа первых разрядов всех регистров Г 23,Недостатком укаэанного устройстваявляются малые функциональные возможности.Цель изобретения - расширение фун-ЗОкциональных возможностей .устройстваза счет обеспечения определения локально-максимальных двоичных чисел.Поставленная цель достигается тем,что в устройстве для сравнения чисел,З 5содержащем п узлов анализачисел,щ узлов управления, каждый из которыхсостоит из двух элементов И, причемвыход первого элемента И узла управления подключен к первому .входу второго элемента И, второй вход которогосоединен с задающим входом узла управления, а выход - .с выходом узлауправления, входы первого элементаИ подключены к информационным входам 45узла управления, триггер, инверсныйвыход триггера подключен ко входузапуска каждого иэ узлов анализа чи-сел,. прямой выход триггера соединенс задающим входом первого узла управОления и с первым входом задания признака каждого из узлов анализа чисел,выход каждого г-го узла управления,где х = 1,2, , .(щ), подключен, к задающему входу (д+1)-го узла сравнения и к -му входу задания признака каждого иэ узлов. анализа чисел,выход щ-го узла управления соединенсо входом установки в нулевоесостояние триггера, выход результатасравнения каждого 1-го разряда, .где6 О1,2, , щ каждого 1 сго узлаанализа чисел, где В 1,2, , п,подключен к Е-му. входу 1-го узла управления, выход результата анализакаждого р-го узла анализа чисел, где 65 р = 2, 3, , (щ), соединен со входом переноса (р)-го и (р+1)-го узлов анализа чисел, выходы результата первого и щ-го узлов анализа чисел подключены ко входам переносов второго и (щ)-го узлов анализа чисел соответственно, первый,и втооой выходы переноса 1-го разряда каждого Е-го узла анализа чисел соединены с входами переноса .1-го разряда (Е) -го и ф+1) -го соответственно узлов анализа чисел.Причем в устройстве каждый узел анализа чисел содержит регистр, состоящий из щ триггеров, и узлов поразрядного сравнения, элементы И, ИЛИ, триггеры, причем прямой и инверсный выходы каждого 1-го триггера регистра, где 1 = 1,2, , щ, соединены с первым и вторым входами соотетственно 1-го поразрядного узла сравнения, третий вход каждого из которых подключен к выходу первого. элемента ИЛИ, первый выход каждого 1-го поразрядного узла сравнения соединен с 1-ым входом второго элемента ИЛИ, выход которого подключен ко входу установки в единичное состояние первого триггера, инверсный выход которого. соединен с первыми входами первого элемента И и первого элемента ИЛИ, второй и третий вхьды которого подключены ко входам переноса узла анализа чисел, прямой выход первого триггера соединен с четвертым входом каждого поразрядного узла сравнения, вход запуска .узла анализа чисел подключен ко второму входу первого элемента И, выход ко" торого соединен с выходом результата анализа узла анализа чисел, инверсный выход каждого 1-го триггера регистра подключен к 1-му входу второго элемента И, выход которого соединен со (щ+1)-ым входом второго элемента ИЛИ и со входом:установки в единичное соетояние второго триггера, прямой выход которого подключен к пятому входу каждого поразрядного узла:сравнения,. 1-ый вход задания признака узла анализа чисел соединен с шестым входом 1-го поразрядного узла сравнения, первый и второй входы переноса разряда поразрядного 1-го узла анализа чисел подключены к седьмому и восьмому входам соответственно 1-го узла поразрядного сравнения, второй и третий выходыкаждого 1-го поразрядного узла сравнения соединены с первым. и вторым выходами переноса 1-го разряда, выход результата сравнения подключен к четвертому выходу поразрядного узла сравнения.Кроме тогО, каждый узел поразряд" ного сравнения содержит элементы И, ИЛИ, НЕ, схему сравнения, причем первый вход узла соединей с первымвходом первого элемента И, выход которого подключен к первому входу первого элемента ИЛИ, выход которого соединен с первыми входами второго элемента И и второго элемента ИЛИ, выход которого подключен к пер вому входу схемы сравнения, второй вход узла соединен со вторым входом схемы сравнения, выход которой подключен к первому выходу узла и через элемент НЕ - к первому входу третьего элемента ИЛИ, третий вход узласоединен со вторым входом первого элемента И, второй вход третьего элемента ИЛИ подключен к четвертому входу узла, пятый вход. узла соединен с первым входом третьего элемента И и со вторым входом второго элемента И, выход которого подключен к третьему выходу узла, шестой вход узла соединен с управляющим входом схемы сравнения, седьмой вход узла подключен ко второму входу третьего элемен.та И, восьмой вход узла соединен со вторым входом. первого элемента ИЛИ, выход третьего элемента НЕ.подключен к четвертому выходу узла.На чертеже приведена функциональная схема устройства.Устройство содержит триггер 1 управления, щ узлов 21, 21, , 2 щ управления, каждый из которых состоит из элементов И 3 и 4, узлов 5, 51,5 п анализа чисел, каждый из которых содержит а поразрядных узлов 61, 61, , б п 1 сравнения, элемент ИЛИ 7 элемент И 8, триггеры 9 и 10, элемент ИЛИ 11, элемент И 12, регистр 13, состоящий из щ триггеров 14, 14, , 14 р,. Каждый поразрядный узел б анализа состоит из элементов И 15 и 16, элементов ИЛИ 17. и 18, элемента ЙЕ 19, элемента И 20, схемы 21 сравнения, элемента ИЛИ 22, шины 23 установки в единичное состояние, шины 24 управления.Устройство работает следующим образом.Триггер 1 управления и триггеры 9 и .10 узлов анализа чисел установлены в нулевое состояние.На первом этапе работы устройствапроизводится разбиение и чисел на несвязанные между собо группы, раз; деленные хотя бы,одиим числом, равным нулю (в пределах каждой группы на втором этапе производится выделение локально-максимальное с числа). На первом этапе Устройство работает следующим образом.При поступлении по.шине 23 установки в единичное состояние сигнала,устанавливаются в единичное состояниевсе триггеры 10 узлов 5 анализа чисел. После этого в регистры 13 принимаются сравниваемые числа. Еслизаписанное в регистр 13 число равнонулю, единичные уровни инверсных выходов всех триггеров 14 этого регистра поступают на соответствующиевходы элемента И 12 и единичный уровень с выхода этого элемента устанавлйвает в нулевые состояния триггер,10 и через элемент ИЛИ 7 - триггер 9.Нулевой уровень прямого выхода триг- гера 10 поступает на первый вход элементов И 16 и 15 всех поразрядных уз, лов б сравнения данного узла 5 анали за чисел. В результате осуществляетсяразрыв цепей передачи информации между узлами .5 анализа чисел узлами,имеющими номера меньшие и большие номера рассматриваемого узла 5 анализа 15 чисел. Таким образом, и узлов 5 анализа чисел устройства разделяются на(1+1) группу узлов, где Е - количество узлов 5 анализа чисел, содержащихравные. нулю числа. В последующем,при выполнении второго этапа, сравнение чисел производится независимо.в пределах каждой группы.Если записанное в регистр 13 число не равно нулю, на соответствующиевходы элемента И 12 поступают какединичные, так и нулевые уровни синверсных выходов каждого триггера 14,и на выходе элемента И 12 - нулевойуровень. В результате триггеры 10 и9 данного узла 5 анализа числа останутся в единичном состоянии. При этомединичный уровень с прямого выходатриггера 10 поступает на первый входэлемента И 16.и 15 всех поразрядныхузлов 6 сравнения данного узла 5 З 5.анализа чисел и открывает цепи передачи информации между узлами анализа;исел с номерами меныцими и большими номера рассматриваемого узла Единичный уровень с прямого выхода триг гера 9, поступающий через элемент.ИЛИ 11 на первый вход элемента И 20каждого поразрядного узла б сравнения данного узла 5 анализа чисел,разрешает выдачу содержимого тригге ра 14 регистра 13 для сравнения впределах группы узлов 5 анализа чисел На втором этапе работы устройства 5 О происходит йоразрядное, начиная состаршего разряда, сравнение чисел.При сравнении одноименных разрядов чисел в пределах каждой группы узлов 5 анализа чисел возможны ситу ации, когда все триггеры анализируемого разряда содержат нули, или единицы, или когда часть триггеров анализируемого разряда содержит единицы, а часть - нули.Второй этап начинается с поступления но шине 24 управления единичного сигнала, который устанавливает в единичное состояние триггер 1 управления. Единичный уровень прямого выхода триггера 1 управления подаф 5 ется на первый вход схемы 21 сравнения всех поразрядных узлов б сравнения старшего разряда.В первых двух ситуациях отсутствует информация, позволяющаясравнить числа. В связи с этим необходимпереход к анали у соседнего младшегоразряда сравниваемью чисел в пределахрассматриваемой группы. Этот переходреализуется следующим образом. Еслив триггерах 14 анализируемого стар.шего разряда сравниваемых чисел в 10пределах группы содержатсянули, натретий вход схеьаи 21 сравнения каждого поразрядного узла 6 сравненияданного разряда в пределах этой группы поступает единичный уровень с ну левого выхода каждого триггера 14.На единичном выходе каждого триггера14 этой группы есть нулевой уровень,который подается на второй вход элемента И 20 и на выходе этого элемента тоженулевой уровень. Этот нулевойуровень .поступает на второй вход элемента ИЛИ 18, на первый вход этогоэлемента подается нулевой уровень свыхода элемента И 1 б узла .5 анализачисел (в пределах данной группы узлов), имеющего номер, меньший рассматриваемого. С выхода элемента ИЛИ18 нулевой уровень подается на второйвход элемента И 1 б и на первый входэлемента ИЛИ 17 данного поразрядного узла сравнения. На втором входе элемента ИЛИ 17 находится, также нулевой уровень с выхода элемента И 15 этого же поразрядного узла сравнения, так как .на второй вход элемента И 15подается нулевой уровень, с выходаэлемента ИЛИ 17 одноименного поразрядного узла сравнения б, узда 5 анализа числа (в пределах рассматриваемойгруппы узлов), имеющего номер, на еди 10 ницу больший рассматриваемого. Следовательно, на выходе элемента ИЛИ 17 каждого поразрядного узла 6 сравнения в пределах рассматриваемой группы будет нулевой уровень, который подается 45 на второй вход схемы 21 сравнения. В результате нулевой уровень с выхода схемы 21 сравнения инвертируется элементом НЕ 19 и единичный уровенье с его выхрда через элемент ИЛИ 22 поступает на соответствующий вход управляющего элемента И 4 старШей схемы управления.Если же во всех триггерах 14 анализируемого старшего разряда в пределах группы содержатся единицы, на третьем входе схемы 21 сравнения каждого из поразрядных узлов 6 сравне ния в пределах этой группы будет нулевой уровень с инверсного выхода60 триггера 14. Следовательно, нулевой уровень с выхода схемы 21 сравнения инвартируется элементом НЕ 19 и через элемент ИЛИ 22 подается единичный уровень на соответствующий вход управляющего элемента И 4 старшей схемы 2 управления-.Если часть триггеров 14,в пределах группы содержит единицы, а часть - нули (третья ситуация), на второй вход схемы 21 сравнения каждого пЬ- разрядного узла сравнения в пределах анализируемой группы поступает единичный уровень хотя бы с одного содержащего единицу триггера 14 узла 5 анализа чисел, имеющего .номер меньший рассматриваемого (через элементы ИЛИ 18 и 17), или от содержащего единицу триггера 14 узла 5 анализа чисел, имеющего номер, больший рассматриваемого (через элемент И 15, элемент ИЛИ 17) . Единичный уровень на выходе .схемы 21 сравнения будет в случае, если на третьем его входе будет единичный уровень с инверсного выхода находящегося в .нулевом состоянии триггера 14. Тогда единичный уровень с выхода схемы 21 сравнения через соответствующий вход элемента ИЛИ 7 устанавливает в нулевое состояние триггер 9 данного узла 5 анализа чисел. Единичный уровень с инверсного выхода триггера 9 подается на второй вход элемента ИЛИ 22 данного узла 5 анализа и поступает на соответствующий вход управляющего элемента И 4 каждой схемы 2 управления. Нулевой уровень с прямого выхода триггера 9 данного узла 5 анализа чисел поступает на второй вход элемента ИЛИ 11 этого же узла 5 анализа чисел. На первый и третий. входы элемента ИЛИ 11 поступают нулевые уровни с выхода элементовИ 8 узлов 5 анализа чисел, имеющих номер соответственно на единицу больший и меньший рассматриваемого, так как на второй вход элемента И 8 всех узлов 5 анализа чисел подан нулевой уровень с инверсного выхода триггера 1 управ" ления, находящегося в единичном состоянии, Нулевой уровень с выхода элемента ИЛИ 11 узла 5 анализа чисел, триггер которого установлен в нулевое состояние, подается на первые входы элементов И 20 и ИЛИ 17 данного узла 5 анализа чисел и разрывает цепь прохождения содержимого регистра 13 для сравнения в пределах группы узлов 5 анализа чисел, т.е. данный регистр 13 выбывает из процесса дальнейшего анализа.Когда процесс сравнения старшего разряда анализируемых чисел заканчивается, на всех входах управляющего элемента И 4 старшей схемы 2 управления будет единичный уровень. На выходе элемента И 3 этой схемы управления будет также единичный уровень, который поступает на второй вход элемента И 3 соседней младшей схемы 2 управления и первый вход схемы 21 сравнения соседнего младшего разрядаанализируемых чисел и разрешает их сравнение.Работа устройства выделения локальныхмаксимумов при анализе следующих разрядов происходит, аналогично рассмотренному второму этапу работы. 5После окончания процесса сравнения младшего разряда чисел единичный уровень с выхода элемента И 15 младшей схемы 2 управления устанавливает в нулевое состояние триггер 1 управ О ления. Единичный уровень с инверсного выхода триггера 1 управления поступает на второй вход элемента И 8 каждого узла 5 анализа числа. На первом входе элемента И 8 будет единичный: уровень с единичного выхода триггера 9, оставшегося в единичном состоянии, т.е, содержащего локально-максимальное число.Единичный уровень с выхода элемента И 8 подается через элемент ИЛИ 11 на первый вход элемента И 20 каждого поразрядного управления узла 6 числа с номером, на единицу меньшим и большим рассматриваемого, что разрешает выдачу, наряду с локально-максимальными, соседних значений (по одному с каждой стороны от локально-максимального).Таким образом, устройство обеспечивает выделение иэ множества сравниваемых чисел (например, ординат дискретиэированного процесса) локальных максимумов и соседних с ними чисел (по одному с каждой стороны). Обрабатывая результаты работы устройства 35 на ЗВИ, можно по известным алгоритмам уточнить положение максимума (например, абсциссы дискретиэированногопроцесса). Это позволяет использоватьустройство выделения локальных максимумов в средствах цифрового корреляционного анализа случайных сигналов.Формула изобретения451. Устройство для сравнения чисел, содержащее и узлов анализа чисел, щ узлов управления, каждый из которых состоит из двух элементов И, прнчем)О выход первого элемента И узла управления подключен к первому входу второго элемента И, второй вход которого соединен с задающим входом узла управления, а выход - с выходом узла управления, входы первого элемен. та И подключены к информационным входам узла управления, триггер., о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет обеспечения опре- деления локальных экстремумов, в нем инверсный выход триггера подключен ко входу запуска каждого из узлов анализа чисел, прямой выход триггера соединен с задающим входом первого 65 узла управления и с первым входомзадания признака каждого из узлованализа чисел, выход каждого 1-гоузла .управления, где 1 = 1, 2,(1+1)-го узла сравнения и к 1-мувходу задания признака каждого изузлов анализа чисел, выход щ-го узла управления соединен со входомустановки в нулевое состояние триггера, выход результата сравнениякаждого -го разряда, где р = 1, 2,щ каждого 1-го узла анализа чисел, где 1 = 1, 2, , и, подключенк л-му входу )-го узла управления,выход результата анализа каждогор-го узла анализа чисел,где .р = 2, 3,(щ), соединен со входом переноса (р) -го и (р+1)-го узлов анализа чисел, выходы результата первогои щ-го узлов анализа чисел подключены ко входам переносов второго и(щ)-го узлов анализа чисел соответственно, первый и второй выходы переноса -го разряда каждого К-го узла анализа чисел соединены с входамипереноса 3-го разряда (Ы)-го и(1+1) -го соответственно узлов анализа чисел.2. Устройство по п. 1, о т л ич а ю щ е е с я тем, что в нем каждый узел анализа чисел содержит регистр, состоящий,из щ триггеров,и узлов поразрядного сравнения, эле-менты И, ИЛИ, триггеры, причем пряой и инверсный выходы каждого -готриггера регистра, где= 1,2,соединены с первым и вторым входами соответственно 1"го поразрщрого узла сравнения, третий вход кйкдого иэ которых подключен к выходу первого элемента ИЛИ, первый выход каждого -го поразрядного узла сравнения соединен с -ым входом второгоэлемента ИЛИ, выход которого подключен ко входу установки в единичноесостояние первого триггера, инверсный выход которого соединен с первыми входами первого элемента И и первого элемента ИЛИ, второй и третийвходы которого подключены ко входампереноса узла анализа чисел, прямойвыход первого триггера соединен счетвертым входом каждого поразрядного .Узла сравнения, вход запуска узла анализа чисел подключен ко второму входу первого элемента И, выходкоторого соединен с выходом результата анализа узла анализа чисел, инверсный выход кажцого -го триггерарегистра подключен к-му входу второго элемента И, выход которого соединен с (щ+1)-ым входом второгоэлемента ИЛИ и со входом установкив единичное состояние второго триггера, прямой выход которого подключенк пятому входу каждого поразрядногоузла сравнения -й вход задания приэ12 960799 ИИПИ з 7282/58 Тираж 731 Подписное ПП "Патент", г.ужгород, ул.Проектная лиа нака узла анализа чисел соединен сшестым входом 3-го поразрядного узла сравнения, первый и второй входы переноса разряда 3-го поразрядного узла анализа чисел подключены к седьмому и восьмому входам соответствен но 3-го узла поразрядного сравнения, второй и третий выходы каждого -го поразрядного узла сравнения соединены с первым и вторым выходами переноса 3-го разряда, выход результата 10 сравнения переноса подключен к чет-. вертому выходу поразрядноцо узла сравнения.3. Устройство по п. 1, о т л и ч аю щ е е с я тем, что в нем каждый узел поразрядного сравнения содержит элементы И, ИЛИ, НЕ, схему сравнения, причем первый вход узла соединен с ,первым входом первого элемента И, выход которого подключен к первому входу первого элемента ИЛИ, выход которого соединен с первыми входами второго элемента И и второго элемента ИЛИ, .выход которого подключен к первому входу схемы сравнения, второй вход узла соединен со вторым входом схемы сравнения, выход которой подключен к первому выходу узла и черезэлемент НЕ - к первому входу третьего элемента ИЛИ, третий вход узласоединен со вторым входом первогоэлемента И, второй вход третьего элемента ИЛИ подключен к четвертому входу узла, пятый вход узла соединенс перВым входом третьего элемента Ии со вторым входом второго элементаИ, выход которого подключен к третьему выходу узла, шестой вход узласоединен с управляюцим входом схемысравнения, седьмой вход узла подключен ко второму входу третьего элемента И, восьмой вход узла соединен совторым входом первого элемента ИЛИ,выход третьего элемента НЕ подключенк четвертому выходу узла,Источники информации,принятые во внимание при. экспертизе1. Патент США Р 3760356,кл. С Об Г 7/04, опублик, 1970,2. Авторское свидетельство СССРпо заявке Р 2852617/18-24,кл. 6 06 Г 7/02, 1978 (прототип).