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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 15968 ИЗОБРЕТЕНИГ,:,ВИДЕТЕЛЬСТВУ ОПИСАН К АВТОРСКОМ с ЖФ и виз уст верхне ет устанвременно дача нул та уст нии пр ограничен1 табл,ГОСУДАРСТВЕННЫЙ КОМИТЕТ ССС ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫ(54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ(57) Изобретение относится к автоматике и вычислительной технике и может быть использовано при реализации систем обработки данных и автоматизированных систем управления, Устройство содержит регистры, схемы сравнения, группы элементов И, регистр результата, счетчик, сумматор, два блока элементов И, группу схем запрета, Новым в устройстве является использование регистров верхней и нижней границ диапазона, групп элементов И, элементов ИЛИ, двух регистров, дополнительной схемы сравнения, элемента И-НЕ, трех элементов задержки, счетчика размера массива, трех элементов И, блока элементов И, триггера и их связей, что обеспечивает достижение цели изобретения. Целью изобретения является расширение области применения за счет упорядочени сел в заданном диапазоне, Сорт ка чисел может выполняться как пределах всего исходного массива,так и в заданном диапазоне. Режимсортировки устанавливается варьированием чисел в регистрах нижней иверхней границ диапазона, Работа усройства состоит из двух этапов. Напервом этапе определяется ограничительный массив, подлежащий упорядочению, путем поочередного сравнениязаданной нижней границы с каждым изчисел исходного массива, На второмэтапе по импульсам опроса производится формирование адреса памяти длразмещения анализируемого числапо сигналам со схем сравнения грунпы "Меньше" и "Равно". При выдаче тва число сравниваетсяаницей. Если оно превышленное значение, то однадресом производится вого числа для записи. Рйства завершается по ок мотра всех чисел массива ого на первом этапе. 1 ил10 15 20 25 30 35 40 45 50 55 Изобретение относится к автоматике и вычислительной технике и может быть использовано при реализации систем обработки данных и автоматизированных систем управления,Цель изобретения - расширение области применения за счет возможностисортировки чисел в заданном диапазоне,На чертеже приведена структурнаясхема предлагаемого устройства.Устройство содержит регистр 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",Пусть необходимо выполнить сортировку чисел в заданном диапазоне,Для этого в регистрах 1 размещается массив исходных чисел, в регистре 25 граница нижнего допуска (число а г), а в регистре 22 - граница верхнего диапазона (а Вг) .Работа устройства разделяется на два этапа, Первый этап начинается по сигналу запуска, поступающему по входу 32. Так как триггер 28 установлен в состояние "0", то единичным сигналом с его нулевого выхода открыты элементы границы И 26. При этом на вторые входы всех схем 2 сравнения подается двоичный код ан из регистра 25. На первые входы схемы сравнения поступает двоичный код из соответствующего регистра 1, Схемы 2. сравнения, на первых входах которых код числа массива больше заданного анг Формируют на выходах "Больше" единичные сигналы, поступающие на первые входы соответствующих элементов И 9. При наличии сигнала запуска происходит установка в состояние "1" одноименных разрядов регистров 10 и 12 через открытые соответствующие элементы И 9. Таким образом, с помошью регистра 10 в дальнейшем разрешается участие в сортировке чисел, больших величин аРегистр 12 предназначен для поочередного анализа содержимого регистра 1, номера которых однозначно соответствуют номерам разрядов регистра 12, установленных в состояние "1".Через некоторое время задержки, определяемое переходными процессами в элементах И 9, через элемент 24 зацержки триггер 28 устанавливается13.15968 где А,К. Адреса Содержимоеячеек ячеек папамяти мяти ЗА,4 Аэ 2 4 7 8 А в состояние "1",.При этом нулевым сигналом с нулевого выхода триггера 28 блокируется подача двоичного кода а щ на схемы 2 сравнения, чем исключается его воздействие на даль нейшую работу устройства, На этом первый этап работы устройства завершается.Второй этап устройства начинается при наличии нулевого сигнала на10 выходе 39, разрешающего подачу импульсов опроса по входу 34. На этом этапе по каждому импульсу опроса в устройстве формируется адрес ячей 15 ки памяти и код числа, подлежащий записи. Адрес ячейки формируется в сумматоре 6 по следующему выражению:20А =А+Ы+К; (=1,2. . .з),адрес памяти в -м циклеработы устройства,количество чисел, меньших25анализируемого числа в -мцикле,количество чисел, равныханализируемому числу в х-мцикле,количество чисел, большиханг 1ФПри этом значение А подается всумматор 6 по входам 33, а сумма И ++К формируется счетчиком 5. 351 Номер ре- Содержимое гистров 1 регистров 1 Количество импульсов опроса опре-деляется количеством чисел, больших.а , о чем свидетельствует число разрядов регистров 10 и 12, установленных в состояние "1" на первом этапе,По окончании каждого цикла опросапроизводится установка в "О" соответствующего разряда регистра 12 иувеличение на единицу содержимого.счетчика 29 при выдаче ненулевой информации на выходы 35,Момент окончания работы устройства определяется нулевым состояниемрегистра 12. При этом в счетчик 29фиксируется количество отсортированных чисел, а триггер 28 устанавливается в состояние "О". Единичный сигнал с нулевого выхода триггера, поступающий на выход 39 Устройства, используется в качестве сигнала концасортировки массива чисел.Рассмотрим работу устройства прип=8 и следующих числах, принятых врегистры 1: а =9 а =7 а =3 а -=2 а =1 а =3 1 ф 2 ф э ф ь4 ф 1 й а =4. Пусть необходимо получить упорядоченный массив чисел при ан=1,а=9, разместив его в области памяти, начиная с адреса А=1,При этих условиях работа устройства отражена в таблице, в которойстрелками показано напряжение записи чисел из регистров 1 в память.После приведения устройства в исходное состояние в регистры 1, 22 и 25 применяются двоичные коды указанных соответствующих чисел.Так как триггер 28 находится в нулевом состоянии, то единичным сигналом с его нулевого выхода открыты элементы И 26, и число а =-1 сравнивается в схемах 228 сравнения с содержимым соответствующих регистров 1, При этом на выходах "Больше" всех схем сравнения, кроме 2, Формируются единичные сигналы, поступающие на первые входы элементов И 9. На первом входе элемента И 96 присутствует нулевой сигнал с выхода "Больше" схемы 2 сравнения.По импульсу запуска через открытые элементы И 9 устанавливаются в "1 соответтвующе разряды регистров 10 и 12, Элементы ИЛИ 11 обеспечивают парафазный способ установки в " 1" разрядов регистра 12 для более быстрого переключения состоя 25 ния триггеров. Таким образом на выходах регистров 10 и 12 устанавливается следующий код: 11111011.Одновременно с установкой в "1" триггеров регистров 10 и 12 задержанным сигналом запуска элементом 24 задержки устанавливается в " 1" триггер 28 блокируя тем самым воздействие выходных сигналов регистра 25 через элементы И 26 на все схе,ы 2 сравнения.Нулевым сигналом с нулевого выхо - да триггера 12, закрываются элементы 15 15, запрета, на выходах которых устанавливаются нулевые сигналы. Поэтому открыты только элемен-" ты И 3 единичным сигналом с единичного выхода триггера 12,. Двоичный код числа 9 из регистра 11 передают - ся в регистр 4 и на вторые входы схем 2 2 ц сравнения, которые формиру 45 ют единичные сигналы на выходах "Меньше". Так как на вторых вхоцах схемы 2 сравнения нулевая информация, то на выходе "Больше" - единичная. Таким образом, на первых входах элементов И 7 сформирован код 01111111 выходными сигналами с выходов "Меньше" схем 228 сравнения, а на вторых - код 11111011 с выходов ре 55 гистра 10, При этом значение И, равно 6. Так как на выходах "Равно" всех схем 2 сравнения сигналы отсутствуют, то значение К=О, Поэтому сумматором формируется адрес ячейки памятиА,=1+6+0=7После завершенияпереходных процессов в сумматоре 6 по нулевому сигналу с выхода 39 устройства в ЭВМ разрешается подача импульсов опроса на вход 34 устройства.Так как на входы элемента И 13 подаются сигналы с нулевых выходов регистра 12, то на его выходе Формируется единичный сигнал, открывающий элемент И 18 по третьему входу. Единичным сигналом с единичного выхода триггера 28 открыты по первым входам элементы И 18 и И 19. Так как в регистре 4 находится код числа 9, а в регистре 22 такой же код, то на выходе "Меньше" схемы 23 сравнения формируется нулевой сигнал, закрывающий элемент И 18.Поэтому первый импульс опроса поступает только через открытый элемент И 19. Этим сигналом через элемент И 16 на выходы 36 передается двоичный код адреса А, сопровождаемый управляющим сигналом с выхода 38. По сигналу с выхода 38 устройства в ЭВМ адресная информация с выходов 36 и числовая информация с выходов 35 принимается для записи в память, Так как элемент И 18 закрыт, то но адресу А в память будет записана нулевая информация.Через некоторое время задержки, определяемое временем для надежного приема информации с выходов 36 и 35 в ЭВМ, сигналом опроса через элемент 20 задержки, открытый элемент И 14, и элемент ИЛИ 11 устанавливает . ся в "0" триггер 12 При этом единичным сигналом с его нулевого выхода. открываются элементы И 15 и 15 по соответствующим входам, а нулевым сигналом с нулевого выхода триггера 12 закрываются элементы И 15И 15 . На выходах регистра 12 устанавливается следующий код: 01111011.Так как на выходах элементов И 15сформирован код 1000000, то единичным сигналом с выхода элемента И 15 открыты элементы И 3 , и код числа 7 с выходов регистра 1 сравнивается во всех схемах сравнения, кроме 2, с содержимым соответствующих регйстров. При этом в сумматоре 6 ана 1315968логично рассмотренному формируетсяадрес АА =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 устанавливается в "0" триггер 12 , При этом на выходегрегистра 12 формируется код 00111011, а на выходах элементов И 15 - код 0100000. На выходе элемента И-НЕ 13 удерживается единичный сигнал, которым поддерживается в открытом сос= тоянии элемент И 18 по третьему входу, а в закрытом состоянии - элемент И 27 по инверсному входу.Единичным сигналом с выхода элемента И 15 открыты элементы И 3 и двоичный код числа 3 сравнивается в схемах сравнения, кроме 2, с ко-. дами соответствующих регистров 1.При этом на выходах "Меньше" схем 2 и 2сравнения и на выходах Равно11 11 40 схем 24 и 2 сравнения формируются единичные сигналы.Так как на вторых входах элементов И 8 присутствует код 11111011,Ф то элемент И 7закрыт, поэтому И =1Так как на вторых входах элементов И 8 присутствует код 00111011, то элементы И 8 и 8 открыты, поэтому К=2.,ЮИсходя из этого в сумматоре 6 фор 4 мируется двоичный код АА =1+1+2=4По очередному импульсу опроса в ЭВМ выдается код А и код числа 3, триггер 12 устанавливается в "0", а в счетчике 29 Формируется код числа 2. В дальнейшем работа устройства производится аналогично, что отражено в таблице.Поочередная установка в 0" триггеров регистра 12 последовательно исключает при формирования величины К сигналы с выходов "Равно" схем 2 сравнения.С учетом того, что единичный сигнал с выхода "Меньше" схемы 2 сравнения из формирования адреса исключен, величины кодов адресов имеют вид:, А+=1+1+1=3,1А =1+0+0=1Так как триггер 12 на первом этапе остался в состоянии "0", то анализ содержимого регистра 26 исключается, Поэтому по очередному импульсу опроса формируется АА 7=1+1+0=2,а затем по следующему импульсу опроса - АвА=1+4+0=5По седьмому импульсу опроса в счетчике 29 формируется код числа 6, все триггеры регистра 12 оказываются в состоянии "0". При этом на выходе элемента И-НЕ 13 формируется нулевой сигнал, закрывающий элемент И 18 по третьему входу и открывающий элемент И 27 по инверсному входу. По завершении переходных процессов в элементах И 14 и ИЛИ11, .регистре 12, элементе И-НЕ 13 задержанным импульсом опроса с выхода элемента 21 задержки через открытый элемент И 27 устанавливается в "0" триггер 28. Единичный сигнал с нулевого выхода триггера 28 поступает на выход 39 и используется в ЭВМ в качестве сигнала завершения сортировки массива чисел, По этому сигнапу в ЭВМ может использоваться значение двоичного кода количества чисел, записанных в памяти, с выхода 37.Для сортировки чисел в пределах всего массива в регистре 25 устанавливается нулевой код, а в регистре 22 - максимальное значение кода.При этом на первом этапе все триггеры регистров 10 и 12 устанавливаются в" "1" и сортировка чисел производится за п импульсов опроса.10 Устройство для сортировки чисел, содержащее и регистров, (и - число сортируемых чисел), и схем сравнения, п групп элементов И, счетчик, сумматор, две группы выходных элементов И, регистр результата и группу из (п) элементов запрета, причем выходы разрядов -го регистра 10 (=1,2п) соединены с первой группой входов -й схемы сравнения и с первыми входами элементов И -й группы, выходы которых соединены с (1-1)-ми группами входов схем срав нения с первой по (х)-го, с 1-ми группами входов схем сравнения с д+1) -й по п-ю.и с -й группой входов регистра результата, выходы разрядов которого соединены с перЮвыми входами выходных элементов И первой группы, выходы которых являются выходами отсортированного числа устройства, выходы разрядов счетчика соединены с первой группой входов сумматора, вторая группа входов которого соединена с входами начального адреса устройства, а выходы - с первыми входами выходных элементов И второй группы, выходы которых являются выходами адреса отсортированного числа устройства 1-е инверсные входы элементов запрета группы, где 1= 1,23, 1=1,2п,обьединены, о т л и ч а ю щ е е с я тем, З 5 что, с целью расширения области применения за счет возможности сортировки чисел в заданном диапазоне, в него ввецены регистры верхней и нижней границ диапазона, группа элементов И перезаписи нижней границы диапазона, четыре группы элементов И переписи, два и-разрядных регистра, и элементов ИЛИ, элемент И-НЕ, счетчик размера массива, три элемента И, три элемента задержки, триггер, дополнительная. схема сравнения, причем вход запуска устройства соединен с первыми входами элементов И переписи первой группы и через первый элемент задержки с входом установки в единичное состояние триггера, инверснвый выход которого является выходом конца сортировки устройства и подключен к первым входам элементов И переписи нижней границы диапазона, вторые входы которых соединены с выходами разрядов регистра нижней границы диапазоа, входы которого являются входами задания нижней границы диапазона уст-ройства, выходы элементов И переписи нижней границы диапазона подключены к дополнительным группам входов всех схем сравнения, выход "Больше" д-й схемы сравнения подключен к второму входу-го элемента И переписи первой группы, выход которого соединен с входами установки в единичное состояние -го разряда первого и второго п-разрядных регистров, прямой выход д-го разряда первого п-разрядного регистра соединен с первым входом -го элемента И переписи второй группы, второй вход которого подключен к выходу "Меньше" -й схемы сравнения, выход "Равно" которой соединен с первым входом х-го элемента И переписи третьей группы, второй вход которого соединен с прямым выходом -го разряда второго и-разрядного регистра, инверсный выход 1-го разряда которого соединен с 1-м инверсным входом 1-го элемента запрета группы и с 1-м входом элемента И-НЕ, выход которого соединен с первым входом первого элемента И и первым инверсным входом второго элемента И, выход которого подключен к входу установки в "О" триггера, прямой выход которого подключен к второму входу первого элемента И и первому входу третьего элемента И, второй вход которого объединен с третьим входом первого элемента И и является входом опроса устройства, а выход является выходом разрешения считывания устройства и подключен к вторым входам выходных элементов И второй группы и входу второго элемента задержки, выход которого подключен к первым входам элементов И переписи четвертой группы и через третий элемент задержки соединен с вторым входом второго элемента И, выходы элементов И переписи второй и третьей групп соединены соответственно с первой и второй группами входов счетчика, инверсный выход -го разряда первого и-разрядного регистра соединен с первым входом х-го элемента ИЛИ, второй вход которого соединен с выходом -го. элемента И переписи четвертой группы, а выход подключен к входу установки в "О" -го разряда второго п-разрядного регистра, прямой вход 1-го элемента запрета группы подключен к пря.Пекарь Техред Л.Олийнык Корректо чик ак 3(50 Тираж 672ВНИИПИ Государственнопо делам изобретении 113035, Москва, Ж, Р Заказ 236 сное Покомитета СССРоткрытий д. 4/ ская на Производственно-полиграфическое предприятие, г, Ужг ул, Проект мому выходу (1+1)-го разряда второгои-разрядного регистра, прямой выходпервого разряда второго и-разрядногорегистра подключен к вторым входамэлементов И первой группы и второмувходу. первого элемента И переписичетвертой группы, выход 3-го элемента запрета группы соединен с вторымивходами элементов И Я+1)-й группыи вторым входом (1+1)-го элемента Ипереписи четвертой группы, входы задания верхней границы диапазона устройства подключены к входам регистра верхней границы диапазона, выходыразрядов которого подключены к первой группе входов дополнительной схемы сравнения, вторая группа входов 5 которой соединена с выходами разрядов регистра результата, а выход подключен к четвертому входу первогоэлемента И, выход которого соединенс вторыми входами выходных элементов И. первой группы и счетным входом счетчика размера массива, выходы разрядов которого явдяются выходами размера массиваустройства.