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

 

УСТРОЙСТВО ДЛЯ BbfBOPA УПОРЯДОЧЕННОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ДАННЫХ, содержащее п входных регистров, п дешифраторов,и регистров результата, (пп| групп элементов Н, h групп элементов ИЛИ, коммутатор, выходы которого являются выходами устройства, блок анализа, включающий поразрядные узлы анализа, каждый из которых содержит (п-1 )элементов И, (г -1 j элеMiEHTOB № и многовходовый элемент ИЛИ, причем выходы каждого i-го регистра, входы которого являются входами i-го сортируемого числа устройства , где ,2,...,h, п - число сортируемых чисел, соединены с входами i-ro дешифратора и с информационными входами i-x элементов И каждой -й группы, j-и выход каждого -го дешифратора соединен с i-M входом j-ro поразрядного узла анализа, где ,2,...,m , m- число разрядов сортируемых чисел, в каждом J-M поразрядном узле анализа k-й вход, где 1 1 ,2,... ..., (п-1)через k-й элемент НЕ соединен с (k+l)-ми входами k-ro, (k + l)-го,. .., ()-го элементов И, каждый р-й вход поразрядного узла анализа подключен к первому входу (р-1 |-го элементам, где ,3,...,№, первый вход j-ro поразрядного узла подключен к его первому выходу,а выход к-го элемента И поразрядного узла анализа соединен с (К+1)-м выходом поразряднаго узла анализа, выходы элементов И V-й группы устройства подключены к соответствующим входам 1-го элемента ИЛИ т -и группы, выходы элементов ИГЩ -и группы соединены с информационными входами )-го регистра результата , выходы которого соединены с информационными входами i-и группы коммутатора, который содержит h (А групп элементов И, дешифратор и гистр, входы которого соединены с шиной Размер Массива, а выходы -с § соответствующими входами дешифратора, i-и выход которого подключен к первым входам элементов И первой, второй,..., (i-и групп, информационные входы i- группы коммутатора со подключены к вторым входам элементов И л-й группы, входы опроса элемен00 00 тов И всех групп соединены с управляющим входом коммутатора, шина Начальное гашение подключена к входам установки в О входных регистров и регистров результата, шина Опрос подключена к управляющему входу коммутатора, о т л и ч аю щ е е с я тем, что, с целью повышения быстродействия, в устройство введены п узлов формирования сигналов переписи, а в блок анализа h узлов преобразования кодов, каждый t-fi узел формирования сигналов переписи содержит п элементов ИЛИ и

СОЮЗ СОВЕТСНИХ3

РЕСПУБЛИК

„.SUÄÄ 1109738 А

Зц)1 G 06 F 7/06

I, —,, ..--ОПИСАНИЕ ИЗОБРЕТЕНИЯ н AB TopcHoMY свидетельству

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

ll0 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3575267/IS-24 (22) 08.04.83 (46) 23.08.84. Бюл. N". 31 (72) В.Г.Попов и А.Х.Ганитулин (53) 681.325(088.8) (56) 1. Авторское .свидетельство СССР . II 903864, кл. G 06 F 7/06, 1979.

2. Авторское свидетельство СССР по заявке II 3479494/24, кл. С 06 F 7/06, 1982 (прототип).

3. Алексеенко A.Ã., Шагурин И.И. . Иикросхемотехника. M., "Радио и и связь", 1982, с.416. (54)(57) УСТРОЙСТВО ДЛЯ ВЫБОРА УПОРЯДОЧЕННОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ДАННЫХ, содержащее и входных регистров, п дешифраторов, и регистров результата, (пв) rpynr. элементов И, п групп элементов ИЛИ, коммутатор, выходы которого являются выходами. устройства, блок анализа, включающий поразрядные узлы анализа, каждый из которых содержит (n-1)элементов И, (и — l) элементов НЕ и многовходовый элемент

ИЛИ, причем выходы каждого i-ro регистра, входы которого являются входами i-го сортируемого числа устройства, где i=l,2,...,n, и — число сортируемых чисел, соединены с входами i-го дешифратора и с информационными входами i-x элементов И каждой -й группы, 1-й выход каждого !-го дешифратора соединен

7 с 1-м входом j-го .поразрядного узла анализа, где )=1,2,...,в, м- число разрядов сортируемых чисел, в каждом 1-м поразрядном узле анализа 1-й вход, где 1<=1,2,. ° . ..., (п -1)через М-й элемент HE соединен с (k +))-ми входами fc-го, (k+1) -го,..., (n — 1) -ro элементов И, каждый р"й вход поразрядного уэна анализа подключен к первому входу (р"1 )-го элемента И, где р=2,3. ..n, первый вход )-го поразрядного узла аналцэа подключен к его первому выходу,а выход к-го элемента И пораз. рядного узла анализа соединен с (Ь+!)-м выходом поразряднîro узла анализа, выходы элементов И 1-й груп пы устройства подключены к соответствующим входам 1-го элемента ИЛИ

i --й "группы, выходы элементов ИЛИ

1 -й группы соединены с информационными входами i-ro регистра результата, выходы которого соединены с информационными входами i-й группы коммутатора, который содержит и групп элементов И, дешифратор и ре гистр, входы которого соединены с шиной "Размер массива", а выходы - с соответствующими входами дешифратора, i -й выход которого подключен к первым входам элементов И первой, второй,..., b-й .групп, информационные входы 1 и группы коммутатора подключены к вторым входам элементов

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

II09738

Ю групп элементов И по п1 элементов в каждой группе, причем в каждом узле формирования сигналов переписи выходы элементов И 1-й группы соединены с входами 1-ro элемента ИЛИ узла формирования сигналов переписи, каждый j-й узел преобразования кодов, где j =2,3,...,n,содержит rn элементов И и о элементов И-НЕ, причем выход }-ro элемента И-НЕ сое( динен с 1"м выходом 1-й группы информационных выходов блока анализа и его вторым входом )-го элемента И () e I)-го узла преобразования кодов, выход j-го элемента И узла преобразования кодов соединен с прямым входом

j "го элемента И-НЕ,с (j+) )-ми инверс. ными входами (j+ I )-го, () +2) -го, Ill-ro элементов И-НЕ и с первым входом

j-ro элемента H(j+I)-го узла преобразования кодов, первый узел преобразования кодов содержит ч элементов И-НЕ, причем. выход j-го элемента

И-НЕ соединен с j-м выходом первой группы информационных выходов блока анализа и с вторым выходом j-го

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

Известно устройство для определе. ния наименьшего из я чисел, содержащее входные регистры, дешифраторы, поразрядные узлы анализа, выполненные на элементах НЕ и .И, элементы

ИЛИ (i g.

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

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

1 -го поразрядного узла анализа соединен с прямым входом j-го элемента

И-НЕ, с (.je I }-ми входами (j+I }-го, (} +2)-го,..., tn-го элементов И-НЕ первого узла преобразования кодов, i --й выход } -ro поразрядного узла анализа подключен к i-му входу многовходового элемента ИЛИ, выход которого является выходом логической су .мы j-го поразрядного узла анализа, i é выход j-го поразрядного ,узла анализа блока анализа соединен с управляющими входами j-го элемента И i-й группы каждого i-ro узла формирования сигналов переписи, информационные входы j-х элементов И, всех групп г-ro узла формирования снг напав переписи соединены с выходом -ro

J элемента И-НЕ i -го узла преобразования кодов блока анализа, выход -ro элемента ИЛИ i-ro узла формирования сигналов переписи соединен с управляющими входами всех элементов И (ii )-й группы устройства. управления, коммутатор, группы элементов ИЛИ и И, элемент ИЛИ, группы входных элементов И и ИЛИ, шины

"Начало операции", "Начальное гаше5 ние" и "Размер. массива", блок анализа, состоящий из элементов ИЛИ и поразрядных узлов анализа, причем выходы каждого i --ro регистра, где

1 =},2,..., ь, соединены с входами

i -го дешифратора и с информационными входами элементов И i é группы, а выходы i-ro элемента ИЛИ подключены к входам управления элементов

И I-. é группы, выходы элементов И

35 каждой i-й группы соединены с входами элементов ИЛИ группы, выходы которых подключены к входам регистра результата, каждый )-й выход .i-ro дешифратора соединен с

20 i-м входом г-го поразрядного узла анализа, где ) =!,2 ..., ln т -число разрядов. сортируемых чисел, каждый

1-й выход j-го поразрядного узла анализа подключен к 1-му входу )-ro

25 элемента ИЛИ, а выход переносов каждого к-ro поразрядного узла ана3 лиза, где к=1,2,...,(гп-l), соединен с входом управления(к+1) -ro поразрядного узла анализа, каждый 1-й поразрядный узел анализа состоит из элементов И,п элементов НЕ и многовходового элемента И, причем каждый -й вход поразрядного узла анализа подключен к первому входу i-го элемента И, вход управления поразрядного узла анализа соединен с вторыми входами элементов И, каждый 1-й вход, к-го поразрядного узла анализа подключен че)жз I-й элемент НЕ к (i+2}-ìó входу (i+I), (i+21,..., ь -ro элементоь.

И и к -му входу многовходового элемента И, выход которого подключен к выходу переносов к-го поразрядного узла анализа, выход каждого i-го элемента И соединен с i ì выходом к-ro поразрядного узла анализа,.э -й поразрядный узел анализа состоит из элементов И и(n-11-го элемента . НЕ, причем каждый р-й вход узла, где р=1 2,...,(ь — I}, соединен с первым входом р-го элемента И, вход,.переносов tn-го поразрядного узла анализа подключен к вторым входам элементов И, каждый р-й входа -ro поразрядного узла анализа через р-й элемент НЕ соединен c(p+2 I-и входом (р+1 },(p+2 },..., II-го элементов И, Пгй вход в-го поразрядного узла анализа подключен к(гп+2)-му входу

Il-го элемента И, выход каждого i-го элемента И соединен с i-ым выходом

nего поразрядного узла анализа, 1-й выход блока анализа, соединенный с выходом i-. ro элемента ИЛИ блока анализа, подключен к первым управляю щим входам 1-х элементов И в каждой из 0 групп элементов 11JIH, где =

=I ?,...,л, информационные входы которых соединены с выходами 3-ro входного регистра, и, к первому входу

j -ro элемента И группы входных элементов И, вторые sxopal всех элементов группы входных элементов И соединены с выходом элемента ИЛИ, выход

i -ro элемента группы входных элементов И с первым входом 1-ro элемента группы входных элементов ИЛИ, выход которого подключен к входу установки в ноль 1-ro входного регистра, 1-й выход блока управления подключен к вторым управляющим входам всех элементов И 1-й группы и к i-му входу элемента ЙЛИ, выходы элементов И i""й" группы из (1в1 групп подключены к со< тветствующим входам i-го элемента

И 51 $-ой группы, выходы которого

9738

t5

25

40 ходом блока управления, информационные входы блока управления подключе-. ны к установочным входам счетчика, коммутатор содержит и групп элементов

И, дешифратор, регистр, входы которо45 го соединены с входами коммутатора, а выходы — с соответствующими входами дешифратора, 1-й выход которого подключен к первым входам 1,2,.. °, i-x групп элементов И, информацион50ные входы 1-й группы коммутатора

35 соединены с информационными входами

3 -ro регистра результата, группа информационных выходов i-ro регистра, результата соединена с соответствую-. щими информационными входами 1-й группы коммутатора, выходы которого являются информационными выходами устройства, управляющий вход коммутатора подключен к выходу блока управления, шина "Начальное гашение" соединена с входом установки блока управления, с нулевыми входами выходных регистров и с вторыми входами всех элементов группы входных элементов ИЛИ, шина "Размер массива" соединена с информационными входами коммутора и блока управления, который содержит триггер управления, счетчик, дешифратор, элементы И, ИЛИ, группу и элементов И, генератор импульсов, выход которого соединен с первым входом элемента И, второй вход которого соединен с прямым выходом триггера управления и первыми входами элементов И группы, а выход - с счетным входом счетчика, информационные выходы которого подключены к дешифратору, i -й выход которого соединен с вторым входом i --ro элемента И группы, выход которого является 3-м выходом блока управления, выход сигнала переполнения счетчика подключен к первому входу элемента

ИЛИ, второй вход которого соединен с шиной "Начальное гашение", а выход элемента ИЛИ подключен к нулевому входу триггера управления, единичный вход которого соединен с входом установки блока управления, а инверсный выход является управляющим выподключены к вторым входам элементов

И i-и группы, управляющие входы элементов h всех групп соединены с управляющим входом коммутатора f2)..

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

09738

20

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

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

i-ro регистра, входы которого являются входами i-ro сортируемого числа устройства, где i =I,2,..., n ,h — число сортируемых чисел., соеди,нены с входами i — го дешифратора и с .информационными входами 1-х элементов И каждой 1-й группы, -й выходкаждого 1-ro дешифратора соединен с

1- входом 1-го поразрядного узла анализа,где 1=1,2,...,rn, т — число разрядов сортируемых чисел, в каждом

j-м поразрядном узле анализа к-ый вход, где к=1,2,...,(n-l) через к-й элемент

НЕ соединен с (1+1) -ми входами k-го, (1<+1 )-го,...,(ь — 1) -го элементов И, каждый р-й вход поразрядного узла анализа подключен к первому входу(р-1) -го . элемента И,где р=2,3,...,h, первый вход -ro поразрядного узла анализа

3 подключен к его первому выходу,а выход к-ro элемента И поразрядного узла анализа соединен c(1 +I} -ым выходом поразрядного узла анализа, выходы элементов И i-ой:группы устройства подключены к соответствующим входам i-го элемента ИЛИ i-й группы, . выходы элементов ИЛИ i-й группы . .соединены с информационными входами

i — го регистра ре зуль тата, выходы ко торого соединены с информационными входами 1-й группы коммутатора, который со— держит и групп элементов И,дешифратор и регистр, входы которого соединены с шиной "Размер массива", а выходы— с соответствующими входами дешифрато. ра, i -и выход которого подключен к первым входам элементов И первой, второй,..., 1 -й групп, информационные входы i -й группы коммутатора подключены к вторым входам элементов

И -й группы, входы опроса элементов .

И всех групп соединены с управляющим входом коммутатора, шина Начальное

ll гашение подключена к входам установки в 0" входных регистров и регистров результата, шина пОпрос" подключена к управляющему входу коммутатора, введены и узлов формирования .сигналов переписи, à в блок анализа ь узлов преобразования кодов, каждый 1 -й узел формирования сигналов переписи содержите элементов ИЛИ и и групп элементов И по

In элементов в каждой группе, причем в каждом узле формирсвания сигналов переписи выходь элементов К 1-й группы соединены с входами i ão элемента ИЛИ узла формирования сигналов переписи, каждый j é узел преобразования кодов, где ) =2,3,...,, содержитfB элементов И и Ill,ýëåìåíòoâ

И-НЕ, причем выход j-го элемента

И-11Е соединен с 1-м выходом 1-й группы информационных выходов блока анализа и его вторым входом )-ro элемента H(j+I )-ro узла преобразования. кодов, выход j-ro элемента И

30 узла .преобразования кодов соединен с прямым входом j-ro элемента И-НЕ, с (j +I) -ми инверсными входами (1+1)го,(1+2)-ro,,в-ro элементов И-ЙЕ с первым входом j-ro элемента И

35 (j +1 )-ro узла преобразования кодов, первый узел преобразования кодов содержит 1п элементов И-НЕ, причем выход j-го элемента И-НЕ соединен с

j-м выходом первой группы информа40 ционных выходов блока анализа и с вторым входом j-ro элемента И второго узла преобразования кодов, выход логической суммы j-го поразрядного узла анализа соединен с прямым входом 1-го элемента И-НГ, с (j+1)-ми входами (j+ I )-го, {j+2)-ro,..., в- го элементов И-НЕ первого узла преобразования кодов,ll-й выход j-ro поразрядного узла анализа подключен к

1-му входу многовходового элемента

ИЛИ, вьиод которого является выходом логической суммы j-ro поразрядного узла анализа, i-й выход 1-ro поразрядного узла анализа блока анализа соединен с управляющими входами j го элемента И 1-й группы каждого 1-ro узла формирования сигналов переписи, информационные входы j --x элементов И всех групп

1109738

Таблица l

25 а„ 101

30 а2 110 а =001

3 а4, =0!0

О I О О О 0 0

0 0 0 0 0 0 0

i --го узла формирования сигналов переписи соединены с выходом j-ãо элемента И-НЕ l -го узла преобразования кодов блока анализа, выход

i --ro элемента ИЛИ i-ro узла формирования сигналов переписи соединен с управляющими входами всех элементов И (ii) -й группы устройства.

На фиг. 1 показана структурная схема устройства; на фиг. 2 — структурная схема блока анализа; на. фиг. 3 — структурная схема поразрядного узла анализа; .на фиг. 4 — струк турная схема узла формирования сигналов переписи; на фиг. 5 †. структурная схема коммутатора.

Устройство(фиг. !Iсодержит информационные входные шины l„ 1„, подключенные к входам соответствующих входных регистров 2 — 2„, соединены с входами соответствующих дешифраторов 3., — 3„, выходные шины 4 — 4„ которых подключены к блоку анализа

5, группы информационных. выходов

61- 6„ и группа управляющих выходов

7 которого соединены с узлами 8 - 8 управления, выходные шины 9„ — 9

1,п ...,9 — 9 которых соединены с ь,.< n.n управляющими входами групп элементов И 10„ — 10,...,10 — 10, выхо1.1 М n.1 М1 ды которых подключены к соответствующим элементам KIH II â !1„ групп пы, выходы которых подключены к информационным входам соответствующих регистров результата 121- 12„, выходы 13 — 13„ регистров подключены к коммутатору 14 выходные шины

15 — 15„ которого являются информационнымй выходами устройства, шину

16 "Начальное гашение", шину 17 "Раз мер массива" и шину 18 "Опрос".

Блок анализа(фиг. 2.!содержит поразрядные узлы 19 — !9,„анализа, узлы 201 в 20Ä преобразования кодов, элемент И-HE. 21 - 21 и элемент И

22„;- 22 B узлах преобразования кодов.

Поразрядный узел анализа(фиг. 3) содержит элементы НЕ 231- 23 „ многовходовый элемент ИЛИ 24 и элементы И 25 25 1

Узел формирования сигналов переписи (фиг. 4} содержит и групп элементов H 26 26 ... 26 — 26 no t«

ll.1 Il e элементов в каждой и и элементов

ИЛИ 27 „- 27„.

КоммутатЪ (фиг. 5 !содержит. Регистр 28, соединенный с дешифратором

29, выходные сигналы которого подключены к элементам И 304- 30п.

° 3

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

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

Пусть имеются четыре числа a -=

=101,à =110, à =001,, а+=010, размещенные в соответствующих регистрах.

Требуется преобразовать эту последовательность в упорядоченную убываюI5

Эти числа преобразуются дешифраторами, выходные .сигналы которых по-. казаны в табл. 1 °

В табл. 1 Q „- Π— сигналы логической суммы, а

1 анализа.

Выходы ДС I 2 3 4 5 6 7 8

0 0 О O l О 0 я

I О 0 О О О О

Из табл. 1 следует, что наименьшее число находится в третьем регистре, 40 очередное число в четвертом, далее в первом и наконец во втором. Таким образом, упорядоченная последовательность чисел следующая: а, а, а

Отсюда, в первом выходном рег1ст"

4 ре результата должно быть размещено . число, находящееся в третьем входном, во втором — число из четвертого входного регистра, в третьем — из второго и в четвертом — из первого входного РегистРа.

Указанием о том, какое первое наименьшее число, является крайняя левая едингца в колонке табл.. 1.

Для дпнного примера — это сигнал

55 81, далее -Q G»G . Информация о .номере входного регистра, где находится экстремальное число, содержится . в индексе сигнала у (соответственно

71 Ъ< 1Ф 9<1 <«2

1109738

1О

ТакИм образом, если код сигналов !

1-8, преобразовать так, чтобы в нем была одна единица, определяющая ном"р поразрядного узла анализа, то посредством сигналов а †, данно01 1 го узла можно передать наименьшее число в соответствующий регистр результата.

Итак, для первого выходного регистра двоичный код 1100110 преобразуется в код 1000000, а для второго выходного регистра из кода

OI0OI!0 в код 0100110. Далее, для третьего выходного регистра из кода

0000110 в код 0000100 и для четвертого будет код 0000010.

Преобразования кодов для выходных регистров с помощью узлов преобразования кодов блока 5 анализа(фиг.2) осуществляют следующим образом.

Предварительно посредством поразрядных узлов анализа(фиг. 3)формируются выходные сигналы 1,„- 9, с поь1ощью э. ементов И 25„-25ь„и сигнь)

@„-6„, с помощью элемейта ИЛИ 24.

Блок анализа 5(фиг. 2)содержит и узлов преобразования. В первом узле преобразования, состоящем из в элементов И-HF., формируется на выходах 6„„-6„ двоичный код сигналов логич»ских сумм Й .

Сигнал логической суммы с выхода

191 закрывает по первым инверсным входам все элементьг И-НЕ 211- 21„, Таким образом, на информационных выходах первой группы формируется двоичный инверсный код 0llllll. Эти же сигналы и соответствующие им сигналы Q.,-É воздействуют на входах элементов И 22 — 22 второго узла преобразования. На выходах элементов

H 22„ — 22 формируется двоичный прямой код 01001 10.

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

В четырех узлах преобразования .формируются двоичные коды: 0111111, 1011111, 1!11011, 11!1101. Это означает, что информация о месте разме,щения минимального числа для первого выходного регистра 12 (фиг. 1)находится в первом поразрядном узле

19„анализа (фиг. 2), для второго — во втором узле(192), для третьего — в!

25 пятом (19 ) и для четвертого выходного регистра в шестом поразрядном узл»

19ь анализа.

Эти сигналы в качестве информационных подаются .в соответствующие узлы 8> — 8„ управления, которые на основе управляющих сигналов

t табл. !!обеспечивают формирование управляющего сигнала на выходе 9 узла 8>, например для первого регистра. По этому сигналу число иэ регистра 2з передается в выходной регистр

12

Аналогичным образом обеспечивается передача чисел из остальных входных регистров 2 — 2,1 в выходные 12 — 12+.

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

С помощью коммута1ора 14 обеспечивается по сигналу "Опрос", поступающему по шину 18, вьдача указанного размера выходного массива на информационные выходы 15 устройства.

Пусть необходимо из массива четырех чисел на выход устройства вьдать два числа. Довичный код этого числа поступает в регистр 28(фиг. 5).

Разрядность регистра определяется; максимальным размером исходного массива чисел h и выбирается по выражению: / . у р=ео - ..

40 В дешифраторе 29 будет возбужден второй выход, разрешающий работу элементов И 30 и 30 . По сигналу

"Опрос", поступающему по шине 18, выходные сигналы регистров 12, 12

1 2 по шинам 131, 13 через элементы И

30„ и 30> поступят на выходные шины

13„, 13> устройства.

С помощью предложенного устройства можно формировать упорядоченную возрастающую последовательность

50 чисел. При этом исходные числа в регистры 21 в 2„принимаются в обратном коде. Выходная последовательность будет также в обратном коде.

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

Вначале по шине 16 "Начальное гашение поступает сигнал, по которому входные регистры 2 — 2„ и выходные

1!0973Я

1 17 «), - (4n+12)

---- — -- ---- 1 007.

)7, »«еМ 9<п

11 регистры 12 — 12 устанавливаются

1 h ,в нулевые состояния. Затем по входным шинам l — 1„принимаются в регистры 2„- 2„ исходные числа. Если нужно получить убывающую последова5 тельность, то числа поступают в прямом коде, если возрастающую — обратном.

Одновременно по шине 17 "Размер массива" в регистр 28 принимается двоичный код требуемого массива.

В дальнейшем в каждом узле преобразования. кодов(фиг. 2)формируются двоичные коды так, что номер. позиции размещения нулевого значения сигнала опредепяет номер поразрядного узла

l9 анализа, выходные сигналы которого используются для передачи экстремального числа из соответствующего входного регистра 2 в выходной регистр 12. Формирование выходных

20 сигналов в. регистрах 12 — 12„определяется временем задержки в формиро вании информационных сигналов 6„„-6

Поэтому сигнал "Опрос",по шине 18 поступает по окончании передачи

25 чисел в выходные регистры. Размер сформированной последовательности. определяется двоичным кодом и "E аэмер массива", по которому в дешифраторе 29(фиг. 5)возбуждается та. шина, номер которой соответствует размеру заданного выходного массива.

В соответствии с этим на выходах устройства 15„ — 15„устанавливается заданный выходной массив данных.

Из анализа структурной схемы и 1 принципов функционирования известного устройства время формирования выходной упорядоченной последовательности данных определяется периодом следования импульсов генератора блока уп- 40 равления и размером выходного массива.

Период следования импульсов характеризует время одного цикла работы устройства и зависит от времени задержки

; при выборе экстремального числа. 5

Для формирования массива размером ,, в«1.чисел(«),< o)время работы устройства составляет T1= q,t„» где „и — период следования импульсов генератора блока управления. 50

Минимальный период следования импульсов равен

««+«+ ««- «+ф, «.ф, Ги или и или тя д «.«н где «и„и, «„, « — времена задержек в элементах ИЛИ, И и триггерах входных

1 регистров соответственно;

12 время работы дешиф-.

4 ратора которое можно принять равным«и;

= i +« +« +« — время анализа блоби HE и и или ком анализа, макси-. мальное время задержки которого определяется последним (п1-ымJпоразрядным узлом анализа; ...Если принять, что Т„= «и,1„,ь«„ =2 «и, «,=В и .. (33, Ф

Т =с),(«+ «+«+В «+ ««.27«+ «+ «+ « 1=17а«(1)

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

Т =«+ + +

2 "Т2 * ин ч« гдето =«+«+

ale НЕ и «, и-не (и и-НЕ!("-1) — время работы блока анализа; иЕ время задержки в элементе И-НЕ;

« «„,,и — время задержки в блоке управления °

Если принять, что t = 2 i i+ « то

+27 + «+«+««2, +jt + « +2

Т„-Т, I9 = . 100 (в (3)

Подставляя в выражение(31выражения(1)и(2 ), получим

17«), <. — (4«n + )2«„)

Р --- — 1ООЖ** !

7« ТИ

Определим при каких соотношениях величин «), и п обеспечивается выиг- рыш в быстродействии.

Очевидно, что выигрыш в быстродействии будет всегда, когда % ) О..

Отсюда, преобразуя выражение(4 ), получим

17 ) -(4 +12) оо 7 > о

17 ч.

17<), -(4n + )2))0. или

1!097!

Таблица2

2 4 8 16

32 64

4в+ 12

° 1 ф) — - — -- —- (5)

17 причем g <

Из выражения(5}видно, что выигрыш в быстродействии обеспечивается для 5 при н 2.

Определим,при каком состоянии с1, и и достигается выигрыш в быстродействии

Лусть и 2, тогда из выражения(5) следует, что

8 + 12 20

Я,) — - — — — - — -) 1

17 17 т.е. при rl 2, q, должно быть равно 2.

Если и 3, то !5

,> †-- > 1, т.е. < =2,3.

24

Из приведенных расчетов следует, что выигрыш в быстродействии дости38, 14 гается при h7 2 для любых значений

q,, причем,<п.

Для случая, когда =, в табл. 2 приведены величины % при различных

< значениях

41 58 67 72 73 74

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

Ф

Ь 1

1)09738

1109738

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

Редактор С.Патрушева Техред Т.Фанта Корректор Л.Пилипенко

Заказ 6085/34 Тираж 699 Подписное

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

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

Филиал ППП "Патент",. г. Ужгород, ул. Проектная, 4