Устройство ранжирования экстремальных значений Советский патент 1987 года по МПК G06F7/02 

1 1

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

Цель изобретения - повышение быстродействия устройства.

На фиг. 1 представлена функциональная схема устройства|на фиг. 2- функциональная схема блока синхрони зации; на фиг. 3 - пример выполнения шифратора; на фиг. 4 - временные диаграммы работы устройства.

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

Блок синхронизации (фиг. 2) содержит элемент ИЛИ 18, элемент НЕ 19, элемент И 20, элемент НЕ 21,элемент И 22, формирователь 23 заднего фронта, элемент И 24, формирователи 25 - 27 заднего фронта, элемент ИЛИ 28, формирователь 29 заднего фронта входы 30 и 31, выходы 32-34.

Шифратор (фиг. 3) может быть выполнен на элементах ИЛИ 35.

На фиг. 4а представлены импульсы на входе 16 синхронизации;на Лиг . 4б на выходе блока 6 сравнения; на фиг. 4в - на выходе блока 7 сравнения; на фиг. 4г - на первом выходе блока 8 синхронизации; на фиг. 4д- на втором выходе блока 8;нафиг.4е - на третьем выходе блока 8;нафиг.4ж на выходе 17 конца цикла;на фиг. 4з на выходе формирователя 27.

Назначение элементов устройства следующее.

Группа основных регистров 2 , служит для хранения набора из ti чисел Ъ- (i 1, 2,...п), расположен ных по порядку их величины,причем самое большое число хранится в регистре 2 и далее по порядку убывания чисел. Группа вспомогательных регистров 11 ,,...,(„-,) служит для осуществления перезаписи в них содержимого группы основных регистров

- (,. ,(ч-1)

с дальнейшем .сдвигом

919602

этой информации в сторону младших рангов чисел в основных регистрах

2 ,,... .(к-1,

Группа многовходовых элементов 5 2 И-ИЛИ 4 . служит для коммутации чисел либо с входной шины, либо с группы вспомог ательных регистров 11 ,(п-,1 в группу основных регистров 2 ....,(н,-,) Эле- fO менты ИЛИ 3,...,,V ,; и И 5 ,

служат для выработки сигнала записи Б регистре 2, .„ . Первый блок 6 сравнения служит для сравнения чисел Б., коммутируемых коммутатором 5 10 с выходов основных регистров 2., на второй вход блока сравнения,с числами А., поступающими на его первый вход. Второй блок 7 сравнения служит для сравнения чисел А;с вход- 20 ной шины с наименьшим числом А.- хранимым в регистре 2. Блок 8 синхронизации служит для выработки сигналов синхронизации для элементов устройства. Счетчик 9 рангов служит для формирования ранга R , соответствующего числу Б-, поступающему через коммутатор 10 с выхода одного из регистров 2. Дешифратор 12 служит для дешифрации двоичного код

30

ранга R,; в позиционный код. Шифратор 13 служит для выработки сигнала разрешения для элементов 2И-ШШ

35

40

45

50

1,. .. , (tn-l)(

причем сигнал разреше-ния на его выходах формируется согласно номеру позиции на его входах, например при номере позиции f разрешение формируется с Е-ГО его выхода по (п-1)-й,

В блоке синхронизации формирователи 23, 26, 27 и 29 служат для формирования импульсов синхронизации и запускаются по отрицательному перепаду входного импульса.Остальные логические элементы служат для выработки соответствующих условий запуска формирователей 23, 25, 26, 27 и 29.

На выходах блоков 6 и 7 разрешающие потенциалы (1) при условии

превышения чисел, поступающих на их первые входы, чисел на их вторых входах.

Элементы устройства могут быть вьтолнены на базе типовых цифровых интегральных схем TTL серий 33,155, 130, 131, 130, 530, 531, 561.Формирователи могут быть выполнены на базе типовых формирователей К155113

с учетом логики функционирования и временных параметров работы устройства.

Шина 1 входных данных служит для ввода в устройство анализируемых чисел А . Выход 14 служит для вывода чисел В и соответствующего им ранга R, на выходе 15 устройства. Выход 17 конца цикла служит для выдачи сигнала окончания анализа (ранжирования) одного входного числа AJ,

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

В исходном состоянии все регистры и счетчик 9 рангов обнулены (цепи сброса не показаны). На.шину 1 входных данных поступает анализируемое число Aj. По входу 16 синхронизации поступает пусковой импульс (фиг. 4а), который затем поступает на второй вход блока 8.

По адресу, определяемому счетчиком 9 рангов, содержимое основного регистра 2, через коммутатор 10 поступает на второй вход первого блока 6 сравнения. На первые входы первого и второго блоков 6 и 7 сравнения поступает анализируемое число А . С выхода последнего основного регистра 2 на второй вход второго блока 7 сравнения поступает младшее по рангу R число В, из содержащихся в регистрах 2j чисел.

10

f5

20

25

вькодах первого и второго блоков 6 и 7 сравнения - нулевые потенциалы, которые поступают на первый и третий входы 30 и 31 блока 8 синхронизации соответственно (см. фиг. 26,в).Нулевые потенциалы поступают на вторые входы первого и третьего элементов И 20 и 24. Нулевой потенциал с входа 31 блока 8 поступает через инвертор 19 на вход второго элемента К 22 и на его входе - единичный разрешающий потенпиал. По синхроимпульсу входа 16 блока 8 срабатывает элемент И 22, импульс с выхода которого поступает через второй элемент ИЛИ 28 на вход формирователя 29. По заднему фронту (1-0) выходного синхроимпульса запускается формирователь 29 (фиг. 4ж) сигнал с выхода которого поступает на выход 17 блока 8 (выход конца цикла устройства), свидетельствуя о готовности к анализу следующего

анализируемого числа А

Анало30

гичным образом будут проходить и последующие циклы анализа поступающих чисел при условии А- В , .

J № 1 Н

Причем в начале цикла происходит обнуление счетчика 9 рангов, а затем запуск устройства по входу 16.

Таким образом, если поступающие меньше, чем самое меньшее

В „in , хранимое в основном регистре 2, это не вызывает изменения в составе чисел в

числа А.

по рангу число

В зависимости от соотношения вели- 35 основных регистрах, а цикл анализа

45

чин поступившего числа А, числа В; содержащегося в подключенном регистре 2 к второму входу первого блока 6. сравнения, и содержимого числа В. в регистре 2, , возможны следу- 40

™п I hп

ющие ситуации:

1.Поступившее число А меньше любого из чисел В, содержащихся в основных регистрах 2(Aj

2.Поступившее число А. в начаJ

ле анализа больше наименьшего числа в регистре 2 (А )„а также превьш1ает при дальнейшем анализе числа, содержащиеся в регистрах 2, начиная с

Lf t I В,n).

3.Поступившее число А . превышает вначале анализа и минимальное число В. и сравниваемое число В, из регистра 2 ,,

реключатель 10.

Ситуация 1. Поскольку поступившее

(А.

оканчивается через длительность импульса с формирователя 29.

Ситуация 2. Поступающее на вход 1 устройства число превьштает минимальное число В. в регистре 2, нисло больше числа В-, хранимых в регистрах 2- с номера L по номер п.

В начале цикла по входу устройства поступает сигнал обнуления счетчика 9 рангов. С выхода блока 7 срав нения на вход 31 блока 8 поступает единичный потенциал, поскольку А j В . (фиг. 4в). С выхода блока

50

6 сравнения на вход 30 блока 8 пос-. тупает нулевой потенциал, так как А . В| (фиг. 4б) . Единичный потенциал с входа 31 блока 8 .поступает на входы элементов И 20,24 и через

поступающие через пе-55 инвертор .19 на вход элемента И 22.

Нулевой потенциал с выхода 30 блока 8 поступает на первые входы элементов И 20 и через инвертор 21 на вход элемента И 24. По синхроимпульсу

число А . не превьш1ает ни одного из

хранимых в регистрах 2j чисел, то на

0

5

0

вькодах первого и второго блоков 6 и 7 сравнения - нулевые потенциалы, которые поступают на первый и третий входы 30 и 31 блока 8 синхронизации соответственно (см. фиг. 26,в).Нулевые потенциалы поступают на вторые входы первого и третьего элементов И 20 и 24. Нулевой потенциал с входа 31 блока 8 поступает через инвертор 19 на вход второго элемента К 22 и на его входе - единичный разрешающий потенпиал. По синхроимпульсу входа 16 блока 8 срабатывает элемент И 22, импульс с выхода которого поступает через второй элемент ИЛИ 28 на вход формирователя 29. По заднему фронту (1-0) выходного синхроимпульса запускается формирователь 29 (фиг. 4ж), сигнал с выхода которого поступает на выход 17 блока 8 (выход конца цикла устройства), свидетельствуя о готовности к анализу следующего

анализируемого числа А

Анало5

0

гичным образом будут проходить и последующие циклы анализа поступающих чисел при условии А- В , .

J № 1 Н

Причем в начале цикла происходит обнуление счетчика 9 рангов, а затем запуск устройства по входу 16.

Таким образом, если поступающие меньше, чем самое меньшее

В „in , хранимое в основном регистре 2, это не вызывает изменения в составе чисел в

числа А.

по рангу число

5

0

оканчивается через длительность импульса с формирователя 29.

Ситуация 2. Поступающее на вход 1 устройства число превьштает минимальное число В. в регистре 2, нисло больше числа В-, хранимых в регистрах 2- с номера L по номер п.

В начале цикла по входу устройства поступает сигнал обнуления счетчика 9 рангов. С выхода блока 7 срав нения на вход 31 блока 8 поступает единичный потенциал, поскольку А j В . (фиг. 4в). С выхода блока

50

с входа 16 устройства через элемент ИЛИ 18 срабатывает элемент И 24, по

заднему фронту импульса (1-0) с

его выхода срабатывает формирователь 26, импульс с выхода последнего поступает на выход 24 бпока В и вход .формирователя 27. Импульс с выхода 34 блока 8 поступает на счетный вход (суммирующий) счетчика 9 рангов.В результате содержимое счетчика 9 рангов увеличивается на +1 и на его выходе выставится код следующего ранга К,, по коду которого выбирается число В на второй вход первого блока 6 сравнения через коммутатор 10 с выхода регистра 2„,

По концу импульса (1- О) с выхода формирователя 26 запускается формирователь 27, импульс с которого через элемент ИЛИ 18 поступает на входы элементов И 20, 24 соответственно (фиг. 4е, з) . Если число В j и последующие за ним числа в регистрах 2- удовлетворяют условия В то циклы ранжирования будут

I, как и в предшествующем случае путем последовательного запуска третьего формирователя 26, по концу импульса с выхода которого запускается четвертый формирова- тель 27.

Таким образом, будет происходить последовательное чтение содержимого

. заключаться,

регистров 2 ,4,,..,. и сравнение в первом блоке 6 сравнения чисел А . с В до тех пор, пока содержимое число В одного из регистров 2 не станет меньше входного исследуемого ранжируемого числа А.. При А , В,

JJ I,

сработает блок 6 сравнения, с выхода которого единичный потенциал поступает на вход 30 блока 8.Таким образом, к началу импульса с выхода элемента ИЛИ 18 на входах элемента И 20 установятся единичные потенциалы, а на входе элемента И 24 - нулевой потенциал. До коду номера ранга R, дешифратор 12 адреса формируе единичный потенциал на одном из, своих выходов (L-M), с выхода которого сигнал разрешения поступает на вход соответствующих (L-l)-x элементов 2И-ИЛИ 4 группы и вход элемента 3 1., . Шифратор 13 осуществляет выработку разрешения на своих выходах, начиная с L-ro по (п-1)-й. Разрешение при этом поступает на входы соответствующих элементов 2ИгИПИ 4 и

входы элементов ИЛИ 3, начиная с L-ro по (п-1)-й соответственно.

Входной синхроимпульс с входа 16 устройства через элемент ИЛИ 18

поступает на вход элемента И 20.Импульс с выхода элемента И 20 поступает на вход формирователя 23, который запускается по заднему фронту входного импульса (). Тактовый

импульс ТИ 1 с выхода формирователя 23 поступает на синхронизирующие входы вспомогательных регистров 11 ,(n-i; группы. По переднему фронту такта ТИ 1 происходит перезапись содержимого основных регистров 2 1,... , () соответствующие регистры 11 ,,. .. ,ih-i) . По заднему фронту (1 - 0) сигнала ТИ 1 запускается формирователь 25, сигнал с выхода которого поступает через элемент ИЛИ 28 на вход формирователя 29. По тактовому импульсу ТИ 2 происходит перезапись содержимого входной шины А . через элементы 2И-ИЛИ 4 через соответствующий элемент И 5 в регистр 2, . Информация с регистров 11.

ьи t

. ...(л-(|переписывается в соответствую

30

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

35 2 в регистр 2,, а вместо числа В в регистр 2 заносится число А,. Кроме того, все числа, начиная с ( L+1), сдвигаются одновременно в такте ТИ 2 в сторону младших рангов

40 Содержимым регистра 2„ становится число, которое ранее находилось в регистре .,) . Число В,, которое ранее хранилось в регистре 2,, исключается из списка ранжированных

5 чисел. По заднему фронту () импульса ТИ 2 с выхода формирователя 25 через элемент ИЛИ 28 запускается формирователь 29, сигнал с выхода которого поступает на выход 17 блока 8 (выход конца цикла),что свидетельствует о готовности к анализу следующего числа.

Ситуация 3. Поступившее число А . сразу превьппает наименьшее по рангу

55 число В. хранимое в регистре 2 , а также первое по рангу число В, в регистре 2,,. Счетчик 9 рангов обнуляется и на его выходе уваличива50

ется код ранга R . Содержимое регистра 2f поступает на второй вход первого.блока 6 сравнения, по первому входу которого поступает число

А .. А поскольку А на выходах блоков 6

В

то

и 7 сравнения единичные потенциалы, которые поступают на входы 30 и 31 блока 8. В дешифраторе 12 формируется единичны потенциал на его первом выходе. Единичный потенциал поступает на вход элемента И 5 и первый вход шифратора 13, причем на его выходах с 1-го по (п-1)-й вьфабатываются единичные потенциалы, поступающие на входы элементов 2И-ИЛИ 4, .,(п) соответственно, а также на входы

соответствующих элементов И 3

...,(tvi). Аналогично предьщущему случаю по синхроимпульсу с входа 16 устройства последовательно запускаются формирователи 23 и 25, по тактовым импульсам ТИ 1 и ТИ 2 которых производится сначала перезапись со hв

держимого регистров 2 соответствующие вспомогательные регистры 11, 11„., числа А, с

запись (сдвиг) содержимого

затем запись 1 в

. J W входной шины 1 в регистр 2, по синхросигналу с выхода элемента И 5, , регистров 11,... 11., в соответствующие регистры 2, 2„, Таким образом, осуществляется включние входного ранжируемого числа А

В., В,

В

в хранимые числа и,, и,, основных регистрах 2,, 2, . , . 2 группы, а также паралелльный (одновременный) сдвиг в сторону меньших рангов всего содержимого тех основ- -ных регистров 2 j, 2(,,, ...,2, , в которых хранились чиёла, меньшие включительного.

При дальнейшей работе устройства в основных регистрах 2, 2, ,..,2 группы будут накапливаться только самые большие по величине (экстремальные) числа, расположенные по порядку величины.

При организации чтения содержимого регистров 2, 2j,... 2 счетчик 9 обнуляется, а по входу Чтение устройства поступают импульсы на суммирующий вход счетчика 9 рангов.При этом на выходной шине 14 каждому

числу В будет соответствовать его порядковьгй номер (ранг) R - с выходов 15 устройства.

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

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

fO группой входов блока сравнения,выход которого соединен с первым входом первого элемента И блока синхронизации, вход синхронизации уст- ройсз;ва соединен с первым входом

f5 первого элемента ИЛИ блока синхронизации выход счетчика рангов является выходом ранга устройства,выходы первого основного регистра группы подключены к первой группе

20 информационных входов коммутатора и к информационным входам вспомогательного регистра, отличающееся тем, что, с целью повышения быстродействия, в устройст2-5 во введены группа элементов ИЛИ, п-1 групп элементов 2И-ИЛИ, группа элементов И, второй блок сравнения, п-2 вспомогательных регистров, дешифратор адреса, шифратор,

30 в блок синхронизации введены третий элемент И, два элемента НЕ и пять ;формирователей заднего фронта импульсов, причем шина данных устройства со- единена с первой группой входов вто35 рого блока сравнения, информационными входами первого основного регистра группы, первыми входами первых элементов И соответствующих элементов 2И-ШШ всех групп, выходы

40 элементов 2И-ИЛИ i-й группы, где i 1, 2,...,(п-1), соединены с информационными входами (i+1)-ro основного регистра группы, выходы основных регистров группы со второго

45 по (п-1)-и соединены с информационными входами соответствующих вспомогательных регистров и с соответствующими группами информационных входов коммутатора, выходы п-го

50 основного регистра группы соединены со второй группой входов второго блока сравнения и п-й группой информационных входов коммутатора, выходы которого являются выходами экстре55 мального числа устройства и подключены к второй группе входов первого блока сравнения, выходы вспомогательных регистров с первого по (п-1)-и подключены к первым входам вторых

912

элементов И элементов 2И-ИЛИ соответствующих групп, выход зторого блока сравнения подключен к второму входу первого элемента И блока синхронизации и первому входу второго элемента И блока синхронизации и через первый элемент НЕ - к первому входу третьего элемента И блока синхронизации, второй вход которого подключен к входу синхронизации устройства, в блоке синхронизации первый вход первого элемента И через элемент НЕ соединен с вторым входом второго элемента И, выход которого через первый и второй формирователи заднего фронта подключены к второму входу первого элемента ИЛИ, выход которого соединен с третьими входами первого и второго элементов И, выход первого элемента И через третий и четвертый формирователи заднего фронта импульсов подключен к- первому входу второго элемента ИЛИ, второй вход которого соединен с выходом третьего элемента И, а выход подключен к входу пятого формирователя заднего фронта импульса, выход которого является выходом конца цикла устройства, выход третьего

010

формирователя заднего фронта импульса соединен с синхровходами всех вспомогательных регистров,выход четвертого формирователя заднего фронта импульса подключен к первым входам элементов И группы, выходы которых соединены с синхровходами соответствующих основных регистров группы, вькоды счетчика рангов соединены с адресными входами коммутатора и входами дешифратора адреса, выходы которого с первого по (п-1)-й соединены с соответствующими входами шифратора,i-й выход которого соединен с. вторыми входами вторых элементов И элементов 2И-ИЛИ i-й группы и первым входом i-ro элемента ИЛИ, второй вход которого соединен с вторыми входами вторых элементов И элементов 2И-Ш1И i-й группы и (i+1)-M выходом дешифратора адреса, первый выход которого подключен к второму входу первого элемента И группы, второй вход (i+1)-ro элемента И группы соединен с выходом i-fo элемента ИЛИ группы, выход первого формирователя заднего фронта блока синхронизации подключен к счетному входу счетчика рангов. ,.

J.f- нногобходовые элементы ИЛИ

Фие.У

Ж

ш

Изобретение относится к вычислительной технике и может быть использовано в устройствах обработки сигналов радиолокаторов, в системах распознавания. Цель изобретения - повышение быстродействия. Устройство содержит группу основных регистров, группы элементов 2И-ИЛИ,ИЛИ,И, группу вспомогательных регистров, блок синхронизации, счетчик рангов, коммутатор, дешифратор адреса,шифратор . Блок синхронизации содержит элементы И,ИЛИ,НЕ, формирователи заднего фронта импульсов. Группа основных регистров служит для хране ния набора чисел, расположенных по порядку их величины. В зависимости от соотношения величин чисел, хранимых в основных регистрах, поступившее число либо не вызывает изменения в составе чисел, хранимых в основных регистрах, либо включается в их состав с соответствующим сдвигом остальных чисел и исключением наименьшего числа. 4 ил. с S (Л