Устройство для вычисления порядковых статистик последовательностей из @ - @ -разрядных чисел Советский патент 1988 года по МПК G06F7/02 

4ib

go

4ib 4 Is9

iJ

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

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

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

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

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

Устройство содержит m п-разрядных входных регистров 1, ...1, входной регистр порога 2, сумматор 3 для сложения п одноразрядных чисел, сумматор 4, т-1 узлов анализа 5,...5

(m-l)(m-2)

2 {m-l)(m-2)

буферных триггеров 6;

буферных регистров 7,

m элементов НЕ 8...8, вход 9 тактовых импульсов и выходы 10,.о. 10 устройства. Каждый узел 5 анализа содержит п элементов ИСКЛЮЧАКНЦЕЕ ИЛИ 11.. 11 группы из п элементов И 12... триггер 13, регистр-зпса- затель 14, регистр 15. столбца,, коммутатор 16, группу из п элементов И 17.. 1 7f| , регистр 18. порога, сумма- тор 19 для сложения п одноразрядных чисел, сумматор 20 со знаковым раз-рядом 21 ,

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

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

5

0

5

0

5

с

0

5

начальное значение порога равно i, а при вычислении минимума, т.е. при , равно п .

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

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

Если , результат суммирования положительный, -и на выходе знакового разряда сумматора 4 находится сигнал Сигнал с выхода знакового разряда поступает на первые входы элементов ИСКЛЮЧАЩЕЕ ИЛИ 1 Ц ... 1 1 первого узла 5 анализа, на вторые входы которьк поступают старшие разряды последовательности чисел из входного регистра 1,. В данном случае код из входного регистра 1 проходит через элементы ИСКЛЮЧАЩЕЕ ИЛИ 11.. П f, и элементы И 12,... 1 2 „ (на вторые входы которых поступают сигналы 1) на входы регистра-указателя 14 без изменений. Сигнал с выхода знакового разряда сумматора 4 поступает также на управляющий вход коммутатора 16 и разрешает прохождение кода коммутатор 16 из входного регистра 18 порога первого узла 5, анализа. Кроме того, в качестве инверсного значения старшего разряда результата сигнал с выхода знакового разряда сумматора 4 поступает на вход триггера 13 первого узла 5 анализа. По второму тактовому импульсу во входные регистры 1-, ... f заносятся разряды второй последовательности из п чисел. Инверсное значение кода резуль тата первой последовательности запи- сьюается в триггер 13. Значение порега Т из входного регистра 2 переписывается через коммутатор 16 в регистр 18 порога первого узла 5 анализа. Значение кода вторых разрядов первой последовательности из п чисел переписьшается в регистр 15 первого узла 5 анализа. Значения кодов разрядов с третьего по m первой последовательности переписьтаются в регистр 7 первого уровня. Для чисел, которые имели О в старшем разряде, в соответствующие разряды регистра-указателя 14 первого узла 5 анализа занесены О. Это значит, что анализируемые числа, в старших разрядах кото- рых были О исключаются из дальнейшего анализа.

Если , результат сзгммирования отрицательный, и на вькоде знакового разряда сумматора 4 присутствует сиг- нал 1. Этот сигнал поступает на управляющий вход коммутатора 16 и разрешает прохождение через коммутатор 16 дополнительного кода с выходов сумматора 4 на входы регистра 18 первого узла 5 анализа. Кроме того, сигнал 1 поступает на первые входы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 1Ц ...4 первого узла 5 анализа, инвертируя код старших разрядов первой последо- вательности, поступающий из-входного регистра 1 .

На входы регистра-указателя 14 узла 5 анализа через элементы И 12...i2f, поступает код, в соответ- ствующих разрядах которого 1 для тех чисел, которые имели О в старшем разряде. Тем самым числа, имеющие 1 в старшем разряде, из дальнейшего анализа исключаются. По вто- рому тактовому импульсу во входные регистры 1 ... 1 заносятся разряды второй последовательности и производится анализ из старших разрядов с помощью сумматоров 3 и 4. Вторые разряды первой последовательности записываются в регистр 15 столбца узла 5 анализа и производится их анализ с помощью элементов узла 5, анализа. Третьи и т.д. разряды пер- вой последовательности переписываются в буферные регистры 7 первого уроня . Анализ вторых разрядов в первом узле 5i анализа выполняется только

для тех чисел первой последовательности, для которых в соответствующих разрядах регистра-указателя 14 записаны .

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

В-. т-м такте (где т-количество разрядов чисел) в узле 5 производитШ-1

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

В такте m-tl на выходе ...10 устройства выдается значение порядко ковой статистики второй последовательности и т.д.

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

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

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

{ra-t)(m-2) входных регистров,

буферных регистров,

(m-l)(m-2)

тригтов ИСКЛЮЧАЮЩЕЕ -ти первого .узла анализа, вторые входы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ первого узла аиализэг соединены с выходами первого входного регистра и входами сумматора для сложения п одноразрядных чисел, информационные вхо ды регистра столбца пер- вого узла анализа соединены с выхогеров, m-l элементов НЕ и m-l узлов анализа, j-я группа элементов И,

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

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

тов ИСКЛЮЧАЮЩЕЕ -ти первого .узла анализа, вторые входы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ первого узла аиализэг соединены с выходами первого входного регистра и входами сумматора для сложения п одноразрядных чисел, информационные вхо ды регистра столбца пер- вого узла анализа соединены с выходами второго входного регистра, вы- ходы разрядов регистра-указателя i-ro Формационным входом триггера, уп- равляющим входом коммутатора

узла анализа, где i-,2,,,, (m-2), соединены с вторыми входами элементов И второй.группы 1+1-го узла анализа, выходы элементов И первой группы i-ro узла анализа соединены с первой, группой элементов ИСКЛЮЧАЮЩЕЕ ИЛИ i+1-го узла анализа, вторые входы которых объединены и соединены с индами второго входного регистра, вы- ходы разрядов регистра-указателя i-ro Формационным входом триггера, уп- равляющим входом коммутатора

узла анализа и выходом знакового разряда сумматора i-ro узла анализа, выходы разрядов регистра порога и сумматора i-ro узла анализа соединены с первой и второй группами входов коммутатора i+1-го узла анализа, выход триггера i-ro узла анализа соединен с информационным входом К-го

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

сложения п одноразрядных чисел, вы- 30 буферного триггера, где К 1

(ш-i-l), выход Ш-1-ГО буферн триггера соединен с входом соо ствующего элемента НЕ, информа ные входы регистра столбца i+

ходы которого соединены с первой груп- пой входов сумматора, вторая группа входов которого соединена с выходами регистра порога, информационные входы которого соединены с выходами ком™ g анализа соединены через i буферных-регистров с выходами i+2-го входного регистра, выходы триггера и знакового разряда сумматора т-1-г узла анализа соединены соответствен но с входами m-l-го и т-го элемен тов НЕ, выходы ш элементов НЕ явля ются выходами устройства, вторые в ды второй группы элементов И перво го узла анализа объединены и подклю чены к входу логической единищз устройсогва.

мутатора, вход тактовых т-шпульсов устройства соединен с синхровходами всех триггеров и регистров, йервая и вторая группы входов коммутатора первого узла анализа соединены соот- ветственно с выходами разрядов входного регистра порога и выходами сумматора, выход знакового разряда которого соединен с управляющим входом коммутатора, информационным входом триггера и первыми входами элемен(ш-i-l), выход Ш-1-ГО буферного триггера соединен с входом соответствующего элемента НЕ, информационные входы регистра столбца i+1-го

анализа соединены через i бу

ферных-регистров с выходами i+2-го входного регистра, выходы триггера и знакового разряда сумматора т-1-го узла анализа соединены соответственно с входами m-l-го и т-го элементов НЕ, выходы ш элементов НЕ являются выходами устройства, вторые входы второй группы элементов И первого узла анализа объединены и подключены к входу логической единищз устройсогва.

t 7

/ m-f

./I 3

«Vf i of-f