Устройство для упорядочивания @ чисел
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСНИХ
РЕСПУБЛИН
А (19) (11) З(51) 06 Г 7 06
ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ
ОПИСАНИЕ ИЗОБРЕТЕНИЯ;
К ABT0PCHGMY СВИДЕТЕЛЬСТВУ (21 ) 3499046/18-24 (22) 12,10.82 (46) 2 3.12.83. Бюл. Р 47 (72) В.Г.Попов и П.П.Бабенко ,(53) 681.325(088.8) (56) 1. Авторское свидетельство СССР
Р 932487, кл. G 06 F 7/06, 1980.
2. Авторское свидетельство СССР
М 903864, кл. G Об F 7/06, 1980 (прототип). (54)(57) 1. УСТРОИСТВО ДЛЯ УПОРЯДОЧИВАНИЯ П ЧИСЕЛ, содержащее входные регистры, дешифраторы, поразрядные узлы анализа, элементы ИЛИ, входной регистр, причем выходы каждого
< --го входного регистра, входы которого являются информационными входами устройства, соединены с входами t -го дешифратора, где (= 1,2,... ...,И,ка>алый j -и выход 4 -годешифратора, где (=1,2,...,m, N — число разрядов операндов, соединен с -ым входом ) -ro поразрядного узла анализа, каждый -й выход 1 -го поразрядного узла анализа подключен к ) -му входу < --ro элемента ИЛИ, каждый j-é поразрядный узел анализа содержит элементы НЕ и И, выходы которых соединены с выходами поразрядного узла анализа, а один из входов через элемент НŠ— с входами поразрядного узла анализа, о т л ич а ю щ е е с я тем, что, с целью повышения быстродействия устройства эа счет одновременного сравнения исходных чисел, в него введены узлы преобразования кодов, коммутаторы и (Р- 1) выходных регистров, причем выход логической суммы j --го поразрядного узла анализа подключен к
k-му входу j --го узла преобразования кодов, где k = — (j — 1), выход переносов каждого i --ro узла преобразования кодов соединен с первым уп равляющим входом (+ 1) -ro узла преобразования кодов, каждый Р -й выход i -ro узла преобразования кодов соединен с Р --ым управляющим входом -ro коммутатора, где p = 1, 2,.; ° ,(е- (i — 1), а (-й выход узла преобразования кодов — с и -ым управляющим входом (+ 1) -го узла преобразования кодов, где = 2, 3„„ ...,(v — q) выходы j -го входного регистра подключены к информационным входам q -ых групп коммутаторов, выходы каждого (-го элемента ИЛИ соединены с -ми входами управления передачей коммутаторов, выходы < -ro коммутатора подключены к входам q -го выходного регистра, выходы которого являются информационными выходгаи 2 устройства., в каждый ) -й поразрядный узел анализа введен элемент
ИЛИ, причем каждый (-й вход поразряд ного узла анализа, где (= 1, 2,..., С,,(и- 1), через 3 --й элемент НЕ соединен с -ми входами 0,3 + 1,. (и- ф
1) -го элементов И и 3 -ым входом элемента ИЛИ, выход которого является выходом логической суммы порязрядного узла анализа, и -й вход узла подключен к и -му входу (n -1) -ro элемента И, первый вход поразрядного узла анализа соединен с его . первым выходом, выход каждого L -го элемента И является ((:+ 1) -ым выходом поразрядного узла анализа.
2. Устройство по п.1, о т л и ч а ю щ е е с я тем, что в нем первый узел преобразования кодов содержит (m - 1) элементов НЕ и (m — 1) элементов И, причем каждый
Р-й вход узла преобразования кодов, где p - =1, 2, ..., (я — 1), через р-й элемент ЙЕ соединен с Г -ми входами 1, р + 1...,, (vn- 1) -го элементов И, выходы которых соединены с (и + 1)-ьм выходами узла преоб-разования кодов, первый вход подклю( чен к первому выходу и выходу пере10б2687 входу -ro элемента И, вход управления узла соединен с вторыми входами элементов И, каждый 1 -и вход узла .подключен через -й элемент НЕ к (i +2 ) -му входу (< +1), (j +2 )... л -го элементов И и к q --му входу многовходового элемента И, выход которого подключен к выходу переносов узла, выход каждого < -ro элемента
И соединен с < -ым выходом узла,щ -й поразрядный узел анализа состоит из элементов И и (n — 1) -ro элемен- тов НЕ, причем каждый р -й вход узла, где p= 1, 2, ..., (n — 1), соединен с первым входом Р --го элемента И, вход переносов узла подклю-, чен к вторым входам элементов И, каждый р --й вход узла через р -й элемент НЕ соединен с (P + 2) -м входом (p+ 1), (р + 2), ..., и го элемен тов И, Ф -й вход узла подключен к (m+ 2) -му входу и -го элемента И, выход каждого „ -го элемента И соединен с i -ым выходом узла (2) .
Однако определение наименьшего числа производится за один цикл работы устройства. Поэтому для упо- . рядочивания массива из П чисел пот ребуется и раз выполнить Обращение к устройству, причем каждый раз необходимо исключать из анализа выбранное число в предыдущем цикле.
Таким образом, известное устройство требует организации П циклов обращения и, следовательно, его неносов узла преобразования кодов, а (v + 1) -й вход узла преобразования кодов соединен дополниТельно c (t +
+ 1) -ым входом г -го элемента И.
3. Устройство по и. 1, о т л и ч а ю щ е е с я тем, что в нем каждый {6+ 1) -й узел преобразования кодов содержит {п1- 3 — 11 элементов
НЕ, (а -e) элементов И и (rn — 0 - 1) элементов ИЛИ, причем Ь -й вход (8 + 1) -го узла преобразования кодов, где 5 = 1, 2, ...,{yn -5), подключен к (+ 1) -му входу 5 --го элемента И, первый .вход управления узла преобразования. кодов соединен с первыми входами первого элемента
И и всех элементов ИЛИ, t -- и .управляющий вход узла, где (. = 2, 3, ° .. ...,Yr -(j -1)), подключен rc 4 -ым входам 5, Я + 1, ..., (щ - 0 — 1) "ro элементов ИЛИ, выход 5 -го элемента
ИЛИ соединен с (о+ 1) -ым входом (5 + 1) -го элемента И, выход первого элемента И соединен с выходом переносов узла преобразования кодов
Изобретение относится к вычислительной технике и может быть использовано при реализации систем обработки данных и автоматизированных систем управления, 5
Известно устройство для упорядочения чисел, содержащее,I входных регистров, где и — количество чисел„ элементы ИЛИ, группы элементов. И, блок памяти из Il выходных регист- 3Q ров (13 .
Наиболее близким по технической сущности к изобретению является уст ройстно для определения наименьшего из Н чисел, содержащее регистры, дешифраторы, регистр результата, поразрядные узла анализа, группы элементов И, ИЛИ, причем каждый 1-й выход каждого 1 -го дешифратора соединен c i -ым входом j -го поразряд- 2О ного узла анализа, где =- 1, 2,...
„;,р = 1, 2, ..., m, n1 — число разрядов операндов, каждый 1 -ый выход
j-го поразрядного узла анализа подключен к 1-му входу j «ro элемента 2
ИЛИ, а выход переносов каждого) -го поразрядного узла анализа, где Ц
1, 2, ..., { e — 1), соединен с входом управления (k+ 1) -го поразрядного узла анализа, каждый l< -й пораэ- 30 рядный узел, анализа состоит из и элементов И, И элементов НЕ и многовходового элемента И, причем каждый -й вход узла подключен к первому и через первый элемент НŠ— с первыми входами остальных элементов И, выход (8 + 1) -го элемента И соединен через (б + 1) -й элемент НЕ с
{ + 2) -ми входами {5 +2,5 +3 ...,(yn -f)-го элементов И.
4. Устройство по п. 1 о т л и ч а ю щ е е с я тем, что, в нем каждый -й коммутатор содержит группу элементов ИЛИ и q блоков из {m + 1
-i) групп элементов И, причем информационные входы элементов И 4 -ro блока подключены к информационным входам g --ой группы коммутатора, первые управляющие входы элементов И
t -ro блока подключены к -ым входам управления передачей, вторые управляющие входы элементов И -й группы каждого j-го блока, t р = 1, 2, ...,(щ+Т-j)),ñoåäèíåíû с р -ым управляющим входом коммутатора, выходы элементов И всех групп подключены к соответствующим входам элементов
ИЛИ группы, выходы которых соедине ны с выходами j --го коммутатора.
1062687 достатком является низкое быстродействие.
Цель изобретения — повышение быстродействия устройства для упорядочивания h чисел за счет одновременного сравнения исходных чисел.
Поставленная цель достигается тем, что, в устройство для упорядочивания п чисел, содержащее входные регистры, дешифраторы, поразрядные узлы анализа, элементы ИЛИ, выходной регистр, причем выходы каждого
j --го входного регистра, входы которого являются информационными входами устройства, соединены с входами -ro дешифратора, где = 1, 2, ...,п,каждый j -й выход ) -го дешифратора, где = 1, 2, ..., в, уп - число разрядов операндов, соединен с -ым входом ) --го поразрядного узла анализа, каждый -й выход j -го поразрядного узла анализа подключен к ) -му входу -го элемента ИЛИ, каждый -й поразрядный узел анализа содержит элементы HE .и И, выходы которых соединены с выходами поразрядного узла анализа, а один из входов через элемент HE — с входами поразрядного -узла анализа, введены узлы преобразования кодов, коммутаторы и (n — 1) выходных регистров, причем выход логической суммы ) -го поразрядного узла анализа подключен к k --му входу i --го узла преобразования кодов, где k = j - (- 1), выход переносов каждого 1 -го узла преобразования кодов соединен с первым управляющим входом (i + 1) -го узла преобразования кодов, каждый
Р-й выход i -го узла преобразования кодов соединен с р -ым управляющим входом I --го коммутатора, где р — 1, 2, ...,(a — (i — 1Ц, ач,-й выход узла преобразования кодов — с ()-ым управляющим входом (j+ 1) -го узла преобразования кодов, где
2, 3, ..., t rn -i) выходы i-го входного регистра подключены к информационным входам -ых групп коммутаторов, выходы каждого i -ro элемента ИЛИ соединены с -ми входами управления передачей коммутаторов, выхсды 1 -го коммутатора подключены к входам i --ro выходного регистра, вьходы которого являются информационными выходами устройства, в каждый 1 -й поразрядный узел анализа введен элемент ИЛИ, причем каждый (-й вход поразрядного узла анализа, где C = 1, 2, ..., (n — 1), через (-й элемент ЙЕ соединен с -ми входами 1, 1 + 1..., (11- 1) -го элементов И и P-ым входом элемента ИЛИ, выход которого является выходом логической суммы поразрядного узла анализа, и -й вход узла подключен к и-му входу (n — 1) -го элемента И, первый вхед поразрядного узла анализа соединен с его первым выходом, выход каждого 3 -го элемента И является ((+ 1) -ым выходом поразрядного узла анализа.
5 Первый узел преобразования кодов содержит (6" 1) элементов НЕ и (р— — 1) элементов И, причем каждый r --й вход узла преобразования кодов, где Р = 1, 2, ...,(т - 1), через
10 Р-й элемент НЕ соединен ct. -ми входами )., 1 + 1, ...,(v - 1) -го элементов И, выходы которых соединены с (r + 1) -ми выходами узла преобразования кодов, причем первый вход
15 подключен к первому выходу и выходу переносов узла преобразования кодов, а (r + 1) -й вход узла преобразования кодов соединен дополнительно с (r +
+ 1) -м входом г-ro элемента И.
Каждый (О+ 1) -й узел преобразования кодов содержит (rn — 3 — - 1) элементов НЕ,(ю - Р) элементов И и (%" Р— 1) элементов ИЛИ, причем б -й вход (Р + 1) -го узла преобразования кодов, где 5 = 1, 2...,(m -0) ., подключен к (S + 1) -му входу 5-го элемента И, первый вход управления узла преобразования кодов соединен с первыми входами первого элемента
И и всех элементов ИЛИ,4 -й управляющий вход узла, где 1 = 2, 3, „,,(р - (1 — 1)), подключен к -ьж входам 5,5+ 1, ..., (m — Г - 1) -го элемейтов ИЛИ, выход 5 -го элемента
ИЛИ соединен с (5+ 1) -ым входом (g + 1) -го элемента И, выход первого элемента И соединен с выходом переносов узла преобразования кодов и через первый элемент НŠ— с первыми входами остальных элементов И, 40 выход (5 + 1) -го элемента И соединен через (5+ 1) -й элемент HE с (5+2) -ми входами (5+ 2), (5+ 3), ..., (щ—
-1)-го элементов И.
Каждый -й коммутатор содержит
45 группу элементов ИЛИ и П блоков иэ (я + 1 -1) групп элементов И, причем информационные входы элементов
И 1--го блока подключены к информационным входам j --й группы коммутато50 ра, первые управляющие входы элементов И < -го блока подключены к -ым входам управления передачей, вторые управляющие входы элементов И р -й группы каждого i -ro блока, р = 1, 55 2, ...,(m + 1 -j )), соединены с р-ым управляющим входом коммутатора, выходы элементов И всех групп подключены к соответствующим входам элементов ИЛИ группы, выходы которых соединены с выходами q -ro коммутато60 ра
На фиг. 1 приведена функциональ-. ная схема устройства для четырех чисел, принимающих значения от 1 до 5; на фиг. 2 — функциональная схема по1062687 разрядного узла анализа; на фиг.3-6узлы преобразования кодов с первого по четвертый; на фиг. 7 - функцио нальная схема коммутатора.
Устройство содержит информационные входы 1(— 14, подключенные к вхоцным регистрам 2(— 24, выходные шины которых 3(— 34 подсоединены к дешифраторам 4, — 4, выходы дешифраторов 544 — 54(5(4 — 5gg 5 (-5)6 10
544 — 54>, соединенные с поразрядными узлами анализа 64 - Gg, имеющие выходы 74 — 7 логической суммы и выходные шины 8(- 844, Sj(- 8 4, 8 (— 8 4, 844 — 844 8Р4 - 8 подключенные к элементам ИЛИ 94 -- 94,, имеющие выходные шины 104 — 104, у-..ы г(реобразования кодов 114 - 11А, имеющие выходные шины 12 44 — 1244
1.:. (— 12,1,. 12 У4 — 1293, 12 4 — 12.4д и г(ьжоды переносов 13 ) — 13 4, комму l а:::оры .14 ., — 144, выходные шины ко: торь х .15 (— 154 подсоединены к выход-...»м регистрам 16 4 - 164 выходы которых соединены с выходными шинами устройства 174 - 174.
Поразрядные узлы анализа имеют
î .:., 1!! «кову:о структуру, каждый узел содержит элементы НЕ 184 — 189, элемент ИЛИ 19 и элементы И 20 ) — 209.
Узлы г.реобразования кодов имеют одинако"..У.о структуру по своему функ-, пиci! Jc..J!i ному назначению. Отличие состоит лишь в количестве входов и выходов и определяется их местом в
-. ке.:.::.. устройства. 35 (срвый узел соцержит группу эле.хов ИЕ 21 и группу элементов
22 „ Последующие узлы преобразова .:;ил .;одов дополнительно содержат группу элементов ИЛИ 23. Коммутато- 4О, ры пме(от одинаковую структуру, от=;..-:ча(о(-.уюся лишь их местом в устрой ",ве „
Коммутатор содержит четыре блока по количеству входных регистров.
i аждый блок состоит из группы элементов ii 24, число которых определяется местом коммутатора B устройст:х, и группы элементов ИЛИ 25.
".. ак, коммутатор 14< содержит в каждом блоке по пять групп элементов
ii 24, коммутатор 14д - по четыре группы, коммутатор 14 9 - по три группы, коммутатор 144 — по две группы элементов И 24.
Устройство работает следующим об .>азз см.
Упорядочивание массива из и чисел ь предлагаемом устройстве производится в порядке возврастания значений чисел таким образом, что в первом выходном регистре 164 размещается наименьшее число иэ l чисел, во вто,о: регистре 16о - наименьшее иэ (л — 1) чисел и т,д., а в 4 --ом выходным регистре — наибольшее из и чи--- 65 сел. Такая последовательность образуется при упорядочивании массива чисел, представленных в прямом коде
При необходимости упорядочивания массива из П чисел в порядке убывания значений все числа принимаются
1во входные регистры 2 4 — 2 в обратном коде. Выбор экстремального числа выполняется путем сравнения сигналов одноименных выходов дешифраторов, преобразующих двоичные коды чисел в распределительные.
Пусть имеется маСсив из четырех чисел: а4 = 5, а = 1, a> = 4, а
2. Для этих значений чисел в табл. 1 приведены распределительные коды.
Из анализа табл. 1 видно, что в первый выходной регистр 164 необходимо передать число из второго вхоцного регистра 2g по управляющему сигналу, сформированному на основе сигналов с первых выходов дешифраторов 4 4 - 44, во второй выходной регистр 16о аналогично рассмотренному выше — из четвертого входного регистра 24, в третий выходной регистр 164 — из третьего входного регистра 2, в четвертый выходной регистр 164 — из первого входного регистра 24..
Формирование обобщенных сигналов
64 — 5< являющихся логической суммой сигналов с одноименных выходов дешифраторов 4 4 — 44, производится в йоразрядных узлах 64 — б анализа.
Эти сигналы поступают на выходы
74 — 7 логических сумм 6(— б узлов анализа и используются в узлах
114 — 114 преобразования кодов для .формирования управляющих сигналов, подаваемых в коммутаторы 14 4 — 144.
Обобщенные сигналы 4< — f 4 формируются элементами ИЛИ 9 — 94 и поступают на шины 10 < — 104 . Эти сигналы используются в коммутаторах 14(14 для управления передачей содержи4 мого входных регистров 2 — 24 co4 ответствующие выходные регистры 16
164 в определенном для них порядке, Поразрядные узлы 64 — б 4- анализа имеют одинаковую структуру и для чисел. При наличии хотя бы одного единичного сигнала на входах 54(-544 (фиг. 2) на одном из выходов 8(-8 4 появляется единичный сигнал, Кроме того, единичный сигнал возникает и на выходе 74 логической суммы, так как все входные сигналы поступают на элемент ИЛИ 19. Элементы HE 184184 необходимы для получения одного лишь сигнала на выходах 84, - 8«при равных кодах исходных чисел.
Так, для указанного выше примера единичный сигнал возникает на вхо,де 5о>, поэтому элемент И 20(. открыт, так как Hà era входах присутствуют
1062687 единичные сигналы с выхода элемента
HE 18 и .с входа 5g< . Нулевой сигнал с выхода элемента НЕ 18 запирает элементы И 20 и 20 .
Таким образом, сигнал с..выхода
8, т.е. 1, указывает ьа то, что 5 наименьшее число находится в регистре 2, а сигнал 71, т е. 5<, определяет необходимость передачи этого числа в первый выходной регистр 16) . 10
Так как сигнал Bg равен единице, то второе число из четвертого входного регистра 24 (f = 1) должно быть передано во второй выходной регистр 16 . 15
Очередной сигнал 5 = О, а 54= 1.
Это означает, что очередное наименьшее число необходимо передать в третий выходной регистр 16 по сигналу
á4 из третьего входного регистра
2з (з= 1) °
Сигнал 5q = 1., что означает необходимость передачи числа в выходной регистр 16 из первого входного регистра 2 (1,= 1) .
Таким образом, двоичный код сигналов 6i — 5g, равный 11011, должен быть преобразован в код 1111. Эти функции выполняются узлами преобразования кодов 11 — 114, каждый из которых формирует управляющие сигналы для соответствующего выходного регистра, Таким образом, каждый узел
11А — 114 преобразования кодов (фиг. 3 — 6) имеет одинаковую структуру. Однако функциональная схема З5 каждого из них определяется местом узла в устройстве. Так, узел 111 формирует управляющие сигналы для передачи числа из одного из четырех входных регистров в первый выходной. 40
Поэтому он имеет пять входов по числу сигналов S -5 5 и пять выходов.
Если значение числа равно единице, то сигнал = 1, и он присутствует на входе 7, коммутатора 14 45 (фиг. 3) . Этот сигнал через элементы HE 21 закрывает элементы И 22 И 224, и поэтому единичный сигнал будет лишь на выходе 12
Если значение . наименьшего числа равно 2, то сигнал б = О, а сигнал
Sg = 1. В этом случае сигнал на выходе 12 узла 111 равен единице.
Если же значенйе наименьшего числа равно 5, то сигнал Br, = 1, а остальные сигналы б -5q равны нулю.
В этом. случае единичный сигнал будет только на выходе 12 узла 11 .
Узлы .11 - 114 преобразрвания кодов (фиг. 4 — 6) отличаются от уз- бО ла 11 тем, что в них учитывается .передача числа в предыдущие выходные- регистры. В этих узлах дополнительно имеются элементы ИЛИ 23, посредством которых учитываются преобразованные коды в предыдущих узлах преобразования. С помощью элементов
HE 21 блокируется формирование ложных единичных сигналов, чем исключается наличие на выходах узла преобразования двух и более. сигналов.
Посредством элемента 221 формируется сигнал переноса при кодах .з1 — )4. — 1111 : в. узле 112 11...„ в узле 11 — 111...
Преобразование кодов в каждом узле 11 — 114 производится в соответствии с табл. 2 состояния узлов.
В крайней левой части табл. 2 указа-, .ны возможные комбинации сигналов (> = 1,5), в остальных частях таблицы - кодовые комбинации выходных сигналов узлов 111< — 11 преобразования.
Рассмотрим работу узлов 11 — 11 преобразЬвания, когда кодовая ком4 бинация сигналов 5 (j = 1,5) равна
11111. При этих условиях сигналы на шинах 7 — 7- равны единице. По сигналу шины 7 в узле 11 (фиг. 3) блокируется через элемент HE 21 формирование сигналов на выходных шинах 12 — 12 . Таким образом, единичный сигнал будет на выходе
12 и кодовая комбинация выходных сигналов составит 10000 (табл. 2).
Сигнал переноса с выхода 13 узла 11 и нулевые сигналы на выходах 12 - 1244 поступают на второй узел 11 преобразования кодов (фиг . 4) . Так как на шинах 13„ и 7 имеются единичные сигналы, то элемент И 224 узла 11 д открыт, и еди- . ничный сигнал с выхода этого элемен- та поступает на выходную шину 12 и шину переноса 13> и через элемент
НЕ 21 закрываются элементы И 22 —
224. На выходе узла 11 образуется кодовая комбинация 1000,(табл,2).
Выходные сигналы с узла 11 поступают на третий узел 11> преобразования кодов. Так как единичные сигналы имеются на шинах 13 и 7 (фиг. 5), то элемент И 22 открыт.
Единичный сигнал с его выхода поступает на выходную шину 122 и шину
13 переноса и через элемент НЕ 21 закрываются элементы И 22 и 22 .
Таким образом, выходная комбинация сигналов составит 100 (табл, 2) .
Сигналы с выходов узла 11 поступают на четвертый узел 11 преобра4 зования кодов. Так как единичные сигналы имеются на входах 13 > и 74 (фиг. 6), то элемент И 21> открыт, Единичный сигнал с его выхода поступает на шину 12 и через элемент
НЕ 21 -закрывает элемент И 222 ° Таким образом, на выходе узла 114 формируется кодовая комбинация сигналов 10, что также соответствует табл ° 2.
106 2687
В узле 11 „(фиг..3) по единичному сигналу на шйне 7» кодовая комбинация 10000, и сигнал переноса на шине 13<. В узле 11 (фиг. 4) по единичПри других кодовых комбинациях сигналов 5» (1= 1,5) работа узлов
11 < 114 производится аналогично рассмотренной выше с участием элементов ИЛИ 23.
Выходные сигналы узлов 11» — 11 по шинам 12 )q - 12 ИЛИ 9 < — 9< по шинам 10< — 10 (сиг4 налы < — f 4) входных регистров 2<2 по шинам 3 < — ЗА ° поступают на коммутаторы 14» — 144. Коммутаторы 14 » — 144 обеспечива" ют в соответствии с .преобразованными кодами сигналов 5< — 9r, в узлах 15 11 < — 114 передачу чисел из входных регистров 2< — 24 в выходные регистры 16< — 164. Коммутаторы име ют одинаковую структуру, различие состоит в количестве оборудования, определяемое местом коммутатора в устройстве, Рассмотрим работу устройства в целом при указанных выше значениях четырех исХодных чисел ° В соответствии с табл. 1 единичные сигналы появляются на выходе 5< дешифратора 4<, на выходе 5 < дешиф ратора 4, на выходе 5,<дешифратора 4, на выходе 54 дешифратора 4 . (фиг. 1) . Таким образом, единичные сигналы появляются на следующих зходах поразрядных узлов анализа б < — б : на входе 52< узла 6»,. на входе 54 узла б, на нходе 5 4 узла 64 и на входе 5 << узла 6 . В узлах б,» - 6> .формируются сигналы (фиг. 1 и фиг. 2), поступающие в узле 6,< на шину 7 (S< = Ц и на шину 8<, .в узле б — .на шину 7 (5p 1) и на шину 8 <.„в узле 6< — на шину 40 7< (5,<= 1) и йа шину 84> ., в узле б на шину 7> (= 1) и на шину 8 . В узле 6 сигналы равны нулю. Сигналы 5», 5< 54, 5 поступают на узлы 11 1 — 114 преобразова- 45 ния. Сигналы с выходов узлов 6< -6> на элементы ИЛИ 9» — 94 поступают по следующим шинам: на элемент ИЛИ 9< по шине 8р», на элемент ИЛИ 9 по шине 8<, на элемент ИЛИ 9> — по шине 8, на элемент ИЛИ 94 - по шине 8 4. На выходах элементов ИЛИ 9» — 94 формируются сигналы соответственно поступающие на коммутаторы 14 < — 144. По кодовой комбинации сигналов о (j = 1;5), равной 11011, формируются выходные сигналы в узлах 11< 114 преобразования кодов следующим образом. ным сйгналам на шинах 13< и 7 кодовая комбинация 1000 и сигнал на шине переносов 13 ° В узле 11 (фиг.5) единичные сигналы присутствуют на шинах 13 < 74 и 7-. Так как элемент И 22< закрыт нулевым сигналом 5 на шине 7> то единичный сигнал с выхода элемента НЕ 21< открывает элементы И 22 и 22 по их первым входам. Так как единичные сигналы присутствуют на втором входе элемента И 22 (сигнал на шине 13 ) и на третьем (сигнал на шине 7А), то элемент И 22 открыт. На ныходе 22 узла 11 формируется единичный сигнал, который через элемент HE 212 закрывает элемент И 22<, Таким образом, на выходе узла 11 формируется кодовая комбинация 010. Эти сигналы и сигнал переноса по шине 139, равчый нулю, поступают в четвертый узел 114, Так как сигнал на шине 13 равен нулю (фиг. 6), то элемент И 22< закрыт, нулевой выходной сигнал которого через элемент- НЕ 21» открывает элемент И 22> по первому входу, На шине 7> имеется единичный сигнал . Так как имеется единичный сигнал на шине 12 2, то элемент И 22 2 открывается, и на выходе 11 формируется кодовая комбинация 01. Кодовые комбинации выходных сигналов узлов 11 4 — 11 4 преобразова,ния соответствуют табл. 2 (строка в табл. 2 помечена звездочкой) . Таким образом, единичные сигналы, по которым производится передача чисел в выходные регистры, присутствуют на шине 12»< коммутатора 14», на шине 12 » коммутатора 14,, на шине 12 коммутатора 14, на шине 124 коммутатора 144, на шинах 10< — 104 элементов ЙЛИ 9» — 94 . По сигналу на шине 12« и сигналу на шине 102 (фиг. 7) число передается в регистр 16» по шине 15» из регистра 2q через группу элементов И 24»» . Ho сигналу на шине 12 < сигналу на шине 10 число из регист-. ра 24 передается в регистр 16» по шине 15 через группу элементов И 244< . По сигналам на шинах 12 и 10 число из регистра 2 передается в регистр 16 по шине 15 через группу элементов И 24 . По сигналам на шинах 124> и 10 » число из регистра 2< передается в регистр 16» по шине 15, через группу элементов И 24«. Таким образом, в регистрах 16< 164 сформирована упорядоченная последовательность чисел: à < = 1, а4 2, а» = 4, а» = 5 за один цикл работы устройства. При необходимости получения убывающей упорядоченной последовательности во входные регистры следует 1062687 16 20 И 2 % 0,5 Таблица 1 » «» «» «»«»» И В%» ° 55 Р ДС 9 вых. ДС 0 а, =.5 аг= а = 4 0 а = 2 4. принимать обратные коды исходных чисел. При этом в выходных регистрах фиксируется последовательность чисел в обратных кодах. Проведем сравнительный анализ предлагаемого устройства и базового 5 объекта по быстродействию, полагая, что оба устройства выполнены на одной и той же элементной базе. В качестве базового объекта выберем устройство для упорядочивания чисел. 1О Общим принципом работы обоих устройств является сравнение чисел от момента приема их во входные регистры и до момента их записи в блок памяти, содержащий и выходных 15 регистров ° B базовом объекте время сравнения кодов чисел определяется задержкой между импульсами СИЗ и СИ +(И-2)7. 20 где — время задержки в элеменили те ИЛИ; время срабатывания триггера в реверсивном счетчике. В соответствии с (3) можно прил л нять л что с < с ил „ "нс или ) "тр """или Тогда "з= "или "8(и-2) "или ЗО Выдача выбранного числа для записи его в блок памяти производится по импульсу СИ . Время выдачи опре деляется как (21 бьд и "или "илg 35 Таким образом, общее время, затрачиваемое на упорядочение чисел, составляет т, (I,,4",„„ ПодставлЯЯ выРажениЯ 1) и (2) в 40 выражение (3), получим (М ";=Ьн,и S(A-2)сили ".илиjA=(13)п и.и В предлагаемом устройстве общее время цикла работы составляет Т2 = 4 1„И 41 Пр и-ли где 4g — время работы дешифратора; время работы поразрядного узла анализа; время работы узлов преобразования кодов; время работы коммутатора. Примем, что дешифраторы выполнены на элементах И, тогда n n g = "и "или Время t>ö (фиг. 2) для чисел составляет л РН НЕ И или Время 1 (фиг. 3-6), 4 „(фиг. 7) Исходя из полученных соотношений, время работы предлагаемого устройства составляет 3 л |) Vlhlh ИЛИ Или " "ИЛИ "илИ 4 "или= .""Или ""или Выигрыш в быстродействии определяется по соотношению T H -13)o i или Sn-13 Ф-— " г п или 8" и.и. |2, 8 В табл. 2 приведены значения и при различных величинах П Из анализа таблицы видно, что применение предлагаемого устройства по сравнению с базовым объектом обеспечивает выигрыш в быстродействии при упорядочивании массива чисел, когда h > 2 ° 1062687 Таблица 2 Узел 11 Узел 119 Узел 11 Узел 114 МИ пп (1 С 1 1 1 2 (3 4 1 2 3 4 5 1 2 3 1 2 О О О О 0 О О 0 0 О 1 О О О О 1 О О О О О О 0 О 1 О О О О О О . О 0.0 1 О О О О О 1 О О О О О О О О О О О О О О О О 1 О О О О 1 О О О 1 О О О О О О 0 О О О О 0 8 О О О 1 О 0 О О О О 1 О О О О О 1 О О О О О О О 1 О О О О 0 О О О 1 О О О О О 1 О О О 1 О 0 О 1 О О О 0 О О 1 О 0 О 1 О О О О 0 О О О О 1 1 О О О О О О О О 1 О О О О 1 О О О О О 1 О О О 1 О О О О О 6 О 1 О О О О 1 0 О 1 1 О О О О 0 О О О О О 1 О 1 1 О 22 О 1 1 О 1 23 1 1 1 О 1 24 О О О 11 О О О О 2510011 О 10 11 27 1 1 О 1 1 2800111 О 0 О О 1 О О 1 О О 1 О О О О 1 О О О О 1 О О 1 О О 1 О О О О 1 О О О 1 О О 29 1 О 1 1 1 1 О О О О 0 1 О О О 1 О О 1 30 0.1.1 1 1 11111 О 1 О 1 О О О 1 О О 1 0 О О О 1 О 1 О с ° ю gita 1 1 О О О О 2 О 1 О О О 4 О О 1 О О 711100 9.10010 10 О 1 О 1 0 12 О О 11 О 13 1 0 1 1 О 15 1 "..1 1 0> 16 О 00 О 1 1710001 1801001 1911001 20 О О 1 О 1 21 10101 1 О О О О О О О О О 1000 0000 О 1 О О О О 1 О О О О О 1 О О О О О 1 О О О О О О 1 О 1 О О О О 1 О О О О О 1 О О О О 1 О О 1 О О О О 1 О О 1 O O О 0Ä 0 О 1 О О О О 1 О О О. О О О О 1 О О 1 О О О О О 1 1 О О О О О О 1 О О 1 О 0 О О О 1 О О 1 О О О, 0 1 О О О 1 0 1 О О О О 0 О О О О О О О О 1 О О О О О 1 1062687 1062687 1062687 1062687 ВНИИПИ Закаэ 10218/19 Тираж 706 Подписное Й ю Филиал ППП "Патент", r. Ужгород, ул. Проектная, 4 
