УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ

Полезная модель относится к автоматике и вычислительной технике и может быть использована в составе вычислительных устройств и устройств обработки данных.
Известны устройства для быстрой сортировки чисел (см. кн. Шевкопляс Б.В. Микропроцессорные структуры. Инженерные решения. Справочник. - 2-е изд. перераб. и доп. - М.: Радио и связь, 1990. - 512 с. С.490-493), состоящие из устройств сравнения (или арифметическо-логических устройств), логических элементов и мультиплексоров и позволяющие осуществлять сортировку максимум четырех чисел.
Недостаток подобных устройств состоит в резком росте аппаратных затрат (количества устройств сравнения) при увеличении количества сортируемых чисел, который обусловлен тем, что устройства реализуют все возможные комбинации сравнений сортируемых чисел. Кроме того, отсутствует возможность сортировки чисел в заданном диапозоне.
Известно устройство для сортировки чисел (см. пат.на изобр. №2246750 RU, 2003 г.), состоящее в том числе из n блоков анализа, каждый из которых состоит из логических элементов, схемы сравнения пары чисел и регистра и обеспечивающее сортировку чисел с попарным их сравнением.
Недостаток устройства - отсутствие возможности сортировки чисел в заданном диапозоне, а также зависимость количества n блоков анализа от количества сортируемых чисел, что увеличивает аппаратные затраты при увеличении количества сортируемых чисел.
Техническая задача: обеспечение сортировки чисел в заданном диапазоне, снижение количества функциональных блоков при сортировке большого количества чисел.
Технический результат: расширение функциональных возможностей устройства сортировки чисел и снижение аппаратных затрат. Он достигается тем, что устройство состоит из счетчика и одноразрядного оперативного запоминающего устройства. К входам параллельной загрузки данных счетчика подключена входная n-разрядная шина данных. Выходы данных счетчика соединены с адресными входами одноразрядного оперативного запоминающего устройства и выходной n-разрядной шиной данных. К входу сброса счетчика подключена линия подачи сигнала «сброс», к его инкрементирующему входу подключена линия подачи сигнала «счет на возрастание». К декрементирующему входу счетчика подключена линия подачи сигнала «счет на убывание». К входу разрешения параллельной загрузки счетчика подключена линия подачи сигнала «разрешение параллельной загрузки». Вход данных одноразрядного оперативного запоминающего устройства соединен с линией подачи сигнала «число для сортировки», его вход разрешения записи соединен с линией подачи сигнала «разрешение записи». Выход данных одноразрядного оперативного запоминающего устройства соединен с выходной линией «признак числа».
Предлагаемое устройство изображено на фиг.1.
Устройство сортировки чисел состоит из счетчика 1 и одноразрядного оперативного запоминающего устройства 2. К входам параллельной загрузки данных 5 счетчика 1 подключена входная n-разрядная шина данных 3. К входу сброса 6 счетчика 1 подключена линия
11 подачи сигнала «сброс», к инкрементирующему входу (добавляющему единицу) 7 счетчика 1 подключена линия 12 подачи сигнала «счет на возрастание», к декрементирующему входу (вычитающему единицу) 8 счетчика 1 подключена линия 13 подачи сигнала «счет на убывание». К входу разрешения параллельной загрузки 9 счетчика 1 подключена линия 14 подачи сигнала «разрешение параллельной загрузки». Выходы данных 10 счетчика 1 соединены выходной n-разрядной шиной данных 4 с адресными входами 17 одноразрядного оперативного запоминающего устройства 2. Вход данных 18 одноразрядного оперативного запоминающего устройства 2 соединен с линией 15 подачи сигнала «число для сортировки», вход разрешения записи 19 одноразрядного оперативного запоминающего устройства 2 соединен с линией 16 «разрешение записи». Выход данных 20 одноразрядного оперативного запоминающего устройства 2 соединен с выходной линией 21 «признак числа».
Устройство сортировки чисел имеет следующий алгоритм функционирования, предусматривающий четыре режима работы.
Режим обнуления. По линии 11 на вход сброса 6 счетчика 1 поступает сигнал «сброс» и устанавливает нулевое значение на выходах данных 10 счетчика 1, что приводит к установлению нулевого значения на выходной n-разрядной шине данных 4 и адресных входах 17 одноразрядного оперативного запоминающего устройства 2. На входе данных 18 одноразрядного оперативного запоминающего устройства 2 сигналом «число для сортировки» с линии 15 подается значение логического нуля, а на вход разрешения записи 19 по линии 16 подается сигнал «разрешение записи», тем самым разрешается запись в одноразрядное оперативное запоминающее устройство 2. Затем на линию 12 подается сигнал «счет на возрастание», в виде импульсов, который, поступает на инкрементирующий вход 7 счетчика 1, последовательно увеличивает значения на выходах данных 10 счетчика 1 и адресных входах 17 одноразрядного оперативного запоминающего устройства 2. Таким
образом, производится заполнение нулями одноразрядного оперативного запоминающего устройства 2.
Режим загрузки чисел. Сигналом «разрешение параллельной загрузки», поданным по линии 14 на вход разрешения параллельной загрузки 9, счетчик 1 переводится в режим параллельной загрузки. По входной n-разрядной шине данных 3 на входы параллельной загрузки данных 5 счетчика 1 подаются числа, предназначенные для сортировки. Одновременно числа оказываются на выходах данных 10 счетчика 1, выходной n-разрядной шине данных 4 и адресных входах 17 одноразрядного оперативного запоминающего устройства 2. По линии 15 на вход данных 18 одноразрядного оперативного запоминающего устройства подается сигнал «число для сортировки» в форме логической единицы, по линии 16 на вход разрешения записи 19 также подается сигнал «разрешение записи», тем самым, разрешается запись логической единицы в одноразрядное оперативное запоминающее устройство 2. Числа, предназначенные для сортировки, представляются единицами, записанными в одноразрядное оперативное запоминающее устройство 2 по адресам равным этим числам. По окончании режима загрузки сигнал «разрешение параллельной загрузки» с линии 14 снимается.
Режим сортировки чисел. На вход сброса 6 счетчика 1 по линии 11 подается сигнал «сброс». На линии 15 подачи сигнала «число для сортировки», входе данных 18, линии 16 подачи сигнала «разрешение записи» и входе разрешения записи 19 одноразрядного оперативного запоминающего устройства 2 устанавливается уровень логического нуля, тем самым одноразрядное оперативное запоминающее устройство 2 переводится в режим чтения. Затем на инкрементирующий вход 7 счетчика 1 по линии 12 подается сигнал «счет на возрастание» в виде импульсов, который заставляет счетчик 1 увеличивать значения на выходах данных 10, выходной n-разрядной шине данных 4 и адресных входах 17 одноразрядного оперативного запоминающего устройства 2. Так
производится последовательное считывание всех значений, записанных в режиме загрузки в одноразрядное оперативное запоминающее устройство 2. Как только на выходе данных 20 одноразрядного оперативного запоминающего устройства 2 обнаруживается единичное значение, оно подается на выходную линию 21 «признак числа» и является сигналом о том, что обнаружено очередное значение числа, предназначенного для сортировки, которое в данный момент присутствует на выходной n-разрядной шине данных 4. После полного цикла счета перебираются и выстраиваются в возрастающем порядке все значения чисел, предназначенных для сортировки.
Для сортировки чисел в убывающем порядке сигнал «счет на убывание» в виде последовательности импульсов подается на линию 13 и декрементирующий вход 8 счетчика 1.
Режим сортировки чисел в заданном диапазоне. Сигналом «разрешение параллельной загрузки», поданным по линии 14 на вход разрешения параллельной загрузки 9, счетчик 1 переводится в режим параллельной загрузки. По входной n-разрядной шине данных 3 на входы параллельной загрузки данных 5 счетчика 1 подается число - заданная граница диапазона. После записи границы диапазона в счетчик 1 сигнал «разрешение параллельной загрузки» с линии 14 снимается. Далее алгоритм аналогичен режиму сортировки чисел, с той разницей, что в цикле счета перебираются числа от границы диапазона, которая записана в счетчик 1 до необходимой границы. При сортировке в возрастающем порядке в счетчик 1 записывается нижняя граница диапазона и счет ведется до верхней границы, подачей соответствующего количества импульсов сигнала «счет на возрастание». При сортировке в убывающем порядке в счетчик 1 записывается верхняя граница диапазона и счет ведется до нижней границы, подачей соответствующего количества импульсов сигнала «счет на убывание».
m
m
В предлагаемом устройстве увеличение количества сортируемых чисел до m не приводит к увеличению количества функциональных блоков, а приводит лишь к наращиванию разрядности счетчика 1 до 2 и увеличению количества адресных входов, также до 2 одноразрядного оперативного запоминающего устройства 2.
Таким образом, предлагаемое устройство обеспечивает расширение функциональных возможностей, за счет сортировки чисел в заданном диапазоне, а также снижение аппаратных затрат при сортировке большого количества чисел.