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

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

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

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

Наиболее близким к предлагаемому является устройство для сортировки чисел, содержащее (п - 1) групп блоков сравнения двух чисел по (п - I - 1) блоков в каждой

группе (где 1 2, 3п; п - количество чисел

в массиве), п групп коммутаторов, п сумматоров и (п - ) групп элементов НЕ, причем входы первого сравниваемого числа устройства соединены с первыми группами входов блоков сравнения первой группы и информационными входами коммутаторов первой группы, входы 1-го сравниваемого числа устройства соединены с первыми группами входов блоков сравнения 1-й группы, информационными входами коммутаторов 1-й группы и вторыми группами входов i-x блоков сравнения р-х групп, где р 1, 2,,. , (i - 1), вход n-го сравниваемого числа устройства соединен с информационными входами коммутаторов n-й группы и вторыми группами входов (п - 1)-х блоков сравнения всех фупп, выходы блоков сравнения каждой k-й группы (где k 1, 2, , п - -1), соединены с первой группой входов k-ro

сумматооа, выходы всех п сумматоров соединены с управляющими входами коммутаторов соответствующих групп, разрядные выходы J-x коммутаторов всех групп объединены (где j«1,2,..., п) и подключены к J-M выходам устройства, входы элементов НЕ О - 1}-й группы соединены соответственно с выходами 1-х блоков сравнения р-х групп, а выходы элементов НЕ (I - 1)-й группы подключены к второй группе входов 1-го сумма- тора,

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

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

Поставленная цель достигается тем, что в устройство для сортировки чисел, содержащее (п -1) групп блоков сравнения, где п - количество сортируемых чисел, (п - 2) счетчиков, {п -1) элементов НЕ и две группы коммутаторов, причем 1-я группа блоков сравнения, где 1 1,2..... (п - 1), содержит (п -1) блоков сравнения, вход 1-го сортируемого числа устройства соединен с первыми входами блоков сравнения 1-й группы, вход (I + 1)-го сортируемого числа устройства соединен с вторыми входами j-x блоков сравнения (I + 1 - jj-й группы, где J 1, 2I,

первые выходы блоков сравнения t-й труп-

пы (I 1, 2п - 2} соединены с входами I

-го счетчика, информационный вход k-ro сортируемого числа устройства {к 1, 2,..., п), соединен с информационным входом k- го коммутатора первой группы, управляю- щие входы 1-х коммутаторов первой и второй групп объединены, выходы коммутаторов первой и второй групп соответственно о€ьединены по группам и являются соответственно первым и вторым информационны- ми выходами устройства, первый выход первого блока сравнения первой группы соединен с входом первого элемента НЕ, введены в JK-триггеров. {п + 1} групп элементов ИЯИ, (п + 1) элементов И и (п - 1} элементов ИЛИ-НЕ, причем первый и второй выходы р-го блока сравнения 1-й группы, где р -1,2,..., (п -1), соединены соответственно с лервым и вторым входами р-го элемента ИЛИ 1-й группы, выход которого соединен с

р-м входом 1-го элемента И, выход которого соединен с управляющим входом 1-го коммутатора первой группы и 1-ми входами всех элементов ИЛИ-НЕ с 1-го по (п - 1)-й, выход первого элемента И соединен с J- входом первого JK-триггера, выход п-го элемента И соединен с управляющим вх,о- дом п-го коммутатора первой группы, выход (I + 1)-го элемента И соединен с первым входом 1-го элемента ИЛИ n-й группы, выход которого соединен с J-еходом (I + 1)-го JK-триггера, прямой выход первого JK- триггера соединен с первым входом (п + 1)-го элемента И, выход которого является выходом окончания работы устройства, прямой выход () + 1)-го JK-триггера соединен с (I + 1}-м входом-(п + 1)-го элемента И и с третьим входом j-ro элемента ИЛИ (I + 1 - JJ-й группы, инверсный выход k-ro JK-триггера соединен с (п - к + 1)-м входом k-ro элемента И, выходы 1-х элементов НЕ и ИЛИ-НЕ соединены соответственно с (п + 1 - J)-M и (п + 2- )-м входами (I + 1)-го элемента И, г-й вход 1-го элемента ИЛИ (п + 1)-й группы, где г- 1,2,...,( + 1) подключен к первому выходу (I + 2 - г)-го блока сравнения r-й группы, первый выход первого блока сравнения первой группы соединен с вторым входом первого элемента ИЛИ n-й группы, выход 1-го элемента ИЛИ (л + 1)-й группы соединен с входом (I + 1)-го элемента НЕ и вторым входом (I + 1)-го элемента ИЛИ n-й группы, выход 1-го счетчика соединен с информационным входом 1-го коммутатора второй группы, первый выход блока сравнения (п - 1}-й группы соединен с информационным входом (п - 1)-го коммутатора второй группы, тактовый вход устройства соединен с входами синхронизации всех JK-триггеров,

Кроме того, счетчш содержит (т -1), где т - разрядность счетчика, разделенных на I групп r-разрядных сумматоров (г - 1, 2

I), по (-) сумматоров в каждой группе,

2Г

причем входы счетчика с первого по гс-й подключены к входам слагаемых одноразрядных сумматоров первой группы в произвольном порядке, выходы суммы и переноса каждого из сумматоров t-й группы (J 1,2, ..„ ({ - 1) подключены к соответствующим разрядам одного из входов слагаемого одного из сумматоров (i 1)-й группы, вУходы суммы и переноса сумматора 1-й группы являются разрядами выхода счетчика.

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

На фиг. 1-3 представлена функциональная схема устройстства; на фиг. 4 - функциональная схема счетчика.

Устройство для сортировки чисел содержит блоки 1 сравнения, счетчики 2, JK- триггерьи 3, группы 4-6 элементов ИЛИ, группу 7 элементов ИЛИ-НЕ, группу 8 элементов И, первую 9 и вторую 10 группы коммутаторов, элементы НЕ 11, информационные входы 12, тактовый вход 13, выход 14 окончания работы, первый 15 и второй 16 информационные выходы.

Счетчик 2 содержит сумматоры 17, входы 18 и выходы 19.

Устройство для сортировки чисел работает следующим,-образом. После подачи напряжения питания на устройство все триггеры 3.1-З.л приводятся в исходное состояние. Затем на входы 12.1-12.п информации одновременно поступают сортируемые числа. Допустим п 5. Пусть на входы информации устройства с первого 12.1 по пятый 12.5 поступили соответственно числа а, Ь, с, d и е, которые соотносятся между собой следующим образом

.(1)

До поступления на тактовый вход 13 устройства первого тактового импульса происходит сравнение чисел между собой на блоках сравнения групп 1.1-1.5.

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

На выходах Меньше всех блоков сравнения с первого по третий второй группы 1.2 устанавливаются единичные сигналы, так как , b d и Ь е, а на выходах Равно - нулевые.

На выходах Меньше и Равно первого и второго блоков сравнения третьей 1.3 группы блоков сравнения устанавливаются нулевые сигналы, так как с d и с е.

На выходе Меньше блока сравнения четвертой 1.4 группы устанавливается единичный сигнал, а на выходе Равно - нулевой, так как d е.

Сигналы с выходов Меньше и Равно блоков сравнения поступают на входы соот- 5 ветствующих элементов ИЛИ соответствующих групп с 4.1 по 4.4 и с выходов этих элементов поступают на входы соответствующих элементов И 8.1-8.5.

На входах первого элемента И 8.1 при0 сутствуют единичные сигналы с инверсного выхода триггера 3.1 и с выходов всех элементов ИЛИ первой группы, кроме первого, на выходе которого присутствует нулевой сигнал, который приводит к тому, что нуле5 вой сигнал с выхода элемента И 8,1 запрещает прохождение сигналов на выходы первых коммутаторов 9.1 и 10.1 первой и второй групп соответственно. На первый коммутатор первой группы 9.1 поступает

0 число а, а на первый коммутатор второй группы 10.1 - число, определяющее количество чисел в массиве, равных числу а. Так как а d, то на входы счетчика 2.1 поступает только один единичный сигнал с выхода

5 первого блока сравнения группы 1.1. а на выходе счетчика 2.1 появляется соответствующий код, равный единице.

Аналогично описанному на входы второго элемента И 8.2 с выходов Меньше

0 блоков сравнения второй группы 1.2 поступают единичные сигналы через элементы ИЛИ второй группы 4.2, а на друше входы этого же элемента И 8.2 поступают единичные сигналы с инверсного выхода второго

5 триггера 3.2, с выхода первого элемента НЕ 11.1, так как на выходе Равно первого блока сравнения первой группы 1.1 присутствует нулевой сигнал, и с выхода первого элемента 7.1, группы элементов ИЛИ-НЕ,

0 так как на выходе первого элемента И 8.1 группы так же присутствует нулевой сигнал. Наличие единичных сигналов на всех входах элемента И 8.2 вызывает появление единичного сигнала на выходе этого элемента, ко5 торый поступает на J-вход второго триггера 3.2 через элемент ИЛИ 5.1 и на входы управления коммутаторами 9.2 и 10.2.

На входы коммутатора 9.2 поступает число Ь с входа 12.2 устройства, а на входы

0 коммутатора 10.2 - нулевой код количества равных чисел со счетчика 2.2, поскольку в сортируемом массиве нет чисел, равных Ь, и на входы счетчика поступают нулевые сигналы с выходов Равно всех блоков сравне5 ния второй группы 1.2.

Наличие единицы на входе управления коммутаторами 9.2 и 10.2 разрешает прохождение на его выход и, следовательно, на первый выход 15 устройства числа Ь, которое является наибольшим в массиве сортируемых исел, в на второй выход 16 поступает нулевой код. Выходы остальных коммутаторов закрыты нулевыми сигналами с выходов соответствующих элементов И ЛИНЕ 7.2-7.4, поскольку на входы указанных элементов поступает единичный сигнал с выхода элемента И 8.2. Так как на выходе Равно третьего блока сравнения первой группы 1.1 присутствует единичный сигнал, поскольку а d, то через элементы ИЛИ второй 6.2 шестой группы и третий 5.3 пятой группы он поступает на J-вход четвертого 3.4 триггера, а на J-входах остальных (третьего 3.3 и пятого 3.5) триггеров имеется нулевой сигнал. По заднему фронту первого тактового импульса на тактовом входе 13 устройства, который поступает на С-входы всех триггеров, второй 3.2 и четвертый 3.4 триггеры устанавливаются в единичное состояние, в на входы элементов И 8.2 и 8.4 поступает нулевой сигнал с инверсных выходов этих триггеров, вследствие чего на выходе элемента И 8.2 появляется также нулевой сигнал, запрещающий прохождение сигналов через коммутаторы 9.2 и 10.2 на первый 15 и второй 16 выходы устройства, а элемент И 8.4 так же блокируется и число b исключается из дальнейшей обработки, как уже поступившее на выход устройства, а число d - так как оно имеет равное ему число а, поступившее на информационный вход устройства с меньшим порядковым номером. Кроме того, единичный сигнал с прямого выходе триггера 3.2 поступает на третий вход первого элемента ИЛИ первой группы 4.1 после срабатывания триггера. Появление указанного сигнала приводит к тому, что на всех входах элемента И 8.1 устанавливаются единичные сигналы, так как на выходе первого элемента ИЛИ первой группы 4.1 до сих пор присутствовал нулевой сигнал из-за поступления на его входы нулевых сигналов с выходов Меньше и Равно первого блока сравнения первой группы (так как а Ь). Это приводит к тому, что на выходе элемента И 8.1 появляется единичный сигнал, который, поступая на входы управления коммутаторами 9.1 и 10.1, открывает их, и на первый 15 и второй 16 выходы устройства поступают соответственно числа а (наибольшее из оставшихся чисел) и единичный код, сообщающий о количестве чисел в сортируемом массиве, равных а, соответственно. Этот же сигнал с выхода элемента И 8.1 поступает на J-вход триггера 3.1 и через элементы ИЛИ-НЕ группы 7.2.7.4 на входы элементов И группы 8.3 и 8.5 и блокирует выдачу остальных чисел на выходы устройства. Единичный сигнал с прямого выхода триггера 3.4 поступает на

третьи входы первого элемента ИЛИ третьей группы 4.3, второго элемента ИЛИ второй группы 4.2 и третьего элемента ИЛИ первой группы 4.1. Поступление укаэанного сигнала не изменяет состояния соответствующих элементов И 8.1, 8.2 и 8.3, так как на выходе третьего элемента ИЛИ первой группы 4.1 и второго элемента второй группы 4.2 ранее уже был установлен еди0 ничный сигнал, а появление единичного сигнала на выходе первого элемента ИЛИ третьей группы не влияет на состояние выходного сигнала элемента И 8.3, так как на выходе второго элемента ИЛИ этой группы

5 остается нулевой сигнал. Поступлением второго тактового импульса на тактовый вход 13 устройства завершается выдача второго по величине числа а сортируемого массива, триггер 3.1 устанавливается в

0 единицу по заднему фронту этого импульса и блокирует элемент И 8.1, нулевой сигнал с выхода которого закрывает коммутаторы 9.1 и 10.1.

Этот же сигнал с выхода элемента И 8.1,

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

0 с выхода элемента НЕ 11.1 (поскольку в массиве отсутствуют числа, равные числу е) и инверсного выхода пятого триггера 3.5, что вызывает появление единичного сигнала на выходе этого элемента. Появление единич5 ного сигнала на выходе элемента И 8.5 разрешает прохождение числа е на выход 15 информации устройства через коммутатор 9.5. При этом на выходе 16 количества равных чисел устройства имеется нулевой код,

0 поскольку во второй группе коммутаторов 10 коммутатор 10.5 отсутствует, так как число е поступает на последний 12.5 информационный вход устройства и. если бы оно имело в массиве равные себе числа, оно

5 было бы обработано (заблокирован элемент И 8.5 срабатыванием триггера 3.5, как и при числа d в первом же такте работы устройства) ранее при обработке первого числа в первом такте работы.

0 При поступлении третьего тактового импульса на вход 13 устройства срабатывает триггер 3.5, что приводит к блокировке элемента И 8.5 и появлению единичного сигнала на третьем входе второго элемента ИЛИ

5 третьей группы 4,3. Появление этого сигнала приводит к появлению на входе элемента И 8.3 единичного сигнала и, поскольку на остальные входы этого элемента единичные сигналы поданы ранее, на его выходе появляется сигнал, разрешающий прохождение числа С через коммутатор 9.3 на выход информации 15 устройства. При этом на выходе количества чисел 16 устройства имеется нулевой код, поскольку на вход коммутатора 10.3 поступает нулевой сигнал с выхода счетчика 2.3.

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

Таким образом, в результате сортировки числового массива на-первом выходе информации 15 устройства формируются последовательно все числа, содержащиеся в массиве в порядке убывания, причем на втором выходе 16 одновременно с числами формируется код количества содержащихся в массиве чисел, равных данному, и для сортировки числового массива из пяти чисел необходимо четыре такта работы устройства.

Устройство на своем втором выходе 16 формирует код количества чисел, равных числу, выдаваемому на первом выходе 15 информации.

Если в группу счетчиков 2.1-2.(п - 2} добавить еще один (п - 1)-й счетчик, один из входов счетчика подсоединить к шине 1 устройства, а во вторую группу коммутаторов добавить коммутатор Ю.п и его вход также подключить к шине 1 устройства, то на втором выходе устройства 16 формируется код общего количества чисел в массиве, имеющих значение числа, выдаваемого на первый выход 15 устройства.

Работа счетчика 2 заключается в том, что он подсчитывает количество единичных сигналов, поступающих на его входы 18.1- 18.т и на выходах 19.1-19.(г+ формирует сумму в двоичном коде.

Формула изобретения Устройство для сортировки чисел, содержащее (п - 1) групп блоков сравнения, где п - количество сортируемых чисел, п - 2 счетчиков, п -1 элементов НЕ и две группы коммутаторов, причем 1-я группа блоков

сравнения, где 1 1,2п -1, содержит

(п -1) блоков сравнения, вход 1-го сортируемого числа устройства соединен с первыми входами блоков сравнения 1-й группы, вход О 1)-го сортируемого числа устройства - с вторыми входами j х блоков сравнения,( + 1 - }-й группы, где j 1, 2, .... I, первые выходы блоков сравнения Ь-й группы (1-1,

2п - 2) соединены с входами 1-го счетчика, информационный вход k-ro сортируемого числа устройства (k - 1,2..... п) соединен с информационным входом k -го коммутато- 5 ра первой группы, управляющие входы 1-х коммутаторов первой и второй групп объединены, выходы коммутаторов первой и второй групп соответственно объединены и являются соответственно первым и вто- 10 рым информационными выходами устройства, первый выход первого блока сравнения первой группы соединен с входом первого элемента НЕ, отлича ю щ - е е с Ятем, что, с целью повышения быстро5 действия, в него введены п JK-триггеров, (п + 1) групп элементов ИЛИ, (п + 1) элементов И и (п -1) элементов ИЛИ-НЕ, причем первый и второй выходы р-го блока сравнения 1-й группы, где р 1, 2п -1, соединены

0 соответственно с первым и вторым входами р-го элемента ИЛИ Ьй группы, выход которого соединен с р-м входом 1-го элемента и, выход которого соединен с управляющим входом 1-го коммутатора первой группы и

5 1-ми входами всех элементов ИЛИ-НЕ с 1-го по (п - 1)-й, выход первого элемента И сое- динен с J-входом первого JK-триггера, выход п-го элеме га И соединен с управляющим входом п-го коммутатора

0 первой группы, выход (I + 1)-го элемента И - с первым входом 1-го элемента ИЛИ п-й группы, выход которого соединен с J-входом 0 + 1)-го JK-триггера, прямой выход первого JK-триггера соединен с первым входом

5 (п + 1}-го элемента И, выход которого является выходом окончания работы устройства, прямой выход (I -1- 1)-го JK-триггера соединен с (I + 1)-м входом (п + 1)-го элемента И и с третьим входом j-ro элемента ИЛИ (I + 1 - j)-u

0 группы, инверсный выход k-ro JK-триггера соединен с (п - k + 1)-м входом k-ro элемента И, выходы -х элементов НЕ и ИЛИ-НЕ соединены соответственно с{п + 1 - )-м и (п + 2- - )-м входами (I + 1)-го элемента И, r-й вход

5 1-го элемента ИЛ И (л + 1)-й группы, где г« 1,

21 + 1, подключен к первому выходу (I +

-2 - г)-го блока сравнения r-й группы, первый выход первого блока сравнения первой группы соединен с вторым входом первого

0 элемента ИЛИ n-й группы, выход 1-го элемента ИЛИ (п + 1)-й группы соединен с входом (I + 1)-го элемента НЕ и с вторым входом (I + 1)-го элемента ИЛИ n-й группы, выход 1-го счетчика соединен с информаци5 онным входом 1-го коммутатора второй группы, первый выход блока сравнения {п - 1)-й группы соединен с информационный входом (п - 1)-го коммутатора второй группы, тактовый вход устройства соединен с входами синхронизации всех JK-триггеров,

ч- чг- т

i

1Ж.Ш

$

W&2 Ф

Изобретение относится к автоматике и вычислительной технике. Цель изобретения - повышение быстродействия. Устройство содержит блоки сравнения, счетчики, IK- триггери, группы элементов ИЛИ, группу элементов ИЛИ-НЕ, группу элементов И, группы коммутаторов, элементы НЕ, информационные входы, тактовый вход, выход окончания работы, информационные выходы. БС сравнивают каждое число с каждым, счетчики подсчитывают количество равных чисел. По каждому тактовому сигналу на один информационный выход устройства выдаются последовательно все числа в порядке убывания, а на другой информационный выход - количество этих чисел в массиве минус единица. 4 ил

г-Л

У1

SJ

US

Г|

j

W-«s

и о

Г

IE-«fe

9W.f