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

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

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

На чертеже представлена схема устройства.

Устройство содержит генератор 1 импульсов, дешифраторы 2-4, шифраторы 5 и 6, счетчик 7, трехстабильный триггер 8, триггер 9, распределитель 10 импульсов, коммутатор П, блок 12 сравнения, регистр 13, элементы И 14 и 15, элементы ИЛИ 16 и 17, входную, группу элементов И 18, группу счетчиков. 19, - 19, где h 1, m - разрядность чисел исходного массива, группу реверсивнь х счетч1-1ков 20.. - 20 j, S - максимальная частость (количество равных) чисел в исходном массиве, группы элементов И 21., -21; перезаписи, группы элементов И

22, - 22, 23, - 23, 24, - 24, 25 - 25. группы элементов 1ШИ 26, - 26s, 27, - 27s, 28, - 28, 29, группу входов 30 числа, вход 31 задания длины массива, вход 32 запуска, выход 33 значения числа и выход 34 значения частости.

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

Предварительно все счетчики 19, 20 и регистр 13 установлены в нулевое состояние, триггер 9 - в единичное состояние, трехстабильный -триггер 8 - в первое состояние. Через вход 31 поступает и записывается в счетчик 7 длина исходного массива. На вход 32 поступает сигнал, устанавливающий триггер 8 во второе состояние, а затем через вход 30 последовательно поступают числа исходного масоосо

4 1C

сива, которые преобразуются дешифратором 3 в единичный код на его соответствующем выходе и подсчитываются

счетчиками 19, - 19. отдельно по ,

дому значению числа и счетчиком 7 по

всем числам. По исчерпании массива счетчик 7 выдает сигнал, переводящий триггер 8 в третье состояние, при этом запускается генератор 1 импуль- сов. К этому моменту в счетчике 19р, р 1 ,h, находится число w (р) - количество чисел р в исходном массиве (частость числа р), Первый импульс генератора 1 импульсов поступает на вход распределителя 10 импульсов, который последовательно со сдвигом по времени (определяемым задержкой срабатывания элементов устройства) выдает импульсы на входы групп элементов И 2 Ц - 21, Частости w(l), w(2),..,,w(h) через группу элементов HJDi 29 поступают последовательно на вход коммутатора 11 и далее - на вхо .дешифратора 2, где преобразуются в единичный код иа соответствующем выходе и подсчитываются реверсивными счетчиками 20., 20,2,... ,20s. работающими на сложение,Нмлульс с (h+l)-ro выхода распределителя 10 импульсов устанавливает триггер 9 в нулевое состояние, Теперь импульсы генератора 1 импульсов поступают на входы элементов И 22 и 23,. Если w(l)0, то импульсы поступают на входы элементов И 22 и 23-J и т.д. Б резул - тате формируется имп/ ъс на г-м входе шифр.атора 5, г l,s, соответствующем ненулевому количеству частсгс- тей w(r) с наименьшим значением частости г, которая преобразуется шифратором 5 в двоичный код и записываетс в регистр 13.

Распределитель 10 импульсов вновь выдает последовательность импульсов на своих выходах, открывая соответствующие группы элементов И 21,- 21. и частости w(l), w(2),...,w(h) сравниваются блоком 12 сравнения с выбранной частостью г. Если какая-либо частость w(p) г, то значение числа р, преобразованное шифратором 6, поступает на выход 33 устройства, а содержимое счетчика 20 уменьшается на единицу. Работа устройства заканчивается, когда во всех счетчиках 20, - 20s будут записаны нули. Сигна ль1 об этом с выхода элемента И 23 через элемент ИДИ 17 поступает на

0

5

0

5

0

5

0

5

вход триггера 3 и устанавливает его в первое состояние.

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

Устройство для сортировки чисел, содержащее первый шифратор, первый дешифратор, генератор импульсов, счетчик, трехстабильный триггер, первый и второй элементы ИЛИ, группу из .8 реверсивных счетчиков, где s - максимальная частость чисел в исходном массиве, первую и вторую группы из S элементов HJIIi каждая, первую и вторую группы из s и S-1 элементов И соответственно и группу из m входных элементов И, где m - разрядность чисел исходного массива, причем вход запуска устройства подключен к первому входу первого элемента ИЛИ, вход i-ro разряда числа устройства, где ,2,...,т, соединен с первым входом i-ro входного элемента И группы, выход которого соединен с i-м входом второго элемента ИЛИ, выход которого соединен с вычитающим входом счетчика, выходы разрядов которого соединены с остальными входами первого элемента ИЛИ, выход которого соединен со счетным входом трехстабильного триггера, первый и второй выходы которого соединены соответственно с вторыми входами входных элементов И группы и с входом запуска генератора импульсов, входы задания длины массива устройства соединены с соответствующими информационными входами счетчика, j-й выход первого дешифратора, где ,2,.,.,s, соединен с первым входом j-ro элемента ИЛИ первой группы, выход которого соединен со счетным входом j-ro реверсивного счетчика группы, входы разрешения суммирования всех реверсивных счетчиков объединены, входы разрешения вычитания всех реверсивных счетчиков группы объединены, прямые выходы разрядов j-ro реверсивного счетчика группы соединены с соответствующими входами j-ro элемента ИЛИ второй группь, выход которого соединен с первым входом j-ro элемента И первой группы, выход которого соединен с J-M входом первого шифратора, инверсные выходы k-ro реверсивного г счетчика группы, где k l,2,...,s-l, соединены с соответствуняцими входами k-ro элемента И второй группы, вы-

ход которого соединен с вторым входом (k-t-l)-ro элемента И первой грун- пы, выход 1-го элемента И второй группы, где 1 1 ,2,...,5-2, соединен с дополнительным входом (1+1)-го элемента И второй группы, о т л и ч а кг щ е е с я тем, что, с целью повышения быстродействия, в него введены второй и третий дешифраторы, 2-1 счетчиков, третья группа из 2 -1 элементов Н, распределитель импульсов, второй шифратор, регистр, блок сравнения, коммутатор, третья группа из элементов 1ШИ, четвертая группа из log s элементов IlHIi, где х - наименьшее целое, превосходящее X, групп элементов И перезаписи по log SС каждая, триггер, четвертая группа из S элементов .И, первый и второй элементы И и s-й элемент И второй группы, причем выход i-ro эле мента И группы соединен с i-м входом второго дешифратора,р-и выход которого где ,2,...,, соединен со счетным входом р-го счетчика, выход q-ro разряда которого, где q l,,

соединен с первым входом q-ro элемента И р-й группы перезаписи, выход которого соединен с q-м входом р-го элемента IITM третьей группы и с р-м входом q-ro элемента ИЛИ четвертой группы, выход которого соединен с q-м информационным входом коммутатора, q-й выход первой группы которого соединен с q-M входом первого дешифратора, а q-й выход второй группы коммутатора соединен с q-м входом первой группы блока сравнения, выход которого соедине с первыми входами всех элементов Н третьей и четвертой групп, выход р-го элемента ИЛИ третьей группы соединен с вторым входом р-го элемента И третьей группы, выход которого соединен с р-м входом второго шифратора, выходы которого являются выходами значения числа устройст

д 5 0 5

О Q

5

5

ва, инверсные выходы разрядов з-го реверсивного счетчика группы соединены с соответствующими входами э-го элемента И второй группы, выход (s-l)- го Элемента И второй группы соединен с дополнительным входом s-ro элемента И второй группы, выход которого соединен с дополнительным входом первого элемента ИЛИ, выход генератора импульсов соединен с первым входом первого элемента И и входом распределителя импульсов, 1-й выход которого соединен с первыми входами всех элементов И перезаписи i-й группы, 2 -1 выход распределителя импульсов соединен с первым входом второго элемента И, выход которого соединен с входом установки триггера в нулевое состояние, прямой выход которого соединен с входами разреиения суммирова ния всех реверсивных счетчиков группы, первым управляющим входом коммутатора и вторым входом второго элемента И, инверсный выход триггера соединен с входами разрешения вычитания всех реверсивных счетчико в группы, вторым управляющим входом коммутатора, а также с вторым входом первого элемента И, выход которого соединен с вторым входом первого элемента И первой группы и с дополнительным входом первого элемента И второй группы, q-й выход первого шифратора соединен с q-м информационным входом регистра, выход q-ro разряда которого является q-м выходом значения частости кода выборки устройства и соединен с q-м входом второй группы блока сравнения и с q-M входом третьего дешифратора, j-й выход которого соединен с вторым входом j-ro Элемента И четвертой группы, выход которого соединен с вторым входом j-ro элемента ИЛИ первой группы.

Изобретение относится к автоматике и вычислительной технике. Цель изобретения - повышение быстродействия устройства. Устройство содержит генератор I импульсов, дешифраторы 2-4, шифраторы 5, 6, счетчики 7, трехстабильный триггер 8, триггер 9, распределитель 10 импульсов, коммутатор 1, блок 12 сравне1шя, регистр 13, элементы И 14, 15, элeмe ты ИЛИ 16, 17, входную группу элементов И 18, группу счетчиков 19 - 19, где h 2 - 1, m - разрядность чисел исходного массива, группу реверсивных счетчиков 20 - 20, s - максимальная частость (количество равных) чисел в исходном массиве, группы элементов И 2 - 21 перезаписи, группы элементов И 22 , - 22, 23 - 23, 24, - 24, 25, - 255, группы элементов ИПИ26т- 265,27, - 27, 28 - 28, 29 с соответст}зующими связями, 1 ил. с ю (Л с