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

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

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

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

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

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

В исходном состоянии триггеры 11, -1 Ц , находятся в единичном состоянии, открывая по одному из входов се элементы И 8 , -8ц-« . В регистры 1, 1 записываются упорядочиваемые исла (входы записи не показаны), осле чего на вход 19 устройства поступает сигнал запуска. Этот сигнал через элемент ИШ 12 поступает на элемент 14 за,п;ержки, одновременно устанавливая первый разряд сдвигающего регистра 13 в единичное состояние. Сигнал с выхода первого разряда регистра 13 открывает по одному из входов элементы И , под- клкченные к первым (старшим) разрядам -каждого регистра Ь -li/ .Начинается сравнение вьщеленных разрядов. Их значения через открывающиеся элементы И 5«, -5,щ поступают на входы элементов ИЛИ 6, -6« . С выхода элемента ИЛИ 6| непосредственно, а с выходов элементов ИЛИ 6 6н-1 - через элементы 18, г18|,г задержки сигналы поступают на входы элементов И 7 -7ц.1 и запрещающие входы элементов 9, -9м-« запрета соответству- кйцих им регистров. Одновременно сигналы с выходов элементов 18 i -18н-(|

s 0 5

0

5

0

5

0

5

задержки поступают на информационные и запрещающие входы соответственно элементов 9, -9(,, и 10, -10„, запрета которые относятся к регистрам, предназначенным для записи больших по значению чисел - старшим регист- i рам (в регистр 1( записьгоается наибольшее из упорядочиваемых чисел, а в регистр 1 - наименьшее. Сравнение вьщеленных разрядов двух соседних регистров 14 -1 ц происходит на элементе 9( -9 запрета старшего регистра, В случае, если значения сравниваемых разрядов равнозначны, Тое, в двух соседних регистрах выделенные разряды равны, то на выходе элемента 9« -9 M-I запрета сигнал отсутствует, так как на его входах одинаковые либо единичные, либо нулевые сигналы. Это будет и в случае, если в старшем регистре значение вьделенного разряда равно 1, а в младшем - О, так как элемент 9( 9к-| запрета относящийся к старшему разряду, закрыт

В случае, если значение сравниваемого разряда старшего регистра равно О, а значение этого же разряда младшего р1егистра равно 1, т,е, в младшем регистре записано большее по значению число, то единичный сигнал с выхода элемента ИЛИ 6 - 6 HJ младшего разряда через открытый элемент 9( 9 и, запрета старшего разряда поступает на вход соответствующего ему элемента ИВ -8 N-I , открытого по второму входу триггером 11 ( -t1)(-( о Сигнал с выхода открьшаю- щего элемента И 8j -8 к-« старшего регистра поступает на входы элемен- тов И 3, 3h)«-( элементов И 4, - 4 старшего и младшего регистров соответственно, разрешая перезапись значений находящихся в них чисел. Значения разрядов регистров через открытые элементы И З, -3 и 4 «2 -4 «,« поступают на элементы 15„ -15„ „., и 16., -16„„ задержки соответственно и запоминаются на них на время, необходимое для обнуления регистров Ь -tч . Обнуление регистров 1, -1н , участвугадих в перезапи- си чисел, осуществляется по входам сброса импульсом сброса, формирующимся дифференцирующим элементом 17 - 17н-, по переднему фронту сигнала, поступающего с элемента И 84 -8и-г После обнуления регистров большее

по значению число, хранящееся в младшем регистре, через элементы ИЛИ 2, ., записывается в старший регистр, а меньшее - наоборот. Процесс перезаписи чисел продолжится до тех пор, пока в двух соседних регистрах встречается -комбинация значений сравниваемых разрядов 01, т.е. все числа, значащее значение сравниваемого разряда которых равно 1, сдвигаются в старшие регистры устройства (начиная с регистра 1, ), а со значением сравниваемого разряда, равным О, - в младшие регистры. Для исключения сбоев устройства при .обнулении регистров 1 -Ijj служат элементы 18 -18(|., задержки обес- печивакяцие задержку сигналов на время, достаточное для перезаписи чи- - сел из регистра в регистр. По окончании перезаписи чисел в регистрах 1 , -1 и записаны числа с 1 в сравниваемом разряде, а в регистрах 1ц- 1ц - с нулевым значением сравниваемого разряда.

Единичный сигнал с выхода К-го элемента ИЛИ 6 поступает на один из входов К-го элемента И 7, , на другой вход которого поступает.сигнал с выхода элемента 14 задержки. Время задержки сигнала элементом 14 выбрано таким, что успевают закончиться все процессы перезаписи чисел в регистрах - , Сигнал с выхода элемента 14 задержки через элемент ИЛИ 12 сдвигает 1 в сдви- гакхцем регистре 13 в следующий разряд, одновременно устанавливая триггеры 11 в нулевое состояние через открьшшийся элемент И 7 и открытый нулевым сигналом с выхода элемента ИЛИ 6к4) элемента 10ц запрета. Тем-самым блокируется элемент И 8 запрещая до конца работы устройства перезапись чисел между регистрами

U и 1

KVI

независимо от значений

сравниваемых разрядов записываемых в них чисело

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

чиселФ

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

двух группах регистров 1« -1 ц 1к+1 IN так как перезапись чисел между К-м и (К+1)-м регистрами запрещена. Следующим сигналом с выхода элемента 14 задержки в нулевое состояние сбрасываются по крайней мере еще два триггера 11 , -11 и-i (по одному в каждой подгруппе регистров-1

К и 1

к-и

-1 f, , и так далее. После

5

5

0

5

0

5

0

сравнения последнего разряда чиссгл на выходе 20 сдвигающего регистра 13 появляется сигнал об окончании tipo- цесса упорядочивания чисел. При этом наибольшее число записано в регистре , а наименьшее - в регистре 1 ц( . Таким образом, устройство реализует принцип упорядочивания чисел по возрастанию с разбиением исходного ряда на 2 подгруппы с каяздым циклом сравнения (i - номер цикла) и последующим одновременным упорядочиванием чисел в каждой подгруппе, что обеспечивает полное упорядочивание чисел за однократный просмотр их разрядов.

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

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

,..oN-2, соединен соответственно с К-м информационным входом (Р+1)-го регистра, выход К-го регистра i-ro регистра, где ,oo.,N, соединен соответственно с первым входом К-го элемента И анализа i-й группы, выход К-го элемента И анализа i-й группы соединен с К-м входом i-ro элемента ИЛИ группы, отли чающееся

тем, что, с целью повышения быстродействия, распределитель управлягощмзс сигналов выполнен на сдвигающем регистре и в устройство введены первая и вторая группы элементов запрета, группа дифференцрфующих элементов, третья группа элементов задержки, причем вход запуска устройства соединен с первым входом элемента ИЛИ., вызсод которого соединен с входом сдвига .сдвигающего регистра и через :элемент задержки с вторым входом элемента ШЖ и первым входом j-ro элемента И второй группы, где .,., №-1, которого соединен с информационным входом j-ro элемента запрета первой , выход которого соединен с входом установки, в О i-ro триггера, выход первого элемента ИЛИ группы соединен с вторым входом первого элемента И второй груп- пы и с запрещающем входом первого элемента запрета второй группы, выход (j+1)-ro элемента ИЛИ группы соединен через соответствующий эл емемт задержки первой группы с запрещающим входом (j+1)-ro элемента запрета пер вой группы и с информационным входом j-ro элемента запрета-второй группы, выход Р-го элемента задержки первой группы соединен с вторым входом (P+t)ro элемента И второй группы и с запрещающим входом )-гo элемента запрета второй группы, выход j-ro элемента запрета второй группы соединен с вторьйГ входом j-ro эле

5

0

5

0

5

мента И первой группы, выход которого соединен с управляющими входами К элементов И записи и перезаписи J-X групп и через j-й дифференцирующий элемент с входами установки в О (j-ro и (j+D-ro регистров, выход j-ro регистра соединен с информационным входом (К-го элемента И записи j-й группы, К-й выход (j+t)- го регистра соединен с информационным входом К-го элемента И перезаписи j-й группы, выход К-го элемента И Р-й группы соединен через соот- ветствунадий элемент задержки второй группы с первым входом К-го входного элемента ИЛИ Р-й группы, выход К-го элемента И записи (Ы-1)-й группы соединен через соответствуищий элемент задержки второй группы с (К-м информационным входом N-ro регистра, выход К-го элемента перезаписи {Р-«-2)-й группы соединен через соответствующий элемент задержки третьей группы с вторым входом К-го входного элемента ИЛИ Р-й группы, выход К-го. элемента И перезаписи второй группы соединен через соответствующий элемент зад ержки третьей группы с К-м информационньм входом первого регистра, К-й выход сдвигающего регистра соединен с вторыми входами К-х элементов И анализа i-x групп, выход старшего разряда сдвигающего регистр 1 является выходом окончания сортировки устройства.

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