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

 

Изобретение относится к области автоматики и вычислительной техники. Цель изобретения - повьшение быстродействия . Устройство содержит генератор импульсов, коммутаторы,счетчик , блок приоритета, k блоков памяти (БП) и k блоков сложения с константой (БСК). После обнуления всех БП в них записываются единичные значения по адресам, равным сортируемым числам. После записи всех чисел происходит одновременное считывание из всех k БП по адресу (), j 1,2,..., k, А2 - адрес, задаваемый счетчиком, что обеспечивается БСК. При наличии в этом диапазоне нескольких сортируемых чисел сортировка среди них осуществляется блоком приоритета . После просмотра очередного диапазона происходит переход к следующему диапазону путем сложения А с константой k. 1 ил. с $ ю

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

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

РЕСПУБЛИН (292 (!2) (.522 4 (06 F 7 06

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

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

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

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

9 10?3770, кл. G 06 F 7/06, 1982.

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

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

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

БП в них записываются единичные значения по адресам, равным сортируемым числам. После записи всех чисел происходит одновременное считывание из всех k БП по адресу (A +j-1), j=

=1,2,..., k, А, — адрес, задаваемый счетчиком, что обеспечивается БСК.

При наличии в этом диапазоне нескольких сортируемых чисел сортировка среди них осуществляется блоком приоритета. После просмотра очередного диапазона происходит переход к следующему диапазону путем сложения А2 с константой k. 1 ил.

277091 а числа, записанного в счетчике 2 с числом j. Поэтому из блока 7 памяти происходит считывание по адресу A +

+j-1, где А, — число, записанное в счетчике 2.

Сигналы о наличии в сортируемом массиве чисел в диапазоне А, -(A +k-1) поступают с выходов блоков 3 — 3 пак мяти в блок 8 приоритета, где они по сигналам с генератора 1 импульсов выделяются в порядок возрастания,и при этом формируется сигнал на соответствующем выходе блока 8 приоритета. Этим сигналом открываются соответствующие элементы И элементов

И-ИЛИ 12, и на выходе 18 устройства формируется код адреса, по которому была в некоторый блок 3 — 3 памяти записана "1", т.е ° на выходах 18 выделяются сами сортируемые числа,После выделения всех чисел в диапазоне

А, †(A2 +k-1) на всех выходах блока

8 приоритета — "0", и на управляющий вход блока 6 сложения с константой поступает "i В результате в блоке

6 произойдет сложение А2 =А2 +k и далее будет осуществляться поиск и сортировка чисел в диапазоне А, -(А, +k-1).

J 1

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

Цель изобретения — повышение быстродействия устройства.

На чертеже изображена схема устройства.

Устройство содержит генератор 1 импульсов, счетчик 2, k блоков 3, -3 к памяти, где 1(k (2, ш — разрядность сравниваемых чисел, коммутаторы 4 и 5 блоки 6 и 7 — 7 сложеУ

К-t ния с константой, блок 8 приоритета, элементы НЕ 9 и 10, ИЛИ 11, группу элементов И-ИЛИ 12, группу информационных входов 13, вход 14 разрешения записи, тактовый вход 15, входы

16 и 17 записи и считывания, группу выходов 18 отсортированных чисел.

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

Перед началом работ производится очистка памяти: на входе 14 разрешения записи и входах 16 и 17 — "0".

Затем с генератора 1 на счетный вход счетчика 2 поступает пачка из 2 им- . пульсов. Одновременно через коммутатор 4 та же пачка импульсов, инвертированная элементом НЕ 9, поступает на вход записи/считывания всех блоков 3 - Зк памяти, задавая режим записи. После полного пересчета счетчиком 2 во всех ячейках блоков 3 — Зк памяти записаны нули.

Затем на входе 14 устанавливается уровень " 1", а на входах 16 и 17 уровень "1" и "0" соответственн при этом тактовые системы через коммутатор 4 поступают на вход запись/ считывание блоков 3 — 3 памяти за4О

1 К

У давая режим записи, а на управляющий вход коммутатора 5 поступает сигнал

" 1". В результате следующее число, поступившее по информационным входам

13, записывается в счетчик 2, а по адресу, равному этому числу, во всех блоках 3, — 3. памяти записывается

После этого происходит сортировка чисел.

На входах 14 и 17 устанавливается потенциал " 1", на входе 16 — потенциал "0". При этом на управляющем входе коммутатора 5 будет "0", а на входах запись/считывание блоков

31- 3 памяти тоже "0", задавая режйм считывания.

Блок 7„., „ = 1,2,..., (k-1) сложения константой производит сложение формула и э о б р е т е н и я

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

i-го разряда которого, где =1,2,..., m, m — разрядность сортируемых чисел, соединен с i-м адресным входом первого блока памяти, о т л и ч а ю щ е е— с я тем, что, с целью повышения быстродействия, в него введены блок приоритета, k блоков сложения с констан1 1 той, где 0 c k (2;, k-1 блоков памя1277Ñ

13

1Ф

1$

17

Составитель В. Горохов

Техред H.öoïîâè÷ Корректор Е. Рошко

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

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

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

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

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

i-га разряда сортируемого числа устройства соединен с 1-м информационным . входом первой группы второго коммута- IO тора, i-й выход которого соединен с информационным входом i-го разряда счетчика, выход i-ro разряда которого соединен с первым входом первого элемента i-ro элемента И-ИЛИ групп и 15 входами i-х разрядов блоков сложения с константой, выход i-ro разряда первого блока сложения с константой соединен с i-м информационным входом второй группы второго коммутато- 20 ра, выход i-го разряда j-ro блока сложения с константой, где j = 2,3,.

91 Ф соединен с i-м адресным входом j-го блока памяти и с первым входом j-го элемента И i-ro элемента

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

"Запись/считывание" которых подключены к выходу первого элемента НЕ.