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

 

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

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

РЕСПУБЛИК

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

% (21) 4878075/24 (22) 25.10.90 (46) 07,02.93. Бюл. № 5 (71) Московский институт инженеров гражданской авиации (72) С,Ж.Кишенский, Н.С.Вдовиченко, С.В.Каменский и О,Ю«Христенко (56) Авторское свидетельство СССР

¹ 1291961, кл. G 06 F 7/02,-1985.

Авторское свидетельство СССР

N 1344214, кл. G 06 F 7/02, 1988. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к автоматике и вычислительной технике, Целью изобретеР2

„„Я2„„1793437 А1 (я)5 G 06 Е 7/02 ния является повышение быстродействия и достоверности работы и расширение области применения устройства за счет возможности сортировки нулевых чисел, Устройство содержит два дешифратора 2, 3, генератор импульсов 1, две группы элементов И 4 и 20, группу счетчиков 5, триггер 11, счетчик 12, регистры 9, 10, группы регистров

6, 7, блок выделения экстремума 8, элементов НЕ, И, ИЛИ-НЕ, задержки. Устройство позволяет осуществить сортировку максимум за 2 тактов работы, включая "нуль" как равноправное число в состав сортируемых чисел. 3 ил., 1 табл.

1793437

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

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

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

Недостатком прототипа является также низкая достоверность его работы.

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

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

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

ИЛИ второй группы.

Недостатком известного устройства, выбранного в качестве прототипа, является низкое быстродействие, Действительно, для сортировки чисел после введения массива по частостям устройству-прототипу требуется в общем слу35 чае до 2" циклов распределителя импульсов, причем каждый цикл распределителя, в свою очередь, требует 2 импульсов с генератора импульсов; таким образом, для надежного (для любой ситуации) про4О цесса — его завершения — сортировки чисел по частостям, прототипу требуется 2 тактовых импульсов, что крайне велико, Кроме того, прототип не позволяет до полного окончания сортировки чисел предыдущего

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

1793437

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

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

Кроме того, каждое устройство сравне30 ния содержит схему сравнения, три элемен35

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

55 2 — структурная схема устройства выделения экстремума; на фиг, 3 — структурная

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

ИЛИ-НЕ, а выход подключен к входу сброса триггера, выходы второго дешифратора соединены соответственно с входами элементов И второй группы, выходы которых подключены к входам сброса соответствующих регистров первой группы, Кроме того, устройство выделения экстремума содержит m групп по pi устройств сравнения в1-й группе, п1-разрядость чисел входного массива, i = 1m, pi = 2, причем первый и второй выходы j-го устройства сравнения первой группы соединены с выходами 2j-1-го и 2)-го регистров первой группы, третий и четвертый входы j-го устройства сравнения первой группы соединены.соответственно с выходами 2 -1-го и 2)-ro регистров второй групйы, j = 1,2, входы с гп-1 первого по четвертый с-го устоойства сравнения i-й группы, i = 2, m, k = 1,2, соединены соответственно с первыми выходами

2k-1-го и 2k-ro устройства сравнения i-1-й группы и со вторыми выходами 2k-1-ro u

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

На фиг. 1 приведена структурная схема схема устройства сравнения.

Устройстводля сортировки чисел содержит генератор импульсов 1, первый 2 и ВТо рой 3 дешифраторы, первую 1 группу

1793437 элементов И, группу.5 счетчиков, первую 6 группу регистров. вторую 7 группу регистров, блок 8 выделения экстремума, первый

9 и второй 10 регистры, триггер 11, счетчик

12, первый 13, второй 14 и третий 15 элементы И, элемент 16 ИЛИ-НЕ, первый 17, второй 18 и третий 19 элементы задержки, вторую 20 группу элементов И, элемент 21

НЕ, входы 22 разрядов чисел устройства, синхровход устройства 23. Входы 24 зада- ния длина массива. Выходы 25 и 26 являются информационными выходами устройства, Выход 27 второго элемента И 14 является управляющим выходом устройства и подключен к установочному входу триггера 11, и к входу элемента 17. Входы 28 регистров группы 7 являются установочными входами устройства. Выходы 29 регистров 7 и выходы 30 регистров 6 соединены соответственно с входами второй и первой групп блока 8. Выходы 31 блока 20 соединены с входами сброса соответствующих блоков 6, Блок выделения экстремума 8 содержит е групп по pi элементов сравнения.

Блок сравнения 32 содержит схему сравнения 33, первый 34 и второй 35 коммутаторы, первый 36, второй 37 и третий

38 элементы ИЛИ, элемент HE 39 и элемент 40 И.

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

Предварительно счетчики 5, регистры 6, триггер 11, регистры 9 и 10, счетчик 12 уста,новлены в нулевое состояние, Условно на чертежах цепи начальной установки не показаны. Перед началом работы в регистры

71 — 7 (n = 2 ), где m — разрядность входных двоичных чисел массива (заносятся двоичные коды соответственно от минимального до максимального значений числа; в регистр 71 — код числа "0", в регистр 72 — код числа "1", в регистр 7з — двоичный код числа

"2", и т,д., в регистр 7, — двоичный код числа

"n-1", Эти коды хранятся в регистрах 7 неизменными в течение всего времени работы устройства, В счетчике 12 по входам 24 заносятся разряды ожидаемого числа, соответствующего объему массива сортируемых двоичных чисел.

На фиг. 1 синхровходы, управляющие записью информации перед работой устройства в блоки 7 и 12 отдельно, не выделены в составе соответственно входам 28 и 24.

После занесения в счетчик 12 длины массива сортируемых чисел на входы 22 устройства начинают поступать двоичные ко.-ды сортируемых чисел, Каждое число массива сопровождается синхроимпульсом, поступающим на вход 23 с некоторым запаздыванием относительно сигналов числа (на входах 22); цель организации запаздывания — необходимость к моменту поступления синхроимпульса на вход 23 на5 личия сформированных сигналов на выходах дешифратора 2.

С приходом каждого сортируемого числа (от 0 до 2 -1) на соответствующем выходе дешифратора 2 появляется сигнал; дешиф10

50 ратор 2 преобразует двоичный код числа в позиционный код, где "единица" находится в позиции, номер которой равен значению кода поступившего числа. С приходом синхроимпульса появляется разрешающий сигнал на выходе элемента И 13 (по разрешающему положительному сигналу с выхода элемента НЕ 21 при отсутствии сигнала с выхода счетчика 12, который формируется счетчиком 12 при нулевом его содержимом} и через соответствующий элемент И 4 поступает с дешифратора 2 сигнал на счетный вход соответствующего счетчика

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

После окончания ввода массива с вводом последнего числа одновременно с записью его (увеличение на единицу соответствующего счетчика 5) сигналом с элемента 13 счетчик 12 устанавливается в нулевое состояние, в результате чего на его выходе появляется положительный потенциал, снимая положительный потенциал с входа элемента И 13 и тем самым запрещая прохождение синхроимпульсов на вход устройства. Этот же положительный сигнал с выхода счетчика поступает на элемент И 14 и, совпадая с. положительным сигналом с триггером (находящегося в нулевом состоянии), формирует сигнал на выходе элемента

И 14, который поступает на установочный вход триггера и устанавливает его в единичное состояние, поступает на управляющий выход устройства в виде короткого импульса, длительность которого ограничена временем срабатывания триггера 11, и сигнализирующего о воэможности (разрешении) ввода в устройство следующего массива чисел; этот же сигнал, поступая на синхровходы регистров 6, осуществляет перезапись содержимого счетчиков 5 в соответствующие регистра 6, а, пройдя с некоторой задержкой чисел первый элемент задержки 17, сбрасывает содержимое счетчиков 5 в "нуль", i793437

Таким образом, элементы 36 — 40 реали- 5 зуют логическую функцию:

С=(А=О) (А - О) (ВN О) (А> В)

При единичном значении функции "С" коммутатор 34 коммутирует на свои выходы вход В, при нулевом — вход А; коммутатор 5

35 соответственно коммутирует нэ свои вы- ходы значение того числа, частость которого поступает на выход коммутатора 34 (первый выход устройства сравнения), Таким образом, первая ступень устройства вновь подготавливается к приему следующего массива чисел (первая ступень устройства содержит блоки 2, 4, 5 и 6).

Положительный потенциал с триггера (с прямого выхода) после его переключения сигналом с элемента 14(поступает на управляющий вход генератора импульсов 1 и запускает его. Генератор импульсов формирует тактовые импульсы для второй ступени сортировки, содержащей блоки 3, 6-11, 15, 16, 18 — 20. Вторая ступень сортировки работает следующим образом.

Частости поступления чисел в данном массиве, записанные после окончания первого этапа сортировки на первой ступени в регистры 6, поступают на устройства сравнения устройства выделения экстремума 8 — нэ его первые входы. На вторые входы устройства сравнения 32 устройства 8 поступают коды чисел, которым соответствуют эти частости с регистров 7. Каждое устройство сравнения работает следующим образом.

В i-e устройство сравнения 32 первой ступени на первый вход поступает частость . чисел "2И" от регистра.62 -1, а на второй вход — частость числа "2i" от регистра 6гь

Обозначим эти частости соответственно "А" и "В". Они поступают на схему сравнения

33, с выхода которой формируется сигнал в том случае, когда А > В. На элементах ИЛИ

36 и 37 соответственно формируются положительные потенциалы в тех случаях, когда соответственно А О и В - О, Логика работы элементов 36 — 40 такова, что реализует приводимую таблицу;

Для первой и последней строк таблицы сигнал с выхода элемента 36 — нулевой, с выхода элемента 39 — единичный и с выхода элемента 38 — также единичный. Для второй строки таблицы сигнала с выходов блоков

33, 36 и 37 — единичные, соответственно, с выходов элементов 40 и 38 — также единичные. Для третьей строки — нулевые сигналы с выходов элементов 33, 40, 39 и 38; для четвертой строки — нулевые сигналы с выходов элементов 37, 38, 39 и 40.

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

его первый и второй вход, а на второ;1 выход

5 — код числа, имеющего эту частость появления в данном массиве. Естественно, что в том случае, когда одна из сравниваемых частостей равна нулю, на выход (в соответствии с вышеприведенной логической

10 функцией) коммутируется ненулевая частость, Если же обе частости равны нулю, на выход коммутируется частость В, однако в данном случае более важным является фактор коммутации на первый выход НУЛЕВО15 ГО кода частости; этот момент будет обсужден далее.

Сформированные попарно меньшие значения частостей по каждой паре из первой ступени устройства 8 поступают в его

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

Пирамидальное построение устройства

8 (фиг, 2) позволяет после срабатывания по25 следней, m-й ступени, выделить на выходе (первом) устройства 8 наименьшую ненулеау.o частость среди всех числе массива, а на втором выходе — число, значение которого имеет в данном массиве наименьшую нену30 левую частость. Эти значения формируются на выходах устройства 8 сразу (с естественной задержкой на m ступенях устройства 8) после занесения данных в регистры 6, Первый импульс с выхода генератора 1, 35 формирующийся через определенное время после поступления на его управляющий вход разрешающего сигнала с триггера 11 (время задержки первого импульса и период следования импульсов с выхода генератора

40 1 определяются задержкой срабатывания устройства 8 (всех его ступеней), осуществляет запись в регистры 9 и 10 соответственно значения числа с минимальной . . ненулевой частостью и значение его часто45 ты, Тактовый импульс задерживается на элементе 18 и поступает на первые входы элементов И 20 второй группы, На эти же элементы (на вторые входы, вернее — на один из них) поступает позиционный код

0 номера регистра 6, частость которого выведена в данном такте в регистр 40, преобразуясь дешифратором 3 из двоичного кода, записанного в регистре 9. Сигнал с соответствующего элемента 20 сбрасывает в нуль

5 значение частости выведенного в данном такте числа.

В следующем такте (к моменту формирования следующего тактового импульса) на выходах устройства выделения экстремума формируется следующая по порядку ми1793437

12 нимальная ненулевая частость и соответствующее ей число; процесс повторяется анаЛОГИЧНО. Таким образом, с каждым тактовым импульсом равномерно последовательно выводятся на выходы 25 и 26 устройства частости чисел и соответствующие им числа.

Если все частости (ненулевые) выведены, на очередном такте на выходах регистра

40 имеет место нулевой код, что вызывает появление единичного сигнала на выходе элемента 16 ИЛИ-НЕ; задержанный элементом 19 тактовый импульс поступает на второй вход элемента 15 и вызывает появление на его выходе импульса, устанавливающего триггер 11 в нулевое состояние. сигнализируя об окончании второго этапа сортировки чисел, то есть, полного окончания процесса сортировки чисел данного массива.

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

В начальном состоянии триггер 11 в нулевом состоянии, счетчик 12 — также; с выхода элемента 14 по сигналам (положительным) с инверсного выхода триггера и счетчика) — формируется на выход 27 сигнал разрешения ввода следующего массива (в начальном состоянии — первого), При введении первого массива снимается положительный сигнал с выхода счетчика (поло>кительный сигнал йа его выходе характеризует нулевое состояние счетчика),,-При окончании введения первого массива счетчик вновь устанавливается в нуль, на его выходе появляется положительный сигнал, происходит перезапись данных в регистры 6 — т.е. во вторую ступень сортировки, сброс счетчиков 5, выдача короткого разрешающего импульса на выход 27 и установка

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

1. Устройство для сортировки чисел, содержащее два дешифратора, генератор импульсов, две группы элементов И, группу счетчиков, триггер, счетчик, два элемента И и первый регистр, причем входы счетчика являются входами задания длины массива устройства, выход первого элемента И подключен к входу установки в "0" триггера, выходы первого регистра являются выходами числа устройства и соединаны с входами первого дешифратора, о т триггера 11 в единичное состояния, в результате чего на выходе 27 вновь устанавливается запрещающий сигнал, Короткий положительный импульс на выходе 27 уст5 ройства сигнализирует внешнему источнику о возможности ввода очередного (например, второго) массива чисел. Во время сортировки на второй ступени первого массива в первую ступень устройства может анало10 гичным образом вводиться и сортироваться второй массив чисел, Если длина второго массива меньше длины первогс, счетчик 12, устанавливаясь в нулевое состояние, не вызывает формирования импульсов на выходе

15 27 и элемента 14, так как регистры 6 заняты вторичной сортировкой чисел первого массива. После окончания второй ступени сортировки чисел первого массива триггер 11. устанавливается в нулевое состояние, и 20 лишь в этот момент формируется сигнал на выходе элемента 4, переписывающий рассортированные на первой ступени устройст- . ва числа из счетчиков 5 в регистры 6; процесс вторичной сортировки второго и

25 последующих массивов на второй ступени осуществляется аналогично.

Если длина второго массива больше длины первого, триггер 11 устанавливается в нулевое состояние раньше счетчика 12, но

30 импульс на выходе 27 элемента 14 появля-. ется в этом случает лишь после полной загрузки второго массива в первую ступень . устройства. Так осуществляется разделение массивов с возможностью одновременной

35 работы с разными массивами чисел íà первой и второй ступенях.

Сигнал об окончании полной сортировки массива (окончании работы второй ступени устройства) может быть снят-с выхода

40 элемента 15.

Если необходимо провести сортировку максимальными значениями частостей вперед, во всех устройствах 32 переключается выход "Больше" на выход "Меньше".

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

ИЛИ-НЕ, причем информационнь е входы разрядов чисел устройства соединены с входами второго дешифратор-":, выходы котороГо подключены к пер ым входам элементов

1793437

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

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

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

2. Устройство по и. 1, о т л и ч а ю щ е ес я тем, что блок выделения экстремума содержит m групп по pi блоков сравнения в i-й группе, где m — разрядность сортируемых чисел массива, (=1, m, р =2, входы блоков сравнения первой группы являются входами блока, входы с первого по четвертый -ro блока сравнения i-й группы, i = — 2, m, k = 1, 2 соединены соответственно с первыми выходами 2k-1-го и 2k-го блоков сравнения (i-1)-й группы и с вторыми выходами 2k-1-ro и 2k-го блоков сравнения (i-1)-й группы, выходы блока сравнения m-й группы являются выходами блока, : 3. Устройство по и. 1, о тлич а ю щеес я тем, что блок сравнения содержит схему сравнения, три элемента ИЛИ, два коммутатора, элемент И и элемент НЕ, причем первый и второй входы блока сравнения соединены соответствейно с входами первого и второго элементов ИЛИ, соответственно с входами первой и второй групп схемы сравнения и соответственно с информационными входами первой и второй групп первого коммутатора, выход которого является первым выходом блока сравнения, третий и четвертый входы блока сравнения соединены соответственно с информационными входами первой и второй групп второго коммутатора, выход которого является вторым выходом блока сравнения, выходы первого и второго элементов ИЛИ и схемы сравнения соединены с входами элемента

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

ixod

V, 3

Редактор С. Кулакова

Заказ 505 Тираж Подписное

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

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

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина, 101 (3 з

Составитель С, Кишенский

Техред M.Ìoðãåíòàë - Корректор С. Лисина