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

 

Изобретение относится к вычислительной технике и может быть использовано в быстродействумицпс системах цифровой обработки одномерных и двумерных сигналов, в частности, для медленной фильтрации изображений с целью подавления импульсных помех. Цепь изобретения - повышение быстро- , действия устройства путем обеспечения конвейерного режима обработки последовательностей чисел. Устройство содержит входные регистры, регистр порога , сумматор для сложения п одноразрядных чисел, сумматор, узлы анализа , буферные триггеры, буферные регистры , элементы НЕ. Каждый узел анализа содержит элементы ИСКЛЮЧАЮЩЕЕ ИЛИ П, группы элементов И, триггер, регистр-указатель, регистр столбца, коммутатор, регистр порога, сумматор Для сложения п одноразрядных чисел, сумматор со знаковым разрядом. Устройство анализирует все разряды чи- § сел, начиная со старшего разряда. После анализа каждого разряда чисел выдается значение очередного разряда вычисляемой порядковой статистики, имеющей номер N. 1 ил.

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

С00ИАЛИСТИЧЕСКИХ

РЕСПУБЛИН (50 4 G 06 F 7/02

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

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

ПО.ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

H А BTOPCHOlVIV СВИДЕТЕЛЬСТВУ (21 ) 4210934/24-24 (22) 18.03.87(46) 30.10.88. Вюл. В 40 (72) А.В. Василькевич, А.Г. Дмитриев и Ю.А. Кипецкий (53) 681.3(088.8) (56) Авторское свидетельство СССР

Ф 607226, кл. G 06 F 15/36, 1975.

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

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

ИЗ n m-РАЗРЯДНЫХ ДВОИЧНЫХ ЧИСЕЛ (57) Изобретение относится к вычислительной технике и может быть использовано в быстродействующих системах цифровой обработки одномерных и двумерных сигналов, в частности, для медленной фильтрации изображений с целью подавления импульсных помех.

„„SU„„1434424 А 1

Цель изобретения — повышение быстродействия устройства путем обеспечения конвейерного режима обработки последовательностей чисел . Устройство содержит входные регистры, регистр порога, сумматор для сложения и оцноразрядных чисел, сумматор, узлы анализа, буферные триггеры, буферные регистры, элементы HE. Каждый узел анализа содержит элементы ИСКЛЮЧАКЩЕЕ

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

1434424

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

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

1, ему в данной последовательности. t5

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

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

На чертеже приведена функциональ- 25 ная схема устройства.

Устройство содержит m и-разрядньгх входных регистров 1, ...1„, входной регистр порога 2, сумматор 3 для сложения и одноразрядных чисел, сумматор .4, m-1 узлов анализа 5, ° 5„ буферных триггеров б, . (m-1)(ш-2) ; (ш-1 )(m-2) буферных регистров 7,,,m элементов НЕ 8 ...8, вход 9 тактовых импульсов и выходы 10,... 10 устройства. Каждый узел 5 анализа содержит и элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 40

ll, 11„ группы из и элементов И

12,... 12„., триггер 13, регистр-указатель 14, регистр 15, столбца, коммутатор 16, группу иэ и элементов И

17„... 17» регистр 18. порога, сумматор 19 для сложения и одноразрядньгх чисел, сумматор 20 со знаковым разрядом 21.

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

Перед началом работы устройства во входной регистр 2 порога заносится дополнительный код значения порога Т со знаком "-", которое равно— (n-И+1 ), где N — номер вычисляемой порядковой статистики. Например, если

55 вычисляется медиана из и двоичных;гйсел, то значение Т =(и+1)/2, при вычислении максимума„ т.е. при N=n, начальное значение порога равно, а при вычислении минимума, т.е. при

N=-l, равно и

По первому тактовому импульсу,, поступающему на вход 9, во входные регистры 1, 1 записываются. коды первой последовательности анализируемых чисел, причем в регистр 1 за.т писываются первые (старшие) разряды и чисел, в регистр l записываются вторые разряды и т.д. В регистр 1,„ записываются младшие m-разряды и чисел. Значения старших разрядов всех и чисел поступают из регистра 1» на входы сумматора 3 для сложения и одноразрядных чисел, и после суммирования код их суммы S поступает на первый вход сумматора 4, на второй вход которого поступает дополнительный код порога Т из входного регистра

2 порога, В сумматоре 4 выполняется сложение кодов, что в данном случае эквивалентно выполнению операции вычитания из S значения Т, так как в регистре 2 порог Т записан в дополнительном коде со знаком "-", а значение Sвсегда положительно. При этом возможны два следующих случая.

Если 87 Т, результат суммирования положительный, и на выходе знакового разряда сумматора 4 находится сигнал "0". Сигнал с выхода знакового разряда поступает на первые входы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 11„ ° ..11 первого узла 51 анализа, на вторые входы которых поступают старшие разряды последовательности чисел из входного регистра I В данном случае код из входного регистра 1, проходит через элементы ИСКЛЮЧАЮЩЕЕ ИЛИ

11, ... 11 „ и элементы И 12 „... 12 „ (на вторые входы которых поступают сигналы "1") на входы регистра-указателя 14 без изменений. Сигнал с выхода знакового разряда сумматора 4 поступает также на управляющий вход коммутатора 16 и разрешает прохождение кода через коммутатор 16 из входного регистра 18 порога первого узла

5 анализа, Кроме того, в качестве инверсного значения старшего разряда результата сигнал с выхода знакового разряда сумматора 4 поступает на вход т триггера 13 первого узла 5„ анализа.

По второму тактовому импульсу во входные регистры 1, ... 1,„ заносятся разF434424 ряды второй последовательности из и чисел . Инверсное значение кода резуль тата первой последовательности записывается в триггер 13. Значение поро- га Т из входного регистра 2 переписывается через коммутатор 16 в регистр 18 порога первого узла 5„ анализа. Значение кода вторых разрядов первой последовательности из и чисел переписывается в регистр 15 первого узла 5„ анализа. Значения кодов разрядов с третьего по ш первой последовательности переписываются в регистр

7 первого уровня. Для чисел, которые имели "0" в старшем разряде, в соответствующие разряды регистра-указателя 14 первого узла 5„ анализа .занесены "0". Это значит, что анализируемые числа, в старших разрядах кото- 20 рых были "0" исключаются из дальнейшего анализа, Если $ (Т, результат суммирования отрицательный, и на выходе знакового разряда сумматора 4 присутствует сиг- 25 нал "1". Этот сигнал поступает на управляющий вход коммутатора 16 и разрешает прохождение через коммутатор 16 дополнительного кода с выходов сумматора 4 на входы регистра 18 30 первого узла 5„ анализа. Кроме того, сигнал "1" поступает на первые входы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 111 ...11„ первого узла 5„ анализа, инвертируя код старших разрядов первой последо5 вательности, поступающий из.входного регистра

На входы регистра-указателя 14 узла 51 анализа через элементы И

12 ...12„ поступает код, в соответ- 40 ствующих разрядах которого "1" для тех чисел, которые имели "0" в старшем разряде. Тем самым числа, имею щие "1" в старшем разряде, из дальнейшего анализа исключаются. По вто- 45 рому тактовому импульсу во входные регистры 1„. ° .1,„ заносятся разряды второй последовательности и производится анализ из старших разрядов с помощью сумматоров 3 и 4. Вторые разряды первой последовательности записываются в регистр 15 столбца узла 51 анализа и производится их анализ с помощью элементов узла 5, анализа.* Третьи и т д разр дь1 пер- 55 вой последовательности переписываются в буферные регистры 7 первого уровня. Анализ вторых разрядов в первом узле 5, анализа выполняется только для тех чисел первой последовательности, для которых в соответствующих разрядах регистра-указателя 14 записаны "1".

В третьм такте во входные регистры 1, ...1 записываются разряды третьей последовательности и производится анализ старших разрядов с помощью сумматоров 3 и 4. В узле 5, анализа производится анализ вторых разрядов второй последовательности, в узле 5 — анализ третьих разрядов первой последовательности и т,д.

В-. m-м такте (где m-количество разрядов чисел) в узле 5 производитМ-ч ся анализ ш-х разрядов чисел и формируется инверсное значение младшеrom-го разряда поряДковой статистики первой последовательности. По ш-му тактовому импульсу в триггеры

6 нижнего уровня заносятся инверсные значения разрядов результата (с первого по m-1-й) После инвертирования с помощью элементов НЕ 8 1...8 на выходе 10„ ... 10 устройства выдается значение порядковой статистики первой последовательности.

В такте ш41å. нHа в bы хоoд е e 1!00....10„, устройства выдается значение порядкоковой статистики второй последовательности и т.д.

Таким образом, за P+m тактов на выходе устройства формируются порядковые статистики P последовательностей. формула изобретения

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

n m-разрядных чисел, содержащее m празрядных регистров, сумматор для сложения и одноразрядных чисел, входной регистр порога, сумматор, m групп элементов И, m элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, m триггеров, элементов НЕ, причем выходы разрядов регистров с первого по m-1-й соединены с первыми входами элементов И соответствующих групп, выходы разрядов входного регистра порога соединены с первой группой входов сумматора, вторая группа входов которого соединена с выходами сумматора для сложения. и одноразрядных чисел, первые входы элементов

ИСКЛЮЧАЮЩЕЕ ИЛИ объединены о т л ич а ю щ е е с я тем, что, с целью повышения быстродействия устройства путем обеспечения конвейерного режи5 1434424 6 ма обработки последовательностей чисел, в устройство введены m-1 (m-1)(m-2) входных регистров, бу(m-1)(m-2) ферных регистров, 2 триг.4 геров, m-l элементов НЕ и m--1 узлов анализа, )-я группа элементов И, : где j=l,2,..., (m-l), и -й и-разряд-lg ный регистр входят в состав j-го уз1 ла анализа и являются регистром столбца j-го узла анализа, который также включает и элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, вторую группу элементов И, триггер, 1б регистр-указатель, коммутатор, регистр . порога, сумматор для сложения одноразрядных чисел, сумматор, m-й п-разрядный регистр является m-м входным регистром, причем в каждом узле 2О анализа выходы элементов ИСКЛЮЧАЮЩЕЕ

ИЛИ соединены с первыми входами соот: ветствующих элементов И второй группы, выходы которых соединены с информационными входами регистра-указателя, 25 выходы разрядов которого соединены с . вторыми входами соответствующих эле ментов И первой группы, выходы которых соединены с входами сумматора для сложения и одноразрядных чисел,,вы- О ходы которого соединены с первой груп пой входов сумматора, вторая группа входов которого соединена с выкодами регистра порога, информационные вхо ды которого соединены с выходами коммутатора, вход тактовых импульсов устройства соединен с синхровходами всех триггеров и регистров, первая и вторая группы входов коммутатора первого узла анализа соединены соответственно с выходами разрядов вход- ного регистра порога и выходами сумматора, выход знакового разряда кото-! рого соединен с управляющим входом коммутатора, информационным входом триггера и первыми входами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ первого узла анализа, вторые входы элементов ИСКЛЮЧА10ЩЕЕ ИЛИ первого узла анализа соединены с выходами первого входного регистра и входами сумматора для сложении и одноразрядных чисел, информационные входы регистра столбца первого узла анализа соединены с выходами второго входного регистра, выходы разрядов регистра-указателя i-го узла анализа, где i-l,2,..., (m-2), соединены с вторыми входами элементов И второй группы i+1-го узла анализа, выходы элементов И первой группы i-го узла анализа соединены с первой, группой элементов ИСКЛЮЧАЮЩЕЕ ИЛИ

i+1-го узла анализа, вторые входы которых объединены и соединены с информационным входом триггера, управляющим входом коммутатора i+1-ãî узла анализа и выходом знакового pasряда сумматора i-ro узла анализа, выходы разрядов регистра порога и сумматора i-го узла анализа соединены с первой и второй группами входов коммутатора i+)-го узла анализа, выход триггера i-ro узла анализа соединен с. информационным входом К-ro буферного триггера, где К = 1 (m-з.-1), выход m-?-. го буферного триггера соединен с входом соответствующего элемента НЕ, информационные входы регистра столбца i+1-го узла анализа соединены через i буферных регистров с выходами i+2-ro входного регистра, выходы триггера и знакового разряда сумматора m-1-го узла анализа соединены соответственно с входами m-1-ro u m-го элементов НЕ, выходы m элементов HE являются выходами устройства, вторые входы второй группы элементов И первого узла анализа объединены и подключены к входу логической единицы устройства.

1 -34424

Составитель В. Журавлев

Техред Л.Сердюкова Корректор О. Кравцова

Редактор И. Касарда

Тираж 704 Подписное

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

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

Заказ 5555)50

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