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

2 А СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК ВТОРСНОМ ДЕТЕЛЬСТ,Ю, Луць нститут скин ьство ССС 1975. тво СССР 1981ид тельс 7/02,ГОСУДАРСТВЕННЫЙ КОМИТЕТ ССПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИИ АНИЕ ИЗОБ(54)(57) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯПОРЯДКОВЫХ СТАТИСТИК ПОСЛЕДОВАТЕЛЬНОСТИ и т-РАЗРЯДНЫХ ДВОИЧНЫХ ЧИСЕЛ,содержащие п щ-разрядных регистров игрупп элементов И, и ш-входовых элементов ИЛИ, и триггеров, п элементовИСКЛЮЧАЮЩЕЕ ИЛИ, причем выходы регистров поразрядно соединены с первыми входами элементов И соответствующей группы, выходы которых соединены с входами соответствующего швходового элемента ИЛИ, а входы установки триггеров в "1" - с входомсброса устройства, вторые входы одноименных элементов И всех группподключены к соответствующим шинамуправления поразрядным сравнением,третьи входы элементов И каждойгруппы соединены с выходами соответствующих триггеров, выходы щ-входовых элементов ИЛИ соединены с первыми входами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, вторые входы которых объединены, а выходы соединены с входами установки в ноль соответствующих триггеров, о т л и ч а ю ш е е с я тем, что, с целью расширения функциональных возможностей устройства путем обеспечения вычисления любой заданной порядковой статистики последовательности чисел, в него введены управляющий ш-входовый элемент ИЛИ, сумматор, регистр порога, элемент НЕ, сумматор для сложения п одноразрядных чисел, входы которого соединены с выходами соответствующих ш-входовых элементов ИЛИ, а выходы - с первой группой входов сумматора, вторая группа вхо- Св дов которого подключена к выходам регистра порога, установочные входыкоторого соединены с выходами разрядов сумматора, выход знакового разряда которого подключен к входу управления записью регистра .порога и входу элемента НЕ, выход которого подключен к вторым входам всех элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и является вь 1- ходом устройства, вход синхронизации сумматора соединен с выходом управляющего ш-входового элемента ИЛИ, входы которого подключены к шинам уп" равления поразрядным сравнением.Изобретение относится к вычислительной технике и технйческой кибернетике и может быть использовано в системах цифровой обработки одномерных и двумерных сигналов (изображений), например, для медианной фильтрации сигналов с целью подавления шума.Порядковой статистикой последовательности из и чисел., имеющей номер 10 И, называют то число, для которого существует ровно Ичисел, меньших или равных ему по величине, и ровно (и-/М/) чисел, больших или равных ему из данной последовательности. Примером порядковых статистик, часто используемых при обработке и распознавании сигналов, являются медиана, минимальный или максимальный элементы последовательности. 20Известно устройство для определения медианы, содержащее источник чисел, блок управления, блоки анализа чисел, элемент И, линии задержки, ключи, элементы неравнозначности, д цифровые компараторы, элементы И, регистры, элементы ИЛИНедостатками этого устройства являются его сложность и малое быстродействие вследствие последователь- З 0 ного сравнения чисел для определения медианы.Наиболее бЛизким по техническому решению к предлагаемому устройству является устройство для выделения З 5 экстремального числа из п ш-разрядных двоичных чисел, содержащее и ш-разрядных регистров для хранения двоичных чисел, ш и-трехвходовых элементов И,п ш-входовых элементов ИЛИ, и эле ментов ИСКЛЮЧАЮЩЕЕ ИЛИ, и триггеров, и входовый элемент ИЛИ, причем выходы регистров поразрядно соединены с первыми входами элементов И соответствующей группы, выходы которых 45 соединены с входами соответствующего и-входового элемента ИЛИ, входы установки триггеров в единицу - с входом сброса устройства, вторые входы одноименных элементов И всех групп 50 соединены с соответствующими шинами управления поразрядным сравнением устройства, третьи входы элементов И каждой группы соединены с выходами соответствующих .триггеров и с вы ходами кода номера регистра, содержащего экстремальное число устройства, выходы ш-входовых элементов ИЛИ соединены с первыми входами соответствующих элементов ИСКЛЮЧАЮЩЕЕ ИЛИи с соответствующими входами п-входового элемента ИЛИ, выход которогосоединен с вторыми входами элементовИСКЛЮЧАЮЩЕЕ ИЛИ и является выходомкода экстремального числа устройства,выходы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединены с нулевыми входами соответствующих триггеров 21 .Однако устройство позволяет вычислять только, две порядковые статистики, а именно максимум или минимум,в то время когда при обработке сигналов требуется вычислять и другиепорядковые статистики, например, медиану последовательности чисел,Цель изобретения - расширениефункциональньг,: возможностей устройства путем вычисленчя любой заданнойпорядковой статистики последовательности чисел,Поставленная цель достигается тем,. что в устройство для вычисления порядковьп статистик последовательности и ш-разрядных двоичных чисел, содержащее и ш-разрядных регистров и, групп элементов И, и ш-входовых элементов ИЛИ, п триггеров, и элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, причем выходы регистров поразрядно соединены с первыми входами элементов И соответствующей группы, выходы которых соединены с входами соответствующего швходового элемента ИЛИ, а входы установки триггеров в "1" -с входом сброса устройства, вторые входы одноименных элементов И всех групп подключены к соответствующим шинам управления поразрядным сравнением, третьи входы элементов И каждой группы соединены с выходами соответствующих триггеров, выходы ш-входовых элементов ИЛИ соединены с первыми входами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, вторые входы которых объединены, а выходы соединены с входами установки в ноль соответствующих триггеров, введены управляющий ш-входовый элемент ИЛИ, сумматор, регистр порога, элемент НЕ, сумматор для сложения и одноразрядных чисел. входы кЬторого соединены с выходами соответствующих ш-входовых элементов ИЛИ, а выходы - с первой группой входов сумматора, вторая группа входов которого подключена к выходам регистра порога, установочные входы которого соедииены с выходами разрядов сумматора,выход знакового разряда которогоподключен к входу управления записьюрегистра порога и входу элемента НЕ,выход которого подключен к вторымвходам всех элементов ИСКЛЮЧАЮЩЕЕ ИЛИи является выходом устройства, входсинхронизации сумматора соединен свыходом управляющего щ-входового элемента ИЛИ, входы которого подключены к шинам управления поразряднымсравнением,На фиг, 1 показана структурнаясхема предлагаемого устройства; нафиг, 2 - схема сумматора для сложения и одноразрядных двоичных чисел.Устройство содержит и щ-разрядныхрегистров 1, и групп элементов И 2,щ и-входовых элементов ИЛИ 3, и элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 4, и триггеров 5, шины б управления, сумматор 7для сложения и одноразрядных двоичных чисел, регистр 8 порога, управляющий щ-входовый элемент ИЛИ 9, сумматор 10 со знаковым разрядом 11 и.элемент НЕ 12.Устройство работает следующим образом.Перед началом работы устройства ви щ-разрядных регистрах 1 записыва 30ются и щ-разрядные коды анализируемых двоичных чисел.а а а,;Ь 1 Ь,;35ч ччщпервый разряд которых является старшим. Все и триггеров 5 устанавливаются в начальное единичное состояние путем подачи единичного импульса на шину установки триггеров в "1". В регистр 8 записывается дополнительный код начального значения порога Т со 45 знаком минус, которое в данном случае равно - Ь+1), где М - номер вычисляемой порядковой статистики. Например, если вычисляется медиана последовательости и двоичных чисел, 50 то значение Т = и/2 при вычислении максимума, т.е. при Я=и, начальное значение порога равно единице, а при вычислении минимума, т.е. при И=1, равно и. 55Для запуска устройства на шину управления первого разряда подается единичный импульс при отсутствии управляюших импульсов на других шинах управления. При этом на первый вход щ-входовых элементов ИЛИ 3 поступает сигнал, соответствующий содержимому первого разряда всех щ-разрядных регистров, а на остальные (щ) входы сигналы, соответствующие О , так как все триггеры 5 находятся в начальном состоянии "1", а их выходы соединены с третьими входами соответствующих схем И 2. Тогда на выходах и щ-входовых .элементов ИЛИ 3 присутствуют сигналы, соответствующие значениям первых разрядов всех анализируемых чисел. Эти сигналы поступают на входные шины сумматора 7 цля сложения и одноразрядных чисел и после суммирования код их суммы поступает на первый вход сумматора 10, на второй вход которого поступает дополнительный код порога Т из выхода регистра 8, При подаче синхронизирующего импульса с выхода щвходового элемента ИЛИ 9 в сумматоре 10 выполняется сложение кодов входных чисел, что в данном случае эквивалентно выполнению операции вычитания из Б значения Т, так как в/регистре 8 порог записан в дополнительном коде, а значение Б всегда положительно. При этом возможны следующие два случая. Если ЯТ, результат суммирования. положительный и на выходе знакового разряда 11 находится сигнал "0".Сигнал с выхода знакового разряда 11 после инвертирования элементом НЕ подается на выход устройства в качестве значения первого разряда вычисляемой порядковой статистики. Одновременно этот сигнал подается на второй вход элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 4, на первый вход которых поступают сигналы с выходов элементов ИЛИ 3, В этом случае на выходе элементов ИСКЛЮЧАЯЩЕЕ ИЛИ 4 будет сигнал1 для тех чисел , в первых разрядах которых записано значение "О" При подаче с выходов элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 4 сигналов " 1 " на нулевые входы триггеров 5 , устанавливаются в нулевое состояние те триггеры, если в соответствующих им регистрах в первом разряде записаны кули , Это значит, что анализируемые числа , в . первых разрядах которых были нули , исключаются из дальнейшего анализа20 вследствие связи триггеров 5 с трехвходовыми элементами И 2.Если Б ( Т, результат суммирования отрицательный и на выходе знакового1 11 разряда 11 присутствует сигнал 1 . 5 Этот сигнал "1" с выхода знакового разряда 11 поступает на управляющий вход записи регистра 8 и после поступления этого сигнала в регистр 8 записывается дополнительный код 10 числа на выходе сумматора 10, как новое значение порога Т, Сигнал "1" из выхода знакового разряда сумматора 10 через элемент НЕ 12 поступает на выход устройства и на вторые вхо ды элементов ИСК 320 ЧАЮЩЕЕ ИЛИ 4, на первые входы которых поступают сигналы с выходов элементов ИЛИ 3. В этом случае на выходе элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 4 будет сигнал "1" для тех чисел, в первых разрядах ко 11 11 торых было записано значение 1 Тогда путем и одачи из элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 4 сигналов на нуле-. вые входы триггеров 5 ус танавлив а ют с я в нулевое состояние те три г геры ы , в соответствующих первых р а з р яд ах регистров которых записаны единицы . При э том из дальнейшего ан ализа исключаются т е числа , в первых ЗО разрядах которых были единицы ,П ри и одач е управляющего сигнала н а шину управления второго разряда выполняется описанный анализ вторых разрядов тех чисел , триггеры которь 1 х З 5 находятся в едничн ом состоянии после анализа первого разряда всех и чис ел , При э т ом определяется значение второго разряда вычисляемой и орядковой статистики и исключается из40 дальнейшего анализа некоторое количество анализируемых чисел. Таким образом, при поочередной подаче управляющих импульсов на шины 6 управления выполняется анализ всех шразрядов задаиных и двоичных чисел ивычисляются ш разрядов требуемой порядковой статистики,Например, требуется определитьмаксимум последовательности чисел,но начальное значение порога равноединице. В этом случае сумма Б анализируемых разрядов чисел меньшезначения Т только тогда, когда всеразряды равны нулю, Это значит, чтофункция всех новых введенных узловэквивалентна функции одного и-входного элемента ИЛИ, который выполняетее в известном устройстве для выделения экстремального числа из ишразрядных двоичных чисел,Сумматор для сложения и одноразрядных чисел содержит К,групп сумматоров параллельного сложения чисел,где К = 1 оя и, причем -я группасумматоров содержит (и/21) параллельно действующих 1-разрядных сумматоров, выходы которых соединены свходами сумматоров (1 + 1)-й группы.Сумматор для сложения и одноразрядных чисел работает следующим образом.При подаче на его входные шиныкодов одноразрядных двоичных чисел,одноразрядные сумматоры первой группы выполняют параллельное попарноесуммирование этих кодов и результаты суммирования поступают на входыдвухразрядных. сумматоров второйгруппы, Этот процесс параллельнопоследовательного суммирования продолжается до сумматора той группы,на выходе которого получаем код суммы и одноразрядных двоичных чисел,состоящий из 1 оя,1 и двоичных разрядов,Заказ 931/40 исноеССР4/5 Патент", г. Ужгород, ул, Проектная,Филиал1 ВНИИПИ Г по делам 13035, Москв раж 710сударственногоизобретений иЖ, Раушск комитет ткрытий я наб