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

 

Изобретение относится к вычислительной технике. Цель изобретения - упрощение устройства. Устройство содержит матрицу из пхга ячеек 1 анализа , где п - количество чисел, та - количество разрядов чисел, регистры верхней и нижней границ, состоящие из триггеров 2 и 3, блок 4 сравнения , группу элементов НЛИ-НЕ 5, группы элементов И 6,8, группу вы

СОЮЗ авЕТСНИХ . СОЦИАЛИСТИЧЕСКИХ . -РЕаЪБЛИК

2 А1

f?9F (2l) (s>)s С 06 F 7!06

»к;, »1 1»» »;1». 1

Ц,3 0N l 1

+)gh»iJ !

С, » j, ) "». ° 1

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (2 t ) 4709242/24 (22) 23.06.89 (46) 07.05.91. Бюл. У 17 (71) Таганрогский радиотехнический институт им. В.Д.Калмыкова (72) В.Н.Решетняк, В.П.Карелин и В.Ф.Гузик

:(53) 681.325.5(088.8) (56) Авторское свидетельство СССР

526888, кл. С 06 F 7/06, 1974.

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

В 1104504, кл. r, 06 Р 7/06, 1983.

2 (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ

ДВОИЧНЪ|Х ЧИСЕЛ (57) Изобретение относится к вычислительной технике ° Цель изобретенияупрощение устройства. Устройство содержит матрицу из nxm ячеек 1. анализа, где п — количество чисел, m— количество разрядов чисел, регистры верхней и нижней границ, состоящие иэ триггеров 2 и 3, блок 4 сравнения, группу элементов .ШИ-НЕ 5, группы элементов И 6,8, группу вы1647562 ходных элементов И 7, группу элементов НЕ 9, группу триггеров 10, группу элементов ИЛИ 11, группу элементов 12 запрета, элемент И 13, элемент

14 задержки, тактовый вход 15, выходы 16 отсортированного числа, выход

17 окончания работы. В каждом такте устройство формирует на выходах 16 числа в порядке убывания, которые пер-!0

Изобретение относится к вычислительной технике и технической кибернетике.

Цель изобретения — упрощение устройства, На фиг. 1 приведена схема устройства; на фиг. 2 — схема ячейки анализа.

Устройство содержит матрицу из nxm ячеек 1 анализа, где n — количество чисел, m — количество разрядов чисел, регистры верхней и нижней границ, состоящие из триггеров 2 и 3, блок 4 сравнения, группу элементов

ИЛИ-НЕ 5, группу элементов И 6, группу выходных элементов И 7, группу элементов И 8, группу элементов НЕ 9, группу триггеров 10, группу элементов

ИЛИ 11, группу элементов 12 запрета, элемент И 13, элемент 14 задержки, тактовый вход 15, выходы 16 отсортированного числа, выход 17 окончания работы. Ячейка 1 анализа содержит триггеР 18, элементы И 19 — 22, элементы ИЛИ 23 и 24, входы 251- 25, выходы 26 - 264..

Устройство работает следующим образом.

В исходном состоянии в регистрах, образованных триггерами 18 ячеек 1 в каждой строке, записаны сортируемые двоичные числа А =а а ...а„„» а„„ где а! — разряд с номером i исходного массива чисел A=(A ), )Т; и.

В регистры верхней границы, образованные триггерами 2, и нижней границы, образованные триггерами 3, записываются числа, равные соответственно верхней К и нижней У границам интерва" лв. Все триггеры 10 установлены в нулевое состояние. В каждом такте из

>5 массива А выделяется максимальное число А®,1к на выходах элементов ИЛИ 11,, яе превышающее верхней границы Х ин- . тервала. Если вь!пелеиное число А воначально размещены в триггерахячейки 1 и которые не меньше, чем верхняя граница, записанная в триггере 2 верхней границы. Сортировка производится до тех пор, пока очередное отсортированное число не становится меньше, чем нижняя граница, записанная в триггере 3 нижней границы.

2 ил. Ó, то при поступлении на вход устройства тактирующего импульса оно передается через элементы И 7 на выходы 16 устройства. После выдачи текущего максимального числа указанным способом оно маскируется и тем самым исключается из дальнейшего рассмотрения. Среди оставшихся чисел исходного массива производится выбор очередного максимального числа А „ и т.д. Если очередное выделенное число А, а (У, то на выходе 17 вырабатывается признак "Конец работы". Маскирование числа, превышающего верхнюю границу Х, производится путем сравнения Х с числом А выполняющимся с помощью эле1 9 ментов И 19 н 20 и ИЛИ 23 . Если в некоторой i-й ячейке анализа 1 a >Õ;, а все предыдущие разряды А и Х равны, то на выходе 264 формируется сигнал логической единицы, в результате на выходах элементов ИЛИ-НЕ 5 и И 6 соответствующей строки формируется сигнал логического нуля, который запрещает выборку данного числа s качестве А,,„,акс.

Максимальное из незамаскированных чисел выделяется элементами И 21, 22 н ИЛИ 24,11. Если i-е разряды части чисел равны единице, а части чисел— нулю, то на выходах соответствующих элементов И 22 и ИЛИ 11 формируются сигналы логической единицы, и на выход 26 соответствующей ячейки анализа поступает сигнал логической единиI цы — для тех чисел, рассмотрение которых на предмет выделения А „д следует продолжить, и логического нуля — в противном случае. Если i-e разряды всех незамаскированных чисел равны нулю, то нуль выделяется на выходе элемента ИЛИ !1, и сигнал логической единицы с выхода элемента НЕ 9 через элементы ИЛИ 24 и И 21 поступает на выход 26 тех ячеек !

5 164 756 анализа, хранящиеся в которых числа ранее не были замаскированы в результате анализа предыдущих разрядов .

Ка цое очередное Амакс сравнивает ся блоком 4 сравнения с нижней грани5 цей У, и в случае если А, „. (Y, выдается сигнал на выход 17.

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

Устройство для сортировки двоичных чисел, содержащее матрицу nxm ячеек анализа, где и — количество чисел, равное количеству строк матрицы» m — количество разрядов чисел, равное количеству столбцов матрицы, регистры верхней и нижней границ, блок сравнения, группу триггеров, группу элементов запрета, группу эле- 20 ментов ИЛИ, группу выходных элементов И, группу элементов НЕ, элемент И и элемент задержки, а ячейка анализа содержит триггер, первый элемент И и два элемента ИЛИ, причем инверсный 25 выход i-го разряда регистра верхней границы, где д=1»2,...,m, соединен с первыми входами всех ячеек анализа

i-го столбца матрицы, второй и третий входы ячейки анализа j-й строки k-ro столбца матрицы, где 1=1,2»...»п, k=2,3,...,m, подключены соответст" венно к первому и второму выходам ячейки анализа j-й строки (k-1)-ro столбца матрицы, третий выход ячейки

35 анализа )-й строки i-ro столбца матрицы соединен с j-м входом i-ro эле мента ИЛИ группы, выход которого соеб дннен с -м входом первой группы блока сравнения и с первым входом i-ro 4п выходного элемента И, выход которого является выходом i-ro разряда отсортированного числа устройства, выход

j.-го разряда регистра нижней границы соединен с i-м входом второй группы 45 блока сравнения, выход "Меньше" которого является выходом окончания работы устройства, а выход "Не меньше" соединен с первым входом элемента И» тактовый вход устройства соединен с вторым входом элемента И, выход которого соединен с вторыми входами всех выходных элементов И и входом элемента задержки, о т л и ч а ю щ е е с я тем» что с целью упрошения устройст- 55 ва, оно содержит группу элементов КЛИНЕ, первую и вторую группы элементов

И, а в каждую ячейк1 анализа введены три элемента И, лрнчем четвертый вы"

6 ход ячейки анализа j — и строки i — ro . столбца матрицы соединен с i-м входбм

j-го элемента ИЛИ-HE группы, выход которого соединен с первым входом

j-ro элемента И первой группы, выход которого соединен с третьим входом

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

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

1647562

Я5

25у

Составитель В. Горохов

Техред И.Дидфпс. Корректор Л.Патай

Редактор В. Б1 гренкова

Заказ 1400 Тираж 403 Подписное

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

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

Производственно-издательский комбинат "Патент", r. Ужгород, уп. Гагарина, 101 !