Устройство для сортировки @ -разрядных чисел

 

Изобретение относится к автоматике и вычислительной технике. Цель изобретения - расширение функциональных возможностей за счет обеспечения возможности-сортировки массивов, содержащих равные числа. Устройство содержит два счетчика, блок памяти, генератор импульсов, коммутатор, триггер , группу элементбв И, элементы ИЛИ, И, НЕ, элементы запрета и элементы задержки. При поступлении очередного числа а, ,2....N, N - количество сортируемых чисел, из сортируемого массива из блока памяти считьшается число Ь, записанное в нем по адресу а, увеличивается на единицу и вновь записывается по тому же адресу. Затем из блока памяти считываются записанные там числа в порядке возрастания адресов, при этом обеспечивается вьщача на выходы устройства текзпдего адреса считываемого числа а як раз. 1 кл. (Л

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

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

РЕСПУБЛИН (19) (И) А1 (504 G 06 F 7 06

«<-" ".%ОЗНОБ р-ч (" (1) . Ц

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

Н А STOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4000391/24-24 (22) 22.10.85 (46) 23.03.87. Бвл. В 11 (72) А.С.Гуляев и В.В.Богданов (53) 681.325 (088.8) (56) Авторское свидетельство СССР, У 1073770, кл. С 06 F 7/06, 1982.

Авторское свидетельство СССР.В 1183956, кл. С 06 F 7/06, 1984. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ш-РАЗРЯДНЫХ ЧИСЕЛ (57) Изобретение относится к автоматике и вычислительной технике. Пель изобретения — расширение функциональных возможностей эа счет обеспечения возможности сортировки массивов, соР держащих равные числа. Устройство содержит два счетчика, блок памяти, генератор импульсов, коммутатор, триггер, группу элементов И, элементы

ИЛИ, И, НЕ, элементы запрета и элементы задержки. При поступлении очередного числа a„, k =t, 2... Л, К вЂ” количество сортируемых чисел, иэ сортируемого массива из блока намял считывается число Ь „, записанное в нем по адресу а„, увеличивается на единицу и вновь записывается по тому же адресу.

Затем из блока памяти считываются записанные там числа в порядке возрастания адресов, при этом обеспечивается выдача на выходы устройства текущего адреса считываемого числа а„ Ю

Ьд раз ° I ил, 1 12987

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

Цель изобретения — расширение функциональньгх возможностей за счет обеспечения возможности сортировки массивов, содержащих равные числа °

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

Устройство содержит генератор 1 импульсов, счетчик 2, блок 3 памяти, коммутатор 4, элемент НЕ.5,. группу 6 элементов И, реверсивный счетчик 7, триггер 8, элементы ИЛИ 9 — 11, элемент И 12, элементы 13 — 15 запрета, элементы 16 — 19 задержки, информационные входы 20, вход 21 разрешения зайиси, вход 22 начальной установки устройства, тактовый вход 23, вход

24 задания режима сортировки, вход

25 задания режима считывания, выходы 26.

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

25 с

В режиме очистки памяти на вход

22 начальной установки устройства подается импульс, устанавливающий счетчики 2 и 7 в нулевое состоянн ; на адресных и информационных входах бло- 30 ка 3 памяти устанавливаются нулевые потенциалы. Затем на входе 21 разрешения записи устанавливается логический нуль, чем запрещается запись в счетчик 2 по входам 20. При установ. е 35 на входах 24 и 25 нулевых потенциалов на первом и втором управляющих входах коммутатора 4 — нулевые потенциалы, в результате чего к выходу коммутатора

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

2. пачки из 2 (m — количество разрядов сортируемь:х чисел) импульсов переполнения со счетчика 2 остановится.

Одновременно на вход управления (запись/считывание) блока 3 памяти через коммутатор 4 и элемент НЕ 5 по= 50 ступает та же инвертированная пачка импульсов записи. После полного просчета счетчика 2 во всех ячейках блока 3 памяти записан нулевой код.

В режиме сортировки на входе 21 разрешения записи устанавливается единичный потенциал, при этом разрешается запись в счетчик 2 по информа38 2 ционным входам 20. На вход 24 задания режима сортировки подается единичный . потенциал, а на входе 25 сохраняется нулевой потенциал, что обеспечивает подключение к выходу коммутатора 4 его информационного входа, который соединен с выходом элемента 18 задержки. Сортируемая последовательность из Nm-разрядных двоичных чисел поступает на входы 20,,записывается в счетчик 2 и с его выходов поступает на адресные входы блока 3 памяти.

Синхронно с каждым числом на вход 23 устройства подается тактовый импульс, который переводит триггер 8, первоначально установленный в нуль, в единичное состояние. При этом на первом управляющем входе коммутатора, подключенном к выходу элемента 13 запрета, устанавливается нулевой потенциал, а единичный сигнал с выхода триггера через элемент ИЛИ 9 поступает на второй управляющий вход коммутатора 4, что определяет состояние коммутатора, обеспечивающее режим считывания из блока 3 памяти.

Одновременно единичный потенциал с выхода триггера S поступает через элемент ИЛИ 10 на вход разрешения записи счетчика 7. Число из блока 3 памяти, находящееся по адресу, опреде ляемому содержимым счетчика 2, переписывается H счетчик 7. Тот же тактовый импульс, задержанный элементом

16 задержки,:возвращает триггер 8 в нулевое состояние, что приводит к установке на первом и втором управляющих входах коммутатора 4 единичного и нулевого потенциалов соответственно. Затем тот же гактовый импульс, задержанный элементом 17 задержки, поступает на суммирующий вход счетчика 7 и увеличивает его содержимое на единицу. После этого тот же тактовый импульс, пройдя через элемент 8 задержки, поступает на второй информационный вход коммутатора 4, что при установленной комбинации на управляющих .входах коммутатора 4 обеспечивает запись в блок 3 памяти содержимого счетчика 7 по адресу, равному. величине числа, поступившего на входы 20 устройства. При поступлении последующих чисел на входы 20 устройство работает аналогично.

В результате обработки всей последовательности сортируемых чисел s блоке 3 памяти по адресам, равным по3 1? 987 ступившим в устройство числам, будет записано количество данных чисел в сортируемом массиве. Например, если в сортируемом массиве число 5 встречается дважды, то в блоке 3 памяти по адресу, равному 5, будет записано число 2.

В режиме считывания на вход 21 разрешения записи подается нулевой потенциал, на входы 24 и 25 — нулевой 10 и единичный потенциалы соответственно. При этом на выходе коммутатора 4 устанавливается нулевой потенциал, а на входе управления блока 3 памяти— потенциал логической единицы, что за- 15 дает режим считывания информации из блока памяти. На вход 22 начальной установки подается импульс, устанавливающий счетчики 2 и 7 в нулевое состояние; на адресных и информационных20 входах блока 3 памяти устанавливаются нулевые потенциалы. Единичный потенциал с входа 25 устройства через открытый элемент 14 запрета и элемент

ИЛИ 10 разрешает запись в счетчик 7.

Затем запускается генератор 1 импульсов, останов которого происходит при о переполнении счетчика 2.

Очередной импульс с генератора 1 через элемент 15 запрета поступает 30 на суммирующий вход счетчика 2, увеличивая его содержимое на единицу.

Этот же импульс через коммутатор 4 и элемент НЕ 5.поступает на управляющий вход блока 3 памяти. При этом число, хранящееся в блоке 3 памяти, по адресу, установленному в счетчике 2, считывается в счетчик 7. Если в счетчик

7 считано число "0, то на выходе элемента ИЛИ 11 сохранится нулевой 40 потенциал, и элементы 14 и 15 запрета останутся открытыми, а элемент И 12— закрытым, следовательно, на выходы 26 устройства число с выходов счетчика 2 не поступит. Если в счетчик 7 считано45 число, отличное от нуля, то на выходе элемента ИЛИ 11 появится единичный потенциал, который откроет элемент И

12 и закроет элементы 14 и 15 запрета. При этом снимается сигнал разре- 50 шения записи со счетчика 7 и блокируется суммирующий вход счетчика 2.

Этот же импульс с генератора 1, задержанный элементом 19 задержки, через элемент И 12 поступает на вто.рые входы элементов И группы 6; при этом значение очередного отсортированного числа с выходов счетчика 2

38 4 подается на выходы 26 устройства. Одновременно содержимое счетчика 7 уменьшается на единицу. Если после этого содержимое счетчика не равно нулю, то сигналы на выходах элементов

14 и 15 запрета и элемента И 12 не изменятся и следующий импульс с генератора 1 через элемент 19 задержки и элемент И 12 вычтет из содержимого счетчика 7 единицу и откроет группу

6 элементов И, что обеспечит повторную выдачу этого же числа. Этот цикл будет повторяться до обнуления счетчика 7, после чего элемент И 12 закроется, а элементы 14 и 15 запрета откроются. Следующий импульс с генератора 1 увеличит содержимое счетчика

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

Если перед считыванием во все разряды счетчика 2 записать единичные значения и переключить счетчик 2 на вычитание, то при считывании на выходах 26 получим последовательность чисел, отсортированную в порядке убывания.

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

Устройство для сортировки m-разрядных чисел, содержащее генератор импульсов, коммутатор, счетчик, блок памяти, группу из m элементов И и элемент НЕ, причем выход генератора импульсов соединен с первым информационным входом коммутатора„ выход которого через элемент НЕ соединен с входом запись/считывание блока памяти, вход начальной установкч устройства соединен с входом установки счетчика в нулевое состояние, вход 1-го разряда сортируемых чисел устройства, где i 1 2,...,m, m — разрядность сортируемых чисел, соединен с -м информационным входом счетчика, выход i -го разряда которого соединен с i-м адресным входом блока памяти и с первым входом i-го элемента И группы, выход которого является i-м информационным выходом устройства, вторые входы всех элементов И группы объединены, вход разрешения записи счетчика является входом разрешения записи устройств, 1 2987

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

Техред g. Ходанич Корректор С.Шекмар

Редактор К.Егорова

Заказ 890/51 Тираж 673 Подписное

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

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

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

\ а счетчика, вычитающий вход которого подключен к вторйм входам элементов

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