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

ел

о со со

05

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

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

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

Устройство содержит первьй элемент 1 задержки, счетчик 2, второй и первый 4 элементы ИЛИ, первый 5 и второй 6 триггеры, первый 7 и трети 8 элементы И, третий 9 элемент ИЛИ, второй 10 элемент задержки, п регистров сдвига 11 (п - максимальная : разрядность анализируемых чисел), группу элементов И 12, генератор 1 тактовых импульсов, второй 14 и чет вертый 15 элементы И, п мультиплексров 16, m элементов 17 сравнения (т количество анализируемых чисел), певый 18 и второй 19 сумматоры, первы 20 и второй 21 пороговые элементы.

В основу работы устройства положны следующие соотношения. Если все числа последовательности -разные, то число чисел больших и меньших медианы при строгом отношении равно k in-j

2 При нестрогом отношении (т.е. с

включением знака равно) приведенное

значение для данной последовательно

ти чисел увеличивается на единицу

k (m - 0/2 + 1 (m + I)/2.

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

Ное ей, будет для обоих случаев равно или больше k . Это правило используется для нахождения медианы.

Если при последовательном сравнении каждого из чисел со всеми остальными окажется, что количество чисел,не превьш1ающих значение данного числа, и чисел, равных с ним, включая и само это число, и одноврё- менно количество чисел, превышающих

количество

I

значение данного числа и равных с ним, будет больше или равно k (m + 1)/2, то это число и является медианой рассматриваемой последовательности чисел.

Номер Р порядковой статистики, отличный от медианы k .(m+l)/2, можно найти, если перераспределить

чисел в ранжированной последовательности, стоящих слева и справа от медианы, или количество чисел, больших и равных, меньших и равных по величине заданному числу. В этом случае получают номер Р k + о порядковой статистики, оп- ределенньш относительно медианы. Тогда количество чисел, стоящих слева от числа Р, включая и само число.

как

т+1 л -и

а колиI

чество чисел, стоящих справа, включая и само число, определяется как

т+1 +

где о - любое целое

полоI

жительное или отрицательное число,

т+1 не превышающее .

I

„gp статистики Р

Если номер числа отсчитывать не от медианы, а от начала последовательности, то приходят к исходному определению лторядковой статистики, т.е. количество чисел, меньших или равных числу Р, равно Р, а количество чисел, больших или равных по чине числу Р, равно m - (Р - 1) ю - Р + 1. Приравняв эти выражения друг другу, получают порядковый ноН1-Р+1, Р .

Эти соотношения затем используются для выбора порога срабатывания элементов устройства при выборе конкретного номера статистики из заданной последовательности чисел.

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

В исходном состоянии триггеры 5, 6 и счетчик 2 обнулены. С первого входа устройства на вход элемента И . 8 поступают тактовые импульсы разрешения записи кодов чисел в регистры П с информационньк шин второго входа устройства. Поскольку на первом и третьем входах логического элемента И 8, соединенных с инверсными выходами триггеров 5 и 6, имеются разрешающие потенциалы, поэтому тактовые импульсы, поступающие с первого входа устройства, проходят на выход этого элемента и через элемент ИЛИ 9 поступают на вход управления сдвигом содержимого регис 1}ров 11 сдвига, вызывая сдвиг содержимого регистров на один разряд вверх, а затем через элемент 10 задержки на вход управления записью этих регистров. В результате значение; числа с информационных входов устройства записывается в первые разряды регистров 11 сдвига.

После каждой записи числа в регистры значение кодов на.информационных входах обновляется, поэтому с каждым тактовым импульсом, поступающим на входы разрешения записи регистров, в них записывается новое число. Информационное слово хранится в одноименных разрядах всех регистров. Число разрядов регистров m соответствует количеству записываемых в них и обрабатываемых затем чисел. Импульсы с выхода элемента ИЛИ 9 могут использоваться вводным устройством в качестве сигнала обратной связи с действительной записи входной информации в информационные регистры сдвига. Количество записываемых в регистры информационных единиц (слов) соответствует количеству поступающих с выхода логического элемента И 8 через элемент ИЛИ 4 на вход счетчика 2 импульсов, которые подсчитываются им

Емкость счетчика 2 на единицу . меньше количества обрабатываемых слов, поэтому при записи в регистры 11 сдвига последнего информационного слова счетчик переполняется. Импульс переполнения с выхода старшего разря- .да счетчика 2, поступающий через элемент ИЛИ 3 и элемент 1 задержки на вход триггера 5, переключает его в единичное состояние. В результате этого элемент ШШ 8 закрывается, а элемент И 7 открывается и импульсы с генератора 13 тактовых импульсов через элементы И 7 и ИЛИ 4 начинают поступать на вход счетчика 2, меняя его содержимое. Значение кода счетчика соответствует порядковому номеру информационного слова, записанного в регистрах 11 сдвига,и номеру выбираемого в мультиплексорах 16 информационного канала. Поэтому при каждом изменении содержимого счетчика 2 изменяется значение кода на адресных входах мультиплексоров 16, а значит

и номер коммутируемого мультиплексорами канала.

В результате этого осуществляется коммутация информационных слов с выходов регистров 11 на входы элементов 17 сравнения. Каждый из элементов сравнения сравнивает между собой значения поданных на его входы чисел

и в зависимости от знака отношения между ними (, , вьщает на своих выходах соответствующие информационные сигналы. Сумматоры 18 и 19 суммируют поступающие со схем 17 сравнения на их входы сигналы, которые поступают на пороговые элементы 20 и 21. При выборе порядковой статистики, имеющей номер Р из m нечетных чисел, уровень срабатывания и„ порогового

элемента 20 выбирается исходя из сле- дукщего соотношения:

., ,

где - коэффициент передачи напря- жения сумматором;

и - уровень сигнала, соответствующий логической 1, а уровень срабатывания, порогового элемента 21 выбирается исходя из сле- дующего соотношения:

2U(m. .p,.

Для выбора медианы значения уровней срабатывания пороговых элементов 20 и 21 выбираются одинаковыми в соответствии со следующим выражением:

V.-iia V U(-,wa

Одновременное срабатывание двух пороговых элементов для какого-либо числа означает, что это число и является порядковой статистикой последовательности из m чисел С номером Р.

При превышении входным сигналом установленных в пороговых элементах 20 и 21 уровней срабатывания элементов на выходах элементов появляется информационный сигнал, соответствую- Щий логической 1. Появление на входах элемента И 15 сигналов, связанных с выходами пороговых элементов 20 и 21, при наличии разрешающего потенциала на третьем входе приводит к появлению на выходе элемента И 15 и

на связанном с ним управляющем входе двухвходовых элементов И 12 сигнала, разрешающего выдачу на выхог. устройства с выходов мультиплексоров 16

значения порядковой статистики анализируемой группы чисел.

Одновременно сигнал с выхода элемента И 15 поступает на вход тригге- ра 6, устанавливая его в единичное состояние, и на входы триггера 5, устанавливая его в нулевое состояние. В результате этого элемент И 7 закрывается и прекращается поступление им- пульсов с вькода этого элемента через элемент ИЛИ 4 на вход счетчика 2. Одновременно открывается элемент И 14, поэтому приходящий на его вход с первого входа устройства тактовый им- пульс приходит на выход этого элемента и на управляющие входы регистров II, вызывая сдвиг содержимого этих регистров на один разряд, этот же, но задержанный элементом 10 задержки д; сигнал, поступающий на другие управляющие входы регистров, разрешает Запись в них очередного числа с информационных входов устройства.

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

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

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

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

0

5 0 5

0

5

0

входу первого элемента ИЛИ, отличающееся тем, что, с целью повьшения быстродействия, в него введены п мультиплексоров, га элементов сравнения (т - количество анализируемых чисел), два элемента задержки, группа элементов И, два элементаИПИ, два сумматора и два пороговых элемента, причем выход первого элемента ИЛИ соединен со счетным входом счетчика, разрядный вькод которого подключен к адресным входам мультиплексоров, а выход переноса счетчика соединен с первым входом второго элемента ИЛИ, выход которого через первый элемент задержки подключен к установочному входу первого триггера и к входу сброса второго триггера, инверсный выход которого подключен к первому входу третьего элемента И, вторые вхо-ды второго и третьего элементов И являются входом разрешения записи устройства, инверсный выход первого триггера соединен с третьим входом третьего элемента И, выход которого подключен к второму входу первого элемента ИЛИ и к первому входу третьего элемента ИЛИ, второй вход которого соединен с вторым входом второго элемента ИЛИ и с выходом второго элемента И, а выход подключен к входам управления сдвигом регистров сдвига и через второй элемент задержки - с входами разрешения записи регистров сдвига, выходы которых соединены с информационными входами соот- ветствуюддсх мультиплексоров, i-й разряд (i 1,п) первого информчционно- го входа j-ro элемента сравнения (j 1,m) соединен с i-м разрядом выхода j-ro регистра сдвига, каждый 1-й разряд второго информационного входа j-ro элемента сравнения соединен с выходом i-rp мультиплексора, который подключен к первому входу i-ro элемента И группы, выходы которых являются разрядным выходом устройства, вторые входы элементов И группы соединены с входами сброса первого триггера и счетчика, с установочным входом второго триггера и выходом четвертого элемента И, выход Равно j-ro элемента сравнения соединен с j-ми входами первого и второго маторов, выход Меньше j-ro элемента сравнения подключен к (m+j)-My входу первого сумматора, выход которого соединен с входом первого поро9 150993610

гового элемента, выход которого под-рого подключен к входу второго поро- ключен к первому входу четвертогогового элемента, выход которого сое- элемента И, выход Больше j-ro эле-динен с вторым входом четвертого элемента сравнения соединен с (m+j)-Mмента И, третий вход которого соеди- входом второго сумматора, выход кото-йен с прямым выходой первого триггера.

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