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

(9) Ы +м 1 31" ЕИ СПИ АВТОРСКО ЕТЕЛЬ рское го о тм.ЧИ ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР НИЕ ИЗОБРЕ(71) Специальное конструктоХарьковского производственнонения "Коммунар"(56) Авторское свидетельство СССРЬ 1107118, кл, 6 06 Р 7/06, 1984,Авторское свидетельство СССРВ 1247860, кл. 6 06 Р 7/06 1985.(54) УСТРОЙСТВО ДЛЯ СОРТИРОВСЕЛ Изобретение относится к цифровой вычислительной технике и может быть использовано в информационно-вычислительных системах.Известно устройство для сортировки чисел, содержащее распределитель импульсов, и регистров, и блоков сравнения, и элементов И, и триггеров, и элементов ИЛИ, счетчик, сумматор и регистр результата.Недостатком данного устройства является низкое быстродействие, обусловленное тем, что на сортировку каждого из чисел массива необходим один такт. работы устройства даже в том случае, когда массив сортируемых чисел содержит некоторое количество одинаковых по значению чисел.Наиболее близким к предлагаемому является устройство для сортировки чисел, содержащее (и - 1) групп блоков сравнения двух чисел по (и - 1- 1) блоков в каждой(57) Изобретение относится к автоматике и вычислительной технике, Цель изобретения - повышение быстродействия, Устройство содержит блоки сравнения, счетчики, Криггеры, группы элементов ИЛИ, группу элементов ИЛИ-НЕ, группу элементов И, группы коммутаторов, элементы НЕ, информационные входы, тактовый вход, выход окончания работы, информационные выходы. БС сравнивают каждое чйсло с каждым, счетчики подсчитывают количество равных чисел. По каждому тактовому сигналу на один информационный выход устройства выдаются последовательно все числа в порядке убывания, а на другой информационный выход - количество этих чисел в ) массиве минус единица. 4 ил. группе(где 1=2,3, , и; и - количество чисел в массиве), и групп коммутаторов, и сумматоров и (и - 1) групп элементов НЕ, причем входы первого сравниваемого числа устройства соединены с первыми группами входов 4 блоков сравнения первой группы и инфор- ф мационными входами коммутаторов пер- р вой группы, входы 1-го сравниваемого числа устройства соединены с первыми группами входов блоков сравнения 1-й группы, информационными входами коммутаторов -й группы и вторыми группами а входов 1-х блоков сравнения р-х групп, где р = 1, 2.(1 - 1), вход и-го сравниваемого числа устройства соединен с информационными входами коммутаторов п-й группы. и вторыми группами входов (и -1)-х блоков сравнения всех групп, выходы блоков сравнения каждой 1-й группы (где 1 = 1, 2, и- -1), соединены с первой группой входов 1-го35 мого числа устройства соединен с первыми входами блоков сравнения 1-й группы, вход (1 + 1)-го сортируемого числа устройства соединен с вторыми входами )-х блоков сравнения (1 + 1 - -й группы, где ) = 1, 2, 1,первые выходы блоков сравнения 1-й.группы ( = 1, 2 и - 2) соединены с входами 1 -го счетчика, информационный вход М-го сортируемого числа устройства (ф = 1, 2, . и), соединен с информационным входом 140 го коммутатора первой группы, управляющие входы 1-х коммутаторов первой и второй групп обьединены, выходы коммутаторов пЕреой и второй групп соответственно оеьединены по группам и являются соотеетственно первым и вторым информационны ми выходами устройства, первый выход первого блока сравнения первой группы соединен с входом первого элемента НЕ, введены и 3 К-триггеров, (и + 1) групп злементов ИЛИ; (и + 1) элементов И и (и - 1) злементое ИЛИ-НЕ, причем первый и второй выходы р-го блока сравнения 1-й группы, где р -1, 2, , (и - 1), соединены соответственно с первым. и вторым входами р-го элемента ,ИДЙ 1-й группы, выход которого соединен с сумматооа, выходы всех и сумматоров соединены с управляющими входами коммутаторов соответствующих групп, разрядныевыходы )-х коммутаторов всех групп объе- .динены (где) -1, 2, ; и) и подключены к)-м 5выходам устройства, входы элементов НЕ(1 - 1)-й группы соединены соответственно свыходами 1-х блоков сравнения р-х групп, авыходы элементов НЕ (1 - 1)-й группы подключены к второй группе входов 1-го сумматора,Недостатком устройства является необходимоегь подсчета в упорядоченном массиве количества равных чисел, что требуетдополнительных временных и, аппаратурных затт,Цель изобретения - повышение быстродействия устройства при сортировке числоеего массива, содержащего некотороеколичество равных чисел, за счет формирования иа еыходе устройства значения чиселв порядке их убывания в сопровождениичисла, дщуеделяющего количество чисел есоетируемом массиве, равных числу, выдаваемому в текущем такте работы устройст. ва,Поставленная цель достигается тем,.чтов устройство для сортировки чисел, содержащее (и - 1) групп блоков сравнения, гдеи - количество сортируемых чисел, (и - 2) ЗОсчетчиков, (и -1) элементов НЕ и две группыкоммутаторов, причем 1-я группа блоковсравнения, где, 2, , (и - 1), содержит(и - ) блоков сравнения, вход 1-го сортируер-м входом 1-го элемента И, выход которого соединен с управляющим входом 1-го ком-. мутатора первой группы и 1-ми входами всех элементов ИЛИ-НЕ с 1-го по (и - 1)-й, выход первого элемента И соединен с 3- входом первого ЗК-триггера, выход и-го элемента И соединен с управляющим входом и-го коммутатора первой группы, выход(1+ 1)-го элемента И соединен с первым входом 1-го элемента ИЛИ и-й группы, выход которого соединен с 3-входом (1 + 1)-го .1 К-триггера, прямой выход первого К- триггера соединен с первым входом(и+ 1)-го элемента И, выход которого является выходом окончания работы устройства, прямой выход (1 + 1)-го ЗК-триггера соединен с ( + 1)-м входом(и+ 1)-го элемента И и с третьим входом )-го элемента ИЛИ ( + 1 - -й группы, инверсный выход й-го ЭК-триггера соединен с (и - й+ 1)-м входом М-го элемента И, выходы 1-х элементов НЕ и ИЛИ-НЕ соединены соответственно с (и+ 1м и(и+ 2- -1)-м входами (1 + 1)-го элемента И, г-й вход 1-го элемента ИЛИ (и+ 1)-й группы, где г= 1,2, .,(1+ 1) подключен к первому выходу (1 + 2 - г)-го блока сравнения г-й группы, первый выход первого блока сравнения первой группы соединен с вторым входом первого элемента ИЛИ и-й группы, выход 1-го элемента ИЛИ (и + 1)-й группы соединен с входом (1 + 1)-го элемента НЕ и вторым входом (1 + 1)-го элемента ИЛИ и-й группы, выход 1-го счетчика соединен с информационным входом 1-го коммутатора второй группы, первый выход блока сравнения (и - 1)-й группы соединен с информационным входом (и - 1)-го коммутатора второй группы, тактовый вход устройства соединен с входами синхронизации всехК-триггеров.Кроме того, счетчик содержит(ги -1), где в - разрядность счетчика, разделенных на 1 групп г-разрядных сумматоров(г = 1, 2, , 1), по ( - ) сумматоров в каждой группе,2причем входы счетчика с первого по в-й подключены к входам слагаемых однораз-, рядных сумматоров первой группы в произвольном порядке, выходы суммы и переноса каждого из сумматоров 1-й группы (1 = 1, 2, , (1 - 1) подключены к соответствующим разрядам одного из входов слагаемого одного из сумматоров (1 + 1)-й группы, выходы суммы и переноса сумматора 1-й группы являются разрядами выхода счетчика,В результате введения и .К-триггеров, (и + 1) групп элементов ИЛИ, (и + 1) элементов И и (и - 1) элементов ИЛИ-НЕ устройство. при сортировке чисел обеспечивает подсчет количества равных чисел, имеющихся в мас10 15 20 25 30 35 40 45 50 ния второй группы 1,2. 55 сиве одновременно с выдачей первого числа иэ каждой группы равных чисел на выходы устройства, что приводит к повышениюего быстродействия.На фиг, 1-3 представлена функциональная схема устройстства; на фиг. 4 - функциональная схема счетчика,Устройство для сортировки чисел со держит блоки 1 сравнения, счетчики 2, 3 Ктриггеры: 3, группы 4-6 элементов ИЛИ,группу 7 алемеитов ИЛИ-НЕ, группу 8 элементов И, первую 9 и вторую 10 группыкоммутаторов, элементы НЕ 11, информационные входы 12, тактовый вход 13, выход14 окончания работы, первый 15 и второй 16информационные выходы.Счетчик 2 содержит сумматоры 17, входы 18 и выходы 19,Устройство для сортировки чисел работает следующим;образом. После подачи напряжения питания на устройство всетриггеры 3.1 - 3 и приводятся в исходное состояние. Затем на входы 12.1 - 12.п информации одновременно поступают сортируемыечисла. Допустим и = 5. Пусть на входы информации устройства с первого 12.1 по пятый12.5 поступили соответственно числа а, Ь, с,б и е, которыесоотносятся между собойследующим образомЬа=бес. (1)До поступления на тактовый вход 13устройства первого тактового импульсапроисходит сравнение чисел между собойна блоках сравнения групп 1 1 - 1.5.На выходах блоков сравнения первойгруппы устанавливают следующие сигналы,На первом "Равно", на втором "Меньше"выходах первого блока сравнения устанавливаются нулевые сигналы, так как иэ(1) аЬ. На выходах "Меньше" второго ичетвертого блоков сравнения устанавливается единичный сигнал, так как ас и ае,а на выходах "Равно" этих же блоков сравнения имеются нулевые сигналы. Так кака = б, на выходе "Равно" третьего блокасравнения устанавливается единичный сигнал, а на выходе "Меньше" - нулевой,На выходах Меньше" всех блоков сравнения с первого по третий второй группы 1.2 устанавливаются единичные сигналы, так как Ьс, ЬбиЬе,ана выходах "Равно" - нулевые.На выходах "Меньше" и "Равно" первого и второго блоков сравнения третьей 1.3 группы блоков сравнения устанавливаются нулевые сигналы, так как сб и се.На выходе "Меньше" блока сравнения четвертой 1.4 группы устанавливается единичный сигнал, а на выходе "Равно" - нулевой, так как бе. Сигналы с выходов Меньше" и "Равно" блоков сравнения поступают на входы соответствующих элементов ИЛИ соответствующих групп с 4,1 по 4.4 и с выходов этих элементов поступают на входы соответствующих элементов И 8,1-8.5.На входах первого элемента И 8;1 присутствуют единичные сигналы с инверсного выхода триггера 3.1 и с выходов всех элементов ИЛИ первой группы, кроме первого, на выходе которого присутствует нулевой сигнал, который приводит к тому, что нулевой сигнал с выхода элемента И 8,1 запрещает прохождение сигналов на выходы первых коммутаторов 9,1 и 10,1 первой и второй групп соответственно, На первый коммутатор первой группы 9,1 поступает число а, а на первый коммутатор второй группы 10.1 - число, определяющее количество чисел в массиве, равных числу а. Так как а = б, то на входы счетчика 2.1 поступает только один единичный сигнал с выхода первого блока сравнения группы 1.1, а на выходе счетчика 2.1 появляется соответствующий код, равный единице,Аналогично описанному на входы второго элемента И 8.2 с выходов "Меньше" блоков сравнения второй группы 1.2 поступают единичные сигналы через элементы ИЛИ второй группы 4,2, а на друг ие входы этого же элемента И 8,2 поступают единичные сигналы с инверсного выхода второго триггера 3.2, с выхода первого элемента Н Е 11.1, так как на выходе "Равно" первого блока сравнения первой группы 1,1 присутствует нулевой сигнал, и с выхода первого элемента 7.1, группы элементов ИЛИ-НЕ, так как на выходе первого элемента И 8.1 группы так же присутствует нулевой сигнал, Наличие единичных сигналов на всех входах элемента И 8,2 вызывает появление единичного сигнала на выходе этого элемента, который поступает на 3-вход второго триггера 3,2 через элемент ИЛИ 5.1 и на входы управления коммутаторами 9,2 и 10,2,На входы коммутатора 9,2 поступает число Ь с входа 12.2 устройства, а на входы коммутатора 10,2 - нулевой код количества равных чисел со счетчика 2.2, поскольку в сортируемом массиве нет чисел, равных Ь, и на входы счетчика поступают нулевые сигналы с выходов "Равно" всех блоков сравнеНаличие единицы на входе управления коммутаторами 9,2 и 10.2 разрешает прохождение на его выход и, следовательно, на первый выход 15 устройства числа Ь, которое является наибольшим в массиве сорти 1737441руемых цисел. в на второй выход 18 поступает нулевой код. Выходы остальных коммутаторов закрыты нулевыми сигналами с выходов соответствующих элементов ИЛИНЕ 7.2-7.4, поскольку на входы указанных элементов поступает единичный сигнал с выхода элемента И 8.2. Тэк как на выходе "Равно" третьего блока сравнения первой группы 1.1 присутствует единичный сигнал, поскольку а - б, то через элементы ИЛИ второй 6.2 шестой группы и третий 5.3 пятой группы он поступает на 4-вход четвертого 3,4 триггера, а на 3-входах остальных (третьего 3,3 и пятого 3,5) триггеров имеется нулевой сигнал. По заднему фронту первого тактового импульса на тактовом входе 13 устройства, который поступает нв С-входы всех триггеров, второй 3,2 и четвертый 3.4 триггеры устанавливаются в единичное состояние, е на входы элементов И 8.2 и 8,4 поступает нулевой сигнал с инверсных выходов этих триггеров, вследствие чего на выходе элемента И 8.2 появляется также нулевой сигнал, запрещающий прохождение сигналов через коммутаторы 9,2 и 16.2 на первый 15 и второй 16 выходы устройства, а элемент И 8.4 тэк же блокируется и число Ь исключается из дальнейшей обработки, как уже поступившее на выход устройства, а число б - тэк кэк оно имеет равное ему число а, поступившее на информационный вход устройства с меньшим порядковым номером. Кроме того, единичный сигнал с прямого выходе триггера 3.2 поступает на третий вход первого элемента ИЛИ первой группы 4.1 после срабатывания триггера. Появление указанного сигнале приводит к тому, что ма всех входах элемента И 8.1 устанавливаются единичные сигналы, тэк как на выходе первого элемента ИЛИ первой группы 4,1 до сих пор присутствовал нулевой сигнал из-за поступления ма вго входы нулевых сигналов с выходов "Меньше" и "Равно" первого блока сравнения первой группы (так кэк эЬ). Это приводит к тому, что на выходе элемента И 6.1 появляется единичный сигнал, который, поступая нэ входы управления коммутаторами 9.1 и 10.1, открывает их, и на первый 15 и второй 16 выходы устройства поступают соответственно числа а (наибольшее из оставшихся чисел) и единичный код, сообщающий о количестве чисел в сортируемом массиве, равных а, соответственно, Этот же сигнал с выходе элемента И 8,1 поступает на 3-вход триггера 3,1 ичерез элементы ИЛИ-НЕ группы 7,2, 7,4 на входы элементов И группы 8.3 и 8.5 и блокирует выдачу остальных чисел на выходы устройства. Единичный сигнал с прямого выхода триггера 3.4 поступает на третьи входы первого элемента ИЛИтретьей группы 4.3, второго элемента ИЛИ.второй группы 4.2 и третьего элемента ИЛИпервой группы 4.1. Поступление указанно 5 го сигнала не изменяет состояния соответствующих элементов И 8.1, 8.2 и 8,3, таккак на выходе третьего элемента ИЛИ первой группы 4.1 и второго элемента второйгруппы 4.2 ранее уже был установлен еди 10 ничный сигнал, а появление единичногосигнала на выходе первого элемента ИЛИтретьей группы не влияет на состояние выходного сигнала элемента И 8.3, тэк как нэвыходе второго элемента ИЛИ этой группы15 остается нулевой сигнал. Поступлениемвторого тактового импульса на тактовыйвход 13 устройства завершается выдачавторого по величине числа а сортируемогомассиве, триггер 3.1 устанавливается в.20 единицу по заднему фронту этого импульса. и блокирует элемент И 8.1, нулевой сигнал свыходе которого закрывает коммутаторы 9 1и 10.1,Этот же сигнал с выхода элемента И 8.1,25 поступая на вход элемента ИЛИ-НЕ 7.4,приводит к появлению на его выходе единичного сигнала, который поступает на входпятого элемента И 8.5, на остальных входахкоторого щисутствуют единичные сигналы30 с выхода элемента НЕ 11.1(поскольку в массиве отсутствуют числа, равные числу е) иинверсного выхода пятого триггера 3.5, чтовызывает появление единичного сигнала навыходе этОго элемента. Появление единич 35 ного сигнала ма выходе элемента И 8.5 разрешает прохождение числа е на выход 15информации устройства через коммутатор9.5. При этом на выходе 16 количестве равных чисел устройства имеется нулевой код,40 поскольку во второй группе коммутаторов10 коммутатор 10.5 отсутствует, твк как число е поступает на последний 12.5 информационный вход устройства и, если бы оноимело в массиве равные себе числа. оно45 было бы обработано (заблокирован элементИ 8,5 срабатыванием триггера 3.5, кэк и причисла б в первом же такте работы устройства) ранее при обработке первого числа впервом такте работы,50 При поступлении третьего тактового импульса на вход 13 устройства срабатываеттриггер 3.5, что приводит к блокировке элемента И 8,5 и появлению единичного сигнала на третьем входе второго элемента ИЛИ55 третьей группы 4,3, Появление этого сигнале приводит к появлению на входе эле-мента И 8.3 единичного сигнала и,поскольку нэ остальные входы этого элемента единичные сигналы поданы раиее, нэего выходе появляется сигнал, разрешаю1737441 5 10 15 20 30 35 40 45 50 55 щий прохождение числа С через коммутатор 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" устройства, а во вгорую группу коммутаторов добавить коммутатор 10.п и его вход также подключить к шине "1" устройства, то на втором выходе устройства 16 формируется код общего количества чисел в массиве, имеющих значение числа, выдаваемого на первый, выход 15 устройства.Работа счетчика 2 заключается в том,что он подсчитывает количество единичных сигналов, поступающих на его входы 18.1- 18 лп и на выходах 19.1 - 19,(г+ 1) формирует сумму в двоичном коде. Формула изобретения Устройство для сортировки чисел, содержащее (и - 1) групп блоков сравнения, где и - количество сортируемых чисел, п - 2 счетчиков, и - 1 элементов НЕ и две группы коммутаторов, причем 1-я группа блоков сравнения, где 1 = 1, 2, , и - 1, содержит (и -) блоков сравнения, вход 1-го сортируемого числа устройства соединен с первыми входами блоков сравнения 1-й группы, вход (11)-го сортируемого числа устройства - с вторыми входами) - х блоков сравнения,(+ +1 - Д-й группы, где ) = 1, 2, 1, первые выходы блоков сравнения 1-й группы (1 1,2, , и - 2) соединены с входами 1-го счетчика, информационный вход М-го сортируемого числа устройства (с" 1, 2, ., и) соединен с информационным входом М -го коммутатора первой группы, управляющие входы 1-х коммутаторов первой и второй групп обьединены, выходы коммутаторов первой и второй групп соответственно объединены и являются соответственно первым и вторым информационными выходами устройства, первый выход первого блока сравнения первой группы соединен с входом перваго элемента НЕ, о т л и ч а ю щ -е е с ятем, что, с целью повышения быстродействия, в него введены и ЭК-триггеров, (п + 1) групп элементов ИЛИ, (и + 1) элементов И и (и - 1) элементов ИЛИ-НЕ, причем первый и второй выходы р-го блока сравнения 1-й группы, где р = 1, 2, , и - 1, соединены соответственно с первым и вторым входами р-го элемента ИЛИ 1-й группы, выход которого соединен с р-м входом 1-го элемента и, выход которого соединен с управляющим входом 1-го коммутатора первой группы и 1-ми входами всех элементов ИЛИ-НЕ с 1-го по (и - 1)-й, выход первого элемента И соединен с 1-входом первого 1 К-триггера, выход и-го элеме га И соединен суправляющим входом п-го коммутатора первой группы, выход(1+ 1)-го элемента И - с первым входом 1-го элемента ИЛИ и-й группы, выход которого соединен с 1-входом(1+ 1)-гоЗК-триггера, прямой выходпервого 1 К-триггера соединен с первым входом (и + 1)-го элемента И, выход которого является выходом окончания работы устройства. прямой выход(1+1)-го ЗК-триггера соединен с ( + 1)-м входом (и + 1)-го элемента И и с третьим входом )-го элемента ИЛИ (1+ 1- Д-й группы, инверсный выход М-го ЗК-триггера соединен с (и - К+ 1)-м входом К-го элемента И, выходы 1-х элементов НЕ и ИЛИ-НЕ соединены соответственно с(п + 1 -, 1)-м и (и + 2- - )-м входами (1 + 1)-го элемента И, г-й вход 1-го элемента ИЛИ (и+ 1)-й группы, где г" 1, 2, , 1+ 1, подключен к первому выходу (1 + 2 - г)-го блока сравнения г-й группы, первый выход первого блока сравнения первой группы соединен с вторым входом первого элемента ИЛИ и-й группы, выход 1-го элемента ИЛИ (и + 1)-й группы соединен с входом ( + 1)-го элемента НЕ и с вторым входом (1+ 1)-го элемента ИЛИ и-й группы, выход 1-го счетчика соединен с информационным входом 1-го коммутатора второй группы, первый выход блока сравнения (и - 1)-й группы соединен с информационным входом (и - 1)-го коммутатора второй группы, тактовый вход устройства соединен с входами синхронизации всех ЗК-триггеров, 1737441