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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к автоматике и вычислительной технике. Цель изобретения - повышение быстродействия устройства. Устройство содержит генератор 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 ил. с ю (Л с

Взамен ранее изданного

СС803 СОВЕТСКИХ

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

РЕСПУБЛИК (51)5 С 06 Г 7/02 E oewai

ПАТЕНТН0 ЩН%

Е iBfiHOTEHA

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

И АBTOPCHOMY СВИДЕТЕЛЬСТВУ

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

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

ПРИ ГННТ СССР

1 (21) 4141984/24 — 24 (22) 16 ° 09.86 (46) 15.01.90. Вял, 11 - 2 (75) И.З.Стрыгин (53) 681. 325, 5 (088. 8) (56) Авторское свидетельство СССР

У 1043666, кл. 0 06 Г 15/36, 1982, Авторское свидетельство СССР

1г 1291961, кл, С Об Г 7/02, 1985, 1 (54) УСТРОЙСТВО ДЛЧ СОРТИРОВ1(И ЧИСЕЛ (5 7) Изобретение относится к автоматике и вычислительной технике ° Цель изобретения — повышение быстродействия устройства. Устройство содержит генератор 1 импульсов, дешифраторы

2-4, шифраторы 5, б, счетчики 7, Изобретение относится к автоматике и вычислительной технике.

Цель изобретения — повышение быстродействия устройства, На чертеже представлена схема устройства, Устройство содержит генератор 1 импульсов, дешифраторы 2-4, шифраторы 5 и 6, счетчик 7, трехстабильный триггер 8, триггер 9, распределитель

10 импульсов, коммутатор 11, блок 12 сравнения, регистр 13, элементы И 14 и 15, элементы ИЛИ 16 и 17, входную группу элементов И 18, группу счетчиков 19, — 19, где h = 2 — 1, m — разрядность чисел исходного массива, группу реверсивных счетчиков

201 — 20, s — максимальная частость (количество равных) чисел в исходном массиве, группы элементов И 21, - 21 перезаписи, группы элементов И

„„SU,„, 1394214 А1

2 трехстабильный триггер 8, триггер 9, распределитель 10 импульсов, коммутатор 11, блок 12 сравнения, регистр

13, элементы И 14, 15, элементы ИЛИ

16, 17, входную группу элементов И

18, группу счетчиков 19, — 19» где

h = 2 — 1, н — разрядность чисел исходного массива, группу реверсивных счетчиков ?О „— 20д, s — максимальная частость (количество р авных) чисел в исходном массиве, группы элементов И 2! — 21 перезаписи, группы элементов И 22, — 22, 231 — 23

24, — 241,, 25, — 25>, группы элементов ИЛИ 26 — 265, 27, — 27, 28

28, 29 с соответствующими связями, ил.

22„ — 22, 23, — 23, 24, — 24

25 — 25, группы элементов ИЛИ

26, — 26, 27, — 27, 23, — 23„, 29, группу входов 30 числа, вход 31 зада— ния длины массива, вход 32 запуска, выход 33 значения числа и выход 34 значения частости.

Устройство работает следующим образом, Предварительно все счетчики 19, 20 и регистр 13 установлены в нулевое состояние, триггер 9 — в единичное состояние, трехстабильный триггер 8 — в первое состояние. Через вход 31 поступает и записывается в счетчик 7 длина исходного массива, Иа вход 32 поступает сигнал, устанавливающий триггер 8 во второе состояние, а затем через вход 30 последовательно поступают числа исходного мас13942) 4 сива, которые преобразуются дешифратором 3 в единичный код на его соответствующем выходе и подсчитываются счетчиками 19 — 19 отдельно по каж1 к 5 дому значению числа и счетчиком 7 по всем числам. По исчерпании массива счетчик 7 выдает сигнал, переводящий триггер 8 в третье состояние, при этом запускается генератор l импульсов, К этому моменту в счетчике )9p, р = 1, Ь, находится число ы (р) — количество чисел р в исходном массиве (частость числа р) . Первый импульс генератора 1 импульсов поступает на вход распределителя 10 импульсов, который последовательно со сдвигом по времени (определяемым задержкой срабатывания элементов устройства) выдает импульсы на входы групп элементов И 2)„ — 21 . Частости w(1), w(2) ы(Ь) через группу элементов

ИЛИ 29 поступают последовательно на вход коммутатора 11 и далее — на вход дешифратора 2, где преобразуются в единичный код на соответствующем выходе и подсчитываются реверсивными счетчиками 20„, 20,...,20s, работающими на сложение, Импульс с (h+1)-ro выхода распределителя 10 импульсов устанавливает триггер 9 в нулевое состояние. Теперь импульсы генератора 1 импульсов поступают на входы элементов И 22 и 23,. Если w(1)=0, то импульсы поступают на входы элементов И 22 и -3 и т.д. Б резулЬ2

3S тате формируется имп; ьс íà r-м входе шифр,атора 5, r 1, s, соответствующем ненулевому количеству частс стей w(r) с наименьшим значением частости r которая преобразуется шифратором 5 в двоичный код и записывается в регистр 13, Распределитель 10 импульсов вновь выдает последовательность импульсов на своих выходах, открывая соответствующйе группы элементов И 2), — 21, и частости w{l), w(2),...,w(h) сравниваются блоком 12 сравнения с выбранной частостью r, Если какая-либо частость w(y) = г, то значение числа р, пр еоб р аз ов анное шифр ат ором б, поступает на выход 33 устройства, а содержимое счетчика 20 „уменьшается на единицу. Работа устройства заканчивается, когда во всех счетчиках

20, — 205 будут записаны нули, Сигналы об этом с выхода элемента И 23 через элемент ИДИ )7 поступает на 1 вход триггера 3 и устанавливает его в первое состояние, Формула и з обретения

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

s реверсивных счетчиков, где s максимальная частость чисел в исходном массиве, первую и вторую группы из s элементов ИЛИ каждая, первую и вторую группы из s a s-1 элементов

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

i-го разряда числа устройства, где

i=1,2...,,m, соединен с первым входом i-ro входного элемента И группы, выход которого соединен с 1-м входом второго элемента ИЛИ, выход которого соединен с вычитающим входом счетчика, выходы разрядов которого соединены с остальными входами первого элемента ИЛИ, выход которого соединен со счетным входом трехстабильного триггера, первый и второй выходы которого соединены соответственно с вторыми входами входных элементов И группы и с входом запуска генератора импульсов, входы задания длины массива устройства соединены с соответствующими информационными входами счетчика, j-й выход первого дешифратора, где j= 1 2,...,s соединен с первым входом j ãо элемента ИЛИ первой группы, выход которого соединен со счетным входом j-ro реверсивного счетчика группы, входы разрешения суммирования всех реверсивных счетчиков объединены, входы разрешения вычитания всех реверсивных счетчиков группы объединены, прямые выходы разрядов j-ro реверсивного счетчика группы соединены с соответствующими входами j-ro элемента ИЛИ второй группы, выход которого соединен с первым входом j-ro элемента И первой группы, выход которого соединен с

j-м входом первого шифратора, инверсные выходы k-го реверсивного счетчика группы, где k 1 2,...,s-l, соединены с соответствующими входами

k-го элемента И второй группы, вы13942)4 ход которого с Оединен с В торым вхо дом ()tl )-го элемента И первой группы, выход 1-го элемента И второй группы, где 1= 1,2,...,s — 2, соединен с дополнительным входом (1+1)-го элемента И второй группы, о т л и ч а ющ е е с я тем, что, с целью повышения быстродействия, в него введены

PFI второй и третий дешифраторы, 2 — 1

) ГП счетчиков, третья группа из 2 -1 элементов И, распределитель импульсов, второй шифратор, регистр, блок сравнения, коммутатор, третья группа из

f11

2 - 1 элементов ИЛИ, четвертая группа из )log в(элементов ИЛИ, где )х)".— наименьшее целое, превосходящее Х, 2 — ) групп элементов И перезаписи по

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

2 -) выход распределителя импульсов соединен с первым входом второго элемента И, выход которого соединен с входом установки триггера в нулевое

2О состояние, прямой выход которого соединен с входами разрешения суммирования всех реверсивных счетчиков группы, первым управляющим входом коммутатора и вторым входом второго эле25 мента И, инверсный выход триггера соединен с входами разрешения вычитания всех реверсивных счетчикон группы, вторым управляющим входом коммутатора, а также с вторым входом

Зо первого элемента И, выход которого соединен с вторым входом первого элемента И первой группы и с дополнительным входом первого элемента И второй группы, q-й выход первого

35 шифратора соединен с q-м информационным входом регистра, выход q-го разряда которого является q-м выходом значения частости кода выборки устройства и соединен с q-м входом

4О второй группы блока сравнения и с

q-м входом третьего дешифратора, j-й выход которого соединен с вторым входом j-ro элемента И четвертой группы, выход которого соединен с

45 вторым входом j-ro элемента ИЛИ первой группы.

1)94214

Составитель В.Горохов

Редактор О.Филитова Техред JI,Олийнык Корр ек т ор Л. Пат ай

Заказ 152 Тираж 566 Подписное

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

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

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