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

) С 06 Р 7 О ГОСУДАРСТВЕННЫЙ КОМИТЕТпо изОБРетениям и СтнРытиПРИ ГКНТ СССР Ц,сЙИМ ОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ехническива(54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИДВОИЧНЫХ ЧИСЕЛ(57) Изобретение относится к вычислительной технике. Цель изобретенияупрощение устройства, Устройствосодержит матрицу из пхтй ячеек 1. анализа, где п - количество чисел, а -количество разрядов чисел, регистрыверхней и нижней границ, состоящиеиэ триггеров 2 и 3, блок 4 сравне"ния, группу элементов ЕЛИ-НЕ 5,группы элементов И 6,8, группу вы1647562 ходных элементов И 7, группу элементов НЕ 9, группу триггеров 10, группу элементов ИЛИ 11, группу элементов 12 запрета, элемент И 13, элемент14 задержки, тактовый вход 15, выходы 16 отсортированного числа, выход17 окончания работы, В каждом тактеустройство формирует на выходах 16числа в порядке убывания, которые перИзобретение относится к вычислительной технике и технической кибернетике.Цель изобретения - упрощение устройства,На Лиг. 1 приведена схема устройства; на Лиг. 2 - схема ячейки анализа.Устройство содержит матрицу изпхтп ячеек 1 анализа, где и - количество чисел, т - количество разрядовчисел, регистры верхней и нижнейграниц, состоящие из триггеров 2 и 3,блок 4 сравнения, группу элементовИЛИ-НЕ 5, группу элементов И 6, группу выходных элементов И 7, группуэлементов И 8, группу элементов НЕ 9,группу триггеров 10, группу элементов1ИЛИ 11, группу элементов 12 запрета,элемент И 13, элемент 14 задержки,тактовый вход 15, выходы 16 отсортированного числа, выход 17 окончанияработы. Ячейка 1 анализа содержиттриггер 18, элементы И 19 - 22, элементы ИЛИ 23 и 24, входы 251- 25,выходы 26- 264,40Устройство работает следующим образом.В исходном состоянии в регистрах,образованных триггерами 18 ячеек 1в каждой строке, записаны сортируемые двоичные числа А =аааю.а,где а - разряд с номером з исходного массива чисел А=А 3 1 иВ регистры верхней границы, образованные триггерами 2, и нижней границы,образованные триггерами 3, записываются числа, равные соответственноверхней К и нижней У границам интерва"ла. Все триггеры 10 установлены в нулевое состояние, В каждом такте из)5массива А выделяется максимальное число Аак на выходах элементов ИЛИ 11яе превышающее верхней границы Х ин- .тбрвала, Если вьпелеиное число Аь воначально размещены в триггерахячейки 1 и которые не меньше, чем верхняя1 граница, записанная в триггере 2 верхней границы. Сортировка производится до тех пор, пока очередное отсортированное число не становится меньше, чем нижняя граница, записанная в триггере 3 нижней границы.2 ил.У, то при поступлении на вход устройства тактирующего импульса оно передается через элементы И 7 на выходы 16 устройства, После выдачи текущего максимального числа указаннымспособом оно маскируется и тем самымисключается из дальнейшего рассмотрения. Среди оставшихся чисел исходногомассива производится выбор очередногомаксимального числа Аи т.д. Еслиочередное выделенное число Ачо (У,то на выходе 17 вырабатывается признак "Конец работы". Маскированиечисла, превышающего верхнюю границу Х,производится путем сравнения Х с числом Авыполняющимся с помощью эле 1 9ментов И 19 н 20 и ИЛИ 23 . Если в некоторой -й ячейке анализа 1 а,Х;,а все предыдущие разряды А и Х равны, то на выходе 26 формируется сигнал логической единицы, в результатена выходах элементов ИЛИ-НЕ 5 и И 6соответствующей строки формируетсясигнал логического нуля, который запрещает выборку данного числа в качестве А,Максимальное из незамаскированныхчисел выделяется элементами И 21, 22н ИЛИ 24, 11. Если -е разряды частичисел равны единице, а части чисел -нулю, то на выходах соответствующихэлементов И 22 и ИЛИ 11 формируютсясигналы логической единицы, и на выход 26 соответствующей ячейки анали фза поступает сигнал логической единицы - для тех чисел, рассмотрениекоторых на предмет выделения А аксследует продолжить, и логическогонуля - в противном случае. Если -еразряды всех незамаскированных чиселравны нулю, то нуль выделяется навыходе элемента ИЛИ 1, и сигналлогической единицы с выхода элемента НЕ 9 через элементы ИЛИ 24 и И 21поступает на выход 26 тех ячеек5 164 756 анализа, хранящиеся в которых числа ранее не были замаскированы в результате анализа предыдущих разрядов .Каждое очередное Асравнивается блоком ч сравнения с нижней грани 5 цей У, и в случае если А С У, выдается сигнал на выход 17.Формула изобретенияУстройство для сортировки двоичных чисел, содержащее матрицу пхщячеек анализа, где и - количествочисел, равное количеству строк матрицы, щ - количество разрядов чисел,равное количеству столбцов матрицы,регистры верхней и нижней границ,блок сравнения, группу триггеров,группу элементов запрета, группу элементов ИЛИ, группу выходных элементов И, группу элементов НЕ, элемент Ии элемент задержки, а ячейка анализасодержит триггер, первый элемент И идва элемента ИЛИ, причем инверсный 25выход 1-го разряда регистра верхнейграницы, где д=1,2щ, соединенс первыми входами всех ячеек анализа1-го столбца матрицы, второй и третийвходы ячейки анализа 3-й строки К-гостолбца матрицы, где 3=1,2п,1=2,3щ, подключены соответст"венно к первому и второму выходамячейки анализа 3-й строки Ь)-гостолбца матрицы, третий выход ячейки35анализа 3-й строки 1-го столбца матрицы соединен с 3-м входом 1-го эле мента ИЛИ группы, выход которого соеВдннен с д-м входом первой группы блока сравнения и с первым входом 1-го 4 Овыходного элемента И, выход которогоявляется выходом 1-го разряда отсортированного числа устройства, выход1.-го разряда регистра нижней границысоединен с 1-м входом второй группыблока сравнения, выход ."Меньше" которого является выходом окончания работы устройства, а выход "Не меньше".соединен с первым входом элемента Итактовый вход устройства соединен свторым входом элемента И, выход которого соединен с вторыми входами всехвыходных элементов И и входом элемента задержки, о т л и ч а ю щ е е с ятем, что, с целью упрощения устройства, оно содержит группу элементов КЛИНЕ, первую и вторую группы элементовИ, а в каждую ячейкФ анализа введенытри элемента И, дрнчем четвертый вы" 6ход ячейки анализа 3 - и строки 1 - го .столбца матрицы соединен с 1-и входбм3-го элемента ИЛИ-НЕ группы, выходкоторого соединен с первым входом3-го элемента И первой группы, выходкоторого соединен с третьим входом3-й ячейки анализа первого столбцаматрицы, вторые входы всех ячееканализа первогостолбца матрицы, каки прямой вход первого элемента запре"та группы и первый вход первого элемента И второй группы, подключены квходу логической единицы устройства,вьюод 1-го элемента запрета группы,где 1=1,2 п, соединен с прямымвходом (1+1)-го элемента запрета группы и с первым входом (1+1)-го элемента И второй группы, второй выход .1-йячейки анализа щ-го столбца матрицысоединен с инверсным входом 3 -го элемента запрета группы и с вторым входом3-го элемента И второй группы, выходкоторого соединен с входом установкив единичное состояние 3-го триггерагруппы, инверсный выход которого соединен с вторым входом 3 -го элемента Ипервой группы, выход -го элемента ИЛИгруппы соединен с входом -го элемента НЕ группы, выход которого соединенс четвертыми входами всех ячеек анализа д-го столбца матрицы, входы синхронизации и установки в нулевое состояние всех триггеров группы подключены соответственно к выходу элементазадержки и к входу логического нуляустройства, в каждой ячейке анализаее первый вход соединен с первымивходами первого элемента И и первогоэлемента ИЛИ, выход которого соединенс первым входом второго элемента И,второй вход ячейки анализа соединенс вторыми входами первого и второгоэлементов И, выходы которых являются соответственно четвертым и первымвыходами ячейки анализа, третий входячейки анализа соединен с первымивходамн третьего и четвертого элементов И, выходы которых являютсясоответственно вторым и третьим выходами ячейки анализа, четвертый входячейки анализа соединен с первым входом второго элемента ИЛИ, выход которого соединен с вторым входом третьего элемента И, выход триггера соединен с вторыми входами четвертогоэлемента И, первого и второго элементов ИЛИ и с третьим входом первогоэлемента И,1647562 оставитель В. Горохехред И.Дидык. едактор В. Б 1 гренкова Т Коррек Патай Г зводственно-издательский комбинат "Патент", г. Ужгород, уп. Гагарина, 10 Заказ 1400 Тир ВНИИПИ Государственного комите 113035, Москва403 Подписное по изобретениям и открытиям -35, Раушская наб., д. 4/5