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

,Йс САНИЕ ИЗОБРЕТ улл чГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЦТИЯПРИ ГКНТ СССР А ВТОРСКОМУ СВИДЕТЕЛЬСТВ(56) Авторское свидетельство СССРВ 1203509, кл. С 06 Р 7/06, 1,984.(54)(57) УСТРОЙСТВО ДЛЯ УПОРЯДОЧЕНИЯи ЧИСЕЛ по авт. св. 1 1203509,о т л и ч а ю щ е е с я тем, что,с целью расширения области применения за счет формирования упорядоченного массива чисел, меньших напередзаданного, в него введены регистрзаданного числа, дополнительный дешифратор, первая группа из (ш - 2)элементов ИЛИ, вторая группа из иэлементов ИЛИ, группа из (и - 1)элементов И, дополнительный шифратор, регистр размера массива и триггер режима, вход установки в едининое состояние которого соединен свходом задания режима упорядочиванияограниченного массива устройства, авход установки в нулевое состояниес входом задания режима упорядочениявсего массива устройства и входомустановки в ноль регистра заданногочисла, вход управления записью которого подключен к прямому выходутриггера режима, а выходы разрядовсоединены с входами дополнительногодешифратора, первый выход которогосоединен с первыми входами элементов ИЛИ первой группы, и инверснымвходом первого элемента И первого1 узла преобразования кодов и вторым инверсным входом первого дополнительного элемента И второго узла преобразования кодов, второй выход дополнительного дешифратора подключен к вторым входам элементов ИЛИ второй группы, р-й выход дополнительного дешифратора (р = 3, 4, ш - 1) соединен с р-ым входом (р)- го элемента ИЛИ первой группы, вы- ход о-го элемента ИЛИ первой группы, где с 1 = 1,2 (тп - 2) соединен с дополнительным инверсным входом (о + 1)-го элемента И первого узла преобразования кодов и дополнительными инверсными входами (о + 1)-го т 1-го (Ч - 1)-го(тп - 3)-го дополнительных элементов И соответственно 2-го, З-го, (ш - 1)-го узлов преобразования кодов, выходы -го выходного регистра (т.=12 и) подключены к входам -го элемента ИЛИ второй группы, выход-го эле мента ИЛИ второй группы (=12и) соединен с прямым входом р-го элемента И группы,-й инверсный вхо-го элемента И группы (= 1, 2, и - р) подключен к выходу (и-+1)- го элемента ИЛИ второй группы, выход-го элемента И группы соединен с-м входом дополнительного шифрато ра, и-й вход которого подключен к выходу и-го элемента И первой группы, а выходы дополнительного шифратора соединены с соответствующими входами регистра размера массива, выходы которого являются выходами размера массива устройства.Изобретение относится к вычислительной технике, может быть использовано для реализации систем обработки данных и автоматизированныхсистем управления и является дополнительным к основному авт. св,Р 1203509.На чертеже приведена функциональная схема предлагаемого устройства,Устройство содержит информационные входы 1, входные регистры 2, дешифраторы 3, элементы ИЛИ 4, узлы5 преобразования кодов, выполненные на элементах И 6, НЕ 7 И 8,шифраторы.9, выходные регистры 10,выходы 11, триггер 12 режима, регистр заданного числа 13, дополнительный дешифратор 14, группу элементов ИЛИ 15, группу элементов ИЛИ16, группу элементов И 17, дополнительный шифратор 18, регистр размерамассива 19, выходы размера массива20 устройства, входы 21 заданногочисла устройства, входы 22 и 23 задания режима,Рассмотрим принципы построения иработу устройства,Упорядочивание исходного массиваустройством может выполняться вдвух режимах: упорядочивание всегоисходного массива; упорядочиваниечисел, меньших наперед заданного.Выбор режима работы обеспечиваетсятриггером режима 12, управляемогопо входам 22 и 23. Установка первогорежима производится по сигналу свхода 23, переключающему триггер 12и регистр 13 заданного числа в нулевое состояние.Для формирования упорядоченногоМмассива во втором режиме в регистр13 заданного числа поступает граничное значение массива, а по входу 22триггер режима устанавливается всостояние "1",В обоих режимах упорядочение исходного массива выполняется одинаково.Пусть необходимо получить упорядоченьгый массив из 4-х чисел,Исходное состояние устройствахарактеризуется тем, что выходныерегистры 10 и регистр 19 установленыв состояние "0", во входные регистры2 принят по входам 1 массив исходныхчисел, и по входу 23 триггер режимаи регистр заданного числа установленыв состояние "0", При этом выходные сигналы дешифратора 14 и соответственно элементов ИЛИ 15 принимаютнулевые значения, аткрьваяпо инверсным входам соответствующие элементы5И во всех узлах 5 преобразованиякодов,Пусть в регистры 1 принят массивисходных чисел: а, = 5 а -аэ - 4, а 5- 2,В соответствии с табл,1 единичныесигналы появляются на пятом выходедешифратора 3, первом - дешифратора,3, на четвертом в ,цешифратора 39и на втором - дешифратора 3+,Из анализа табл,1 видно, что по-.рядок размещения единичных сигналов,если объединить одноименные выходыдешифраторов, соответствует возрастанию значений чисел, и по существуномер выхода дешифратора отражаетзначение числа на его .входе.Посредством элементов ИЛИ 4 проводится объединение одноименныхвыходов дешифраторов, Как следует изтабл.1, позиционный код ка выходахэлементов ИЛИ 4 имеет вид 11011. Всоответствии с этим кодом в выходных регистрах 10 необходимо разметить числа в следующем порядке возрастания значения Ь = 1, Ь = 2,Ь = 4, Ь= 5. Это обеспечиваетсясоответствующими шифраторами 9, навходы которых необходимо податьследующие позиционные коды:10000 - на входы шифратора 9,01000 - на входы шифратора 900010 - на входы шифратора 900001 - на входы шифратора 9Преобразование исходного позиционного кода, полученного элементами ИЛИ 4, производится соответствующими узлами 5 преобразования кодов.В узле 5 на его входы подаетсяпозиционный код 11011, При этом единичный сигнал на его входе черезэлемент НЕ 7 закрывает все элементыИ 8, поэтому на выходе узла 5 Формируется код 10000,Формирование входного кода длявторого узла 5 должно выполнятьсяс учетом работы предыдущего узла 5,т.е. необходимо при анализе исключитьвыделенное значение числа, Эту функцию выполняют элементы И 6, насгинверсные входы которых поступаютвыходные сигналы узла 5, а напрямые сигналы с выходов элементовИЛИ 4, т,е,153637 10000 01111 40 выходы узла 5,обратный кодвыходы элементовИЛИ 4 11011выходы элементов И 6 01011В узле 5 из выходных сигналовэлементов И 01011 за счет блокиров 6ки элементов И 8 нулевым сигналомс выхода элемента НЕ 7, формируетсявыходной код 01000, поступающий нашифратор 9.Построение узлов преобразованиякодов 5 5 . выполнено с учетомминимизации оборудования, что поясняется табл .2, когда массив исходных чисел. размещается в входныхрегистрах, причем значения чисел лежат в пределах 1-5 и в этом диапазоне могут принимать одинаковые значения. Из табл.2 видно, что при формировании позиционного кода для очередного узла преобразования, например, для узла 5 нет необходимостив Формировании первой позиции кода, 25для узла 5 - первых двух и так далее, так как единичные сигналы этихпозиций уже использованы для Форми -рования знпчений упорядоченных чисел .Такое положение справедливо до формирования входного кода для узла Е ,При этом число входов шифраторов9 равно ш и при щ и входные сигналы для 1-го шифратора, где 1 =.2, 3,и, подаваемые на входы"1, 2,(1 - 1), равны нулю, Поэтому, хотя35эти поразрядные узлы преобразованиякодов выполняют одинаковые Функциидлй любого из 1.-го регистров, когдад = 1,2 п, имеется возможностьминимизации оборудования с учетомразмещения узла,2 6разования кодов 5, блокирующие передачи чисел в выходные регистры 10,больших или равных заданному,Формирование этих управляющихсигналов для приведенных выше условий отражено в табл.З.Пусть для приведенного примеранеобходимо сформировать упорядоченный массив чисел, меньших числа,равного 4.Устройство работает следука 1 имобразом.Двоичный код 100 по входам 21принимается в регистр 13 после установки триггера режима 12 по входу22 в состояние "1", При этом начетвертом выходе дешифратора 14 Формируется един 1 чный сигнал . В соответствии с табл,З с помощью дешифратора 14 и элементов ИЛИ 15 формируется следующий позиционный кодуправляющих сигналов 0011. Нулевымисигналами с второго выхода дешифратора 14 открыты по инверсным входамэлемент И 8 в первом узле преобразования кодов 5 и элемент И 6 вовтором узле 5, Нулевым сигналом свыхода элемента ИЛИ 15открыты впервом узле 5 - элемент И 8, вовтором - элемент И 6, в третьем -элемент И 6. Единичными сигналамис выходов элементов ИЛИ 15 , ИЛИ 15 ззакрыты по инверсным входам остальные элементы И 8 в первом узле 5 иэлементы И 6 в остальных узлах 5. Выбор и расстановка чисел выполняется аналогично рассмотренному выше. При этом выходной массив в регистрах 10 имеет вид Ь = 1, Ь2, ь,=о, ь,=о.Во второй режим устройство переводится при наличии сигналов двоичного кода заданного числа на входах 21 устройства и управляющего сигнала на входе 22, которым устанавливается в "1" триггер режима, По единичному сигналу с выхода триггера, поступающему на вход синхронизации регистраФ заданного числа, двоичный код заданного числа принимается в этот регистр, При этом с помощью дешифратора 14 и элементов ИЛИ 15 Формируются управляющие сигналы для узлов преоб 45 50 55 В дальнейшем с помощью элементовИЛИ 16 формируется следующий код1100,Единичным сигналом с выхода элемента ИЛИ 16 закрыт по соответствующему инверсному входу элемент И 17,При этом на входах шифратора 18 устанавливается позиционный код 0100по которому. на выхрдах 20 устройст-.ва формируется двоичньп код числа 2,означающий, что упорядоченный массивчисел, меньших заданного, размещенв первых двух выходных регистрах 10.1536372 л и ц а 1 Таб выхода дешифратора 3 3 Номер Код числа 1 Га, =101а = 001йа = 1009а = 010ф 0 1 0 0 1 0 0 0 Таблица 2 еВыходныесигналы Выходныесигналы Входные ВыходныесигналыэлементаИЛИ 4 Номери/и Входные;.сигналышифратора9 сигналышифратора9 элемента И 6 узла5 элементаИ б узла5 10000 2 01000 3 11000 4 00100 5 10100 6 01100 7 11100 8 00010 9 10010 10 01010 11 11010 12 00110 13 10110 14 01110 15 11110 16 00001 17 10001 18 01001 19 11001 20 00101 21 10101 22 01101 23 11101 24 00011 25 10011 26 01011 27 11011 28 00111 29 10111 30 - 011111536372 Таблица 3 Сигналы блокировки передачи чисел ввыходные регистры 10 для заданных кодов Двоичные кодызаданного числа Составитель дактор М,Недолуженко Техред М.Дидвано орректорТ Пачии Заказ 109 Тираж 551 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ С113035, Москва, Ж, Раушская наб., д. 4/5 роизводственно-издательский комбинат "Патент", г.ужгор Гагарина 010 011 100 101 1 0 0 0 1 1 0 0 1 1 0