Дан короткий дискретный звук как набор отсчётов (длительностью, ну, например, 1/10 секунды). Нужно определить частоту звука, с хорошей точностью. 

Если использовать Дискретное Преобразование Фурье (ДПФ), то, чтобы вычислить с точностью, скажем, 1Гц, надо брать интервал в 1 секунду (а у меня длительность звука --- 1/10 сек).

PS. Отсчётов достаточно и известно что частота сигнала достаточно большая для вычисления. Ещё лучше было бы если бы целиком спектр удалось найти, но это уже не обязательно

 Вам прямая дорога в FFT. Вот только Вы должны указать верхнюю частоту спектра исследуемого звука - отсюда частота дискретизации, а из нее сколько именно сэмплов содержит Ваш интервал рассмотрения. Например верхняя частота 4 kHz - частота дискретизации 8 kHz, 0.1 секунды 800 отсчетов. Можно сделать FFT на 800 точек (это не RADIX2 который можно встретить в любом учебнике), можно передискретизировать сигнал под степень 2-ки (а еще большая удача если изначально колличество семплов в интервале совпадает).
 Кстати, поскольку отсчеты у Вас только вещественные то FFT должно быть либо вещественное (отдельная методика) либо обнулен один из входных массивов (если нет желания/времени копаться с готовым алгоритмом)...
 Для 800 отсчетов FFT даст ровно столько же выходных бинов т.е. разрешение по частоте будет 10 Hz, причем соседние отсчеты будут влиять друг на друга по закону sinc(f) (т.е. (sin(f))/ f ) лучшее частотное разрешение можно получить только накоплением - оверсэмпленгом. 
 Но... если стоит задача не привязанная именно к представлению Фурье - например распознавание или выявление наличия определенной частоты, то можно воспользоваться гораздо менее ресурсоемкими представлениями например быстрым дискретным косинусным преобразованием...


Так нельзя говорить, есть понятие теоремы Котельникова-Найквиста от нее и пляшем - с точными значениями...

FFT -- это убыстренное дискретное преобразование Фурье, то есть разложение по синусам кратных дуг. Эта дуга должна полностью укладыватся в интервале подсчёта.  Мне нужно определить частоту с точностью до 1Гц, значит дуги должны быть кратны 1сек  и надо брать изначальный интервал в 1сек, но звук у меня известен только на 1/10 сек! Я же, услышив его, могу понять, какая это нота!


Я имел ввиду, что кол-во отчётов можно будет увеличить при необходимости, а низкие частоты распознавать не надо (я понимаю, что для низких частот нужна большая длительность). Всё ограничено только длительностью сигнала.

Да с чего Вы взяли такую глупость? Сами придумали или такое уже в нерецензируемых книжках пишут?

Добавлено через 1 минуту и 15 секунд

Та откуда???    Нет! Вы неверно понимаете преобразование Фурье.

Добавлено через 1 минуту и 50 секунд

Чтобы узнать ноту незачем точность в 1 Hz...

Добавлено через 4 минуты и 38 секунд
FFT это не разложение ни по каким синусам кратных дуг... это разложение по комплексным экспонентам exp(j*w) = cos(w) + j*sin(w);

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

Это я к тому что даже 2-х точечное FFT даст математически корректные выходные данные для 0-й(!!! по сути постоянная составляющая) и Fs/2 частот. 

Если же Вы имели в виду, что допустим что-то(сигнал) меняется по низким частотам недостаточно быстро что-бы его отследить то точно такое же изменение по высоким мы тоже не успеем отследить. Вобщем - у Вас неверная формулировка.

Так что лучше детально опишите задачу - какой диапазон частот и что именно (я так понял ноту) нужно распознать.

P.S.:2-а отсчета прошедшие через аналоговый фильтр низких частот (а это АБСОЛЮТНО ОБЯЗАТЕЛЬНАЯ часть любого DSP устройства, например звуковой карты) дадут на выходе синусоидальный всплеск.

Ну хорошо, не по синусам, если вам так хочется, а по экспонентам, но всё равно, период там будет делить длину интервала, на котором происходит вычисление. ДПФ вычисляет коэффициент A_k при e^(2πikn/N) (это можно записать и в синусной форме и в косинусной и в смешанной). Т. о. первая гармоника имеет периодом --- исходный интервал. Вторая --- пол интервала, третья треть и т. д. Если я возьму интервал, скажем, 1/2 секунды, что периоды гармоник будут кратны 2Гц, что не годится. Или я неправ? Тогда как задать точность?

Про низкие частоты я имел ввиду, что кажется, в интервале должно укладываться два периода для корректного восстановления (а у низких частот периоды длинные), а нулевая гармоника получается естественно.

Задача, например:
дано 4410 отсчётов на 1/10 сек. Нужно определить частоту от, скажем от 200Гц до 4000Гц с точностью до 1Гц (или хотя бы с максимальной точностью). 

Это сообщение отредактировал(а) d06osipov - 2.7.2008, 09:35

Это не мне так хочется, это само определение преобразования Фурье. В синусной(и любой другой) форме это не Фурье спектр.




да... 3-я особенно у вас классно ... например если 8 отсчетов.
 Нееееееет!!!  Это Вы что-то все в одну кучу. Это быстрые вейвлеты так вычисляются и то с точностью до наоборот - чем ниже частота тем меньше отсчетов (не противоречит Котельникову-Найквисту разумеется).

В Фурье - первая гармоника коррелируется абсолютно со всеми отсчетами, вторая со всеми, треться со всеми, четвертая со всеми и т.д.

Ну да, длинная. Так вот это и попадет в наименьшую ширину бина. Т.е. что-то вы поняли может и правильно но сказали не "политкорректно"   .

Т.е. Fs = 44 100 Hz. Ну седлав FFT на 4410 точки получите спектр с шагов 10 Hz. Большее разрешение можно получить увеличив колличество точек накоплением большего интервала. 
Есть правда абсолютно маразматичный способ - из 4410 отсчетов сделать 44100 вставив по линейной интерполяции 9 отсчетов между ралными. Но это маразм чистой воды ничего с действительностью не имеющий.

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

Вот оно! Мне нужна точность (то есть шаг) 1 Герц. При длине интервала 1/10 сек! Иначе не было бы проблемы.




Не хочу спорить, но применив формулы
sin x= e^ix-e^-ix/2i
cos x=e^ix+e^-ix/2
A sin x + B cos x = sqrt(A^2+B^2)cos(arctg(-B/A)+x)
Можно свести экспоненту с синусам и косинусом или даже к одной функции. Может, это не будет называться спектром фурье, но будет ему равно.




А можно по-подробнее?

Ну да, все верно, вместо значений проекций Вы берете абсолютную длину и фазу - величины однозначно от длинны проекций зависящие. Это же не разложение по косинусам, это сведение к одной з форм записи разложения в проекции на cos(w) - j*sin(w). Но это не то, что можно было подумать. Просто по косинусам можно разложить и совершенно по иному. Но не будем хвастаться друг перед другом глубиной трактовки школьного курса математики   ...



А что именно подробнее? Это целое подмножество ЦОС - бесконечное в своем многообразии.   
Ну если навести на мысль, разве что... Знакомы с понятием корреляции и коэффициента корреляции?
Представим такой скользящий FIFO алгоритм. Вот Ваш болчок в 4410 отсчета сворачивается с синусоидой на 44100 (да хоть на 50000) отсчетов. На выходе имеем 44100 (50000) отсчетов отклика. Этот отклик грубо говоря суммируем в одно число и компаратором ("1" если больше заданного порога иначе "0") проверяем была нота или нет При этом происходит размен точности определения амплитуду на точность определения частоты. Те же яйца только в профиль - кратковременное  FFT.
... Но это только вариант из неисчислимого множества.

Это сообщение отредактировал(а) DRUID3 - 2.7.2008, 11:55

Я знаю, что это такое из теории вероятностей, но какой смысл у этого в ДПФ не знаю.


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

Если всё прокатит, всё равно есть такая проблема: 
Скажем, у меня нота с частотой 440,5Гц , кроме того там есть ещё первый обертон с частотой 881Гц. Если я разложу в фурье с шагом 1, то у меня будут большие коэффициенты при 440-й и 441-й гармониках, но при 881 будет всё равно, гораздо больше. Если я буду находить максимум модуля коэффициента в таком случае, то я получу обертон --- 881Гц.

Философский(как и в теорвер) смысл корреляционной функции - функция подобия. Берем отсчеты в каждой точке, одной функции и умножаем на соответствующие отсчеты в другой -> если одна из функций обращается в "0"-ль в него же обращается и корреляционная функция, максимальные отсчеты одного знака дадут максимальное значение этой функции(максимум совпадения), "разнополярные" отсчеты дадут отрицательный отсчет (антисовпадение) и т.д.

Автокорреляционная функция - смотрим первый пункт, с одной лишь особенностью - вместо 2-х разных функций теперь вычисляется взаимосовпадение функции с собой же, сдвинутой на определенный временной интерал (запаздывающей). Очень эффективный метод выявления периодичности в функции - оно и понятно, раз функция периодична то сдвинув ее на определенный интервал получим максимальное совпадение отсчетов...

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

Корреляция(автокорреляция, свертка) (число) - все отсчеты полученной функции мы просуммировали и поделили на их(отсчетов) количество - плучается эдакое абстрактное число характеризующее подобие функций. Но им довольно неудобной пользоваться - два абсолютно одинаковых случая для функции но взятые с разным в  масштабом дадут совершенно разные числа. Потому для числового определения взаимопохожести функций намного чаще используют коэффициент корреляции. Корреляцию делят на произведение средней мощности каждой из функций на рассматриваемом периоде. Понятие "мощность" - очень условное, потому как сами определения пришли к нам из электросвязи, но точно такая формула справедлива для статистики, экономики и т.д. Каждый отсчет возводится в квадрат (как в если бы
это было напряжение в извесной формуле нахождения мощности когда известно действующее напряжение и константное - не меняющееся - сопротивление) а затем все они суммируются и делятся на количество отчетов(нормировка) и из этого числа извлекается корень.
Коэффициент корреляции - число принимающее на интервале [-1..1]. Соответственно "-1" -> функции антисовпадатют (компенсируют друг-друга суммированием), "1" -> абсолютное совпадение (одна и та же функция), "0" -> абсолютно независимые на интервале(ортогональные) функции. У этого параметра есть очень забавная интерпретация (если не забывать о трактовке математики как непрерывном континиуме  ) - если предположить, что каждый числовой отсчет функций между которыми находится коэффициент корреляции на интервале длительностью N - это 
одна из координат некоего абстрактного вектора в N-мерном пространстве, то коэффициент корреляции ни что иное как косинус угла между этими векторами! Корреляция - ни что иное как скалярное приизведение этих векторов. А компоненты усредненной мощности - это модули векторов(их абсолютная длинна) в N-мерном пространстве...      

 Вобщем очень хорошее (просто замечательное введение в ЦОС вот)... Есть в электронном виде, но я рекомендую купить с любой раскладки и держать под рукой  ...



А кто определяет интервал свертки(корреляции)???  Вот только про "пик" - неосилил... Пик в частотной или временнОй области?


Да откуда Вы такое берете???   Некий смысл конечно в этом есть, но если речь о музыкальных инструментах (а не лабораторных приборах) - это не реально. Если у Вас есть обертон, он по мощности слабее первой гармоники и даже не в половину (у симметричного относительно "0"-я меандра и то слабее третья гармоника). Что это за струнно-духовой камертон излучающий дельта-функции?  Причем бин FFT это не просто так - это не какой-то сплошной фильтр это sinc(w). Потому если синусоида встанет между бинами она будет не в 2-а раза (а намного меньше) слабее своего истинного размера...

Берём ваши семплы, которых хватает на 1/10 секунды. Херачим по бокам нули так, чтобы хватило на целую секунду. Теперь у вас секунда звука, т.е. 44100. Но FFT хочет степень двойки семплов. Придётся нахерачить до 65536. Берём от этого добра FFT, получаем 32768 частотных канала. Это даже больше, чем вам надо. Точность будет повышенная.

Но когда вы дописывали нули, вы создали новый вид сигнала, в котором сначала идёт ноль, потом резко начинается ваш сигнал, потом он резко обрывается. Это резкое начало и резкий обрыв FFT будет стараться как-то представить, "описать синусами и косинусами". Эти резкие вещи будут видны как комбинация большой энергии на многих частотах одновременно. Поэтому, края лучше скруглить - точнее умножить ваши 1/10 отсчёта на кусок синуса (кусок длиной ПИ - нарастает с нуля до 1->спадает с 1 до нуля). Это, вроде, называется окном ханна. Эти окна - отдельный разговор ваще.