Устройство для сортировки двоичных чисел Советский патент 1991 года по МПК G06F7/06 

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

Цель изобретения - упрощение устройства .

На фиг. 1 приведена схема устройства; на фиг. }. - схема ячейки анализа.

Устройство содержит матрицу из nxm ячеек 1 анализа, где п - количество чисел, m - количество разрядов чисел, регистры верхней и нижней границ, состоящие из триггеров 2 и 3, блок 4 сравнения, группу элементов ИЛИ-НЕ 5, группу элементов И 6, группу выходных элементов И 7, группу элементов И 8, группу элементов НЕ 9, группу триггеров 10, группу элементов ИЛИ 11, группу элементов 12 запрета, элемент И 13, элемент 14 задержки, тактовый вход 15, выходы 16 отсортированного числа, выход 17 окончания работы. Ячейка 1 анализа содержит триггер 18, элементы И 19 - 22, элементы ИЛИ 23 и 24, входы 25ц- 25$, выходы 26 - 264..

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

В исходном состоянии в регистрах, образованных триггерами 18 ячеек 1 в каадой строке, записаны сортируемые двоичные числа .. .а.а, где а - разряд с номером i исходного массива чисел , , п. В регистры верхней границы, образованые триггерами 2, и нижней границы, образованные триггерами 3, записываются числа равные соответственно верхней X и нижней Y границам интервла. Все триггеры 10 установлены в нулевое состояние. В каждом такте из массива А выделяется максимальное чило АдддКС на выходах элементов ИЛИ 11 не превышающее верхней границы X интервала. Если выделенное число Амоте

0

5

0

,« 5

0

45

i5

, то при поступлении на вход устройства тактирующего импульса оно передается через элементы И 7 на выходы 16 устройства. После выдачи текущего максимального числа указанным способом оно маскируется и тем самым исключается из дальнейшего рассмотрения. Среди оставшихся чисел исходного массива производится выбор очередного максимального числа А и т.д. Если очередное выделенное число Амакс Ґ, то на выходе 17 вырабатывается признак Конец работы. Маскирование числа, превышающего верхнюю границу X, производится путем сравнения X с числом А ., выполняющимся с помощью элементов И 19 и 20 и ИЛИ 23. Если в некоторой i-й ячейке анализа 1 а,, а все предыдущие разряды А и X равны, то на выходе 26 формируется сигнал логической единицы, в результате на выходах элементов ИЛИ-НЕ 5 и И 6 соответствующей строки формируется сигнал логического нуля, который запрещает выборку данного числа в качеСТВе А/МО«

Максимальное из незамаскированных

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

516

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

Каждое очередное АМОКС сравнивается блоком 4 сравнения с нижней границей Y, ив случае если A«Q(CU Y, выдается сигнал на выход 17.

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

Устройство для сортировки двоичных чисел, содержащее матрицу nxm ячеек анализа, где п - количество чисел, равное количеству строк матрицы, m - количество разрядов чисел, равное количеству столбцов матрицы, регистры верхней и нижней границ, блок сравнения, группу триггеров, группу элементов запрета, группу элементов ИЛИ, группу выходных элементов И, группу элементов НЕ, элемент И и элемент задержки, а ячейка анализа содержит триггер, первый элемент И и два элемента ИЛИ, причем инверсный выход 1-го разряда регистра верхней границы, где 1-1,2,...,т , соединен с первыми входами всех ячеек анализа 1-го столбца матрицы, второй и третий входы ячейки анализа j-й строки k-ro столбца матрицы, где ,2,...,n, ,3,...,m, подключены соответст- - венно к первому и второму выходам ячейки анализа j-й строки (k-l)-ro столбца матрицы, третий выход ячейки анализа j-й строки 1-го столбца матрицы соединен с j-м входом 1-го элемента ИЛИ группы, выход которого соединен с i-м входом первой группы блока сравнения и с первым входом 1-го выходного элемента И, выход которого является выходом 1-го разряда отсортированного числа устройства, выход |.-го разряда регистра нижней границы соединен с i-м входом второй группы блока сравнения, выход Меньше которого является выходом окончания работы устройства, а выход Не меньше соединен с первым входом элемента И, тактовый вход устройства соединен с вторым входом элемента И, выход которого соединен с вторыми входами всех выходных элементов И и входом элемента задержки, отличающееся тем, что, с целью упрощения устройства-, оно содержит группу элементов ИЛИ НЕ, первую и вторую группы элементов И, а в каждую ячейку анализа введены три элемента И, причем четвертый вы562 6

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

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

5 выход 1-го элемента запрета группы, где ,2,..., п-1, соединен с прямым входом (1+1)-го элемента запрета группы и с первым входом (1+1)-го элемента И второй группы, второй выход j-й

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

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

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

0 соответственно вторым и третьим выходами ячейки анализа, четвертый вход ячейки анализа соединен с первым входом второго элемента ИЛИ, выход которого соединен с вторым входом третье5 го элемента И, выход триггера соеди- 1нен с вторыми входами четвертого элемента И, первого и второго элемен тов ИЛИ и с третьим входом первого элемента И.

V

i

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

25f

#JO#40f8

23

20

+28i

21

Ј4

21

26}

Фиг. 2.