Устройство для сортировки чисел

 

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

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

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

РЕСПУБЛИК („)SU(„) 15968 А1

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЕ,, К ABTOPCHOMY СВИДЕТЕЛЬСТВУ

Ф ние цели изобретения. Целью изобретения является расширение области применения за счет упорядочения чисел в заданном диапазоне. Сортировка чисел может выполняться как в (21) 4011138/24-24 (22} 14.01.86 (46) 07, 06. 87, Бюл. ¹ 21 (72) В.Г.Попов, О.В.Михайлов и А.10.Дубров (53) 681.325.5 (088.8) (56) Авторское свидетельство СССР. № 981988, кл. G 06 F 7/06, 1980.

Авторское свидетельство СССР

N 1092494, кл. G 06 F 7/06, 1983. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано при реализации систем обработки данных и автоматизированных систем управления. Устройство содержит регистры, схемы сравнения, группы элементов И, регистр результата, счетчик, сумматор, два блока элементов И, группу схем запрета.

Новым в устройстве является использование регистров верхней и нижней границ диапазона, групп элементов И, элементов ИЛИ, двух регистров, дополнительной схемы сравнения, элемента

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

1315968

i0

i5

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

Устройство содержит регистр 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 опроса устройства, выходы 35. отсортированного числа устройства, .выходы 36 адреса числа устройства, выходы 37 размера массива устройства, выход 38 разрешения считывания устройства, Рассмотрим принцип построения и работу устройства.

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

Устройство может использоваться в двух режимах сортировки чисел. В

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

Для задания второго режима сортировки чисел в регистр 25 принимается двоичный код числа нижней границы диапазона, а в регистр 22 — двоичный код числа верхней границы диапазона, Варьируя значениями границ диапазона, можно задавать либо сортировку чисел, меньших наперед заданного путем установки в состояние "0" регистра 25, а в регистре 22 — двоичного кода верхней границы, либо сортировку чисел, больших наперед заданного, путем установки границы в регистре 25, а разряды регистра 22 — в состояние "1".

Пусть необходимо выполнить сортировку чисел в заданном диапазоне.Для этого в регистрах l размещается массив исходных чисел, в регистре 25 граница нижнего допуска (число а „г), а в регистре 22 — граница верхнего диапазона (а 8 ) .

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

"1" одноименных разрядов регистров

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

Регистр 12 предназначен для поочередного анализа содержимого регистра

1, номера которых однозначно соответствуют номерам разрядов регистра

12, установленных в состояние "1".

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

13.15968 где А;

N °

К.

Адреса Содержимое ячеек ячеек папамяти мяти

2А7

ЗА, Э

5А8

6À

7А„

0 в состояние "1". При этом нулевым сигналом с нулевого выхода триггера

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

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

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

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

А =А„+Ы1.+К; (=1,2,...,з), адрес памяти в i-м цикле работы устройства, количество чисел, меньших

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

1 ю

При этом значение А„ подается в сумматор 6 по входам 33, а сумма N1 +

+К формируется счетчиком 5. 35

Номер ре- Содержимое гистров 1 регистров 1

Количество импульсов опроса опре- деляется количеством чисел, больших. а„, о чем свидетельствует число разрядов регистров 10 и 12, установленных в состояние "1" на первом этапе.

По окончании каждого цикла опроса производится установка в "0" соответствующего разряда регистра 12 и увеличение на единицу содержимого счетчика 29 при выдаче ненулевой информации на выходы 35.

Момент окончания работы устройства определяется нулевым состоянием регистра 12. При этом в счетчик 29 фиксируется количество отсортированных чисел, а триггер 28 устанавливается в состояние "0". Единичный сигнал с нулевого выхода триггера, поступающий на выход 39 устройства, используется в качестве сигнала конца сортировки массива чисел.

Рассмотрим работу устройства при п=8 и следующих числах, принятых в регистры 1: а=9 а=7 a=3 а-=2 а=1 а=3

1 2 Э Ь 4 1 в а8=4.

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

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

1315968

После приведения устройства в исходное состояние в регистры 1, 22 и

25 применяются двоичные коды укаэанных соответствующих чисел.

Так как триггер 28 находится в нулевом состоянии, то единичным сигналом с его нулевого выхода открыты элементы И 26, и число ац„ =-1 сравнивается в схемах 2,...,28 сравнения с содержимым соответствующих регистров 1. При этом на выходах "Больше" всех схем сравнения, кроме 2, формируются единичные сигналы, поступающие на первые входы элементов И 9.

На первом входе элемента И 96 присутствует нулевой сигнал с выхода

"Больше" схемы 2 сравнения.

По импульсу запуска через открытые элементы И 9 устанавливаются в

"1" соответствующие разряды регистров 10 и 12,. Элементы ИЛИ 11 обеспечивают парафазный способ установки в "1" разрядов регистра 12 для более быстрого переключения состоя25 ния триггеров. Таким образом на выходах регистров 10 и 12 устанавливается следующий код: 11 111011.

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

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

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

2 сравнения.

Нулевым сигналом с нулевого выхо— да триггера 12, закрываются элементы 15„ 15> запрета, на выходах которых устанавливаются нулевые сигналы. Поэтому открыты только элемен-. ты И 3„ единичным сигналом с единичного выхода триггера 12,. Двоичный код числа 9 иэ регистра iz передают— ся в регистр 4 и на вторые входы схем

2,...,2 сравнения, которые формиру45 ют единичные сигналы на выходах "Меньше".. Так как на вторых вхоцах схемы

2„ сравнения нулевая информация, то на выходе "Больше" — единичная. Таким образом, на первых входах элементов И 7 сформирован код 01111111 выходными сигналами с выходов "Меньше" схем 2„,...,28 сравнения, а на вторых — код 11111011 с выходов ре55 гистра 10. При этом значение N равно 6. Так как на выходах "Равно" всех схем 2 сравнения сигналы отсутствуют, то значение К„=О. Поэтому сумматором формируется адрес ячейки памяти

A =1+6+0=7

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

O разрешается подача импульсов ойроса на вход 34 устройства.

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

Поэтому первый импульс опроса поступает только через открытый элемент И 19. Этим сигналом через элемент И 16 на выходы 36 передается двоичный код адреса A„, сопровождаемый управляющим сигналом с выхода

38. По сигналу с выхода 38 устройства в 3НМ адресная информация с выходов 36 и числовая информация с выходов 35 принимается для записи в память. Так как элемент И 18 закрыт, то но адресу A„ в память будет записана нулевая информация.

Через некоторое время задержки, определяемое временем для надежного приема информации с выходов 36 и

35 в ЭВМ, сигналом опроса через элемент 20 задержки, открытый элемент И

14, и элемент ИЛИ ii„ устанавливает ся в "0" триггер 12, . При этом единичным сигналом с его нулевого выхода. открываются элементы И 15„ и 15 по соответствующим входам, а нулевым сигналом с нулевого выхода триггера

12K закрываются элементы И 152,...

И 15 . На выходах регистра 12 устанавливается следующий код: 01111011.

Так как í- выходах элементов И 15 сформирован код 1000000. то единичным сигналом с выхода элемента И 15„ открыты элементы И 3, и код числа

7 с выходов регистра 1 сравнивается во всех схемах сравнения, кроме

Z,,с содержимым соответствующих регйстров. При этом в сумматоре 6 ана 315968 логично рассмотренному формируется адрес А2

А = 1+5+0=6.

Так как в регистре 22 находится код числа 9, а в регистре 4 код числа 7, то на выходе "Меньше" схемы 23 сравнения устанавливается единичный сигнал, которым по второму входу открывается элемент И 18. Поэтому по очередному импульсу опроса, поступающему по входу 34, через открытые элементы И 18 и 19 на выходы 36 через элементы И 16 передается в ЭВМ код адреса А2> а на выходы 35 че15 рез элементы И 17 — код числа 7 из регистра 4. Одновременно сигналом с выхода элемента И 19, поступающим на выхоп 38 устройства, аналогично рассмотренному обеспечивается прием адресной и числовой информации в ЭВМ.

Сигналом с выхода элемента 20 задержки через открытый элемент И 14 и элемент ИЛИ 11 устанавливается в

"О" триггер 12 . При этом на выходе

2 регистра 12 формируется код 00111011, а на выходах элементов И 15 — код

0100000. На выходе элемента И-НЕ 13 удерживается единичный сигнал, которым поддерживается в открытом сос= тоянии элемент И 18 по третьему входу, а,в закрытом состоянии — элемент

И 27 по инверсному входу.

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

2 сравнения и на выходах Равно

11 11 40 схем 24 и 2 сравнения формируются единичные сигналы.

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

Так как на вторых входах элементов

И 8 присутствует код 00111011, то элементы И 8 и 8 открыты, поэтому К =2.

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

А =1+1+2=4

По очередному импульсу опроса в

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

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

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

К сигналы с выходов "Равно" схем 2 сравнения.

С учетом того, что единичный сигнал с выхода 11Меньше11 схемы 2 сравнения из формирования адреса исключен, величины кодов адресов имеют вид:, A+=1+1+1=3, 1

А,=1+О+О=1

Так как триггер 12 на первом этапе остался в состоянии "011 то анализ содержимого регистра 2 исключается. Поэтому по очередному импульсу опроса формируется А

А =1+1+0=2, а затем по следующему импульсу oIIpoca — As

А1=1+4+0-=5

По седьмому импульсу опроса в счетчике 29 формируется код числа

6, все триггеры регистра 12 оказываются в состоянии "О". При этом на выходе элемента И-НЕ 13 формируется нулевой сигнал, закрывающий элемент И 18 по третьему входу и открывающий элемент И 27 по инверсному входу. По завершении переходных процессов в элементах И 14 и ИЛИ 1

11, .регистре t2 элементе И-HE 13 задержанным импульсом опроса с выхода элемента 21 задержки через открытый элемент И 27 устанавливается в

"0" триггер 28. Единичный сигнал с нулевого выхода триггера 28 поступает на выход 39 и используется в ЭВМ в качестве сигнала завершения сортировки массива чисел. По этому сигна пу в ЭВМ может использоваться значение двоичного кода количества чисел, записанных в памяти, с выхода 37.

Для сортировки чисел в пределах всего массива в регистре 25 устанавливается нулевой код, а в регистре

22 — максимальное значение кода.При этом на первом этапе все триггеры регистров 10 и 12 устанавливаются в"

"1" и сортировка чисел производится за п импульсов опроса.

9 1315968

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

Устройство для сортировки чисел, содержащее и регистров, (n — число сортируемых чисел), и схем сравнения, п групп элементов И, счетчик, сумматор, две группы выходных элементов И, регистр результата и группу из (п-1) элементов запрета, причем выходы разрядов i-ro регистра 10 (i=1,2,...,n) соединены с первой группой входов i-й схемы сравнения и с первыми входами элементов И i-й группы, выходы которых соединены с (i-i)-ми группами входов схем сравнения с первой по (i-1)-го, с i-ми группами входов схем сравнения с ((i+1) -й по п-ю.и с i-й группой входов регистра результата, выходы разрядов которого соединены с пер- 20

Ю выми входами выходных элементов И первой группы, выходы которых являются выходами отсортированного числа устройства, выходы разрядов счетчика соединены с первой группой входов сумматора, вторая группа входов которого соединена с входами начального адреса устройства, а выходы— с первыми входами выходных элементов И второй группы, выходы которых являются выходами адреса отсортированного числа устройства 1-е инверс1 ные входы элементов запрета группы, где 1= 1,2,...,j, j=1,2,...,п-1,обьединены, о т л и ч а ю щ е е с я тем, З5 что, с целью расширения области применения за счет возможности сортировки чисел в заданном диапазоне, в него ввецены регистры верхней и нижней границ диапазона, группа элементов И перезаписи нижней границы диапазона, четыре группы элементов И переписи, два и-разрядных регистра, и элементов ИЛИ, элемент И-НЕ, счетчик размера массива, три элемента И, три элемента задержки, триггер, дополнительная. схема сравнения, причем вход запуска устройства соединен с первыми входами элементов И переписи первой группы и через первый элемент задержки с входом установки в единичное состояние триггера, инверснвый выход которого является выходом конца сортировки устройства и подключен к первым входам элементов И переписи нижней границы диапазона, вторые входы которых соединены с выходами разрядов регистра нижней границы диапазоа, входы которого являются входами задания нижней границы диапазона уст- ройства, выходы элементов И переписи нижней границы диапазона подключены к дополнительным группам входов всех схем сравнения, выход "Больше" i-й схемы сравнения подключен к второму входу i-го элемента И переписи первой группы, выход которого соединен с входами установки в единичное состояние i-го разряда первого и второго и-разрядных регистров, прямой выход i-ro разряда первого п-разрядного регистра соединен с первым входом

i-ro элемента И переписи второй группы, второй вход которого подключен к выходу "Меньше" i-й схемы сравнения, выход "Равно" которой соединен с первым входом i-го элемента И переписи третьей группы, второй вход которого соединен с прямым выходом i-го разряда второго п-разрядного регистра, инверсный выход 1-ro разряда которого соединен с 1-м инверсным входом j --го элемента запрета группы и с 1-м входом элемента И-НЕ, выход которого соединен с первым входом первого элемента И и первым инверсным входом второго элемента И, выход которого подключен к входу установки в "0" триггера, прямой выход которого подключен к второму входу первого элемента И и первому входу третьего элемента И, второй вход которого объединен с третьим входом первого элемента И и является входом опроса устройства, а выход является выходом разрешения считывания устройства и подключен к вторым входам выходных элементов И второй группы и входу второго элемента задержки, выход которого подключен к первым входам элементов И переписи четвертой группы и через третий элемент задержки соединен с вторым входом второго элемента И, выходы элементов И переписи второй и третьей групп соединены соответственно с первой и второй группами входов счетчика, инверсный выход i-го разряда первого и-разрядного регистра соединен с первым входом i-го элемента ИЛИ, второй вход которого соединен с выходом i-ro. элемента И переписи четвертой группы, а выход подключен к входу установки в "0" i-го разряда второго п-разрядного регистра, прямой вход j-го элемента запрета группы подключен к пря1315968!

Составитель Е.Иванова

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

Корректор M.Äåì÷èê

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

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

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

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

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