Устройство упорядочивания массива чисел
Устройство упорядочивания массива чисел относится к автоматике и вычислительной технике и может быть использовано в составе вычислительных устройств и устройств обработки данных. Техническим результатом является расширение функциональных возможностей за счет подсчета количества одинаковых чисел в заданном диапазоне сортировки. Он достигается тем, что устройство состоит из первого счетчика, n-разрядного оперативного запоминающего устройства и второго счетчика. К входам параллельной загрузки данных первого счетчика подключена входная n-разрядная шина данных, выходы данных первого счетчика соединены с выходной n-разрядной шиной данных, которая соединена также с адресными входами оперативного запоминающего устройства. Входы данных оперативного запоминающего устройства соединены второй n-разрядной шиной данных «количество одинаковых чисел» с выходами данных второго счетчика. Выходы данных оперативного запоминающего устройства соединены с первой n-разрядной шиной данных «количество одинаковых чисел», а также с входами параллельной загрузки данных второго счетчика.
Полезная модель относится к автоматике и вычислительной технике и может использоваться в составе вычислительных устройств или устройств обработки данных.
Известно устройство для сортировки чисел (патент на полезную модель №60746), состоящая из счетчика и одноразрядного оперативного запоминающего устройства (ОЗУ).
Недостаток устройства состоит в том, что оно воспринимает два одинаковых числа как одно, что обусловлено наличием одноразрядного ОЗУ и неспособностью подсчитывать количество одинаковых чисел.
Техническая задача: обеспечение сортировки чисел в заданном диапазоне с возможностью подсчета количества одинаковых чисел.
Технический результат: расширение функциональных возможностей известного устройства сортировки чисел (патент на полезную модель №60746) за счет обеспечения возможности подсчета количества одинаковых чисел. Он достигается тем, что в известное устройство (патент на полезную модель №60746) добавлен дополнительно второй счетчик, кроме того, оперативное запоминающее устройство заменено на n-разрядное.
Предлагаемое устройство изображено на фиг.1.
Устройство упорядочивания массива чисел состоит из первого счетчика 1, n-разрядного (n-разрядность чисел для сортировки) оперативного запоминающего устройства 2 и второго счетчика 3. К входам параллельной загрузки данных 4 первого счетчика 1 подключена входная n-разрядная шина данных 18. К входу 5 сброса первого счетчика 1 подсоединена первая линия 19 подачи сигнала «сброс» первого счетчика, к
инкрементирующему (добавляющему единицу) входу 6 первого счетчика 1 подключена линия 20 подачи сигнала «счет на возрастание», к декрементирующему (вычитающему единицу) входу 7 первого счетчика 1 подключена линия 21 подачи сигнала «счет на убывание», к входу 8 разрешения параллельной загрузки данных первого счетчика 1 подсоединена линия 22 подачи сигнала «разрешение параллельной загрузки», выходы данных 9 первого счетчика 1 соединены с выходной n-разрядной шиной данных 28, которая соединена также с адресными входами 10 оперативного запоминающего устройства 2. Вход 12 разрешения записи в оперативное запоминающее устройство 2 соединен линией 23 подачи сигнала «разрешение записи в оперативное запоминающее устройство», входы данных 13 оперативного запоминающего устройства 2 соединены второй n-разрядной шиной 27 данных «количество одинаковых чисел» с выходами 17 данных второго счетчика 3. Выходы данных 11 оперативного запоминающего устройства 2 соединены с первой n-разрядной шиной 26 данных «количество одинаковых чисел», а также с входами 16 параллельной загрузки данных второго счетчика 3. К входу 14 сброса второго счетчика 3 подсоединена вторая линия 24 подачи сигнала «сброс» второго счетчика 3, к инкрементирующему (добавляющему единицу) входу 15 второго счетчика 3 подключена линия 25 подачи сигнала «добавление одинакового числа».
Устройство упорядочивания массива чисел имеет следующий алгоритм функционирования, имеющий четыре режима работы.
Режим обнуления. По первой линии 19 подачи сигнала «сброс» на вход 5 сброса первого счетчика 1 поступает сигнал «сброс» и устанавливает нулевое значение на выходах данных 9 первого счетчика 1, что приводит к установлению нулевых значений на выходной n-разрядной шине данных 28 и адресных входах 10 оперативного запоминающего устройства 2. Одновременно на вход 14 сброса второго счетчика 3 по второй линии 24 подачи сигнала «сброс» поступает сигнал «сброс»
второго счетчика 3, который устанавливает на выходах данных 17 второго счетчика 3 нулевые значения, подающиеся по второй n-разрядной шине данных 27 «количество одинаковых чисел» на входы данных 13 оперативного запоминающего устройства 2. На вход 12 разрешения записи оперативного запоминающего устройства 2 по линии 23 подачи сигнала «разрешение записи в оперативное запоминающее устройство» подается сигнал разрешения записи, тем самым, разрешая запись нулевых значений, установившихся на входах данных 13 оперативного запоминающего устройства 2 по адресу, установленному на адресных входах 10 оперативного запоминающего устройства 2. Затем на линию 20 подачи сигнала «счет на возрастание» подается сигнал в виде импульсов, который, поступает на инкрементирующий вход 6 первого счетчика 1, последовательно увеличивает значения на выходах данных 9 первого счетчика 1 и адресных входах 10 оперативного запоминающего устройства 2. Таким образом производится заполнение нулями n-разрядного оперативного запоминающего устройства 2 по всем адресам.
Режим загрузки чисел. Сигналом «разрешение параллельной загрузки», поданным по линии 22 подачи сигнала «разрешение параллельной загрузки» на вход 8 разрешения параллельной загрузки, первый счетчик 1 переводится в режим параллельной загрузки. По входной n-разрядной шине данных 18 на входы параллельной загрузки данных 4 первого счетчика 1 подаются числа, предназначенные для сортировки. Одновременно числа оказываются на выходах данных 9 первого счетчика 1 и адресных входах 10 оперативного запоминающего устройства 2. На выходах данных 11 оперативного запоминающего устройства 2 устанавливается значение данных, содержащееся в ячейке памяти оперативного запоминающего устройства 2, находящейся по адресу равному числу, предназначенному для сортировки. По первой n-разрядной шине 26 данных «количество одинаковых чисел» это значение подается на входы 16 параллельной загрузки данных второго счетчика 3 и фиксируется
в нем. Далее по линии 25 подачи сигнала «добавление одинакового числа» на инкрементирующий вход 15 второго счетчика 3 подается сигнал, заставляющий увеличить значение второго счетчика 3 на единицу. Это, увеличенное на единицу значение, устанавливается на выходах данных 17 второго счетчика 3, и по второй n-разрядной шине данных 27 «количество одинаковых чисел» поступает на входы данных 13 оперативного запоминающего устройства 2. Затем, сигналом «запись в оперативное запоминающее устройство» по линии 23 подачи сигнала «разрешение записи в оперативное запоминающее устройство» на вход 12 разрешения записи в оперативное запоминающее устройство 2, разрешается запись увеличенного на единицу значения количества одинаковых чисел по адресу, установленному на выходах данных 9 первого счетчика 1 и адресных входах 10 оперативного запоминающего устройства 2. Таким образом, числа, предназначенные для сортировки, представляются количествами одинаковых чисел, записанными в оперативное запоминающее устройство 2 по адресам равным сортируемым числам.
Режим сортировки чисел. На вход сброса 5 первого счетчика 1 по первой линии 19 подачи сигнала «сброс» подается сигнал «сброс», обнуляя значение первого счетчика 1. По линии 23 подачи сигнала «разрешение записи в оперативное запоминающее устройство» на вход 12 разрешения записи оперативного запоминающего устройства 2 подается сигнал, запрещающий запись в оперативное запоминающее устройство 2, переводя тем самым его в режим чтения. Затем для сортировки чисел в возрастающем порядке на инкрементирующий вход 6 первого счетчика 1 по линии 20 подачи сигнала «счет на возрастание» подается сигнал в виде импульсов, который заставляет первый счетчик 1 увеличивать значения на его выходах данных 9, выходной n-разрядной шине данных 28 и адресных входах 10 оперативного запоминающего устройства 2. Так, перебирая все возможные значения чисел на выходах данных 9 первого счетчика 1, производится последовательное чтение значений из оперативного
запоминающего устройства 2, занесенных в него в режиме загрузки чисел. Как только на выходах данных 11 оперативного запоминающего устройства 2 обнаруживается ненулевое значение (т.е., если хотя бы один разряд из n возможных не равен нулю), оно подается на первую n-разрядную шину 26 данных «количество одинаковых чисел» и является данными что, во-первых, обнаружено очередное значение числа, предназначенного для сортировки, которое в данный момент присутствует на выходной n-разрядной шине данных 28, и во-вторых, количество совпадающих (одинаковых) чисел равно значению, выставленному на первой n-разрядной шине 26 «количество одинаковых чисел». Например, если на выходной n-разрядной шине данных 28 присутствует значение «пять», а на первой n-разрядной шине 26 «количество одинаковых чисел» значение «три», то это означает, что обнаружено число для сортировки «пять» и количество одинаковых чисел «пять» равно трем. После полного цикла счета перебираются и выстраиваются в возрастающем порядке все значения чисел, предназначенных для сортировки, причем для повторяющихся (одинаковых) чисел известно сколько раз они повторяются, что позволяет различать одинаковые числа, в отличие от прототипа, где несколько одинаковых чисел будут приняты за одно число.
Для сортировки чисел в убывающем порядке сигнал «счет на убывание» в виде последовательности импульсов подается на линию 21 подачи сигнала «счет на убывание» и декрементирующий вход 7 первого счетчика 1. Далее алгоритм сортировки чисел в убывающем порядке аналогичен режиму сортировки чисел в возрастающем порядке.
Режим сортировки чисел в заданном диапазоне. Сигналом «разрешение параллельной загрузки», поданным по линии 22 подачи сигнала «разрешение параллельной загрузки» на вход 8 разрешения параллельной загрузки первого счетчика 1, первый счетчик 1 переводится в режим параллельной загрузки. По входной n-разрядной шине данных 18 на входы 4 параллельной загрузки данных первого счетчика 1 подается
число - заданная граница диапазона. После записи границы диапазона в первый счетчик 1 сигнал «разрешение параллельной загрузки» с линии 22 подачи сигнала «разрешение параллельной загрузки» снимается. Далее алгоритм сортировки чисел в заданном диапазоне аналогичен режиму сортировки чисел, с той разницей, что в цикле счета перебираются числа от границы диапазона, которая записана в первый счетчик 1 до необходимой границы, которая достигается подачей требуемого количества импульсов импульсного сигнала «счет на возрастание» по линии 20 подачи сигнала «счет на возрастание» на инкрементирующий вход 6 первого счетчика 1. При этом для сортировки в возрастающем порядке в первый счетчик 1 записывается нижняя граница диапазона, и счет ведется до верхней границы, подачей соответствующего количества импульсов сигнала «счет на возрастание». При сортировке в убывающем порядке в первый счетчик 1 записывается верхняя граница диапазона, и счет ведется до нижней границы, подачей соответствующего количества импульсов сигнала «счет на убывание»
В предлагаемом устройстве решена проблема устройства прототипа (патент на полезную модель №60746), заключающаяся в том, что два и более одинаковых числа устройство обрабатывает как одно число. При этом все режимы работы прототипа реализуются также и в предлагаемом устройстве.
Таким образом, предлагаемое устройство упорядочивания массива чисел обеспечивает расширение функциональных возможностей за счет подсчета количества одинаковых чисел в заданном диапазоне сортировки.
Устройство упорядочивания массива чисел, состоящее из первого счетчика, n-разрядного оперативного запоминающего устройства и второго счетчика, к входам параллельной загрузки данных первого счетчика подключена входная n-разрядная шина данных, к входу сброса первого счетчика подсоединена первая линия подачи сигнала «сброс» первого счетчика, к инкрементирующему входу первого счетчика подключена линия подачи сигнала «счет на возрастание», к декрементирующему входу первого счетчика подключена линия подачи сигнала «счет на убывание», к входу разрешения параллельной загрузки данных первого счетчика подсоединена линия подачи сигнала «разрешение параллельной загрузки», выходы данных первого счетчика соединены с выходной n-разрядной шиной данных, которая соединена также с адресными входами оперативного запоминающего устройства, вход разрешения записи в оперативное запоминающее устройство соединен линией подачи сигнала «разрешение записи в оперативное запоминающее устройство», входы данных оперативного запоминающего устройства соединены второй n-разрядной шиной данных «количество одинаковых чисел» с выходами данных второго счетчика, выходы данных оперативного запоминающего устройства соединены с первой n-разрядной шиной данных «количество одинаковых чисел», а также с входами параллельной загрузки данных второго счетчика, к входу сброса второго счетчика подсоединена вторая линия подачи сигнала «сброс» второго счетчика, к инкрементирующему входу второго счетчика подключена линия подачи сигнала «добавление одинакового числа».
