Устройство для упорядочивания @ чисел

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН

<191 (11) 54 A l (51)4 G 06 F 7 06

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4020841/24-24 (22) 27.01.86 (46) 23.09.87. Бюл. ¹ 35 (72) В.Г.Попов, В,Р,Насибуллин .и И.Н.Фатыхов (53) 681.325 (088.8) (5e) Авторское свидетельство СССР № 1062687, кл. G 06 F 7/06, 1982.

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

¹ 1203509, кл. С 06 F 7/06, 1984, (54) УСТРОЙСТВО цЛЯ УПОРЯДОЧИВАНИЯ . К ЧИСЕЛ (57) Изобретение относится к вычислительной технике и может быть использовано при реализации систем обработки данных и автоматизированных систем управления. Устройство содержит и входных регистров l, n дешифраторов 2, первую группу из m элементов

ИЛИ 3 (m — количество разрядов анализируемых чисел в позиционной форме их представления), первую группу иэ р узлов 4 преобразования кодов,, вторую группу из q узлов 5 преобразования кодов (p=q=n/2, если n — четное, р=(п + 1)/2, q=n-ð, если q - нечетное), первую и вторую группы шифраторов 9 и 10 по р и q шифраторов

1339548 а, = 101 а = OO1 а = 100 а = 010

0 0 0

Выходные сигналы

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

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

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

На чертеже приведена структурная схема предлагаемого устройства (при

n=4 когда значения чисел массива лежат в пределах 1-5 (m=5).

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

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

Исходное состояние устройства характеризуется тем, что входные 1 и выходные 11 и 12 регистры установлены в состояние "0" (не пока ано), Для упорядочивания чисел исходный массив принимается во входные регистры 1 по входам 15. Через некоторое время, определяемое переходными процессами в элементах схемы, в выходных регистрах 11 и 12 формируется упорядоченный массив чисел, Работу устройства условно можно разделить на два этапа. На первом этапе посредством дешифратора 2 и элементов И!И 3 производится упорядоупорядоченных чисел из выходного кода элементов ИЛИ 3 начиная с крайней леной единицы, а вторая половина узлов — начиная с крайней правой единицы. За счет такого разделения производится как бы встречная расстановка чис ел, ч то по зволяет по в ьк ить б ыс тро†действие устройства. 1 ил., 2 табл. чивание величин чисел, начиная с наименьшего ненулевого значения, на втором — встречная расстановка чисел в выходных регистрах 11 и 12 ° с помощью узлов 4 и 5 преобразования кодов, дешифратора 13 и группы элементов ИЛИ 14.

Работа устройства на первом этапе.

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

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

2, четвертом дешифратора 2 и на втором дешифратора 2 .

Т а б л и ц а 1

Код числа Номера выходов дешифраторов ? f y o o o р 24

1 2 3 4 5

0 0 0 0 1

1 0 0 0 0

0 0 0 1 0

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

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

1339548

RG9, RG9z

RGI 0< йГ10

RG9I

Ы9, 35

Входные сигналы узла 4 шифратора 9

О 0000

О 0000

О 1000

О 0000

О 0100

О 0100

P ооо!Оо!

000 00

000 00

Ооо 00

000 00!

000 00

00 000

00 000

00 000

00 000

00 000

00 000

oI0ooo о оооо

О 1000

l

О 0000

О Oloo

О OIOO оо ооо оо оооо

00 000

00 000

00 000

00 000!

l !0000 !0000

2 01000 О!000

3 I!000 10000

4 00!00 00100

5 !О!00 10000

6 О!!00 01000 код на выходах элементов ИЛИ 3 имеет вид 11011 (табл .1), В соответствии с этим кодом в выходных регистрах

11 и 12 необходимо разместить числа в порядке возрастания значения Ь, =1, 5

b = 2, Ь1= 4, Ь = 5. Это обеспечивается соответствующими шифраторами 9 и 10, на выходы которых необходимо подать следующие позиционные коды. 10000 на входы шифратора 9, 01000 на входы шифратора 9, 00010 на входы шифратора 10 00001 на входы шифратора 10 .

Формирование указанных позиционных кодов производится на втором этапе работы устройства из выходных сигналов элементов ИЛИ 3 посредством узлов 4 и 5 преобразования кодов.

При этом в каждом узле 4 должны иск-.. 20 лючаться из анализа выделенные крайние левые единичные сигналы элементов

KIH 3 в предыдущих узлах 4. Для приведенного примера последовательное преобразование выходных сигналов 25 элементов ИЛИ 3 можно условно показать следующим образом

11011 — 10000 01011 01011

-+0001!†00010 — 00001 00001

RG10, RG10

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

Набор Выходные сигналы

НЛН Э шифратора 9 чисел.. Тогда такое преобразование условно выглядит следующим образом.

I I 011 10000 — 01011 O I 000

000010 01010 00001 11011

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

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

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

Таблицами

1 узла 5< шифрато- пифрара !О, тора !О

1339548

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

Входные сигналы

Выходные сигналы

ИЛИ 3

Набор узла 4, шнфрато- узла 5, ра 9 шифра" тора 9, шифратора 10, шифратора 10.

10000

00010

10000

01000

10000

00100

10000

0!000

10000

0000!

)0000

01000

)0000

1000О

01000

)0000

00010

)0000

)0000

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

Из табл„2 следует, что в регистре должно размещаться наименьшее число, значение которого соответствует номеру крайнего левого возбужденного элемента K)II 3,. Выделение крайней левой единицы производится в узле 4, элементами И 7, подключенными к «ыходлм элементов И. )И 3 по

1 11100

8 000)0

9 10010

10 01010

11 11010

12 00110

13 10110

14 01110

l5 1!110 !

6 00001

17 10001

18 0100!

19 11001

20 OOIOI

21 )0!01

22 01101

23 1! 101

24 0001 1

25 10011

26 0101!

27»011

28 00» l

29 10»1

30 01!1) О 1100 !

О 0000 !

0 ОО!О !

О 0010 !

0 10)О !

0 0010 !

) 0110 !

О 0110

0 1110 !

О 0000 !

О 0001 !

О 0001 !

О 1001 !

О 0001 !

0 0!01

О 0101 !

О 1101 !

О 0001 !

О 00»

0 ОО» !

О 101) !

О 00» !

О О!)Е !

О)О!»

О 1000

Oi0000 ! !

О 0010 ! о! оо!о

О 1000 !

О 0010

О 0100

О 0100 !

О 1000 !

О 0000 !

0 000) !

0 000! !

0 1000 !

О 0001 !

О 0100 !

О OIOO

О 1000 !

О 0001 !

О 0010. !

О 0010 !

О )000 !

О 00)0 !

О 0100 ! о!о!оо оо)!Оо

0О!0О0!

00 000!

00(000 оо!о!о

00 000

00!010

ОО)О)О

00!110

00(000

00 000

00 00!

00 001!

00 000!

00 001!

00 001

00 101!

00 000

00 OOI!

00 001

00 Oll!

00 00!!

00 Oll! оо!о»

00 100!

00 000

00 000!

00 000

00,010

00,000!

00 0)0!

0O,О10!

00 100!

00, 000!

00 000!

00(000

00 001!

0О!ОО0

00 001

00 001!

00 !00

00 000 оо !оо!

00 001!

00 010

00 OOI!

00 010.О0 О!О

000 00!

000 00!

000 00!

000 00!

000 00!

000 00!

000 ОО!

000 00!

000 10!

000 00!

000 00!

000 00!

000 00

000 00!

000 00!

OOO 00!

000 Ol!

000 О(!

000,0С!

000 00

000 Ol!

000 00!

000 01 ооо!о!

l339548 выполняется в узле 4„ посредствам элементов И 8, на прямые входы которых подаются выходные сигналы элементов ИЛИ 3 а на инверсные выхадУ

5 ные сигналы узла 4, (табл,2,27 набор). выходной код узла 4, 10000, обратный кад 01111, выходной код элемента ИЛИ 3 11011, выходной код элемента И 8 01011.

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

Размещение чисел во второй половине регистров 12 производится следующим образом, 30 формирование единичных сигналов для шифраторов 10 (табл,2, 8-й столбец) выполняется только тогда, когда число возбужденных выходов элементов ИЛИ 3 равно четырем (15,23,27, 35

29 и 30 наборы), а для шифратора 10, (табл.2, 7-й столбец) - когда число возбужденных выходов элементов

ИЛИ 3 больше двух (7,11,13,1.4,15,19, 21,22,23,25,26,27,28,29 и 30). 4

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

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

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

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

Управление элементами И 7 в узле

5, производится единичным сигналом с выхода элемента ИЛИ 14,„

Например (табл .2, ?7-й набор), выходными сигналами элемента ИЛИ 14, элементы И 7 в узле 5, открыты, При этом выходной код узла 5 00001, обратный кад 00010, вых<.дной код элемента ИЛИ 3 11011, выходной кад элемента И 8 00010, входной кад шифратора 10, 00010. Таким образом, в регистрах 11 и 12 числа размещены в порядке Ь, =1, Ь =2, Ь =4, Ь,, =-5.

Построение устройства для лраизвальнаГо количества сартируемых чисел п и максимального значения Jlf060ro из них, определяемого па выражению

m = 2 — 1, где k - разрядность чисАнализ количества единиц выполняется посредством дешифратора 13 и элементов ИЛИ 14.

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

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

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

ИЛИ 14 разрешается рабата в узле

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

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

l 339548 ла в двоичной системе счисления, выполняется в соответствии с указанными принципами.

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

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

4(1=2,3,...,п/2) определяется выраже. ниями и (m

ИТ НЕ6

При этом в первом узле 4, входы элементов И 7 совместно с элементами

НЕ 6 подключены к выходам элементов

ИЛИ 3 по приоритетной схеме. В каж- 25 дом узле преобразования 4,...,4 „ входы элементов И 7 и НЕ 6 подключены к выходам элементов И 8 также по приоритетной схеме, Выходы элементов И 7 каждого узла 4, кроме n/2-ro, соединены с инверсными входами соответствующих элементов И 8 последующего узла.

Построение узлов преобразования кодов во второй группе выполняется с учетом того, что расстановка чисел, начиная с n/2-го регистра 12, производится путем последовательного выделения крайней правой единицы из выходных сигналов элементов ИЛИ 3. 40

При этом исключение из анализа выделенных единиц в узлах 5 производится путем блокировки элементов И 8 единичными сигналами позиционных кодов с выходов элементов И 7 предыдущих узлов. формула изобретения

Устройство для упорядочивания и чисел, содержащее и входных Регистров, 50 и дешифраторов, первую группу из а элементов ИЛИ (m — количество разрядов анализируемых чисел в позиционной форме их представления), первую группу из р узлов преобразования кодов, вто- 55 рую группу из q узлов преобразования кодов (p=q=n/", если п-четное, р=

=(и + 1)/2, q = n " р, если и — нечетное), первую и вторую группы шифраторов по р и q шифраторов соответ— ственно, первую и вторую группы выходных регистров по р и q выходных регистров соответственно, первый узел преобразования кодов первой группы содержит m-1 элементов НЕ и

m-1 элементов И, 1-й узел преобразования кодов первой группы (1=

=2,3,...,р) содержит первую группу из m-1 элементов И, m-1 элементов

НЕ и вторую группу из m-1+1 элементов

И, j-й узел преобразования кодов вто-! рой группы (j =1,2,...,q-1) включает две группы элементов И и группу элементов НЕ, q-й узел преобразования кодов второй группы содержит группу элементов И и группу элементов НЕ, причем выходы i-го входного регистра (1=1,2,...,n) входы которого являются входами i-ro числа устройства, соединены с входами i ãî дешифратора, j-й выход 1-го дешифратора (j=l,2...,,m) соединен с i ì входом

j""го элемента ИЛИ первой группы, вы— ход k-го элемента ИЛИ первой группы (k=1,2,...,m-l) через k-й элемент НЕ первого узла преобразования кодов первой группы соединен в этом узле с k-ми управляющими входами k>k+1, m-1 элементов И, выход первого элемента ИЛИ первой группы соединен с первым входом первого шифратора пер-. вой группы, выход (k+1)-ro элемента ИЛИ первой группы соединен с информационным входом k-ro элемента и первого узла преобразования кодов первой группы, выход k-ro элемента Иявляется (k+1) -м выходом этого узла и подключен к (k+1)-му входу первого шифратора первой группы, в 1-м узле преобразования кодов первой группы выход s го элемента НЕ (s=1,2,...,m 1) подключен к s-му управляющему входу . (s,s+1 я-1)-ro элементов И первой группы, информационный вход s-ro элемента И первой группы соединен с входом (s+1)-ro элемента НЕ и выходом (s+l}-го элемента И второй группы, прямой вход z-го элемента И второй группы (z=1,2,...,m-1+1) соединен с выходом (z+1-1)-го элемента KIH первой группы„ а инверсный вход — с (z + 1)-м выходом (1+1)-ro узла преобразования кодов первой группы, выход первого элемента И второй группы соединен с входом первого элемента НЕ! 339548!

Составитель Е.Иванова

Техред М.Ходанич

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

Редактор И.Горная

Заказ 42?2/38

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

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

113035, Москва, Ж-35, Раушская наб., д.4/5.Производственно-полиграфическое предприятие, г.ужгород, ул.Проектная,4 и является первым входом 1-го узла преобразования кодов первой группы, выход s-ro элемента И первой группы является (s+ ) -м выходом 1-го узла

В преобразования кодов первой группы т

t"é вход 1-ro шифратора первой группы (t=!,1+1,...,m), соединен с (t-1+1)-м выходом 1-го узла преобразования кодов первой группы, выходы каждого ið шифратора первой и второй групп соединены с входами соответствующего выходного регистра соответственно: первой и второй групп, выходы вы- ходных регистров являются выходами упорядоченных чисел устройства, информационный вход r-ro элемента И первой группы соединен с выходом r-го элемента И второй группы (г=1,2,..., m-p- ), g =1,2,...,ц)и через r-й элемент НЕ подключен к г-м управляющим входам (r+1) -го, (г+2) -го...,,(m-p- g+

+1)-го элементов И первой группы о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в устройство введены вторая группа из

q элементов ИЛИ и дешифратор, входы которого подключены к выходам соответствующих элементов ИЛИ первой группы, входы g -го элемента ИЛИ

30 второй группы соединены с выходами дешифратора, двоичные коды номеров которых содержат p+ у и более единиц, прямой вход r-го элемента И второй группы (-го узла преобразования кодов второй группы подключен к выходу (m-r+1) -го элемента ИЛИ первой группы, информационный вход (m-p-(+1)ro элемента И первой группы g -го узла преобразования кодов второй груп- 4О пы соединен с выходом (р+ +2)-го элемента ИЛИ первой группы, выход

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

И группы q-го узла преобразования кодов второй группы, (m-р+ )-й вход

) † шифратора второй группы, кроме первого, соединен с инверсными входами (р- +1)-х элементов И второй группы (n -1) -го, (-2) "ro, 1-го узлов преобразования кодов второй группы, инверсный вход элементов И второй группы с (q- +1)"ro по (m-р"()-й (-го узла преобразования ко" дов второй группы подключен к выходу соответствующего элемента И первой группы (+1)-гр узла преобразования кодов второй группы, в q-м узле пре-! образования кодов второй группы информационный вход Р -го элемента И через $ -й элемент НЕ группы соединен с -ми управлякицими входами (+1)ro (P +2 -го,...,(m-n) -го элементов И группы.