Устройство ранжирования экстремальных значений

 

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

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

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (11) А1 (51) 4 G 06 F 7/02

1 в

1ЫьЯi(1

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

К А BTOPCHOIVIY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3940443/24-24 (22) 30.07.85 (46) 23.02.87. Бюл. № 7 (72) А.Н.Мурашко (53) 681.325.5(088.8) (56) Патент США № 3829664, кл. G 06 F 7/02, 1974.

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

¹ 1049899, кл. С 06 F 7/02, 1982. (54) УСТРОЙСТВО РАНЖИРОВАНИЯ ЭКСТРЕМАПЬНЪ|Х ЗНАЧЕНИЙ (57) Изобретение относится к вычислительной технике и может быть использовано в устройствах обработки сигналов радиолокаторов, в системах распознавания. Цель изобретения— повышение быстродействия. Устройство содержит группу основных регистров, группы элементов 2И-ИЛИ,ИЛИ,И, группу вспомогательных регистров, блок синхронизации, счетчик рангов, коммутатор, дешифратор адреса,шифратор. Блок синхронизации содержит элементы И,ИЛИ,НЕ, формирователи заднего фронта импульсов. Группа основных регистров служит для хране ния набора чисел, расположенных по порядку их величины. В зависимости от соотношения величин чисел, хранимых в основных регистрах, поступившее число либо не вызывает изменения в составе чисел, хранимых в основных регистрах, либо включается в их состав с соответствующим сдвигом остальных чисел и исключением наименьшего числа. 4 ил.

1291960 2

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

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

На фиг. 1 представлена функциональная схема устройства;на фиг. 2— функциональная схема блока синхронизации; на фиг. 3 — пример выполнения шифратора; на фиг. 4 — временные диаграммы работы устройства, Устройство (фиг. 1) содержит шину 1 данных устройства, группу основных регистров 2, группу элементов ИЛИ 3, группы элементов 2И-ИЛИ

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 и 3 1, выходы 32-34.

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

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

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

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

2,, «„, с дальнейшем сдвигом

«е )«<«

5

1О

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

2, Группа многонходoBblx элементов

2 И-ИЛИ 4 «<„„. служит для коммутации чисел либо с входной шины, либо с группы вспомогательных регистров 11,„, в группу основных регистров 2,, <„,! . Элементы ИЛИ 3, <„,, и И 5,,< - 1- )« служат для выработки сигнала записи н регистре 2, „ . Первый блок 6 сравнения служит для сравнения чисел В,, коммутируемых коммутатором

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

4,,„ „ причем сигнал разрешения на его выходах формируется согласно номеру позиции на его входах, например при номере позиции Г разрешение формируется с I-го его выхода по (n-1) -й.

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

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

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

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

Шина 1 входных данных служит для ввода в устройство анализируемых чисел A ... .Выход 14 служит для вывоJ да чисел В и соответствующего им 1 ранга R, на выходе 15 устройства.

Выход 17 конца цикла служит для выдачи сигнала окончания анализа (ранжирования) одного входного числа А;, Устройство работает следующим образом.

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

По адресу, определяемому счетчи— ком 9 рангов, содержимое основного регистра 2, через коммутатор 10 поступает на второй вход первого блока

6 сравнения. На первые входы первого и второго блоков 6 и 7 сравнения поступает анализируемое число

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

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

6 сравнения, и содержимого числа

В . в регистре 2„, возможны следуtnih ющие ситуации:

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

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

2 начиная с В -го (А. >

Ь| . е Ь 4 ,„).

3. Поступившее число А .превыша4 ет вначале анализа и минимальное число В, и сравниваемое число В, Win !1 из регистра 2 „ поступающие через переключатель 10.

Ситуация 1. Поскольку поступившее число А . не превышает ни одного из

J хранимых в регистрах 2; чисел, то на выходах первого и второго блоков 6 и 7 сравнения — нулевые потенциалы, которые поступают на первый и третий входы 30 и 3 1 блока 8 синхронизации соответственно (см. фиг. 26,в) .Нулевые потенциалы поступают на вторые входы первого и третьего элементов

И 20 и 24. Нулевой потенциал с входа

3 1 блока 8 поступает через инвертор

19 на вход второго элемента И 22 и на его входе — единичный разрешающий потенциал. По синхроимпульсу входа

16 блока 8 срабатывает элемент И 22, импульс с выхода которого поступает через второй элемент ИЛИ 28 на вход формирователя 29. По заднему фронту (1 — О) выходного синхроимпульса за пускается формирователь 29 (фиг. 4ж), сигнал с выхода которого поступает на выход 17 блока 8 (выход конца цикла устройства), свидетельствуя о готовности к анализу следующего анализируемого числа А . . АналоJ+ 1 гичным образом будут проходить и

25 последующие циклы анализа поступающих чисел при условии А„ В

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

Таким образом, если поступающие числа А. меньше, чем самое меньшее по рангу число В ;„, хранимое в основном регистре 2„, это не вызывает изменения в составе чисел в

35 основных регистрах, а цикл анализа оканчивается через длительность импульса с формирователя 29.

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

1 регистрах 2 с номера L по номер и.

В начале цикла по входу устройст45 ва поступает сигнал обнуления счетчика 9 рангов. С выхода блока 7 срав" нения на вход 3 1 блока 8 поступает единичный потенциал, поскольку А „

В . (фиг. 4в). С выхода блока

50 6 сравнения на вход 30 блока 8 пос тупает нулевой потенциал, так как

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

55 инвертор 19 на вход элемента И 22.

Нулевой потенциал с выхода 30 блока

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

1291960 с входа 16 устройства через элемент

ИЛИ 18 срабатывает элемент И 24, по заднему фронту импульса (1 О) с его выхода срабатывает формирователь

26, импульс с выхода последнего поступает на выход 24 блока 8 и вход .формирователя 27. Импульс с выхода

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

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

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

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

J с В; до тех пор, пока содержимое число В„ одного из регистров 2 „ не станет меньше входного исследуемого ранжируемого числа AJ При А „ ) В„ сработает блок 6 сравнения, с выхода которого единичный потенциал ,поступает на вход 30 блока 8.Таким образом, к началу импульса с выхода элемента ИЛИ 18 на входах элемента

И 20 установятся единичные потенциалы, а на входе элемента И 24 — нулевой потенциал, По коду номера ранга R, дешифратор 12 адреса формирует единйчный потенциал на одном из своих выходов (L-м), с выхода которого сигнал разрешения поступает на вход соответствующих (L-1)-х элементов

2И-ИЛИ 4 группы и вход элемента

3 „, Шифратор 13 осуществляет выработку разрешения на своих выходах, начиная с L-ro по (и-1)-й. Разрешение при этом поступает на входы соответствующих элементов 2И-,ИЛИ 4 и

45 чисел. По заднему фронту (1 — 0} импульса ТИ 2 с выхода формирователя 25 через элемент ИЛИ 28 запускается формирователь 29, сигнал с выхода которого поступает на выход

17 блока 8 (выход конца цикла)„что свидетельствует о готовности к анализу следующего числа.

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

30 входы элементов ИЛИ 3, начиная с

L-ro по (п-1)-й соответственно.

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

23 поступает на синхронизирующие входы вспомогательных регистров

11,,„, группы. По переднему фронту такта ТИ 1 происходит перезапись содержимого основных регистров

2, <„, в соответствующие регистры 11,,(w, . По заднему фронту (1 О) сигнала ТИ 1 запускается формирователь 25, сигнал с выхода которого поступает через элемент ИЛИ

28 на вход формирователя 29. По тактовому импульсу ТИ 2 происходит перезапись содержимого входной шины А . ! через элементы 2И-ИЛИ 4 через соответствующий элемент И 5 „ в регистр

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

2 „ в регистр 2„,, а вместо числа В„ в регистр 2 заносится число А ..

I 4

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

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

1 в регистре 2 . Счетчик 9 рангов обнуляется и íà его выходе увеличива20

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

При организации чтения содержимого регистров 2„, 2,... 2; счетчик

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

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

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

А .. А поскольку А о В > В ., то на выходах блоков 6 и 7 сравнения единичные потенциалы, которые поступают на входы 30 и 31 блока 8. В дешифраторе 12 формируется единичный потенциал на его первом выходе. Еди- 10 ничный потенциал поступает на вход элемента И 5, и первый вход шифратора 13, причем на его выходах с

1-ro по (и-1)-й вырабатываются единичные потенциалы, поступающие на входы элементов 2И-ИЛИ 4, соответственно, а также на входы соответствующих элементов И 3, ...,(+t). Аналогично предыдущему случаю по синхроимпульсу с входа 16 устройства последовательно запускаются формирователи 23 и 25, по тактовым импульсам ТИ 1 и ТИ 2 которых производится сначала перезапись содержимого регистров 2,..., 2 „, в соответствующие вспомогательные регистры 11, 11„, а затем запись

1 числа A„ с входной шины 1 в регистр

2 по синхросигналу с выхода элемен 1 та И 5, запись (сдвиг) содержимого регистров 11,..., 11„,. в соответствующие регистры 2, 2„.

Таким образом, осуществляется включение входного ранжируемого числа А в хранимые числа В „ В,. ° ., В„ в основных регистрах 2 „ 2д,... 2„ группы, а также паралелльный (одновременный) сдвиг в сторону меньших рангов всего содержимого тех основ-ных регистров 2 „, 2,„„>, ...,2„,, 40 в которых хранились числа, меньшие включительного.

60 8

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

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

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

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

19бО 10 формирователя заднего фронта импульса соединен с синхровходами всех вспомогательных регистров, выход четвертого формирователя заднего фронта импульса подключен к первым входам элементов И группы, выходы которых соединены с синхровходами соответствующих основных регистров группы, выходы счетчика рангов соединены

10 с адресными входами коммутатора и входами дешифратора адреса, выходы которого с первого по (n-1)-й соединены с соответствующими входами шифратора, i-й выход которого соединен с. вторыми входами вторых элементов

И элементов 2И-ИЛИ i-й группы и первым входом i-ro элемента ИЛИ, второй вход которого соединен с вторыми входами вторых элементов И элементов 2И-ИЛИ i-й группы и (i+1) ì выходом дешифратора адреса, первый выход которого подключен к второму входу первого элемента И группы, второй вход (i+1)-го элемента И группы соединен с выходом i-го элемента

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

1291960 щг. 2

0m IZ

° ° °

Л" . кногойадобые апемеиты ИЛИ

47ие. У

Составитель E.Èâàíoâà

Техред В. Кадар Корректор Е. Сирохман

Редактор В.Данко

Заказ 265/47 Тираж 673 ПОДписнОе

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

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

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