Устройство для сортировки @ -разрядных чисел Советский патент 1987 года по МПК G06F7/06 

to

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

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

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

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

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

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

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

В режиме очистки памяти на вход 22 начальной установки устройства подается импульс, устанавливающий счетчики 2 и 7 в нулевое состояние; на

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

Одновременно единичный потенциал с выхода триггера 8 поступает через элемент ИЛИ 10 на вход разрешения за25

адресных и информационных входах бло- 30 писи счетчика 7. Числб из блока 3 пака 3 памяти устанавливаются нулевые потенциалы. Затем на входе 2 Т разрешения записи устанавливается логический нуль, чем запрещается запись в счетчик 2 по входам 20. При установ.се на входах 24 и 25 нулевых потенциалов на первом и втором управляющих входах коммутатора 4 - нулевые потенциалы, в результате чего к выходу коммутатора 4 подключается, его информационный вход, соединенный с генератором 1 импульсов. После этого запускается генератор 1 имйульсов, которьш nocjie выдачи на суммирую1ций вход счетчика 2. пачки из 2 (ш - количество разрядов сортируемых чисел) импульсов переполнения со счетчика 2 остановится. Одновременно на вход управления (за- пись/считьшание) блока 3 памяти через коммутатор 4 и элемент НЕ 5 по- ступает та же инвертированная пачка импульсов записи. После полного просчета счетчика 2 во всех ячейках блока 3 памяти записан нулевой код.

В режиме сортировки на входе 21 разрешения записи устанавливается . единичный потенциал, при этом разрешается запись в счетчик 2 по информаto

; 587382

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

Одновременно единичный потенциал с выхода триггера 8 поступает через элемент ИЛИ 10 на вход разрешения за

мяти, находящееся по адресу, опреде- ляемому содержимым счетчика 2, переписывается в счетчик 7. Тот же такто- вьй импульс, задержанный элементом

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

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

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

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

Очередной импульс с генератора 1 через элемент 15 запрета поступает на суммирующий вход счетчика 2, увеличивая его содержимое на единицу, Этот же импульс через коммутатор 4 и элемент НЕ 5-поступает на управляющий вход блока 3 памяти. При этом число, хранящееся в блоке 3 памяти, по адресу, установленному в счетчике 2, считывается в счетчик 7. Если в счетчик ,7 считано число О, то на выходе элемента ИЛИ 11 сохранится нулевой потенциал, и элементы 14 и 15 запрета останутся открытыми, а элемент И 12 - закрытым, следовательно, на выходы 26 устройства число с выходов счетчика 2 не поступит. Если в счетчик 7 считано число, отличное от нуля, то на выходе элемента ИЛИ 11 появится единичный потенциал, который откроет элемент И 12 и закроет элементы 14 и 15 запрета. При этом снимается сигнал разре- шения записи со счетчика 7 и блокируется суммирующий вход счетчика 2.

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

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

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

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

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

отличающееся тем, что,

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

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

единен с суммирующим входом реверсивного счетчика и, через третий элемент задержки, с вторым информационным входом коммутатора, первый управляющий вход которого подключен к выходу 20 ° второго элементов ИЛИ, выход первого элемента запрета, прямой вход первого элемента ШШ соединен с вто- которого является входом задания режима сортировки устройства, вход за-- даиия режима считывания устройства соединен с первым входом первого эле-25 прета и, через четвертый элемент за- мента ИЛИ и прямым входом второго . держки, с вторым вх:одом элемента И, элемента запрета, выход которого сое- вход установки в нулевое состояние динен с первьм входом второго элемен- реверсивного счетчика подключен к та ИЛИ, выход которого соединен с входу начальной установки устройства, входом разрешения записи реверсивного 30 выход переполнения счётчика соединен счетчика, выход разряда которого с входом останова генератора импуль- (где ,2....,, N - количе- сов.

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

ство сортируемьЬс чисел в массиве,

х - ближайшее целое, не меньшее х)

соединен с j-м входом третьего элемента ИЛИ и с J-M информационным входом блока памяти, выход j-ro разряда которого соединен с j-M информационным входом разряда реверсивного счетчика, вычитающий вход которого подключен к входам элементов И группы и к выходу элемента И, первый вход которого подключен к выходу третьего элемента ИЛИ и к инверсным входам второго и третьего элементов

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

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

рым управляющим рходом коммутатора, выход генератора импульсов соединен с прямым входом третьего элемента за2SO

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

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

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

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

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

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

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

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