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

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

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

Устройство содержит распределитель 1 импульсов, регистры 2, элементы 3 сравнения, группы входных элементов И 4, группы выходных элементов И 5 и 6, счетчик 7, сумматор 8, регистр 9 результата, дешифратор 10, группу элементов ИЛИ 11, шифратор 12, элементы И 13, 14, триггер 15 управления, элемент И 16, генератор 17 импульсов, дешифратор 18, ассоциативные регистры 19, группы элементов И 20 переписи, группу элементов И 21, элемент 22 задержки, группу элементов ИЛИ 23, элементы 24 запрета, группы элементов И 25 результата, группу элементов ИЛИ 26, элемент ИЛИ-НЕ 27, выход 28 разрешения выдачи, вход 29 запуска, выходы 30, вход 31 разрешения вьщачи, выход 32 конца работы, выходы 33, вход 34 задания начального адреса устройства

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

Исходное состояние устройства характеризуется тем, что распределител 1 импульсов, триггер 15 управления и регистры 19 установлены в состояние О (не показано).

Сортировка чисел устройством совместно с ЭВМ производится в два этапа.

На первом этапе после принятия исходного массива в регистры 2 и по входам 34 в сумматор 8 по сигналу ПУСК, поступающему по входу 29, триггер 15 управления устанавливается в состояние 1. После этого производится поочередное сравнение чисел, и в ассоциативных регистрах 19 фиксируются номера регистров 2 так, что они отражают размещение чисел исходного массива в возрастающем порядке.

Пусть при в регистрах 2 размещен следующий массив чисел:

„ ;С . 1 .

г i

а ) ..

dj, J ,cto I ,

aj.6; a,.

a, 2;

.5;

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

(

и число из

регистра /, передается в регистр 9

открываются элементы И

2,

результата и одновременно сравнивается со всеми числами, находящимися в регистрах 2-...2,0, в соответствую

щих элементах 3.,.3 сравнения. На выходах Меньше элементов 3 и Зо сравнения формируются единичные сигналы, а в счетчике 7 - значение .

При этом на третьем выходе дешифратора 18 возникает единичный сигнал, открывающий элементы И 20 . Одновременно единичный сигнал с первого выхода распределителей 1 поступает на

шифратор 12, на выходе которого формируется двоичный код числа 1. Так как триггер 15 установлен в состояние 1, то двоичный код номера регистра 2j т.е. выходные сигналы шифратора 12, записывается в регистр 19j.

По второму, очередному импульсу генератора 17 на втором выходе распределителя 1 формируется сигнал, и число сравнивается во всех

элементах 3| сравнения, кроме 3.2. При этом единичные сигналы на выходах Меньше формируют элементы 3,, 3j, 3, 3, 3g, и 3, сравнения и аналогичным образом номер регистра 2 и так далее т.е. двоичный код числа два будет записан в регистр 19f. Дальнейшая работа устройства аналогична. По десятому импульсу с распределителя 1 в регистрах 19 будут записаны номера регистров 2, однозначно соответствующие возрастающему порядку размещения в них чисел. Так для указанного примера в регистрах 19 размещены следующие номера регистров 2: 19)9; . 19,о 7, что. отражает порядок возрастания чисел - 1-7.

По сигналу с 10-го выхода распределителя очередным импульсом генера- тора 17 устанавливается в О триг- . гер 15, и элементом И 14 на выходе 28 формируется единичный сигнал, как готовности устройства к выдаче отсортированного массива чисел. Одновременно устанавливается в О распределитель 1.

Второй этап работы устройства начинается при приходе сигнала на

вход 31.

До поступления данного сигнала после того, как триггер 15 установился в состояние О, на выходах элементов ИЛИ 23 формируется следующий позиционный код в соответствии с содержимым регистров 19: :1010111011. Посредством элементов запрета 24, соединенных по приоритетной схеме, этот код преобразуется в позиционный код следующего вида: 1000000000, так как единичным сигналом с выхода элемента ИЛИ 23 по инверсным входам закрываются элементы 24 запрета.

По единичному сигналу с выхода элемента ИЛИ 23,- открываются элементы И 25, и двоичный код из регист ра 19,, т.е. код числа 9, через элементы И 25, и ИЛИ 26 поступает на дешифратор 10. Так как триггер 15 находится в О, то по входу управления дешифратор 10 открыт, и на его 9-м выходе формируется единичный сигнал, которым через элемент ИЛИ 11д открыты элементы И 4, . Со-- держимое регистра 2, через эти элементы передается в регистр 9 резуль- тата, в котором фиксируется число а. 1 .

По -сигналу с входа 31 через элементы И 5 выдается двоичный код Ац(,,ц из сумматора 8 по выходам 33, а через элементы И 6 на выходы 30 - содержимое регистра 9 результата. По адресу А,А j, число Яд } записывается в ячейку внешней памяти.

Через время с , определяемое зле- ментом 22 задержки, устанавливается в О регистр 19, через открытый элемент И 21 , . Одновременно в сумма тор 8 формируется очередной адрес . Время Т выбирается таким, чтобы обеспечить надежное считывание выходных сигналов элементов И 5, 6 ЭВМ.

После установки в О регистра 191 на выходах элементов ИЛИ 23 формируется позиционный код 0010111011, преобразуемый элементами И 24 в код 0010000000. Единичным сигналом с выхода элемента И 24 открываются элементы И 25, и содержимое регистра 19 , т.е. двоичный код номера регистра 2. передается через элементы И 25} и ИЛИ 26 на дешифратор 10. На четвертом выходе дешифратора 10 формируется единичный сигнал, которы через элемент ИЛИ 11 открывает элементы И 4 4 , и содержимое регистра

2 () фиксируется в регистре 9 результата.

По импульсу с входа 31 код адреса Л и двоичный код числа 2 из регистра 9 передается во внешнее устройство.

Через время регистр 19 устанавливается в О, -и работа устройства затем аналогична рассмотренной Bbmie.

По седьмому импульсу на входе 31 последнее число а,о 7 вьщается во внешнее устройство и все регистры 19 оказываются в состоянии О. При это н выходе элемента И-НЕ 27 формируется единичный сигнал, поступающий по выходе 32 в качестве сигнала конца работы устройства во втором этапе.

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

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

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

где п- количество сортируемых чисел) соединены с первой группой входов

-го элемента сравнения и с первыми входами соответствующих входных элементов И 4-и группы, выходы которых соединены с л-и группой входов регистра результата и с (4 + 1)-ми группами входов элементов сравнения соответственно с ((+1)-го по п-и, выходы входных элементов И j-и группы, где j 2,3, . . . ,11, соединены с -ми группами входов элементов сравнения соответственно с первого по (-1)-й, выходы регистра результата соединены с первыми входами выходных элементов И первой группы, выход которых являются выходами отсортированного числа устройства, выход неравенства 1-го элемента сравнения соединен с i-м входом счетчика,вход задания начального адреса устройства подключен к первому входу сумматора, выходы которого соединены с первыми входами соответствующих выходных

5

элементов И второй группы, выходы которых являются выходами адреса числа устройства, вторые цходы выходных элементов И первой и второй групп подключены к входу разрр.шения выдачи результата устройства, S в инверсные входы элементов запрета, где ,2...,п-1, объединены, отличающееся тем, что, с целью повышения быстродействия при сортировке массива, содержащего равные числа, в него введены два дешифратора, шифратор, п групп элементов И переписи, п групп элементов И резуль тата, три группы элементов ИЛИ, груп па элемеАтов И, п ассоциативных регистров,- элемент задержки, триггер управления, три элемента И, элемент ИЛИ-НЕ, генератор импульсов, выход которого соединен с первыми входами первого и второго элементов И, второй вход первого элемента И подклю- чен к прямому выходу триггера управления и первым входам элементов И переписи всех групп, а выход соединен с входом запуска распределителя импульсов, 1 -и выход которого соединен с первым входом i то элемента ШШ первой группы и с i -м входом шифратора, п -и выход распределителя импульсов дополнительно подключен к первому входу третьего элемента И и второму входу второго элемента И, выход которого подключен к входу установки в О триггера управления, вход установки в 1 которого является входом запуска устройства, инверсный выход которого соединен с инверсным входом элемента ШШ-НЕ, входом установки в О распределителя импульсов, управляющим входом первого дешифратора и вторым входом третьего элемента И, выход которого является вйвсо- дом разрешения вьщачи устройства, i -и вь1ход первого дешифратора соеди

544676

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

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

20 шифратора соединены с третьими входами сбЪтветствующих элементов И переписи всех групп, j -е инверсные входы каждого S-го элемента запрета (j 1,2,.. .,3; 6 1,) соеди25 йены с выходом -го элемента ИЛИ второй группы, выход первого элемента ИЛИ второй группы соединен с управляющими входами элементов И результата первой группы, с первым

30 входом первого элемента И группы и, с первым входом элемента ШШ-НЕ, выход -го элемента ИЛИ второй группы (J 2,3,..., п) соединен с прямым входом ((|-1)-го элемента запрета и

3J с (-м входом элемента ШШ-НЕ, выход S-ro элемента запрета соединен с управляющими входами элементов И результата (5+1)-й группы и с первым входом (5+1)-го элемента И группы,

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

45 ШШ-НЕ является выходом конца работы устройства.

3) . 32 33

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