Устройство для сортировки мк-разрядйопшс!

 

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

Соцмапмстмческмк

Респубпми

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ. СВИДЕТЕЛЬСТВУ

«ii826340 (6l ) Дополнительное к авт. свид-ву (22) Заявлено 19. 12. 79 (21) 2855736/18-24 (SI )M. Кл.

G 06 F 7/08 с присоединением заявки М (23) ЙеуАвретвеииый кемитет

СССР

П риоритет

Опубликовано.30.04,81, Бюллетень М 16 (53) УДК 681..325. . .5 (088.8) ао двием изобретений и еткрытий

Дата опубликования описания 04.05.81 (72) Авторы изобретения

В. М. Верченко, В. И. Дроздов и В; Г.. Калашников

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

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

Однако это устройство сложно и требует для своей реализации больших аппаратурных затрат.

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

Недостатком этого устройства является его сложность.

Цель изобретения — упрощение устройства.

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

3 82634 группы, выход каждого j-го из которых подключен к первому входу j-го элемента ИЛИ группы, где j = 1,2,...,n, выход каждого из которых соединен со входом 3-го разряда первого регистра

5 выходы а-го регистра подключены ко входам второй группы схемы сравнения и к информационным входам элементов И второй группы, выход каждого j-го из которых соединен со вторым входом 10

j-ro элемента ИЛИ группы, выход. элемента равнозначности подключен к управляющим входам элементов И первой группы и через элемент НŠ— к управляющим входам элементов И второй груп- 15 пы.

На чертеже представлена функциональная схема устройства.

Устройство содержит шп-разрядных

20 регистров 14 -!, регистр 2 результата, схему 3 сравнения, элемент 4 равнозначности,элемент НЕ 5, группы элементов И 61-61 и 74 -7и, группу эле" ментов ИЛИ 84-8>, элемент И 9, управляющую шину 10, шину 11 тактовых сигналов.

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

30 . При сортировке чисел в порядке убывания в начале работы все разряды регистра 2 результата устанавливаются в единичное состояние (цепи начальной установки регистра 2(на чертеже

3S не показаны) и на управляющую шину 10 подается .единичный потенциал. Затем в регистры 14 -l заносится массив исходных чисел и после этого устройство готово к работе. Число, записанное в

40 регистр 1, сравнивается с содержимым регистра 2 результата схемой 3 сравнения. В качестве схемы 3 сравнения может использоваться любая известная схема для сравнения двух и-разрядных чисел. Если в результате сравнения число, записанное в регистре !, оказывается меньше числа, находящегося в регистре 2 результата,. то на выходе схемы 3 сравнения по"

50 является единичный потенциал,. по,которому элемент 4 равнозначности разрешает прохождение тактового сигнала записи через элемент И 9 на вход записи регистра 2 результата, прохождение информации с выходов регистра 2 результата через вторую группу элементов И 74 -71, и запрещает через элемент НЕ 5 прохождение информации с

0 4 выходов регистра 1 через первую группу элементов И 6< — 6<.

Тактовый сигнал, поступающий с шины 11, переписывая содержимое регистра 2 результата (единичный. вектор) через группы элементов И 7 -7 и

ИЛИ 8 -8> в регистр 1, а содержимое регистров 14 -1 последовательно переписывает из каждого предыдущего в .последующий регистр, причем содержимое последнего регистра 1 заносится в регистр 2 результата. Если при очередном сравнении содержимое регистра 11 вновь становится меньше содержимого регистра 2, то по следующему тактовому сигналу с шины 11 повторяется перезапись чисел из регистра в регистр, как было указано.

Если при сравнении чисел оказывается, что содержимое регистра 11 больше или равно содержимому регистра 2 результата, то на выходе схемы 3 сравнения появляется нулевой потенциал и элемент 4 равнозначности запрещает прохождение через элемент И 9 тактового сигнала записи на регистр 2 результата, прохождение информации с регистра 2 результата через вторую группу элементов И 7 -7 и разрешает через элемент НЕ 5 работу первой группе элементов И 6 -б

4 И

Поступающий тактовый сигнал, воздействуя только на входы записи регистров 1,„ -1, переписывает содержимое регистра 1 через группы элементов

И 6 -6> и ИЛИ 8А-8 в регистр 1, а содержимое регистров 14 -1;последовательно переписывает из каждого предыдущего регистра в каждый последующий и в регистр 1, заносится новое число для сравнения с содержимым регистра 2 результата, которое за время действия такта остается неизменным.

Как видно, в зависимости от результата сравнения содержимого регистра 2 результата и регистра 1 „, перезапись чисел массива проводится через группу элементов И 6„ -6> или группу И

74 -7н и после каждого тактового сигнала в регистре 2 результата остается меньшее из сравниваемых чисел.

Через m тактовых сигналов регистр 2 результата содержит минимальное число массива, а в регистре 11 находится единичный вектор, при этом на выходе схемы 3 сравнения присутствует нулевой потенциал.

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

5 82634

Для того, чтобы переписать минимальное число массива в регистр 1! и продолжить сортировку чисел, на управляющую шину 10 подается нулевой потенциал, соответствующий в данном случае записи в регистр 2 результата большего из двух сравниваемых чисел.

Тогда схема равнозначности 4 разрешает прохождение тактового сигнала на регистр 2 результата, а его содержи- !р мому — через элементы И 7! -7! на элементы ИЛИ 8 -8и. При поступлении очередного (m+1) тактового сигнала минимальное число массива из регистра 2 результата переписывается в регистр 11, а единичный вектор из регистра 1!,, — в регистр результата. На шине 10 вновь устанавливается единичный потенциал и на этом заканчивается первый цикл сортировки чисел. По вы- щ полнению (m-1)-го циклов исходные числа массива располагаются в регистрах 1 -1 „ в порядке убывания, начиная с регистра 1!.

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

Порядок сортировки чисел по возрастанию аналогичен сортировке чисел по убыванию, но за счет инвертирования по отношению к предыдущему случаю сигнала, подаваемого на шину 10 управления, в данном случае больше из сравниваемых чисел, записанных в регистре 2 результата и регистре 1 я, после тактового сигнала остается в 40 регистре результата, а меньшее переписывается в регистр l< через группу элементов И 6! -6 или группу элементов И 7! -7п.

После поступления м-го тактового 4s сигнала регистр 2 результата содержит максимальное число массива, а регистр 1 — нулевой вектор.

Для того, чтобы перезаписать максимальное число массива в регистр и продолжить сортировку чисел, на управляющую шину 10 подается единичный потенциал, соответствующий в этом случае записи в регистр 2 результата меньшего из двух сравниваемых чисел. Схема равнозначности разрешает очередному (в+!)-му тактовому сигналу

0 6 переписать содержимое регистра 2 ре зультата в регистр 1, а нулевой век-! тор из регистра 1 „ — в регистр результата.

На шине 10 вновь устанавливается нулевой потенциал и на этом заканчивается первый цикл сортировки. По выполнению (m-1)-го циклов исходные числа массива располагаются в регистрах

1„,-1 „ в порядке возрастания, начиная с регистра 1!».

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

Устройство для сортировки mn-разрядных чисел, содержащее регистров, элементы И, НЕ, элемент равнозначности, две группы элементов И, схему сравнения, группу элементов ИЛИ, причем выходы регистра результата соединены со входами первой группы схемы сравнения, выход которой подключен к первому входу элемента равнозначности, выход которого соединен с первым входом элемента И, выход которого соединен со входом управления регистра результата, о т л и ч а ю щ е— е с я тем, что, с целью упрощения устройства, в нем выходы каждого i-ro регистра, где i = 1,2... °,(m-1) подключены ко входам (i+1}-го регистра, выходы m-го регистра соединены со входами регистра результата, выходы которого подключены к информационным входам элементов И первой группы, выход каждого j-ro из которых подключен к первому входу j-ro элемента ИЛИ группы, где j 1,2,...,n, выход каждого из которых соединен со входом 1-го разряда первого регистра, выходи m-ro регистра подключены ко входам второй группы схемы сравнения и к информационным входам элементов И второй группы, выход каждого j-го из которых соединен со вторым входом

1-ro элемента ИЛИ группы, выход элемента равнозначности подключен к управляющим входам элементов И первой группы и через элемент НŠ— к управ7 826.340 ляющим входам элементов И второй группы .!, Авторское

В 263277, кл. G

2. Авторское

Источники информации, Ф 637810, кл. G принятые во внимание при экспертизе тотип).

8 свидетельство СССР

06 F 7/00, 1968, свидетельство СССР

06 Р 7/00, 1976 (проЗаказ 2516 70 Тираж 745

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

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

Подписное

Филиал ППП "Патент", r. Ужгород, ул. Проектная, 4

Составитель B. Белкин

Редактор С. Шевченко ТехредМ.Коштура Корректор Г. Решетник