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

 

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

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

РЕСПУБЛИН (51) 4 G 06 F 7/06

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

3, . ° . 3 „, первый сдвиг овый регистр

4, элементы И 5, — 5 „, управления циклом с открытым коллектором, второй сдвиговый регистр 6, схему сравнения 7, триггер 8, элемент И9, вход 10 выход 11. Регистры предназначены для записи и хранения чисел, подлежащих сортировке, представляют собой совокупность регистров с третьим состоянием, схема сравнения предназначена для сравнения пары чисел, записанных в соседних регистрах, и переписи их в регистры в порядке убывания. Лереписью чисел и подключением следующей пары чисел на сравнение управляет сдвиговый регистр 4 с элементами ИЛИ3, — 3„ и элементами

И2„-.2„. Сдвиговый регистр 6 и элементы И5,-5„, с открытым коллектором служат для организации и-1 циклов сортировки. 1 ил.

{21) 4103424/24-24 (22) 11.08.86 (46) 30.07,88. Бюл. № 28 (72) А.В. Тупица, b.Ã. Шарон и Б.А. Швед (53) 681.325(088.8) (56) Авторское свидетельство СССР

¹ 1223222, кл . G 06 F 7!08, 1984.

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

I (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ, (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано прн реализации технических средств 38М и создании устройств обработки статистической информации. Цель изобретения — упрощение устройства. Устройство содержит регистры 1, — 1„ с третьим состоянием, группу элементов ИЛИ (р (Ф

3(Pppr q > е

ОПИСАНИЕ ИЗОБРЕТЕНИЯ,,„- "; ц1

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

1413622

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

Цель изобретения — упрощение устройства.

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

Устройство содержит регистры 1 с третьим состоянием (п — количество чисел, подлежащих сортировке), элементы И 2 управления переписью, элементы ИЛИ 3, первый сдвиговый регистр 4, элементы И 5 управления цикг лом с открытым коллектором, второй сдвиговый регистр 6, схему 7 сравнения, D-триггер 8, элемент И 9, вход

10, выход 11.

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

В начальном состоянии триггер 8 устанавливается в нулевое состояние, 25 в первый разряд первого сдвигового регистра 4 и в (n-1)-й разряд второго сдвигового регистра 6 заносится " 1", После того, как в регистры 1„ » 1„ будут занесены числа, подлежащие 3О сортировке (цепи начальной установки и занесение чисел не приводятся), на вход 10 устройства подаются импульсы тактовой частоты. По переднему фронту первого импульса В первом сдви З5 говом регистре 4 происходит сдвиг

"1" с первого разряда во второй. С выхода второго разряда первого сдвигового регистра 4 " 1" через элементы

KIH 3 и 3 подается на входы элемен- 4О тов И 2, и 2 и на управляющие входы регистров 1, и 1, Регистры 1, и 1 будут выведены из третьего состояния, и находящаяся в них информация будет подана на информационные входы А и В 45 схемы 7 сравнения. В первом такте схема 7 сравнения работает в режиме

А В. На ее выходе появится " 1", если большое число будет подаваться на информационный вход А схемы 7 сравнения.

В этом случае по заднему фронту импульса на выходе элемента И 9 произойдет перезапись информации между регистрами

1, и 1, меньшее число будет занесено в регистр с большим порядковым номером .

По заднему фронту первого импульса на входе 10 устройства триггер 8 перебро- сится в единичное состояние, переключив схему 7 сравнения в режим работы

В)А. В этом режиме 1" на выходе схемы сравнения появится в там случае, если в следующем такте работы большее число будет подано на информационный вход В схемы 7 сравнения, С приходом второго импульса на вход 10 устройства " 1" в первом сдвиговом регистре 4 сдвинется в третий разряд, в этом такте будут сравниваться числа, находящиеся в регистрах 1 и 1 . Меньшее число по окончанию второго такта снова будет находиться в регистре с большим порядковым номером. Когда "1" за п-1 такта импульсов на входе 10 устройства достигнет n-ro разряда, в регистр

1„ будет занесено минимальное число из группы и надлежащих сортировке чисел. В этом же (n-1)-м такте на выходе элемента И 5 „ < появится " 1", С приходом следующего п-го импульса на вход 10 устройства на выходе элемента И 5„, снова появится "0". По заднему фронту импульса на выходе элемента И 5, произойдет начальная установка первого сдвигового регистра

4 в начальное состояние н сдвиг " 1" во втором сдвиговом регистре 6 с (n-1)-ro в (п-2)-й разряд. Следующий цикл работы уже будет состоять из и-1 тактов и закончится записью в регистр 1„, минимального числа. из группы и-1 оставшихся чисел, Сортировка всех чисел будет состоять из и-1 циклов работы устройства.

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

Устройство для сортировки чисел, содержащее и регистров,,где n — число сортируемых чисел, схему сравнения, элемент И, узел синхронизации, элементы И управления переписью, элементы И управления циклом, ппу элементов ИЛИ, коммутатор ч, коммутатор циклов, причем управляющий вход устройства соединен с входом узла синхронизации, первый выход которого соединен с выходом управления режимом схемы сравнения, выход которой соединен с первым входом элементаИ,отличающееся тем, чт о, с целью упр още ния устройства, регистры выполнены с третьим состоянием, а элементы И управления циклом с открытым коллектором, коммутаторы чисел и циклов выполнены соответст" венно на первом и втором сдвиговых регистрах, управляющих вход устройства является его тактовым входом, 141 36

Составитель Е. Иванова

Техред И.Верее Корректор Э. Лончакова

Редактор М. Келемеш

Закаэ 3786/51 Тираж 704 Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 узел синхронизации выполнен на D1 триггере, синхровход которого является входом узла синхронизации, прямой выход — выходом узла синхрониза5 ции, вход управления режимом схемы сравнения является входом задания режима "Больше", вход задания режима

"Меньше" схемы сравнения соединен с инверсным выходом D-триггера и его

D-входом, первый вход первого элемента ИЛИ группы подключен к входу логического нуля устройства, выходы одноименных разрядов всех нечетных регистров с третьим состоянием подклю- 15 чены к соответствующим входам первой группы схемы сравнения и соответствующим информационным входам всех четных регистров с- третьим состоянием, одноI именные выходы разрядов которых под- 20 ключены к соответствующим входам второй группы схемы сравнения и соответствующим информационным входам всех нечетных регистров с третьим состоянием, вход разрешения считывания - 25 го регистра с третьим состоянием, где

i=1,2,...,n соединен с выходом i-ro гг

4. элемента ИЛИ группы и первым входом

>-го элемента И управления переписью, выход которого соединен с синхровходом i-го регистра с третьим состоянием, вторые входы всех элементов И управления переписью подключены к выходу элемента И, второй вход которого соединен с тактовым входом устройства и синхровходом первого сдвигового регистра, вход начальной установки которого соединен с выходами всех элементов И управления циклом с открытым коллектором и входом начальной установки второго сдвигового регистра, выход первого разряда которого является выходом конца цикла устройства, а выход j-го разряда, где 1=2,3, и, соединен с первым входом (j 1)-го элемента И управления циклом с открытым коллектором, второй вход которого соединен с выходом j-го разряда первого сдвигового регистра, вторым входом (j-1)-го и первым входом j-ro элементов

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

ИЛИ группы подключен к входу логического нуля устройства.