Устройство для вычисления порядковых статистик последовательности @ @ -разрядных двоичных чисел
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОРЯДКОВЫХ СТАТИСТИК ПОСЛЕДОВАТЕЛЬНОСТИ п т-РАЗРЯДНЫХ ДВОИЧНЫХ ЧИСЕЛ, содержащие п т-разрядных регистров и групп элементов И, п т-входовых элементов ИЛИ, п триггеров, п. элеиентов ИСКЛЮЧАЩЕЕ ИЛИ, причем выходы регистров поразрядно соединены с первыми входами Элементов И соответствующей группы, выходы которых соединены с входами соответствующего твходового элемента ИЛИ, а входы установки триггеров в 1 - с входом сброса устройства, вторые входы одноименных элементов И всех групп подключены к соответствующим шинам управления поразрядным сравнением, третьи входы элементов И каждой группы соединены с выходами соответствующих триггеров, выходы т-входовых элементов ИЛИ соединены с первыми входами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, вторые входы которых объединены, а выходы соединены с входами установки в ноль соответствующих триггеров, отличающееся тем, что, с целью расширения функциональных возможностей устройства путем обеспечения вычисления любой заданной порядковой статистики последовательности чисел, в него введены управляющий т-входовый элемент ИЛИ, сумматор, регистр порога, элемент НЕ, сумматор для сложения п одноразрядных чисел, входы которого соединены с выходами соответствующих т-входовых элементов СЛ ИЛИ, а выходы - с первой группой входов сумматора, вторая группа входов которого подключена к выходам регистра порога, установочные входы которого соединены с выходами разрядов сумматора, выход знакового разряда которого подключен к входу управления записью регистра порога и вхо4 ду элемента НЕ, выходкоторого подключен к вторым входам всех элементов ИСКЛЮЧАЩЕЕ ИЛИ и является выходом устройства, вход синхронизации сумматора соединен с выходом управляющего т-входового элемента ИЛИ, входы которого подключены к шинам управления поразрядным сравнением.
2 А
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИ4ЕСНИХ
РЕСПУБЛИК (l9) () 1) 4 (51) ОПИСАНИЕ ИЗОБРЕТ
К ABTOPCHOMV СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР .
llO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3640677/24-24 (22) 12.09,83 (46) 07.03.85. Бюл. ¹- 9 (72) В.В. Грицык, А.Ю. Луцык и P.M. Паленичка (71) Физико-механический институт им, Г.В, Карпенко (53) 681.325(088. 8) (56) 1. Авторское свидетельство СССР
¹ 660077222266,, кKл . G F 15/36, 1975.
Авторское свидетельство СССР № 966690, кл. G 06 F 7/02, 1981 (прототип). (54)(57) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ
ПОРЯДКОВЫХ СТАТИСТИК ПОСЛЕДОВАТЕЛЬНОСТИ n m-РАЗРЯДНЫХ ДВОИЧНЫХ ЧИСЕЛ, содержащие и m-разрядных регистров и групп элементов И, n m-входовых элементов ИЛИ, и триггеров, и элементов
ИСКЛЮЧАЮЩЕЕ ИЛИ, причем выходы регистров поразрядно соединены с первыми входами злементов И соответствующей группы, выходы которых соединены с входами соответствующего mвходового элемента ИЛИ, а входы установки триггеров в "1" — с входом сброса устройства, вторые входы одноименных элементов И всех групп подключены к соответствующим шинам управления поразрядным сравнением, третьи входы элементов И каждой группы соединены с выходами соответствующих триггеров, выходы ш-входовых элементов ИЛИ соединены с первыми входами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, вторые входы которых объединены, а, выходы соединены с входами установки в ноль соответствующих триггеров, о т л и ч а ю ш е е с я тем, что, с целью расширения функциональных возможностей устройства путем обеспечения вычисления любой заданной порядковой статистики последовательности чисел, в него введены управляющий
m-входовый элемент ИЛИ, сумматор, регистр порога, элемент НЕ, сумматор для сложения и одноразрядных чисел, входы которого соединены с выходами соответствующих ш-входовых элементов
ИЛИ, а выходы — с первой группой входов сумматора, вторая группа входов которого подключена к выходам регистра порога, установочные входы которого соединены с выходами разрядов сумматора, выход знакового разряда которого подключен к входу управления записью регистра .порога и входу элемента НЕ, выход которого подключен к вторым входам всех элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и является выходом устройства, вход синхронизации сумматора соединен с выходом управляющего ш-входового элемента ИЛИ, входы которого подключены к шинам управления поразрядным сравнением.
1144102
Изобретение относится к вычислительной технике и технйческой кибернетике и может быть использовано в системах цифровой обработки одномерных и двумерных сигналов (изображений), например, для медианной фильтрации сигналов с целью подавления шума.
Порядковой статистикой последовательности из и чисел., имеющей номер 10
N, называют то число, для которого существует ровно N-1 чисел, меньших или равных ему по величине, и ровно (и-/N-1/) чисел, больших или равных ему из данной последовательности.
Примером порядковых статистик, часто используемых при обработке и распознавании сигналов, являются медиана, минимальный или максимальный элементы последовательности. 20
Известно устройство для определения медианы, содержащее источник чисел, блок управления, блоки анализа чисел, элемент И, линии задержки, ключи, элементы неравнозначкости, цифровые компараторы, элементы И, регистры, элементы ИЛИ )1j .
Недостатками этого устройства являются его сложность и малое быстродействие вследствие последователь- З0 ного сравнения чисел для определения медианы.
Наиболее бЛизким по техническому решению к предлагаемому устройству является устройство для выделения З5 экстремального числа из п m-разрядных двоичных чисел, содержащее n m-разрядных регистров для хранения двоичных чисел, m n-трехвходовых элементов
И,n m-входовых элементов ИЛИ, и эле- щ0 ментов ИСКЛЮЧАЮЩЕЕ ИЛИ, и триггеров, и входовый элемент ИЛИ, причем выходы регистров поразрядно соединены с первыми входами элементов И соответствующей группы, выходы которых 45 соединены с входами соответствующего и-входового элемента ИЛИ, входы установки триггеров в единицу — с входом сброса устройства, вторые входы одноименных элементов И всех групп 50 соединены с соответствующими шинами управления поразрядным сравнением устройства, третьи входы элементов
И каждой группы соединены с выходами соответствующих .триггеров и с вы- Ы ходами кода номера регистра, содержащего экстремальное число устройства, выходы ш-входовых элементов ИЛИ соединены с первыми входами соответствующих элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и с соответствующими входами п-вхо дового элемента ИЛИ, выход которого соединен с вторыми входами элементов
ИСКЛЮЧАЮЩЕЕ ИЛИ и является выходом кода экстремального числа устройства, выходы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединены с нулевыми входами соответствующих триггеров (2) .
Однако устройство позволяет вычислять только, две порядковые стати стики, а именно максимум или минимум, в то время когда при обработке сигналов требуется вычислять и другие порядковые статистики, например, медиану последовательности чисел.
Цель изобретения — расширение функциональньг. . возможностей устройства путем вычисленчя любой заданной порядковой статистики последовательности чисел, Поставленная цель достигается тем,. что в устройство для вычисления порядковьп статистик последовательности n m-разрядных двоичных чисел, содержащее n m-разрядных регистров и: групп элементов И, n m-входовых элементов ИЛИ, и триггеров, и элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, причем выходы регистров поразрядно соединены с первыми входами элементов И соответствующей группы, выходы которых соединены с входами соответствующего mвходового элемента ИЛИ, а входы установки триггеров в "1" -с входом сброса устройства, вторые входы одноименных элементов И всех групп подключены к соответствующим шинам управления поразрядным. сравнением, третьи входы элементов И каждой группы соединены с выходами соответствующих триггеров, выходы m-входовых элементов ИЛИ соединены с первыми входами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, вторые входы которых объединены, а выходы соединены с входами установки в ноль соответствующих триггеров, введены управляющий ш-входовый элемент ИЛИ, сумматор, регистр порога, элемент НЕ, сумматор для сложения и одноразрядных чисел. входы кЬторого соединены с выходами соответствующих
m-входовых элементов ИЛИ, а выходы— с первой группой входов сумматора, вторая группа входов которого подключена к выходам регистра порога, установочные входы которого соеди1144102 иены с выходами разрядов сумматора, выход знакового разряда которого подключен к входу управления записью регистра порога и входу элемента HF, выход которого подключен к вторым входам всех элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и является выходом устройства, вход синхронизации сумматора соединен с выходом управляющего m-входового элемента ИЛИ, входы которого подключе- 10 ны к шинам управления поразрядным сравнением.
На фиг. 1 показана структурная схема предлагаемого устройства; на фиг. 2 — схема сумматора для сложения и одноразрядных двоичных чисел.
Устройство содержит n m-разрядных регистров 1, и групп элементов И 2, m и-входовь»х элементов ИЛИ 3, и элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 4, и триггеров 5, шины 6 управления, сумматор 7 для сложения и одноразрядных двоичных чисел, регистр 8 порога, управляюший m-входовый элемент ИЛИ 9, сумматор 10 со знаковым разрядом 11 и. элемент НЕ 12.
Устройство работает следующим образом.
Перед началом работы устройства в и m-разрядных регистрах 1 записыва30 ются n m-разрядные коды анализируемых двоичных чисел. а а ...а ь ь,...ь„;
35 . 2 первый разряд которых является старшим. Все и триггеров 5 устанавливают-40 ся в начальное единичное состояние путем подачи единичного импульса на шину установки триггеров в "I". В регистр 8 записывается дополнительный код начального значения порога Т со 45 знаком минус, которое в данном случае равно — (n-0+1), где М вЂ” номер вычисляемой порядковой статистики. Например, если вычисляется медиана последователь1»ости и двоичных чисел, 50 то значение Т = и/2 при вычислении максимума, т.е. при N=n, начальное значение порога равно единице, а при вычислении минимума, т.е. при N=i, равно и. 55
Для запуска устройства на шину управления первого разряда подается единичный импульс при отсутствии управляюших импульсов на других шинах управления. При этом на первый вход
m-входовых элементов ИЛИ 3 поступает сигнал, соответствующий содержимому первого разряда всех m-разрядных регистров, а на остальные (m-1) входы сигналы, соответствующие "0 !, так как все триггеры 5 находятся в на-: чальном состоянии "1", а их выходы соединены с третьими входами соответствующих схем И 2. Тогда на выходах и ш-входовых .элементов ИЛИ 3 присутствуют сигналы, соответствующие значениям первых разрядов всех анализируемых чисел. Эти сигналы поступают на входные шины сумматора
7 цля сложения и одноразрядных чисел и после суммирования код их суммы поступает на первый вход сумматора
10, на второй вход которого поступает дополнительный код порога Т из выхода регистра 8, При подаче синхронизирующего импульса с выхода mвходового элемента ИЛИ 9 в сумматоре
10 выполняется сложение кодов входных чисел, что в данном случае эквивалентно выполнению операции вычитания из S значения Т, так как в
/ регистре 8 порог записан в дополни г тельном коде, а значение S всегда положительно. При этом возможны сле« дующие два случая.
Если S > Т, результат суммирования. положительный и на выходе знакового разряда 11 находится сигнал "0".
Сигнал с выхода знакового разряда
11 после инвертирования элементом
НЕ подается на выход устройства в качестве значения первого разряда вычисляемой порядковой статистики.
Одновременно этот сигнал подается на второй вход элементов ИСКЛЮЧАЮЩЕЕ
ИЛИ 4, на первый вход которых поступают сигналы с выходов элементов
ИЛИ 3. В этом случае на выходе элементов ИСКЛЮЧАКМЦЕЕ ИЛИ 4 будет сигнал
tI !!
1 для тех чисел, в первых разрядах которых записано значение "0".. При подаче с выходов элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 4 сигналов "1" на нулевые входы триггеров 5, устанавливаются в нулевое состояние те триггеры, если в соответствующих им регистрах в ! первом разряде записаны кули. Это значит, что анализируемые числа, в . первых разрядах которых были нули, исключаются из дальнейшего анализа
1144102
20 вследствие связи триггеров 5 с трехвходовыми элементами И 2.
Если S (Т, результат суммирования отрицательный и на выходе знакового
l l It разряда 11 присутствует сигнал 1 . 5
Этот сигнал "1" с выхода знакового разряда 11 поступает на управляющий вход записи регистра 8 и после поступления этого сигнала в регистр 8 записывается дополнительный код 10 числа на выходе сумматора 10, как новое значение порога Т. Сигнал "1" из выхода знакового разряда сумматора 10 через элемент НЕ 12 поступает на выход устройства и на вторые вхо- 15 ды элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 4, на первые входы которых поступают сигналы с выходов элементов ИЛИ 3. В этом случае на выходе элементов
ИСКЛЮЧАЮЩЕЕ ИЛИ 4 будет сигнал "1" для тех чисел, в первых разрядах ко11 I I торых было записано значение 1
Тогда путем подачи из элементов
ИСКЛЮЧА10ЩЕЕ ИЛИ 4 сигналов на нуле-. вые входы триггеров 5 устанавлива- 25 ются в нулевое состояние те триггеры, в соответствующих первых разрядах регистров которых записаны единицы. При этом из дальнейшего анализа исключаются те числа, в первых щ разрядах которых были единицы.
При подаче управляющего сигнала на шину управления второго разряда выполняется описанный анализ вторых разрядов тех чисел, триггеры которых З находятся в едничном состоянии после анализа первого разряда всех п чисел. При этом определяется значение второго разряда вычисляемой порядковой статистики и исключается из
40 дальнейшего анализа некоторое количество анализируемых чисел. Таким образом, при поочередной подаче управляющих импульсов на шины 6 управления выполняется анализ всех m разрядов задаиных и двоичных чисел и вычисляются m разрядов требуемой порядковой статистики.
Например, требуется определить максимУм последовательности чисел, но начальное значение порога равно единице. В этом случае сумма S анализируемых разрядов чисел меньше значения Т только тогда, когда все разряды равны нулю. Это значит, что функция всех новых введенных узлов эквивалентна функции одного и-входного элемента ИЛИ, который выполняет ее в известном устройстве для выделения экстремального числа из nmразрядных двоичных чисел.
Сумматор для сложения и одноразрядных чисел содержит К,групп сумматоров параллельного сложения чисел, где К = 1оя и, причем i-я группа сумматоров содержит (и/2 ) параллельно действующих i-разрядных сумматоров, выходы которых соединены с входами сумматоров (i + t)-й группы.
Сумматор для сложения и одноразрядных чисел работает следующим образом.
При подаче на его входные шины кодов одноразрядных двоичных чисел, одноразрядные сумматоры первой группы выполняют параллельное попарное суммирование этих кодов и результаты суммирования поступают на входы двухразрядных. сумматоров второй группы. Этот процесс параллельнопоследовательного суммирования продолжается до сумматора той группы, на выходе которого получаем код суммы и одноразрядных двоичных чисел, состоящий из 1og 1144102 1144102! i-oz zpgnno (Y 1/8 Составитель Е. Иванова Редактор Р, Цицика Техред И.Гергель Корректор Е. Сирохман Тираж 710 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5 Заказ 931/40 Филиал IIIIII "Патент", r. Ужгород, ул, Проектная, 4!! 1!! + !! !!! !!! !!! !! 1 I I уППс7 !! 1 !! !!! ! (1 !!
