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

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано при реализации технических средств ЭВМ и создании устройств обработки статистической информациИо Цель изобретения - повышение быстродействия. Устройство содержит т-разрядные регистры 1, группы элементов И 3-5, 7,8 группу элементов ИЛИ 6, группы элементов запрета 9, 10, группу триггеров П, элемент 12, cдвигaющi й регистр 13, группы элементов задержки 15, 16, группу дифференцирующих элементов 17. Устройство реализует принцип упоря дочивания чисел по возрастанию с разбиением исходного ряда на 2 подгруппы с каждым циклом сравнения (i номер цикла) и последукшщм одновременным упорядочиванием чисел в каждой подгруппе, что обеспечивает полное упорядочивание чисел за однократный просмотр их разрядов. 1 ил IS. с ( (Л

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

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

РЕСПУБЛИК (19) 07) А1 цу 7 С 06 F 7/06

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4244327/24-24 (22) 13.05.87 (46) 23.11.88. Вкп. У 43 (72) В.П.Фролов и Т.А.Миронова (53) 381.325 (088,8) (56) Авторское свидетельство СССР

Р 876339, кл. G 06 F 7/06, 1979. Авторское свидетельство СССР

Ф 1001083 кл. G 06 F 7/06 1981. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано при реализации технических средств ЭВМ и создании устройств обработки статистической информации. Цель изобретения — повышение быстродействия. Устройство содержит m-разрядные регистры 1, группы элементов И 3-5, 7,8, группу элементов ИЛИ 6, группы элементов запрета 9, 70, группу триггеров 17, элемент 12, сдвигающий регистр 13, группы элементов задержки 75, 16, группу дифференцирующих элементов 17.

Устройство реализует принцип упорядочивания чисел по возрастанию с разбиением исходного ряда на 2 подгруппы с каждым циклом сравнения (iномер цикла) и последующим одновременным упорядочиванием чисел в каждой подгруппе что обеспечивает полФ с ное упорядочивание чисел за однократный просмотр их разрядов. 1 ил.

1 1439576 :?

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

Цель изобретения --повышение быст родействия устройства.

На чертеже представлена блок-схе- 1О ма устройства.

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

:регистры 1, -1ц, группу входных зле;ментов ИЛИ 2, группу элементов И 3, записи, группу элементов И 4 перезаписи, группу элементов И 5 анализа, группу элементов ИЛИ 6, первую и. вторую группы элементов И 7 и 8, первую и вторую группы, элементов 9 и 10 ,запрета, группу триггеров 11, .эле мент ИЛИ 12, сдвигающий регистр 13, : элемент 14 задержки, первую и вторую .группы элементов !5 и 16 задержки, группу дифференцирующих элементов 17, третью группу элементов 18 задержки, 25 . вход 19 запуска устройства и выход, :20 окончания сортировки устройства.

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

В исходном состоянии триггеры

11< 11 находятся в единичном сос тоянии, открывая по одному из входов, все элементы И 8, -8я, . В регистры, 1 -1ц записываются упорядочиваемые

;числа (входы записи не показаны),, после чего на вход 19 устройства поступает сигнал запуска. Этот сигнал через элемент ИЛИ 12 поступает на . элемент 14 задержки, одновременно устанавливая первый разряд сдвигающего регистра 13.в единичное состояние. Сигнал с выхода первого разряда регистра 13 открывает по одному из входов элементы И 5 ц -5 щ, подключенные к первым (старшим) разрядам *каждого регистра 1< -1)I . Начинается сравнение вьделенных разрядов. Их значения через открывающиеся элементы И 5н -5,я поступают на входы элементов ИЛИ б -6» . С выхода элемента ИЛИ 61 непосредственно, а с выходов элементов ИЛИ 6» -6 1- через элементы 18 -.18» g задержки сигналы поступают на входы элементов

И 7, -7q и запрещающие входы элементов 9, -9q запрета соответствующих им регистров. Одновременно сигналы с выходов элементов 18 i -18н-i задержки поступают на информационные и запрещающие входы соответственно элементов 9 I -9 N, и 10, -10„, запрета которые относятся к регистрам, предназначенным для записи больших по значению чисел — старшим регистрам (в регистр 1 записывается наибольшее из упорядочиваемых чисел, а в регистр 1 — наименьшее. Сравнение выделенных разрядов двух соседних регистров 1 -1 q происходит на элементе 9 -9 ц запрета старmего регистра. В случае, если значения сравниваемых разрядов равнозначны, т.е. в двух соседних регистрах выделенные разряды равны, то на выходе элемента 9 -9 u запрета сигнал отсутствует, так как на его входах одинаковые либо единичные, лйбо нулевые сигналы. Это будет и в случае, если в старшем регистре значение выделенного разряда равно 1, а в младшем — 0, так как элемент

9 -9 „,, запрета относящийся к старшему разряду, закрыт.

В случае, если значение сравниваемого разряда старшего регнстра равно О, а значение этого же разряда младшего регистра равно 1, т.е. в мяадшем регистре записано большее по значению число, то единичный сигнал с выхода элемента ИЛИ 6 —

6 @ младшего разряда через открытый элемент 9, -9 g < запрета старшего

I разряда поступает на вход соответствующего ему элемента И8 -8 1, открытого по второму входу триггером

11 -11 < . Сигнал с выхода открывающего элемента И 8 -8 к старшего регистра поступает на входы элемен- тов И 3, -3 „, и элементов И 4«

4 „ старшего и младшего регистров соответственно, разрешая перезапись значений находящихся в них чисел.

Значения разрядов регистров через открытые элементы И 3, -3 „,„ и

4 п -4 „ поступают на элементы

15„-15 „, и 16., -16„„„задержки соответственно и запоминаются на них на время, необходимое для обнуления регистров 1 -1 ц . Обнуление регистров 1, -1„, участвующих в перезапи- ° си чисел, осуществляется по входам

I сброса импульсом copocaó формирующимся дифференцирующим элементом 17 17 р, по переднему фронту сигнала, поступающего с элемента И 8 q -8р < .После обнуления регистров большее

1439576 . по значению число, хранящееся в младшем регистре, через элементы

ИЛИ 2 « -2„„,, записывается в старший регистр, а меньшее — наоборот. Процесс перезаписи чисел продолжится . до тех пор, пока в двух соседних регистрах встречается комбинация значений сравниваемых разрядов 01„ т.е. все числа, значащее значение сравниваемого разряда которых равно 1, сдвигаются в старшие регистры устройства (начиная с регистра 1, ), а со значением сравниваемого разряда, равным 0; - в младшие регистры.

Для исключения сбоев устройства при ,обнулении регистров 1< -11 служат элементы 18, -18 „, задержки>обеспечивающие задержку сигналов на время, достаточное для перезаписи чи-сел из регистра в регистр. По окончании перезаписи чисел в регистрах

1, -1 записаны числа с 1 в сравниваемом разряде, а в регистрах

1„ - 1» — с нулевым значением сравниваемого разряда.

Единичный сигнал с выхода К-ro элемента ИЛИ 6„ поступает на один из входов К-го элемента И 7„, на другой вход которого поступает сигнал с выхода элемента 14 задержки.

Время задержки сигнала элементом 14 . выбрано таким, что успевают за кончиться все процессы перезаписи чисел в регистрах 1< »111 . Счгнал с выхода элемента 14 задержки через элемент ИЛИ 12 сдвигает 1 в сдвигающем регистре 13 в следующий разряд, одновременно устанавливая триггеры 11 в нулевое состояние через открывшййся элемент И 7„ и открытый нулевым сигналом с выхода элемента

ИЛИ 6„+, элемента 10„ запрета.

Тем самым блокируется элемент И 8„, запрещая до конца работы устройства перезапись чисел между регистрами

1х и 1к, независимо от значений сравниваемых разрядов записываемых

В ННх чисело

Сигнал с выхода второго разряда сдвигающего регистра 13 открывает элементы И 5 < -5 < всех регистров, после чего начинается цикл сравнения вторых разрядов упорядочиваемых чисел.

Цикл сравнения и перезаписи чисел между регистрами повторяется, только теперь упорядочивание чисел по значению второго разряда происходит в

Устройство для сортировки чисел, содержащее распределитель управляющих сигналов, элемент задержки, элемент ИЛИ, N регистров, где К вЂ” количество сортнруемых чисел, первую и вторую группы элементов И, К групп

35 элементов И анализа по ш элементов

И анализа в каждой группе, где ш— количество разрядов сортируемых чисел, N-1 групп элементов И записи

40 m элементов И записи s каждои группе

Ы-1 групп элементов И перезаписи ш элементов И перезаписи в каждой группе, группу элементов ИЛИ, N-2 групп входных элементов ИЛИ, первую и вто45 рую группу элементов задержки. rpyIIлу триггеров причем выход каждого триггера группы соединен соответст- венно с первым входом элемента И первой группы, выход -ro входного эле.мента ИЛИ Р-й группы, где К 1,- ш, Р=1,...N-2, соединен соответственно с К-м информационным входом (Р+1)-ro регистра, выход К-го регистра i-го регистра, где i=1,...,N, соединен соответственно с первым входом К-го элемента И анализа д-й группы, выход

К-го элемента И анализа i группы соединен с К-м входом i-го элемента

KIH группы, о т л к ч а ю щ е е с я

20 двух группах регистров 1< -1 „ н

1 „„- 1 K так как перезапись чисел между К-м и (К+1)-м регистрами запрещена. Следующим сигналом с выхода элемента 14 задержки в нулевое состояние сбрасываются по крайней мере еще два триггера 11 -11 q, (ло одному в каждой подгруппе регистров .1 и 1„+< -1, и так далее. После сравнения последнего разряда чисел на выходе 20 сдвигающего регистра 13 появляется сигнал об окончании процесса упорядочивания чисел. Прн этом наибольшее число записано в регистре

1,, а наименьшее — в регистре 1 .

Таким образом, устройство реализует принцип упорядочивания чисел по возрастанию с разбиением исходного ряда на 2 подгруппы с каждым циклом сравнения (i — номер цикла) и последующим одновременным упорядочиванием чисел в каждой подгруппе, что обеспечивает полное упорядочиванне чисел за однократный просмотр их разрядов.

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

Составитель В.Козлов

Техред A.Кравчук Корректор М.Максимишинец

Редактор О.Юрковецкая

Заказ 6077/47 . Тираж ?04 Подписное

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

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

Производственно-полиграфическое предприятие, r. Ужгород, ул, Проектная, 4

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

1 динен с первым входом элемента ИЛИ., выход которого соединен с входом сдвига .сдвигающего регистра и через элемент задержки с вторым входом элемента ИЛИ и первым входом j--го элемента И второй группы, где =1..., N-1, выход которого соединен с информационным входом j-го элемента запрета первой группы, выход которого соединен с входом установки. в "О"

i-го триггера, выход первого элемен-! та ИЛИ группы соединен с. вторым входом первого элемента И второй группы и с запрещающим входом первого элемента запрета второй группы, выход (j+1)-го элемента ИЛИ группы соединен через соответствующий элемент задержки первой группы с запрещающим входом (j+1)-го элемента запрета первой группы и с информационным входом

j-го элемента запрета. второй группы, выход Р-го элемента задержки первой

rpyama соединен с вторым входом (Р+t)-го элемента И второй группы и с запрещающим входом (Р+1)-го элемента запрета второй группы, выход

j-го элемента запрета второй группы соединен с вторым входом j-го элеl

39576 6 мента И первой группы, выход которого соединен с управляющими входами К элементов И записи и перезаписи

j-х групп и через j-й дифференцирующнй элемент с входами установки в

"О" (j-го и (j+1)-ro регистров, К-й выход j-го регистра соединен с информационным входом (К-го элемента

И записи j-й группы, К-й выход (1+1)го регистра соединен с информацион« ным входом К-ro элемента-И перезаписи j-й группы, выход К-го элемента

И Р-й группы соединен через соответствующий элемент задержки второй группы с первым входом К-го входного элемента ИЛИ P-й группы, вьиод

К-го элемента И записи (Я-1)-й группы соединен через соответствующий ро элемент задержки второй группы с (К-м информационным входом Б-го регистра, выход К-го элемента перезаписи (Р+2)-й группы соединен через соответствующий элемент задержки

25 третьей группы с вторым входом К-го входного элемента ИЛИ Р-й группы, выход К-го„ элемента И перезаписи второй группы соединен через соответствующий элемент задержки третьей

ЗО группы с К-и информационным входом первого регистра, К-й выход сдвигающего регистра соединен с вторыми входами К-х элементов И анализа i-x групп, выход старшего разряда сдви гающего регистра является выходом окончания сортировки устройства.