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

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

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

На фиг.1 изображена структурная схема предлагаемого устройства; на фиг. 2 - структурная схема блока приоритета.

Устройство.содержит блок из п сдвиговых регистров 1, п элементов И 2, п-входовый элемент ИЛИ 3, п элементов ИСЮЕОЧАЮЩЕЕ ЮШ 4, п .триггеров 5 первой группы, блок 6 приоритета, п триггеров 7 второй группы, сдвиговый регистр 8, шифратор 9, регистр i О кода номера.порядковой статистики, блок II синхро низаиди, состоящий из генератора 12 тактовых импульсов и счетчика 13, информационный ,вход 14 и вход 15 записи устройства.

Блок приоритета содерлшт п элементов И 16, (п-1) элементов НЕ 17, п входов 18, управляющий вход 19 и п выходов 20.

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

Перед началом вычислений выполняется установка в единичное состояние триггеров первой и-второй группы. При поступлении импульса записи на вход 15 устройства в блок 1 с информационного входа 14 устройства записываются коды входной последовательности чисел. Блок I состоит из п кольцевых сдвиговых регистров, работающих параллельно. Входы управления сдвигом всех кольцевых сдвиговых регистров соединены с входом управления сдвигом блока , а выходы первых (старших) разрядов сдвиговых регистров являются соответствуюл ;ими выходами блока.

В данном устройстве все порядковые статистики последовательности п двоичных чисел вычисляются поочередно, начиная с первой, т.е„ с максимального числа заданной последовательности чисел, и кончая п-ой порядковой статистикой, т.е. минимумом этой последовательности. КажfO

J5

20

25

30

35

40

45

50

55

дан порядковая статистика вычислн-ег- ся за время одного цикла работы устройства, причем каждый цикл состоит из m тактов работы устройства, где m - количество разрядов двоичных чисел из входной последовательности. В i-M цикле работы устройства вычисляется т-разрядный код i-й порядковой статистики, например код медианного значения последовательности вычисляется в цикле с номером (п + ) /2. где п - нечетное.

Значения всех п порядковых статистик вычисляются поразрядно, начиная со старшего разряда, следующим образом.

В первом цикле работы устройства при поступлении j-ro тактового импульса с первого выхода блока 11, который является выходом генератора 12 тактовых импульсов, на вход управления сдвигом блока 1 происходит считывание j-x разрядов всех п чисел последовательности и затем сдвиг кодов в кольцевых сдвиговых регистрах на один разряд в сторону старшего разряда. С выходов блока 1 сигналы, соответствующие j-м разрядам чисел, поступают на первый вход соответствующих элементов И 2. С помощью п элементов И 2, п-входового элемента ИЛИ 3, п элементов ИСКЛЮЧАЮЩЕЕ ИЛР1 4 и п триггеров 5 первой группы поразрядно (начиная со старшего разряда) вычисляется максимум последовательности чисел, коды которых поступают на первые входы элементов И 2. В первом цнкле работы устройства на выход п-входового элемента ИЛИ 3 поразрядно поступает код максимума входной последовательности чисел, т.е. первая порядковая статистика, такнм образом, что в J-M такте цикла определяется j-й разряд порядковой статистики. После га тактов работы в сдвиговом регистре 8 записывается код максимума входной последовательности, который поразрядно поступает на вход его первого разряда с выхода элемента ИЛИ 3. Триггеры 5 первой группы устанавливаются в нулевое состояние за исключением триггера, номер которого являетс5{ номером максимума входной последс Вательности, т.е. этот триггер остается в единичном состоянии. После окончания первого цикла работы на втором выходе блока 11, т.е.

на выходе счетчика 13 появляется управляющий импульс. Частота импульсов на выходе счетчика 13-в m раз меньше частоты генератора 12 тактовых импульсов. Импульс с второго выхода блока 11 поступает на управляющий вход блока 6. В предлагаемом устройстве блок 6 выполняет следующую функцию. При определении максимума последовательности чисел может оказаться, что в этой последовательности имеется несколько равных максимальных чисел. Следовательно, в этом случае в единичном состоянии будет несколько триггеров 5, которые соответствуют этим максимальным числам, и не будет однозначности при oTipe- делении индекса максимального числа т.е. в общем случае индекса вычисляемой порядковой статистики. Блок 6 за счет использования п элементов И 16 и (п-1) элементов НЕ 17 позволяет однозначно определить номер вычисляемой порядковой статистики путем селекции первого из триггеров 5, находящихся в единичном состоянии. При поступлении импульса на вход 19 блока 6 на одном из п его выходов 20 появляется импульс, который устанавливает соответствующий триггер 7 в нулевое состояние, а состояния остальных триггеров 7 остаются без изменения. Число входной последовательности чисел, которое было определено в первом цикле работы как максимум, во втором цикле исключено из анализа при определении второй порядковой статистики. Таким образом, во втором цикле работы устройства определяемый максимум последовательности кодов чисел на выходе элементов И 2 будет второй порядковой статистикой входной последовательности чисел. Выходные сигналы блока 6 также поступают на входы шифратора 9, которьй преобразовывает .входной код 1 из п в позиционный двоичный, имеющий пЧ разрядов (где знак f обозначает округление до ближайшего целого, не меньшего данного числа).

После окончания каждого цикла работы устройства управляюш 1Й импульс на втором выходе блока 11 устанавливает все п триггеров 5 первой группы в единичное состояние, которое является исходным при определении максимума последовательности в.

0

5

0

5

0

5

0

5

0

5

следующем цикле работы. Также при поступлении управляющего импульса на вход управления записью регистра 10 происходит запись номера порядковой статистики в регистр 10. Таким образом, после окончания i-ro цикла работы устройства в m разрядном сдвиговом регистре 8 будет записан код i-й порядковой статистики входной последовательности чисел, а в регистре 10 - код индекса i-й порядковой статистики. После п циклов работы будут последовательно вычислены все порядковые статистики.

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

Устройство для вычисления порядковых статистик последовательности двоичных чисел, содержащее блок из п сдвиговых регистров, п элементов И, где п - число анализируемых чисел, п элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, п геров первой группы, элемент ИЛИ, регистр кода номера порядковой статистики, регистр и блок синхронизации, причем выходы старших разрядов сдвиговых регистров блока соединены с первыми входами соответствующих элементов И, выходы которых соеди- , нены с первыми входами соответствующих элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, выходы которых соединены с входами установки в ноль соответствующих триггеров первой группы, выходы которых подключены к вторым входам соответствующих элементов И,.входы установки в единицу триггеров - .первой группы объединены, вторые входы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ объединены, выход элемента ИЛИ подключен к входу регистра, отличающееся тем, что, с целью расширения области применения за счет устранения неоднозначности при вычислении равных порядковых статистик, регистр выполнен сдвиговым и в устройство введены блок приоритета, шифратор, п триггеров второй группы, выходы которых соединены с третьими входами соответствующих элементов И, выходы которых дополнительно подключены к входам элемента ИЛИ, выход которого соединен с вторыми входами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, выходы триггеров соединены с информационными входами блока .приоритета, управляющий вход которого соединен с входами установки в

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

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

Ш

Уст.„1 о

г

Г

Sf

С

т

//

/4

dbixodi

о в

rN

-

П

г

13

иг.1

9

ikii-.

10 I

i

Выход

Изобретение относится к области вычислительной техники и технической кибернетики и может быть использовано в системах цифровой обработки сигналов , например для ранговой фильтрации сигналов. Цель изобретения расширение области применения устройства за счет устранения неоднозначности при вычислении равных порядковых статистик входной последовательности чисел. Устройство.содержит блок из п сдвиговых регистров, п элементов И, где п - количество чисел заданной последовательности, п - входовый элемент ИЛИ, п элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, п триггеров первой группы, блок приоритета, п триггеров второй группы, сдвиговый регистр, шифратор, регистр номера порядковой статистики и блок синхронизации. Порядковые статистики последовательно вычисляются путем определения максимума в каждом цикле работы устройства и исключения его при анализе чисел в следующем цикле, общее количество которых равно п. 2 ил. I (Л tc ;о Nd ;о ел

Редактор М.Дыпын

Заказ 7902/46Тираж 67 3 , Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, , Раушская наб., д. 4/5

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

Составитель Е.Иванова Техред Л.Олейник

Корректор М.Демчик