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

ния порога, выходы сумм и переносов одноразрядных сумматоров каждого блока сумматоров соединены соответственно с шинами сумм и переносов данного блока сумматоров, шина сум.-л блока слоя сумматоров подключена к входам блоков сумматоров ()го слоя одинакового веса, шина .переносов блока слоя сумматоров подключена к входам блоков сумматоров (Р + О-ГО слоя соответствующих больших весов, шины сумм и переносов блоков сумматоров последнего слоя соединены с первыми входами соответствующих элементов И, первые входы которых подключены к входу считывания кода порога узла определения порога, а выходы являются выходами узла определения порога.

I, УСТРОЙСТВО ДЛЯ ВЫДЕЛЕНИЯ ЭКСТРЕМАЛЬНЫХ ЧИСЕЛ по авт,ев, № 1003070, отличающееся тем, что, с целью поиышения достоверности при выделении экстремумов дискретных функций путем введения порога сравнения, рассчитывае мого по уровню шумов, в устройство введеьы узел определения порога и узел распределений тактовых сигналов, включающий m элементов, ИЛИ, р триггеров, р элементов И, (р-1) элементов ИЛИ-НЕ,где р- значение порога, pi (m-1), m - число разрядов сравниваемых чисел, причем информационные выходы узлов уравнения соеди нень с соответствующими информацион№1ми входами узла определения порога, С-й выход которого, где t I, 2,,..,р. соединен с входом установки в состояние I Е-ГО триггера узла распределения тактовых сигналов, входы установки в состояние О всех триггеров и первые входы всех :элементов ИЛИ узла распределения тактовых сигналов подключены к шине начальной установки устройства, выход j-ro элемента ИЛИ узла распределения тактовых сигналов (j l,2,,,,m ) соединен с j-й шиной тактовых сигналов узлов сравнения в узле распределения тактовых сигналов, каждый г-и элемент ИЛИ-НЕ, где г 1,2,,,,, (р-1), имеет (р-г+О входов, соединенных соответственно с пряьыми выходами триггеров с г-го по р-и, выход г-го элемента ИЛИ-НЕ подключен к первому входу г-го элемента И, второй вход которого соединен с г-шиной тактовых сигналов устройства, а выход с вторым входом г-го элемента ИЛИ, инверсный- выход р-го триггера соединен с первым входом р-го элемента И, второй вход которого соеди нен с р-шиной тактовых сигналов устройства, а выход - с вторым входом р-го элемента ИЛИ, шины тактовых сигналов с (р+1)-го по т-ю подключены к вторым входам соответствующих элементов ИЛИ узла распределотния тактовых сигналов, 2, Устройство по п. I, о т л и чающее ся тем, что узел определения порога содержит р элеменСО тов И и однотактный многослойный матричный умножитель, включающий со слоев сумматоров, где 1,2,,,., 05 каадый из которых содержит Р блоков сумматоров, включающих одноразрядные сумматоры, причем к входов одноразрядного сумматора первого -I-. i . слоя сумматоров, где к N - а., - среднее значение шумов, а JH 0..,

1

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

По основному авт.св. № 1003070 известно устройство для выделения экстремальных чисел, содержащее п у31лов сравнения, каждый из которых состоит из регистра, элемента И, узла связи, состоящего из двух элеM HToi; ИЛИ, .т узлов коммутации, содержащих элемент ИЛИ и два элемента И, схемы сравнения, состоящей из двух триггеров и трех элементов И, и m информационных выходов, m входов тактовых сигналов, m адресных выходов, вход опроса, причем вход блокировки каждого i-ro сравнения, где ,2,...,п, соединен с управляняцим входом (i+l)-ro узла сравнения, первый и второй выход1)1 переносов каждого i-ro узла сравнения подключены к первому и второму входам переносов (i-i)-ro узиа сравнения, вход опроса устройства соединен с первым входом элемета И каждого узла сравнения, выход элемента И каждого j-ro узла сравнения подключен к i-му адресному выходу устройства, прямой и инверсный выходы каждого j-ro разряда регистра, где ,2., ,.. ,т., m - количество разрядов в сравниваек&1х числах, соедир1ены с первыми входами первого и второго элементов И соответственно j.-ro узла коммутации, выход элемента И каждого i-ro узла сравнения подключен к. первому входу элемента

2

ИЛИ каждого узла коммутации i-ro узла сравнения, каждый j-вход тактовых сигналов ycTpoficTBa соединен с вторым входом элемента ИЛИ, j-го узла коммутации всех узлов сравнения , выход элемента ИЛИ каждого j-r узла коммутации подключен к вторым входам элементов И j-ro узла коммутации, выход первого и второго элементов И каждого j-rq узла коммутации каждого i-ro узла сравнения соединен с J-M входом первого и второго элемента ИЛИ узла связи соответственно i-ro узла сравнения, выходы первого и второго элементов ИЛИ узла связи каждого i-ro узла сравнения подключены к первым входа первого и второго элементов И соответственно схе№.1 сравнения i-ro узла сравнения, выходы первого и второго элементов ИЛИ узла связи i-ro узла сравнения соединены с вторым и первым выходами переносов соответственно i-ro узла сравнения, первый и второй входы переносов каждого i-ro узла сравнения подключены к вторым входам первого и второго элементов И схемы сравнения i-ro узла сравнения, выходьГ первого и второго элементов И сравнения каждого i-ro узла сравнения соединены с входами установки в единичное состояние первого и второго триггеров схемз сравнения i-ro узла сравнения, инверсные выходы первого и второго триггеров схемы сравнения в каждом из узлов сравнения подключены к входам третьего элемента И схемы сравнения, выход которого соединен с третьими вхо11дами первого и второго элементов И cxeNbi сравнения, прямой выход первого триггера схемы сравнения i-ro узла .сравнения подключен к второму входу элемента И -го узла сравнения, прямой выход второго триггера схемы сравнения соединен с выходом блокировки i-ro узла сравнения, управляющий вход каждого i-ro узла сравнения подключен к третьему

входу элемента И t-ro узла сравне.ния, выход первого элемента И каждого j-ro узла коммутации каждого i-ro узла сравнения соединен с j-м информационным выходом i-ro узла сравнения. Работа устройства заключается в попарном параллельном поразрядном сравнении чисел, происходящем по тактовым сигналам единичного уровня. Элементы узлов сравнения фиксируют изменение знака приращения сравниваеьых чисел, т.е. точку перегиба (экстремума) функции что обеспечивает выделение всех локальных экстремумов, в массиве сравниваеи 1х чисел, например ординат дис кретной корреляционной функции fl. Недостатком известного устройства является уменьшение достоверности информации, выдаваемой для дальнейшей обработки, за счет шумовы выбросов при увеличении интенсивности шумов. Цель изобретения - повышение дост верности информации при выделении экстремумов дискретных функций, выдаваемой для дальнейшей обработки, путем введения порога сравнения, рас считываемого по уровню шумов. Поставленная цель достигается тем, что в устройство дпя выделения экстремальных чисел введены узел определения порога и Vsen распределения тактовых сигналов, включающий m элементов ИЛИ, р триггеров, р элементов И, (р-1) элементов ИЛИ-НЕ, где р - значение порога, р (m-J), m - число разрядов сравнивае1 1х чисел, причем информационные выходы узлов сравнения ..сое динены с с6ответствую1цими информационными входами узла определения порога, t-K выход которого, где 1,2,...,р, соединен с входом установки в состояние I -го триггера узла распределения тактовых сигналой, входы установки в состояние О всех триггеров и первые входы всех элементов ИЛИ узла распределепрям)1ми выходами триггеров с г- -го по р-й, выход h-ro элемента ИЛИ-НЕ Jпoдключeн к первому входу h-ro элемента И, второй вход которого соеди15 нен шиной тактовых сипгалов устройства, а выход - с вторым входом t -го элемента ИЛИ, инверсный выход р-го триггера соединен с первым входом р-го элемента И, второй

20 вход которого соединен с р-п шиной тактовых сигналов устройства, а ;зыход - с вторым входом р-го элемента ИЛИ, шины тактовых сигналов с (р-И)-го ло m-ю подключены к вто736 ия тактовых сигналов подключены к шине начальной установки устройства. выход j-ro элемента ИЛИ узла распределения тактовых сигналов (j l,2,...,m) соединен с j-шинон так5товых сигналов узлов сравнения в узле распределения тактовых сигналов, каждый г -и элемент ИЛИ-ИЕ-, где ,2,..., (р-1), имеет (p-r+l) вхоР дов, соединенных соответственно с РЫм входам соответствующих элемен ° ™ распределения тактовых сигналов. Кроме того, узел определения порога содержит р элементов И и однотактный многослойный матричный умножитель, включающий слоев сумматоров, где 1,2,..., каждый из которых содержит f блоков сумматоров, включающий одноразрядные сумматоры, причем k входов одноразрядного сумматора первого слоя Р I V сумматоров, где к , а ---хг.-. М--1 а- - среднее значение шумов, о( 0. . .() - значение числа, записанного в регистр . д-го узла сравнения,. f. l ,2,. .. ,N, Ni n подключены к информационным входам соответствующего веса узла определения порога, выходы сумм и переносов одноразрядных сумматоров каждого блока сумматоров соединены соответственно с шинами сумм и переносов данного блока сумматоров, шина сумм блока f слоя сумматоров подключена к входам блоков сумматоров (В +)-го слоя одинакового веса, шина переносов блока Р слоя сумматоров подключена к входам блоков су№1атор ©в (6 + 1)-го слоя соответствующих больших весов, шины сумм и переносов блокЬв сумматоров последнего слоя соединены с первыми входами соответствунвдих элементов И, первые входы которых подключены к входу считывания кода порога узла определения порога, а выходы являются выходами узла определения порога. На фиг. I представлена структурная схема предлагаемого устройства на фиг. 2 - структурная схема узла определения порога; на фиг. 3 процесс вычисления порога; на фнг.4 графики значений времен сравнения и преобразования кода в узле опреде ления порога. Устройство Содержит п узлов I сравнения, каждый из которых включа ет регистр 2, элемент И 3, узел 4 связи, включающий первый 5 и второй 6 элементов ИЛИ, nt узлов 7 коммутации, содержащих элемент ИЛИ 8, первый 9 и второй 10 элементы И, схему 11 сравнения, в которую входят первый 12 и второй 13 триггеры, первый 14, второй 15 и тр тий 16 элементы И, и m информационн выходов 17, га входов 18 тактовых сигналов, п адресных выходов 19, вход 20 опроса. Узел 2 Г распределения тактовых сигналов содержит m выходных элементов ИЛИ 22 и шин 23 тактовых сигналов, р элементов И 24 и триггеров 25, (p-lj элементов Ш1И-НЕ 26, шину 27 начальной установки устройства. Узел 28 определения порога (фиг.2) с входом 29, выходом 30 и управляющим входом 31 со стоит из слоев сумматоров 32, содер жащих блоки 33 сумматоров, состоящих из одйораЗрядных сумматоров 34 р элементов И 35 коммутации. К одному слою относятся суммато ры, которые начинают работать в оди и тот же момент времени. Сумматоры одного слоя, складывающие разряды чисел одного веса, объединены в бло ки 33. Каждый слой сумматоров 32 и блок 33 сумматоров построены аналогично. Одноразрядный 1с-входовый сумма тор 34 j-го веса вырабатывает разряд суммы того же веса и разряды переноса с весами (j + 1) (j+IlogjKL Разряды сравниваемых чисел и со ветствующие им узлы 7 коммутации, формационные выходы 17, шимы 18 та товых сигналов, а также выходные элементы ИЛИ 22 и шины 23 тактовых сигналов узла 21 имеют текуищй инд i и пропумрроваШ) справа ргалево от 36 Т до W (1-й .- мпадшийт-й - старший). 1 и входящие в их состав элементы И 3, узлы 4 связи и схемы II сравнения, а также адресные выходы 19 имеют текущий ивдекс i и пронумерованы сверху вниз от до /п- Входящие в состав узла 21 элементы И 24. и триггеры 25 имеют текущий индекс t и пронумерованы справа налево от 1 до р (р-й - старший, 1-й - младший, ), а элементы ИЛИ-НЕ 26 имеют тот же текущий индекс и пронумерованы от 11 до (р-1). Входящие в узел 28 определения порога сумматоров 32 и составляющие их блоки 33 имеют текущий индекс е и пронумерованы сверху вниз (1,2,...). Устройство работает следующим образом. В начальный момент времени по шине начальной установки устройства подается сигнал единичного уровня, устанавливающий в состояние О триггеры 25 узла 21. Этот же сигнал через элементы ИЛИ 22 узла 21 распределения тактовых сиг1галоп и эле- менты ИЛИ 8 подается на входы элементов И 9 и 10 узлов 7 коммутации всех узлов I сравнения и разрешает выдачу информации, записанной в регистры 2, на информационные выходы 17 узлов 1 сравнения и на вход 29 узла 28 определения порога. В узле 28 рассчить1вается порог , где k N/2q - коэффициент - if. -а -N-g/, увеличения порога среднее значение шумов, ,..., (2 -1) - значение чи.слй, записанного в регистр 2ju.-ro узла 1 сравнения, ,...,N, . Узел 28 определения порога выполняет функции преобразователя многоразрядного кода матрицы - суммы А, образованной подписыванием друг под другом одноразрядных кодов слагаемых а .одноразрядньй код результата. Процесс преобразования многоразрядного кода (фиг.3) показан для разрядности чисел номер разряда , их количество , и использования в узле 28 одноразрядных трехвходовых сумматоров. Каждая точка изображает двоичную цифру соответствующего веса. Цифры одного веса изображе1ш друг под другом. Каждая рамка окружает цифры, подаваемые на вход сумматора 34. Пунктирная рамка окружает сумматоры 34, откосящнес.я к одному блоку 33 сумматоров. Ступе,-. ни сумматоров 32 разграничены горизонтальными линиями, справа от которых представлены номера тактов преобразования. Такт преобразования равен времени срабатывания сумматора. Сумматор 34 складывае.т :цифры одинарного веса, на его :выходах появляются цифра суммытого же веса и цифра переноса соседнего большего веса, переходящие для сложения в следующую ступень сумматоров 32. Исходная матрица А последовательно за несколько тактов прео разуется в одноразрядный код резуль тата Р; Этот код подается на вторые входы элементов коммутации И 35 со сдвигом на гп разрядов вправо ( а ,, ) и по сигналу Ьди ,jU 1 Время сравнения (цикл) устройства определяется как , где tj. - такт - время срабатывания логического элемента (для удобства принижаем Cj Время преобразования .. рядной матрицы - суммы в одноразрйдный код результата (в тактах) в зависимости от разрядности .т входных данных и Количества входов одноразрядных сумматоров, используемых для преобразования, определяется путем расчетов на ЭВМ. На графике (фиг.1) и н таблицах приведены значения времени сравнения Трр (табл.1) и времени .преобразования Т„- (табл.2) в зависимости от разрядностиffl , количества N выбираемых для расчета I Для разрядности входных данных, равной А и 8 {при использовании rpe входовых сумматоров), области значений ff левее точек А и 6 на графи ке (фиг.4) соответствуют усповиям выполнения преобразования за время, меньшее времени сравнения чисел в . устройстае. Поэтому основным условием выбора значения N (для обеспечения высокого быстродействия в системах адаптивной обработки сигналов реального времени) может быть . Уменьшение количества пр ср значений N практически ие указывается на величине порога, рассчитыва мого как математическое ожидание (среднее) из шумовой выборки. Другое условие выбора N можно записать из выражения для коэффициента увеличения рассчитываемого порога к N/2, где к 1,2,... выби рается на этапе проектирования устройства для решения конкретной задачи. По этому выражению можно определить величину сдвига q log (N/l) по выбранным (или подбираемым) значениям к и N при усло вии, что должно быть целым чисом. Разрядность входной информации для узла 28 определения порога целесообразно выбирать равной разря ности ш входных сигналов. Это позволяет рассчитать порог как по шу,мовой (калибровочной ) выборке, так И по реальной информации - смеси си нала и шума. Разрядность выходной информации порога выбирается в предположении, что уровень шумов всегда меньше уро ня входных сигналов р т -1. Для систем цифровой фильтрации или корр ляционной обработки максимальный ур вень амплитуды шума в выходных дискретах составляет примерно 21, а средний уровень шума не превышает 1 от значения амплитуды сигнала. Выбор порога, в два раза превьшающеl ro средний уровень шума (I/4 от ам литуды сигнала), гарантирует исключение шумовых выбросов из информации, выдаваемой для дальнейшей обра ботки. В этом случае значение р мо но выбрать, записав условие равенства амплитуд сигнала и порога , откуда после логарифмирования получаем р m -2 . Дпя решения других задач значение ,f можно выбрать исходя из конкретных условий. Сигналом единичного уровня, подан11ым по шине 27 начальной установки устройства, триггеры 25 узла 21 распределения тактовых сигналов устанавливаются в состояние О. Единичный уровень с инверсного выхода р-го триггера 25, поданный на р-й элемент И 24, открывает цепь прохождения р-го тактового сигнала: элементы И 24, ИЛИ 22, р-й вход 18 тактового сигнала всех узлов I сравнения. Сигналы нулевого уровня с прямого выхода всех триггеров 25, поданные на соответствующие входы элементов ИЛИ-НЕ 26, вызывают появление на их выходах сигналов единичного уровня, которые открывают цепи прохождения сигналов с р-го по первый. Сравнение производится во всех разрядах сравниваемых чисел (тактовые сигналы с-т-го по ф-+1)-й подаются, непосредственно на входы 18 тактовых сигналов всех узло,в сравнения). Рассчитанный в узле 28 порог подается с выхода 30 на вход узла 2I распределения тактовых сигналов и устанавливает в состояние 1 соответствующие триггеры 25. Сигнал единичного уровня с прямого выхода установленного в состояние 1 триггера 25, имеющего наибольший номер, например Е-й, подается на соответствующиевходы элементов ИЛИ-НЕ 26 с F-ro по первый. Сигналы нулевого уровня с выхода этих элементов, поданные на входы элементов И 24, разрывают цепи прохождения тактовых сигналов. Сравнение в разрядах чисел с Е-го по первый не производится. Если , то нулевой уровень с инверсного выхода р-го триггера 25, поданный на вход р-го элемента И 24, разрывает цепь прохождения p-rd тактового сигнала. Цепи прохождения тактовых сигналов с (p-l)-ro по первый также разомкнуты. Сравнение чисел производится по тактовым сигналам только в старших (с гц-го по (р+1,)-й) разрядах. Поскольку предлагаемое изобретение не создает экономии, а направлено на улучшение технических характеристик, производим сравнение достоверности информации, ныдаваемой для дальнейшей обработки предпагаемым и известным устройствами. В качестве критерия сравнения принимаем значение условной вероятности ложной тревоги, характеризующее достоверность информации. Условная вероятность ложной тревоги F представляет собой среднее число ложной информации, выдаваемой после обнаружения экстремумов в массиве зашумпенных значений дискретной функции для дальнейшей обработки. Для известного устройства так как устройство обнаруживает все экстремумы в обрабатываемом массиве, о.тносящиеся как к полезным сигналам, так и к шумовым выбросам Для предлагаемого устройства зна чение можно опре;;елить по выражению для условной вероятности ложной тре воги устройства порогового обнаружения .F (п)1 у - фиксированный уровень порога По уровень .шумов помех ; и значение табулированного интеграла вероятности. При УО По ) Ф(1) 0,8427, ,86-IO-Z. При () ф (2)0,9953, ,35- 10. Уменьшение количества ложной ин формации, выдаваемой для дальнейшей обработки, для предлагаемого устрой ства по сравнению с известным опре деляется как W Fg/F5 ,2; .WiSl2,7; .426. Введение порога :рассчитываемого по уровню шумов, сказывается на уровень условной вероятности правильного обнаружения полезных сигналов 3) -г-| 1 iVx-yo 11 + и Я уровень сигнал Величина D существенно зависит от отношения сигнал/шум на входе устро ства порогового обнаружения. Для того, чтобы обеспечить вероятность правильного обнаруже1шя полез1гых сигналов в диапазоне (),5...1, необходимым условием является равенство Ф(-i-fi-) 0. . . 1 . По значениям ф(п) находим --- 0.. .3. .п 6 X - уо 0...3, откуда При ур Пр отношение сигнал/шум -:-- 1...2. X - 2по При УЭ 2 «о---а 0. ..3, отX „ куда ---. 2. . .5. В цифровых согласованных фильтрах отношение сигнал/шум на выходе тем больше, чём больше коэффи1и1ент сжафильтра (для современных тия к фильтров к может достигать величины 10 и более). Это означает,. что наличии полезных сигналов в обрабатываемом массиве значение вероятности правильного обнаружения близко к единице. Введение порога сравнения, рассматриваемого по уровню шумов, позволяет на несколько порядков увеличить достоверность информации (уменьшить количество ложной информации), выдаваемой для дальнейшей обработки предлагаемым устройством, по сравнению с известным при условии превышения сигнала над шумом. Вероятность правильного обнаружения экстре- . мумов полезных сигналов при этом тем больше, чем больше отношение сигнал/шум на входе устройства. Предлагаемое устройство может быть использовано при построении специализированных средств цифровой обработки сигналов в системах гидро, -радио- и звуколокации и навигации для уменьшения объема данных, выдаваемых для дальнейшей обработки. Это позволит освободившееся время перераспределить между другими задачами обработки. П, г J, Ч L M tHf I I Ч : JJ

If

28

30

0t4tZ

Пя Гга

Ill --- LiJ

г™1

TR PS. Й и

га rmT Г||1

iTyj fcrS

51

npSal

Ш

J kryj

IVinПр ч1

IfojlEB

iri ril