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

соответственно, первую н вторую группы выходных регистров 11 и 12 по р и q регистров соответственно о Цель изобретения - повьшгение быстродействия. Выходные регистры и узлы преобразования кодов разделяются на две равные группы При этом первая половина узлов обеспечивает формирование

1

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

Цель изобретения - повышение быстродействия „

На чертеже приведена структурная схема предлагаемого устройства (при , когда значения чисел массива лежат в пределах 1-5 ()с

Устройство содержит входные регистры 1, дешифратор 2, первую группу элементов ИЛИ 3, первую группу 4 и вторую группу УЗЛОВ 5 преобразования кодов, включающих в себя группы элементов НЕ 6, элементов И 7 и И 8, первую группу шифраторов 9,вторую группу шифраторов 10, первую группу выход- ных регистров 1 1 , вторую группу выход ных регистров 12, дешифратор 13, вторую группу элементов ИЛИ 14, входы .15 устройства, выходы 16 устройст- -ва.

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

Исходное состояние устройства характеризуется тем, что входные 1 и выходные 11 и 12 регистры установлены в состояние О (не показано). Для упорядочивания чисел исходный массив принимается во входшле регисры 1 по входам 15 о Через некоторое время, определяемое переходными процессами в элементах схемы, в выходных регистрах 11 и 12 формируется упорядоченный массив, чисел

Работу устройства условно можно разделить на два этапа На первом этапе посредством дешифратора 2 и элементов Ш1И 3 производится упорядоупорядоченных чисел из выходного кода элементов ИЛИ 3 начиная с крайней левой единицы, а вторая половина узлов - начиная с крайней правой единицы. За счет такого разделения производится как бы встречная расстановка чисел,что позволяет повысить быстродействие устройства,. ил., 2 табл.

0

5

0 25

именьшего ненулевого значения, на втором - встречная расстановка чисел в выходных регистрах П и 12- с помощью узлов 4 и 5 преобразования кодов, дешифратора 13 и группы элементов ИЛИ 14о

Работа устройства на первом этапе с Пусть в регистры 1 принят массив исходных чисел а, 5, а 1, а, 4, а, 2о

В соответствии с табл.1 единичные сигналы появляются на пятом выходе дешифратора 2, первом дешифратора 2, четвертом дешифратора 2, и на втором дешифратора

Таблица. 1

а, 101 О

Из табЛо видно, что порядок размещения единичных сигналов, если объединить одноименные выходы Дешифраторов , соответствует возрастанию значений чисел.

Посредством элементов ИЛИ 3 производится объединение одноименных выходов дешифраторов„ Позиционный

код на выходах элементов ИЛИ 3 имеет вид 11011 (табл.1) В соответствии с этим кодом в выходных регистрах 11 и 12 необходимо разместить числа в порядке возрастание значения Ь, 1 bj 2, bj Ц, Ь 5. Это обеспечивается соответствующими шифраторами 9 и 10, ria выходы которых необходимо подать следующие позиционные коды;10000 на входы шифратора 9,, 01000 на входы шифратора 9 , 00010 на входы шифратора 10, , 00001 на входы шифратора Ю.

Формирование указанных позиционных кодов производится на втором этапе работы устройства из выходных сигналов элементов ИЛИ 3 посредством узлов 4 и 5 преобразования кодов. При этом в каждом узле 4 должны исключаться из анализа вьщеленные крайние левые единичные сигналы элементо ИЛИ 3 в предыдущих узлах 4, Для приведенного примера послеД овательное преобразование выходных сигналов элементов ИЛИ 3 можно условно пока- ,зать следующим образом

11011

10000

01011

01011

RG9,

RG9i

0001100010

-00001

-00001

RG10,

RG10,

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

10000

о 0000 о 0000 о 1000 о 0000 о 0100

0,0100 I

т 1, о13395484

чисеЛо Тогда такое преобразование условно выглядит следующим обрязом:

11011

-10000

-0101I

-01000

RG9,RGSj

000010-01010- 00001--1 101 1

10

RG10,

RG10.

Данная схема может быть реализована путем разделения выходных регист 5 ров на две равные независимые группь с соответствующими узлами преобразования кодов. При этом в первой группе узлов 4 преобразования производится формирование позиционных кодов для

2Q соответствующих шифраторов 9 путем последовательного вьщеления левой единицы из выходных сигналов элементов ИЛИ 3, а во второй группе 5 путем последовательного выделения крайней

25 правой единицы из выходных сигналов элементов ИЛИ 3. Такое решение справедливо для частного случая, когда во входных регистрах 1 размещен массив чисел различных по величине. При

30 этом число возбужденных выходов элементов ШШ 3 равно числу выходных регистров. Если во входные регистры 1 принят ряд одинаковых кодов либо нулевые коды одного или нескольких чисел, количество возбужденных выхо35

0

дов элементов ИЛИ 3 меньше числа выходных регистров.

Для пояснения принципов построения устройства используется табл.2 (истинности для различных значений выходных сигналов элементов ИЛИ З).

Таблица2

00 000

00000

00(000 00 000 00 000 00 000

I

00 000

Из табл„2 следу€1т,, что в регистре 11 должно размещаться наименьшее число, значение которого соответствует номеру крайнего левого воабуж- денного элемента ИЛИ Зо Выделение крайней левой единицы производится )j узле 4 4 элементами И 7, подключенными к выходам : jiCN eHTOH Ш1И 3 по

Продолжение табл.2

приоритетной схеме с помощью элементов НЕ 6„ Для размещения следующего наименьшего числа в регистре 1 из оставшихся исключается выбранное число путем операции логического умножения выходных элементов ИЛИ 3 с инверсным кодом выходных сигналов элементов И 7 узла 4,, Эта операция

выполняется в узле 4 посредством элементов И 8, на прямые входы которых подаются выходные сигналы элементов ИЛИ 3, а на инверсные выходные сигналы узла 4 (табл.2,27 набор): выходной код узла 4 10000, обратный код 01111, выходной код элемента ИЛИ 3 1Ю11, выходной код элемента И 8 01011.

В младшей позиции кода значение выходного сигнала тождественно равно нулю при любом наборе выходных сигналов элементов ИЛИ 3 (табл.2,4-й столбец) , поэтому входной сигнал для первого входа шифратора 9 также всегда равен нулю. Отсюда имеется возможность в минимизации оборудования узлов 4 преобразования кодов, начиная со второго. Таким образом, с помощью элементов И 8 в узле 4, формируется код 1011, из которого с помощью эле ментов И 7 и НЕ 6, В1спючённых с выходами элементов И 8 по приоритетной схеме, выделяется крайняя левая един да. При этом на входах шифратора 9 формируется позиционный код 01000.

Размещение чисел во второй половине регистров 12 производится следующим образом.

Формирование единичных сигналов для шифраторов 102(табло2, 8-й столбец) выполняется только тогда, когда число возбужденных выходов элементов ИЛИ 3 равно четырем (15,23,27, 29 и 30 наборы), а для шифратора 10 (табл.2, 7-й столбец) - когда число возбужденных выходов элементов ИЛИ 3 больше двух (7,11,13,14,15,19, 21,22,23,25,26,27,28,29 и 30},

Исходя из этого, для размещения числа в регистрах 12 И 12, необходимо определить количество единиц в выходном коде элементов ИЛИ 3, Если число единиц равно трем, разрешается работа узла 5, и блокируется узел 5j, если число единиц равно четырем, разрешается работа узлов 5, и 5 , если число единиц меньше трех, работа узлов 5, и 5 блокируется

Анализ количества единиц выполняется посредством дешифратора 13 и элементов ИЛИ 14

С помощью элемента ИЛИ 14 объединяются сигналы с 15,23,27,29 и 30 выходов дешифратора 13, двоичные коды номеров которых содержат четыре единицы (табЛо2, 1-й и .2-й столбцы).

С помощью элемента ШШ 14 оО ьоди- няются сигналы с 7,11,1.3,14,15,19,21, 23,22,25,26,27,28,29 н 30 выходов де- (. шифратора 13, двоичш.ш коды номеров содержат либо три, либо четыре единицы .

Например (таблл2,27-й набор), единичным сигналом с выхода элемента

10 ИЛИ 14 разреп1ается работа в узле 52 элементов И 7, включенных с помощью элемента НЕ 6 с выходами двух старших элементов ИЛИ 3 по приоритетной схеме. Узел 5 выполнен с учетом

15 возможности минимизации оборудования, В регистре 12,, размещается наибольшее число из массива, поэтому на мпа,чших трех позициях шифратора 10 входные сигналы тождественны и рав20 ны нулю.

Например (табл.2, 27-й набор), на выходе элемента ИЛИ 14 формируется единичный сигнал, открывающий 25 элементы И 7 в узле 5. При этом из выходного кода элементов ИЛИ 3 ПОП на входах шифратора 10 формируется позиционный код 00001. Кроме того, единичным сигналом с выхода Ьлемен- Q та И 7, узла 5 закрывается по инверсному входу элемент И 8,, а нулевым сигналом с выхода элемента И 7 открывается по инверсному входу элемент И 8j в узле

Для формирования кода в регистре

5

12,

на входы узла 5, подаются старшие три позиции кода элементов ИЛИ 3 (табл.2, 6-й столбец), так как входные сигналы для первого и второго выходов шифратора 10, тождественно равны нулюо

Управление элементами И 7 в узле 5, производится единичным С1:гналом с выхода элемента ИЛИ 14,,

. Например (табл.2, 27-й набор), выходными сигналами элемента ИЛИ 14, элементы И 7 в узле 5, открыты. При этом выходной код узла 5 00001, обратный код 00010, выходной код

Q элемента HITIi 3 ПОП, выходной код элемента И 8 000IП, входной код шифратора 10, 0001Оо Таким образом, в регистрах 11 и 12 числа размещены в порядке Ь 1, bj 2, b , Ь 5«

g Лостроение устройства для произ- вольноГ О количества сортируемых чисел п и максимального значеиг{я любого из них, опрел.еляемого по выражению, m 2 - 1, где k - разрядность числа в двоичной системе счисления, выполняется в соответствии с указанными принципами„

При четном . количестве каждая группа содержит по п/2 выходных регистров и п/2 узлов преобразования кодов„ В данном случае узел 4, преобразования кодов содержит группу из (т-1) элементов И 7 и группу из (т-1) элементов НЕ 6„ Каждый последующий узел

1 о с

.

Щг.

включает в себя группы

элементов И 7, И 8, НЕ 6, число которых определяется местом размещения узла. В общем виде количество элементов И 7, И 8 и НЕ 6 для 1-го узла

3395А810

четное), первую и вторую группы шифраторов по р и q шифраторов соответственно , первую и вторую группы выходных регистров по р и q выходных регистров соответственно, первый узел преобразования кодов первой группы содержит т-1 элементов НЕ и т-1 элементов И, 1-й узел преоб- 10 разования кодов первой группы (1 2,3,. .,р) содержит первую группу из т-1 элементов И, т-1 элементов НЕ и вторую группу из т-1+1 элементов

И, j-й узел преобразования кодов вто- 15 рой группы ,2,,о о,q-1)включает две группы элементов И и группу элементов НЕ, q-й узел преобразования кодов второй группы содержит rpfyniry элементов И и группу элементов НЕ, причем выходы i-ro входного регистра (,2,oaa,n), входы которого являются входами i-ro числа устройства, соединены с входами i-ro дешифратора, j-й выход i-ro дешифратора (j 1 ,2 , .:, ,т) соединен с i-м входом j-ro элемента ИЛИ первой группы, выход k-ro элемента ИЛИ первой группы (,2,..,,т-1) через k-й элемент НЕ первого узла преобразования кодов первой группы соединен в этом узле с k-ми управляющими входами k,k+1, m-1 элементов И, выход первого элемента ИЛИ первой группы соединен с первым входом первого шифратора первой группы, выход (k+l)-ro элемента ИЛИ первой группы соединен с информационным входом, k-ro.элемента и первого узла преобразования кодов первой группы, выход k-ro элемента И является (k+l)-M выходом этого узла и подключен к )-My входу первого шифратора первой группы, в 1-м узле преобразования кодов первой группы выход s-ro элемента НЕ (,2,„о.,m-l) подключен к s-му управляющему входу (s,5+1,о о о,т-1)-го элементой И первой группы, информационный вход s-ro элемента И первой группы соединен с входом (s+l)-ro элемента НЕ и выходом (s + l)-ro И второй группы, прямой вход z-ro элемента И второй группы (,2,о о„,т-1 + 1) соединен с выходом (z+1-l)-ro элемента ИЖ первой группы, а инверсный вход - с

НЕ 6 подключены к выходам элементов ИЛИ 3 по приоритетной схеме. Б каждом узле преобразования входы элементов И 7 и НЕ 6 подключены к выходам элементов И 8 также по приоритетной схеме.

Выходы элементов И 7 каждого узла 4, кроме П/2-ГО, соединен с инверсными входами соответствующих элементов И 8 последующего узла.

Построение узлов преобразования кодов во второй группе выполняется с учетом того, что расстановка чисел, начиная с п/2-го регистра 12, производится путем последовательного выделения крайней правой единицы из выходных сигналов элементов ИЛИ Зо При этом исключение из анализа выделенных единиц в узлах 5 производится путем блокировки элементов И В единичными сигналами позиционных кодов с выходов элементов И 7 предыдущих узлов

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

Устройство для упорядочивания п чисел, содержащее п входных регистров п дешифраторов, первую группу из m элементов ИЛИ (т - количество разрядов анализируемых чисел в позиционной форме их представления), первую группу

25

30

И, j-й узел преобразования кодов вто- 15 рой группы ,2,,о о,q-1)включает две группы элементов И и группу элементов НЕ, q-й узел преобразования кодов второй группы содержит rpfyniry элементов И и группу элементов НЕ, причем выходы i-ro входного регистра (,2,oaa,n), входы которого являются входами i-ro числа устройства, соединены с входами i-ro дешифратора, j-й выход i-ro дешифратора (j 1 ,2 , .:, ,т) соединен с i-м входом j-ro элемента ИЛИ первой группы, выход k-ro элемента ИЛИ первой группы (,2,..,,т-1) через k-й элемент НЕ первого узла преобразования кодов первой группы соединен в этом узле с k-ми управляющими входами k,k+1, m-1 элементов И, выход первого элемента ИЛИ первой группы соединен с первым входом первого шифратора первой группы, выход (k+l)-ro элемента ИЛИ первой группы соединен с информационным входом, k-ro.элемента и первого узла преобразования кодов первой группы, выход k-ro элемента И является (k+l)-M выходом этого узла и подключен к )-My входу первого шифратора первой группы, в 1-м узле преобразования кодов первой группы вы ход s-ro элемента НЕ (,2,„о.,m-l) подключен к s-му управляющему входу (s,5+1,о о о,т-1)-го элементой И первой группы, информационный вход s-ro элемента И первой группы соединен с входом (s+l)-ro элемента НЕ и выходом (s + l)-ro И второй группы, прямой вход z-ro элемента И второй группы (,2,о о„,т-1 + 1) соединен с выходом (z+1-l)-ro элемента ИЖ первой группы, а инверсный вход - с

35

40

45

50

из р узлов преобразования кодов, вто- 55 (z+l)-M выходом (1+1)-го узла преоб- рую группу из q узлов преобразования разования кодов первой группы, выход кодов (п +

(., если п-четное, р 1)/2, q п р, если п - непервого элемента И второй группы соединен с входом первого элемента НЕ

5

0

И, j-й узел преобразования кодов вто- рой группы ,2,,о о,q-1)включает две группы элементов И и группу элементов НЕ, q-й узел преобразования кодов второй группы содержит rpfyniry элементов И и группу элементов НЕ, причем выходы i-ro входного регистра (,2,oaa,n), входы которого являются входами i-ro числа устройства, соединены с входами i-ro дешифратора, j-й выход i-ro дешифратора (j 1 ,2 , .:, ,т) соединен с i-м входом j-ro элемента ИЛИ первой группы, выход k-ro элемента ИЛИ первой группы (,2,..,,т-1) через k-й элемент НЕ первого узла преобразования кодов первой группы соединен в этом узле с k-ми управляющими входами k,k+1, m-1 элементов И, выход первого элемента ИЛИ первой группы соединен с первым входом первого шифратора первой группы, выход (k+l)-ro элемента ИЛИ первой группы соединен с информационным входом, k-ro.элемента и первого узла преобразования кодов первой группы, выход k-ro элемента И является (k+l)-M выходом этого узла и подключен к )-My входу первого шифратора первой группы, в 1-м узле преобразования кодов первой группы выход s-ro элемента НЕ (,2,„о.,m-l) подключен к s-му управляющему входу (s,5+1,о о о,т-1)-го элементой И первой группы, информационный вход s-ro элемента И первой группы соединен с входом (s+l)-ro элемента НЕ и выходом (s + l)-ro И второй группы, прямой вход z-ro элемента И второй группы (,2,о о„,т-1 + 1) соединен с выходом (z+1-l)-ro элемента ИЖ первой группы, а инверсный вход - с

5

0

5

0

(z+l)-M выходом (1+1)-го узла преоб- разования кодов первой группы, выход

первого элемента И второй группы соединен с входом первого элемента НЕ

и является первым входом 1-го узла преобразования кодов первой группы, выход 5-го элемента И первой группы является (s+l)-M выходом 1-го узла преобразования кодов первой группы, t-й вход 1-го шифратора первой групп (,1+1,,„,т), соединен с (t-l+1)выходом 1-го узла преобразования кодов первой группы, выходы каждого шифратора первой и второй групп соединены с входами соответствующего выходного регистра соответственно : первой и второй групп, выходы вы- ходных регистров являются выходами упорядоченных чисел устройства, информационный вход г-го элемента И первой группы соединен с выходом г-г элемента И второй группы (,2,о.., 2 1 |2 о, ,q)H через г-й эле- мент НЕ подключен к г-м управляющим входам (г+1)-го, (г+2)-го, о. о, (т-р+1)-го элементов И первой группы отличающееся тем, что, с целью повьщ1ения быстродействия, в устройство введены вторая группа из q элементов ИЛИ и дешифратор, входы которого подключены к выходам соответствующих элементов ИЛИ первой группы, входы 2 -го элемента ИЛИ второй группы соединены с выходами дешифратора, двоичные коды номеров которых содержат р+ч и более единиц прямой вход г-го элемента И второй группы У -го узла преобразования кодов второй группы подключен к выходу (m-r+l)-ro элемента ИЛИ первой группы информационный вход ()- го элемента И первой группы у -го узла преобразования кодов второй группы соединен с выходом ()-го

Редактор И„Горная Заказ 4222/38

Составитель ЕоИванова Техред М.Ходанич

Корректор

Тираж 672Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., До4/5

.Производственно-полиграфическое предприятие, г,Ужгород, ул.Проектная,4

0

5

Q

5

0

5

0

элемента ИЛИ первой группы, выход I-го элемента И первой группы У -го узла преобразования кодов второй группы подключен к (т-г-1)-му входу у-го шифратора второй группы, выход J -го элемента ИЛИ второй группы соединен с дополнительными управляющими входами элементов И первой группы у-го узла преобразования кодов второй группы, выход ()-го элемента ИЛИ первой группы, где /3 1,2, .о.,П1-п соединен с информационным входом -го элемента И группы q-ro узла преобразования кодов второй группы, выход которого соединен с ()-м входом q-ro шифратора второй группы, выход q-ro элемента ИЛИ второй группы соединен с дополнительными управляющими входами элементов И группы q-ro узла преобразования кодов второй группы, (т-р+)-й вход 2-го шифратора второй группы, кроме первого, соединен с инверсными входами (p- + l)-x элементов И второй группы (f-l)-ro, (2-2)-го,„ао,1-го узлов преобразования кодов второй группы, инверсный вход элементов И второй группы с (q-g+1)-ro по (т-р- Ч)А f о узла преобразования кодов второй группы подключен к выходу соответствующего элемента И первой группы (у4-1)-гр узла преобразования кодов второй группы, в q-M узле преобразования кодов второй группы информационный вход и -го элемента И через /3 -и элемент НЕ группы соединен с 1 -ми управляющими входами (+1)- го (/3+2 -го, о о о, (m-n)-го элементов И группыо

Корректор НоКороль

Изобретение относится к вычислительной технике и мржет быть использовано при реализации систем обработки данных и автоматизированных систем управления„ Устройство содержит п входных регистров 1,п дешифраторов 2, первую группу из m элементов ИЛИ 3 (т - количество разрядов анализируемых чисел в позиционной форме их представления), первую группу из р узлов 4 преобразования кодов,, вторую группу из q узлов 5 преобразования кодов (, если п - четное, р(п + 0/2, , если q - нечетное), первую и вторую группы шифраторов 9 и IО по р и q шифраторов i (Л САд 00 со СП j;; 00