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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (54)5 6 06 F 7/06

ГОСУДАРСТВЕ ННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4804685/24 (22) 26.03.90 (46) 30.05.92, Бюл. М 20 (71) Специальное конструкторское бюро

Харьковского производственного обьединения "Коммунар" (72)А.E. Горбель, Н.Ф.Сидоренко, Б.В,Остроумов и В,И,Петренко (53) 681.325.5(088.8) (56) Авторское свидетельство СССР

М 1107118, кл. 6 06 F 7/06, 1984.

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

М 1247860, кл. 6 06 F 7/06 1985. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ.ЧИСЕЛ

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

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

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

Наиболее близким к предлагаемому является устройство для сортировки чисел, соДержащее (п - 1) групп блоков сравнения двух чисел по (n - i 1) блоков в каждой Ы, 1737441 А1 (57) Изобретение относится к автоматике и вычислительной технике. Цель изобретения — повышение быстродействия, Устройство содержит блоки сравнения, счетчики, IKтриггеры, группы элементов ИЛИ, группу элементов ИЛИ-НЕ, группу элементов И, группы коммутаторов, элементы НЕ, информационные входы, тактовый вход, выход окончания работы, информационные выходы. БС сравнивают каждое чйсло с каждым счетчики подсчитывают количество равных чисел. I-Io каждому тактовому сигналу на один информационный выход устройства выдаются последовательно все числа в порядке убывания, а на другой информационный выход — количество этих чисел в массиве минус единица. 4 ил . группе {где i 2, 3, ..., n; п — количество чисел в массиве), п групп коммутаторов, и сумматоров и (и — 1) групп элементов НЕ, причем входы первого сравниваемого числа устройства соединены с первыми группами входов блоков сравнения первой группы и информационными входами коммутаторов первой группы, входы 1-го сравниваемого числа устройства соединены с первыми группами входов блоков сравнения i-й группы, информационными входами коммутаторов -й группы и вторыми группами входов i-x блоков сравнения р-х групп, где р = 1, 2„.„(i - 1), вход n-ro сравниваемого числа устройства соединен с информационными входами коммутаторов п-й группы. и вторыми группами входов (n - 1)-х блоков сравнения всех групп, выходы блоков сравнения каждой k-й группы (где k = 1, 2...„n-1), соединены с первой группой входов k-ro

1737441

35 мого числа устройства соединен с первыми входами блоков сравнения i-й группы, вход (! + 1)-го сортируемого числа устройства соединен с вторыми входами j-x блоков сравнения.(l + 1 - J)-й группы, где ) = 1, 2...„1, первые выходы блоков сравнения l-й.группы (I = 1, 2, ..., и - 2) соединены с входами I

-го счетчика, информационный вход k-го сортируемого числа устройства (k = 1, 2, ..., и), соединен с информационным входом k40 го коммутатора первой группы, управляющие входы l-x коммутаторов первой и второй групп обьединены, выходы коммутаторов первой и второй групп соответственно оеь|щинены по группам и являются соответствеино !ервым и вторым информационны- 50 ми выходами устройства, первой выход первого блока сравнения первой группы соединен с входом первого элемента НЕ, введены п J K-триггеров, (и + 1) групп злементов ИЛИ; (л + 1) элементов И и (n - 1) элементов ИЛИ-НЕ, причем первый и второй выходы р-го блока сравнения 1-й группы, где р -1, 2, ..., (n- 1), соединены соответственно с ущрвым. и вторым входами р-го элемента ,ИЛЙ I-й группы, выход которого соединен с сумматооа, выходы всех и сумматоров соединены с управляющими входами коммутаторов соответствующих групп, разрядные выходы J-х коммутаторов всех групп объединены (где ) 1, 2, ...; и) и подключены к J-м 5 выходам устройства, входы элементов HE (I - 1)-й группы соединены соответственно с выходами 1-х блоков сравнения р-х rpynn, а выходы элементов НЕ (1 - 1)-й группы подключены к второй группе входов I-ro сумма- 10 тора, Недостатком устройства является необходимость подсчета в упорядоченном массиве количества равных чисел, что требует дополнительных временных и аппаратур- 15 ных зат т, Цель изобретения — повышение быстродействия устройства при сортировке числоего массива, содержащего некоторое количество равных чисел, за счет формиро- 20 вания иа выходе устройства значения чисел в порядке их убывания в сопровождении числа, ощуеделяющего количество чисел в сортируемом массиве, равных числу, выдаваемому в текущем такте работы устройст- 25 . ва, Поставленная цель достигается тем,.что в устройство для сортировки чисел, содержащее (n - 1) групп блоков сравнения, где и — количество сортируемых чисел, (n - 2) ЗО счетчиков, (n - 1) элементов HE и две группы коммутаторов, причем I-я группа блоков сравнения, где l - 1, 2, ..., (п - 1), содержит (n - !) блоков сравнения, вход 1-го сортируер-м входом I-го элемента И, выход которого соединен с управляющим входом 1-ro ком-. мутатора первой группы и I-ми входами всех элементов ИЛИ-НЕ с 1-го no (n - 1)-й, выход первого элемента И соединен с Jвходом первого JК-триггера, выход и-го элемента И соединен с управляющим входом n-ro коммутатора первой группы, выход(1+ 1)-ro элемента И соединен с первым входом I-ro элемента ИЛИ и-й группы, выход которого соединен с 3-входом (I + 1)-го

JK-триггера, прямой выход первого JKтриггера соединен с первым входом(п+ 1)-ro элемента И, выход которого является выходом окончания работы устройства, прямой выход (l + 1)-го JK-триггера соединен с (! +

1}-м входом (и+ 1)-го элемента И и с третьим входом j-го элемента ИЛИ (! + 1 - J}-й группы, инверсный выход k-ro JK-триггера сое-. динен с (n - k+ 1)-м входом k-го элемента И, выходы 1-х элементов НЕ и ИЛИ-HE соединены соответственно с (и + 1 - j)-м и (n + 2- -1)-м входами (! + 1)-ro элемента И, г-й вход 1-го элемента ИЛИ (и+ 1)-й группы, где

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

Кроме того, счетчик содержит(в -1), где

rn — разрядность счетчика. разделенных на

1 групп r-разрядных сумматоров (г = 1, 2, ..., 1), по (— ) сумматоров в каждой группе, 2 причем входы счетчика с первого по в-й подключены к входам слагаемых однораз-. рядных сумматоров первой группы в произвольном порядке, выходы суммы и переноса каждого из сумматоров 1-й группы (! = 1, 2, ..., (l - 1) подключены к соответствующим разрядам одного из входов слагаемого одного из сумматоров (i + 1)-й группы, выходы суммы и переноса сумматора I-й группы являются разрядами выхода счетчика.

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

15

40

50 ния второй группы 1,2.

55 сиве одновременно с выдачей первого числа иэ каждой группы равных чисел на выходы устройства, что приводит к повышению

его быстродействия.

На фиг. 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 — 3 и приводятся в исходное состояние. Затем на входы 12.1 — 12.п информации одновременно поступают сортируемые числа. Допустим n = 5. Пусть на входы информации устройства с первого 12.1 по пятый

12.5 поступили соответственно числа а, Ь, с, d и е, которые соотносятся между собой следующим образом

b>a=d>e>c. (1)

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

На выходах блоков сравнения первой группы устанавливают следующие сигналы.

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

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

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

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

На входах первого элемента И 8;1 присутствуют единичные сигналы с инверсного выхода триггера 3.1 и с выходов всех элементов ИЛИ первой группы, кроме первого, на выходе которого присутствует нулевой сигнал, который приводит к тому, что нулевой сигнал с выхода элемента И 8,1 запрещает прохождение сигналов на выходы первых коммутаторов 9.1 и 10,1 первой и второй групп соответственно, На первый коммутатор первой группы 9,1 поступает число а, а на первый коммутатор второй группы 10;1 — число, определяющее количество чисел в массиве, равных числу а. Так как а = d, то на входы счетчика 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 вызывает появление единичного сигнала на выходе этого элемента, который поступает на J-вход второго триггера

3,2 через элемент ИЛИ 5.1 и на входы управления коммутаторами 9,2 и 10,2, На входы коммутатора 9.2 поступает число b с входа 12.2 устройства, а на входы коммутатора 10.2 — нулевой код количества равных чисел со счетчика 2.2, поскольку а сортируемом массиве нет чисел, равных Ь, и на входы счетчика поступают нулевые сигналы с выходов "Равно" всех блоков сраанеНаличие единицы на входе управления коммутаторами 9,2 и 10.2 разрешает прохождение на его выход и, следовательно, на первый выход 15 устройства числа Ь, которое является наибольшим в массиве сорти1737441 руемых исел. в на второй выход 16 поступает нулевой код. Выходы остальных коммутаторов закрыты нулевыми сигналами с выходов соответствующих элементов ИЛИНЕ 7.2-7.4, поскольку на входы указанных элементов поступает единичный сигнал с выхода элемента И 8.2. Так как на выходе

"Равно" третьего блока сравнения первой группы 1.1 присутствует единичный сигнал, поскольку а - б, то через элементы ИЛИ второй 6.2 шестой группы и третий 5.3 пятой группы он поступает íà J-вход четвертого

3,4 триггера, а на J-входах остальных (третьего 3,3 и пятого 3,5) триггеров имеется нулевой сигнал. По заднему фронту первого тактового импульса нв тактовом входе 13 устройства, KoropblA поступает на С-входы всех триггеров, второй 3,2 и четвертый 3.4 триггеры устанавливаются в единичное состояние, е на входы элементов И 8.2 и 8,4 поступает нулевой сигнал с инверсных выходов этих триггеров, вследствие чего на выходе элемента И 8.2 появляется также нулевой сигнал, запрещающий прохождение сигналов через коммутаторы 9.2 и 10.2 на первый 15 и второй 16 выходы устройства, а элемент И 8.4 так же блокируется и число Ь исключается из дальнейшей обработки, как уже поступившее на выход устройства, а число б — так как оно имеет равное ему число а. поступившее на информационный вход устройства с меньшим порядковым номером. Кроме того, единичный сигнал с прямого выходе триггера 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. Поступление указанно5 го сигнала KB изменяет состояния соответствующих элементов И 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 поскольку во второй rpynne коммутаторов

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

45 было бы обработано (заблокирован элемент

И 8,5 срабатыванием триггера 3.5. как и при числа б в первом же такте работы устройства} ранее при обработке nepsoro числа в первом такте работы.

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

55 третьей группы 4.3. Появление этого сигнала приводит к появлению на входе эле- мента И 8.3 единичного сигнала и, поскольку на остальные входы этого элемента единичные сигналы поданы раиее, на его выходе появляется сигнал. разрешаю1737441

10

20

55 щий прохождение числа С через коммутатор

9,3 на выход информации 15 устройства.

При этом на выходе количества чисел 16 устройства имеется нулевой код, поскольку на вход коммутатора 10.3 поступает нулевой

"сигнал с выхода счетчика 2.3.

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

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

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

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

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

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

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

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

Устройство для сортировки чисел, содержащее (и - 1) групп блоков сравнения, где и — количество сортируемых чисел, n - 2 счетчиков, n - 1 элементов НЕ и две группы коммутаторов, причем l-я группа блоков сравнения, где i = 1, 2, ..., n - 1, содержит (n - I) блоков сравнения, вход I-го сортируемого числа устройства соединен с первыми входами блоков сравнения I-й группы, вход (i 1)-го сортируемого числа устройства — с вторыми входами j - х блоков сравнения,(l+

+1 - Д-й группы, где l = 1, 2, .„, I, первые выходы блоков сравнения -й группы (I 1, 2, ..., n - 2) соединены с входами I-го счетчика, информационный вход k-го сортируемого числа устройства (k - 1, 2, „.. n) соединен с информационным входом k -го коммутатора первой группы, управляющие входы I-x коммутаторов первой и второй групп обьединены, выходы. коммутаторов первой и второй групп соответственно объединены и являются соответственно первым и вторым информационными выходами устройства, первый выход первого блока сравнения первой группы соединен с входом перваго элемента НЕ, о т л и ч а ю щ— е е с я тем, что, с целью повышения быстродействия, в него введены n JK-триггеров, (ni

+ 1) групп элементов ИЛИ, (n + 1) элементов

И и (n - 1) элементов ИЛИ-НЕ, причем первый и второй выходы р-го блока сравнения

I-й группы, где р = 1, 2, ..., и - 1, соединены соответственно с первым и вторым входами р-го элемента WIN i-й группы, выход которого соединен с р-м входом )-го элемента и, выход которого соединен с управляющим входом )-го коммутатора первой группы и

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

nepsoA группы, выход(1+ 1)-го элемента И— с первым входом I-ro элемента ИЛИ п-й группы, выход которого соединен с 4-входом(}+ 1)-го JK-триггера, прямой выход первого JK-триггера соединен с первым входом (n + 1)-го элемента И, выход которого является выходом окончания работы устройства. прямой выход(1+ 1)-ro JK-триггера соединен с (! + 1)-м входом (и + 1)-го элемента И и с третьим входом j-го элемента ИЛИ (1+ 1- Д-й группы, инверсный выход k-ro JK-триггера соединен с (n - k+ 1)-м входом k-ro элемента

И, выходы I-х элементов HE и ИЛИ-НЕ соединены соответственно с(п + 1 -, i)-м и (и + 2- I)-м входами (i + 1)-го элемента И, r-й вход

I-ro элемента ИЛИ (и+ 1)-й группы, где г" 1, 2, ..., 1+ 1, подключен к первому выходу {! +

«2 - rj-го блока сравнения r-й группы, первый выход первого блока сравнения первой группы соединен с вторым входом первого элемента ИЛИ и-й группы, выход I-ro элемента ИЛИ (n + 1)-й группы соединен с входом (t + 1)-го элемента НЕ и с вторым входом (1+ 1)-го элемента ИЛИ и-й группы, выход I-ro счетчика соединен с информационным входом I-ro коммутатора второй группы, первый выход блока сравнения (и - 1)-й группы соединен с информационным входом (n - 1}-го коммутатора второй группы, тактовый вход устройства соединен с входами синхронизации всех J К-триггеров, 1737441

1737441

1737441

1737441 ° °

ВЮФ Ю Ю.1.

Е J ) Заказ 1892 Т и р а ж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

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

Производственно-издательский комбинат "Патент", г, Ужгород, ул.Гагарина, 101 — -3

Составитель А. Горбель

Редактор Л. Пчолинская Техред М.Моргентал Корректор M. Демчик

ФЮ. 1

ФУ. Х

4Р,Ь

49. 2

Ф (i r)