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

 

Изобретение относится к вычислительной технике. Цель изобретения - повышение быстродействия. Устройство I Изобретение относится к вычислительной технике. Цель изобретения - повышение быстродействия . На чертеже приведена схема устройства . Устройство содержит генератор 1 импульсов, дешифратор 2, группу,из Р элементов ИЛИ 3,-Зр, где Р 2, п - количество разрядов сортируемых чисел, Р реверсивных счетчиков 4у- 4р, группу элементов И 5, -5р. и 6р, группу элементов ИЛИ 7 -7р , группу из п элементов И 8, шифратор 9 и блок 10 управления, содержащий элемент РШИ 11, счетчики 12 и 13, элемент ИЛИ 14 и трехстабильньм триггер 15. Устройство содержит также группу входов 16 сортируемых чисел, вход 17 задания объема сортируемого массива , вход 18 запуска устройства и выход 19. содержит генератор 1 импульсов, дешифратор 2, группу 3,-Зр из р элементов ИЛИ, где Р 2 , п - количество разрядов сортируемых чисел, Р реверсивных счетчиков 4,-4р, группу элементов И 5,-5p-f и , группу элементов ИЛИ 7 -7р , группу из п элементов И 8, шифратор 9, блок 10 управления , содержащий элемент ИЛИ 11, счетчики 12 и 13, элемент ИЛИ 14 и трехстабильный триггер 15 с соответствующими функциональными связями . 1 ил. Устройство работает следующим образом. Перед началом работы счетчики 4, - 4р и триггер 15 устанавливаются в нулевое состояние (не показано). Затем на вход 17 подается код О объема массива и записывается в счетчики 12 и 13, по входу 18 подается сигнал запуска устройства. При этом триггер 15 переводится в первое состояние и на его первом выходе появляется потенциал логической единицы , который открывает группу элементов И 8 и устанавливает счетчики 4I-4р в режим суммирования. Сортируемые числа поступают по входу 16, при этом содержимое счетчика 12 уменьшается каждый раз на единицу, а на а -м выходе дешифратора 2 ( i-e сортируемое число) появляется сигнал, который поступает на счетчик 4a.t , увеличивая его содержимое на единицу. Таким образом, в J-M счетчике 4 (,...,p) хранитсл ю со ( СЭ5

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

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

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

РЕСПУБЛИК (5D4С 6F 7 02

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

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

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

ПО ИЗОБРЕТЕНИЯМ И OTHPbfTHRM

ПРИ ГКНТ СССР (21) 3955173/24-24 (22) 23.09.85 (46) 15.03.89. Бюл. ¹ 10 (75) Н.3 ° Стрыгин и Н.Н.Мельников (53) 681,325.66 (088.8) (56) Авторское свидетельство СССР

¹ 482756, кл. G 06 F 15/36, 1974 °

Авторское свидетельство СССР № .1043666, кл. G 06 F 15/36, 1983. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к вычислительной технике. Цель изобретенияповышение быстродействия. Устройство

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

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

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

Устройство содержит генератор 1 импульсов, дешифратор 2, группу.из

P элементов ИЛИ 3, -Зр, где P = 2", n — количество разрядов сортируемых чисел, Р реверсивных счетчиков 4 —

4р, группу элементов И 5, -5р., и 6,— бр, группу элементов ИЛИ 7 -7р, группу из п элементов И 8, шифратор 9 и блок 10 управления, содержащий элемент ИЛИ 11, счетчики 12 и 13, элемент ИЛИ 14 и трехстабильный триггер

15.

Устройство содержит также группу входов 16 сортируемых чисел, вход

17 задания объема сортируемого массива, вход 18 запуска устройства и выход 19.

„„SU„„1291961 а1 содержит генератор 1 импульсов, дешифратор 2, группу 3, -Зр из р элеи ментов ИЛИ, где P = 2, и — количество разрядов сортируемых чисел, P реверсивных счетчиков 4, -4р, группу элементов И 5< -5p. и 6 -6р, группу элементов ИЛИ 7 -7р, группу из и элементов И 8, шифратор 9, блок 10 управления, содержащий элемент ИЛИ

11, счетчики 12 и 13, элемент ИЛИ

14 и трехстабильный триггер 15 с соответствующими функциональными связями. 1 ил.

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

Перед началом работы счетчики 4,—

4р и триггер 15 устанавливаются в нулевое состояние (не показано). 3атем на вход 17 подается код < (?) объема массива и записывается в счетчики 12 и 13, по входу 18 подается сигнал запуска устройства. При этом триггер 15 переводится в первое состояние и на его первом выходе появляется потенциал логической единицы, который открывает группу эле ментов И 8 и устанавливает счетчики 4 -4р в режим суммирования. Сортируемые числа поступают по входу 16, при этом содержимое счетчика 12 уменьшается каждый раз на единицу, а на а„ -м выходе дешифратора 2 (a„—

i-е сортируемое число) появляется сигнал, который поступает на а;-й счетчик 4, ;, увеличивая его содержимое на единицу. Таким образом, в

1-м счетчике 4 ()=1,...,р) хранит1291961 ся количество чисел в массиве, равных ).

После приема 0 чисел счетчик 12 выдает сигнал переполнения, который переводит триггер 15 во второе состояние. При этом гоявляется единичный сигнал на его втором выходе, который устанавливает счетчики 4< -4< в режим вычитания и запускает генера- 10 тор 1 импульсов.

Импульсы от генератора 1 поступают в счетчик 13 и на элементы Н 5 и

6, . Если в счетчике 4 ненулевое число, то элемент 6 открыт, импульс с его выхода поступает на шифра.тор 9, где преобразуется в двоичный код

"00...01" и поступает на. вьгход 19.

Зтот же импульс через элемент ИЛИ 3 поступает на счетный вход счет в 20 чика 4,, при этом его содержимое уменьшается на единицу. Если в счетчике 4, нуль, то элемент И 6, закрыт, но открыт элемент И 5 и импульсы от

) генератора 1 поступают на элементы 25

И 5 и 6 . В дальнейшем устройство работает аналогично.

После сортировки всего массива из () чисел счетчик 13 выдает сигнал переполнения, который установит триг—

prep 15 в нулевое состояние и остановит генератор 1. формула и з обретения

VcTpoHcTBo для сорТНроВКН чисел, содержащее дешифратор, группу из 2 элементов ИЛИ,где и- количество раз". рядов сортируемых чисел, группу из

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

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

k=1 2,..., llog Q(, — количество сор тируемых чисел, j x L — ближайшее целое, не большее х, соединен c. k-м входом 1-го элемента И третьей л груцпь (1=1,7,...,2 -1), выход котор го соединен с первым входом (1+1)ro элемента И первой группы: и, за исключением (2 -1)-го элемента И третьей группы, c(flog „QL+1) м входом (1+1)-го элемента Й третьей группы, прямой выход k-го разряда i-ro реверсивного счетчика соединен с k-м входом i-го элемента ИЛИ второй группы, выход которого соединен с вторым входом х-го элемента И первой группы, выход которого соединен с вторым входом i-ro элемента ИЛИ первой группы, вход задания объема сортируемого массива устройства соединен с информационными входами первого и второго счетчиков, выход переполнения первого счетчика соединен с вторым входом второго элемента ИЛИ, третий вход которого является входом запуска устройства, выход генератора импульсов соединен с первым входом первого элемента И первой группы и с )lop 0 E +1)-м входом первого элемента И третьей группы.

129т961

Составитель В.Варфоломеев

Редактор П.Филиппова Техред М.Моргентал Корректор Э.Лончакова

Заказ 1854

Тираж 667

Подписное

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

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

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