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

11

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

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

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

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

Устройство содержит (см.фиг.1) триггеры Ц п узел 2 выделения старшей единицы, элемент ИЛИ 3,группы 4 4 элементов И, регистр 5 результата, регистры 6 б,,, схемы 7 - 7 сравнения, счетчики 8 и 9, дополнительные регистры 10 - 10, элемент И 11, постоянное запоминающее устройство 12, вход 13 тактовых импульсов устройства и выход Конец сортировки 14 устройства.

032

Узел 2 выделения старшей единицы содержит (см.фиг.2) элементы ИЛИ-НЕ 15, - 15jj, , элементы И 16 i - , входы 17 - 17„ , подгруппы 18 - 18

входов 17 и выходы 9 - 19,.

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

Уз.ел 2 выделения старшей единицы служит для быстрого выделения единич- ного сигнала, присутствующего на выходе триггера 1 с наименьшим номером, и блокировки единичных сигналов, поступающих с выходов всех остальных триггеров 1. При максимальном быстродействии (длительность срабатывания узла складывается из длительностей срабатывания элемента ИЛИ-НЕ и элемента И) такая организация структуры связей между входами 17 узла, элементами ИЛИ-НЕ 15 и элементами И 16 узла обеспечивает минимальные затраты оборудования при реализации узла.Элемент ЮТИ-НЕ 15 с номером К; + Wg, где S 1,2,...,R, а Wg 0,1,,..,ms-l, имеет Ws +1 входов, элемент И 16 с номером Kg+ Wg имеет S + 1 входов. Элемент ИЛИ 3 имеет п входов и предназначен для выработки нулевого сигнала Конец сортировки на выходе 14 устройства после анализа всех чисел массива, в результате чего запирается элемент И 1, что прекращает действие тактовых импульсов на устройство.

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

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

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

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

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

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

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

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

Элемент И I1 имеет 2 входа и предназначен для блокировки тактовых им

,

W

15

20

30

пульсов, поступающих на вход 13 уст7 ройства, при формировании нулевого сигнала Конец сортировки на выходе элемента ИЛИ 3.

Постоянное запоминающее устройство 12 представляет собой стандартное ПЗУ, имеющее +2 адресных входов, где квадратные скобки обознаг

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

Логика программирования ПЗУ проста . Пусть выходы счетчика 9 соединены соответственно с младшими адресными входами ПЗУ, а выходы счетчика 8 - со старшими адресными входами ПЗУ, т.е. полный адрес А, поступающий на ПЗУ, в старшей половине раз- р, рядов AI несет информацию р количестве чисел в массиве, которые меньше анализируемого числа, а в младшей половине разрядов А - информацию о количестве чисел в массиве, равных по значению анализируемому числу. Тогда видно (сортировка массива ведется в порядке возрастания значений чисел), что анализируемое число должно занимать в- отсортированном массиве (А,+ 1)-е место, а последующие Ag- 1 мест должны занимать числа,равные по значению анализируемому (в число AJ входит единица, которую дает анализ1 руемое число), т.е. ана- лизируемое число должно быть записано во все дополнительные регистры 10, имеющие номера с (А + 1)-го по (А +

- ТЭТУ rrtrtTTTTrri l г

35

40

45

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

и адреса А

-f

А,

двухразрядные,

соответственно имеем следующую таблицу программирования ПЗУ:

1-й разряд 01 1 1000000000000 2-й разряд 0011011000000000 3-й разряд 0001001001000000

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

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

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

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

5

0

5

0

5

0

5

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

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

71310803

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

8

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

После того, как устройство отработает k тактов, где k - количество различных значений чисел в сортируемом массиве, в регистрах 10, начиная с первого, сформируется отсортированный в порядке возрастания мас сив чисел, причем после сброса в k-м

f5

Второй процесс начинается со срабаты- 0 такте последних триггеров 1 на вы- вания (по отрицательному перепаду на ходе элемента ИЛИ 3 сформируется ну- управляющих входах) тех триггеров 1, на информационных (счетных) входах которых действуют единичные сигналы с выходов Равно соответствующих схем 7 сравнения, в результате чего сбрасываются в нулевое состояние триггеры 1, соответствующие отсортированным в данном такте числам. Затем -.

узел 2 выделяет старшую единицу, при-20 устройства сутствующую на выходе триггера 1 с наименьшим номером, блокируя единицы на выходах всех остальных триггеров 1 путем формирования нулевых сигналов соответствующими элементами ИЛИ-НЕ 15 узла 2. Выделенная узлом 2 старшая единица подключает выходы соответствующего регистра 6 через соответствующую группу 4 элементов И к ин30

25

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

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

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

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

сравнения. 40

формационным входам регистра 5, на нем и заканчивается второй процесс. С приходом второго тактового импульса на вход 13 устройства начинается второй такт работы устройства. При этом в регистр 5 записывается очередное анализируемое число и сравнивается с числами, хранящимися во всех регистрах 6. Счетчики 8 и 9 подсчитывают количество схем 7 имеющих единичные сигналы соответст венно на выходах Меньше и выходах Равно, и выдают двоичные коды на соответствующие адресные входы ПЗУ 12. После окончания второго тактового импульса разрешается работа ПЗУ, кото- рое выдает на входы разрешения записи регистров 10, номера которых соответствуют показаниям счетчиков 8 и 9, единичные сигналы и обеспечивает тем самым фиксацию анализируемого числа в соответствующих регистрах 10. К этому моменту заканчивается также процесс сброса триггеров 1, соответствующих отсортированным во втором такте числам, с выдачей под управлением узла 2 следующего числа, подлежащего анализу, на информационные входы регистра 5.

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

55

8

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

После того, как устройство отработает k тактов, где k - количество различных значений чисел в сортируемом массиве, в регистрах 10, начиная с первого, сформируется отсортированный в порядке возрастания массив чисел, причем после сброса в k-м

такте последних триггеров 1 на вы- ходе элемента ИЛИ 3 сформируется ну-

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

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

устройства

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

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

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

9 1310803

выходы Меньше всех схем сравне- 2п - соединены соответственно с входапервого счетчика, а выход Равно дой схемы сравнения соединен с инмационным входом соответствующего 5 ггера и соответствующим входом рого счетчика, выходы датчиков соеены соответственно с первой и втоS-я п т, S в

(5(S-P пои S S-P м вый в ницы ка/адьм соеди элеме мента едини ноиме ния с г-го являе ния с каждо НЕ узл от Kj тельн + (S-iветствпослед вгз1деле + Шд (Kg+Di выделе с соот )г И узла

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

2. Устройство по п.1, отличающееся тем, что узел выделения старшей единицы содержит п-1 элементов ИЛИ-НЕ и п-1 элементов И, причем элементы ИЛИ-НЕ разбиты на R подгрупп, где R - целая часть числа

;о

2п -

,75 - 0,5, таким образом, что S-я подгруппа ,2,..,,R включает т, S входов, где т,Я равно R-S+H

(57), где Р равно 0,5-R(R+3)-n+l , (S-P) - единичная функция, равная 1 пои S-P больше нуля и равная О при S-P меньше нуля либо равном нулю,первый вход узла выделения старшей единицы соединен с его первым выходом, ка/адьм q-й вход узла, где ,3,...,п, соединен с первым входом (q-l)-ro элемента И узла, выход каждого элемента ИЛИ-НЕ узла выделения старшей единицы соединен с вторым входом одноименного элемента И узла выделения старшей единицы, выход каждого г-го элемента И, где ,2,,..,п-1, является Сг+1)-м выходом узла выделения старшей единицы, каждый вход в каждой подгруппе элементов ИЛИ- НЕ узла, содержащий входы с номерами от Kj-ro до (Kg + )-ro включительно, где Kg равно (R+1,5-0,5S)S-R+ + (S-iP)-(2- (S-l-P), соединен с соответствующими входами одноименного и последующих элементов ИЛИ-НЕ узла вгз1деления старшей единицы до (К + + Шд 1)-го включительно, а выход (Kg+Di 5 -1)-го элемента РШИ-НЕ узла выделения старшей единицы соединен с соответствующими входами (Kg + )го и всех последующих элементов И узла выделения старшей единицы.

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