Устройство для сортировки чисел

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано в устройствах дискретной автоматики для решения задач квазиоптимального регулирования, в частности в системах обработки результатов испытаний технических объектов. Цель изобретения - повышение быстродействия. Устройство содержит регистры 1, элементы И 2 опроса разрядов , элементы И 3 анализа разрядов, элементы И-НЕ 4, элементы ИЛИ 5 разрядов, многовходовые элементы ИЛИ-НЕ 6, выходные элементы И 7, элементы И 8 обнуления, регистр результата 11. Устройство определяет минимальное отличное от нуля число из чисел, записанных в регистрах, и выводит его на регистр результата, исключает его из анализа путем обнуления регистра, в котором оно записано, потом определяет следуюш,ее по величине число и т.д. На выходе устройства формируется отсортированная в порядке возрастания последовательность чисел . 1 ил. З (Л со ю ел 05 & 7aivr i

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

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

РЕСПУБЛИК

„„SU „„1325461 (so 4 G 06 F 7/06

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЙ ":;,/

К А BTOPCHOMV СВИДЕТЕЛЬСТВУ - "" С,.„., /

:1., „ (21) 4000742/24-24 (22) 30.12.85 (46) 23.07.87. Бюл. № 27 (71) Таганрогский радиотехнический институт им. В. Д. Калмыкова (72) М. Д. Скубилин и В. А. Грищенко (53) 681.325 (088.8) (56) Авторское свидетельство СССР № 525083, кл. G 06 F 7/06, 1975.

Авторское свидетельство СССР № 922725, кл. G 06 F 7/06, 1977. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ

ЧИСЕЛ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в устройствах дискретной автоматики для решения задач квазиоптимального регулирования, в частности в системах обработки результатов испытаний технических объектов. Цель изобретения — повышение быстродействия. Устройство содержит регистры 1, элементы И 2 опроса разрядов, элементы И 3 анализа разрядов, элементы И вЂ” НЕ 4, элементы ИЛИ 5 разрядов, многовходовые элементы ИЛИ вЂ” НЕ 6, выходные элементы И 7, элементы И 8 обнуления, регистр результата 11. Устройство определяет минимальное отличное от нуля число из чисел, записанных в регистрах, и выводит его на регистр результата, исключает его из анализа путем обнуления регистра, в котором оно записано, потом определяет следующее по величине число и т.д. На выходе устройства формируется отсортированная в порядке возрастания последовательность чисел. 1 ил.

1325461

Элемент

И вЂ” НЕ 4;

И2;;

И 3;;

ИЛИ 5;;

И 8;

ИЛИ вЂ” HE

Формула изобретения

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

Цель изобретения — повышение быстродействия устройства за счет исключения из процесса сортировки нулевых чисел.

На чертеже представлена схема устройства.

Устройство содержит и регистров 1, элементы И 2 опроса разрядов, элементы И 3 анализа разрядов, элементы И вЂ” HE 4, элементы ИЛИ 5 разрядов, многовходовые элементы ИЛИ вЂ  6, выходные элементы И 7, элементы И 8 обнуления, элемент 9 задержки, многовходовый элемент ИЛИ 10, регистр 11 результата.

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

В исходном состоянии регистры обнуления (цепи первоначальной установки устройства в исходное состояние не показаны), так как эта операция может осуществляться через пусковой вход, при этом на нулевых выходах m разрядов всех регистров установлены высокие, единичные потенциалы, а»а выходах всех m разрядов регистра 11 — низкие. Значения параметров в двоичном коде поразрядно записываются через единичные входы в регистры. При отсутствии записи в регистре на инверсных выходах его разрядов ij (где i= 1,...,и, j= 1,...,m) — высокие потенциалы, а на выходе элемента И вЂ” НЕ 4 — низкий потенциал, тогда на выходах элементов И 2;;, элементов

ИЛИ 5ц — также низкие потенциалы, а на выходах элементов ИЛИ вЂ” НЕ 6> — высо35 кие. И хотя на вторых входах элементов

И 3„— высокие потенциалы, но так как на их первых входах — низкие потенциалы, то и на выходах элементов И 3;; — низкие потенциалы. Низкие потенциалы сохраня- 40 ются и на выходах элементов И 8;, на выходе элемента ИЛИ 10, на выходе элемента

9 задержки и на выходах элементов 7;.

При наличии записи в регистре хотя бы в одном разряде, на выходе элемента И вЂ” НЕ

4; устанавливается высокий потенциал, 45 благодаря чему элементы И 2; всех m разрядов по третьим входам оказываются под высокими потенциалами, так как при содержимом регистров 1; a;,з, l, а,з,2,...,а;,з, ° выходе элемента И вЂ” НЕ 4; устанавливается потенциал а;,4= а;,з,! Л a;,8,2/l, ....Ла, з,,„= О, а если хотЯ бы одно значейие alaj = а!з; то а...=а !,,Л ... Ла;, /\...hà,, =1, Следовательно, на выходе элемента И 2;,„, будет потенциал, равный а;,5, а з,,„Ла.4=

=О при а;,8, = 0 и/или а;,4= О и а;,2

=a„l„,Лa;4=1 при а;,! 1 и a;:!=1.

Тогда потенциалы на выходе элементов определяются из следующих соотношений:

3,4 ауЛ34!,2Л""Ла,l,lË-"Л

Л 3<,l ni а; 2;= а,, !; Л а;,-,q !) Л а, „ а,з,!= а,s,(j- !)Л а,2,; /\a;,4

a;> l= а!,2, Л а,з,; а,8= а;8 Л al!

6; аб,j — 3 2,! I а!,2 j \/-- ° /

,l а..., \/ ... Q a

ИЛИ 10 а 0 = 3 8 / 3 2,8 \/ ° \/ 3 !, 8 / ° / а „8 / 3 „Где а„— потенциал на пусковом входе устройства.

Задержки (9) С запаздыванием по времени

Н3 тзаа на и 7! а„;=а„,A а,.

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

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

Импульсом с пускового входа устройства через элемент ИЛИ 10 обнуляется регистр 11, с задержкой по времени íà l>+z с выхода элемента 9 задержки содержимое выходов элементов ИЛИ вЂ” НЕ 6 через элементы И 7 фиксируется в регистре 11, через элемент И 8 регистр 1, содержащий минимальное, но отличающееся от нуля значение параметра обнуляется, после чего процесс через элемент ИЛИ 10 и другие элементы повторяется. Причем каждый раз в регистре 1 фиксируется следую!цее, в порядке возрастания абсолютных значений, значение параметра.

Процесс прекращается после сортировки всех значений, 3 так как на каждом этапе регистры обнуляются, то устройство вновь готово к работе.

Устройство для сортировки чисел, содержащее прегистров,,где и — количество сортируемых чисел, п групп по (т — 1) элементов И опроса разрядов, где m — разрядность чисел, и — групп по (m — 1) элементов И анализа разрядов, п групп по ти элементов ИЛИ разрядов, m многовходовых элементов

ИЛИ вЂ” НЕ, m выходных элементов И, и элементов И обнуления, регистр результата, элемент задержки, причем выход элемента

ИЛИ i-ro разряда j-й группы, где i = 1,2...,n. ! == 1,2,...,(m — 1), соединен с первыми входами элементов И опроса и анализа (i+1)-го разряда 1 -й группы, выходы которых соединены с входами элемента ИЛИ (i+1) -го раз132546

3 ряда /-и группы, вторые входы элементов И опроса и анализа разрядов j-й группы объединены, выход элемента ИЛИ m-го разряда

/-й группы соединен с первым входом /-го элемента И обнуления, выход которого соединен с входами установки в «0» регистров

j-й группы, первые входы элементов ИЛИ первых разрядов всвх групп соединены с входами первого элемента ИЛИ вЂ” HE, выход которого соединен с вторыми входами элементов И первых разрядов, выходы элементов lp

И спроса всех (i+1)-х разрядов соединены с входами (i+1)-го элемента ИЛИ вЂ” НЕ, выход которого соединен с третьими входами элементов И анализа (i+1)-го разряда всех групп, выходы выходных элементов И соединены соответствующими информационными входами регистра результата, вторые входы всех элементов И обнуления и первые входы выходных элементов И соединены с выходом элемента задержки, отличающееся тем, что, с.целью повышения быстродействия, 1

4 оно содержит и элементов И опроса первых разрядов, и элементов И вЂ” НЕ и многовходовый элемент ИЛИ, причем инверсный выход первого разряда /-го регистра соединен с первым входом /-го элемента И первого разряда, выход которого соединен с /-м входом первого элемента ИЛИ вЂ” НЕ, инверсный выход (i+1)-го разряда /-ro регистра соединен с третьим входом элемента И опроса (i+I)-го разряда /-го регистра, инверсные выходы всех разрядов J-го регистра соединены с входами /-ro элемента И вЂ” НЕ, выход которого соединен с вторыми входами всех элементов И опроса и анализа разрядов -й группы, выходы элементов И обнуления соединены с и входами многовходового элемента ИЛИ, (и+ 1)-й вход которого подключен к входу запуска устройства, а выход соединен с входом элемента задержки и входом установки в «О» регистра результата, выходы элементов ИЛИ вЂ” НЕ соединены с вторыми входами соответствующих выходных элементов И.

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

Редактор В. Петра ш Техред И. Верее Корректор Л. Пилипенко

Заказ 3110/44 Тираж 672 Подписное

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

113035, Москва, Ж вЂ” 35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4