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

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

Цель изобретения расширение области применения за счет возможности сортировки чисел в заданном диапазоне.

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

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

Рассмотрим принцип построения и работу устройства.

Исходное состояние устройства характеризуется тем, что триггер ч28, регистры 10 И 12 и счетчик 29 установлены в состояние О (не показано) .

Устройство может использоваться в двух режимах сортировки чисел. Б первом из них. сортируются числа в пределах всего исходного массива, принятого в регистры 1, а во втором - в заданном диапазоне. Режим сортировки устанавливается по содержимому регистра 25 нижней границы диапазона и регистра 22 верхней границы диапазона. При этом для задания первого режима все разряды регистра 25 устанавливаются в состоя

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

Для задания второго режима сортировки чисел в регистр 25 принимается двоичный код числа нижней границы диапаз она, а в регистр 22 - двоичньш код числа верхней границы диапазона. Варьируя значениями границ диапазона, можно задавать либо сортировку чисел, меньших наперед заданного путем установки в состояние О регистра 25, а в регистре 22 - двоичного кода верхней границы, :пибо сортировку чисел, больших наперед заданного, путем установки границы в регистре 25, а разряды регистра 22 - в состояние 1. Пусть необходимо выполнить сортировку чисел в заданном диапазоне,Для этого в регистрах 1 размещается массив исходных чисел, в регистре 25 - граница нижнего допуска (число ), а в регистре 22 - граница верхнего

диапазона (agr)Работа устройства разделяется на два этапа. Первый этап начинается по сигналу запуска, поступающему по входу 32. Так как триггер 28 установлен в состояние О, то единичным сигналом с его нулевого выхода открыты элементы границы И 26. При этом на вторые входы всех схем 2 сравнения подается двоичный код регистра 25. На первые входы схемы сравнения поступает двоичньй код из соответствующего регистра 1 , Схемы 2. сравнения, на первых входах которых код числа массива больше заданного

0

5

, формируют на выходах Больше единичные сигналы, поступающие на первые входы соответствующих элементов И 9. При наличии сигнала запуска происходит установка в состояние 1 одноименных разрядов регистров 10 и 12 через открытые соответствующие элементы И 9. Таким образом, с помощью регистра 10 в дальнейшем разрешается участие в сортировке чисел,

„ больших величин а,,г i 0

Регистр 12 предназначен для поочередного анализа содержимого регистра 1, номера которых однозначно соответствуют номерам разрядов регистра 12, установленных в состояние 1.

Через некоторое время задержки, определяемое переходными процессами в элементах И 9, через элемент 24 задержки триггер 28 устанавливается

3,

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

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

Адрес ячейки формируется в сумматоре 6 по следующему выражению:

A,. (,2,.,,,s),

где А. - адрес памяти в i-м цикле

работы устройства, N. - количество чисел, меньших анализируемого числа в i-м цикле, К. - количество чисел, равных

анализируемому числу в i-м цикле,

S - количество чисел, больших

нгПри этом значение АН подается в сумматор 6 по входам 33, а суммаN;+ +K. формируется счетчиком 5.

159684

Количество импульсов опроса определяется количеством чисел, больших-. , о чем свидетельствует число разрядов регистров 10 и 12, установлен- 5 ных в состояние 1 на первом этапе. По окончании каждого цикла опроса производится установка в О соответствующего разряда регистра 12 и увеличение на единицу содержимого счетчика 29 при вьщаче ненулевой информации на выходы 35.

Момент окончания работы устройства определяется нулевым состоянием регистра 12. При этом в счетчик 29 ,,

10

15

20

25

30

фиксируется количество отсортированных чисел, а триггер 28 устанавливается в состояние О. Единичный сигнал с нулевого выхода триггера, поступающий на выход 39 устройства, используется в качестве сигнала конца сортировки массива чисел.

Рассмотрим работу устройства при и следующих числах, принятых в регистры 1:

, , , , , .

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

При этих условиях раббта устройства отражена в таблице, в которой стрелками показано напряжение запи- си чисел из регистров 1 в память.

Изобретение относится к автоматике и вычислительной технике и может быть использовано при реализации систем обработки данных и автоматизированных систем управления. Устройство содержит регистры, СХЕМЫ сравнения, группы элементов И, регистр результата, счетчик, сумматор, два блока элементов И, группу схем запрета. Новым в устройстве является использование регистров верхней и нижней границ диапазона, групп элементов И, элементов ИЖ, двух регистров, дополнительной схемы сравнения, элемента И-НЕ, трех элементов задержки, счетчика размера массива, трех элементов И, блока элементов И, триггера и их связей, что обеспечивает достижение цели изобретения. Целью изобретения является расширение области применения за счет упорядочения чисел в заданном диапазоне. Сортировка чисел может выполняться как в пределах всего исходного массива, так и в заданном диапазоне. Режим сортировки устанавливается варьированием чисел в регистрах нижней и верхней границ диапазона. Работа устройства состоит из двух этапов. На первом этапе определяется ограничительный массив, подлежащий упорядочению, путем поочередного сравнения заданной нижней границы с каждым из чисел исходного массива. На втором этапе по импульсам опроса производится формирование адреса памяти для размещения анализируемого числа по сигналам со схем сравнения группы Меньше и Равно. При вьздаче из устройства число сравнивается с верхней границей. Если оно превышает установленное значение, то одно- f временно с адресом производится выдача нулевого числа для записи. Работа устройства завершается по окон- чании просмотра всех чисел массива, ограниченного на первом этапе. 1 ил., 1 табл. i 00 01 CD О 00

1 2 3 4 .5 6 7 8

9

7 3 3 2 1 3 4

2 3 3 3 4 7 О

51

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

Так как триггер 28 находится в нулевом состоянии-, то единичным сигналом с его нулевого выхода открыты элементы И 26, и число сравнивается в схемах 2,...,2д сравнения с содержимым соответствующих регистров 1. При этом на выходах Больше всех схем сравнения, кроме 2, формируются единичные сигналы, поступающие на первые ВХОДЫ элементов И 9. На первом входе элемента И 9 присутствует нулевой сигнал с выхода Больше схемы 2 сравнения.

По импульсу запуска через открытые элементы И 9 устанавливаются в 1 соответствующие разряды регистров 10 и 12.- Элементы Ш1И 11 обеспечивают парафазный способ установки в 1 разрядов регистра 12 для более быстрого переключения состояния триггеров. Таким образом на выходах регистров 10 и 12 устанавливается следующий код: 1.1111011.

Одновременно с установкой в 1 триггеров регистров 10 и 12 задержанным сигналом запуска элементом

24задержки устанавливается в 1 триггер 28, блокируя тем воздействие выходных сигналов регистра

25через элементы И 26 на все схемы 2 сравнения.

Нулевым сигналом с нулевого вько- да триггера 12 закрываются элементы 15,..., 15, запрета, на выходах которых устанавливаются нулевые сигналы. Поэтому открыты только элементы И 3 единичным сигналом с единичного выхода триггера 12.,. Двоичный код числа 9 из регистра 1j передаются в регистр 4 и на вторые входы схе 22,...,2g сравнения, которые формируют единичные сигналы на выходах Менше .. Так как на вторых входах схемы 2 сравнения нулевая информация, то на выходе Больше - единичная. Таким образом, на первых входах элементов И 7 сформирован код 01111111 выходными сигналами с выходов Меньше

схем 2,...,2g сравнения, а

на

вторых - код 11111011 с выходов регистра 10. При этом значение N., равно 6. Так как на выходах Равно всех схем 2 сравнения сигналы отсутствуют, то значение К-)0. Поэтому сумма5968

5

0

5

0

5

0

5

0

тором формируется адрес ячейки памяти

А 1+6+0 7.

После завершения переходных процессов в сумматоре 6 по нулевому сигналу с выхода 39 устройства в ЭВМ разрешается подача импульсов опроса на вход 34 устройства.

Так как на входы элемента И 13 подаются сигналы с нулевых выходов регистра 12, то на его выходе формируется единичный сигнал, открывающий элемент И 18 по третьему входу. Единичным сигналом с единичного выхода триггера 28 открыты по первым входам элементы И 18 и И 19. Так как в регистре 4 находится код числа 9, а в регистре 22 такой же код, то на выходе Меньше схемы 23 сравнения формируется нулевой сигнал, закрывающий элемент И 18.

Поэтому первый импульс опроса поступает только через открытый элемент И 19. Этим сигналом через элемент И 16 на выходы 36 передается двоичный код адреса А., , сопровождаемый управляю1цим сигналом с выхода 38. По сигналу с выхода 3S устройства в ЭВМ адресная информация с выходов 36 и числовая информация с выходов 35 принимается для записи в память. Так как элемент И 18 закрыт, то по адресу в память будет записана нулевая информация.

Через некоторое время задержки, определяемое временем для надежного приема информации с выходов 36 и 35 в ЭВМ, сигналом опроса -через элемент 20 задержки, открытый элемент И 14., и элемент ИЛИ 11 устанавливает- ся в О триггер 12 . При этом еди- ничнь м сигналом с его нулевого выхо- да открываются: элементы И 15., и 15 по соответствующим входам, а нулевым сигналом с нулевого выхода триггера 122 закрываются элементы И 15,, . . ., И 15. На выходах регистра 12 устанавливается следующий код: 01111011.

Так как на выходах элементов И 15 сформирован код 1000000, то единичным сигналом с выхода элемента И 15 открыты элементы ИЗ,, и код числа 7 с выходов регистра 1 сравнивается во всех схемах сравнения, кроме 2. 5 с содержимым соответствующих, регистров. При этом в сумматоре 6 аналогично, рассмотренному формируется адрес А

А2 И-5+0 6.

Так как в регистре 22- находится код числа 9, а в регистре 4 код числа 7, то на выходе Меньше схемы 23 сравнения устанавливается единичный сигнал, которым по второму входу открывается элемент И 18. Поэтому по очередному импульсу опроса, поступающему по входу 34, через открытые элементы И 18 и 19 на выходы 36 через элементы И 16 передается в ЭВМ

код адреса А2, а на выходы 35 через элементы И 17 - код числа 7 из региЬтра 4. Одновременно сигналом с выхода элемента И 19, поступающим на выход 38 устройства, аналогично рассмотренному, об еспечивается прием адресной и числовой информации в ЭВМ.

Сигналом с выхода элемента 20 задержки через открытый элемент И 14 и элемент ИЛИ 11 устанавливается в О триггер 12 , При этом на выходе регистра 12 формируется код 00111011 а на выходах элементов И 15 - код 0100000, На выходе элемента И-НЕ 13 удерживается единичный сигнал, ко- торым поддерживается в открытом соетоянии элемент И 18 по третьему входу, а закрытом состоянии - элемент И 27 по инверсному входу.

Единичным сигналом с выхода элемента И 1 Sj. открыты элементы И Зд , и двоичный код числа 3 сравнивается в схемах сравнения, кроме 2, с ко-. дами соответствующих регистров 1.При этом на выходах Меньше схем 25 и 2 сравнения и на выходах Равно схем 24 и 2 сравнения фор шруются единичные сигналы.

Так как на вторых входах элементов И 8 присутствует код 11111011, то элемент И 7 закрыт, поэтому Nj 1

Так как на вторых входах элементо И 8 присутствует код 00111011, то элементы И 84. и 8-j открыты, поэтому ., .

Исходя из этого в сумматоре 6 фор мируется двоичный код Aj

АЗ 1+1+2 4.

По очередному импульсу опроса в ЭВМ выдается код Aj и код числа 3, триггер 12j устанавливается в О, а в счетчике 29 формируется код числа 2.

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

Поочередная установка в О триггеров регистра 12 последовательно исключает при формирования величины К сигналы с выходов Равно схем 2 сравнения.

С учётом того, что единичный сигнал с выхода Меньше схемы 2g сравнения из формирования адреса исключен, величины кодов адресов имеют вид:

.А4 1+1+1 3,

Aj 1+0+0 1.

Так как триггер. 12 на первом

этапе остался в состоянии

то

0

5

0

5

анализ содержимого регистра 2 исключается. Поэтому по очередному импульсу опроса фop шpyeтcя А.

+

а затем по следующему импульгу опроса - Ag

Ag 1+4+0 5.

По седьмому импульсу опроса в счетчике 29 формируется код числа 6, все триггеры регистра 12 оказываются в состоянии О. При этом на выходе элемента И-НЕ 13 формируется нулевой сигнал, закрывающий элемент И 18 по третьему входу и открывающий элемент И 27 по инверсному входу. По завершении переход- ньк процессов в элементах И 14 и ИЛИ/ 11, регистре 12, элементе И-НЕ 13 задержанным импульсом опроса с выхода элемента 21 задержки через откры- тьй элемент И 27 устанавливается в О триггер 28. Единичный сигнал с нулевого выхода триггера 28 поступает на выход 39 и используется в ЭВМ в качестве сигнала завершения сортировки массива чисел. По этому сигна- шу в ЭВМ может использоваться значение двоичного кода количества чисел, записанных в памяти, с выхода 37,

Для сортировки чисел в пределах всего массива в регистре 25 устанавливается нулевой код, а в регистре 22 - максимальное значение кода.При этом на первом этапе все триггеры регистров 10 и 12 устанавливаются в - 1 и сортировка чисел производится за п импульсов опроса.

913

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

Устройство для сортировки чисел, содержащее п регистров, (п - число сортируемых чисел), п схем сравнения, п групп элементов И, счетчик, сумматор, две группы выходных элементов И, регистр результата и группу из (п-1) элементов запрета, причем выходы разрядов i-ro регистра (,2,...,п) соединены с первой группой входов i-й схемы сравнения и с первыми входами элементов И i-й группы, выходы которых соединены с (i-1)-ми группами входов схем сравнения с первой по (i-1)-го, с i-ми группами входов схем сравнения с ((i+1)-й по п-ю.и с i-й группой входов регистра результата, выходы разрядов которого соединены с первыми входами выходных элементов И первой группы, выходы которых являются выходами отсортированного числа устройства, выходы разрядов счетчика соединены с первой группой входов сумматора, вторая группа входов которого соединена с входами начального адреса устройства, а выходы - с первыми входами выходных элементов И второй группы, выходы которых являются выходами адреса отсортированного числа устройства 1-е инверсные входы элементов запрета группы, где ,2,,,.,j, j 1,2,. ,..,n-1 oбьe- динeны, отличающееся тем, что, с целью -расширения области применения за счет возможности сортировки чисел в заданном диапазоне, в него введены регистры верхней и нижней границ диапазона, группа элементов И перезаписи нижней границы диапазона, четыре группы элементов И переписи, два п-разрядных регистра, п элементов ИЛИ, элемент И-НЕ, счетчик размера массива, три элемента И, три мента задержки, триггер, дополнительная, схема сравнения, причем вход запуска устройства соединен с первыми входами элементов И переписи первой группы и через первый элемент задерж ки с входом установки в единичное состояние триггера, инверснвый выход которого является выходом конца сортировки устройства и подключен к пер вым входам элементов И переписи нижней границы диапазона, вторые входы которых соединены с выходами разрядов регистра нижней границы диапазо25

596810

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

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

О с входами установки в единичное состояние i-ro разряда первого и второго п-разрядных регистров, прямой выход i-ro разряда первого п-разрядно- го регистра соединен с первым входом

5 i-ro элемента И переписи второй группы, второй вход которого подключен к выходу Меньше i-й схемы сравнения, выход Равно которой соединен с первым входом i-ro элемента И переписи

20 третьей группы, второй вход которого соединен с прямым выходом i-ro разряда второго п-разрядного регистра, инверсный выход 1-го разряда которого соединен с Г-м инверсным входом j -го элемента запрета группы и с входом элемента И-НЕ, выход которого соединен с первым входом первого элемента И и первым инверсным входом второго элемента И, выход которого подключен к входу ус- . тановки в О триггера, прямой выход которого подключен к второму входу первого элемента И и первому входу третьего элемента И, второй вход

35 которого объединен с третьим входом первого элемента И и является входом : опроса устройства, а выход является выходом разрешения считывания устройства и подключен к вторым входам выходных элементов И второй группы и входу второго элемента задержки, выход которого подключен к первым входам элементов И переписи четвертой группы и через третий элемент, задержки соединен с вторым входом второго элемента И, выходы элементов И переписи второй и третьей групп соединены соответственно с первой и второй группами входов счетчика, инверсный выход i-ro разряда первого п-разрядного регистра соединен с первым входом i-ro элемента ИЛИ, второй вход которого соединен с выходом i-ro. элемента И переписи четвертой группы, а выход подключен к входу установки в О i-ro разряда второго п-разрядного регистра, прямой вход j-ro элемента запрета группы подключен к пря30

40

45

50

55

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

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

Составитель Е.Иванова Редактор С.Пекарь Техред Л.Олийнык

Заказ 2363/50 Тираж 672Подписное

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

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

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

Корректор М.Демчик