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

 

Изобретение относится к области автоматики и вычислительной техники. Цель изобретения - повьшение надежности . Устройство содержит генератор импульсов, счетчики, блок памяти (БП), триггер, коммутатор, элементы И, ИЛИ-НЕ, элементы запрета и задержки . Сортируемые числа записываются в БП в виде единичного значения ячейки с адресом, равным поступившему числу. Одновременно, если данное число встречалось ранее в сортируемом массиве, значение реверсивного счетчика (PC) увеличивается на единицу. При считывании, которое производится последовательно по всем ячeйкa, БП, значение в PC уменьшается на единицу при наличии единицы в данной ячейке БП. После окончания процесса сортировки в PC при отсутствии ошибок находится нулевое значение. 1 ил. ю

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

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

РЕСПУБЛИК (19) (И) (51) 4 С 06 F 7 06

ОПИСАНИЕ ИЗОБРЕТЕНИЯ (Н АВТОРСНОЬ У СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3876185/24-24 (22), 27.03.85 (46) 15. 12.86. Бюл. ¹ 46 (72) Е.Я. Ваврук (53) 681.325.5(088.8) (56) Авторское свидетельство СССР

I№ 1073770, кл. G 06 Р 7/06, 1982.

Авторское свидетельство СССР № 1183956, кл. G 06 F 7/06, 1984.,(54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к области автоматики и вычислительной техники.

Цель изобретения — повьппение надежности. Устройство содержит генератор импульсов, счетчики, блок памяти (БП), триггер, коммутатор, элементы

И, ИЛИ-НЕ, элементы запрета и задержки. Сортируемые числа записываются в

БП в виде единичного значения ячейки с адресом, равным поступившему числу. Одновременно, если данное число встречалось ранее в сортируемом массиве, значение реверсивного счетчика (РС) увеличивается на единицу.

При считывании, которое производится последовательно по всем ячейками, БП, значение в PC уменьшается на единицу при наличии единицы в данной ячейке БП. После окончания процесса сортировки в PC при отсутствии ошибок находится нулевое значение. 1 ил.

l 12770

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

Цель изобретения — повышение надежности, На чертеже изображена схема уст5 ройства.

Устройство содержит генератор 1 импульсов, счетчик 2, блок 3 памяти, коммутатор 4, элементы 5 и 6 запрета, реверсивный счетчик 7, триггер 8,элементы И 9, 10 и 11, ИЛИ 12, НЕ 13 и

14, элемент 15 задержки, группу информационных входов 16, вход 17 разрешения записи, вход 18 начальной установки, тактовый вход 19, входы 20 и

21 записи и считывания, вход 22 начала сортировки, группу информационных выходов 23 и выход 24 разрешения

1 считывания.

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

В режиме очистки памяти сигнал с входа- 18 начальной установки устанавливает счетчики 2 и 7 (не показано) в нулевое состояние. На входе 17 разрешения записи устанавливается "01, запрещающий запись в счетчик 2, на входах 20 и 21 — потенциал "0",разрешающий передачу через коммутатор

4, и элемент НЕ 13 импульсов с выхода генератора 1, на выходах элементов !

;6 и 7 запрета — нулевой уровень.После этого на вход 22 подается сигнал, который устанавливает триггер 8 в единичное состояние. Далее с генератора 1 на счетчик 2 поступает пачка из 2 импульсов, где m — количество разрядов счетчика 2. Одновременно та же инвертированная пачка импульсов через коммутатор 4 и элемент НЕ 13 поступает на вход записи/считывания блока 3 памяти, устанавливая его в режим записи. После полного пересчета счетчика 2 во всех ячейках блока

3 памяти записаны нули.

В режиме сортировки на входе 17 устанавливается потенциал "1", разрешая запись чисел в счетчик 2 с информационных входов 16. На входах 20 и 21 устанавливаются соответственно уровни "1" и "0", разрешая поступление на выход коммутатора 4 сигналов с тактового входа 19. В этом режиме на выходе элемента 5 запрета устанавливается единичный потенциал, на выходе элемента 6 запрета вЂ,нулевой потенциал. Сортируемый массив из п различных по величине m-разрядных

92 2 чисел (n (2"7 поступает на входы

16, записывается в счетчик 2 и с его выхода поступает на адресные входы блока 3 памяти. Синхронно с каждым числом на тактовый вход 19 поступает тактовый импульс, который через коммутатор 4 и элемент HE 13 поступает на вход записи/считывания блока 3 памяти. При этом сначала устанавливается режим чтения и, если состояние соответствующей ячейки памяти нулевое (т.е. поступившее число ранее не встречалось в сортируемом массиве), то через коммутатор 4,элемент 15 задержки и открытый элемент

И 9 тактовый импульс поступает на суммирующий вход реверсивного счетчика 7.

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

По окончании режима сортировки задается режим считывания.

На входах 17, 20 и 21 устанавливаются соответственно потенциалы

"0", "0" и "1", на выходе элемента

5 — нулевой уровень, на выходе элемента 6 — единичный уровень. На вход

22 поступает сигнал, снимающий установку триггера 8 в единичное состояние. На вход 18 начальной установки подается импульс, устанавливающий счетчик 2 в нулевое состояние. С генератора 1 поступает пачка из

2 -1 импульсов. При этом на выходе 24 формируется "1" в случае наличия в сортируемом массиве числа, значение которого в порядке возрастания установлено на выходах 23.

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

1 через коммутатор 4, элемент 15 задержки и открытый элемент И 10 поступает на вычитающий вход реверсивного счетчика 7, Если при этом счетчик окажется в нулевом состоянии, то задним фронтом сигнала с вь1хода элемента ИЛИ 12 триггер 8 устанавливается в нулевое состояние, чем вызывает прекращение поступпения импульсов на счетный вход счетчика 2.

Если количество считанных единиц больше количества сортируемых чисел, . триггер 8 устанавливается в нулевое состояние раньше окончания режима считывания. Если количество единиц меньше, после окончания режима считыСоставитель В. Горохов

Техред И.Попович Корректор А. Обручар

Редактор Е. Копча

Заказ 6667/42 Тираж 671 Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

3 12 вания на выходе элемента ИЛИ 12 устанавливается единичный уровень.

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

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

10 И, выходы которых соединены соответственно с суммирующим и вычитающим входами реверсивного счетчика, выходы разрядов которого соединены с соответствующими входами элемента ИЛИ, выход которого соединен с входом установки в нулевое состояние триггера, счетный вход счетчика подключен к выходу третьего элемента И, первый и второй входы которого подключены со2О ответственно к выходу генератора импульсов и к прямому выходу триггера, вход установки в единичное состоI яние которого является входом начала сортировки разрешения устройства, 25 выход считывания устройства соединен с выходом блока памяти, вторым входом первого элемента И и через второй элемент НЕ с вторым входом второго элемента И, выход коммутатора

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