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

 

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ, содержащее распределитель лмпульсов , и регистров, п блоков сравнения , группы элементов И, счетчик, сумматор регистр результата, причем выходы разрядов каждого i-ro регистра , где , 2, ..., п, соединены с соответствующими информационными входами первой группы i-ro блока сравнения и i-и группы элементов И,выходы которых подключены к входам i-й группы регистра результата, выходы разрядов которого подключены к информационным входам второй группы всех блоков сравнения и к информационным входам выходных элементов И первой группы,выходы которых являются информационными выходами устройства, a управляющие входы первых выходных элементов И подключены к шине разрешения выдачи числа устройства и управляющим входам выходных элементов И второй группы, выходы которых являют ся выходами адреса блока памяти устройства , a информационные входы соединены с соответствующими выходами сумматора, входы первой группы которого соединены с входами задания адреса области памяти устройства a входы второй группы - с выходами разрядов счетчика, каяздый i-й выход распределителя импульсов подключен к управляющим входам элементов И i-й группы, отличающееся тем, что, с целью повышения достоверности записи массива путем исключения потерь информации при записи одинаковых чисел, в устройство введены п триггеров, п элементов И и п элементов ИЛИ, причем каждый i-й выход распределителя импульсов с единен с входом установки в единичное состояние i-ro триггера, выход которого подключен к первому входу i-ro элемента И, выход которого соединен с первым входом i-ro элемента ИЛИ, a второй вход - с выходом Равно блока сравнения, выход Меньше которого подключен к второму входу i-ro 00 элемента ИЛИ, выход которого-соединен с соответствующим входом счетчика.

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

СЮ ЛВМ«

РЕСПУБЛИК

gag С 06 F 7/06

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬПЪФ

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

Н АВТОРСНОМЫ СВИДЕТВЪСТВЗГ (21) 3579295/18-24 (22) 15.04.83 (46) 07.08.84. Бюл. В 29 (72) И.Б. Мичков (53) 681.325.5(088.8)

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

У 637810, кл. G 06 F 7/08, 1976.

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

9 911513, кл. С 06 F 7/06, 1980 (прототип). (54)(57) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ

ЧИСЕЛ, содержащее распределитель .импульсов, и регистров, и блоков сравнения, группы элементов И, счетчик, сумматор регистр результата, причем выходы разрядов каждого i-ro регистра, где i=1, 2, ..., и, соединены с соответствующими информационными входами первой группы i-го блока сравнения и 1-й группы элементов И,выходы которых подключены к входам i-й группы регистра результата, выходы разрядов которого подключены к иншормационным входам второй группы всех блоков сравнения и к информационным входам выходных элементов И первой группы, выходы которых являются информационными выходами устройства, а управляющие входы первых выходных элеt ментов И подключены к шине разреше.,SU.„11074 I8 . А ния выдачи числа устройства и-управляющим входам выходных элементов И второй группы, выходы которых являются выходами адреса блока памяти устройства, а информационные входы соединены с соответствующими выходами сумматора, входы первой группы которого соединены с входами задания ад реса области памяти устройства, а входы второй группы — с выходами разрядов счетчика, каждый i-й выход рас пределителя импульсов подключен к управляющим входам элементов И i-й группы, отличающееся тем, что, с целью повышения достоверности записи массива путем исключе- Е ния потерь информации при записи одинаковых чисел, в устройство введены п триггеров, п элементов И и и элементов ИЛИ, причем каждый i-й выход распределителя импульсов соеди- Я нен с входом установки в единичное .состояние i-ro триггера, выход которого подключен к первому входу i-ro элемента И, выход которого соединен с первым входом i-ro элемента ИЛИ, а второй вход — с выходом "Равно" блока сравнения, выход "Меньше" которого подключен к второму входу i-го элемента ИПИ, выход которого.соедиНен с соответствующим входом счетчика.

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

5 ,Известно устройство для сортировки 11исел, содержащее m регистров, выходы которых соединены с входами схем сравнения, другие вьжоды которых подключены к выходам регистра ре- 1О зультата, выходы схем сравнения соединены через переключатель с входами элемента ИЛИ, элементы И, триггер, узлы запрета и временной распределитель (1 J.

Недостатком этого устройства является низкое быстродействие.

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

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

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

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

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

118

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

Цель изобретения — безошибочное формирование упорядоченного массива чисел.

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

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

Устройство содержит распределитель 1 импульсов, и регистров 2, п схем 3 сравнения, регистр 4 результата, группы 5-6 элементов И, сумма1107118 тор 8, счетчик 9, входы 10 и 11 устройства, вход 12 управления устройства, выходы 13 и 14 устройства, п триггеров 15, и элементов И 16, п элементов ИЛИ 17. 5

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

В регистры 2 заносятся сортируемые числа, регистр 4 результата и триггеры 15 устанавливаются в нуль, а распределитель 1 импульсов — в исходное состояние (не показано). После этого устройство готово к сортировке чисел в порядке возрастания.

Затем на вход 10 устройства подается первый тактовых сигнал, по которому появляется сигнал на первом (верхнем) выходе распределителя импульсов. При этом верхний триггер

15 установится в единичное состояние, 1О сигнал с которого разрешает прохождение сигнала с выхода."Равно схемы 3 сравнения через элемент И 16 .

Также открывается группа 6 элементов И и число из верхнего регистра 2 перезаписывается в верхний регистр 4 результата. Это число сравнивается со всеми сортируемыми числами в схемах 3 сравнения. Если число в каком-либо регистре 2 меньше чиспа, - ® находящегося в регистре 4 результата, то на выходе Меньше соответствующей схемы 3 сравнения появляется сигнал, если числа равны, то сигнал появляется на выходе "Равно . Сигнал 35

II II с выхода Равно поступит через элементы И 16 и ИЛИ 17 на счетчик 9 только при наличии разрешающего сигнала с триггера 15, т.е. для чисел ранее сравниваемых со всеми (включая 40 число сравниваемое в текущем такте).

Счетчик 9 подсчитывает количество схем 3 сравнения, имеющих сигнал на своем выходе.

Таким образом, с выхода счетчика 45

9 на один иэ входов сумматора 8 подается код количества сортируемых чисел, меньших или равных (но ранее сравниваемых со всеми) числу, записанному в регистре 4 результата. На вто- 50 рой вход сумматора 8 подается уменьшенный на единицу код адреса области памяти, начиная с которого необхо-. димо разместить отсортированную информацию. Тогда адрес области памяти, по которому следует записать число, находящееся в регистре 4 результата, определяется соотношением (À яач 1) + где А„ — адрес области памяти, начиная с которого необходимо разместить отсортированные чиспа;

Й вЂ” число чисел, -меньших или равных, но ранее сравниваемых со всеми, числу, записанному в регистре результата.

Сумматор 8 вычисляет сумму (A

12 устройства число, находящееся в регистре 4 результата, записывается в запоминающее устройство по адресу, выдаваемому сумматором 8.

Второй такт работы устройства начинается с подачи второго тактового сигнала на вход 10 устройства. При этом появляется сигнал на втором выходе распределителя 1 импульсов, который устанавливает в единичное состояние соответствующий триггер 15.и открывает соответствующую группу эле ментов И, вследствие чего в регистр

4 результата перезаписывается число из регистра 2. Дальнейшая работа устройства аналогична рассмотренному.

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

Предлагаемое устройство обладает расширенными возможностями по сортировке чисел, т.е. позволяет безоши- бочно формировать отсортированный массив as любого произвольного масси1 ва чисел.

1107118

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

Редактор С. Патрукева Техред Ж. Кастелевич Корректор И Шулла

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

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

113035, Москва, 3-35, Раутская наб., д. 4/5

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