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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИН А 1 19 5114 С 06 Р 15/ ОСУДАРСТВЕННЫЙ НОМИТЕТО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМРИ ПНТ СССР1 1;803 ХРГА",; ; . ОПИСАНИЕ ИЗОБРЕТЕНИЯ Р 35 стичес ский.Логи СССР983.СР985. тельствоР 7/02,льство СР 7/02,НИЯ ПОРЕЛЬНОСТИ к вычисли ой киберзовано в сиги ВТОРСНОМУ СВИДЕТЕЛЬСТВУ(54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛ КОВЫХ СТАТИСТИК ПОСЛЕДОВАТ ДВОИЧНЫХ ЧИСЕЛ(57) Изобретение относится тельной технике и техничес нетике и может быть испол системах цифровой обработки например для ранговой фильтрации сигналов, в системах обработки изображений с целью улучшения качестваизображений и подавления шумов. Цельизобретения - повьппение быстродействия. Устройство срдержит два элемента задержки 1 и 10, счетчик 2, триэлемента ИЛИ 3, 4 и 9, два триггера5 и 6, четыре элемента И 7, 8, 14и 15, и регистров сдвига,11 (и - максимальная разрядность анализируемыхчисел), группу элементов И 12, генератор тактовых импульсов 13, и мультиплексоров 6, ш элементов сравнения 17 (п 1 - количество анализируемыхчисел), два сумматора 18 и 19 и двапороговых элемента 20 и 21. Повышение быстродействия достигается засчет пословной, а не поразрядной, обработки информационного массива. ил.третьем входах логического элементаИ 8, соединенных с инверсными выхода-ми триггеров 5 и 6, имеются разрешающие потенциалы, поэтому тактовые им 3 150993Изобретение относится к вычислительной технике и технической кибернетике и может быть использовано всистемах цифровой обработки сигналов,например, для ранговой фильтрациисигналов, в системах обработки изображений с целью улучшечия качестваизображений и подавления шумов,Цель изобретения - повышение быст Ородействия .На чертеже изображена структурнаясхема устройства для вычисления порядковых статистик последовательности двоичных чисел. 15Устройство содержит первый элемент 1 задержки, счетчик 2, второй 3и первый 4 элементы ИЛИ, первый 5 ивторой 6 триггеры, первый 7 и третий8 элементы И, третий 9 элемент ИЛИ, 2 Овторой 1 О элемент задержки, и регистров сдвига 11 (и - максимальная:разрядность анализируемых чисел),группу элементов И 12, генератор 13тактовых импульсов, второй 14 и четвертый 15 элементы И, и мультиплексоров 16, тп элементов 17 сравнения (тп -количество анализируемых чисел), первый 18 и второй 19 сумматоры, первый20 и второй 21 пороговые элементы, 3 ОВ основу работы устройства положены следующие соотношения. Если всечисла последовательности разные, точисло чисел больших и меньших медианы при строгом отношении Равно Е = 35т 2При нестро гом отношении (т. есвключением знака р.авно) приведенноезначение для данной последовательности чисел увеличивается на единицу1 с (тп - 1)/2 + 1 = (ш + 1)/2.На практике имеют место и такиепоследовательности, у которых несколько чисел по своему значению.могут быть равны медиане, В этом случае происходит перераспределение,чи-:сел и, тогда количество чисел, непревышающих значения медианы и равное ей, будет для обоих случаев равно или больше 1 . Это правило используется для нахождения медианы,Если при последовательном сравнении каждого из чисел со всеми остальными окажется, что количествочисел не превышающих значение данного числа, и чисел, равных с ним,включая и само зто число, и одновременно количество чисел, превышающих 6 4значение данного числа и равных с ним, будет больше или равноЕ(ш + 1)/2, то это число и является медианой рассматриваемой последовательности чисел .Номер Р порядковой статистики, отличный от медианы 1 с =,(ш+1)/2, можно найти, если перераспределить количество чисел в ранжированной последовательности, стоящих слева и справа от медианы, или количество чисел, больших и равных, меньших и равных по величине заданному числу. В этом случае получают номер Р = = 1 + 3 порядковой статистики, определенный относительно медианы. Тогда количество чисел, стоящих слева от числа Р, включая и само число, 1ш+1определяется как ---- 6 а коли 2 чество чисел, стоящих справа, включая и само число, определяется как в+1-- + , где й - любое целое положительное или отрицательное число,тп+ не превышающее --- . 2 Если номер числа отсчитывать неот медианы, а от начала последовательности, то приходят к исходному определению порядковой статистики, т.е. количество чисел, меньших или равных числу Р, равно Р, а количество чисел, больших или равных по величине числу Р, равно т - (Р - 1) = ш - Р + 1. Приравняв эти выражения друг другу, получают порядковый нош+1мер статистики Р= ш-Р+1, Р =Эти соотношения затем используются для выборапорога срабатывания элементов устройства при выборе конкретного номера статистики из заданнойО последовательности чисел.Устройство работает следующим образом.В исходном состоянии триггеры 5, 6 и счетчик 2 обнулены. С первого входа устройства на вход элемента И 8 поступают тактовые импульсы разрешения записи кодов чисел в регистры 11 с информационных шин второго входа устройства. Поскольку на нервом ипульсы, поступающие с первого входаустройства, проходят на выход этогоэлемента и через элемент ИЛИ 9 поступают на вход управления сдвигомсодержимого регистров 11 сдвига, вызывая сдвиг содержимого регистров наодин разряд вверх, а затем через элемент 10 задержки на вход управлениязаписью этих регистров. В результатезначение числа с информационных входов устройства записывается в первыеразряды регистров 11 сдвига,После каждой записи числа в регистры значение кодов на.информационных входах обновляется, поэтому скаждым тактовым импульсом, поступающим на входы разрешения записи регистров, в них записывается новое число, Информационное слово хранится водноименных разрядах всех регистров.Число разрядов регистров ш соответствует количеству записываемых в нихи обрабатываемых затем чисел. Импульсы с выхода элемента ИЛИ 9 могутиспользоваться вводным устройством вкачестве сигнала обратной связи сдействительной записи входной информации в информационные регистры сдвига. Количество записываемых в регистры информационных единиц (слов соответствует количеству поступающих свыхода логического элемента И 8 через элемент ИЛИ 4 на вход счетчика 2импульсов, которые подсчитываются им.Емкость счетчика 2 на единицу,меньше количества обрабатываемыхслов, поэтому при записи в регистры11 сдвига последнего информационногослова счетчик переполняется. Импульспереполнения с выхода старшего разряда счетчика 2, поступающий через элемент ИЛИ 3 и элемент 1 задержки навход триггера 5, переключает его вединичное состояние. В результатеэтого элемент ИЛИ 8 закрывается, аэлемент И 7 открывается и импульсы сгенератора 13 тактовых импульсов через элементы И 7 и ИЛИ 4 начинают поступать на вход счетчика 2, меняя егосодержимое. Значение кода счетчикасоответствует порядковому номеру информационного слова, записанного врегистрах 11 сдвига,и номеру выбираемого в мультиплексорах 16 информационного канала, Поэтому при каждомизменении содержимого счетчика 2 изменяется значение кода на адресныхвходах мультиплексоров 16, а значит и номер коммутируемого мультиплексорами канала.В результате этого осуществляется 5коммутация информационных слов с выходов регистров 1 на входы элементов 17 сравнения. Каждый из элементов сравнения сравнивает между собойзначения поданных на его входы чисели в зависимости от знака отношениямежду ними (=, (,вьщает на своихвыходах соответствующие информационные сигналы, Сумматоры 18 и 19 суммируют поступающие со схем 17 сравне ния на их входы сигналы, которые поступают на пороговые элементы 20 и2. При выборе порядковой статистики,имеющей номер Р из ш нечетных чисел,уровень срабатывания Б порогового 20 элемента 20 выбирается исходя из следующего соотношения;Ц,По20 ргде- коэффициент передачи напря жения сумматором;1 - уровень сигнала, соответствующий логической "1",а уровень срабатывания порогового элемента 21 выбирается исходя из сле дующего соотношения;(+11 12 1(щ-р) фДля выбора медианы значения уровней срабатывания пороговых элементов 3520 и 21 выбираются одинаковыми в соответствии со следующим выражением;01, У ) Б 1(Одновременное срабатывание двух 40 пороговых элементов для какого-ли 5 очисла означает, что это число и является порядковой статистикой последовательности из ш чисел с номером Р. При превышении входным сигналом установленных в пороговых элементах 20 и 21 уровней срабатывания элементов на выходах элементов появляется информационный сигнал, соответствующий логической "1". Появление на входах элемента И 15 сигналов, связанных с выходами пороговых элементов 20 и 21, при наличии разрешающего потенциала на третьем входе приводит к появлению на выходе элемента И 15 и на связанном с ним управляющем входе двухвходовых элементов И 12 сигнала, разрешакицего выдачу на выход устройства с выходов мультиплексоров 16значения порядковой статистики анализируемой группы чисел.Одновременно сигнал с выхода элемента И 15 поступает на вход тригге 5 ра 6, устанавливая его в единичное состояние, и на входы триггера 5, устанавливая его .в нулевое состояние. Врезультате этого элемент И 7 закрывается и прекращается поступление им пульсов с выхода этого элемента через элемент ИЛИ 4 на вход счетчика 2. Одновременно открывается элемент И 14, поэтому приходящий на его вход с первого входа устройства тактовый им пульс приходит на выход этого элемента и на управляющие входы регистров 11, вызывая сдвиг содержимого этих регистров на один разряд, этот же, но задержанный элементом 10 задержки 1 20 сигнал, поступающий на другие управ-, ляющие входы регистров, разрешает запись в них очередного числа с информационных входов устройства.Далее импульс с выхода элемента И 25 14 через элемент ИЛИ 3 и элемент 1 задержки поступает на вход триггера 6, переключая его в инверсное состояние, в результате чего логический элемент И 14 закрывается, и на 1.ход 30 триггера 5, включая его в единичное состояние, при этом логический элемент И 7 открывается и описанный цикл обработки информации повторяется е 35Устанавливая различные значения уровней срабатывания пороговых элементов 20 и 21 в соответствии с приведенным выражением, можно находить значение любого члена порядковой ста тистики в последовательности обрабатываемых чисел. Формула изобретения45Устройство для вычисления порядковых статистик последовательности дво-,ичных чисел, содержащее счетчик,два триггера, четыре элемента И,первый элемент ИЛИ, и регистров сдвига(и - максимальная разрядность анализируемых чисел), информационные входы которых являются информационнымивходами устройства, и генератор тактовых импульсовпрямые выходы первого и второго триггеров соединены спервыми входами соответственно первого и второго элементов И, выход первого элемента И подключен к первому входу первого элемента ИЛИ, о т л ич а ю щ е е с я тем, что, с целью повышения быстродействия, в него ввеВ дены и мультиплексоров, ш элементов сравнения (ш - количество анализируемых чисел), два элемента задержки, группа элементов И, два элемента ИЛИ, два сумматора и два пороговых элемента, причем выход первого элемента ИЛИсоединен со счетным входом счетчика,разрядный выход которого подключен кадресным входам мультиплексоров, авыход переноса счетчика соединен спервым входом второго элемента ИЛИ,выход которого через первыйэлементзадержки подключен к установочномувходу первого триггера и к входусброса второго триггера, инверсныйвыход которого подключен к первомувходу третьего элемента И, вторыевходы второго и третьего элементов Иявляются входом разрешения записиустройства, инверсный выход первоготриггера соединен с третьим входомтретьего элемента И, выход которогоподключен к второму входу первогоэлемента ИЛИ и к первому входу третьего элемента ИЛИ, второй вход которого соединен с вторым входом второго элемента ИЛИ и с выходом второго элемента И, а выход подключен к входам управления сдвигом регистровсдвига и через второй элемент задержки - с входами разрешения записи ре. -гистров сдвига, выходы которых соедииены с информационными входами соответствующих мультиплексоров, 1-й разряд (д = 1,п) первого информчционного входа 1-го элемента сравнения (31,ш) соединен с -м разрядом выхода 3-го регистра сдвига, каждый д-йразряд второго информационного входа3-го элемента сравнения соединен свыходом -го мультиплексора, которыйподключен к первому входу -го элемента И группы, выходы которых являются разрядным выходом устройства, вторые входы элементов И группы соединены с входами сброса первого триггера и счетчика, с установочным входом второго триггера и выходом четвертого элемента И, выход "Равно" 3-го элемента сравнения соединен с 3-ми входами первого и второго сумматоров, выход "Меньше" 1-го элемента сравнения подключен к (ш+1)-му входу первого сумматора, выход которого соединен с входом первого поро150993610 Составитель Е. УуртинРедактор М.Бланар Техред, Л.Сердюкова Корректор И.Шароши Заказ 5816/49 Тираж 668 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб., д. 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101 гового элемента, выход которого подключен к первому входу четвертого элемента И, выход "Больше" 1-го элемента сравнения соединен с (ш+1)-м входом второго сумматора, выход кото 5 рого подключен к входу второго порогового элемента, выход ко.торого сое- динен с вторым входом четвертого элемента И, третий вход которого соединен с прямым выходом первого триггера.