Добрый вечер! Есть массив 128 точек выборок, который соответствует периоду сигнала. Есть 100 эталонов сигнала, которые представляют так же 128 точек выборок, равное периоду сигнала. Необходимо определить насколько сигнал похож на эталон. Проблема заключается в том, что сигнал может отличатся по фазе с эталоном и зачастую искажен. Если тупо перебором, то нужно сравнить 128*128 (со сдвигом) для одного эталона. Это очень долго. Подозреваю, что данная проблема решается с помощью преобразований Фурье, но как приступить я не знаю. Может кто то подскажет метод решения.

Cуществуют конечно научный способы вычисления корреляции, но можно попробовать по типу разложения по квадратурам. Сдвинуть тестовый сигнал на 90гр. и сделать перемножение сигнала на две квадратуры тестового сигнала, а потом посчитать что то типа модуля.
Ну либо если нужен научный метод, то искать алгоритмы вычисления корреляции.

128*128*100 == 1.6E6 умножений, на калькуляторе считаете, что очень долго получается? насколько надо быстро?
преобразованием Фурье проблема решается в том смысле, что амплитуда спектра от фазы не зависит, так что если эталоны настолько разные что у них амплитуды спектров отличаются настолько что информацию о фазе можно выкинуть, то считайте Фурье и сравнивайте только амплитуды в частотной области.
если одной амплитуды не хватит, то фазы при сдвиге отличаются только добавлением линейной зависимости к*w, соответственно можно наверное в первом приближении просто вычесть линейный фит из ФЧХ и сигнала и эталонов, убрав тем самым неизвестный сдвиг по фазе.

Это называется преобразование Гильберта.

Только зачем оно здесь? Разве в описанном методе есть какое-то сравнение сигнала с эталоном?

Что касается вопроса ТС. Да, можно применить преобразование Фурье.

Для сравнения сигналов используют понятие корреляции. Вычисление корреляции двух сигналов = вычисление свёртки этих двух сигналов.

БПФ можно использовать для вычисления так называемой быстрой свёртки. В спектральной области свёртка заменяется на простое умножение.

То есть, схема примерно такая: есть принятый сигнал s(t) и набор эталонов Ai(t). Вычисляем БПФ[s(t)] и БПФ[Ai(t)]. Вычисляем x = БПФ[s(t)]*БПФ[Ai(t)]. В конце вычисляем ОБПФ[x].

Спасибо за подсказку, я не мог понять, где взять мнимую часть сигнала. Действительно сдвинув сигнал на 90 градусов я получаю мнимую часть сигнала. Для одной свертки я должен получить 4 массива: M1, M2, M3, M4, где M1 cos сигнала, M2 sin сигнала, M3 cos эталона, M4 sin эталона. Отдельно суммирую от n=0..127: M1(n)*M3(n) - M2(n)*M4(n) и M1(n)*M4(n)+M3(n)*M2(n). Затем эти суммы возвожу в квадрат и суммирую и извлекаю корень квадратный. Что мне даст эта свертка? Я так понимаю, что если сигналы совпадают я получу максимальное значение амплитуды?




Предположим я вычислил БПФ и получил амплитуды разных частот. На какое количество частот разбить сигнал? Для каждой частоты нужно произвести свертку. Если частот много - это слишком затратно по вычислениям, даже если применить БПФ. Не пройдет ли одна свертка с эталоном сигнала, как я написал выше?

Почитайте про согласованный фильтр.

Ну вы писали, что у вас сигнал из 128 отсчетов. Следовательно, БПФ тоже должен быть на 128 точек - получается, для сравнения сигнала с одним из эталонов надо 2 БПФ, 128 умножений и ОБПФ.

Сообщение отредактировал el.d - Dec 19 2017, 10:40

с учётом того, что БПФ на обычных МК вроде кортексов делаются за ~100 тактов на отсчёт, на таких коротких выборках делать 2 раза БПФ, туда и обратно, (для эталонов можно посчитать заранее) получается не быстрее чем тупо посчитать корреляцию за 128*128 умножений во временной области.

Да, скорее всего выигрыш от вычисления свёртки через БПФ будет весомым для бОльшего количества точек. Правда, ТС ничего про МК не говорил.

Сообщение отредактировал el.d - Dec 19 2017, 10:53

Не так, для построения БПФ на 128 частот потребуется применить 127 "бабочек". Каждая бабочка это 4 умножения и 4 суммирования. Следовательно, умножений нужно сделать 127*4=508. Для эталонов БПФ выполнять не нужно, его можно выполнить 1 раз и забить в память. После БПФ нам нужно рассчитать амплитуду сигнала для каждой из 128 частот. Т.е. возвести в квадрат действительную и мнимую часть, сложить и найти корень квадратный. И можно сравнивать с амплитудами эталонов забитыми в память. Зачем мне делать обратное преобразование Фурье?

Потому что корреляционная функция (результат свёртки принятого сигнала с эталоном) - это функция от времени. После применения БПФ к принятому сигналу или к эталону получается функция от частоты.

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

Сообщение отредактировал el.d - Dec 19 2017, 11:27

Вы правильно написали, что амплитуды будут разные. Но амплитуды можно нормировать. Амплитуда, как раз и отвечает за отклик на ту или иную частоту и сравнивать я могу только амплитуды (как иначе, что с чем я должен сравнивать. Только мне нужно не теоретически, а что с чем я должен сравнить?).
После БПФ мы можем построить амплитудно-частотную характеристику, которую можно сравнить с эталоном.

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

Сообщение отредактировал el.d - Dec 19 2017, 11:45

Хотелось бы конкретную привязку. На вход БПФ я подаю сигнал, который представляет 128 выборок. Если бы я делал в аналоговом виде, то мне нужно было бы поставить 128 фильтров, каждый из которых пропускает только свою частоту (настроены на разные частоты). На выходе каждого фильтра я получаю синусоиду одной данной частоты. Поэтому мне надо поставить после каждого фильтра выпрямитель и мерить амплитуду после каждого фильтра.
В цифровом виде в качестве выпрямителя и будет вычисление амплитуды.


Зачем делать обратное преобразование Фурье (ОБПФ) и что с чем сравнивать я так и не понял?

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

Вы видимо пропустили то сообщение, где я говорил, что БПФ как раз и используем для вычисления свёртки принятого сигнала с эталоном.

Еще раз: свёртка[принятый сигнал,эталон] = ОБПФ[БПФ[принятый сигнал]*БПФ[эталон]].

Это так называемая быстрая свёртка, по результатам - ничем не хуже классической. Доказательство можно посмотреть в любом учебнике по ЦОС.

Однако, данный метод точно дает ускорение в случае относительно большого числа точек БПФ (тысячи). Даст ли этот метод прирост в вашем случае - зависит от того, что и как делать.