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

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано в устройствах для сортировки чисел. Цель изобретения - повышение быстродействия работы устройства. Устройство содержит группу регистров 6 - 6, схемы сравнения 7 триггеры 1 - 1р,группы 4 - 41 элементов И, два счетчика 8, 9, регистр 5 результата, распределитель импульсов, выполненный в виде узла 2 выделения старшел единицы , формирователь адреса, выполненный на схеме постоянного запоминающего устройства 12, группу дополнительных регистров Ю - 10. В каждом такте производится сортировка сразу всех чисел массива, имеющих одинаковые значения, что позволяет увеличить быстродействие устройства, формирование отсортированного массива в дополнительных регистрах позволяет сохранить после сортировки исходный массив. I з.п. ф-лы, 1 табл., 2 ил. /J (О (Л Г4 00 о СХ5 о со (риг.1

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

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

РЕСПУБЛИН (59 4 G 06 F 7/06

ВСP<

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4009724/24-24 (22) 16.01.86

1 (46) 5.05.87. Бюл. Ф 18 (71) Харьковский авиационный институт им. Н.Е.Жуковского (72) Ю.И.Ялинич, В.Ю.Ларченко, В.И.Хлестков и M.Ô.Õoëoäíûé (53) 681.325(088.8) (56) Авторское свидетельство СССР

N- 911513, кл. G 06 F 7/06, 1980.

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

Ф 1117631, кл. G 06 F 7/06,,1983. (54) .УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в устройствах для сортировки чисел. Цель изобретения — повышение быстродействия работы устройства. Устройство содержит

„„Я0„„13108ОЗ А1 группу регистров 6, — 6 „, схемы сравнения 7„ — 7п, триггеры 1„ — ln,ãðóïпы 4, — 4 „ элементов И, два счетчика 8, 9, регистр 5 результата, распределитель импульсов, выполненный в виде узла 2 выделения старшеМ единицы, формирователь адреса, выполненный на схеме постоянного запоминающего устройства 12, группу дополнительных регистров 10„ — 10 . В каждом такте производится сортировка сразу всех чисел массива, имеющих одинаковые значения, что позволяет увеличить быстродействие устройства, формирование отсортированного массива в дополнительных регистрах позволяет сохранить после сортировки исходный массив. 1 з.п. ф-лы, 1 табл., 2 ил.

1310803

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

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

Сущность изобретения заключается в использовании дополнительных регистров, постоянного запоминающего устройства и быстродействующего узла выделения старшей единицы, причем в каждоь гакте производится сортировка сразу всех чисел массива, имеющих одинаковые значения, вследствие чего длительность сортировки равна 1 тактам, где К вЂ” количество различных значений чисел в сортируемом массиве, а процесс формирования сигналов на выходе постоянного запоминающего устройства, разрешающих запись анализируемого числа в соответствующие дополнительные регистры, предназначенные для хранения отсортированного массива, и процесс выдачи под управлением узла выделения старшей единицы следующего числа, подлежащего анализу, на информационные входы регистра результата совмещены во времени, что позволяет повысить быстродействие устройства ° Кроме того, формирование отсортированного массива в дополнительных регистрах исключает необходимость менять местами числа исходного массива в процессе сортировки и сохраняет после сортировки исходный массив, предоставляя возможность контроля отсортированного массива, что позволяет повысить надежность работы устройства так же, как и исключение из него большого числа элементов задержки.

На фиг.l изображена структурная схема устройства для сортировки чисел; на фиг.2 — схема узла выделения старшей единицы.

Устройство содержит (см.фиг.l) триггеры 11 — 1„, узел 2 выделения старшей единицы, элемент ИЛИ З,группы 4, — 4„ элементов И, регистр 5 результата, регистры 6„ — 6„, схемы

7 — 7„ сравнения, счетчики 8 и 9, дополнительные регистры 10„ — 10„, элемент И ll, постоянное запоминающее устройство 12, вход 13 тактовых импульсов устройства и выход "Конец сортировки" 14 устройства.

f0

Узел 2 выделения старшей единицы содержит (см .фиг.2) элементы ИЛИ-НЕ ! 5, — l 5 „„> элементы И 6 „- 16,, входы 17„ — 17„, подгруппы 18, — 18„ входов !7 и выходы 19„ - 19 „.

Каждый из и триг.-.еров представляет собой Т -триггер (т.е. синхрон1 ный Т-триггер с внутренней задержкой), срабатывающий по отрицательному перепаду напряжения на входе синхронизации: единица на информационном входе Т при этом вызывает переход триггера в противоположное состояние, при нуле на входе Т состояние триггера не меняется. Триггеры 1 предназначены для осведомления о тех числах массива, которые еще не участвовали в процессе сортировки, и перед началом сортировки устанавливаются в единичное состояние подачей сигнала на вход S (не показано).

Узел 2 выделения старшей единицы служит для быстрого выделения единичного сигнала, присутствующего на выходе триггера 1 с наименьшим номером, и блокировки единичных сигналов, поступающих с выходов всех остальных триггеров 1. При максимальном быстродействии (длительность срабатывания узла складывается из длительностей срабатывания элемента ИЛИ-НЕ и элемента И) такая организация структуры связей между входами 17 узла, элементами ИЛИ-НЕ 15 и элементами И 16 узла обеспечивает минимальные затраты оборудования при реализации узла.Элемент ИЛИ-НЕ 15 с номером К + И где $ = 1,2,...,R, à Ws =0,1,,шs-1) имеет Из +1 входов, элемент И 16 с номером K<+ M> имеет S + 1 входов.

Элемент ИЛИ 3 имеет и входов и предназначен для выработки нулевого сигнала "Конец сортировки" на выходе

14 устройства после анализа всех чисел массива, в результате чего запирается элемент И 11, что прекращает действие тактовых импульсов на устройство.

Каждая из и групп 4 элементов И содержит ш двухвходовых элементов И, где ш — разрядность сортируемых чисел, и предназначена для подключения выхода одноименного регистра 6 к информационному входу регистра 5 результата при наличии единичного сигнала на управляющих входах элементов И.

1310803

Выходы одноименных элементов И всех групп 4 объединяются по схеме монтажного ИЛИ, поэтому элементы И должны быть реализованы по схеме с открытым коллектором, а еще лучше — 5 по схеме с тремя состояниями. о

Регистр 5 результата состоит из

m синхронных D-триггеров, срабатывающих по единичному уровню сигнала на входе синхронизации, и предназначен для приема очередного анализируемого числа с приходом тактового импульса на вход синхронизации, для хранения этого числа в течение периода тактовых импульсов и для выдачи его на входы всех схем 7 сравнения и всех дополнительных регистров 10.

Каждый из и регистров б состоит из m синхронных D-триггеров, срабатывающих по уровню сигнала на входе синхронизации, и служит для приема соответствующего числа, подлежащего сортировке (цепи приема не показаны), для хранения этого числа и выдачи

его на входы одноименной схемы 7

25 сравнения и информационные входы элементов И одноименной группы 4.

Каждая из п схем 7 сравнения реализуется стандартным образом и предназначена для сравнения двух ш — раз— рядных чисел и формирования на своих двух выходах сигналов "Меньше" и

"Равно".

Счетчик 8 служит для подсчета количества схем 7 сравнения, имеющих 35 единичные сигналы на выходах "Меньше"

) и реализуется стандартным образом.

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

"Равно", и реализуется стандартным образом. ,Дополнительные регистры 10 служат для приема и хранения чисел отсорти45 рованного массива. Каждый из и реги" стров 10 состоит из m синхронных Dтриггеров, срабатывающих по уровню сигнала на входе синхронизации.

Элемент И 11 имеет 2 входа и предназначен для блокировки тактовых импульсов, поступающих на вход 13 устройства, при формировании нулевого сигнала "Конец сортировки" на выходе элемента ИЛИ 3.

Постоянное запоминающее устройство 12 представляет собой стандартное

ПЗУ, имеющее 2 (1о8 и .1+2 адресных входов, где квадратные скобки обознаI чают операцию выделения целой части числа, инв ер сный управляющий вход и и выходов. Выдача числа из ячейки

ПЗУ с адресом, установленным на адресных входах, происходит при нулевом сигнале на управляющем входе, т.е. после окончания действия очередного,тактового импульса.

Логика программирования ПЗУ проста. Пусть выходы счетчика 9 соединены соответственно с младшими адресными входами ПЗУ, а выходы счетчика

8 — со старшими адресными входами

ПЗУ, т.е. полный адрес А, поступающий на ПЗУ, в старшей половине разрядов А„ несет информацию о количестве чисел в массиве, которые меньше анализируемого числа, а в младшей половине разрядов А — информацию о количестве чисел в массиве, равных по значению анализируемому числу.

Тогда видно (сортировка массива ведется в порядке возрастания значений чисел), что анализируемое число должно занимать в отсортированном массиве (A,+ 1)-е место, а последующие

А — 1 мест должны занимать числа,равные по значению анализируемому (в число А входит единица, которую дает анализНруемое число), т.е. анализируемое число должно быть записано во все дополнительные регистры 10, имеющие номера с (А„ + 1)-го по (А) +

+ A )-й включительно, а следовательно, в ячейку ПЗУ, имеющую адрес А, равный А„А, необходимо записать единицы во все разряды с (А„ + 1)-го по (A„ + А ))-й включительно. Так, например, для случая, когда и равно трем и адреса А,, А — соответственно двухразрядные, имеем следующую таблицу программирования ПЗУ:!

310803

О О О О О О О 1 1 1 1 1 1 1

О О О 1 I I 1 О О О О 1 1 1

) 1 О О 11 О О 1 1 О О 1 1

О 1 О 1 О 1 О 1 О 1 О 1 О 1 О 1

1 и разряд О 1 1 1 О О О О О О О О О О 0 О

2-й разряд 0 О 1 О 1 l О О О О О О О О О

3-й разряд О О О 1 О О 1 О О 1 О О О О О О

Из 16 адресуемых ячеек ПЗУ информация заносится только в 6, что ускоряет и облегчает программирование ПЗУ. Объясняется это тем, что многие адресные комбинации не являются рабочими, т.е. при работе устройства эти комбинации счетчиками 8 и 9 не формируются. К нерабочим относятся те адреса, которые соответствуют

А, равному нулю,(так как в массиве всегда есть хотя бы одно число, равное анализируемому), а также те адреса, которые дают сумму А, + А, большую и.

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

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

При подаче первого тактового импульса на вход 13 устройства он через элемент И 11, открытый единичным сигналом с выхода элемента ИЛИ 3, проходит на управляющий вход регистра 5 результата, разрешая запись в регистр 5 числа, поступившего с выхода верхнего регистра 6 через группу

4 элементов И, открытых единичным сигналом с верхнего (первого) выхода узла 2 в то время, как на всех остальных выходах узла 2 будут нулевые сигналы, формируемые соответствующими элементами ИЛИ-НЕ 15, И 16 узла 2 под воздействием старшей единицы на верхнем (первом) входе узла. Записанное в регистр 5 анализируемое число сравнивается со всеми сортируемыми числами в схемах 7 сравнения. Счетчик 8 подсчитывает количество схем сравнения, имеющих единичные сигналы

»а выходах Меньше, показывающие, что числа в соответствующих регистрах 6 меньше анализируемого числа, а счетчик 9 подсчитывает количество схем сравнения, выдающих единичные сигналы на выходах "Равно". Двоичные коды с выходов счетчиков 8 и 9 поступают соответственно на старшие и ". младшие адресные входы постоянного запоминающего устройства (ПЗУ) 12. В каждой ячейке ПЗУ, имеющей рабочий адрес, записаны единицы во все разряды с (г+1)-го по (г+1)-й включительно, где г равно значению двоичного числа, соответствующего старшей поло— вине адреса, а 1 равно значению двоичного числа, соответствующего младшей половине адреса, причем разрядность адреса равна 2 j logan 3+2, где квадратные скобки обозначают операцию выделения целевой части числа. Например, при .п равном 15, разрядность адреса ПЗУ равна 8, а в ячейку ПЗУ с адресом 00110100 записываются единицы во все разряды с четвертого по седьмой включительно (г=3, 1=4).Большинство адресов ПЗУ являются нерабочими, т.е. в процессе работы устройства на адресных входах ПЗУ формироваться не могут„ что ускоряет и облегчает запись информапии в ПЗУ.

По заднему фронту тактового импульса начинаются два параллельно протекающих процесса: процесс формирования на выходе ПЗУ единичных сигналов, разрешающих запись анализируемого числа в соответствующие дополнительные регистры 10, и процесс сброса соответствующих триггеров 1

1310803 и выдачи под управлением узла 2 следующего числа, подлежащего анализу, на информационные входы регистра 5.

Первый процесс начинается под воздействием нулевого разрешающего сигнала 5 на управляющем входе ПЗУ и заканчивается фиксацией в соответствующих регистрах 10 анализируемого числа, поступающего с выходов регистра 5.

Второй процесс начинается со срабаты- 10 вания (по отрицательному перепаду на управляющих входах) тех триггеров 1, на информационных (счетных) входах которых действуют единичные сигналы с выходов "Равно" соответствующих схем 7 сравнения, в результате чего сбрасываются в нулевое состояние триг. геры 1, соответствующие отсортированным в данном такте числам. Затем узел 2 выделяет старшую единицу, при-20 сутствующую на выходе триггера 1 с наименьшим номером, блокируя единицы на выходах всех остальных триггеров

1 путем формирования нулевых сигналов соответствующими элементами ИЛИ-НЕ

15 узла 2. Выделенная узлом 2 старшая единица подключает выходы соответствующего регистра 6 через соответствующую группу 4 элементов И к информационным входам регистра 5, на нем и заканчивается второй процесс.

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

При этом в регистр 5 записывается 35 очередное анализируемое число и сравнивается с числами, хранящимися во всех регистрах 6. Счетчики 8 и 9 подсчитывают количество схем 7 сравнения. имеющих единичные сигналы соответст- 40 венно на выходах "Меньше" и выходах

"Равно", и выдают двоичные коды на соответствующие адресные входы ПЗУ 12.

После окончания второго тактового импульса разрешается работа ПЗУ, которое выдает на входы разрешения записи регистров 10, номера которых соответствуют показаниям счетчиков 8 и

9, единичные сигналы и обеспечивает тем самым фиксацию анализируемого числа в соответствующих регистрах 10.

К этому моменту заканчивается также процесс сброса триггеров 1, соответствующих отсортированным во втором такте числам., с выдачей под управлением узла 2 следующего числа, подлежащего анализу, на информационные входы регистра 5.

Дальнейшая работа устройства ана-. логична рассмотренной.

После того, как устройство отработает k тактов,,где k — - количество различных значений чисел в сортируемом массиве, в регистрах 10, начиная с первого, сформируется отсортированный в порядке возрастания массив чисел, причем после сброса в k-м такте последних триггеров 1 на вы— ходе элемента ИЛИ 3 сформируется нулевой потенциал, поступающий на выход 14 устройства в качестве признака "Конец сортировки" и блокирующий подачу тактовых импульсов с входа 13 устройства путем запирания элемента

И 11.

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

Для сортировки чисел в порядке убывания их значений необходимо в регистры 6 записать обратные коды чи— сел, а числа отсортированного массива считывать с инверсных выходов регистров 10. формула изобретения

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

3108

4 т 19m 1

m1 !9т i1

19м, 196

@ my-1

19>

Фин Z

ВНИИПИ Заказ 1891/44 Тираж б73

Подписное

Произв. — полигр. пр-тие, r. Ужгород, ул. Проектная, 4 чем выходы "Меньше всех схем сравнения соединены соответственно с входами первого счетчика, а выход "Равно" каждой схемы сравнения соединен с информационным входом соответствующего 5 триггера и соответствующим входом второго счетчика, выходы датчиков соединены соответственно с первой и второй группами адресных входов постоянного запоминающего устройства, каждый

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

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

"Конец сортировки" устройства и соединен с вторым входом элемента И.

2. Устройство по п.l, о т л и ч аю щ е е с я тем, что узел выделения

30 старшей единицы содержит и-1 элементов ИЛИ вЂ  и п-1 элементов И, причем элементы ИЛИ вЂ  разбиты на R под— групп, rye R — целая часть числа

03 l0 ! 2п — 1, 75 — О, 5, таким образом, что

S-я подгруппа $=1,2,...,R включает

m,$ входов, где m,$ равно R-$+1+

" 1($-P), где Р равно 0,5.R(R+3)-n+1, 11,($-P) — единичная функция, равная 1 пои S-P больше нуля и равная 0 при

$-P меньше нуля либо равном нулю,первый вход узла выделения старшей еди— ницы соединен с его первым выходом, каждый q-й вход узла, где q=2,3. ..n, соединен с первым входом (q-1)-ro элемента И узла, выход каждого элемента ИЛИ-HE узла выделения старшей единицы соединен с вторым входом одноименного элемента И узла выделения старшей единицы, выход каждого

r-ro элемента И, где r=1,2,...,n-l, является (г+1)-м выходом узла выделения старшей единицы, каждый вход в каждой S-й подгруппе элементов ИЛИНЕ узла, содержащий входы с номерами от KS — ro до (КЗ + гг. c — 1)-го включи— тельно, где К> равно Я+1,5-0,5S) S — R+

+(S-1 — Р) y ($-1-Р), соединен с соответствующими входами одноименного и последующих элементов ИЛИ-НЕ узла выделения старшей единицы до (К +

+ ш — 1)-го включительно, а выход (К +ш g †!)-го элемента ИЛИ-HE узла выделения старшей ециницы соединен с соответствующими входами (Кз +

+m 1-го и всех последующих элементов

И узла выделения старшей единицы. !

9в