Устройство для упорядочивания чисел

 

Изобретение относится к вычислительной технике и может исполь- , эоваться при построении с:истем сбора и обработки информации. изобретения является расширение области применения за счет обеспечения возможности фиксации равных чисел и запоминания упорядоченного массива, а также повышения быстродействия. Устройство содержит счетчик адреса, счетчик результата, m схем сравнения, где m - число упорядочиваемых чисел, блок обнаружения равных чисел, блок памяти, элементы И, ИЛИ, НЕ. Блок обнаружения равных чисел содержит формирователи импульсов, триггеры, элементы И, ИЛИ, ШШ-НЕ. Предлагае- ;мое устройство позволяет осуществить .запоминание упорядоченного массива чисел, вывод упорядоченного массива чисел в нарастающем либо в у(Я гаающем порядке и запоминание равных чисел в массиве. 1 з.п. ф-лы,-,2 ил. (Л

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

РЕСПУБЛИК

А1 (19) (И) (51) 4 О 06 Р 7/08

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21 ) 3832976/24-24 (22) 28,12.84 (46) 23.07.86. Бюл. У 27 (71) Ордена Ленина институт киберне- .тики им. В. М. Глушкова (72) В. П. Боюн, В. А. Жук и А. А. Столяров (53) 681.325(088.8) (56) Авторское свидетельство СССР

У 463968, кл. G 06 F 7/08, 1972.

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

В 637810, кл, G 06 F 7/08, 1976. (54) УСТРОЙСТВО ДЛЯ УПОРЯДОЧИВАНИЯ

ЧИСЕЛ (57) Изобретение относится к вычислительной технике и может использоваться при построении систем сбора и обработки информации, Целью изобретения является расширение области применения за счет обеспечения возможности фиксации равных чисел и запоминания упорядоченного массива, а также повышения быстродействия. Устройство содержит счетчик адреса, счетчик результата, m схем сравнения, где m — число упорядочиваемых чисел, блок обнаружения равных чисел, блок памяти, элементы И, ИЛИ, НЕ. Блок обнаружения равных чисел содержит формирователи импульсов, триггеры, элементы И, ИЛИ, ИЛИ-НЕ. Предлагае мое устройство позволяет осуществить ,запоминание упорядоченного массива чисел, вывод упорядоченного массива ф чисел в нарастающем либо в убывающем порядке и запоминание равных чисел в массиве. l з,п. ф-лы,;2 ил. С:

1 l2

Изобретение относится к вычислительной технике и может использовать. ся при построении систем сбора и об работки информации.

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

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

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

Блок 7 обнаружения равных чисел (фиг, 2) содержит тактовый вход 17, информационные входы 18-1-18-ш, формирователи 19-1-19-m импульсов, триггеры 20-1-20-m группы элементов И 21-1-21-m 22-1-22-(m-l), элемент ИЛИ 23, элемент ИЛИ-НЕ 24, второй 25 и первый 26 выходы связи.

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

На тактовый вход I подается последовательность тактовых импульсов, а на вход 3 задания режима нулевой потенциал, обеспечивающий перевод . блока 9 памяти в режим записи входных кодов, закрывающий второй элемент И ll и через элемент НЕ 13, открывающий третий элемент И 12. На информационные входы 4-1-4-m устрой. ства поступают числа, которые необходимо упорядочить. С окончанием импульса на установочном входе 2 устройства оно готово к работе, при этом на выходе 26 блока 7 обнаружения разных чисел устанавливается единичный потенциал, так как все его триггеры 20-l-20-m находятся в нуле вом состоянии.

Выходной единичный потенциал с выхода 26 блока 7 обнаружения равных чисел разрешает прохождение тактовых импульсов с так" îâîãî входа 1 устройства через первый элемент И 10 на тактовый вход счетчика 5 резуль46089 2

5 I0

2S

45 IÎ

55 тата. С приходом каждого тактовогo импульса «а его вход содержимое счетчика 5 результата увеличивается на единицу, а состояние других элеме«тов не изменяется до тех пор, пока не установится число на выходе счетчика 5 результата, равное меньшему из чисел, поступивших на информационные входы устройства, С наступлением этого момента на выходе соответствующей схемъ| 6 сравнения устанавливается единичный потенциал, обеспечивающий через формирователь 19 импульсов (фиг. 2) перевод соответствующего триггера 20 в единичное состояние. При этом на выходе элемента ИЛИ-НЕ 24 устанавливается нулевой потенциал, запрещающий прохож- дение импульсов через первый элемент И 10, а тактовый импульс в блоке 7 обнаружения равных чисел обеспечивает выделение одного импульса на выходе 25 блока 7 обнаружения равных чисел через открытый соответствующим триггером 20 элемент И 21 и элемент ИЛИ 23 и одновременно сброс. триггера 20 в нулевое состояние и установку единичного потенциала на выходе элемента ИЛИ-НЕ 24.

Импульс с выхода 25 блока 7 обнаружения равных чисел, пройдя через открытый третий элемент И 12 и элемент ИЛИ 14 на вход счетчика 8 адреса„ устанавливает на его выходах первое значение адреса. Этот же импульс, пройдя через элемент 15 задержки, осуществляет запись минимального числа с выхода счетчика 5 результата по адресу, установленному на выходах счетчика 8 адреса.

Время задержки элемента l5 задержки должно выбираться из условия > „ +

f1

"нл ли Сч9 где Ф.„ — время задержки элемента И 12; „„„л4- ВРЕМЯ ЗаДЕРжКИ ЭЛЕМЕНта ИЛИ 14; — максимальное время задержки счетчика 8 адреса, Далее устройство работает а«алогично„ осуществляя запись по следуь.:" щим адресам все нарастающих ч;.сел вплсть до максимального числа во входном массиве.

Таким образом, на выходах счетчика 5 результата могут быть выделе«ы в нарастающем порядке все числа из входной последовательности. Наличие того или иного числа «одтверждает

3 1? импульс на выходе 25 блока 7 обнаружения равных чисел, Эти числа записываются н блок 9 памяти по нарастающим адресам, начиная с первого адреса, и в случае необходимости могут быть многократно считаны. Для этого необходимо подать единичный сигнал на вход 3 устройства, который переведет блок 9 памяти в режим Считывание, и установить счетчик 8 адреса в нулевое состояние подачей импульса на установочный вход 2 устройства. С подачей каждого тактового импульса на вход 1 устройства счетчик 8 адреса устанавливает последующее значение адреса на адресных входах блока 9 памяти, на выходах которого проявляются числа входного массива в нарас" тающем порядке.

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

В случае, если входной массив содержит R равных чисел, устройство работает следующим образом. С установкой на выходе счетчика 5 результата числа, равного R одинаковым числам, на выходах R схем 6 сравнения устанавливается единичный потен циал, который обеспечивает установку в единичное состояние R триггеров 20 блока 7 обнаружения равных чисел. Элемент ИЛИ-НЕ 24 запрещает прохождение тактовых импульсов через первый элемент И 10 на вход счетчика 5 результата, на выходах которого установлено значение равных чисел. С приходом каждого из последующих тактовых импульсов на вход блока 7 обнаружения равных чисел один иэ его триггеров 20 устанавливается в нулевое состояние, при этом на выходе 25 блока 7 выделяется один импульс, обеспечинающий установку нового значения адреса и запись кода с выхода счетчика 5 результата по каждому значению адреса. С установкой каждого из предыдущих триггеров в нулевое состояние единичным потенциалом с его инверсного выхода разрешается прохождение тактовых импульсов через элемент И 21 на последующие элементы И 21 и 22, пока все равные числа не будут переписаны в блок 9 памяти по соответствующим ад46089 4 ресам. Элемент ИЛИ-HE 24 поддерживает нулевой потенциал на входе первого элемента И 10 до тех пор, пока все триггеры 20 не будут установлены

5 и нулевое состояние, Таким образом, предлагаемое устройство может осуществлять запоминание упорядоченного массива либо в нарастающем, либо н убывающем порядке и запоминание равных чисел в массиве.

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

1,- Устройство для упорядочивания

15 чисел* содержащее m схем сравнения где m — число упорядочиваемых чисел, первые группы входов которых соединены с входами упорядочиваемых чисел устройства, а вторые группы входов—

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

40 наличия числа - с.первым входом третьего элемента И и через элемент задержки — с входом записи блока памя-, ти, информационные входы которого соединены с выходами разрядов счет45 чика результата, счетный вход которого соединен с выходом первого эле1мента И, а адресный вход блока памяти соединен с выходом счетчика адреса, счетный вход которого соединен с вы о ходом элемента ИЛИ, входы которого соедииены с выходами второго и третьего элементов И, вход считывания блока памяти соединен с входом задания режима устройства, с вторым вхо55 дом второго элемента Ии через элемент НŠ— с вторым входом третьего элемента И, вход начальной установки счетчика адреса соединен с установочным нхо2. Устройство по п. 1, о т л и— ч а ю щ е е с я тем, что блок обнаружения равных чисел содержит m формирователей импульсов, m триггеров, m элементов И первой группы и (m-1) элементов И второй группы, элемент ИЛИ и элемент ИЛИ-НЕ, i-й информационный вход. обнаружения равных чисел соединен череэ i-й формирователь (i=1-, m) импульсов с единичным установочным входом i-ro триггера, прямой выход которого соединен с пер. вым входом i-ro элемента И . первой группы, выход которого соединен с входом установки в "О" i-го тригге5 1246089 Ь дом устройства, выходы блока памяти ра и подключен к х-му входу элеменявляются выходами устройства. та ИЛИ, выход которого является вы ходом наличия числа блока обнаружения равных чисел, прямые выходы всех

5 триггеров соединены с входами элемента ИЛИ-НЕ, выход которого является выходом отсутствия чисел блока обнаружения равных чисел, инверсный выход J-го триггера ()=1, 2,,m-1)

10 соединен с первым входом )-ro элемента И второй группы, выход которого соединен с вторым входом (+1)-ro элемента. И первой группы, вторые входы -х элементов И первой и второй

15 групп объединены, вторые входы первых элементов И первой и второй групп подключены к тактовому входу блока обнаружения равных чисел.

Составитель А. Александров

Редактор Н. Тупица Техред Э.Чижмар

Корректор И.Муска

Заказ 4000!41 Тираж 671

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, R-35, Раушская наб., д, 4/5

Подписное (1ронзводс.твенно-полиграфическое предприятие, г. ужгород, ул. Проектная, 4