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

113

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

Цель изобретения - расширение области применения устройства за счет нахождения числа заданного ранга.

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

Устройство содержит генератор 1 импульсов, счетчик 2, блок 3 памяти, группу элементов И 4, коммутатор 5, элемент НЕ 6, тактовый вход 7, информационные входы 8, вход 9 начальной -установки устройства, вход 10 разрешения записи, входы 11 и 12 управления режимом, выходы 13, вычитающий счетчик 14, злемент И 15, элемент ИЛИ 16, дополнительный элемент НЕ 17, входы 18 кода заданного

ранга, вход 19 записи кода заданного ранга, вход 20 задания режима поиска числа заданного ранга и выход 21 окончания поиска.

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

В режиме Очистка памяти на вход 9 начальной установки подается импульс, который устанавливает счетчик

2в нулевое состояние. Затем на входе 10 разрешения записи устанавливается о, чем запрещается запись

в счетчик 2 по входам 8, на информационном входе блока памяти устанавливается потенциал О. При установке на входах 11 и 12 коммутатора 5 потенциала О к выходу коммутатора подключается его вход, соединенный с генератором 1 импульсов. После этого с генератора 1 на счетчик 2 поступает пачка импульсов (2), одновременно на вход Запись/Считывание блока

3памяти через коммутатор 5 и элемент НЕ 6 поступает т& же инвертированная пачка импульсов записи.

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

В режиме Сортировка на входе 10 разрешения записи устанавливается потенциал I. При этом разрешается запись в счетчик 2 по информационным входам 8, на информационном входе памяти устанавливается потенциал 1. На входе 11 управления режимом коммутатора 5 устанавливается потенциал 1, а на входе 12 управления режимом сохраняется потенциал

42

о. При этом к выходу коммутатора 5 ,подключается тактовый вход 7. Сортируемая (упорядочиваемая) произвольная последовательность п различных по величине т-разрядных двоичных чисел (где поступает на входы 8, записывается в счетчике 2 и с его выхода поступает на адресные входы блока 3 памяти. Синхронно с

каждым числом на тактовый вход 7 поступает тактовый импульс, который через коммутатор 5 и элемент НЕ подается на вход Запись/Считывание блока 3 памяти, что задает режим

Запись блока 3 памяти. При этом в ячейку блока 3 памяти, номер которой

равен величине числа, записывается I111t

В результате признак местонахож- дения в массиве каждого из чисел - - записывается в ячейку блока 3 памяти, номер которой равен по величине числу.

По окончании сортировки устройство переходит в режим считывания. На входе 10 разрешения записи устройства устанавливается потенциал О, на входах 11 и 12 управления режимом

0

устанавливаются соответственно по5

тенциала О и 1. При этом на выходе коммутатора 5 устанавливается потенциал О, а на входе Запись/Считывание блока 3 памяти - потенциал 1, что задает режим Считывание блока 3 памяти. На вход 9 начальной установки подается импульс, счетчик 2 устанавливается в нулевое состояние.

При считывании данных может производиться .Выдача последовательности упорядоченных чисел и Выдача определенного по величине числа. При Выдаче последовательности упорядоченных чисел на вход 20 посту5

0

5

пает единичный сигнал. С генератора 1 импульсов на счетчик 2 выдается пачка из 2 -I импульсов. В процессе счета содержимое счетчика 2 поступает на адресные входы блока 3 памяти и на первые входы элементов И 4.

Если по данному адресу в блоке 3 памяти записывается 1, то этот уровень с выхода блока 3 памяти поступает на вторые входы элементов И 4, разрешает формирование на выходах 13 устройства очередного числа, так как на третий вход элементов И 4 также поступает код 1. Числа формируются в порядке возрастания их величины. Если перед считыванием записывают единичные значения во все разряды счетчика 2 и переключаю счетчик 2 на вычитания, то при считывании на выходах. 13 числа формируются в порядке убывания.

При Выдаче определенного по величине числа на вход 20 в режиме считьшания поступает нулевой сигнал По единичному сигналу на входе 19 с входов I8 устройства в вычитающий счетчик 14 записывается код искомого по величине числа. Затем с генератора I импульсов на счетчик 2 начинают поступать импульсы. При этом из ячеек блока 3 памяти начинает считываться информация. Если по данному адресу в блоке 3 памяти записана 1, то этот уровень поступает с выхода блока 3 памяти на счетный вход вычитающего счетчика 14 и уменьшает его содержимое на единицу. На выходе элемента И 15 и элемента ИЛИ 16 имеется код о. Поэтому на выход 13 устройства также выдаются нулевые сигналы. Пусть в счетчик 14 вначале было записано число k,T.e. необходимо на выход 13 устройства выдать k-e по величине число(число k-ro ранга). Тогда при считывании первых k-1 чисел последовательности содержимое счетчика 14 будет с каждым разом уменьшаться на единицу, но не будет равно нулю (содержать код 1 на всех инверсных выходах). При считывании ik-ro по величине числа упорядоченной последовательности счетчик 14 обнуляется. При этом на все входы элемента И 15 поступает код

Редактор Е.Копча Заказ 1891/44

Составитель Е.Иванова Техред И.Попович

Корректор

Тираж 673Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г.Ужгород, ул.Проектная, 4

I. Элемент И 15 открывается, и единичный сигнал с его выхода выдается на выход 21 устройства, свидетельствуя о том, что k-e по величи-. не число найдено. Одновременно код 1 через элемент ИЛИ 16 поступает на третьи входы элементов И 4 и разрешает выдачу k-ro по величюне числа на выход 13 устройства.

5

0

5

0

5

Ф о

0

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

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

Корректор А.Обручар

Изобретение относится к вычислительной технике, может быть использовано в системах обработки информации и является усовершенствованием устройства по а.с. № 1183956. Цель изобретения - расширение области применения устройства за счет нахождения числа заданного ранга. Цель изобретения достигается тем, что в устройство, содержащее генератор импульсов 1, счетчик 2, блок памяти 3, коммутатор 5, элемент НЕ 6 и группу элементов И 4, дополнительно введены вычитающий счетчик 14, дополнитель- ньй элемент НЕ 17, элемент И 15 и элемент ИЛИ 16. Упорядочивание чисел производится за счет отождествления величины числа с кодом адреса ячейки блока памяти, в которую записывается единичный код. Введение вычитающего счетчика, в который записывается код искомого по величине числа (числа заданного ранга), позволяет при наличии любого числа в последовательности уменьшать его содержимое на единицу. При нахождении искомого по величине числа вычитающий счетчик обнуляется и за счет элементов И и ИЛИ фомируется разрешающий сигнал, по которому на выход устройства выдается это число. 1 ил. S ел со О 00 4 14)