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

 

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

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

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

РЕСПУБЛИН

1 А1 (19) (И) (5I)4 С 06 F 15 36

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

H А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4095473/24-24 (22) 29.07.86 (46) 23.11.87. Бюл. ¹ 43 (71) Физико-механический институт им. Г.В.Карпенко (72) В.В.Грицык, M.À.Ïàëåíè÷êà и P.M.Паленичка (53) 681.3 (088.8) (56) Патент США № 4456968, кл. G 06 F 7/06, опублик. 1984.

Патент CUA ¹ 4441165, кл. G 06 F 7/06, опублик. 1984. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОРЯДКОВЫХ СТАТИСТИК (57) Изобретение относится к вычислительной технике и может быть использовано в системах цифровой обработки сигналов. Цель изобретения— расширение функциональных возможностей за счет определения ранговых порядковых статистик. Для достижения указанной цели в устройство введены группа из п блоков постоянной памяти, группа из и компараторов, регистр ранга и преобразователь кода, состоящий из шифратора приоритета и дешифратора. Благодаря введенным элементам устройство может вычислять однозначно заданную посредством регистра ранга порядковую статистику в случае, когда имеется несколько одинаковых по величине чисел. 1 ил.

1354 21О

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

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

На чертеже представлена блок-схе10 ма устройства.

Устройство для вычисления порядковых статистик содержит и элементов i задержки (регистров), блок 2 сравнения, состоящий из и-1 компара15 торов 3 и (и-2)-х групп двухразрядных запоминающих элементов 4„ 2п блоков 5 постоянной памяти, регистр

6 ранга, и трехвходовых компараторов 7, преобразователь 8 коца, содержащий шифратор 9 приоритета и дешифратор 10, и мультиплексор 11.

Перед началом работы устройства в регистр 6 ранга записывается двоичZ5 ный код вычисляемой порядковой статистики. Например, для выполнения медианной фильтрации в регистр 6 ранга записывается двоичный код числа R = (n+1) /2, где n — нечетное.

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

Отсчеты входного сигнала (двоичные числа) последовательно поступают на вход устройства и в каждом такте работы устройства на вьгходах п регистров 1 присутствуют коды п последовательных отсчетов сигнала. Посредством и-1 компараторов 3 параллельно выполняется сравнение числа на выходе пер- 40 вого регистра 1 с (и-1) числами, которые В данном такте хранятся в остальных регистрах 1. Каждый из компараторов 3 имеет два выхода: первый

"Больше" и второй "Меньше". С помощью 45 (п-2)-х групп запоминающих элементов 4. осуществляется последовательное запоминание результатов сравнения текущего отсчета сигнала, т.е. числа на выходе первого регистра 1 с (n-1) его 50 предыдущими отсчетами. При этом каждый из запоминающих элементов 4 имеет два разряда. Таким образом, при последовательном поступлении чисел на вход устройства,.рекурсивно вычисля.ются результаты всех возможных попарных сравнений и последовательных отсчетов сигг.ала, общее количество которых равно n(n-1)/2.

В каждом такте работы устройства вьгходные сигналы "Больше" тех компараторов 3 и запоминающих элементов 4, которые относятся к результатам сравнения i-ro числа с остальными (п-1) числами, поступают на адресный вход i-ro блока 5 постоянной памяти первой группы. Аналогично выходные сигналы Меньше тех компараторов 3 и запоминающих элементов 4, которые относятся к результатам сравнения i-го числа с остальными и-1 числами, поступают на адресный вход

i-ro блока 5 второй группы.

Все блоки 5 постоянной памяти первой группы программируются таким образом, что на информационном выходе i-ro блока 5 появляется код количества чисел a;, хранящихся в и регистрах 1, которые меньше по величине от 1-ro числа, в зависимости от результатов попарного сравнения посредством соответствующих компараторов 3.

Все блоки 5 второй группы программируются таким образом, что на информационном выходе i-го блока 5 постоянной памяти второй группы появляется двоичный код числа (n-Ь, ), где

b; — количество чисел, хранящихся в регистрах 1, которые больше по величине i-го числа. Выходные коды двух

i-х блоков 5 первой и второй групп поступают соответственно на первый и второй входы 1-го трехвходового компаратора 7, на третий вход которого одновременно поступает код номера вычисляемой порядковой статистики из регистра 6 ранга. Если устройство вычисляет R-ю порядковую статистику, то при этом х-й трехвходовый компаратор 7 реализует следующую функцию:

1, при аR nb;

Cj = (1)

О, в противном случае, где C; — выходной сигнал 1-го трехвходового компаратора 7.

Таким образом, если С; = 1, то

i-e число из и чисел, хранящихся в регистрах 1, является Р-й порядковой статистикой, в частности при R = — (n+1)/2 является медианой.

При наличии равных по величине чисел в регистрах 1 может оказаться, что одновременно имеется несколько сигналов на выходах трехвходовых

13S4210

50 компараторов 7, которые имеют значение "1". В данном случае получается неоднозначность при определении номера того числа, которое является

R-й порядковой статистикой.

Для устранения этой неоднозначности введен шифратор 9, который выбирает одно определенное число из несколько равных по величине чисел, которые все являются (удовлетворяют условию (1)) R-й порядковой статистикой.

Шифратор 9 работает таким образом, что если на его n входов поступают одновременно несколько сигналов

"1", то первый из этих сигналов остается равным "1", а остальные устанавливаются в "0". Посредством дешифратора 10 двоичный код "1 из n" 2p на выходе шифратора 9 преобразуется в позиционный двоичный код. Этот код номера числа, которое является

R-й порядковой статистикой, поступает на управляющий вход мультиплек- 25 сора 11, и тогда на его выходе появляется код R-й порядковой статистики и чисел, которые хранятся в регистрах 1.

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

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

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

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

Устройство для вычисления порядковых статистик, содержащее п-2 групп запоминающих элементов, п последовательно соединенных элементов задержки, выход первого элемента задержки подключен к первым входам (и-1) компараторов первой группы, второй вход

k-ro xoMnapavopa (k=1,n-1) первой группы соединен с выходом (k+1)-го элемента задержки, входы i-х запоминающих элементов -й группы (i

1,п-3) соединены с выходами с первого по -й запоминающих элементов (i+1) é группы (где i = 1,п-3), входы запоминающих элементов (n-2)-й группы подключены к выходам Меньше (n-2) компараторов первой группы, входы блоков постоянной памяти первой группы соединены с выходами

"Больше" компараторов первой группы и запоминающих элементов всех групп, выходы элементов задержки подключены к информационным входам мультиплексора, выход которого является выходом устройства, о т л и ч а ю щ е е— с я тем, что, с целью расширения функциональных возможностей за счет определения ранговых порядковых статистик, в устройство введены п блоков постоянной памяти второй группы, п компараторов второй группы, регистр ранга и преобразователь кода, состоя-, щий из шифратора приоритета и дешифратора, при этом выходы шифратора приоритета подключены к соответствующим входам дешифратора, выход которого соединен с управляющим входом мультиплексора, входы блоков постоянной памяти второй группы соединены с соответствующими выходами компараторов второй группы и запоминающих элементов всех групп, информационный выход j-ro блока постоянной памяти первой группы подключен к первому входу j-го компаратора (j = 1,пу второй группы, информационный выход j-го блока постоянной памяти второй группы соединен с вторым входом j-ro компаратора второй группы, третий вход которого соединен с выходом регистра ранга, выходы компараторов второй группы соединены с соответствующими входами шифратора приоритета.

1354210

Редактор Н.Тупица

Заказ 5696/45 Тираж 671 Подписное

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

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

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

Составитель Л.Григорьян-Чтенц

Техред Л.Олийнык Корректор Л.Пилипенко