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

 

Изобретение относится к вычислительной технике и технической кибернетике и может быть использовано в системах цифровой обработки сигналов, например, для ранговой фильтрации сигналов, в системах обработки изображений с целью улучшения качества изображений и подавления шумов. Цель изобретения - повышение быстродействия. Устройство содержит два элемента задержки 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 ил.

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

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

РЕСПУБЛИН (19) (11) g1) 4 G 06 F 15/36

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

Н А ВТОРСЙОМУ СВИДЕТЕЛЬСТВУ

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

Il0 ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР

1 (21) 4397046/24-24 (22) 25 . 03. 88 (46) 23.09. 89. Бюп. h» 35 (71) Иинский радиотехнический институт (72) Ю.И.Тормьппев, А. В.Логиновский и Н.И.Мурашко (53) 681.3 (088.8) (56) Авторское свидетельство СССР

Р 1144102, кл . G 06 F 7/02, 1983.

Авторское свидетельство СССР

Р 1290295, кл. G 06 F 7/02, 1985. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОРЯДКОВЫХ СТАТИСТИК ПОСЛЕДОВАТЕЛЬНОСТИ

ДВОИЧНЫХ ЧИСЕЛ (57) Изобретение относится к вычислительной технике и технической кибернетике и может быть использовано в системах цифровой обработки сигналов, например для ранговой фильтрации сигналов, в системах обработки изображений с целью улучшения качества изображений и подавления шумов. Цель изобретения — повышение быстродействия. Устройство содержит два элемента задержки 1 и 10, счетчик 2, три элемента ИЛИ 3, 4 и 9, два триггера

5 и 6, четыре элемента И 7, 8, 14 и 15, и регистров сдвига,11 (n — максимальная разрядность анализируемых чисел), группу элементов И 12, генератор тактовых импульсов 13, и мультиплексоров 16, ш элементов сравнения 17 (m — количество анализируемых чисел), два сумматора 18 и 19 и два .пороговых элемента 20 и 21. Повышение быстродействия достигается за счет пословной, а не поразрядной, обработки информационного массива.l ил. третьем входах логического элемента

И 8, соединенных с инверсными выхода- ми триггеров 5 и 6, имеются разрешающие потенциалы, поэтому тактовые им3 150993

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

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

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

Устройство содержит первый элемент 1 задержки, счетчик 2, второй 3 и первый 4 элементы ИЛИ, первый 5 и второй 6 триггеры, первый 7 и третий

8 элементы И, третий 9 элемент ИЛИ, 2О второй 10 элемент задержки, и регистров сдвига 11 (n — максимальная: разрядность анализируемых чисел), группу элементов И 12, генератор 13 тактовых импульсов, второй 14 и четвертый 15 элементы И, и мультиплексоров 16, m элементов 17 сравнения (m— количество анализируемых чисел), первый 18 и второй 19 сумматоры, первый

20 и второй 21 пороговые элементы.

В основу работы устройства положены следующие соотношения. Если все числа последовательности разные, то число чисел больших и меньших медианы при стро ом отношении Равно Е = 35

m-1

При нестро гом отношении (т. е .. с включением знака р.авно) приведенное значение для данной последовательнос-.40 ти чисел увеличивается на единицу

k (m — 1)/2 + 1 = (m + 1)/2.

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

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

Номер P порядковой статистики, отличный от медианы k = .(ш+1)/2, можно найти, если перераспределить количество чисел в ранжированной последовательности, стоящих слева и справа от медианы, или количество чисел, больших и равных, меньших и равных по величине заданному числу.

В этом случае получают номер P =

= k + О порядковой статистики, определенный относительно медианы.

Тогда количество чисел, стоящих слева от числа Р, включая и само число, 1

m+1 определяется как — — — — 6 а коли2 чество чисел, стоящих справа, включая и само число, определяется как

m+1 — — +, где 3 — любое целое положительное или отрицательное число, тп+1 не превышающее — — —.

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

= m — P + 1. Приравняв эти выражения друг другу, получают порядковый нош+1 мер статистики Р= m-Р+1, Р =

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

0 последовательности чисел.

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

В исходном состоянии триггеры $, 6 и счетчик 2 обнулены. С первого входа устройства на вход элемента И

8 поступают тактовые импульсы разрешения записи кодов чисел в регистры

11 с информационных шин второго входа устройства. Поскольку на нервом и

1509936 пульсы, поступающие с первого входа устройства, проходят на выход этого элемента и через элемент ИЛИ 9 поступают на вход управления сдвигом содержимого регистров 11 сдвига, вызывая сдвиг содержимого регистров на один разряд вверх, а затем через элемент 10 sадержки на вход управления записью этих регистров. В результате значение числа .с информационных входов устройства записывается в первые разряды регистров 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!. При выборе порядковой статистики, имеющей номер P из m нечетных чисел, уровень срабатывания U„ ïoðoãoâoão

2р элемента 20 выбирается исходя из следующего соотношения: Пр Un > )Uð-, где — коэффициент передачи напря25 жения сумматором;

U — уровень сигнала, соответствующий логической "1", а уровень срабатывания порогового элемента 21 выбирается исходя из сле3р дующего соотношения: (+i) 1г !) (m-р)

Для выбора медианы значения уровней срабатывания пороговых элементов

20 и 21 выбираются одинаковыми в соответствии со следующим выражением: Б-.,) ъУ) Б,ИЯ

Одновременное срабатывание двух

40 пороговых элементов для какого-zw5o числа означает, что это число и яв1 ляется порядковой статистикой последовательности иэ ш чисел с номером P.

При превышении входным сигналом установленных в пороговых элементах

20 и 21 уровней срабатывания элементов на выходах элементов появляется информационный сигнал, соответствую50 щий лОгической 1 ПОЯВЛBBHe на ВХО дах элемента И 15 сигналов, связанных с выходами пороговых элементов

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

Одновременно сигнал с выхода элемента И 15 поступает на вход тригге5 ра 6, устанавливая его в единичное состояние, и на входы триггера 5, устанавливая его .в нулевое состояние.

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

11, вызывая сдвиг содержимого этих регистров на один разряд, этот же, но задержанный элементом 10 задержки 20 сигнал, поступающий на другие управ-, ляющие входы регистров, разрешает запись в них очередного числа с информационных входов устройства.

Далее импульс с выхода элемента И 25

l4 через элемент ИЛИ 3 и элемент 1 задержки поступает на вход триггера

6, переключая его в инверсное состояние, в результате чего логический элемент И 14 закрывается, и на .ход 30 триггера 5, включая его в единичное состояние, при этом логический элемент И 7 открывается и описанный цикл обработки информации повторяется е 35

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

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

Устройство для вычисления порядковых статистик последовательности дво-, ичных чисел, содержащее счетчик, два триггера, четыре элемента И,первый элемент ИЛИ, и регистров сдвига (и — максимальная разрядность анализируемых чисел), информационные входы которых являются информационными входами устройства, и генератор тактовых импульсов прямые выходы пер 55 вого и второго триггеров соединены с первыми входами соответственно первого и второго элементов И, выход первого элемента И подключен к первому входу первого элемента ИЛИ, о т л ич ающее ся тем, что, сцелью повышения быстродействия, в него введены и мультиплексоров, m элементов сравнения (m — количество анализируемых чисел), два элемента задержки, группа элементов И, два элемента ИЛИ, два сумматора и два пороговых элемента, причем выход первого элемента ИЛИ соединен со счетным входом счетчика, разрядный выход которого подключен к адресным входам мультиплексоров, а выход переноса счетчика соединен с первым входом второго элемента ИЛИ, выход которого через первый элемент задержки подключен к установочному входу первого триггера и к входу сброса второго триггера, инверсный выход которого подключен к первому входу третьего элемента И, вторые входы второго и третьего элементов И являются входом разрешения записи устройства, инверсный выход первого триггера соединен с третьим входом третьего элемента И, выход которого подключен к второму входу первого элемента ИЛИ и к первому входу третьего элемента ИЛИ, второй вход которого соединен с вторым входом второго элемента ИЛИ и с выходом второго элемента И, а выход подключен к входам управления сдвигом регистров сдвига и через второй элемент задержки — с входами разрешения записи регистров сдвига, выходы которых соедииены с информационными входами соответствующих мультиплексоров, i-й разряд (i = 1,n) первого информчционноro входа j-го элемента сравнения (j

1,m) соединен с i-м разрядом выхода j-го регистра сдвига, каждый i-й разряд второго информационного входа

g -го элемента сравнения соединен с выходом i-го мультиплексора, который подключен к первому входу z-го элемента И группы, выходы которых являются разрядным выходом устройства, вторые входы элементов И группы соединены с входами сброса первого триггера и счетчика, с установочным входом второго триггера и выходом четвертого элемента И, выход "Равно"

j-го элемента сравнения соединен с

j-ми входами первого и второго сумматоров, выход "Меньше" j-го элемента сравнения подключен к (m+j)-му входу первого сумматора, выход которого соединен с входом первого поро1509936

Составитель Е. Ууртин

Редактор M.Áëàíàð Техред, Л.Сердюкова

Корректор М.Шароши

Заказ 5816/49 Тираж 668 Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101 гового элемента, выход которого подключен к первому входу четвертого элемента И, выход "Больше" j-ro элемента сравнения соединен с (m+j)-м входом второго сумматора, выход кото5 рого подключен к входу второго порогового элемента, выход ко.торого сое- динен с вторым входом четвертого элемента И, третий вход которого соединен с прямым выходом первого триггера.