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

(21)4103424/24-24

(22)11.08.86

(46) 30.07.88. Бкш. № 28 (72) А.В. Тупица, Б.Г. Шаров и Б.А. Швед

(53)681.325(088.8)

(56) Авторское свидетельство СССР № 1223222, кл. G 06 F 7/08, 1984.

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

I

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

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

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

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

с

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

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

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

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

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

В начальном состоянии триггер 8 устанавливается в нулевое состояние, в первый разряд первого сдвигового регистра А .и в (п-1)-й разряд второг сдвигового регистра 6 заносится 1. После того, как в регистры 14, ,,. будут занесены числа, подлежащие сортировке (цепи начальной установки и занесение чисел не приводятся), на вход 10 устройства подаются импулсы тактовой частоты. По переднему фронту первого импульса в первом сдв говом регистре 4 происходит сдвиг 1 с первого разряда во второй. С выхода второго разряда первого сдвигвого регистра 4 1 через элементы

. В этом режиме на вьгкоде схмы сравнения появится в там случае, если в следующем такте работы большее число будет подано на информационньй вход В схемы 7 сравнения. С приходом второго импульса на вход 10 устройства 1 в первом сдвиговом регистре 4 сдвинется в третий разряд, в этом такте будут сравниваться числа, находящиеся в регистрах 1., и 1,. Меньшее число по окончанию второго такта снов будет находиться в регистре с большим порядковым номером. Когда 1 за п-1 такта импульсов на входе 10 устройства достигнет п-го разряда, в регистр 1„ будет занесено минимальное число из группы п надлежащих сортировке чисел. В этом же (п-1)-м такте на выходе элемента И 5., появится 1. С приходом следующего п-го импульса на вход 10 устройства на выходе элемента И 5(,-, снова появится О. По заднему фронту импульса на выходе эле- мента И З., произойдет начальная установка первого сдвигового регистра 4 в начальное состояние и сдвиг 1 во втором сдвиговом регистре 6 с (п-1)-го в (п-2)-й разряд. Следующий цикл работы уже будет состоять из п-1 тактов и закончится записью в регистр 1 , минимального числа, из группы п-1 оставшихся чисел. Сортировка всех чисел будет состоять из п-1 циклов работы устройства.

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

Устройство для сортировки чисел, содержащее п регистров, где п - чис

ИЛИ 3, и 3 подается на входы элемен- Q ло сортируемых чисел, схему сравне- тов И 2, и 2,j и на управляющие входы ния, элемент И, узел синхронизатдаи, регистров 1, и 1. Регистры 1 и 1 будут выведены из третьего состояния, и находящаяся в них информация будет

элементы И управления переписью, элементы И управления циклом, /nity элементов ИЛИ, коммутатор , ком

подана на информационные входы А и В . Д5 мутатор циклов, причем управляющий

схемы 7 сравнения. В первом такте схема 7 сравнения работает в режиме , На ее выходе появится 1, если большое число будет подаваться на информационный вход А схемы 7 сравнения В этом случае по заднему фронту импуль- с.а на выходе элемента И 9 произойдет перезапись информации между регистрами

50

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

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

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

ло сортируемых чисел, схему сравне- ния, элемент И, узел синхронизатдаи,

элементы И управления переписью, элементы И управления циклом, /nity элементов ИЛИ, коммутатор , ком

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

узел синхронизации вьшолнен на D- , триггере, синхровход которого является входом узла синхронизации, прямой выход - выходом узла синхрониза- ции, вход управления режимом схемы сравнения является входом задания режима Больше, вход задания режима Меньше схемы сравнения соединен с инверсным выходом D-триггера и его D-входом, первый вход первого элемента ИЖ группы подключен к входу логического нуля устройства, выходы одноименных разрядов всех нечетных регистров с третьим состоянием подклю- чены к соответствующим входам первой группы схемы сравнения и соответствующим информационным входам всех четных регистров с третьим состоянием, одноименные выходы разрядов которых под- ключены к соответствующим входам второй группы схемы сравнения и соответствующим информационным входам всех нечетных регистров с третьим состоянием, вход разрешения считывания i- го регистра с третьим состоянием, где ,2,... ,п,. соединен с выходом i-ro

,

, Q1505

13622

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