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

ЕЛЬСТ И с ЧИСЕЛтома- мо- твах рете- рабоГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТ ОПИСАНИК АВТОРСКОМ(71) Харьковский авиационный интут им. Н.Е.Жуковского(56) Авторское свидетельство ССУ 911513, кл. С 06 Р 7/06, 1980Авторское свидетельство СССРФ 1117631, кл, С 06 Р 7/06, 1983(57) Изобретение относится к автике и вычислительной технике ижет быть использовано в устройсдля сортировки чисел. Цель изобния - повышение быстродействияты устройства. Устройство содерж БРЕТЕНИЯ группу регистров 6, - 6 , схемы сравнения 7 - 7 п, триггеры 1- 1,группы 4, - 4элементов И, два счетчика 8, 9, регистр 5 результата, распределитель импульсов, выполненный в виде узла 2 выделения старшеМ единицы, формирователь адреса, выполненный на схеме постоянного запоминающего устройства 12, группу дополнительных регистров 10 - 10 п. В каждом такте производится сортировка сразу всех чисел массива, имеющих одинаковые значения, что позволяет увеличить быстродействие устройства, формирование отсортированного массива в дополнительных регистрах позволяет сохранить после сортировки исходный массив. 1 з.п. ф-лы, 1 табл., 2 ил.д5055 Изобретение относится к автоматике и вычислительной технике, а точнее к устройствам для сортировки чисел, и предназначено для упорядочения произвольных массивов чисел в системах обработки данных.Цель изобретения - повышение быстродействия.Сущность изобретения заключается в использовании дополнительных регистров, постоянного запоминающего устройства и быстродействующего узла выделения старшей единицы, причем в каждом гакте производится сортировка сразу всех чисел массива, имеющих одинаковые значения, вследствие чего длительность сортировки равнатактам, где К - количество различных значений чисел в сортируемом массиве, а процесс формирования сигналов на выходе постоянного запоминающего устройства, разрешающих запись анализируемого числа в соответствующие дополнительные регистры, предназначенные для хранения отсортированного массива, и процесс выдачи под управлением узла выделения старшей единицы следующего числа, подлежащего анализу, на информационные входы регистра результата совмещены во времени, что позволяет повысить быстродействие устройстваКроме того, формирование отсортированного массива в дополнительных регистрах исключает необходимость менять местами числа исходного массива в процессе сортировки и сохраняет после сортировки исходный массив, предоставляя возможность контроля отсортированного массива, что позволяет повысить надежность работы устройства так же, как и исключение из него большого числа элементов задержки.На фиг.1 изображена структурная схема устройства для сортировки чисел; на фиг.2 - схема узла выделения старшей единицы.Устройство содержит (см.фиг.1) триггеры 11 - 1, узел 2 выделения старшей единицы, элемент ИЛИ З,группы 4, - 4 элементов И, регистр 5 результата, регистры 6 - б, схемы 7 - 7 сравнения, счетчики 8 и 9, дополнительные регистры 10 - 10, элемент И 11, постоянное запоминающее устройство 12, вход 13 тактовых импульсов устройства и выход "Конец сортировки" 14 устройства. 5 10 15 20 25 30 35 40 45 Узел 2 выделения старшей единицы содержит (см.фиг.2) элементы ИЛИ-НЕ 15, - 15, элементы И 6- 1 б входы 17 - 17, подгруппы 18, - 18 входов 7 и выходы 19 - 19 .Каждый из и триггеров 1 представляет собой Т -триггер (т.е. синхронный Т-триггер с внутренней задержкой), срабатывающий по отрицательному перепаду напряжения на входе синхронизации: единица на информационном входе Т при этом вызывает переход триггера в противоположное состояние, при нуле на входе Т состояние триггера не меняется. Триггеры 1 предназначены для осведомления о тех числах массива, которые еще не участвовали в процессе сортировки, и перед началом сортировки устанавливаются в единичное состояние подачей сигнала на вход Б (не показано).Узел 2 выделения старшей единицы служит для быстрого выделения единичного сигнала, присутствующего на выходе триггера 1 с наименьшим номером, и блокировки единичных сигналов, поступающих с выходов всех остальных триггеров 1. При максимальном быстродействии (длительность срабатывания узла складывается из длительностей срабатывания элемента ИЛИ-НЕ и элемента И) такая организация структуры связей между входами 17 узла, элементами ИЛИ-НЕ 15 и элементами И 16 узла обеспечивает минимальные затраты оборудования при реализации узла.Элемент ИЛИ-НЕ 15 с номером Кз + И где Я = 1,2К, а 11 =0,1шз, имеет 11; +1 входов, элемент И 16 с номером К+ з имеет Б + 1 входов.Элемент ИЛИ 3 имеет и входов и предназначен для выработки нулевого сигнала "Конец сортировки" на выходе 14 устройства после анализа всех чисел массива, в результате чего запирается элемент И 11, что прекращает действие тактовых импульсов на устройство. Каждая из и групп 4 элементов И содержит ш двухвходовых элементов И, где ш - разрядность сортируемых чисел, и предназначена для подключения выхода одноименного регистра 6 к информационному входу регистра 5 результата при наличии единичного сигнала на управляющих входах элементов И.Выходы одноименных элементов И всех групп 4 объединяются по схеме монтажного ИЛИ, поэтому элементы И должны быть реализованы по схеме с открытым коллектором, а еще лучше по схеме с тремя состояниями.оРегистр 5 результата состоит из ш синхронных П-триггеров, срабатывающих по единичному уровню сигнала на входе синхронизации, и предназначен 10 для приема очередного анализируемого числа с приходом тактового импульса на вход синхронизации, для хранения этого числа в течение периода тактовых импульсов и для выдачи его на входы всех схем 7 сравнения и всех дополнительных регистров 10.Каждый из и регистров б состоит из ш синхронных Р-триггеров, срабатывающих по уровню сигнала на входе синхронизации, и служит для приема соответствующего числа, подлежащего сортировке (цепи приема не показаны), для хранения этого числа и выдачи его на входы одноименной схемы 725 сравнения и информационные входы элементов И одноименной группы 4.Каждая из и схем 7 сравнения реализуется стандартным образом и предназначена для сравнения двух ш-разрядных чисел и формирования на своих двух выходах сигналов "Меньше" и "Равно".Счетчик 8 служит для подсчета количества схем 7 сравнения, имеющих 35 единичные сигналы на выходах "Меньше") и реализуется стандартным образом.Счетчик 9 предназначен для подсчета количества схем 7 сравнения, имею 40 щих единичные сигналы на выходах "Равно", и реализуется стандартным образом.,Дополнительные регистры 10 служат для приема и хранения чисел отсорти 45 рованного массива. Каждый из и реги" стров 10 состоит из ш синхронных 0- триггеров, срабатывающих по уровню сигнала на входе синхронизации.Элемент И 11 имеет 2 входа и предназначен для блокировки тактовых импульсов, поступающих на вход 13 устройства, при формировании нулевого сигнала "Конец сортировки" на выходе элемента ИЛИ 3.Постоянное запоминающее устройство 12 представляет собой стандартное ПЗУ, имеющее 21 о 8 и 3+2 адресных входов, где квадратные скобки обозначают операцию выделения целой части числа, инверсный управляющий вход и и выходов. Выдача числа из ячейки ПЗУ с адресом, установленным на адресных входах, происходит при нулевом сигнале на управляющем входе, т.е. после окончания действия очередного,тактового импульса.Логика программирования ПЗУ проста. Пусть выходы счетчика 9 соединены соответственно с младшими адресными входами ПЗУ, а выходы счетчика 8 - со старшими адресными входами ПЗУ, т,е. полный адрес А, поступающий на ПЗУ, в старшей половине разрядов А несет информацию о количестве чисел в массиве, которые меньше анализируемого числа, а в младшей половине разрядов А - информацию о количестве чисел в массиве, равных по значению анализируемому числу. Тогда видно (сортировка массива ведется в порядке возрастания значений чисел), что анализируемое число должно занимать в отсортированном массиве (А,+ 1)-е место, а последующие А - 1 мест должны занимать числа,равные по значению анализируемому (в число А входит единица, которую дает анализНруемое число), т.е. анализируемое число должно быть записано во все дополнительные регистры 10, имеющие номера с (А + 1)-го по (А) + + А)-й включительно, а следовательно, в ячейку ПЗУ, имеющую адрес А, равный АА , необходимо записать единицы во все разряды с (А + 1)-го по (А + А-й включительно. Так, например, для случая, когда и равно трем и адреса А А- соответственно двухразрядные, имеем следующую таблицу программирования ПЗУ:-и разряд чик 8 подсчитывает косравнения, имеющих еГа выходах Меньшечто числа в соответсрах 6 меньше анализир личество схеминичные сигналыпоказывающие,вующих регистуемого числа, ат количество счетчик 9 подсчитыва 1-й разряд 01 1 0 Из 16 адресуемых ячеек ПЗУ информация заносится только в 6, чтоускоряет и облегчает программирование ПЗУ. Объясняется это тем, чтомногие адресные комбинации не являются рабочими, т,е. при работе устройства эти комбинации счетчиками 8 и 9не формируются. К нерабочим относятся те адреса, которые соответствуютА, равному нулю ,(так как в массивевсегда есть хотя бы одно число, равное анализируемому), а также те адреса, которые дают сумму А, + А,большую и,Устройство работает следующим образом.Перед началом работы триггеры 1устанавливаются в единичное состояние, а в регистры 6 заносятся сортируемые числа, после чего устройствоготово к сортировке чисел в порядкевозрастания.При подаче первого тактового импульса на вход 13 устройства он через элемент И 11, открытый единичнымсигналом с выхода элемента ИЛИ 3,проходит на управляющий вход регистра 5 результата, разрешая запись врегистр 5 числа, поступившего с выхода верхнего регистра 6 через группу4 элементов И, открытых единичнымсигналом с верхнего (первого) выходаузла 2 в то время, как на всех остальных выходах узла 2 будут нулевыесигналы, формируемые соответствующими элементами ИЛИ-НЕ 15, И 16 узла 2под воздействием старшей единицы наверхнем (первом) входе узла. Записанное в регистр 5 анализируемое числосравнивается со всеми сортируемымичислами в схемах 1 сравнения. Счетсхем сравнения, выдающих единичные сигналы на выходах "Равно". Двоичные коды с выходов счетчиков 8 и 9 поступают соответственно на старшие и " младшие адресные входы постоянного запоминающего устройства (ПЗУ) 12. В каждой ячейке ПЗУ, имеющей рабочий адрес, записаны единицы во все разряды с (г+1)-го по (г+1)-й включительно, где г равно значению двоичного числа, соответствующего старшей полонине адреса, а 1 равно значению двоичного числа, соответствующего младшей половине адреса, причем разрядность адреса равна 21 одп 3+2, где квадратные скобки обозначают операцию выделения целевой части числа. Например, при,п, равном 15, разрядность адреса ПЗУ равна 8, а в ячейку ПЗУ с адресом 00110100 записываются единицы во все разряды с четвертого по седьмой включительно (г=3, 1=4) .Большинство адресов ПЗУ являются нерабочими, т.е. в процессе работы устройства на адресных входах ПЗУ формироваться не могут что ускоряет и облегчает запись информапии в ПЗУ.По заднему фронту тактового импульса начинаются два параллельно протекающих процесса: процесс формирования на выходе ПЗУ единичных сигналов, разрешающих запись анализируемого числа в соответствующие дополнительные регистры 10, и процесс сброса соответствующих триггеров 1и выдачи под управлением узла 2 следующего числа, подлежащего анализу,на информационные входы регистра 5.Первый процесс начинается под воздействием нулевого разрешающего сигнала 5на управляющем входе ПЗУ и заканчивается фиксацией в соответствующихрегистрах 10 анализируемого числа,поступающего с выходов регистра 5.Второй процесс начинается со срабатывания (по отрицательному перепаду науправляющих входах) тех триггеров 1,на информационных (счетных) входахкоторых действуют единичные сигналыс выходов "Равно" соответствующихсхем 7 сравнения, в результате чегосбрасываются в нулевое состояние триггеры 1, соответствующие отсортированным в данном такте числам, Затем .узел 2 выделяет старшую единицу, при сутствующую на выходе триггера 1 снаименьшим номером, блокируя единицына выходах всех остальных триггеров1 путем формирования нулевых сигналовсоответствующими элементами ИЛИ-НЕ15 узла 2. Выделенная узлом 2 старшая единица подключает выходы соответствующего регистра 6 через соответ.ствующую группу 4 элементов И к информационным входам регистра 5,нанем и заканчивается второй процесс.С приходом второго тактового импульса на вход 13 устройства начинается второй такт работы устройства.При этом в регистр 5 записывается 35очередное анализируемое число и сравнивается с числами, хранящимися вовсех регистрах 6. Счетчики 8 и 9 подсчитывают количество схем 7 сравнения,имеющих единичные сигналы соответственно на выходах Меньше" и выходах"Равно", и выдают двоичные коды насоответствующие адресные входы ПЗУ 12.После окончания второго тактового импульса разрешается работа ПЗУ, кото- ф 5рое выдает на входы разрешения записи регистров 1 О, номера которых соответствуют показаниям счетчиков 8 и9, единичные сигналы и обеспечиваеттем самым фиксацию анализируемогочисла в соответствующих регистрах 10.К этому моменту заканчивается такжепроцесс сброса триггеров 1, соответствующих отсортированным во второмтакте числам., с выдачей под управлением узла 2 следующего числа, подлежащего анализу, на информационныевходы регистра 5,Дальнейшая работа устройства ана-,логична рассмотренной,После того, как устройство отработает 1 тактов, где Е - количество различных значений чисел в сортируемом массиве, в регистрах 10, начиная с первого, сформируется отсортированный в порядке возрастания массив чисел, причем после сброса в 1-мтакте последних триггеров 1 на выходе элемента ИЛИ 3 сформируется нулевой потенциал, поступающий на выход 14 устройства в качестве признака "Конец сортировки" и блокирующийподачу тактовых импульсов с входа 13устройства путем запирания элементаИ 11.Далее по внешнему запросу числаотсортированного массива выводятсяиз устройства.Для сортировки чисел в порядке убывания их значений необходимо в регистры 6 записать обратные коды чи - сел, а числа отсортированного массива считывать с инверсных выходов регистров 10.Формула изобретения1. Устройство для сортировки чисел, содержащее и регистров (и - количество чисел в сортируемом массиве), и схем сравнения, и групп элементов И, и триггеров, два счетчика, регистр результата, элемент И, элемент ИЛИ, распределитель импульсов и формирователь адреса, причем выход каждого -го регистра,где 1=1,2. и, соединен с первой группой входов д-й схемы сравнения и с первыми входами соответствующих эпементов И 1-й группы, выходы одноименных элементов И всех групп объединены и соединены с одноименными информационными входами регистра результата, выходы которого соединены с входами второй группы каждой схемы сравнения, 1-й выход рас: пределителя импульсов соединен с вторыми входами элементов И х-й группы, о т л и ч а ю щ е е с я тем, что, с целью повьппения быстродействия уст.-, ройства, распределитель импульсов выполнен в виде узла выделения старшей единицы, формирователь адреса выполнен в виде постоянного запоминающего устройства, в устройство введены и дополнительных регистров, при-ти изв.-по чем выходы "Меньшевсех схем сравнения соединены соответственно с входами первого счетчика, а выход "Равно"каждой схемы сравнения соединен с инФормационным входом соответствующего 5триггера и соответствующим входомвторого счетчика, выходы датчиков соединены соответственно с первой и второй группами адресных входов постоянного запоминающего устройства, каждыйх-й выход которого соединен с управляющим входом -го дополнительногорегистра, выход каждого -го триггера соединен с соответствующим входом элемента ИЛИ и с -м входом узла вь 1- деления старшей единицы, вход тактовых импульсов устройства соединен с первым входом элемента И, выход которого соединен с управляющим входом20 постоянного запоминающего устройства, управляющими входами всех триггеров и регистра результата, выходы которого соединены с информационными входами каждого дополнительного регистра, выход элемента ИЛИ является выходом "Конец сортировки" устройства и соединен с вторым входом элемента И,2, Устройство по п.1, о т л и ч аю щ е е с я тем, что узел выделения30 старшей единицы содержит иэлементов ИЛИ-НЕ и пэлементов И, причем элементы ИЛИ вразбиты на К под - групп, где К - целая часть числа О 3 1 О 1 2 п - 1,75 - 0,5, таким образом, что Б-я подгруппа Б=1,2. К включает ш,Б входов, где ш,Б равно К-Я+1+ " 1(Б-Р), где Р равно 0,5 К(К+3)-п+1,1(Б-Р) - единичная функция, равная 1 пои Б-Р больше нуля и равная 0 при Б-Р меньше нуля либо равном нулю,первый вход узла выделения старшей единицы соединен с его первым выходом, каждый с 1-й вход узла, где Ч=2,3. и, соединен с первым входом (Ч)-го элемента И узла, выход каждого элемента ИЛИ-НЕ узла выделения старшей единицы соединен с вторым входом одноименного элемента И узла выделения старшей единицы, выход каждого г-го элемента И, где г=1,2п, является (г+1)-м выходом узла выделения старшей единицы, каждый вход в каждой Б-й подгруппе элементов ИЛИНЕ узла, содержащий входы с номерами от Кз - го до (К з + ш з - 1)-го включи - тельно, где Кз равно (К+1 в 5-0,5 Б)Б - К+ +(Б-Р)(Б-Р), соединен с соответствующими входами одноименного и последующих элементов ИЛИ-НЕ узла выделения старшей единицы до (К +Я + тп - 1)-го включительно, а выход (К+шв )-го элемента ИЛИ-НЕ узла выделения старшей ециницы соединен с соответствующими входами (Кз + +г )-го и всех последующих элементов И узла выделения старшей единицы73 в