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

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

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

Недостатком э.того устройства является малое быстродействие.

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

каждого i-ro разряда регистра (где i 1,2, ..., m; j 1,2, ...,n) срединф ы с информационными входами (i X j)-го узла анализа. Узел анализа состоит из трех элементов И, причем .первые входы первого и второго элементов И соединены с первым управляющим входом узла, а их вторые входы - с инфО{ 4ационными входами

to узла Выход первого элемента И подключён к первому входу узла, выход второго элемента. И соединен с первым входом третьего элемента И исо вторым выходом узла, второй и третий

15 входы третьего элемента И подключены ко второму и третьему управляющим входам узла, а выход третьего элемента И соединен с третьим выходом узла, первый .выход каждого (i х j)-го узла

20 анализа соединен с j-ым входом i-ro элемента ИЛИ первой группы, второй выход каждого (i х j)-ro узла анализа подключен к j-ому входу i-ro элемента ИЛИ второй группы. В устроит

25 ство также входят п дополнительных триггеров, группы элементов И-НЕ, И, группа элементов ИЛИ, причем выход каждого i-ro элемента ИЛИ первой группы соединен с первым входом 30i-ro элемента И-НЕ группы, с i-ым

.информационном выходом устройства и с первым управляющим входом i-ых узлов анализа. Выход каждого i-ro элемента ИЛИ второй группы подключен ко второму входу i-ro элемента И-НЕ группы, третий выход каждого (i х j)-rp узла анализа соединен с i-ым входом j-ro элемента ИЛИ третьей группы, :выход каждого j-го элемента ИЛИ .третьей .группы подключен ко входу установки в нулевое состояние -j-ro 10 дополнительного триггера, прямой выход каждого j-ro дополнительного триггера оое;цинен с j .-ым вькодом управления устройства и со вторьм управляющим входом j-х узлов анали- 5 за, выход каждого i-ro элемента И-НЕ группы подключен к первому входу i-ro элемента И группы, выход каждого из которых соединен с третьим управляющим входом (i +Д)-ых узлов 20 анализа и со вторым входом (i+1)-ro элемента И группы., вход управления устройства подключен ко второму входу первого элемента И группы и третьим управляющим входам узлов 7s анализа первых разрядов всех регистров 2..

Недостатке указанного устройства являются малые функциональные возможности . . , -:

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

Поставленная цель достигается тем, что в устройстве для сравнения чисел,35

содержас ем п узлов анализа чисел, m узлов управления, каждый из которых состоит из двух элементов И, причем выход первого элемента И узла управления подключён к первому входу вто- 40 рого элемента И, второй вход которого соединен с задающим входом узла управления, а выход - с выходом узла управления, входы первого элемента И подключены к информационным входам 45 узла управления, триггер, инверсный выход триггера подкл1эчен ко входу запуска каждого из узлов анализа чисел , прямой выход триггера соединен с задающи входом первого узла управ-гп ления и с первым входом задания признака каждого из узлов анализа чисел, выход каждого 1-го узла управления, /где i 1,2, ,.., .(m-1), подключен

К задающему входу {i-«-1)-ro узла орав-. нёния и к i-му входу задания приз нака каждого из узлов анализа чисел, выход тто узла управления соединен со входом установки в нулевое, сост.ояние триггера, выход результата сравнения каждого j-ro разряда, ,где °0 j 1,2, ..., m каждого k-ro узла анализа чисел, где k ° 1,2, ..., п, подключен к k-му: входу j-ro узла управления, выход результата анализа к 1ждого р-го узла анализа чисел, где 65

Р 2,3, ..., (т-1), соединен со .входом переноса (р-1)-го и (р+1)-гр узлов анализа чисел, выходы результата первого и га-го узлов анализа чисел подключены ко входам переносо второго и Cii-D-ro узлов анализа чисел соответственно, первый, и ВТОРОЙ выходы переноса j-ro разряда каждого k-ro узла анализа чисел соединены с входами переноса j-ro разряда (k-l)-ro и (k-t-l)-ro соответственно узлов анализа чисел.

Причем в устройстве каждый узел анализа чисел содержит регистр, состоящий из m триггеров, п узлов поразрядного сравнения, элементы И, ИЛИ, триггеры, причем прямой и инверсный выходы каждого j-ro триггера регистра, где j 1,2, . .., m, средирены с первым и вторым входами соотжетствённо j-ro поразрядного узла сравнения, третий вход каждого из которых подключен к выходу первого элемента ИЛИ, первый выход каждогр j-ro поразрядного узла сравнения соединен с j-ьюл входом второго элемента ИЛИ, выход которого подключен ко входу установки в единичное состояние первого триггера, инверсный выход которого, срединен с первыми входами первого элемента И и первого элемента ИЛИ, второй и третий входы которого подключены ко входам переноса узла анализа чисел, прямой выход первого триггера соединен с четвертым входрм каждого поразрядного узла сравнения, вход запуска узла ансшйза чисел подключен ко второму входу первого элемента И, выход которого соед1|нён с выходе результата анализа узЛа анализа чисел, инверсный выход каждого j-ro триггера регистра подключен к j-му входу второго элемента И, выход которого соединен со () -ым входом второго элемента ИЛИ и со входом-установки в единичное состояние второго триггера, прямой выход которого подключен к пяттаяу входу Ксокдого поразрядного узла сравнения, j-ый вход задания признака узла анализа чисел соединен с шестым входрм j-ro поразрядного узла сравнения, первый и второй входы переноса разряда поразрядного j-ro узла анализа чисел подключены к седьмому и восьмому входам соответственно j-ro узла поразрядного сравнения, второй и третий выходыкаясдого j-ro поразрядного узла сравнения соединены с первым и вторым выходами переноса j-го разряда, выход результата сравнения подключен к четвертрму выхрду прразрядного узла сравнения.

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

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

На чертеже приведена функциональная схема устройства.

Устройство содержит триггер 1 управления, m узлов 2, 2, 2 управления,, каждый из которых состоитг из элементов И 3 и 4, узлов 5, 5, ..., 5п анализа чисел, каждый из которых содержит m поразрядных узлов 6tr 6-, ..., 6 fy сравнения, элемент ИЛИ 7., элемент И 8, триггеры 9 и 10, элемент ИЛИ 11, элемент и 12, регист 13, состоящий из m триггеров 14, 14г, ..., 14п1. Каждый поразрядный узел б анализа состоит из элементов И 15 и 16, элементов ИЛИ 17 и 18, элемента НЕ 19, элемента И 20, схемы 21 сравнения, элемента ИЛИ 22 шины 23 установки в единичное состояние, шины 24 управления.

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

Триггер 1 управления и триггеры 9 и 10 узлов ансшиза чисел установлены в нулевое состояние.

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

При поступлении по, шине 23 установки в единичное состояние сигнала, устанавливаются в единичное состояни все триггеры 10 узлов 5 анализа чисел. После этого в регистры 13 принимаются сравниваемые числа. Если записанное в регистр 13 Число равно нулю, единичные уровни инверсных

выходов всех триггеров 14 этого регистра поступают на соответствующие входы элемента И 12 и единичный уровень с выхода этого элемента устанавливает в нулевые состояния триггер

О и через элемент ИЛИ 7 - триггер 9. Нулевой уровень прямого выхода триггера 10 поступает на первый вход элементов И ;16 и 15 всех поразрядных узлов 6 сравнения данного узла 5 анализа чисел. В результате осуществляется разрыв цепей передачи информации между узлами 5 анализа чисел узлами, имеющими номера меньшие и большие номера рассматривае/лого узла 5 анализа

чисел. Таким образом, п узлов 5 анализа чисел устройства разделяются на (k-«-13 группу узлов, где k - количество узлов 5 анализа чисел,-содержащих равные нулю числа. В последующем,

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

Если записанное в регистр 13 число не равно нулю, на соответствующие

входы элемента И 12 поступают как единичные, так и Нулевые уровни с инверсных выходов каждого триггера 14, и на выходе элемента И 12 - нулевой уровень. В результате триггеры 10 и 9 данного узла 5 анализа числа останутся в единичном состоянии. При этом единичный уровень с прямого выхода триггера 10 поступает на первый вход элемента И 16. и 15 всех поразрядных узлов 6 сравнения данного узла 5

анализа чисел и открывает цепи передачи информации между узлами анализа 1исел с нсмерами меньшими и большими номера рассматриваемого узла. Единичный уровень с прямоговыхода триггера 9, поступающий через элемент ИЛИ 11 на nepBbtft вход элемента И 20 каждого поразрядного узла б сравнения данного узла 5 анализа чисел, разрешаетвщдачу содержимого триггера 14 регистра 13 для-сравнения в пределах группы узлов 5 анализа чи;сел. . .

На втором &тапе работы устройства происходит поразрядное/ начиная со старшего разряда, сравнение чисел.

При сравнении одноименных разрядов чисел в пределах каждой группы узлов 5 аиализа чисел возможны ситуации, когда все триггеры анализируемого разряда содержат нули, или еда1Иицы, иди когда часть триггеров анализируемого разряда содержит единицы, а часть - нули.

Второй этап начинается с поступления по шине 24 управления единичного сигнала, который устанавливает в единичное состояние триггер 1 управления. Единичный уровень прямого выхода триггера 1 управления подается на первый вход схемы 21 сравнения всех поразрядных узлов б сравнения старшего разряда. В первых двух ситуациях отсутствует информация, позволяющаясравнить числа, в связи с этим необходим Переход к анализу соседнего младшего разряда сравниваемы чисел в предела рассматриваемой группы. Этот переход реализуется следующим образом. Если в триггерах 14 анализируемого стар.ыего разряда сравниваемнлх чисел в пределах группы содержатся.нули, на третий вход cxeftttJ 21 сравнения каждого поразрядного узла 6 сравнения данного разряда в пределах этой груп пы поступает единичньдй уровень с ну левого выхода каждого триггера 14. На единичном выходе каждого триггера 14 этой группы есть нулевой уровень, который подается на второй вход элемента И 20 и на выходе этого элемента тоженулевой уровень. Этот нулево уровень .поступает на второй вход эле мента ИЛИ 18, на первый вход этого элемента подается нулевой уровень с выхода элемента И 16 узла 5 анализа чисел (в пределах данной группы узлов) , имеющего номер, меньший рассматриваемого. С выхода элемента ИЛИ 18 нулевой уровень подается на второй вход элемента И 16 и на первый вход элемента ИЛИ 17 данного поразрядного узла сравнения.- На втором входе элемента ИЛИ 17 находится .также нулевой уровень с выхода элемента И 15 этого же поразрядного узла сравйеиия, так как -на второй вход элемента И 15 подается нулевой уровень, с выхода элемента ИЛИ 17 рдиоименного поразряд ного узла сравнения б, узла 5 анализа числа (в пределах рассматриваемой группы узлов), тлеющего номер, на еди ницу больший рассматриваемого. Следовательно, на выходе элемента ИЛИ 17 каждого поразрядного уэла 6 сравнения в пределах рассматриваемой группы будет нулевой уровень, который подается на второй вход схемы 21 сравнения. В результате нулевой уровень с выхода схемы 21 сравнения инвертируется элементом НЕ 19 и единичный уровень с его выхрда через элемент ИЛИ 22 поступает на соответствующий вход управляющего элемента И 4 старшей йхемы управления. Если же во всех триггерах, 14 анализируемого старшего разряда в пределах группы содержатся единицы, на третьем входе схемы 21 сравнения каждого из поразрядных узлов 6 сравнения в пределах этой группы будет нулевой уровень с инверсного выхода триггера 14i Следовательно, нулевой уровень с выхода схекы 21 сравнения инвертируется элементом НЕ 19 и через элемент ИЛИ 22 подается единичный уровень на соответствую11ий-вход управляющего элемента И 4 старшей схемы 2 управления. Если часть триггеров 14.в пределах группы содержит единицы, а часть нули (третья ситуация), на второй вход схемы 21 сравнения каждого п6разрядногр узла сравнения в пределах анализируемой группы поступает единичный уровень хотя бы с одного содержащего единицу триггера 14 узла 5 анализа чисел, имеющего номер меньший рассматриваемого (через элементы ИЛИ 18 и 17), или от содержащего единицу триггера 14 узла 5 анализа чисел, имеющего номер, больший рассматриваемого (через элемент И 15, элемент ИЛИ 17) . Единичный уровень на Bi-аходе .схемы 21 сравнения будет в случае, если на третьем его входе будет единичный -уровень с инверсного выхода на- ходящегося в нулевом состоянии триггера 14. Тогда единичный уровень с выхода схемы 21 сравнения через соответствующий вход элемента ИЛИ 7 устанавливает в нулевое состояние триггер 9 данного узла 5 анализа чисел. Единичный уровень с инверсного выхода триггера 9 подается на второй вход элемента ИЛИ 22 данного узла 5 анализа и поступает на соответствую1одй вход управляющего элемента И 4 каждой схемы 2 управления. Нулевой уровень с прямого выхода триггера & данного узла 5 анализа чисел поступает на второй вход элемента ИЛИ 11 этого же узла 5 анализа чисел. На первый и третий, входы элемента ИЛИ 11 поступают нулевые уровни с тчыхода элементов И 8 узлов 5 анализа чисел, имеющих номер соответственно на единицу больший и меньший рассматриваемого, так как на второй вход элемента И 8 всех узлов 5 анализа чисел подан нулевой уровень с инверсного выхода триггера 1 управления, находящегося в единичном состоянии. Нулевой уровень с вьгхода элемента ИЛИ 11 узла 5 анализа чисел, триггер которого установлен в нулевое состояние, подается на первые входы элементов И 20 и ИЛИ 17 данного узла 5 анализа чисел и разрывает цепь прохождения содержимого регистра 13 для сравнения в пределах группы узлов 5 анализа чисел, т.е. данный регистр 13 выбывает из процесса дальнейшего анализа. 1, .. Когда процесс сравнения старшего разряда анализируемых чисел заканчивается, на всех входах управляющего элемента И 4 старшей схемы 2 управле,ния будет единичный уровень. На выходе элемента И 3 этой схемы управления будет также единичный уровень, которьзй поступает на второй вход элемента И 3 соседней младшей схемы 2управления и первый вход схемы 21 сравнения соседнего младшего разряда знализируегл-лх чисел и разрешает их сравнение. Работа устройства выделения локальных максимумов при анализе следующих . разрядов происходит;.аналогично рассмотренному второму этапу работы, После окончания процесса сравнения мпад1иего разряда чисел единичный уровень с выхода элемента И 15 младшей схемы 2 управления устанавливает в нулевое сосТ ояние триггер 1 управления. Единичный уровень с инверсного выхода триггера 1 управления поступает на второй вход элемента И 8 каждого узла 5 анализа числа. На первом входе элемента И 8 будет единичныйуровень с единичного выхода триггера 9, оставшегося в единичном состоянии, т.е. содержащего локально- максимальное число. Единичный уровень с выхода элемента И 8 подается через элемент ИЛИ 11 на первый вход элемента И 20 каждого поразрядного управления узла 6 числа с номером, на единицу меньшим и боль шим рассматриваемого, что разрешает выдачу, наряду с локально-максимальными, соседних значений (по одному с каждой стороны от локально-максимального) . Таким образом, устройство обеспечивает вьвделение из множества сравнивя1емых чисел (например, ординат дискретизированного процесса) локальных максимумов и соседних с ними чисел (по, одному с каждой стороны). Обраба тывая результаты работы устройства на ЭВМ, можно по известным алгоритмам уточнить положение максимума -(на пример, абсциссы дискрётизированного процесса). Это позволяет использовать устройство выделения локальных макси мумов в средствах цифрового корреляционного анализа случайных сигналов. Формула изобретения 1. Устройство для сравнения чисел, содержащее п узлов анализа чисел, m узлов управления, каждый из которы состоит из двух элементоё И, причем выход первого элемента И узла управ ления подключен к первому входу второго элемента И, второй вход которого соединен с адающим входом узла управления, а выход - с выходом узла управления, входы первого элемен та И подключены к информационньм входам узла управления, триггер., о т .личающее с я тем, что, с целью расширения функциональных возможностей за счет обеспечения определения лЬкальных экстремумов, в нем инверсный выход триггера подключен ко входу запуска каждого из узлов анализа чисел, прямой выход триггера соединен с задающим входом первого узла управления и с первым входом задания признака каждого из узлов анализа чисел, выход каждого i-ro узла управления, где i 1, 2 (m-1), подключен к задающему входу (i--l)-ro узла сравнения и к i-му входу задания признака каждого из узлов анализа чисел, выход т-го узла управления соединен со входом установки в нулевое состояние триггера, выход результата сравнения каждого j-ro разряда, где j 1, 2, ..., m казадого k-ro узла анализа чисел, где fe 1, 2, ... п, подключен к k-му входу j-ro управления, выход результата анализа каждого р-го узла анализа чисел,где р 2, 3, ... (m-1), соединен со входом переноса (р-1)-го и (р+1)-го узлов анализа чисел, выходы результата первого и т-го узлов анализа чисел подключены ко входам переносов второго и (m-l)-ro узлов анализа чисел соответственно, первый и второй выходы переноса j-ro разряда каждого k-ro узла анализа чисел соединены с входами переноса j-ro разряда (k-l)-ro и (k+1)-ro соответственно узлов анализа чисел. 2. Устройство по п. 1, о т л и- . чающееся тем, что в нем каждый узел анализа чисел содержит регистр, состоящий .из m триггеров, п узлов поразрядного сравнения, элементы И, ИЛИ, триггеры,причем прямой и инверсный выходы каждого j-ro триггера регистра, где j 1,2, ..., m, соединены с первым и вторым входами соответственно j-ro поразряшюго узла сравнения, третий вход к кдого из которых подключен к выходу первого элемента ИЛИ, первый выход каждого j-ro поразрядного узла сравнения соединен с j-ым входом второго элемента ИЛИ, выход которого подключен ко входу установки в единичное состояние первого триггера, инверсный выход которого соединен с первыми входами первого элемента И и первого элемента ИЛИ, второй и третий входы которого подключены ко входам переноса узла анализа чисел, прямой выход первого триггера соединен с четвертым входом каждого поразрядного узла сравнения, вход запуска узла анализа чисел подключен ко второму входу первого элемента И, выход которого соединен с выходом результата анализа узла анализа чисел, инверсный выход каждого j-ro триггера регистра подключен к j-му входу второго элемента И, выход которого соединен с ()-ым входом второго элемента ИЛИ и со входом установки в единичное состояние второго триггера, прямой выход которого подключен к пятому входу каждого поразрядного узла сравнения j-и вход задания приз