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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИРЕСПУБЛИН 9) И 1) 5 51)4 006 Г 70 ОПИСАНИЕ ИЗОБРЕТЕК АВТОРСНОМЪГ СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫИ НОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТ(57) Изобретение относится к вычислительной технике и может быть испол зовано при реализации систем обработки данных и автоматизированных систем управления. Устройство содержити входных регистров 1,о дешифраторов 2, первую группу из в элементовИЛИ 3 (щ " количество разрядов ана"лизируемых чисел в позиционной формеих представления), первую группу иэр узлов 4 преобразования кодоввторую группу из 1 узлов 5 преобразования кодов (р=ц=п/2, если и - четное, р=(п + 1)/2, о=п-р, если с 1 - нечетное), первую и вторую группы шифраторов 9 и 10 по р и с 1 шифраторов1339548 а, = 101 а = ОО 1 а = 100 а = 010 0 О 0 0 Выходныесигналы 0 1 1 соответственно, первую и вторую группы выходных регистров 11 и 12 пор и ц регистров соответственно, Цельизобретения - повьшение быстродействия, Выходные регистры и узлы преобразования кодов разделяются на дверавные группы, При этом первая половина узлов обеспечивает формирование Изобретение относится к вычислительной технике и может быть использовано при реализации систем обработки данных автоматизированных сис 5 тем управления.Цель изобретения - повышение быстродействияНа чертеже приведена структурная схема предлагаемого устройства (при п=4, когда значения чисел массива лежат в пределах 1-5 (в=5).Устройство содержит входные регистры 1, дешифратор 2, первую группу элементов ИЛИ 3, первую группу 4 и вторую группу узлов 5 преобразования кодов, включающих в себя группы элементов НЕ 6, элементов И 7 и И 8, первую группушифраторов 9, вторую группу шиФраторов 10,первую группу выход ных регистров 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 Код числа Номера выходов дешифраторов 2, уооор 2 1 2 3 4 5 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 Из табл,1 видно, что порядок размещения единичных сигналов, если объединить одноименные выходы дешифраторов , соответствует возрастанию значений чисел.Посредством элементов ИЛИ 3 про изводится объединение одноименных выходов дешифраторов, Позиционный1339548 В 69,869 В 610,й 610 30 Й 69,92 35 Входные сигналы уэла 4 шифратоРа 9 е0 0000 0 0000 0 000 0 0000 0 О 00 0 0100Р 000 00000 00Ооо 00000 00000 001 0000 10000 2 01000 О 000 Э 1000 10000 4 0000 00100 5 10100 10000 6 01100 01000 код на выходах элементов ИЛИ 3 имеетвид 11011 (табл,1), В соответствиис этим кодом в выходных регистрах11 и 12 необходимо разместить числав порядке возрастания значения Ь, =1,5Ь = 2, Ь 1= 4, Ь = 5. Зто обеспе"чивается соответствующими шифраторами 9 и 10, на выходы которых необхо"димо подать следующие позиционныекоды,10000 на входы шифратора 901000 на входы шифратора 9, 00010на входы шифратора 1 О 00001 навходы шиФратора 10,формирование указанных позиционных кодов производится на второмэтапе работы устройства из выходныхсигналов элементов ИЛИ 3 посредствомузлов 4 и 5 преобразования кодов,При этом в каждом узле 4 должны исключаться из анализа выделенные крайние левые единичные сигналы элементовИЛИ 3 в предыдущих узлах 4. Для при"веденного примера последовательноепреобразование выходных сигналов 25элементов ИЛИ 3 можно условно показать следующим образом 11011 - 10000 01011 0101-+0001 в -00010 - 00001 00001 8610, Й 610 Из этой схемы преобразования следует, что данный процесс можно уско рить за счет встречной расстановки Набор ВыходныесигналыНЛИ Э шифратора 9 чисел. Тогда такое преобразование условно выглядит следующим образом: 1011 10000 0101 О 000 000010 в 010 в 00 в 110 Данная схема может быть реализова на путем разделения выходных регистров на. две равные независимые группы с соответствующими узлами преобразования кодов, При этом в первой группе узлов 4 преобразования производит" ся формирование позиционных кодов для соответствующих шифраторов 9 путем последовательного вьщелениялевой единицы из выходных сигналов элементов ИЛИ 3, а во второй группе 5 - путем последовательного выделения крайней правой единицы из выходных сигналов элементов ИЛИ 3. Такое решение справедливо для частного случая, когда во входных регистрах 1 размещен массив чисел различных по величине. При этом число возбужденных выходов элементов ИЛИ 3 равно числу выходных регистров. Если во входные регистры 1 принят ряд одинаковых кодов либо нулевые коды одного или нескольких чисел, количество возбужденных выходов элементов ИЛИ 3 меньше числа выходных регистров.Для пояснения принципов построения устройства используется табл,2истинности для различных значений выходных сигналов элементов ИЛИ 3,.Таблица 21 е и 1узла 5 шифрато- шифра"ра О, тора О1339548 Продолжение табл,2 Входные сигналы ВыходныесигналыИЛИ 3 Набор узла 4, шифрато- узла 5, ра 9 шифра" тора 9,шифрато"ра 10,шифратора 10.Е 10000 00010 30000 01000 10000 00100 10000 0)000 10000 0000) 30000 03000 30000 00100 0000 01000 10000 00010 10000 0100030000 00100 10000 01000 приоритетной схеме с помощью элементов НЕ 6 Дляразмещения следующегонаименьшего числа в регистре )3 изоставшихся исключается выбранноечисло путем операции логического умножения выходных элементов ИЛИ 3 синверсным кодом выходных сигналовэлементов И 7 узла 4 Эта операция Из табл 2 следует, что в регистре ) должно размещаться наименьшее число, значение которого соответствует номеру крайнего левого возбужденного элемента ИИ 3 Выделение крайней левой единицы производится и узле 4, элементами И 7, подключенными к ыходам элементов И.13 3 по 1 11)00 8 000)О 9 10010 10 01010 11 110) 0 12 00110 33 )0110 14 01110 15 11110 36 00001 17 10001 18 01003 39 1100 20 0003 21 30301 22 01101 23 13 101 24 00011 25 10011 26 010127 1013 28 00111 29 10 11130 01)13 О 11000 00000 ООО0 00300 10 О0 00101 01100 03100 )1100 00000 00010 00010 3001О 00010 03030 01010 11010 00010 00330 00110 10110 0031О 03)Е0 0311 0 1000ООООО0 0010О ОО)О0 10000 00100 01000 01000 10000 00000 00030 0000 10000 00010 03000 О 000 10000 00010 0010.0 00100 30000 00300 010000100 ОООО00 00000000ООО)О00 00000010ООО)ОООО0000000 00000 0000 00300 00000 00100 001ОО 10300 00000 00100 00100 011Оо 00300 ОООО) 00 10000 00000 00000 00000,0 О300,00000 ОО00,01000 30000,00000 00000(00000 0010000000 00300 00100 10000 000ОО ОО00 00100 03000 00100 0101 О Анализ количества единиц выполняется посредством дешифратора 13 и элементов ИЛИ 14.С помощью элемента ИЛИ 14 объединяются сигналы с 15,23,27,29 и 30 выходов дешифратора 13, двоичные коды номеров которых содержат четыре единицы (табл.2, 1-й и 2-й столбцы). выполняется в узле 4 посредствамэлементов И 8, на прямые входы которых подаются выходные сигналы элементов ИЛИ 3 а на инверсные выхад5ные сигналы узла 4, (табл,2,27 набор)ф выходной код узла 4, 10000,обратный кад 01111, выходной кодэлемента ИЛИ 3 1101, выходной кодэлемента И 8 01011,В младшей позиции кода значениевыходного сигнала тождественно равнонулю при любом наборе выходных сигналов элементов ИЛИ 3 (табл,2,4-й столбец), поэтому входной сигнал для пер Бваго входа шифратора 9 также всегда равен нулю, Отсюда имеется возможность в минимизации оборудования узлов 4 преобразования кодов, начинаясо второго. Таким образом, с помощьюэлементов И 8 в узле 4 формируетсякод 1011, из которого с помощью эле-,ментов И 7 и НЕ 6, включенных с выходами элементов И 8 по приоритетнойсхеме, выделяется крайняя левая единиБца При этом на входах шифратора 9формируется позиционный код 01000,Размещение чисел во второй половине регистров 12 производится следую"щим образом, 30формирование единичных сигналовдля шиФраторов 10(табл,2, 8-й столбец) выполняется только тогда, когдачисло возбужденных выходов элементов ИЛИ 3 равно четырем (15,23,27,3529 и 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,Если число единиц равно тРем, Разрешается работа узла 5, и блокируетсяузел 5 , если число единиц равно четырем, разрешается работа узлов 5,и 5 , если число единиц меньше трех,работа узлов 5, и 5 блокируется. С помощью элемента ИЛИ 14, объединяются сигналы с 7,11,13,14,15,19,21, 23,22,25,26,27,28,29 и 30 выходов дешифратора 13, двоичные кс цы номеров содержат либо три, либо четыре единицы.Например (табл .2,27-й набор), единичным сигналом с выхода элемента ИЛИ 14 разрешается рабата в узле 5 элементов И 7, включенных с помощью элемента НЕ 6 с выходами двух старших элементов ИЛИ 3 па приоритетной схеме. Узел 5 выполнен с учетом вазможности минимизации оборудования. В регистре 12размещается наибольшее число из массива, поэтому на младших трех позициях шифратора 10 входные сигналы тождественны и равны нулю.Например (табл.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, 27-й набор),выходными сигналами элемента ИЛИ 14,элементы И 7 в узле 5, открыты, Приэтом выходной код узла 5 00001,обратный кад 00010, выхдной кодэлемента ИЛИ 3 11011, выходной кадэлемента И 8 00010, входной код шифратора 10, 00010. Таким образом, врегистрах 11 и 12 числа размещены впорядке Ь, =1, Ь :2, Ь =4, Ь, =5.Построение устройства для произвольного количества сартируемых чисел п и максимального значения любого из них, определяемого па выражениюв = 2 - 1, где 1 - разрядность чис 1339548ла в двоичной системе счисления, выполняется в соответствии с указанными принципами.При четном количестве каждая груп 5 па содержит по и/2 выходных регистров и и/2 узлов преобразования кодов, В данном случае узел 4 преобразования кодов содержит группу из Ь) элементов И 7 и группу из (в) элементов НЕ 6. Каждый последующий узел 441 включает в себя группы элементов И 7, И 8, НЕ б, число которых определяется местом размещения узла. В общем виде количество элементов И 7, И 8 и НЕ 6 для 1-го узла 4(1=2,3и/2) определяется выраже ниями20ЕПри этом в первом узле 4, входыэлементов И 7 совместно с элементамиНЕ 6 подключены к выходам элементовИЛИ 3 по приоритетной схеме. В каждом узле преобразования 44входы элементов И 7 и НЕ б подключенык выходам элементов И 8 также по приоритетной схеме,Выходы элементов И 7 каждого узла 4, кроме и/2-го, соединены с инверсными входами соответствующихэлементов И 8 последующего узла.Построение узлов преобразованиякодов во второй группе выполняетсяс учетом того, что расстановка чисел,начиная с и/2-го регистра 12, производится путем последовательного вы"деления крайней правой единицы из выходных сигналов элементов ИЛИ 3. 40При этом исключение из анализа выделенных единиц в узлах 5 производится путем блокировки элементов И 8единичными сигналами позиционных кодов с выходов элементов И 7 предыдущих узлов,формула изобретенияУстройство для упорядочивания и чисел, содержащее и входных регистров, 50 и дешифраторов, первую группу из а элементов ИЛИ (щ - количество разрядов анализируемых чисел в позиционной форме их представления), первую группу из р узлов преобразования кодов, вто рую группу из Ц узлов преобразования кодов (р=1=и/2, если и-четное, р= =(и + 1)/2, ц = и " р, если и - нечетное), первую и вторую группы шифраторов по р и с шифраторов соответственно, первую и вторую группы выходных регистров по р и с выходных регистров соответственно, первый узел преобразования кодов первой группы содержит щэлементов НЕ и юэлементов И, 1-й узел преобразования кодов первой группы (1= =2,3,р) содержит первую группу из щэлементов И, яэлементов НЕ и вторую группу из щ+1 элементов И, 1-й узел преобразования кодов второй группы ( =1,2 п)включает две группы элементов И и группу элементов НЕ, с 1-й узел преобразования кодов второй группы содержит группу элементов И и группу элементов НЕ, причем выходы 1-го входного регистра (1=1,2и), входы которого являются входами 1-го числа устройства, соединены с входами -го дешифратора, 3-й выход 1-го дешифратора (1=1,2 п соединен с 1-м входом 1"го элемента ИЛИ первой группы, вы - ход к-го элемента ИЛИ первой группы (1=1,2 п) через 1-й элемент НЕ первого узла преобразования кодов первой группы соединен в этом узле с )с-ми управляющими входами 1 с,1 с+1, щэлементов И, выход первого элемента ИЛИ первой группы соединен с первым входом первого шифратора пер-. вой группы, выход (к+1)-го элемента ИЛИ первой группы соединен с информационным входом 1-го элемента и первогО узла преобразования кодов первой группы, выход М-го элемента Иявляется (1+1) -м выходом этого узла и подключен к (к+1)-му входу первого шифратора первой группы, в 1-м узле преобразования кодов первой группы выход Б-го элементаНЕ (э=1,2в) подключен к з-му управляющему входу(з,э+1щ"1)-го элементов И первой группы, информационный вход з-го элемента И первой группы соединен с входом (э+1)-го элемента НЕ и выходом (э+1)-го элемента И второй группы, прямой вход л-го элемента И второй группы (У=1,2щ+1) соединен с выходом (г+1-1)-го элемента ИЛИ первой группы а инверсный вход - с (г + 1)-м выходом (1+1)-го узла преобразования кодов первой группы, выход первого элемента И второй группы соединен с входом первого элемента НЕ