Устройство для вычисления функций упорядоченного выбора Советский патент 1974 года по МПК G06F15/34 

I

Изобретение относится к автоматике и вычислительной тех.аике и может найти применение в операциовных устройствах систем автоматического управления и контроля, : Известно устройство для вычисления одI ной из функций упорядоченного выбора 1функции медианы, содержащее мажоритар;ный элемент со схемами И.ЛИ на входе, триггеры, инверторы, схемы И и схемы

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

Цель изобретения - повышение быстродействия вычисления любого К-го числа из 11роизвольного набора двоичных нисел.

; Для этого, предлагаемое устройство содержит элементы задержки, разрядные схемы выбора и регистры, выходы одноименных разрядов которых связаны с первыми (информационными входами соответствующих

схем сравнения и с соответствующими входами разрядной схемы выбора, выход каж-; дои из которых соединен с соответствующими вторыми информационными входами соответствующих схем сравнения, при этом выход равнозначности схемы сравнения каждого предыдущего разряда через элемент задержки связан с управляющим вхо дом схемы сравнения последующего разряда, а нулевые и единичные выходы этих схем через соответствующие схемы ИЛИ соединены соответственно с щинами установка соответствующего регистра в нулевое и единичное состояния, причем j управЛ5оощие входы схем сравнения старщих разрядов подключены к соответствующим управляющим входам устройства.

На чертеже представлена функциональна схема устройства.

Предлагаемое устройство содержит числовые регистры 1, выходы одноименных

.разрядов которых соединены :: первыми ннформадионными входами схем сравнения 2 и с входами разрядных схем выбега 3;

.схемы ИЛИ 4 установки чяс)повых региiCTpOB в нулевое состояние и схемы ИЛИ 5 установки числсв:ых регистров в единичное состояние, входьГкоторых связаны соответственно с нулевыми и единичными выходами схем сравнения; управляющие шины 6, соединенные с управляющими входами схем сравнения старщих разрядов, и элементы задержки 7, которые включень; между выходом равнозначности схемы сравнения предыдущего разряда и управляющим входом схемы сравнения последующего разряда.

Выходы разрядных схем выбора 3 соединены с вторыми информационными входами одноименных схем сравнения 2.

Устройство работает следующим образом. Числа, подлежащие обработке, зано- , сятся в числовые регистры 1. Значения одноименных разрядов .всех Ц числовых регистров поступают на входы соответствующей разрядной схемы выбора 3, Если число единиц, поступивщих на входы схемы выбора, превыщает ее порог Q , то на ее выходе формируется единичное значение. В противном случае сигнал на выходе разрядной схемы выбора принимает нулевое значение.

Для работы устройства по всем управлярщим шинам 6 необходимо одновременно подать управляющие сигналы. По этим сиг налам срабатывают схемы сравнения 2 старщих разрядов. Появляется сигнал на одном из трех выходов каждой из схем сравнения 2; на выходе Q , если на выходе старшего разряда числового регистра 1 имеется нулевое значение, а на выходе схмы выбора 3 - единичное значение, на единичном выходе b - в противоположной ситуации, на выходе равнозначности - при равенстве значений.

Сигнал на нулевом выходе схемы сравнения 2 через схему ИЛИ 4 устанавливает все разряды одноименного числового регистра 1 в нулевое состояние. С еди- Ш1ЧНОГО выхода схемы сравнения 2 сигнал через схему ИЛИ S устанавливает все разряды соответствующего числового регистра в единичное состояние.

Изменение состояния числовых регистров, значения старших разрядов которых отличаются от значений сигналов на выходе схемы выбора 3 этого разряда, приi водит к изменению значений сигналов, подаваемых на входы разр$шных схем выбора 3. В результате этого могут измениться значения сигналов на выходах схем выбора 3 последующих разрядов.

У тех числовых регистре, аначениэ старших разрядов которых оквзалдсь равными значению сирнала на выходе разрядной схемы вь|бора 3, возникнут сигналы на выходе равнозначности схем сравнения 2. Они задерживаются элементами задерж;ки 7 на время, необходимое для изменения состояния разрядов устройства по результатам сравнения старших разрадов, и приводят к срабатьгоанию схем сравнения 2. последующего второго разряда.

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

Описанные действия будут производиться m раз по числу разрядов обрабатываемых чисел. В результате этого на выходах разрядных схем выбора установитря двоичное

число, соответствующее К-му по величине числу из тъ обрабатываемых чисел, где

К п-9-ц .

(1)

Если из п двоичных чисел требуется выбрать К-ое число по величине, то порог 40 разрядных схем выбора в соответствии с (1) следурт выбрать равным

(2)

П р и м е jg. Даны четыре числа: , Б)110, , . Из указанного набора чисел требуется выбрать второе число по величине.

г.:

В соответствии с уравнением (2), по,рог разрядных схем выбора 3 должен бьпч взят равным 9 3 (схема выбора 3 из 4-х ). Только при наличии не менее трех -единиц на его входах на выходе появится единичный сигнал. Пример поясняется таблицей. Из таблицы видно, что в результате ра- 20 боты устройства на выходе разрядных схем выбора устанавливается число ОНО, которое является вторым по величине среди рассматриваемых чисел. Таким образом, устройство позволяет 25 повысить скорость вычисления функции упорядоченного выбора из произвольного набора двоичных чисел. Предмет изобретения Устройство для вычисления функции упорядоченного выбора, содержащее схемы 36 сравнения и схемы ИЛИ, отличающееся тем, что, с целью повышения быстродействия вычисления любого К-го числа из произвольного набора двоичных чисел, устройство содержит элементы за- 40 держки, разрядные схемы и регистры, выходы одноименных разрядов которых связаны с первыми информационными входами соответствующих схем сравнения и с соответствующими в1ходами разрядной схемы выбора, выход каждой из которых соединен с соответствующими вторыми информационными входами соответствующих .схем сравнения, при этом выход равнозначности схемы сравнения каждого пре.дьгдущего разряда через элемент задержки связан с управляющим входом схемы срда-нения последующего разрада, а нулевые и единичные выходы этих схем через соответствующие схемы ИЛИ соединены соответственно с шинами установки соответствующего регистра в нулевое и единичное состояния, причем, управляющие входы схем сравнения старших разрядов подключены к соответствующим управлюощим входам устройства.