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

1109736 ния порога, выходы сумм и переносов одноразрядных сумматоров каждого блока сумматоров соединены соответственно с шинами сумм и переносов данного блока сумматоров, шина сумм блокаслоя сумматоров подключена к входам блоков сумматоров (+)- го слоя одинакового веса, шина ,переносов блокаслоя сумматоров подключена к входам блоков суммато Изобретение относится к автомати- ке и вычислительной технике и может быть использовано при реализации технических средств для выделения локальных экстремумов полезных сигналов из массива зашумленных. По основному авт,св. Ф 003070 известно устройство для выделения экстремальных чисел, содержащее и узлов сравнения, каждый из которых сьстоит из регитра, элемента И, узла связи, состоящего из двух элементов ИЛИ, ш узлов коммутации, содержащих элемент ИЛИ и два элемента И, схемы сравнения, состоящей из двух триггеров и трех элементов И, и в информационных выходов, ш входов тактовых сигналов, а адресных выходов, вход опроса, причем вход блокировки каждого 1-го сравнения, где 1=1,2п, соединен с управляющим входом (1+1)-го узла сравненйя, первый и второй выходы переносов каждого 1-го узла сравнения подключены к первому и второму входам переносов (1-1)-го узла сравнения, вход опроса устройства соединен с первым входам элемента И каждого узла сравнения, выход элемента И каждого 1-го узла срав-нения подключен к -му адресному выходу устройства, прямой и инверсный выходы каждого 1-го разряда регистра, где 1=1,2 ,щ, ш - количество разрядов в сравниваемых числах, соединены с первыми входами первого и второго элементов И соответственно 1-го узла коммутации, выход эле- мента И каждого д-го узла сравнения подключен к первому входу элемента ров (+)-го слоя соответствующихбольших весов, шины сумм и переносовблоков сумматоров последнего слоясоединены с первыми входами соответствующих элементов И, первые входыкоторых подключены к входу считывания кода порога узла определения порога, а выходы являются выходами узла определения порога. ИЛИ каждого узла коммутации 1-гоузла сравнения, каждый 1-вход тактовых сигналов устройства соединен свторым входом элемента ИЛИ, 1-го 5 узла коммутации всех узлов сравнения, выход элемента ИЛИ каждого 1-гоузла коммутации подключен к вторымвходам элементов И 1-го узла коммутации, выход первого и второго элементов И каждого 1-го узла коммутации каждого 1-го узла сравнения соединен с 1-м входом первого и второго элемента ИЛИ узла связи соответственно -го узла сравнения, вы 5ходы первого и второго элементовИЛИ узла связи каждого -го узласравнения подключены к первым входампервого и второго элементов И соот 20ветственно схемы сравнения д-гоузла сравнения, выходы первого ивторого элементов ИЛИ узла связи-го узла сравнения соединены с вторым и первым выходами переносовсоответственно -го узла сравнения,первый и второй входы переносовкаждого 1-го узла сравнения подключены к вторым входам первого и второго элементов И схемы сравненияд-го узла сравнения, выходы первого и второго элементов И схемысравнения каждого х-го узла сравнения соединены с входами установкив единичное состояние первого и второго триггеров схемы сравнения -гоузла сравнения, инверсные выходыпервого и второго триггеров схемысравнения в каждом из узлов сравнения подключены к входам третьегоэлемента И схемы сравнения, выход 40которого соединен с третьими вхо5 О 20 25 дами первого и второго элементов И схемы сравнения, прямой выход первого триггера схемы сравнения д.-го узла сравнения подключен к вто" рому входу элемента И -го узла срав. нения, прямой выход второго триггера схемы сравнения соединен с выходом блокировки 1-го узла сравнения, управляющий вход каждого 1.-го узла сравнения подключен к третьему входу элемента И д-го узла сравне,ния, выход первого элемента И каждого 1-го узла коммутации каждого -го узла сравнения соединен с 1-м информационным выходом д-го узла сравнения. Работа устройства заключается в попарном параллельном поразрядном сравнении чисел, происходящем по тактовым сигналам единичного уровня. Элементы узлов сравнения фиксируют изменение знака приращения сравниваемых чисел, т.е. точку перегиба (экстремума) функции, что обеспечивает выделение всех локальных экстремумов, в массиве сравниваемых чисел, например ординат дискретной корреляционной функции 1.Недостатком известного устройства является уменьшение достоверности информации, выдаваемой для дальнейшей обработки, за счет шумовых выбросов при увеличении интенсивности шумов.Цель изобретения - повышение досто" верности информации при выделении экстремумов дискретных функций, выдаваемой для дальнейшей обработки, путем введения порога сравнения, рас считываемого по уровню шумов.Поставленная цель достигается тем, что в устройство для выделения экстремальных чисел введены узел определения порога и узел распределения тактовых сигналов, включающий в элементов ИЛИ, р триг-. геров, р.элементов И, (р) элементов ИЛИ-НЕ, где р - значение порога, р (ш), ш - число разрядов сравниваемых чисел, причем информационные выходы узлов сравнениясое. динены с соответствунзцими информационными входами узла определения порога, 1-й выход которого, где 3=1,2р, соединен с входом установки в состояние "1" 1-го триггера узла распределения тактовых сигналоь, входы установки в состояние "0" всех триггеров и первые входы всех элементов ИЛИ узла распределения тактовых сигналов подключены кшине начальной установки устройства,выход 1-го элемента ИЛИ узла распределения тактовых сигналов (1,2в) соединен с 1-шиной тактовых сигналов узлов сравнения в узлераспределения тактовых сигналов,каждый г -й элемент ИЛИ-НЕ, гдеГ=1,2 ., (р), имеет (р-г+1) входов, соединенных соответственно спрямыми выходами триггеров с г -гопо р-й, выход г-го элемента ИЛИ-НЕ,подключен к первому входу г-го элемента И, второй вход которого соединен с 1.-й шиной тактовых сигналовустройства, а выход - с вторым входом 7. -го элемента ИЛИ, инверсный выход р-го триггера соединен с первым входом р-го элемента И, второйвход которого соединен с р-и шинойтактовых сигналов устройства, а выход - с вторым входом р-го элемента ИЛИ, шины тактовых сигналовс (р+1)-го ло о -ю подключены к вторым входам соответствующих элементов ИЛИ узла распределения тактовых сигналов. Кроме того, узел определения порога содержит р элементов И и одно 30 тактный многослойный матричный умножитель, включающийслоев сумматоров, где =1,2 каждый изкоторых содержитблоков сумматоров, включающий одноразрядныеЗ 5 сумматоры, причем 1 входов одноразрядного сумматора первого слояМр - 1сумматоров, где к = в : в , а = .сц=1а - среднее значение шумов,40 о 1 =О..(2 -) - значение числа,записанного в регистр, р.-го узласравнения с =1,2М, М 4 и подключены к информационным входам соответствующего веса узла определе 45 ния порога, выходы сумм и переносоводноразрядных сумматоров каждого блока сумматоров соединены соответственно с шинами сумм и переносов данного блока сумматоров, шина сумм бло 50 каслоя сумматоров подключена квходам блоков сумматоров (, +1)-гослоя одинакового веса, шина переносов блокаслоя сумматоров подключена к входам блоков сумматоров55(Е+1)-го слоя соответствующих большйх весов, шины сумм и переносов блоков сумматоров последнего слоя соединены с первыми входами соответствующих элементов И, первые входыКоторых подключены к входу считывания кода порога узла определения порога, а выходы являются выходами узла определения порога.На фиг, 1 представлена структурная схема предлагаемого устройства;на фиг. 2 - структурная схема узлаопределения порога; на фиг, 3 -процесс вычисления лорога; на фиг.4 графики значений времен сравнения Ои преобразования кода в узле определения порога.Устройство содержит и узловсравнения, каждый из которых включает регистр 2, элемент И 3, узел 4 5связи, включающий первый 5 и второй 6 элементов ИЛИ, ш узлов 7коммутации, содержащих элементИЛИ 8, первый 9 и второй 10 элементы И, схему 11 сравнения, в которую входят первый 12 и второй 3триггеры, первый 14, второй 15 и третий 16 элементы И, и ш информационныхвыходов 17, ш входов 18 тактовыхсигналов, и адресных выходов 19, 25вход 20 опроса.Узел 21 распределения тактовых сигналов содержит ш выходныхэлементов ИЛИ 22 и шин 23 тактовыхсигналов, р элементов И 24 и триг- З 0геров 25, (р -1) элементов ИЛИ-НЕ26, шину 27 начальной установкиустройства. Узел 28 определенияпорога (фиг.2) с входом 29, выходом 30 и управляющим входом 31 состоит из слоев сумматоров 32, содержащих блоки 33 сумматоров, состоящих из одноразрядных сумматоров 34,р элементов И 35 коммутации.одному слою относятся суммато 40ры, которые начинают работать в одини тот же момент времени, Сумматорыодного слоя, складывающие разрядычисел одного веса, объединены в блоки 33. Каждый слой сумматоров 32 иблок 33 сумматоров построены аналогично,Одноразрядный %-входовый сумматор 34-го веса вырабатывает разряд суммы того же веса и разрядыпереноса с весами (1+1) (1+11 о 8 К+1)50Разряды сравниваемых чисел и соответствующие им узлы 7 коммутации, информационные выходы 17, шины 8 тактовых сигналов, а также выходные5элементы ИЛИ 22 и шины 23 тактовыхсигналов узла 21 имеют текущий индекси пронумерованы справа налево от 1109736 6Ф1 до гй (1-й . - младший ю-й - старший).Узлы 1 и входящие в их состав элементы И 3, узлы 4 связи и схемы 11сравнения, а также адресные выходы 19имеют текущий индекси пронумерованы сверху вниз от 1 до и. Входящие в состав узла 2 элементы И 24и триггеры 25 имеют текущий индекс Еи пронумерованы справа налево от1 до р (р-й - старший, 1-й - младший, р ( в -1), а элементы ИЛИ-НЕ 26имеют тот же текущий индекс и пронумерованы от 1, до (р). Входящие вузел 28 определения порога сумматоров 32 и составляющие их блоки 33имеют текущий индекси пронумерованы сверху вниз (=1,2,)Устройство работает следующим образом,В начальный момент времени по шине начальной установки устройстваподается сигнал единичного уровня,устанавливающий в состояние "0"триггеры 25 узла 21. Этот же сигналчерез элементы ИЛИ 22 узла 21 распределения тактовых сигналов и эле-менты ИЛИ 8 подается на входы элементов И 9 и О узлов 7 коммутациивсех узловсравнения и разрешаетвыдачу информации, записанной в регистры 2, на информационные выходы 17узлов 1 сравнения и на вход 29 узла 28 определения порога.В узле 28 рассчитывается порогр=Еа, где 1 = М/2 ц - коэффициент1(2 -) - значение числа, записанного в регистр 2 р.-го узла 1 срав.нения, р=1,.М, Ии. Узел 28определения порога выполняет функциипреобразователя многоразрядного кодаматрицы - сумма А, образованнойн вюподписыванием друг под другом одноразрядных кодов слагаемых а, вЦФ,одноразрядный код результата.Процесс преобразования мйогоразрядного кода (фиг,З) показан для разрядности чисел в=4 номер разрядаих количество 8=8, и использованияв узле 28 одноразрядных трехвходовых сумматоров. Каждая точка изображает двоичную цифру, соответствующего веса. Цифры одного веса изображены друг лод другом. Каждая рамкаокружает цифры, подаваемые на входсумматора 34. 11 унктирная рамка окру.жает сумматоры 34, относящиеся к35 Разрядность выходной информации -40 порога выбирается в предположении, что уровень шумов всегда меньше уровня входных сигналов р (в -1. Для систем цифровой фильтрации или корреляционной обработки максимальный уро 45 вень амплитуды шума в выходных дискретах составляет примерно 217, аФ средний уровень шума не превышает 1 ЗХ от значения амплитуды сигнала. Выбор порога, в два раза превышающе- . го средний уровень шума (ф 1/4 от амп-. литуды сигнапа), гарантирует исключение шумовых выбросов из информации, выдаваемой для дальнейшей обработки. В этом случае значение р можно выбрать, записав условие равен 55 ства амплитуд сигнала и порога 2 /4=2, откуда после логарифмирования получаем р = е -2 Для разрядности входных данных, равной 4 и 8 (при использовании трех входовых сумматоров), области значений 1 левее точек А и В на графике (фиг.4) соответствуют условиям выполнения преобразования за время, меньшее времени сравнения чисел в устройстве. Поэтому основным условием выбора значения И (для обеспечения высокого быстродействия в (сйстемах адаптивной обработки сигналов реального времени) может быть Тяр 4 Т . Уменьшение количества значений М практически не сказывается на величине порога, рассчитывае. мого как математическое ожидание (среднее) из шумовой выборки.Другое условие выбора М можно записать из выражения для коэффициента увеличения рассчитываемого порога к = й/2, где к = 1,2, выбирается на этапе проектирования устройства для решения конкретной задачи. По этому выражению можно определить величину сдвига и = щ 1 од (И/) по выбранным (или подбираемым) значениям к и И при условии, что , должно быть целым чис,лом.Г Разрядность входной информации для узла 28 определения порога целесообразно выбирать равной разрядности ш.входных сигналов. Это позволяет рассчитать порог как по шу,мовой (калибровочнойвыборке, таки по реальной информации - смеси сиг, нала и шума. Для решения другнх задач значение р можно выбрать исходя из конкретных условий.Сигналом единичного уровня, по данным по шине 27 начальной установки устройства, триггеры 25 узла 2распределения тактовых сигналов устанавливаются в состояние "0", Единичный уровень с инверсного выхо да р-го триггера 25, поданный нар-й элемент И 24, открывает цепьпрохождения р-го тактового сигнала:элементы И 24, ИЛИ 22, р-й вход 18тактового сигнала всех узлов 1 срав 5 нения. Сигналы нулевого уровня с прямого выхода всех триггеров 25, поданные на соответствующие входы элементов ИЛИ-НЕ 26, вызывают появление на их выходах сигналов еди ничного уровня, которые открываютцепи прохождения сигналов с р-го попервый. Сравнение производитсяво всех разрядах сравниваемых чисел (тактовые сигналы с в-го по 25 -+)-й подаются непосредственнона входы 18 тактовых сигнапов всехузлов сравнения).Рассчитанный в узле 28 порогподается с выхода 30 на вход узла 2 распределения тактовых сигналов и устанавливает в состояние11 1соответствующие триггеры 2 5 .Сиги ап единичного уровня с прямоговыхода ,установленного в состояниен 1 триггера 25, имеющего наибольший номер, например Г-й, подаетсяна соответствующиевходы элементовИЛИ-НЕ 26 с 1-го по первый. Сигналы нулевого уровня с выхода этихэлементов, поданные на входы элементов И 24, разрывают цепи прохождения тактовых сигналов. Сравнение в разрядах чисел с 1-го попервый не производится, Если 1=р,то нулевой уровень с инверсноговыхода р-го триггера 25, поданныйна вход р -го элемента И 24, разры"вает цепь прохождения р-го тактового сигнала. Цепи прохождениятактовых сигналов с (р)-го попервый также разомкнуты. Сравнениечисел производится по тактовым сигналам только в старших (с П-гопо (р+1)-й) разрядах.Поскольку предлагаемое изобретение не создает экономии, а направлено на улучшение технических характеристик, производим сравнениедостоверности информации, ныдавае30 Уменьшение количества ложной информации, выдаваемой для дальнейшей 35 обработки, для предлагаемого устройства по сравнению с известным определяется как Ф, =ГВ/Г 5,1=1,2; , %12,7; %426. Введение порога, рассчитываемого по уровню шумов, 40 сказывается на уровень условной вероятности правильного обнаружения1полезных сигналов 2=- - 11 +2+ ф,ф.1 где х - уровень сигнала, 45 Величина Й существенно зависит от отношения сигнал/шум на входе устроймой для дальнейшей обработки предлагаемым и известным устройствами.В качестве критерия сравненияпринимаем значение условной вероятности ложной тревоги, характеризующее достоверность информации.Условная вероятность ложной тревоги Г представляет собой среднеечисло ложной информации, выдаваемой после обнаружения экстремумов 1 Ов массиве зашумленных значений дискретной функции для дальнейшей обработки.Для известного устройства Гб=1,так как устройство обнаруживает 15все экстремумы в обрабатываемоммассиве, относящиеся как к полезнымсигналам, так и к шумовым выбросам.Для предлагаемого устройства зна чение можно определить по выражению 20для условной вероятности ложной тревоги устройства порогового обнаружения Г = -- 1- ф ), гдеу - фиксированный уровень порога; 25и - уровень .шумов помех; фзначение табулированного интегралавероятности.ПРи у о= н (к=1) ф (1) =0,8427,=7,86 10-2,При уд=2 но(к=2) ф (2)=0,9953,Е 3=2,35 1 О . ства порогового обнаружения. Для того, чтобы обеспечить вероятность правильного обнаружения полезных сигналов в диапазоне 0,5 1, необходимым условием является равенствоФ(- - ф-) = О 1. По.значениям"(х - 2 ьПри у =2 в ----= 03 от 9 о н фохкуда -- ,= 25.В цифровых согласованных фильтрах отношение сигнал/шум на выходе тем больше, чем больше коэффициент сжатия к фильтра (для современных фильтров к может достигать величины 10 и более). Это означает,. что пои наличии полезных сигналов в обрабатываемом массиве значение вероятности правильного обнаружения близко к единице.Введение порога сравнения, рассмагриваемого по уровню шумов, позволяет на несколько порядков увеличить достоверность информации (умень-шить количество ложной информации), выдаваемой для дальнейшей обработки предлагаемым устройством, по сравнению с известным при условии превышения сигнала над шумом. Вероятность правильного обнаружения экстремумов полезных сигналов при этом тем больше, чем больше отношение сигнал/шум на входе устройства.Предлагаемое устройство может быть использовано при построении специализированных средствцифровой обработки сигналов в системах гидро, -радио- и звуколокации и навигации для уменьшения объема данных, выдаваемых для дальнейшей обработки. Это позволит освободившееся время перераспределить между другими задачами обработки.