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

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

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

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

Недостатками этого устройства являются его сложность и малое быстродействие вследствие последовательного сравнения чисел для определения

медианы. I

Наиболее б 1изким по техническому

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

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

Однако устройство позволяет вычислять только. ДВР. порядковые статистики, а именно максимум или минимум в то время когда при обработке сигналов требуется вычислять и другие порядковые ста )истики, например, медиану последовательности чисел.

Цель изобретения - расширение функциональны;: возможностей устройства путем вычисления любой заданной порядковой статистики последовательности чисел,

Постахзленная цель достигается темчто в устройство для вычисления порядковых статистик последовательности п т-разрядных двоичных чисел, содержащее п т-разрядных регистров и групп элементов И, п т-входовых элементов ИЛИ, п триггеров, п элементов ИСЮЧЮЧАЮШЕЕ ИЛИ, причем выходы регистров поразрядно соединены с первыми входами элементов И соответствующей группы, выходы которых соединены с входами соответствующего твходового элемента ИЛИ, а входы установки триггеров в 1 -с входом сброса устройства, вторые входы одноименных элементов И всех групп подключены к соответствующим шинам управления поразрядным сравнением, третьи входы элементов И каждой группы соединены с выходами соответствующих триггеров, выходы га-входовых элементов ШШ соединены с первыми входами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, вторые входы которых объединены, а выходы соединены с входами установки в ноль соответствующих триггеров, введены управляющий т-входовый элемент РШИ, сумматор, регистр порога, элемент НЕ, сумматор для сложения п одноразрядньгх чисел, входы кЬторого соединены с выходами со,ртветствующих га-входовых элементов ШШ, а выходы с первой группой входов сумматора, вторая группа входов которого подключена к выходам регистра порога, установочные входы которого соедийены с выходами разрядов сумматора, выход знакового разряда которого подключен к входу управления записью регистра порога и входу элемента НЕ, выход которого подключен к вторым входам всех элементов ИСКЛЮЧАЮЩЕЕ ИЛ и является выходом устройства, вход синхронизации сумматора соединен с выходом управляющего т-входового эле мента ИЛИ, входы которого подключе- ны к шинам управления поразрядным сравнением. На фиг. 1 показана структурная схема предлагаемого устройства; на фиг. 2 - схема сумматора для сложения п одноразрядных двоичных чисел. Устройство содержит п т-разрядных регистров 1, п групп элементов И 2, m п-входовых-элементов ИЛИ 3, п эле ментов ИСКЛЮЧАЩЕЕ ШШ 4, п триггеров 5, шины 6 управления, сумматор для сложения п одноразрядных двоичных чисел, регистр 8 порога, управляющий т-входовый элемент ИЛИ 9, сум матор 10 со знаковым разрядом 11 и элемент НЕ 12. Устройство работает следующим образом. Перед началом работы устройства п та-разрядных регистрах 1 записываются п т-разрядные коды анализируеМЬЕХ двоичных чисел. { г) Ь, bj... V, V...V, первый разряд которых является старшим. Все п триггеров 5 устанавливают ся в начальное единичное состояние путем подачи единичного импульса на шину установки триггеров в 1. В регистр 8 записывается дополнительны код начального значения порога Т со знаком минус, которое в данном случа равно - (n-N+1), где N - номер вычисляемой порядковой статистики. Например, если вычисляется медиана последовательности п двоичных чисел, то значение Т п/2 при вычислении максимума, т.е. при , начальное значение порога равно единице, а при вычислении минимума, т.е. при , равно п, Для запуска устройства на шину управления первого разряда подается единичный импульс при отсутствии управляющих импульсов на других шинах управления. При этом на первый вход га-входовых элементов ИЛИ 3 поступает сигнал, соответствуюпщй содержимому первого разряда всех т-разрядных регистров, а на остальные (ta-1) входы сигналы, соответствующие О, так как все триггеры 5 находятся в на-: чальном состоянии 1, а их выходы соединены с третьими входами соответствующих схем И 2. Тогда на выходах п т-входовых.. элементов ИЛИ 3 присутствуют сигналы, соответствующие значениям первых разрядов всех анализируемых чисел. Эти сигналы поступают на входные ншны сумматора 7 для сложения п одноразрядных чисел и после суммирования код их суммы поступает на первый входсумматора 10, на второй вход которого поступает дополнительный код порога Т из выхода регистра 8. При подаче синхронизирующего импульса с выхода т- входорого элемента ШШ 9 в сумматоре 10выполняется сложение кодов входных чисел, что в данном случае эквивалентно выполнению операции вычитания из S значения Т, так как в регистре 8 порог записан в дополнительном коде, а значение S всегда положительно. При этом возможны следующие два случая. Если , результат суммирования. положительный и на выходе знакового разряда 11 находится сигнал О. Сигнал с выхода знакового разряда 11после инвертирования элементом НЕ подается на выход устройства в качестве значения первого разряда вычисляемой порядковой статистики. Одновременно этот сигнал подается на второй вход элементов ИСКЛЮЧАЩЕЕ ИЛИ 4, на первый вход которых поступают сигналы с выходов элементов ИЛИ 3. В этом случае на выходе элементов ИСКЛЮЧАЩЕЕ ИЛИ 4 будет сигнал 1 для тех чисел, в первых разрядах которых записано значение О. При подаче с выходов элементов ИСКЛЮЧАЮЩЕЕ ЮШ 4 сигналов 1 на нулевые входы триггеров 5, устанавливаются в нулевое состояние те триггеры, если в соответствующих им регистрах в первом разряде записаны нули. Это значит, что анализируемые числа, в первых разрядах которых быпи нули, исключаются из дальнейшего анализа

вследствие связи триггеров 5 с трехвходовыми элементами И 2.

Если , результат суммирования отрицательный и на выходе знакового разряда 11 присутствует сигнал 1. Этот сигнал 1 с выхода знакового разряда 11 поступает на управляющий вход записи регистра 8 и после поступления этого сигнала в регистр 8 записывается дополнительный код числа на выходе сумматора 10, как новое значение порога Т. Сигнал 1 из выхода знакового разряда сумматора 10 через элемент НЕ 12 поступает на выход устройства и на вторые входы элементов ИСЮБОЧАЮЩЕЕ ИЛИ 4, на первые входы которих поступают сигналы с выходов элементов ИЛИ 3. В этом случае на выходе элементов ИСЮ1ЮЧАЮЩЕЕ ИЛИ 4. будет сигнал 1 для тех чисел, в первых ,разрядах которых было записано значение 1. Тогда путем подачи из элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 4 сигналов на нулевые входы триггеров 5 устанавливаются в нулевое состояние те триггеры, Б соответствующих первых разрядах регистров которых записаны единицы. При этом из дальнейшего анализа исключаются те числа, в первых разрядах которых были единицы.

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

Например, требуется определить максимум последовательности чисел, но начальное значение порога равно единице. В этом случае сумма S анализируемых разрядов чисел меньше значения Т только тогда, когда все разряды равны нулю. Это значит, что функция всех новых введенных узлов эквивалентна функции одного п-входного элемента ИЛИ, который выполняет ее в известном устройстве для выделения экстремального числа из пгаразрядных двоичных чисел.

Сумматор для сложения п одноразрядных чисел содержит К групп сумматоров параллельного сложения чисел, где К loggH, причем i-я группа сумматоров содержит (п/2) параллельно действующих i-разрядных сумматоров, выходы которых соединены с

входами сумматоров (i + 1)-й группы. Сумматор для сложения п одноразрядных чисел работает следующим образом.

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

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

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОРЯДКОВЫХ СТАТИСТИК ПОСЛЕДОВАТЕЛЬНОСТИ п т-РАЗРЯДНЫХ ДВОИЧНЫХ ЧИСЕЛ, содержащие п т-разрядных регистров и групп элементов И, п т-входовых элементов ИЛИ, п триггеров, п. элеиентов ИСКЛЮЧАЩЕЕ ИЛИ, причем выходы регистров поразрядно соединены с первыми входами Элементов И соответствующей группы, выходы которых соединены с входами соответствующего твходового элемента ИЛИ, а входы установки триггеров в 1 - с входом сброса устройства, вторые входы одноименных элементов И всех групп подключены к соответствующим шинам управления поразрядным сравнением, третьи входы элементов И каждой группы соединены с выходами соответствующих триггеров, выходы т-входовых элементов ИЛИ соединены с первыми входами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, вторые входы которых объединены, а выходы соединены с входами установки в ноль соответствующих триггеров, отличающееся тем, что, с целью расширения функциональных возможностей устройства путем обеспечения вычисления любой заданной порядковой статистики последовательности чисел, в него введены управляющий т-входовый элемент ИЛИ, сумматор, регистр порога, элемент НЕ, сумматор для сложения п одноразрядных чисел, входы которого соединены с выходами соответствующих т-входовых элементов СЛ ИЛИ, а выходы - с первой группой входов сумматора, вторая группа входов которого подключена к выходам регистра порога, установочные входы которого соединены с выходами разрядов сумматора, выход знакового разряда которого подключен к входу управления записью регистра порога и вхо4 ду элемента НЕ, выходкоторого подключен к вторым входам всех элементов ИСКЛЮЧАЩЕЕ ИЛИ и является выходом устройства, вход синхронизации сумматора соединен с выходом управляющего т-входового элемента ИЛИ, входы которого подключены к шинам управления поразрядным сравнением.

в.

4:5

а

ФигЛ I I ti-ff гр1/лг7а / o-1 I .1-(i- V2pi/ /7(7

Фиг. 2 I I . I Ilb l