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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

Республик (Qii

Ф

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву— (22) Заявлено 16.02. 81(21) 3250561 18 24 (51) М.Кп.з с присоединением заявки NDG 06 F 7/04

Государственный комитет

СССР по делам изобретений и открытий (23) ПриоритетОпубликовано 230982. Бюллетень Мо 35 (5МУДК 681.325.

° 5 (088. 8) Дата опубликования описания 23. 09. 82 (54) УСТРОЙСТВО ДЛЯ СРАВНЕНИЯ ЧИСЕЛ

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

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

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

Наиболее близким техническим решением к предложенному является устройство для выделения экстремального иэ n m-разрядных двоичных чисел, которое содержит n m-разрядных регистров на триггерах, выходы триггера каждого i-го разряда j- ;о регистра . (где 1 = f,2, ..., m; j = 1,2, ...,n) соединены с информационными входами (i x j)-го узла анализа. Узел анали за состоит иэ трех элементов И, причем .первые входы первого и второго элементов H соединены с первым управляющим входом узла, а их вторые входы - с информационными входами узла. Выход первого элемента И подключен к первому входу узла, выход второго элемента. И соединен с первым входом третьего элемента И и со вторым выходом узла, второй и третий входы третьего элемента И подключены ко второму и третьему управляющим входам узла, а выход третьего элемента И соединен с третьим выходом узла, первый выход .каждого (i х j)-ro узла анализа соединен с j-ым входом i-го элемента. ИЛИ первой группы, второй выход каждого (i х j)-ro узла анализа подключен к j-ому входу i-ro эле- . мента ИЛИ второй группы. В устрой-, ство также входят и дополнительных триггеров, группы элементов И-НЕ, И, группа элементов ИЛИ, причем выход каждого i-ro эЛемента ИЛИ первой группы соединен с первым входом

ЗО.i-го элемента И-НЕ группы, с i-ым

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

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

j-ro элемента ИЛИ третьей группы, выход каждого j-го элемента ИЛИ .,третьей .группы подключен ко входу установки в нулевое состояние,j-го дополнительного триггера, прямой .выход каждого j-ro дополнительного триггера соединен с 1;ым выходом управления устройства и со вторым управляющим входом j-x узлов анализа, выход каждого i-го элемента И-HE группы подключен к первому входу

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

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

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

Поставленная цель достигается тем, что в устройстве для сравнения чисел,35 содержащем п узлов анализа:чисел, m узлов управления, каждый из которых состоит из двух элементов И, причем выход первого элемента И узла управления подключен к первому .входу вто- 40 рого элемента И, второй вход которого соединен с задающим входом узла управления, а выход - .с выходом узла управления, входы первого элемента

И подключены к информационным входам 45 узла управления, триггер, инверсный выход триггера подключен ко входу запуска каждого иэ узлов анализа чи-.. сел,.- прямой выход триггера соединен с задающщл входом первого узла управ-1О ления и с первым входом задания признака каждого из узлов анализа чисел, выход каждого i-го узла управления, где i = 1,2, ..., .(а-1), подключен, к задающему входу (i+1)-ro узла сравнения и к i-му входу задания признака каждого иэ узлов. анализа чисел, выход m-го узла управления соединен со входом установки в нулевое„состояние триггера, выход результата сравнения каждого j-ra разряда, где

1,2, ..., m каждого k««ro узла анализа чисел, где k 1,2, ..., n, подключен к k-му: входу j-ro узла управления, выход результата анализа каждого р-го узла анализа чисел, где 65.р = 2гЗ ° ° ., (m-1), соединен со ! входом переноса (р-1)-го и (p+1)-ro узлов анализа чисел, выходы результата первого и m-ro узлов анализа чисел подключены ко входам переносов второго и (m-1)-го узлов анализа чисел соответственно, первый.и второй выходы переноса j-го разряда каждого

k-ro узла анализа чисел соединены с входами переноса j-ro разряда (k-1)-ro и (k+1)-го соответственно узлов анализа чисел.

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

j-ro поразрядного узла сравнения .соединен с j-ым входом второго элемента ИЛИ, выход которого подключен ко входу установки в единичное состояние nepsoro триггера, инверсный выход которого. соединен с первыми входами первого элемента И и первого элемента ИЛИ, второй и третий вхьды которого подключены ко входам первноса узла анализа чисел, прямой выход первого триггера соединен с четвертым входом каждого поразрядного узла сравнения, вход запуска .узла анализа чисел подключен ко второму входу первого элемента И, выход которого соединен с выходом результата анализа узла анализа чисел, инверсный выход каждого j-го триггера регистра подключен к j-му входу второго элемента И, выход которого соединен со (в+1)-ым входом второго элемента ИЛИ и со входом:установки

s единичное соетояние второго триггера, прямой выход которого подключен к пятому входу каждого поразрядного узла:сравнения,. j-ый вход задания признака узла анализа чисел соединен с шестым входом j-го поразрядного узла сравнения, первый и второй входы переноса разряда поразрядного j -го узла анализа чисел подключены к седьмому и восьмому входам соответственно j-го узла поразрядного сравнения, второй и третий выходы каждого j-ro поразрядного узла сравнения соединены с первым. и вторым выходами переноса j-го разряда, выход результата сравнения подключен к четвертому выходу поразрядного узла сравнения.

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

960799 входом первого элемента И, выход которого подключен к первому входу первого элемента ИЛИ, выход которого соединен с первыми входами второго элемента И и второго элемента

ИЛИ, выход которого подключен к пер вому входу. схемы сравнения, второй вход узла соединен со вторым входом схемы сравнения, выход которой подключен к первому выходу узла и через элемент НŠ— к первому входу третьего элемента ИЛИ, третий вход узла соединен со вторым входом первого элемента И, второй вход третьего элемента ИЛИ подключен к четвертому входу узла, пятый вход. узла соединен с первым входом третьего элемента И и со вторым входом второго элемента

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

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

Устройство содержит триггер 1 управления, m узлов 21, 2, ..., 2щ управления, каждый из которых состоит из элементов И 3 и 4, узлов 5„, 51, 5„ анализа чисел, каждый из которых содержит m поразрядных узлов

61, 61, ..., бп1 сравнения, элемент

ИЛИ 7., элемент И 8, триггеры 9 и 10, элемент ИЛИ 11, элемент И 12, регистр

13, состоящий из m триггеров 14„, 14, ..., 14m Каждый поразрядный узел 6 анализа состоит из элементов

И 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 анали l0 за чисел. В результате осуществляется разрыв цепей передачи информации между узлами .5 анализа чисел узлами, имеющими номера меньшие и большие номера рассматриваемого узла 5 анализа

15 чисел. Таким образом, и узлов 5 анализа чисел устройства разделяются на (k+1) группу узлов, где k — количество узлов 5 анализа чисел,.содержащих .равные. нулю числа. В последующем, при выполнении второго этапа, сравнение чисел производится независимо. в пределах каждой группы.

Если записанное в регистр 13 число не равно нулю, на соответствующие входы элемента И 12 поступают как единичные, так и нулевые уровни с инверсных выходов каждого триггера 14, и на выходе элемента И 12 - нулевой уровень. В результате триггеры 10 и

9 данного узла 5 анализа числа останутся в единичном состоянии. При этом единичный уровень с прямого выхода триггера 10 поступает на первый вход элемента И 16.и 15 всех поразрядных узлов 6 сравнения данного узла 5

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

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

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

Второй этап начинается с поступления но шине 24 управления единичного сигнала, который устанавливает в единичное состояние триггер 1 управления. Единичный уровень прямого выхода триггера 1 управления пода6 ется на первый вход схемы 21 сравне960799 ния всех поразрядных узлов 6 сравнения старшего разряда.

В первых двух ситуациях отсутствует информация, позволяющая сравнить числа. В связи с этим необходим переход к анализу соседнего младшего разряда сравниваемью чисел в пределах рассматриваемой группы. Этот переход реализуется следующим образом. Если в триггерах 14 анализируемого стар.шего разряда сравниваемых чисел в 10 пределах группы содержатся..нули, на третий вход схеьаи 21 сравнения каждого поразрядного узла 6 сравнения данного разряда в пределах этой группы поступает единичный уровень с ну-15 левого выхода каждого триггера 14.

На единичном выходе каждого триггера

14 этой группы есть нулевой уровень, который подается на второй вход элемента И 20 и на выходе этого элемента тоже нулевой уровень. Этот нулевой уровень .поступает на второй вход элемента ИЛИ 18, на первый вход этого элемента подается нулевой уровень с выхода элемента И 16 узла .5 анализа чисел (в пределах данной группы узлов), имеющего номер, меньший рассматриваемого. С выхода элемента ИЛИ

18 нулевой уровень подается на второй вход элемента И 16 и на первый вход элемента ИЛИ 17 данного поразрядного узла сравнения. На втором входе элемента ИЛИ 17 находится, также нулевой уровень с выхода элемента И 15 этого же поразрядного узла сравнения, так как .на второй вход элемента И 15 подается нулевой уровень, с выхода элемента ИЛИ 17 одноименного поразрядного узла сравнения 6, узла 5 анализа числа (s пределах рассматриваемой группы узлов), имеющего номер, на еди4О ницу больший рассматриваемого. Следовательно, на выходе элемента ИЛИ 17 каждого поразрядного узла 6 сравнения в пределах рассматриваемой группы будет нулевой уровеньi который подается45 на второй вход схемы 21 сравнения.

В результате нулевой уровень с выхода схемы 21 сравнения инвертируется элементом НЕ 19 и единичный уровень е с его выхрда через элемент ИЛИ 22 поступает на соответствующий вход управляющего элемента И 4 старШей схемы управления.

Если же во всех триггерах 14 анализируемого старшего разряда в преде-55 лах группы содержатся единицы, на третьем входе схемы 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 сравнения соседнего младшего разряда

960799

10 анализируемых чисел и разрешает их сравнение.

Работа устройства выделения локальных максимумов при анализе следующих разрядов происходит, аналогично рассмотренному второму этапу работы. 5

После окончания процесса сравнения младшего разряда чисел единичный уровень с выхода элемента И 15 младшей схемы 2 управления устанавливает в нулевое состояние триггер 1 управ- )p ления. Единичный уровень с инверсного выхода триггера 1 управления поступает:на второй вход элемента И 8 каждого узла 5 анализа числа. На первом входе элемента И 8 будет единичный: уровень с единичного выхода триггера 9, оставшегося в единичном состоянии, т.е. содержащего локально-максимальное число.

Единичный уровень с выхода элемента И 8 подается через элемент ИЛИ 11 на первый вход элемента И 20 каждого поразрядного управления узла 6 числа с номером, на единицу меньшим и большим рассматриваемого, что разрешает выдачу, наряду с локально-максимальными, соседних значений (по одному с каждой стороны от локально-максимального).

Таким образом, устройство обеспечивает выделение иэ множества сравниваемых чисел (например, ординат дискретиэированного процесса) локальных максимумов и соседних с ними чисел (по одному с каждой стороны). Обрабатывая результаты работы устройства З5 на ЗВИ, можно по известным алгоритмам уточнить положение максимума .(например, абсциссы дискретиэированного ! процесса). Это позволяет использовать устройство выцеления локальных макси-4О мумов в средствах цифрового корреляционного анализа случайных сигналов.

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

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

)О выход первого элемента И узла управления подключен к первому входу второго элемента И, второй вход которого соединен с задающим входом узла управления, а выход — с выходом узла управления, входы первого элемен. та И подключены к информационным входам узла управления, триггер., о тI л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет обеспечения .опре- деления локальных экстремумов, в-нем инверсный выход триггера подключен ко входу запуска каждого из узлов анализа чисел, прямой выход триггера соединен с задающим входом первого 65 узла управления и с первым входом задания признака каждого из узлов анализа чисел, выход каждого i-го узла .управления, где i = 1, 2, (m-1), подключен к зацающему входу (i+1)-ro узла сравнения и к i-му входу задания признака каждого из узлов анализа чисел, выход m-го узла управления соединен со входом установки в нулевое состояние триггера, выход результата сравнения каждого j-го разряда, где j = 1, 2, m каждого k-ro узла анализа чисел, где 1 = 1, 2, ..., и, подключен к k-му входу j-ro узла управления, выход результата анализа каждого р-го узла анализа чисел,где .р = 2, 3, (m-1), соединен со входом переноса (р-1) -го и (р+1)-го узлов анализа чисел, выходи результата первого и m-го узлов анализа чисел подключены ко входам переносов второго и (m-1)-ro узлов анализа чисел соответственно, первый и второй выходы переноса j-го разряда каждого k-го узла анализа чисел соединены с входами переноса j-ro разряда (k-1)-ro u (k+1) -го соответственно узлов анализа чисел.

2. Устройство по п. 1, о т л ич а ю щ е е с я тем, что в нем каждый узел анализа чисел содержит регистр, состоящий,из щ триггеров, и узлов поразрядного сравнения, эле- менты И, ИЛИ, триггеры, причем пряой и инверсный выходы каждого j-го триггера регистра, где j = 1,2, соединены с первым и вторым входами соответственно j-ro поразр щного узла сравнения, третий вход к!Йкдого иэ которых подключен к выходу первого элемента ИЛИ, первый выход каждого j-ro поразрядного узла сравнения соединен с j-ым входом второго элемента ИЛИ, выход которого подключен ко входу установки в единичное состояние первого триггера, инверсный выход которого соединен с первыми входами первого элемента И и первого элемента ИЛИ, второй и третий входы которого подключены ко входам переноса узла анализа чисел, прямой выход nepaoro триггера соединен с четвертым входом каждого поразрядного .узла сравнения, вход запуска узла анализа чисел подключен ко второму входу первого элемента И, выход которого соединен с выходом результата анализа узла анализа чисел, инsepcíûé выход каждого j-ro триггера регистра подключен к j --му входу второго элемента И, выход которого соединен с (m+1)-ым входом второго элемента ИЛИ и со входом установки в единичное состояние второго триггера, прямой выход которого подключен к пятому входу каждого поразрядного узла сравнения j-й вход задания приэ12

960799

ВНИИПИ Заказ 7282/58 Тираж 731 Подписное

Филиал ППП "Патент", r.Óæãoðîä, ул.Проектная,4 нака узла анализа чисел соединен с шестым входом j-ro поразрядного узла сравнения, первый и второй входы переноса разряда j-го поразрядного узла анализа чисел подключены к седьмому и восьмому входам соответствен- 5 но j-ro узла поразрядного сравнения, второй и третий выходы каждого j-ro поразрядного узла сравнения соединены с первым и вторым выходами переноса j-ro paapagta, выход результата 10 сравнения переноса подключен к чет-. вертому выходу поразряднояо узла оравнения.

3. Устройство по п. 1, о т л и ч ato tq е е с я тем, что в нем каждый узел поразрядного сравнения содержит элементы И, ИЛИ, НЕ, схему сравнения, причем первый вход узла соединен с .первым входом первого элемента И, выход которого подключен к первому входу первого элемента ИЛИ, выход которого соединен с первыми входами .второго элемента И и второго элемента ИЛИ, .выход которого подключен к перво "у входу схемы сравнения второй 25 вход узла соединен со вторым входом схемы сравнения, выход которой подключен к первому выходу узла и через элемент НЕ - к первому входу третьего элемента ИЛИ, третий вход узла соединен со вторым входом первого элемента И, второй вход третьего элемента ИЛИ подключен к четвертому входу узла, пятый вход узла соединен с перВым входом третьего элемента И и со вторым входом второго элемента

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

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

1. Патент CWA 9 3760356, кл. G 06 F 7/04, опублик. 1970.

2. Авторское свидетельство СССР по заявке Р 2852617/18-24, кл. G 06 F 7/02, 1978 (прототип).