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

(я)5 6 06 Г 7/О ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ОПИСАНИЕ ИЗОБРЕТЕНИ УУ СВИДЕТЕЛЪСТВ ВТО ажнко УСТРОЙС ЕЛ зобретенлительно овано для чисел. Це ТВО ДЛЯ СОРТИРОВ(57) ие относится к автома и технике и может бы сортировки массивов лью изобретения явГ ике и ть ис- двоич- яется вычи пол ных(71) Московский институт инженерданской авиации(56) Авторское свидетельство СССРФ 1397900, кл. 6 06 Р 7/08, 1988.Авторское свидетельство СССРМ 1112362, кл. 0 06 Р 7/08, 1983. расширение области применения за счет обеспечения сортировки массивов чисел произвольного обьема, Устройство содержит К ячеек анализа, где К - количество чисел в массиве, каждая ячейка анализа содержит регистр 2, регистр 3 результата. блок 4 сравнения, коммутатор 5, триггеры б - 9, элемент НЕ 10, элементы И 11, 12, элемент ИЛИ 13, Кроме того, устройство содержит элемент НЕ 22, элементы И 23, 24, триггер 25, элемент 26 задержки. Устройство позволяет осуществлять сортировку массивов чисел в режимах возрастания и убывания. Сразу за загрузкой последнего числа предыдущего массива может начаться загрузка первого числа следующего массива. Для каждого массива можно задать индивидуально режим сортировки. 1 ил,10 15 20 Изобретение относится к автоматике и вычислительной технике и может быть использовано при сортировке двоичных массивов чисел.Известно устройство для сортировки чисел, содержащее К ячеек анализа, каждая из которых содержит приемный регистр, регистр результата, блок сравнения и коммутатор,Недостатками известного устройства являются низкое быстродействие и узкие функциональные возможности.Наиболее близким к заявленному является устройство для сортировки чисел, содержащее группу узлов сравнения, входной регистр, выходной регистр, элемент НЕ и два элемента И, причем каждый узел сравнения содержит элемент И, регистр, схему сравнения и коммутатор,Недостатком известного устройства является узкая область применения, так как оно позволяет сортировать массивы лишь фиксированного объема.Целью изобретения является расширение области применения устройства за счет обеспечения сортировки массивов чисел произвольного объема. Цель достигается тем, что в устройство для сортировки чисел, содержащее Кузлов сравнения, где К - количество чисел сортируемого массива, элемент НЕ, два элемента И, причем вход задания режима устройства соединен с первым входом первого элемента И и через элемент НЕ- с первым входом второго элемента И, вторые входы первого и второго элементоэ И объединены и подключень 1 к входу начальной установки устройства, каждый узел сравнения содержит первый элемент И, схему сравнения, коммутатор и первый регистр, выходы разрядов которого соединены с первыми группами информационных входов схемы сравнения и коммутатора, выход схемы сравнения соединен с первым входом первого элемента И, выхОды коммутатора 1-го узла сравнения, 1=1, К. соединены с информационными входами первого регистра (+1)-го узла сравнения, введены элемент задержки, триггер, К-й узел сравнения, а в каждый узел сравнения - элемент НЕ, второй элемент И, элемент ИЛИ, второй регистр и триггеры с первого по четвертый, причем вход тактовых импульсов устройства соединен через элемент задержки с синхровходами всех триггеров, а также первого и второго регистров всех узлов сравнения, вход начальной установки устройства соединен с информационным входом первого триггера первого узла сравнения, в каждом 25 30 35 40 45 50 узле сравнения прямой выход первого триггера соединен с информационным входом второго триггера и с первым входом элемента ИЛИ, второй и третий входы которого соединены с выходами первого и второго элементов И, выход схемы сравнения через элемент НЕ соединен с первым входом второго элемента И, вторые входы первого и второго элементов И соединены соответственно с прямым и инверсным выходами третьего триггера, прямой выход которого соединен с информационным входом четвертого триггера, выходы разрядов первого регистра соединены с информационными входами второго регистра, выхоцы разрядов которого подключены к вторым группам информационных входов коммутатора и схемы сравнения выход элемента ИЛИ соединен с управляющим входом коммутатора и входом разрешения записи второго регистра,прямые выходы второго и четвертого триггеров )-го узла сравнения соединены соответственно с информационными входами первого и третьего триггеров Я+1)-го узла сравнения, )=1, К, выходы коммутатора К)-гоузла сравнения соединены с информационными входами первого регистра К-го узла сравнения, информационные входы первого регистра первого узла сравнения являются информационными входами устройства, прямые выходы второго и четвертого триггеров К-го узла сравнения являются соответственно выходом окончания сортировки массива и выходом сортировки массива устройства, выходы коммутатора К-го узла сравнения являются информационными выходами устройства, выходы первого и второго элементов И устройства соединены соответственно с входами установки в "0" и в "1" триггера, прямой выход которого соединен с информационным входом третьего триггера первого узла сравнения.На чертеже представлена структурная схема устройства для сортировки чисел.Устройство для сортировки чисел содержит узлы сравнения 11-1 к, каждый узел сравнения содержит первый и второй регистры 2 и 3, схему 4 сравнения и коммутатор 5, триггеры 6-9 с первого по четвертый соответственно, элемент НЕ 10, первый и второй элементы И 11 и 12, элемент ИЛИ 13, информационный вход 14, вход 15 начальной установки, тактовый вход 16, вход 17 задания режима работы устройства, информационный выход 18, выходы 19 и 20 соответственно триггеров 7 и 9 каждого узла 1 сравнения, вход 21 выбора режима узла сравнения, элемент НЕ 22, второй и первый элементы Исоответственно 23 и 24, триггер 26 и элемент задержки 26.Устройство работает следующим образом.На вход 14 устройства последовательно параллельным кодом поступают числа сортируемых массивов. Одновременно с ними поступают тактовые импульсы на вход 16 устройства. Первое число массива сопровождается сигналом логической "1" на входе 15. Перед началом ввода очередного массива чисел на входе режима 17 должен быть установлен потенциал, соответствующий режиму сортировки чисел данного массива. Если необходимо выдавать на выход числа массива, начиная с наибольшего, на входе 17 должен быть установлен (и поддерживаться в течение ввода всех чисел данного массива) нулевой потенциал. При выводе младшими числами вперед - единичный потенциал на входе 17. При нулевом потенциале на входе 17 появление сигнала начала массива на входе 15 вызывает срабатывание элемента И 23 и устанавливает триггер 25 в единичное состояние, которое поддерживается в течение всего текущего ввода массива чисел, С приходом первого тактового импульса, задержанного на время установки триггера 25, триггер 8 первого узла сравнения устанавливается в единичное состояние; впоследствии по мере поступле ния тактовых импульсов триггеры 8 и 9 блоков 1 последовательно заполняются "единицами", определяя режим работы устройства "большими числами вперед".В данном режиме по первомутактовому импульсу первое число массива записывается в регистр 21, а триггер 61 устанавливается в единичное состояние. Единичньй сигнал с его выхода предопределяет перезапись в следующем (втором) такте числа из регистра 21 в регистр 31, а числа из регистра 31 (если оно там имеется - это может быть последнее число предыдущего массива) - в регистр 22 независимо от соотношения чисел в регистрах 21 и 31, На втором такте.работы "единица" из триггера 61 переписывается в триггер 71; в этот же момент времени в регистр 21 записывается второе число массива, а первое переписывается в регистр 31. В третьем такте работы устройства происходит сравнение чисел, содержащихся в регистрах 21 и 31. Если число в регистре 31 больше, схема сравнения 41 формирует положительный сигнал, подключая через коммутатор 51 выходы регистра 31 к входам регистра 22, и этот же сигнал, по которому формируется разрешающий сигнал на регистр 31, организует перепись числа из регистра 21 в регистр Зь В регистр 21 в этом10 35 40. ном индивидуальном для каждого массиварежиме массивы размерностью до К чисел включительно, Прл этом возможен выбор 45 50 55 15 20 25 30 же такте записывается третье число массива. При условии, что число в регистре 21 больше, отсутствие сигнала со схемы сравнения 41 подключает через коммутатор 5 выходы регистра 2 к входам регистра 2 г; в регистре 31 при этом остается то же число, что и раньше. Таким образом, в данном режиме большие числа переписываются из узла в узел, не записываясь в регистры 3, чем организуется "обгон" ими меньших чисел.При режиме "меньшими числами вперед" триггеры 8 и 9 узлов сравнения последовательно устанавливаются в нулевое состояние, при этом задействуется элемент И 12 (вместо И 11), то есть режим подключения коммутатора определяется инверсным сигналом с блока сравнения 4, что обеспечивает обратный ("меньшими числами вперед") режим работы,Сразу за загрузкой последнего числа данного массива может в следующем такте начаться загрузка чисел следующего массива, При этом для каждого массива можно задать индивидуальный режим сортировки, Единичное значение сигнала в триггерах 6 и 7 запрещает сравнение первого числа последующего массива и последнего числа предыдущего массива, чем исключается "перемешивание" чисел смежных массивов, Окончание сортировки очередного массива фиксируется по наличию единичного значения сигнала на выходе 19 последнего узла сравнения. Режим сортировки текущего массива определяется потенциалом на выходе 20 последней ячейки 1, на информационном выходе 18 которой формируется очередное число отсортированного массива чисел. При наличии К узлов сравнения устройство позволяет сортировать в выбранрежима ("бол ь шими числами вперед" ил и"меньшими числами вперед" ). Таким образом, позволяя сортировать массивы произвольной размерности, устройство обеспечивает расширение областиприменения. Формула изобретения Устройство для сортировки чисел, содержащее (К) узлов сравнения, где К - количество чисел сортируемого массива, элемент НЕ, два элемента И, причем вход задания режима устройства соединен с первым входом первого элемента И и через элемент НЕ - с первым входом второго элемента И, вторые входы первого и второго элементов И объединены и подключены к входу начальной установки устройства, каждый узел сравнения содержит первьй эле1791812 Составитель С.КишенскийТехред М.Моргентал Корректор О,Кравцова Редактор Заказ 152 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб 4/5 Производственно-издательский комбинат "Патент", г, Ужгород, ул,Гагарина, 101 мент И, схему сравнения, коммутатор и первый регистр, выходы разрядов которого соединены с первыми группами информационных входов схемы сравнения и коммутатора, выход схемы сравнения соединен с первым входом первого элемента И, выходы коммутатора 1-го узла сравнения (1=1, Ксоединены с ин ормационными входами первого регистра1, гоузла сравнения, отлича ю щеещ, что, с целью расширения областии и мнения.устройства путем обеспечения сортирговки массивов чисел .произвольного объема, в него введены элемент задержки, триггер, К-й узел сравнения, а в каждый узел сравнения - элемент НЕ, второй элемент И, элемент ИЛИ, второй регистр и триггеры с первого по четвертый, причем вход такто. вых импульсов устройства соединен черезэлемент задержки с синхровходами всех триггеров, а также первого и второго регистров всех узлов сравнения, вход начальной установки устройства соединен с информационным входом первого триггера первого узла сравнения, в каждом узле сравнения прямой выход первого триггера соединен с информационным входом второго триггера и с первым входом элемента ИЛИ, второй итретий входы которого соединены с выходами первого и второго элементов И, выход схемы сравнения через элемент НЕ соединен с первым входом второго элемента И, вторые входы первого и второго элементов И соединены соответственно с прямым и.инверсным выходами второготриггера, прямой выход которого соединен с информационным входом четвертого триггера, выходы разрядов первого регистра соединены с ин формационными входами второго регистра,выходы разрядов которого подключены к вторым группам информационных входов коммутатора и схемы сравнения, выход элемента ИЛИ соединен с управляющим вхо дом коммутатора и входом разрешениязаписи второго регистра, прямые выходы третьего и четвертого триггеров )-го узла сравнения соединены соответственно с информационными входами первого и второго 15 триггеров Д+1)-го узла сравнения Ц=1, К),выходы коммутатора (К)-го узла сравнения соединены с информационными входами первого регистра К-го узла сравнения, информационные входы первого регистра 20 первого узла сравнения являются информационными входами устройства, прямые выходы третьего и четвертого триггеров К-го узла сравнения являются соответственно выходом окончания сортировки массива и 25 выходом режима сортировки массива устройства, выходы коммутатора К-го узла сравнения являются информационными выходамиустройства, выходы первого и второго элементов И устройства соединены 30 соответственно с входами установки в "Он ив "1" триггера, прямой выход которого соединен с информационным входом второго триггера первого узла сравнения.