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

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

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

Устройство содержит информационные входы 1, входные регистры 2, дешифраторы 3, элементы ИЛИ 4, узлы 5 преобразования кодов, выполненные на элементах И 6, НЕ 7„ И 8, шифраторы 9, выходные регистры 10, выходы 11, триггер 12 режима, регистр заданного числа 13, дополнительный дешифратор 14, группу элементов ИЛИ 15$ группу элементов ИЛИ 16, группу элементов И 17, дополнительный шифратор 18, регистр размер массива 195 выходы размера массива 20 устройства, входы 21 заданного числа устройства, входы 22 и 23 задания режима.

Рассмотрим принципы построения и работу устройства.

Упорядочивание исходного массива устройством может выполняться в двух режимах: упорядочивание всего исходного массива; упорядочивание чисел, меньших наперед заданного.

Выбор режима работы обеспечивается триггером режима 12, управляемого по входам 22 и 23. Установка первого режима производится по сигналу с входа 23, переключающему триггер 12 и регистр 13 заданного числа в нулевое состояние.

Для формирования упорядоченного массива во втором режиме в регистр 13 заданного числа поступает - ранич- ное значение массива, а по входу 22 триггер режима устанавливается в состояние 1,

В обоих режимах упорядочение исходного массива выполняется одинаково.

Пусть необходимо получить упорядоченный массив из 4-х чисел.

Исходное состояние устройства характеризуется тем, что выходные регистры 10 и регистр 19 установлены в состояние О, во входные регистры 2 принят по входам 1 массив исходных чисел, и по входу 23 триггер режима и регистр заданного числа установлен в состояние О. При этом выходные

0

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

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

В соответствии с табл.1 единичные сигналы появляются на пятом выходе дешифратора 31t первом - дешифратора 3, на четвертом - дешифратора 33 5 и на втором - дешифратора 3..

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

Посредством элементов ИЛИ 4 проводится объединение одноименных выходов дешифраторов. Как следует из табл.1, позиционный код на выходах элементов ИЛИ 4 имеет вид 11011. В соответствии с этим кодом в выходных регистрах 10 необходимо разметить числа в следующем порядке возрастания значения Ь 1, Ь2 2,

0

5

0

5

0

Ъ4 4,

5

5

Ъ5 5, Это обеспечивается

соответствующими шифраторами 9, на входы которых необходимо подать следующие позиционные коды:

10000

01000

00010

00001

-на входы шифратора 9

-на входы шифратора 9г

-на входы шифратора 9}

0 „„,

- на входы шифратора 94 Преобразование исходного позиционного кода, полученного элементами ИЛИ 4, производится соответствующими узлами 5 преобразования кодов. В узле 54 на его входы подается позиционный код 11011. При этом единичный сигнал на его входе через элемент НЕ 7( закрывает все элементы И 8, поэтому на выходе узла 5,, формируется код 10000.

Формирование входного кода для второго узла 5й должно выполняться с учетом работы предьцгядего узла 5,, т.е. необходимо при анализе исключить выделенное значение числа. Эту функцию выполняют элементы И 6, на инверсные входы которых поступают выходные сигналы узла Ьх, а на прямые сигналы с выходов элементов ИЛИ 4, т.ес

выходы узла

5, 10000 обратный код 01111 выходы элементов ИЛИ 411011

выходы элементов И 6 01011 В узле 5а из выходных сигналов элементов И, 01011 за счет блокировки элементов И 8 нулевым сигналом с выхода элемента НЕ 7{ формируется выходной код 01000, поступающий на шифратор 9ji.

Построение узлов преобразования кодов 5д,...,5 и выполнено с учетом минимизации оборудования, что поясняется табл.2, когда массив исходных чисел- размещается в входных регистрах, причем значения чисел лежат в пределах 1-5 и в этом диапазоне могут принимать одинаковые значения . Из табл.2 видно, что при формировании позиционного кода для очередного узла преобразования, например, для узла 5 нет необходимости в формировании первой позиции кода, для узла 5а - первых двух и так далее, так как единичные сигналы этих позиций уже использованы для форми - рования знпчений упорядоченных . чисел Такое положение справедливо до формирования входного кода для узла Еh+1 . При этом число входов шифраторов 9 равно m и при m n входные сигналы для 1-го шифратора, где 1 2, 3, ..., п, подаваемые на входы 1, 2,.. (1-1), равны нулю. Поэтому, хотя эти поразрядные узлы преобразования кодов выполняют одинаковые функции дли любого из 1-го регистров, когда i l,2,...,n, имеется возможность минимизации оборудования с учетом размещения узла.

Во второй режим устройство переводится при наличии сигналов двоичного кода заданного числа на входах 21 устройства и управляющего сигнала на входе 22, которым устанавливается в 1 триггер режима. По единичному сигналу с выхода триггера, поступающему на вход синхронизации регистра заданного числа, двоичный код заданного числа принимается в этот регистр. При этом с помощью дешифратора 14 и элементов ИЛИ 15 формируются управляющие сигналы для узлов преоб15

372 . 6 разования кодов 5, блокирующие передачи чисел в выходные регистры 10, болыпих или равных заданному.

Формирование этих управляющих сигналов для приведенных выше условий отражено в табл.3.

Пусть для приведенного примера необходимо сформировать упорядочен- JQ ный массив чисел, меньших числа, равного 4.

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

Двоичный код 100 по входам 21 5 принимается в регистр 13 после установки триггера режима 12 по входу

22 в состояние 1. При этом на четвертом выходе дешифратора 14 формируется единичный сигнал. В соответствии с табл.3 с помощью дешифратора 14 и элементов ИЛИ 15 формируется следующий позиционный код управляющих сигналов ООП. Нулевыми сигналами с второго выхода дешифра- тора 14 открыты по инверсным входам элемент И 8 в первом узле преобразования кодов 5 и элемент И 64 во втором узле 5. Нулевым сигналом с выхода элемента ИЛИ 15t открыты в первом узле 5 - элемент И 8, во втором - элемент И 6„, в третьем - элемент И 6. Единичными сигналами с выходов элементов ИЛИ 15, ИЛИ 159 закрыты по инверсным входам остальные элементы И 8 в первом узле 5 и элементы И 6 в остальных узлах 5.

Выбор и расстановка чисел выполняется аналогично рассмотренному выше. При этом выходной массив в регистрах 10 имеет вид Ь, 1, Ь4 2,

Ь, О, Ъ

0.

В дальнейшем с помощью элементов ИЛИ 16 формируется следующий код 1100.

Единичным сигналом с выхода элемента ИЛИ 162 закрыт по соответствующему инверсному входу элемент И 17. При этом на входах шифратора 18 устанавливается позиционный код 0100, по которому, на выходах 20 устройства формируется двоичный код числа 2, означающий, что упорядоченный массив чисел, меньших заданного, размещен

в первых двух выходных регистрах 10.

7.

15363728

Т а б л и ц а 1

1536372

10 ТаблицаЗ

Цель изобретения - расширение области применения за счет формирования упорядоченного массива чисел, меньших наперед заданного. Сущность: в устройство введены регистр заданного числа, дополнительный дешифратор, первая группа из ( -2) элементов ИЛИ, вторая группа из элементов ( -1) элементов И, дополнительный шифратор, регистр размера массива и триггер режима.

010 ОН 100 101

1 1

о о

1 о