Объясните FFT мне
Нет такой вещи, как “good хеширует function” для универсальных хешей (редактор да, я знаю, что существует такая вещь как “universal hashing”, но это не то, что я имел в виду). В зависимости от контекста различные критерии определяют качество хеша. Два человека уже упомянули SHA. Это - криптографический хеш, и это не во всей пользе для хеш-таблиц, которые Вы, вероятно, имеете в виду.
Хеш-таблицы имеют совсем другие требования. Но тем не менее, нахождение хорошей хеш-функции универсально трудно, потому что различные типы данных выставляют другую информацию, которая может быть хеширована. Как показывает опыт, хорошо рассмотреть весь информация, которую тип содержит одинаково. Это не всегда легко или даже возможно. По причинам статистики (и следовательно коллизия), также важно генерировать хорошее распространение по пространству задач, т.е. все возможные объекты. Это означает, что при хешировании чисел между 100 и 1050 это бесполезно, чтобы позволить старшей значащей цифре играть большую роль в хеше, потому что для ~ 90% объектов, эта цифра будет 0. Намного более важно позволить последним трем цифрам определить хеш.
Точно так же при хешировании строк важно рассмотреть все символы †“кроме тех случаев, когда известно заранее, что первые три символа всех строк будут тем же; рассмотрение их затем является отходами.
Это - на самом деле один из случаев, где я советую для чтения то, что Knuth должен заявить в Искусство Программирования , издание 3. Другим хорошим чтением является Julienne Walker Искусство Хеширования .
3 ответа
На самом деле вы можете искать спектрограмму , которая в основном представляет собой БПФ данных в небольшое окно, скользящее по оси времени. Если у вас есть программное обеспечение, которое реализует это, это может сэкономить вам некоторые усилия. Это то, что обычно используется для анализа изменяющихся во времени акустических сигналов, и это очень полезный способ изучения звуков. Кроме того, есть некоторые уловки, например, с оконными данными для БПФ, которые спектрограмма, вероятно, будет правильной, но вам будет труднее (хотя и не очень сложно) сделать правильно.
Если частота дискретизации ваших данных PCM равна F, то самая высокая частотная составляющая в БПФ - F / 2. Предположим, ваши данные PCM были выбраны на частоте 44100 Гц, тогда ваши значения FFT будут работать от 0 Гц (DC) до 22050 Гц. Если вы начнете с N выборок (N - степень 2), тогда БПФ может вернуть N / 2 значений, представляющих все положительные частоты от 0 до F / 2, или может вернуть N значений, которые также включают отрицательные частоты из - От F / 2 до 0. Вы должны проверить спецификацию вашего алгоритма БПФ, чтобы узнать, с какой частотой отображается каждый элемент массива.
Чтобы найти пики, вам нужно посмотреть на величину значений БПФ. Таким образом, вам нужно сложить квадрат действительной и мнимой частей каждого комплексного значения.
Предположим, что ваш БПФ из N выборок PCM возвращает N / 2 комплексных значений, представляющих положительные частоты. Тогда расстояние между двумя комплексными отсчетами составляет F / 2N Гц. При F = 44100 Гц и N = 1024 отсчета это будет 21,5 Гц. Это ваше разрешение по частоте. Если вам нужно найти биения с более низкой частотой, необходимо расширить окно БПФ.
хорошо, Необработанный массив комплексных чисел размером 512, выражающий входную волну, при обработке с помощью БПФ мы заменим мнимые части нулем (в соответствии с предполагаемым использованием), оставив реальные части, а затем передадим массив в БПФ с частотой дискретизации: 8192 Гц.
Теперь у нас есть 512 массивов БПФ реальных значений, каждое значение - иррациональное число, каждое иррациональное число выражает несколько полезных значений.
Чтобы получить основную частоту, мы должны разделить частоту дискретизации на размер буфера :
8192/512 = 32;
32 - разрешение значений БПФ, означает, что мы узнаем частоты высокой амплитуды около чисел, кратных 32.
Как если бы у нас есть волна
частоты: 3 48 23 128 Амплитуда: 10 5 12 8 дБ (ref = 1)
после БПФ получаем:
частота: 0 32 64 128 Амплитуда: 9 8 2 8
БПФ в частотной области означает, что он упорядочивается в соответствии с частотой С другой стороны, временная область означает упорядочение по времени, которое мы слушаем, от второго нуля до секунды N.
БПФ может слушать только тогда, когда оно расположено по частоте от частоты 0 до частоты N.
Таким образом, оно распределяет частоты по возрастанию. заказ, поскольку он не взял все фактические выборки из звука (которые приближаются к бесконечности), например, каждую наносекунду и меньше на БПФ, к счастью, этого не происходит БПФ берет выборки из аудио, берет выборку каждые (1 / частота дискретизации) секунда. эти сэмплы буферизуются (в нашем случае: 512), каждые 512 сэмплов буферизуются в БПФ, на выходе получается 512 значений БПФ.
Так как БПФ упорядочивает частоты, оно искажает временные выборки, теперь выборки упорядочены в соответствии с их частотами.