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

 

О П 682893

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

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

Республик

ИЗОБРЕТЕН И Я

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву— (22) Заявлено 14.06.76 (21) 2372597/18-24 с сгрисоединением заявки №вЂ” (23) Приоритет— (43) Опубликовано 30.08.79. Бюллетень ¹ 32 (45) Дата опубликования описания 30.08.79 (51) М. Кл- "6 06 F 7/04

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

СССР (53) УДК 681.305 (088.8) по делаМ изобретений и открытий (72) Авторы твзобретения

Ю. Д. Полисский, В. Х. Цингауз

Научно-исследовательский и опытно-конструкторский институт автоматизации черной металлургии (71) Заявитель (45)УСТРОЙСТВО ДЛЯ СРАВНЕНИЯ ЧИСЕЛ

Изобретенс|е относится к автоматике и вычислительной технике и может быть использовано в системах дискретного управления,и ЭВМ.

Известно устройство для сравнения чисел (1), представленных параллельным позиционным способом. Недостатком этого устройства является невысокое быстродействие, так как в нем результаты сравнения формируются путем вычитания единичных импульсов из всех чисел.

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

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

Известно устройство (2) для сразнения

;.исел, представленных последовательным позиционным способом. Основной недостаток этого устройства состоит в невозможности получения комплексного решения задачи сравнения, т. е. получения максимальной разности наряду с наибольшим и наименьшим числами. За исключением экстремальных чисел остальные числа массцва уничтожаются, что в целом ряде практических случаев нежелательно илп недопустимо. Положение экстремальных чисел с указанием наибольшего и наименьшего не нндицпруется. Зачастую доступ к регистрам массива невозможен, и результаты сравнения требуется выводить в отдельные регистры. что в известном устройстве не предусмотрено. Указанные недостатки обусловливают невысокие функциональные возможности устройства.

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

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

15 г. устройстве для сравнения чисел, содержащем 2п блоков коммутации, и кольцевых сдвигающпх регистров. причем прямой и инверсный выходы каждого <-го кольцевого сдвпгающего регистра соединены с первым и вторым входамп i-го и (i+n)-!î блоков коммутации, где = 1,2 ..., n, регистр максимальной разности, регистр наибольшего числа, регистр наименьшсго числа элементы И, ИЛИ, НЕ, 25 триггер, первые t! вторые выходы каждого с-го блок.-". коммуташ;и соединены с входами первого и второго элементов ИЛИ соответственно, а выход первого элемента

ИЛИ вЂ” с первыми входами первого и второго элементов И и через первый элемент

682893

НЕ с первыми входами третьего и четвертого элементов И. Выход второго элемента

ИЛИ подключен к второму входу первого элемента И, K первому входу пятого элемента И, к вторым входам третьего н

«твертсго элем41HTOB И, выход третьего элелеHTà ИЛИ -- к второму входу пятого элемента И и первому входу шестого элемснта И., выход четвертого элемента ИЛИ— к вторым входам второго и шестого элементов И, к входу регистра наибольшего числа и через второй элемент НЕ к третьему входу третьего элемента И. Выход первого элемента И соединен с третьими входами 4-х блоков коммутации, выход второго элемента И вЂ” с ипфор;,1ацпонным входом регистра максимальной разности, выходы третьего и четверто-.о элементов

И вЂ” с управляю1цим входом регистра максимальной разности и с входом pef 1стра наименьшего числа coGTBHTCTBeHHo.

Выход пятого элемента И подключен ко входу установки в единичное состояние триггера, инверсный выход которого соединен с третьим входом пятого элемента И, выход шестого элемента И вЂ” к треть11м выходам (4+42)-х блоков коммутации, Выход пятого элемента И соединен с етвертыми входами блоков коммутации, пятыс входы которых и вход установки в нулевое состояние триггера подключены к правля1ошей шине устройства.

Кроме того, ка>кд11й блок коммутации содержит элементы И., элемент ИЛИ триггер. Первые входы первого и второго элементов И соединены с первым входом блока коммутации, второй вход первого элемента И подключен к выходу элемента

ИЛИ, а выход первого элемента И соединен с первым входом триггера, инверсный выход которого подключен к второму. г,. оду второго элемента И и первому входу третьего элемента И, выходь. ксторъ1х ссединены е первым и вторым выходами блока коммутации соответственно. Второй вход третьего элемента И подключен к второму входу блока коммутации, первый и второй входы элемента ИЛИ соединены с третьим II четгертым входами блока коммутации соответственно, второй вход триггера подключен к пятому входу блока коммутации.

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

Устройство содержит кольпевые сдвигающие регистры (сравниваемых висел) 1,, 1, ..., 1„; кольцевой сдвигающий регистр 2 максимальной разности, выполненный в виде вычитающего счетчи«а с соответствующими цепями развязки сдвига и вычитания с использованием в качестве вычитающего информационного входа, регистра счетного входа его старшего разряда; кольцевые сдвигающие зе5

15 0

Зо

Э -..

45

55

50 чисел соответственно; блоки 51, 5, ..., 5„.

5, „5 +„, ...., 5 „коммутации, состоящие каждьш пз элемента ИЛИ б, первого

7, второго 8 и третьего 9 элементов И и триггера 10; первый 11, второи 12, третий

18 и четвертый 14 элементы ИЛИ; первый

15, второй 1б, третий 17, четвертый 18, пятый 19 и шестой 20 элементы И; триггер

21; первый 22 и второй 28 элементы HE (инверторы); клемму К установки всех триггеров устройства в исходное состояние.

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

В исходном состоянии в регистрах 1, 1, ..., 1„записань. сравниваемые числа, имеются сигналы на выходах триггеров 10 и 21, регистры 2, 8 и 4 очищены.

В том случае, если в анализируемом разряде всех чисел записаны единицы либо нули, появляются сигналы на вторых входах элементов 9 одних, например i-x (i=1,2, ..., 42), коммутационных блоков и отсутствуют сигналы на вторых входах элементов 9 (i+22) коммутационных блоков. Следовательно, нет сигнала на Bbl. оде элемента 18, на одном пз входов и поэтому HH выходе эл310HTH 19.

Поскольку имеются сигналы на вторых входах элементов 8 (4+42) -., коммутацпопHI;Ix блоков и cf пал н"-,,в"ыходе элемента 14, следовательно, есть сигналы и на о.,ном пз входов элемента 1б, па входе элемента 22 и на выходе установки в едии; 4п ое состояние триггера старшего ра

J1H. 2 n сег11СТра 8. В ре3 IbT 1TC в 3ТОТ ОН3 ..1я41 данного регистра записывается еди11П Il 3

Поскольку имеется сигнал па входе элемента 22, отсутствует сигнал на его выходе. Следовательно, нет сигнала на одном из входов элемента 17 и сигнала на

11ы .ит4пощем входе регистра 2. На входе установки в единичное состояние триггера ста1101сго разряда этого же регистра сиг11ала с выхода элемента 1б также не наблюдается, так как отсутствуют сигналы

1а выходах элементов 8 4-х коммутационных блоков.

На обоих входах элемента 18 оказываются сигналы: один — с выхода элемента 12, другой — с выхода элемента 28.

Поэтому в старший разряд регистра 4 наименьшего числа записывается единица. В итоге, на первом такте получаем естественный результат: поскольку все числа в этом разряде равны, в регистрах наибольшего и наименьшего чисел записаны в .-вином разряде единицы, в регистре максимальной разности — нуль, Состояние индикаторных триггеров не изменяется.

Пусть при анализе очередного разряда сбна ружеffo неравенство сравниваемых

::1сел. В схеме устройства при этом про682893

65 ляются сигналы на вторых входах элементов 8 блоков 5 i (i=1,2, ..., n) коммутации и вторых входах элементов 9 блоков

5;1 тех регистров чисел, у которых в анализируемом разряде записан нуль, а также элементов 9 блоков 5; и элементов 9 блоков 5;+,, регистров чисел, у которых в анализируемом разряде записана единица. В результате хотя бы на одном из входов элементов 11 — 14, а значит и на .tz выходах, имеются сигналь;.

Сигналом с выхода элемента 14 записывается единица в анализирувмый разряд регистра 3. На выходе элемента 18 сигнала нет, так как после элемента 28 исчезает сигнал на входе элемента 18. Поэтому состояние регистра 4 не изменяется. Поскольку с выхода элемента 2Д нет сигнала на входе элемента .17, отсутствует сигнал на вычитающем входе регистра 2. Однако сигналом с выхода элемента 16 в анализируемый разряд регистра 2 записывается един и.ца.

На всех трех входах элемента 19 имеются сигналы. Появляющийся на выходе элемента 19 сигнал через эчемент 6 перебрасывает индикаторные триггеры 10 блоков 5; (i = 1,2,..., n) регистров чисел с единицей в анализируемом разряде, в результате чего исчезают сигналы на вторых входах элементов 8 и 9 блоков 5, этих регистров. В итоге, до окончания процесса сравнения эти регистры посредством, первых коммутационных блоков отключаются от элементов

11 и 12 и подключаются через коммутационные блоки 5,, к элементам 18 и 14. Аналогичные переключения происходят в блоках 5; „регистров с нулем в анализируемом разряде, в результате чего эти регисгры отключаются от элвментов 18 и 14 и яодключаются к элементам .11 и 12. Сигнал с выхода элемента 19 также перебрасывает триггер 21, в результате чего исчезает один вход элемента 19 и сигнал на его выходе до окончания, процесса сравнения.

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

B 3ToM под массиве ItpoBQQHTcH. Индикаторные триггеры 10 при помощи элементов

11, 12 и 15 всех блоков коммутации регистров этого подмассива из состояния «11» переходят в состояние «01». Соответственно регистры подмассива чисел с наименьшим числом подключаются к элементам 13 и 14, состояние индикаторных триггеров этих регистров с «11» изменяется на «10».

После продвижения сравниваемых чисел .и результатов сравнения на одну позицию в сторону старших разрядов возможны

25 зо

45 следующие четыре варианта представления информации.

Первый вариант. На выходах элементов

15 и 20 сигналы отсутствуют. Это означает, что в анализируемом разряде каждого нз подмассивов сравниваемые числа равны.

Этому варианту соответствуют следующие четыре случая.

В анализируемом разряде обоих подмассивов записаны нули. В этом случае имеются сигналы на выходах элементов 11 и 13 и отсутствуют сигналы на выходах элементов 12,и 14. Следовательно, состояние регистров 2, 8 и 4 не изменяется.

В анализируемом разряде обоих подмассивов записаны единицы. При этом есть сигналы .на выходах элементов 14 н 12 и нет сигналов на выходах элементов 11 и 13, Сигналом с выхода элемента 14 записывается единица .в анализируемый разряд регистра 3. Единица в анализируемый разряд регистра 4 записывается с выхода элемента 18, на обоих входах которого имеются сигналы: один с выхода элемента 12, другой — с.выхода элемента 28, на входе которого отсутствует сигнал с выхода элемента 11. Состояние регистра 2 не изменяется, так как,нет сигналов с выходов элементов 16 и 17.

В анализируемом разряде подмассива чисел, среди которых содержится наибольшее число, записана единица, второго подмассива — нуль. В этом случае имеются сигналы на выходах элементов 14 и 11 и отсутствуют сигналы на выходах элементов

18 и 12. Сигналом с выхода элемента 14 записывается единица в анализируемый разряд регистра 8 наибольшего числа. Поскольку отсутствует сигнал на выходе элемента 12, т. е. на одном входе элемента 18, не оказывается также сигнала на выходе элемента 18. Поэтому состояние регистра

4 наименьшего числа .че изменяется. На обоих входах элемента 16 с выходов элементов 11 и 14 имеются сигналы. Сигналом с,выхода элемента 16 записывается единица в анализируемый разряд регистра 2 максимальной разности. Поскольку сигнал, по. ступающий с выхода элемента ll на вход элемента 23, исчезает на выходе элеме (га

28, сигнал на выходе элемента 17 и на вычитающем входе регистра 2 отсутствует.

В анализируемом разряде лодмассива чисел, среди которых содержится наибольшее число, записан нуль, второго подмассива — единица. В этом случае имеются сигналы на выходах элементов 18 п 12 и не появляются сигналы на выходах элементов

14 и 11. Поскольку нет сигнала на выходе элемента 14, состояние регистра 3 наибольшего числа не изменяется. Сигналом с выхода элемента 18 записывается единица в анализируемый разряд регистра 4 наименьшего числа. Сигнал записи единицы в регистр 2 максимальной разности отсутству682893 ет, так как нет сигналов на обоих входах элемента lб. Однако имеются все три входных сигнала элемента 17, поэтому подается сигнал на вычитающий вход регистра 2, в результате чего из содержимого этого регистра вычитается единица.

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

В анализируемом разряде падмассива с наименьшим числом записан нуль. В этом случае имеются сигналы на выходах элементов 11, 18 и 14 и отсутствует сигнал на выходе элемента 12. Сигналом с выхода элемента 14 записььвается единица в анализируемый разряд регистра 3. Состояние регистра 4 не изменяетоя, так как .на выходе элемента 18 нет сигнала с выхода элемента

12, поэтому отсутствует, сигнал на выходе элемента 18. Сигналом с выхода элемента

lб, на обоих входах которого имеются сигналы с выходов элементов 11 и 14, записывается единица в анализируемый разряд регистра 2. На,вычитающем входе регистра

2 сигнал с выхода элемента 17 не появляется.

Поскольку имеются сигналы на выходах элементов 18 и 14, появляется сигнал на выходе элемента 20, который через элементы б блоков 5; „перебрасывает индикаторные триггеры 10 тех регистров подмассива с наибольшим числом, у которых в анализируемом разряде записан нуль. В итоге индикаторные триггеры этих регистров из состояния «01» переходят в состояние «00», а сами эти регистры, таким образом, отключаются до окончания процесса сравнения как от элементов 11 и 12, так и от элементов 13 и 14. Следовательно, записанные в них числа сохраняются, но из последующего сравнения исключаются. Та же ситуация имеет место и в следующем случае.

В анализируемом разряде подмассива с наименьшим числом записана единица. В этом случае имеются сигналы на выходах элементов 12, 18 и 14 и отсутствует сигнал на выходе элемента 11. Сигналами с выходо в элементов 14 и 18, на обоих входах которого теперь есть сигналы, записываются единицы в анализируемый разряд регистров

3 и 4. На выходах элементов lб и 17 сигналы не появляются, поэтому состояние регистра 2 не изменяется.

Третий вариант. На выходе элемента 15 имеется сигнал, но не оказывается сигнала на выходе элемента 20. Это означает, что в анализируемом разряде подмассива с наи10

5

)5

55 большим числом сравниваемые числа равны, по не равны сравниваемые числа в подмассиве с наименьшим числом. Этому варианту также соответствуют два случая, определяемые содержимым анализируемого разряда подмассива с наибольшим числом.

В анализируемом разряде подмасси ва с наибольшим числом, записан нуль. В этом елучае имеютоя сигналы на выходах элементов 11, 12 и И и отсутствует сигнал .на выходе элемента 14. Состояния регистров

2, 3 и 4 не изменяются, так как нет сигналов на выходах элементов 14, lб, 17 и 18.

Сигнал с выхода элемента 15 через элемен. ты б блоков 5; перебрасывает индикаторные триггеры 10 тех регистров подмассива с наименьшим числом, у которых в анализируемом,разряде за писана единица. В итоге индикаторные триггеры этих регистров из состояния «10» переходят в состояние

«00», а сами эти регистры, таким образом, отключаются до окончания процесса сравнения от элементов 11, 12, И и 14. Следовательно, записанные в них числа сохраняются, но из последующего сра внения исключаются. Аналогичная ситуация имеет место и в следующем случае данного варианта.

В анализируемом разряде подмассива с наибольшим числом записана единица. В этом случае имеются сигналы на выходах элементов 11, 12 и 14 и отсутствует сигнал на выходе элемента 18. Сигналами с выходов элементов 14 и lб записываются единицы в анализируемый разряд регистров 8 и 2. Состояние регистра 4 не изменяется.

На вычитающем входе регистра 2 сигнал с выхода элемента 17 отсутствует.

Четвертый вариант. На выходах элементов 11 — 14 есть сигналы. Это означает, что в анализируемом разряде обоих подмассивов сравниваемые числа не равны.

На выходах всех элементов 11 — 14 имеются сигналы. Сигналом с выхода элемента

14 записывается единица в анализируемый разряд регистра 8. На выходе элемента 18 сигнал отсутствует, поэтому состояние регистра 4 не изменяется. На обоих входах элемента lб имеются сигналы, в связи с этим сигналом с выхода элемента lб записывается единица в анализируемый разряд регистра 2. Сигнал на вычитающем входе регистра 2 с выхода элемента 17 отсутствует.

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

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

В итоге в регистре 8 записывается наибольшее число, в регистре 4 — наименьшее число, в регистре 2 — максимальная разность. Регистры (либо один регистр), в которых записано наибольшее число, индицируются комбинацией состояний индикаторных триггеров «01», наименьшее число— комбинацией «10».

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

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

1. Устройство для сравнения чисел, содержащее 2п блоков коммутации, и кольцевых сдзигающих регистров, причем прямой и инверсный выходы каждого i-го кольцевого сдвигающего регистра соединены с первым и вторым входами i-го и (1+п)-го блоков коммутации, где 1==1,2 ..., п, регистр максимальной разности, регистр наибольшего числа, оегистр наименьшего числа, элементы И, ЙЛИ, НЕ, триггер, о т л ич а ю щ е е с я тем, что, с целью расширения функциональных возможностей в ча "тн получения значения максимальной разности наряду с наибольшим и,наименьшим числами, в нем первые и вторые выходы каждого

i ãî блока коммутации соединены с входами первого и второго элементов ИЛИ соответственно, выход первого элемента ИЛИ соединен с первыми входами первого и второго элементов И и через первый элемент

НЕ с первыми входами третьего и четвертого элементов И, выход второго элемента

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

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

НЕ к третьему входу третьего элемента И, выход первого элемента И соединен с третьими входами I-х блоков коммутации, выход второго элемента И подключен к информационному входу регистра максимальной разности, выходы третьего и четвертого элементов И соединены с управляющим входом регистра максимальной разности и с входом регистра наименьшего числа соответственно, выход пятого элемента И по:15 ключен к входу установки,в единичное состояние триггера, инверсный выход которого соединен с -,Ilåòbèì входом пятого элемента И, выход шестого элемента И подключен к третьим выходам (1+и)-х блоков

20 коммутации, .выход пятого элемента И соединен с чегзертымн ", îäàìè блоков коммутац11н, пятые входы которых и вход установки з нулевое состояние триггера подключены к управляющей шине устройсгва.

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

„0 входом блока коммутации, второй вход первого элемента И подк.почен к выходу элемента ИЛИ, а выход первого элемента И соединен с IlcpBbIM входом триггера, инверсный выход которого подключен к второму зБ входу второго элемента И и первому входу третьего элемента И, выходы которых соединены с первым и вторым выходами блока коммутации соотзетсгвенно, второй .вход третьсго элемента И подключен к второму

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

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

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

¹ 444180, кл, G 06 F 7/04, 11.08.72

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

¹ 328450, кл. (06 Г 7. 00, 06.11.70 (прототип).

682893

Составитель Ю. Полисский

Техред А. Камышникова

Корректор С. Файн

Редактор И. Грузова

Тнп, Харьк. фил. пред. «Патент»

Заказ 758/966 Изд. ¹ 483 Тираж 780 Подписное

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

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