Устройство для вычисления порядковых статистик последовательности двоичных чисел

 

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

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

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

РЕСПУБЛИН (19) (11) (51) 4 С 06 Р 7 02

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЦТИЙ

К ABTGPCHGMY СВИДЕТЕЛЬСТВУ (21) 3885186/24-24 (22) 18.04.85 (46) 15.02.87, Бюл. № 6 (71) Физико-механический институт им.Г.В.Карпенко (72) B.Â.Ãðèöûê, А.Ю.Луцык и P.М.Паленичка (53) 681.325 (088.8) (56) Авторское свидетельство СССР

¹ 1096638 кл.G 06 F 7/02, 1983.

Авторское свидетельство СССР № 1239708 кл.G 06 F 7/02, 1984. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПО-.

РЯДКОВЫХ СТАТИСТИК ПОСЛЕДОВАТЕЛЬНОСТИ ДВОИЧНЫХ ЧИСЕЛ (57)Изобретение относится к области вычислительной техники и технической кибернетики и может быть использовано в системах цифровой обработки сигналов, например для ранговой фильтрации сигналов. Цель изобретения— расширение области применения устройства за счет устранения неоднозначности при вычислении равных порядковых статистик входной последовательности чисел. Устройство.содержит блок из п сдвиговых регистров, и элементов И, где п — количество чисел заданной последовательности, n — - входовый элемент ИЛИ, и элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, п триггеров первой группы, блок приоритета, п триггеров второй группы, сдвиговый регистр, шифратор, регистр номера порядковой статистики и блок синхронизации. Порядковые статистики последовательно вычисляются путем определения максимума в каждом цикле работы устройства и исключения его при анализе чисел в следующем цикле, общее количество которых равно и.

2 иле

1290295

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

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

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

Устройство содержит блок из п сдвиговых регистров 1, и элементов

И 2, и-входовый .элемент ИЛИ 3, п элементов 11СКЛ1ОЧА!ОЩЕЕ ИЛИ 4, и .триггеров 5 первой группы, блок 6 приоритета, и триггеров 7 второй группы, сдвиговый регистр 8, шифратор 9, регистр 10 кода номера порядковой статистики, блок 11 синхро-25 низа|гни, состоящий из генератора

12 тактовых импульсов и счетчика 13, информационный вход 14 и вход 15 записи устройства.

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

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

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

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

m - -количество разрядов двоичных чисел из входной последовательности.

В i-м цикле работы устройства вычисляется ш-разрядный код 1-й порядковой статистики, например код медианного значения последовательности вычисляется в цикле с номером (n + l) /2. где n — нечетное.

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

В первом цикле работы устройства при поступлении j-го тактового импульса с первого выхода блока 11, который является выходом генератора

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

1-м такте цикла определяется j-й разряд порядковой статистики. После ш тактов работы в сдвиговом регистре 8 записывается код максимума входной последовательности, который поразрядно поступает на вход его первого разряда с выхода элемента

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

После окончания первого цикла работы на втором выходе блока 11, т.е.

1290295 на выходе счетчика 13 появляется управляющий импульс. Частота импуль-, сов на выходе счетчика 13 в т раз меньше частоты генератора 12 тактовых импульсов. Импульс с второго 5 выхода блока 11 поступает на управляющий вход блока 6. В предлагаемом устройстве блок 6 выполняет следующую функцию. При определении максимума последовательности чисел может оказаться, что в этой последовательности имеется несколько равных максимальных чисел. Следовательно, в этом случае в единичном состоянии будет несколько триггеров 5, которые соответствуют этим максимальным числам, и не будет однозначности при определении индекса максимального числа, т.е. в общем случае индекса вычисляемой порядковой статистики. Блок 6 за счет использования и элементов

И 16 и ï-1) элементов HE 17 позволяет однозначно определить номер вычисляемой порядковой статистики путем селекции первого из триггеров

5, находящихся в единичном состоянии. При поступлении импульса на вход 19 блока 6 на одном из и его выходов 20 появляется импульс, ко30 торый устанавливает соответствующий триггер 7 в нулевое состояние, а состояния остальных триггеров 7 остаются без изменения. Число входной последовательности чисел, которое было определено в первом цикле работы как максимум, во втором цикле исключено из анализа при определении второй порядковой статистики. Таким образом, во втором цикле работы уст40 ройства определяемый максимум последовательности кодов чисел на выходе элементов И 2 будет второй порядковой статистикой входной последовательности чисел. Выходные сигна- лы блока 6 также поступают на входы

45 шифратора 9, который преобразовывает входной код "1 из n" в позиционный двоичный, имеющий 1=11о8 п1 разрядов (где знак (g обозначает округление до ближайшего целого, не меньшего данного числа).

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

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

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

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

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

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

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

290295

l 1 1

Составитель Е.Иванова

Техред Л.Олейник

Редактор M.Дылын

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

Тираж 67 3

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

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

Заказ 7902/46

Подписное

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