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

 

1. УСТРОЙСТВОдля СОРТИРОВКИ ДВОИЧНМХ ЧИСЕЛ, содержащее П входных , т-разрядных регистров, где П-число сортируемых чисел, m -число разрядов сортируемых чисел, И групп элементов И по m элементов И в группе, дешифраторы и блоки сравнения, причем вход- . ные информационные шины устройства г соединены с информационными входами соответствуювдх входных регистров, прямой выход -го разряда каждого входного регистра, где i 1,2,..., tl , подключен к первому входу i-го элемента И соответствуюп1ей группы, выходы -го блока сравнения, где j 1,2,.. .lni-2j , соединены с соответствующими входами первой группы (J +1)-го блока сравнения, входы первой группы первого блока сравнения соединены с соответствующими выходами первого дешифратора, выходы k -го дешифратора, где k 2,3,..., И1, подключены к соответствующим входам второй группы .Ij-ro блока сравнения, о т л и - , Чающееся тем, что, с целью расширения функциональных возможностей устройства путем сортировки чисел по возрастанию их величины, в него введены П выходных tH -разрядных регистров , выходы которых соединены с соответствующими выходными шинами устройства , К групп элементов И, где 2 (п+1) , (п+2) , ...,2П, блок управления , блок выявления равных чисел, .формирователь сброса и коммутатор, причем первый вход блока управления : подключен к шине начала работы устг ройства,а разрешающий выход соединен с вторыми входами элементов И всех групп,инверсный выход 4 -го разряда каждого входного регистра подключен к первому входу -го элемента И соответствующей Р. группы, второй вход блока упс равления соединен с первым выходом блока выявления равных чисел,а такТовый вы (Л ход - с тактовым входом блока выявления равных чисел,второй выход которого подключен к управляющему входу формирователя сброса, выходы которого соединены с установочными входами соответствующих входных регистров, распределительные выходы блока управления сое-, динены с входами первой группы комсо со мутатора, выходы первой группы кото-рого подключены к соответствующим входам выходных регистров, выходы второй группы коммутатора соединены с соответствующими информационными входами формирователя сброса, входы второй группы коммутатора соединены с соответствующими выходамиэлементов И П групп, входы третьей группьт коммутатора подключены к соответствующим выходам (ni-l) -fo блока сравнения и к соответствующим информационным входам выявления равных чисел, выходы ч -х элекентов И и групп подключены к соответствующ1ш входам

ÄÄSUÄÄ 1049900 А

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

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

РЕСПУБЛИК (д1) С 06 Г 7/06

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

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

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ABTOPCHOIVIY СВИДЕТЕЛЬСТВУ, . "":=. :::(:тадж я=ила:ас. ;:ас -... 1 (21) 3462244/19-24 (22) 02-.07.82 (46) 23.10.83. Вюл. У 39 (72) В.И.@инаев (71) Таганрогский радиотехнический институт им. В.Д.Калмыкова (53) 681.325(088.8)

l .56) 1. Авторское свидетельство СССР

Ф 620976, кл. G 1 06 Г 7/02, 1977.

2. Авторствqe свидетельство СССР

Ф 746501, кл. 1 06 F 7/02, 1978.

3. Авторское свидетельство СССР по заявке Ф 3262048/24, кл. G 06 F/02, 1981 (прототип). (54) {57) 1. УСТРОЙСТВО ДЛЯ СОРТИРОВКИ

ДВОИЧН14Х ЧИСЕЛ, содержащее и входных

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

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

1,2,... _#_-2j, соединены с соответст вующими входами первой группы (1 +1)-го блока сравнения, входы первой группы первого блока сравнения соединены с соответствующими выходами первого дешифратора, выходы k -го дешифратора, где k =2,3,..., п1, подключены к соот" ветствующим входам второй группы (-.—

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

0 =(И+1), (0+2);...,20, блок управления, блок выявления равных чисел, формирователь сброса и коммутатор, причем первый вход блока управления подключен к шине начала работы уст. ройства,а разрешающий выход соединен с вторыми входами элементов И всех групп, инверсный выход q -ro разряда каждого входного регистра подключен к первому входу < -го элемента И соответствующей F. группы, второй вход блока управления соединен с первым выходом бло- Ж ка выявления равных чисел, а тактовый вы- - ур1 ход — c тактовым входом блока выявления равных чисел, второй выход которого под- С ключен к управляющему входу формирователя сброса, выходы которого соедине" ны с установочными входами соответствующих входных регистров, распределительные выходы блока управления сое-, динены с входами первой группы ком" мутатора, выходы первой группы которого подключены к соответствуначим входам выходных регистров, выходы второй группы коммутатора соединены с соответствующими информационными входами формирователя сброса, входы второй группы коммутатора соединены с соответствующими выходами элементов И и групп, входы третьей группы коммутатора подключены к соответствующим выходак" (В-1) -ro блока сравнения и к соответствующим информационным входам блока выявления равных чисел выходы е -х эле ентов И и групп подключены к соответствующим входам

104 первой группы ) - го дешифратора, входы второй группы которого, соединены с выходами соответствующих -х элементов И 3 групп, выходы (P -1) -х элементов И И групп, гдето 1,2,...,(п1 "1), подключены к соответствующим входам .третьей группы Р -х блоков сравнения.

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

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

s ноль триггера, выходы распределителя сигналов соединены с соответствующими распределительными выходами блока управления.

3. Устройство по п.1, о т л и— ч а ю щ е е с я тем, что блок выявления равных чисел содержит кодоЬреобразователь, реверсивный счетчик и Элемент задержки, причем тактовый вход блока выявления равных чисел подключен к тактовому входу реверсивного счетчика, информационные входы которого соединены с соответствующими выходами кодопреобразователя, входы которого соединены с информационными входами брока выявления равных чисел, выход

9900 . реверсивного счетчика соединен с

1 первым выходом блока выявления равных чисел и через элемент задержкис вторым выходом блока выявления равных чисел.

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

5. Устройство по п.1, о т л и— ч а ю щ е е с я тем, что коммутатор содержит И групп входных элементов И, и элементов ИЛИ и n rpynn выходных элементов И, причем R -й вход первой группы входов, где 11 =1, 2,..., й, соединен с первыми входами выходных элементов И соответствующей группы, вторые входы Я -х выходных элементов И всех групп соединены с выходами К -х элементов ИЛИ, входы

4 которых соединены с выходами (-х входных элементов И всех групп и соответствующими выходами nepaof. группы коммутатора, первый вход j -го входного элемента И

1 -й группы соединен с соответствующим входом второй группы входов коммутатора, R --fi вход третьей группы входов коммутатора соединен с вторыми входами элементов.И соответствующей группы, выходы выходных элементов И соединены с выходами второй группы коммутатора.

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

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

Известно устройство для выделения многоразрядного кода, содержащее 25

Н (2 — 11 узел анализа, 11 мажоритарных элементов, причем информацион- ный вход каждого(1 j) -го узла анализа соединен с 1 --ым входом < -ой группы входов устройства, где < =1,2, ур

111, j =1 2,..., (2Ф -1),. выход < -ro мажоритарного элемента подключен к . первому входу управления r (» . 1), (1 2), tj (2m — 1Ц -ro узлов анализа, первый второй, третий, четвертый и пятый выходы каждого(1) -ro узла анализа соединены с вторым, третьим, четвертым, пятым и шестым входами управле. ния(((+1) j) -ro узла анализа соответственно выход результатаt q «j| Го 4О узла анализа подключен к -му входу

h--ro мажоритарного элемента 12 .

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

3 1049 шенин экстремальных задач управления объектами с многими параметрами.

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

ИЛИ и НЕ fl).

Наиболее близким к предлагаемому по совокупности конструктивных и функциональных признаков является устройство для определения экстремального числа, содержащее регистры, элементы И, блоки сравнения, дешифраторы состояний, число которых равно числу регистров, причем входные шины соединены с входами регисТров соответственно, вьмоды регистров соединены соответственно с входами gemnn, раторов состояний, первыми входами бло ков сравнения и первыми входами элементов И, выходы которых соединены с выходными шинами устройства, а вторые входы — с выходами последнего блока сравнения, причем выходы каждого блока сравнения, кроме последнего соединены с вторыж входами последующего блока сравнения, а вторые входы первого блока сравнения соединены с выходами первого дешифратора сос(тояний„третьи входы блоков сравнения соединены с выходами соответствующих дешифраторов состояний (3) .

Однако устройство осуществляет выбор либо минимального, либо максимального числа, в зависимости от то

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

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

Указанная цель достигается тем,. что в устройство для сортировки двоичных чисел, содержащее rl входных

Щ-разрядных регистров, где tl -число сортируемых чисел, п1 -число разрядов .сортируемых чисел, П групп элементов И по П1 элементов И в группе, дешифраторы и блоки сравнения, причем входные информационные шины устрой,ства соединены с информационными вхо дами соответствующих входных регистВ ров, прямой выход < -ro разряда каждого входного регистра, .где 1 =1,2...

О, подключен к первому входу < -ro элемента И соответствующей группы, выходы 1 -го блока сравнения, где 1

1,2,...,(tn-2), соединены с соответст вующими входами первой группы(1+1) -ro . блока сравнения, выходы первой группы первого блока сравнения соединены с соответствующими выходами первого дешифратора, выходы l< -ro дешифратора, где k =2,3,...,а, подключены к соответствующим входам второй группы (k-1)-го блока сравнения, введены

5 выходных N -разрядных регистров., выходы которых соединены с соответствукицими выходными шинами устройства, групп элементов И, где ? =(ИФ1), (11 +2},..., 2h блок управления, блок

5 104 выяй(ления равных чисел, формирователь . сброса и коммутатор, причем первый вход блока управления подключен к шине начала работы устройства, а разрешающий выход соединен с вторыми входами элементов И всех групп, ин», версный выход 1 -го разряда каждого входного регистра подключен к первому входу (-го элемента И соответствующей группы, второй вход блока управления соединен е первым. выходом блока выявления равных чисел, а такто- вый выход - с тактовым входом блока выяв.ления равных чисел, второй выход которого подключен к управляющему .; входу Аормирователя сброса, выходы которого соединены с установочными входами соответствующих входных регистров, распределительные выходы блока управления соединены с входами первой группы коммутатора, выходы первой группы которого подключены к соответствующим входам выходных . регистров, выходы Второи группы ком-, мутатора соединены с соответствующими инАормационными входами Аорми рователя сброса, входы второй груп- . пы коммутатора соединены с соответству1ощими выходами элементов И групп, входы третьей группы коммутатора подключены к соответствующим . 30 выходам (%-1) -ro блока сравнения и к соответствующим инАормационным входам блока выявления равных, чисел, выходы (-х элементов И g групп под ключены к соответствующим входам 35 первой группы 4 --го дешифратора, входы второй группы которого соединены с выходами соответствующих 4 -х элементов И E групп, выходы (p — 17-х элементов И 11 групп, где р =1,2,..., 4О (—

1п-1), подключены к соответствующим входам третьей группы р -х блоков сравнения.

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

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

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

Формирователь сброса содержит формирователь сигнала, ПФ-входовых эле- ментов ИЛИ и q элементов И, причем информационные входы формирователя сброса соединены с соответствующими вкодами элементов ИЛИ, выходы которых соединены с первыми входами соответ/ствующих элементов И, вторые .входы которых через формирователь сигналов соединены с управляющим входом формирователя сброса, а выходы — с соответствующими выходами формирователя сброса.

Кроме того, коммутатор содержит групп входных элементов И>й элементов ИЛИ и И групп выходных элементов И, причем (-й вхоЦ первой группы входов, где К -1,2,..., Н соединен с первыми входами выходных элементов И соответствукйпей Группы, вторые входы g -х выходных элементов И всех групп соединены с выходами К -х элементов ИЛИ, входи которых соединены с выходами q -х входных элементов И всех групп и соответствующими выходами первой группы коммутатора, первый вхад < -ro входного элемента И К -й группы соединен с соответствующим входом второй группы входов коммутатора, К -й вход третьей группы входов коммутатора соединен с вторыми входами входных элементов

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

1049900 - 8

На фиг. 1 приведена блок-схема предлагаемого устройства; на фиг.2функциональная схема блока управления; на фиг. 3 — функциональная cxef ма блока выявленйя равных чисел; на фин. 4 — функциональная схема формирователя сброса;, на фиг. 5 — функцио.нальная схема коммутатора; на фиг.б- . функциональная схема дешифраторов; на фиг. 7 — функциональная схе-g 16 .ма " каждого иэ блоков сравне,ния; на фиг. 8 — временные диаграммы, отображающие работу устройства для сортировки двоичных нисел во времени. (под выходом Й» понимается jg сигнал на (-ом выходе И-ой позиции).

Блок-схема предлагаемого устройства для сортировки двоичных чисел содержит информационные входные шины 1, -1, где »и -число разрядов 2О

» 3П двоичных чисел, П -число двоичных чи- .. сел, входные регистры 2(-2, элежнты И 3„-3п, 4(-4„:, блок 5 управ-! ttl (ttt ления, шину 6 начала работы устройства, блок 7 выявления равных чисел, щ формирователь 8 сброса. регистров 2, коммутатор 9, дешифраторы 10(- 10(п состояний одноименных разрядов регист». ров 2, блоки 11(— II сравнения, сравнивающие коды по разрядам, причем блок 11>.(ñðàâíåíèÿ выдает сигнал, определяищий, в каком иэ регистров

2 хранится минимальный код, выходные регистры 12 — 121», выходные шины

rn

13 (— 1 Зя ус т ройс тва. 1

Функциональная схема блока 5 управления содержит триггер 14, генератор 15 тактовых импульсов, синхронизирующий работу устройства, второй вход 16, элемент ИЛИ 17, первый и второй выходы 18 и 19, элемент 20 40 задержки, распределитель 21 сигналов, реализованный как обычные распределители телемеханических устройств, сигналы на выходах, которого появляют ся однозначно и последовательно во.

p, ° времени, распределительные .выходы -

22(- 22 блока управления.

I гл

Функциональная схема блока 7 выяв- ., ления равных чисел, содержит реверсивный счетчик 23, кодопреобраэова- © тель 24, предназначенный для выявле-, .ния одинаковых чисел и записи их ко- . личества в двоичном исчислении в счетчик 23, информационные входы 29(1 .

25»1 элемент 26 задержки (времени) ..,И

Функциональная схема формировате-» ля 8 сброса содержит управляющий код 27, : формирователь 28 сигнала, представляю- . щий сЪбой дифференцирующую цепь для формирования заднего фронта сигнала, элементы И 29,(- 29tt s выходы 30(- 30я элементы ИЛИ 31(- 3ltt, входы второй группы 32(- 32, .

Функциональйая схема коммутатора

9 содержит вшходные элементы И 33("

33я, выходи 34 " 34п, элементы

Щ Я

ИЛИ 35 — 35»1, входные, элементы И 36 —

»л

36»1, входы 37 (— 37„.

Функциональная схема дешифраторов

10 — IOttt содержит входы первой .и вто(ttt (1П рой группы 38(- 38, 39(†. 39„, первые и вторые элементы И соответственно

40(— 40»t,s 41(— 41ttt, элементы ИЛИ 42(42, выходы 43(— 43> дешифраторов и (tt соответственно.

Функциональная схема каждого иэ . блоков 11 сравнения содержит первые и вторые элементи И соответственно

44 -44ъ, 45 — 45>, входы второй группы 46(- 46tts первые элементы

НЕ 47(- 47п, третьи элементы И 48»48t1, вторые элементы HE 49(-49п, четвертые элементы И 5О(- 501», третьи . элементы НЕ 51(- 5111, пятые элементы

И 52(= 52(1, первые элементы ИЛИ 53 -.

531, выходы 54(- 54п, вторые элемен- .( ты ИЛИ 55(— 55п.

Устройство для сортировки двоичных чисел работает следующим образом.

По входным шинам 1 — Itt в первые

tn t регистры,2 - 2 » заносятся двоичные числа в параллельных кодах, причем расположение чисел по регистрам 2 производится случайным образом. Задача состоит в том, что данные числа из

1 первых регистров 2 переносят во вторые регистры 12 в порядке возрастания.их величины, т.е. если допустим в регистре 2(есть число 8, в регистре 2у- З,,в регистре 2 -10, в регистре 24- 5, в регистре 2 -1 в двоичной системе счисления, то в ретистрах 12 после сортировки числа эаписывают в следующем порядке: в ре-. гистре 12(-1, в регистре 12 -3, в регистре 12 -5, в регистре 12 -8, в регистре 12 -10.

После того, как числа, подлежащие сортировке, записаны в регистры 2, по второй входной шине 6 подается сигнал управления пуском устройства.

Данный сигнал поступает на первый вход блока 5 управления и перебрасывает триггер 14 в единичное состояние.

Потенциал с единичного выхода триггера 14 запускает генератор тактовых импульсов (фиг.2 и фиг.8). Импульсы

1049900

9 с выхода генератора 15 подаются на второй вход элемента ИЛИ 17 и от второго выхода 19 блока 5 управления на первый вход блока выявления равных чисел. Кроме того, импульсами с выходами генератора 15 через элемент

° 20 задержки времени управляется движение распределителем 21 сигналов.

Элемент 20 задержки времени необходим для задержки времени появления Ið сигналов на выходах распределителя

21 на время, большее времени переходных процессов в дешифраторах 10 и блоках 11 сравнения.

Импульс с выхода генератора 15 через элемент ИЛИ 17 с первого выхода 18 блока 5 управления подается на . вторые входы первых 3 и вторых 4 элементов И, разрешая подачу содержимого первых регистров 2 на соответствую- О щие входы дешифраторов 10, блоков 11 сравнения и коммутатора 9. По данному первому импульсу генератора 15 дешиф° ратрры 10 и блоки 11 сравнения выявляют первое минимальное число, хранящееся в одном из регистров 2.

Происходит это следующим образом.

Алгоритм выбора минимального кода состоит в последовательном анализе параллельных разрядов И . кодовых ком.30 бинаций, записанных в регистрах 2, с последовательным выявлением больших по величинам кодов в параллельных (одноименных разрядах, начиная со старшего разряда вплоть до младшего. Причем анализ параллельных раз-З5 рядов кодовых комбинаций производится как дешифраторами 10, так и блоками 11 сравнения, но выявление кодовыхккомбинаций, меньших по величине, чем наибальшие, производится пер-40 вым деп?нфратором 104и блоками 11

11!и 4 сравнения, причем последний блок 11 п сравнения выявляет минимальные (одну или несколько) кодовые комбинации.

П р и.м е р. Пусть в регистрах

2 записаны коцовые комбинации:

Регистр 1 1 О 1 1, О 1

Регистр 2 ".0 О 1 1 .0 О

Регистр 3 О О О 1 1 О 50

Регистр 4 - О О 0 1 О 1

Регистр 5 l О О 1 О О

Регистр 6 О 0 1 1 1 О

Регистр 7. О О О 1 О 1

Регистр 8,1 О i О 0

Причем минимальные по величине кодовые комбинации хранятся в регистрах.

Сущность алгоритма работы устрои ства выбора минимального кода состоит в следующем. Возможны следующие события. Символы всех старших разрядов. могут быть равны единице, либо нулю, либо имеются символы, равные нулю и единице В первых двух случаях на выходах 43„-43" дешифратора 10 (фиг.6) должны быть единичные потенциалы, а в третьем случае единичные потенциалы должны быть на тех выходах 43— и

43, которые соответствуют по верхнему индексу регистрам 2, в старшие разряды которых записаны нулевые еим+ волы кодов. Для рассматриваемого случая единичный потенциал есть на выходах 43 43 434 43, 43, Действительно, потенциалы на выходах элементов И 40 и 41 равны нулю и на выходах элементов VJIH 4? q- 42 я есть потенциалы, определяемые потенциалами снимаемыми с прямых входов

38 - 38 дешифратора 10,!. Значения

1 и фуйкций, снимаемых с выходов 43 — 43я, дешифраторов 10, запишем в табл. l.

Таким образом первый дешифратор

10!состояний выделяет номера регистров 2, в которых хранятся меньшие кодовые комбинации. Однако из табл.l следует, что дешифратор 10 подобную. функцию уже не выполняет. В этом случае блоки сравнения 11! -II q выде ляют регистры с минимальными кодовыми комбинациями.

Работу блоков Il сравнения проследим для примера восьми регистров сопласно логическим функциям, значения которых сведены в табл.2, причем значение функции, определяющее состоя; ние J -го блока, находится на пересечении 1 -го столбца и -ой .строки соответствующего раздела табл.2.

Hs табл,2 видно, что единичные потенциалы имеются на выходах 54< и 547

Д сблока 11 сравнения и тем самым выделяют номера регистров 24. и 27, в которых находятся минимальные кодовые комбинации.

Пусть согласно примеру (фиг.8) имеется пять регистров 2, в которых записаны кодовые комбинации: минимальная Х1 в регистре 22, следующая по величине Х в регистре 2г, следующая по величине Х в регистре 2, равная Х кодовая комбинация Х,1 в регистре 24 и наибольшая по величине X — в регистре 21.

Пб первому импульсу генератора 15 сбросится счетчик 23 блока 7 выявле ления код Хg регистра 2» записывается в регистр 12у.I

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

13 в результате имеются коды двоичных чисел, упорядоченные по мере их возрастания.

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

:выходных регистров экстремальные

I числа.

10499 ния равных чисел и разрешается подача чисел регистров 2 на блоки 11 и дешифраторы 10, которая выявит, как описано, что минимальный код Х„1 записан в регистре 2у и на втором выходе 54я блока l l < сравнения имеется потенциал, поданный на соответствукиций вход 25 коммутатора 9 и на второй вход 25 блока выявления равных чисел.,10

Блок 7 выявления равных чисел необходим для выявления одинаковых т по величине кодов, записанных в регйстры 2. Действительно, среди ко-. дов регистров 2 может быть.два или несколько одинаковых чисел, причем в выходных регистрах 12 они должны быть записаны все. В реверсивный счетчик 23 каждый раз, после сброса в нулевое состояние по выходу 19 по его вторым входам от выходов кодопреобразователя 24 записывается в двоичном счислении число, равное ко- личеству одинаковых минимальных ко- . дов, выявляемых на данном такте. 25

Кодообразователь 24 строится, ис- --. ходя из соображений. Допустим, у нас имеется пять регистров 2. Тогда сос- тояние выходов 54 блока 11 я4сравнения сводим .в табл.3.

Так как на первом также выявлен минимальный код Х4 и равных ему,больше нет, кодопреобразователь 24 записывает в реверсивный счетчик 23 код;.

001, т.е. единицу в десятичном счислении.

35.

Через время, обусловленное элементом 20,задержки, сработает распределитель 21 и íà его первом выходе появится потенциал, который подается с третьего выхода 22 1 блока 5 управле" ния на первый вход коммутатора 9.

В коммутаторе 9 на первые входы

37 подаются коды регистров 2, но на втором входе 25 имеется разрешающий потенциал от блока 11 р„, который 45 . откроет элемент И 36 — 36 и код ф 1 регистра 22 подается через .элементы

ИЛИ 35 — 35п и открытые элементы И

331 — 33 (разрешающий потенцил на входе 22 коммутатора 9) подаются на Sg первые выходы 34 - 34 кожутатора

Ф

9, с которых запйсывается, в регистр

12.1.

Кроме этого, с вторых выходоЪ: подаются потенциалы на соответствую 55

00 12 щие вторые входи формирователя 8 сброса. На выходе элементов КПИ 31 индекс 1 — которого соответствует номеру 2 регистра, в котором хранится на данном такте работы устРойства минимальный код, имеется потенциал. Формирователь сигнала по заднему фронту импульса с вьпсода счетчика 23 блока 7 выдает сигнал, открывающий соответствующий элемент

И 29 . В рассматриваемом случае по1

J. тенциал есть на выходе элемента

И 29 . С выхода 30у формирователя

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

По второму импульсу генератора 15 блока 5 управления выявляют второй но величине от минимального код Х регистра 2д. По третьему импульсу rer нератора 15 выявляют два одинаковых минимальных числа Х регистра 29 и

Хф регистра 2 1. В этом случае на выходе кодопреобразователя 24 имеется код двойки, т, е. 010, и счетчик. сбрасывается четвертым импульсом генератора 15. Причем по третьему импульсу генератора 15, импульсом с третьего выхода 22 „код Х записывается во второй регистр 12>, а по четвертому импульсу генератора 15 код Х 1 записывается в регистр 124 . По пятому импульсу генератора 15 блока 5 управ!

Таблица

1049900 .

I

Выходы gl)l 10

Разряды регистра

Регистр

1 2 3 4 5 6

Ю» ЕГ Х

1 1 О

1 1 1

1 О 1

2 О О

3 О О 0

1 1 О

4 О О

1 I 1

1 О l

1 ) О

5 ) О О

6 О О

7 О

8 ) О

1: l 1

О

Та блица 2

Номера ре

Выходы схем сравнения

Разряды регистра

Выходы дешифратора

J Т

1 2 I

1 2 3 4 5 6

3 4 5 6 гистр ов 2..........1........

1 1 О 1 1 О l О. 1 О 1 1 00 О О 0 0

2 О О 1 1 О 0 1 1 О 1 1 1 1 О О О О

О 1 ) I 0 ) l 1 О О

3 О 0 О 1

1 1 1

4 О О О

1 I 1 1 1 О 1 1

1 О

5 1 О 0 1 0 0 О 1 1 1 1 10 О О О О

1 ) 1 О 1 1 О ) 0 1 1 О О О О

О 1 О 1 1 1 ) 1 1 01 1 1 Г 1

11000)0111000 00

6 О О

7 О О

8: 1 О

Таблица 3

Номера выходов блока 11

Выходы кодопреобразователя 24 1 1

0 О О О 1. 0 О 1

О 1

О О

О О

1 О О

О О

О 1 О

0 О 1

1 О 1

О 1 1

О О О

1. О. )

О 1 1

О О О

1 О

1 О

I 1

1 1

I 1

1049900, 0

0 1

0

1 0

0 0

0

0,0

0

0

0

0

) 1

0 1

0

0

0

Номера выходов блока )I

1 2 3 4 . 5

0 1 ,1 0

1 1

0 . 0

1 ° 0 0 - ) ) Продолжение табл. 3

Выходы кодопреобраэователя 24

1 2 ) 3

1049900

1049900

1049900

1049900!

049900 1049900

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

Техред А.Бабинец Корректор А. Првх

Редактор Н. Бобкова

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

Заказ 8427/46 Тираж 706 Подписное

ВНИИПИ. Государственного комитета СССР

:по делам изобретений и открытий

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