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

(45)УСТРОЙСТВО ДЛЯ СРАВНЕНИЯ ЧИСЕЛ

НЕ с первыми входами третьего и четвертого элементов И. Выход второго элемента ИЛИ подключен к второму входу первого элемента И, к первому входу пятого элемента И, к вторым входам третьего и етзертого элементов И, выход третьего элемента ИЛИ - к второму входу пятого элемента И и первому входу шестого элемента И, выход четвертого элемента ИЛР1- к вторым входам второго и шестого элементов И, к входу регистра наибольшего числа и через второй элемент НЕ к третьему входу третьего элемента И. Выход первого элемента И соединен с третьими входами t-x блоков коммутации, выход второго элемента И - с информационным входом регистра максимальной разности, выходы третьего и четвертого элементов И - с управляющим входом регистра максимальной разности и с входом регистра наименьшего числа соответственно. Выход пятого элемента И подключен ко входу установки в единичное состояние три1тера, инверсный выход которого соединен с третьим входом пятого элемента И, выход шестого элемента И - к третьим выходам {i+n)-x блоков коммутации. Выход пятого элемента И соединен с четвертыми входами блоков коммутации, пятые вхОх ы которых и вход установки нулевое состояние триггера подключены к упрярляюш.ей шине устройства.

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

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

Устройство содержит кольцевые сдвигающие регистры (сравниваемых чисел) /ь /2, ..., /„Г кольцевой сдвигающий регистр 2 максимальной разности, выполненный в виде вычитающего счетчика с соответствующими цепями развязки сдвига и вычитания с использованием в качестве вычитаюш,его информационного входа, регистра счетного входа его старшего разряда; кольцевые сдвигающие речисел соответственно; блоки 5i, 2, ..., 5„. 5| „, 52-f и, ... ., 52д коммутации, состоящие каждый из элемента ИЛИ 6, первого 7, второго 8 и третьего 9 эле.ментов И « триггера JO; первый //, второй 12, третий 13 и четвертый М элементы ИЛИ; первый 15, второй 16, третий /7, четвертый 18, пятый- 19 и шестой 20 элементы И; триггер 21; первый 22 и второй 23 элементы НЕ (инверторы); клемму К установки всех триггеров устройства в исходное состоянне.

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

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

В том случае, если в анализируемом разряде всех чисел записаны единицы либо нули, появляются сигналы на вторых входах элементов 9 одних, например i-x (г 1,2, ..., я), коммутационных блоков и отсутствуют сигналы на вторых входах s/лементов 9 (i+n)- коммутационных блоков. Следовательно, нет сигнала на выходе элемента 13, на одном из входов и поэтому на выходе элемента 19.

Поскольку имеются сигналы на вторых входах элементов 8 (1+п}-к коммутационных блоков и сигнал на выходе элемента 14, следовательно, есть сигналы и на одном из входов элемента 16, на входе элемента 22 и на выходе установки в единичное состояние триггера старшего рл;)яда регистра 3. В результате в этот рлз)яд данного регистра затесывается единица.

Поскольку имеется сигнал на входе элемента 22, отсутствует ситал на его выходе. Следовательно, нет сигнала на одном из входов элемента 17 н сигнала на вычитающем входе регистра 2. На входе установки в единичное состояние триггера старшего разряда этого же регистра сигнала с выхода элемента 16 также не наблюдается, так как отсутствуют сигналы на выходах элементов 8 i-x коммутационных блоков.

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

Пусть при анализе очередного разряда обнаружено неравенство сравниваемых чисел. В схеме устройства при этом проляются сигналы на вторых входах элементов 8 блоков 5 i (,2, ,.., n) коммутации и вторых входах элементов 9 блоков тех регистров чисел, у которых в анализируемом разряде записан нуль, а также элементов 9 блоков 5,- и элементов 9 блоков 5i+,; регистров чисел, у которых в анализируемом разряде записана единица. В результате хотя бы на одном из входов элементов 11-14, а значит и на их выходах, имеются сигналы.

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

На всех трех входах элемента 19 имеются сигналы. Появляющийся на выходе элемента/5 сигнал через элемент б перебрасывает индикаторные триггеры 10 блоков 5; (i 1,2,... ,п) регистров чисел с единицей в анализируемоМ разряде, в результате чего исчезают сигналы на вторых входах элементов S и 9 блоков 5j этих регистров. В итоге, до окончания процесса сравнения эти регистры посредством первых коммутационных блоков отключаются от элементов 11 1:1 12 -ц подключаются через коммутационные блоки 5,+/; к элементам 13 и 14. Аналогичные переключения происходят в блоках регистров с нулем в анализируемом разряде, в результате чего эти регистры отключаются от элементов 13 и 14 и подключаются к элементам .// и 12. Сигнал с выхода элемента 19 также перебрасывает триггер 2,1, i.B результате чего исчезает один вход элемента 19 и сигнал на его выходе до окончания процесса сравнения.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

определяемые содержимым анализируемого

разряда подмассива с наибольшим числом.

В анализируемом разряде подмассива с

наибольшн.м числом записан нуль. В этом

елучае имеются сигналы на выходах элементов 11, 12 и 13 и отсутствует сигнал на выходе элемента 14. Состояния регистров 2, 3 li 4 не изменяются, так как нет сигналов на выходах элементов 14, 16, 17 и 18. Сигнал с выхода элемента 15 через элемен

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

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

В анализируемом разряде подмассива с

наибольшим числом Записана единица. В это.м случае имеются сигналы на выходах элементов 11, 12 и 14 и отсутствует сигнал на выходе элемента 13. Сигналами с выходов элементов 14 и 16 записываются единвцы в анализируемый разряд регистров 3 и 2. Состояние регистра 4 не изменяется. На вычитающем входе регистра 2 сигнал с выхода элемента 17 отсутствует.

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

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

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

Сравнение продолжается до тех пор, пока не будет произведен полный цикл продвижения чисел и результатов сравнения по кольцевым регистрам. 9 Б итоге в регистре 3 записывается нaE большее число, в регистре 4 - иаименьшее число, в регистре 2 - .максимальная разность. Регистры (либо один регистр), в которых записано наибольшее число, индицируются комбинацией -состояний индикаторных триггеров «01, наименьшее число - комбинацией «10. Введение новых связей между элементами устройства, а также реализация блоков коммутации Ба элементах И, ИЛИ и триггерах с соответствуюши ми связями позволяет расширить его функциональные возможности, что выгодно отличает его от известных устройств, поскольку дает возможность лри сравнительной схемной простоте получить за то же самое время комплексное решение задачи сравнения, сохранить информацию, индицировать положение экстремальных чисел в массиве. Формула изобретения 1. Устройство для сравнения чисел, содержаш,ее 2л блоков коммутации, п кольцевых сдзигаюших регистров, причем прямой и инверсный выходы каждого t-ro кольцевого сдвигающего регистра соединены с первым и вторым входами i-ro и (t + n)-ro блоков коммутации, где ,2 ..., п, регистр максимальной разности, регистр наибольшего числа, регистр наименьшего числа, элементы И, ИЛИ, НЕ, триггер, о т л ичающееся тем, что, с целью расширения функциональных возможностей Б чагти получения значения максимальной разности наряду с наибольшим и наименьшим числами, в нем первые и вторые выходы каждого t-ro блока коммутации соединены с входами первого и второго элементов ИЛИ соответственно, выход первого элемента ИЛИ соединен с первыми входами первого и второго элементов И и через первый элемент НЕ с первыми входами третьего и четвертого элементов И, выход второго элемента ИЛИ подключен к второму входу первого элемента И, к первому входу пятого элемента И, к вторым входам третьего и четвертого элементов И, выход третьего элемента ИЛИ соединен с вторым входом пятого элемента И и с первым входом шесто68го элемента И, выход четвертого элемента ИЛИ подключен к вторым входам второго и шестого элементов И, к входу регистра наибольшего числа и через второй элемент НЕ к третьему входу третьего элемента PI, выход первого элемента Pi соединен с третьими входами 1-х блоков коммутации, выход второго элемента 1-1 подключен к информациолному входу регистра максимальной разности, выходы третьего и четвертого элементов И соединены с управляющим входом регистра максимальной разности и с входом регистра наименьшего числа соответственно, выход пятого элемента И подключен к входу установки в единичное состояние триггера, инверсный выход которого соединен с третьим входом пятого элемента И, выход шестого элемента И подключен к третьим выходам (i + n)-x блоков коммутации, выход пятого элемента И соединен с четвертыми входами блоков коммутации, пятые входы которых и вход установки .в пулевое состояние триггера подключены к управляющей шине устройства. 2. Устройство по п. 1, о т л п чающеес я тем, что в нем каждый блок коммутации содержит элементы И, элемент ИЛИ и триггер, причем первые входы первого и второго элементов И соединены с первым входом блока коммутации, второй вход первого элемента И подключен к выходу элемента ИЛИ, а выход первого элемента И соединен с первым входом триггера, инверсный выход которого подключен к второму входу второго элемента И и первому входу третьего элемента И, выходы которых соединены с первым и вторым выходами блока коммутации соответственно, второй вход третьего элемента И подключен к второму входу блока коммутации, первый п второй входы элемента ИЛИ соединены с третьим и четвертым входами блока коммутации соответственно, второй вход триггера подключен к пятому входу блока коммутации. Источники информации, принятые во внимание при экспертизе: 1.Авторское свидетельство СССР ЛГо 444180, кл. G Об F 7/04, 11.08.72 2.Авторское свидетельство СССР № 328450, кл. G Об F 7/00, 06.11.70 (прототип) .