Устройство для сортировки чисел Советский патент 1986 года по МПК G06F7/06 

-

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

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

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

Устройство содержит генератор 1 импульсов, счетчик 2, k блоков 3, -3 памяти, где 1 k m - разрядность сравниваемых чисел, коммутаторы 4 и 5, блоки 6 и 7 сложения с константой, блок 8 приоритета, элементы НЕ 9 и 10, РШИ 11, группу элементов И-ИЛИ 12, группу информационных входов 13, вход 14 разрешения записи, тактовый вход 15, входы 16 и 17 записи и считывания, группу выходов 18 отсортированных чисел.

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

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

. -/- rv

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

Затем на входе 14 устанавливается уровень 1, а на входах 16 и 17 - уровень 1 и О соответственно, при этом тактовые системы через коммутатор 4 поступают на вход, запись/ считывание блоков 3-3 памяти, задавая режим записи, а на управляющий вход коммутатора 5 поступает сигнал 1. В результате следующее число, поступившее по информационным входам. 13, записывается в счетчик 2, а по адресу, равноГ Ту этому числу, во всех блоках 3 - 3 памяти записывается 1

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

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

Блок 7j , j 1,2,..., (k-1) сложе- .ния константой производит сложение

77091

числа, записанного в счетчике 2 с числом J.. Поэтому из блока 7 памяти происходит считывание по адресу AJ+ +J-1, где Aj число, записанное в

е счетчике 2.

Сигналы о наличии в сортируемом массиве чисел в диапазоне -(A +k-} ) поступают с выходов блоков 3 - 3 памяти в блок 8 приоритета, где они

IQ по сигналам с генератора 1 импульсов выделяются в порядок возрастания,и при этом формируется сигнал на соответствующем выходе блока 8 приоритета. Этим сигналом открываются соотjc ветствующие элементы И элементов И-ИЛИ 12, и на выходе 18 устройства формируется код адреса, по которому бьта в некоторый блок 3 памяти записана 1, т.е. на выходах 18 выд деляются сами сортируемые числа.После вьзделения всех чисел в диапазоне A2-{A2+k-1) на всех выходах блока 8 приоритета - О, и на управляющий вход блока 6 сложения с константой

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

30

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

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

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

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

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

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

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

Составитель В. Горохов Техред и.Попович

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

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

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

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

Корректор Е. Рошко

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