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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИН 9) 01 18 А р С 06 Р 7/06 ОПИСАНИЕ ИЗОБРЕТЕК АВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ в ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИ(56) Авторское свидетельство СССР Р 903864, кл. С 06 Р 7/06, 1979.Авторское свидетельство СССР В 1059565, кл. С 06 Р 7/06, 1982. (54) УСТРОЙСТВО ДЛЯ ВЫБОРА УПОРЯДОЧЕННОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ДАННЫХ (57) Изобретение относится к автоматике и вычислительной технике, Целью изобретения является сокращение объема оборудования. Устройство содержит п входных регистров, и дешифраторов,п регистров результата, и групп элементов И, группы входных элементов И и ИЛИ, группу элементов ИЛИ, элемент ИЛИ, две группы элементов НЕ, коммутатор, состоящий из и групп элементов И, дешифратора и регистра, блок управления, содержащий триггер управления, счетчик, дешифратор, элементы И, ИЛИ, группу из и элементов И и енератор импульсов, информационные ходы и выходы, шины "Начальное гашение", "Начало операции" и "Размер массива". Новым является введение шифратора и и узлов сравнения, содержащих две группы элементов И, группу элементов ИЛИ и элемент И, и их связей в устройстве. На вход устройства может быть подан массив с( различных по значению чисел, причеми. С помощью устройствачисел сортируются в порядке возрастания, причемс п. Задача сводится к оп" ределению минимального числа, записи его в первый регистр результата и гашению того вхоцного регистра, котором оно находится, для исключения уже выбранного числа в очередном цикле анализа. Затем этот процесс повторяется, пока не выполнитсяциклов. По завершении р циклов в регистрах результата будет нахо" диться упорядоченная последовательность чисел, составляющая вырезанный массив в Ъ чисел из исходного массива в Ы чисел, причем с и. 1 ил.а =101 0 0 0 0 0 1 1 0 0 0 0 0 0 1.0 0 0 0 1 0 0 0 0 0 0 0 а= 011 аз =. 001 а = 100 0 0 Выходные сигналыэлементов ИЛИ 3 0 0 Входные сигналышифратора 6 0 О 1 121Изобретение относится к автоматике и вычислительной технике и можетбыть использовано,при реализациисистем обработки данных и автоматизированных систем управления,Цель изобретения - сокращениеаппаратурных затрат.На чертеже приведена Функциональная схема устройства,Устройство содержит входныерегистры 1, дешифраторы 2, группуэлементов ИЛИ 3, группу элементовНЕ 4, группу элементов И 5, шифратор6, группы элементов И 7, регистры8 результата, выходы 9 регистров 8,коммутатор 10, информационные выходы 11 устройства, блок управления12, выходы 13 блока управления 12,группу элементов НЕ 14, узлы сравнения 15, в которые входят группыэлементов И 16, группа элементовИЛИ 17 и элемент И 18, элементИЛИ 19, группу входных элементовИ 20, группу входных элементовИЛИ 21, информационные входы 22устройства, вход "Начало операции"23, вход "Начальное гашение" 24,выход конца сортировки 25, шину"Размер массива" 26,Блок управления 12 содержит элемент ИЛИ 27, триггер управления 28,элемент И 29, генератор импульсов30, счетчик 31, дешифратор 32, группу элементов И 33. Коммутатор 10содержит регистр 34, дешифратор 35и группу элементов И 36.Рассмотрим принципы построенияи работу устройства.На вход устройства может бытьподан массив с различных по значе 8381нию чисел, причем ,и, С помощьюустройства необходимо расставитьчисел в порядке их возрастания,причем Р с и, Задача сводится к определению минимального числа, записи его в первый регистр результатаи гашению того входного регистра, вкотором оно находится, для исключения уже выбранного числа в очеред ном цикле анализа. Затем процессповторяется, пока не выполнится Ъциклов. По завершениициклов врегистрах результата будет находиться упорядоченная последовательность 15 чисел, составляющая вырезанный массив в Р чисел из исходного массивав Ы чисел, причем М ( и. 1 управление-формирование упорядо 20 ченного массива производится блоком управления на основе анализа требуемого размера массива.Коммутатор обеспечивает выдачуупорядоченного массива из регистров25 результата.Выбор минимального числа в цикле работы устройства производитсяпутем анализа объединенных выходныхсигналов с одноименных выходов де 30 шифратора, преобразующих двоичныекоды чисел в распределительные,посредством приоритетной схемы, формирующей входные сигналы для шифратора.Пусть имеется массив из четырехчисел а 1 = 101, а = 011, аз = 001,а = 100,Определение минимального числав первом цикле работы устройства40 поясняется табл. 1.Таблица 1 Номера выходов дешифраторов 2, , 23 1Из анализа табл. 1 видно, что номера возбуженных выходов дешифраторов 2, а также соответствующих элементов ИЛИ 3 однозначно отражают значения чисел, содержащихся во входных регистрах 1, С помощью элементов НЕ 4 и элементов И 5, подключенных к выходам элементов ИЛИ 3, формируется распределительный входной код для шифратора 6. Так как возбужденным является первый вход шифратора, то на его выходах формируется двоичный код Ъ = 001, т,е. наименьшее число из исходного массива.В дальнейшем это число через элементы И 7 передается в регистр 8 и одновременно в узлах сравнения 15 производится формирование единичного сигнала для гашения входного третьего регистра, так Ъ = аз.В каждом узле сравнения производится поразрядное сравнение прямых и обратных кодов выходных сигналов шифратора 6 и регистров 1.Работа узла сравнения для одного разряда поясняется табл, 2.Та блица 2х,000Примечание. Хи Х значения одноименных разрядов двух чисел, У - значение сигнала сравнения, т.е. равенства разряда.Из табл. 2 следует, что У =ХХЧХХ.В соответствии с табл. 2 выполнен узел сравнения 15 для каждого входного регистра 1. Единичные значения выходного сигнала узла сравнения используются для гашения соответствующего регистра 1.В узле сравнения 15 в первой группе элементов И 16 производится сравнение прямых кодов 1 с разрядов регистров 1 и шифратора 6, а во второй группе элементов И 16 - обратных кодов. Для каждого из К разрядов используется элемент ИЛИ 17, объединяющий выходные сигналы эле" ментов И 16 соответствующих разря О152025 3035 40 45 50 55 ное значение сигнала формируетсяв третьем узле сравнения 15 , и в очередном цикле производится анализ следующих значений чисел: а - 101; а = 011; аз = 000; ац = 100.Устройство работает следующим образом.Исходное состояние устройства характеризуется тем, что сигналом, поступаюЩим на вход "Начальное гашение" 24, устанавливаются в нулевые состояния регистры 8 результата, через элементы ИЛИ 21 - входные регистры 1 и через элемент ИЛИ 27 - триггер управления 28 в блоке управления 12. После этого по входам 22 во входные регистры принимается исходный массив чисел, а по шинам "Размер массива" 26 - значение требуемого размера выходного массива в регистр 34 коммутатора 10 в прямом коде и в счетчик. 31 - в дополнительном коде. По окончании приемаисходных чисел сигналом, поступающим по входу "Начало операции" 23,триггер управления 28 блока управления 12 устанавливается в единичноесостояние.Дальнейшую работу устройства рассмотрим при следующих условиях: необ.ходимо получить возрастающую последовательность из п чисел, наиболь-.шее число находится в регистре 1,наименьшее - в регистре 111.В дешифраторе 35 возбужден и-йвыход, разрешающий формирование выходных сигналов на шинах 1111 устройства.В дешифраторе 32 блока управления 12 возбужден первый выход, итак как триггер 28 находится в единичном состоянии, элементом И 33на выходе 13 формируется единичныйсигнал, разрешающий работу элемен-,тов И 7,Одновременно по единичному сигна"лу с выхода элемента ИЛИ 31, наи-й вход которого поступает единичный сигнал с первого выхода дешифратора 2, через элемент НЕ 4 зак 218381 4дов регистраи шифратора 6, Посредством элемента И 18 формируется единичный сигнал, когда на его вхо" дах действуют единичные сигналы одновременно со, всех элементов ИЛИ 17, что означает полное совпадение двоичных кодов шифратора 6 и регистра 1.Для приведенного примера единич 12183811 О 20 рываются все элементы И 5, При этом возбужденным будет только первый вход шиФратора 6. двоичный код числа с выхода шифратора 6 подается через открытые элементы Ив регистр 8 результата. Одновременно произ-т водится сравнение кодов шифратора 6 и всех регистров 1 в узлах сравнения 15, При этом единичное значение сигнала Формируется элементом И 18 узла 15 которым регистр 1, через открытый элемент И 20 сигналом элемецта ИЛИ 19 устанавливается в нулевое состояние, чем исключается выбр нное уже число из анализа в очередном цикле.Очередной цикл начинается по импу;гьсу от генератора 30, который переводит счетчик 31 в очередное состояние, по которому возбуждается выход 13 блока управления 12. Габота по анализу, передаче числа в регистр 8результата и гашению входного регистра, где находится 25 очередное наименьшее число, производится аналогично описанной.В последнем и-и цикле большее число окажется в регистре 8 результата. По очередному импульсу от30 генератора 30 в блоке управления 12 триггер 28 устанавливается в цупевае состояние сигналом переполнения счетчика 31, поступающим ца инверсный вход триггера через элемент35 ВП 1 2, По единичному сигналу с инверсного выхода триггера 28 в коммутаторе 10 производится передача содсржимого регистров 8 в шины 11 устройства, представляющего собой возрастающую последовательность из и исходных чисел.Сигнал с инверсного выхода триггера 28, поступающий по шине 25, например, в ЭВИ, используется в ка 45 честве сигнала, разрешающего обработку сформированной последовательности чисел.При необходимости получения убывающей последовательности из чисел50 на входные шины 22 устройства числа подаются в обратном коде.Если необходимо получить последовательность чисел, вырезанную из и исходных чисел, по шине 26 подается двоичный код требуемого размера, определяющий число циклов работы устройства, При этом работа устройства не отличается от описанной за исключением того, что в дешифраторе 35 коммутатора 10 будет возбужден выход, номер которого соответствует размеру требуемого массива и открывающий соответствующее число элементов И 36.Формула и з о б р е т е н и яУстройство для выбора упорядоченной последовательйости данных, содержащее и входных регистров, и дешифраторов, и групп элементов И, и регистров результата, группы входных элементов И и ИЛИ, группу элементов ИЛИ, элемент ИЛИ, группу элементов И, две группы элементов НЕ, коммутатор, включающий и групп элементов И, дешифратор и регистр, блок управления, содержащий триггер управления, счетчик, дешифратор, элементы И, ИЛИ, группу из и элементов И и генератор импульсов, причем прямые выходы разрядов каждого .-го входного регистра, информацион - ные входы которого являются информационными входами устройства, где г = 1, 2, , и, и - количество сортируемых чисел, соединены с соответствующими входами г-го дешифратора, вход "Начальное гашение" устройства соединен с входами установки в цОн всех регистров результата, первыми входами входных элементов ИЛИ группы и первым входом элемента ИЛИ,блока управления, в котором выход элемента ИЛИ подключен к входу установки в "0" триггера управления, вход установки в "1" которого соединен с входом "Начало операции" устройства, а прямой выход соединен с первыми входами элементов И группы и элемента И, второй вход которого подключен к выходу генератора импульсов, а выход соединен со счетным входом счетчика, выход-,переполнения которого подключен к второму входу элемента И, а выходы разрядов соединены с соответствующими входами дешифратора, выходы которого подключены к вторым входам элементов И группы, выход 1.-го элемента И группы блока управления, являющийся 1-м выходом блока управления, соединен с управляющими входами элементов И х-й группы и -и входом элемента ИЛИ, выход которого подключен к первымвходам входных элементов И группы,выходы которых соединены с вторымивходами соответствующих входныхэлементов ИЛИ группы, выходы которых подключены к входам установкив "0" соответствующих входных регистров, шина "Размер массива" устройстваподключена к информационным входамсчетчика блока управления и входамрегистра коммутатора, в которомвыходы разрядов регистра соединеныс соответствующими входами дешифратора, д-й выход которого подключен кпервым входам первой, второй,ь-й групп элементов И, вторые входыэлементов И -й группы подключены квыходам разрядов д-го регистра результата, а выходы являются информационными выходами устройства, инверсный выход триггера управления блокауправления является выходом концасортировки устройства и подключен куправляющим входам элементов И всехгрупп коммутатора, выход 7-го элемента НЕ первой группы подключен к Г-мувходу ( Р + 1), , (п - 1) -го элемента. И группы, где й = 1, 2,(ш - 1), ш-разрядность сортируемыхчисел, о т л и ч а ю щ е е с ятем, что, с целью сокращения аппаратурных затрат, в него введены шифратор и и узлов сравнения, каждый изкоторых содержит две группы элементов И, группч элементов ИЛИ и эле 1 мент и, причем 1-ый выход -годешифратора, где 1 = 1, 2.ш,соединен с д-м входом 1-го элементаИЛИ группы, выход Г-го элемента ИЛИгруппы соединен с входом Г-го элемента НЕ первой группы, выход первогоэлемента ИЛИ группы соединен с первым входом шифратора, а выход ( 7 + 10 + 1) элемента ИЛИ группы - с ( ++ 1)-м входом Г-го элемента И группы, выход которого соединен с ( Г ++ 1)-м входом шифратора, 1-й выходкоторого подключенк информационным 1 входам 1-х элементов И всех групп,входу )-го элемента НЕ второй группы и к первым входам 1-х элементовИ первых групп всех узлов сравнения,вторые входы -х элементов И первой 20 группы 1-го узла сравнения соединены с прямыми выходами )-х разрядов-го входного регистра, инверсныевыходы которых подключены к первымвходам соответствующих элементов И 25 второй группы -го узла сравнения,вторые входы )-х элементов И вторыхгрупп всех узлов сравнения подключенык выходам 1-го элемента НЕ второйгруппы, в х-м узле сравнения выходы