Fft size что это
ACMLib
Быстрое преобразование Фурье
Мотивировка
Хитрость FFT в том, что точки, в которых считаются значения многочлена, выбираются отнюдь не произвольным образом.
Описание
Тут сразу возникает два вопроса:
С первым вопросом всё просто: нужно дополнять коэффициенты нулями до ближайшей степени двойки.
Разделяй и властвуй
Обратное преобразование
Можно рассмотреть FFT как линейное преобразование:
Таким образом, обратное преобразование выглядит следующим образом:
Оптимизации
Что мы глобально делаем:
Если один раз в самом начале применить все перестановки индексов, то можно будет сразу двигаться от более глубоких уровней рекурсии в начало.
Как переставляются индексы: в левую часть идут чётные индексы, в правую — нечётные, потом к каждой из половин рекурсивно примерняется то же правило. Если рассмотреть битовую запись числа, то мы сначала сортируем по младшему биту, потом “отрезаем” его и делаем дальше то же самое. Нетрудно догадаться, что мы на самом деле сортируем индексы по реверснутой битовой записи; строгое доказательство проводится мат.индукцией по номеру уровня.
Наконец, можно уменьшить количество умножений комплексных чисел. Вспомним, что
Их можно считать одновременно, это уменьшит количество умножений вдвое.
Умножение многочленов
Размер применяемого FFT должен быть строго больше, чем степень произведения многочленов.
В задачах часто многочлены имеют целочисленные коэффициенты, причём неотрицательные. Понятно, что при таких условиях коэффициенты у произведения будут тоже целыми и неотрицательными.
С таким способом округления следует быть осторожным, он верен только для неотрицательных чисел. Если коэффициенты многочлена могут быть отрицательными, следует округлять аккуратно:
Разные мелочи
Удивительно, но написание своего класса Complex также может уменьшить время работы.
Операции по модулю
“Хороший” модуль
Любой модуль
Тут есть два принципиально разных подхода:
Несколько хороших модулей + Китайская теорема об остатках
Название говорит само за себя. Можно незавсимо выполнить умножение по 3 разным хорошим модулям, а потом узнать искомые коэффициенты при помощи КТО.
Разбить на многочлены с меньшими коэффициентами
Применение
Понятно, что FFT используется для умножения многочленов, так что это будет скорее описание применений умножения многочленов.
Умножение длинных чисел
Вычисление скалярных произведений
Нечёткий поиск
Все суммы
Динамическое программирование
Иногда в ДП переход выглядит как свёртка, и его можно ускорить при помощи FFT.
Преобразование Фурье в действии: точное определение частоты сигнала и выделение нот
Начнём с пианино. Очень упрощёно этот музыкальный инструмент представляет собой набор белых и чёрных клавиш, при нажатии на каждую из которых извлекается определённый звук заранее заданной частоты от низкого до высокого. Конечно, каждый клавишный инструмент имеет свою уникальную тембральную окраску звучания, благодаря которой мы можем отличить, например, аккордеон от фортепиано, но если грубо обобщить, то каждая клавиша представляет собой просто генератор синусоидальных акустических волн определённой частоты.
Когда музыкант играет композицию, то он поочерёдно или одновременно зажимает и отпускает клавиши, в результате чего несколько синусоидальных сигналов накладываются друг на друга образуя рисунок. Именно этот рисунок воспринимается нами как мелодия, благодаря чему мы без труда узнаём одно произведение, исполняемое на различных инструментах в разных жанрах или даже непрофессионально напеваемое человеком.
Наглядная иллюстрация нотного рисунка
Определение частоты (режим гитарного тюнера)
Обратная задача состоит в том, чтобы разобрать звучащую музыкальную композицию на ноты. То есть разложить суммарный акустический сигнал, улавливаемый ухом, на исходные синусоиды. По сути, этот процесс и представляет собой прямое преобразование Фурье. А нажатие на клавиши и извлечение звука есть процесс обратного преобразования Фурье.
Математически в первом случае происходит разложение сложной периодической (на некотором временном интервале) функции в ряд более элементарных ортогональных функций (синусоид и косинусоид). А во втором их обратное суммирование, то есть синтез сложного сигнала.
Ортогональность, в некотором роде, обозначает несмешиваемость функций. Например, если мы возьмём несколько кусочков цветного пластилина и склеим их, то потом всё же сможем разобрать, какие цвета были изначально, но если хорошенько перемешаем несколько баночек гуашевых красок, то точно восстановить исходные цвета без дополнительной информации уже будет невозможно.
(!) Важно понимать, когда мы берёмся анализировать реальный сигнал с помощью преобразования Фурье, мы идеализируем ситуацию и исходим из предположения, что он периодический на текущем временном интервале и состоит из элементарных синусоид. Зачастую это именно так, поскольку акустические сигналы, как правило, имеют гармоническую природу, но вообще возможны и более сложные случаи. Любые наши допущения о природе сигнала обычно ведут к частичным искажениям и погрешностям, но без этого выделить полезную информацию из него крайне сложно.
Теперь опишем весь процесс анализа более подробно:
1. Всё начинается с того, что звуковые волны колеблют мембрану микрофона, который преобразует их в аналоговые колебания электрического тока.
2. Затем происходит дискретизация аналогового электрического сигнала в цифровую форму. На этом моменте стоит остановиться подробно.
Поскольку аналоговый сигнал математически состоит из бесконечного непрерывного во времени множества точек-значений амплитуды, в процессе измерения мы можем выделить из него лишь конечный ряд значений в дискретные моменты времени, то есть, по сути, выполнить квантование по времени…
Как правило, значения-отсчёты берутся через небольшие равные временные промежутки, то есть с определённой частотой, например, 16000 или 22000 Гц. Однако в общем случае дискретные отсчёты могут идти и неравномерно, но это усложняет математический аппарат анализа, поэтому на практике обычно не применяется.
Существует важная теорема Котельникова-Найквиста-Шеннона, которая гласит, что аналоговый периодический сигнал, имеющий конечный (ограниченный по ширине) спектр, может быть однозначно восстановлен без искажений и потерь по своим отсчётам, взятым с частотой, большей или равной удвоенной верхней частоте спектра (называемой частотой дискретизации или Найквиста).
Для этого восстановления необходимо применить специальные интерполирующие функции, но проблема в том, что при использовании данных функций вычисления нужно выполнять на бесконечном временном интервале, что на практике невозможно. Поэтому в реальной жизни нельзя сколь угодно повысить частоту дискретизации искусственным образом без искажений даже если изначально она удовлетворяет теореме Котельникова-Найквиста-Шеннона. Для этой операции применяются фильтры Фарроу.
Также дискретизация происходит не только по времени, но и по уровню значений амплитуды, поскольку компьютер способен манипулировать лишь ограниченным множеством чисел. Это также вносит небольшие погрешности.
3. На следующем этапе происходит само дискретное прямое преобразование Фурье.
Мы выделяем короткий кадр (интервал) композиции, состоящий из дискретных отсчётов, который условно считаем периодическим и применяем к нему преобразование Фурье. В результате преобразования получаем массив комплексных чисел, содержащий информацию об амплитудном и фазовом спектрах анализируемого кадра. Причём спектры также являются дискретными с шагом равным (частота дискретизации)/(количество отсчётов). То есть чем больше мы берём отсчётов, тем более точное разрешение получаем по частоте. Однако при постоянной частоте дискретизации увеличивая число отсчётов, мы увеличиваем анализируемый временной интервал, а поскольку в реальных музыкальных произведениях ноты имеют различную длительность звучания и могут быстро сменять друг друга, происходит их наложение, поэтому амплитуда длительных нот «затмевает» собой амплитуду коротких. С другой стороны для гитарных тюнеров такой способ увеличения разрешения по частоте подходит хорошо, поскольку нота, как правило, звучит долго и одна.
Существует также довольно простой трюк для увеличения разрешения по частоте — нужно исходный дискретный сигнал заполнить нулями между отсчётами. Однако в результате такого заполнения сильно искажается фазовый спектр, но зато увеличивается разрешение амплитудного. Также возможно применение фильтров Фарроу и искусственное увеличение частоты дискретизации, однако и оно вносит искажения в спектры.
Длительность кадра обычно составляет приблизительно от 30 мс до 1 с. Чем он короче, тем лучшее разрешение мы получаем по времени, но худшее по частоте, чем сэмпл длиннее, тем лучшее по частоте, но худшее по времени. Это очень напоминает принцип неопределённости Гейзенберга из квантовой механики..и не с проста, как гласит Википедия, соотношение неопределенностей в квантовой механике в математическом смысле есть прямое следствие свойств преобразования Фурье…
Интересно и то, что в результате анализа сэмпла одиночного синусоидального сигнала амплитудный спектр очень напоминает дифракционную картинку…
Синусоидальный сигнал, ограниченный прямоугольным окном, и его «дифракция»
Дифракция световых волн 
На практике это нежелательный эффект, затрудняющий анализ сигналов, поэтому его стараются понизить путём применения оконных функций. Таких функций придумано немало, ниже представлены реализации некоторых из них, а также сравнительное влияние на спектр одиночного синусоидального сигнала.
Применяется оконная функция ко входному кадру очень просто:
Что касается компьютеров, в своё время был разработан алгоритм быстрого преобразования Фурье, который минимизирует число математических операций, необходимых для его вычисления. Единственное требование алгоритма состоит в том, чтобы число отсчётов было кратно степени двойки (256, 512, 1024 и так далее).
Ниже его классическая рекурсивная реализация на языке C#.
Существует две разновидности алгоритма БПФ — с прореживанием по времени и по частоте, но оба дают идентичный результат. Функции принимают массив комплексных чисел, заполненный реальными значениями амплитуд сигнала во временной области, а после своего выполнения возвращают массив комплексных чисел, содержащий информацию об амплитудном и фазовом спектрах. Стоит помнить, что реальная и мнимая части комплексного числа — это далеко не то же самое, что его амплитуда и фаза!
magnitude = Math.Sqrt(x.Real*x.Real + x.Imaginary*x.Imaginary)
phase = Math.Atan2(x.Imaginary, x.Real)
Результирующий массив комплексных чисел заполнен полезной информацией ровно на половину, другая половина является лишь зеркальным отражением первой и спокойно может быть исключена из рассмотрения. Если вдуматься, то этот момент хорошо иллюстрирует теорему Котельникова-Найквиста-Шеннона, о том, что частота дискретизации должна быть не меньше максимальной удвоенной частоты сигнала…
Также существует разновидность алгоритма БПФ без рекурсии по Кули-Тьюки, которая часто применяется на практике, но она чуть более сложна для восприятия.
Сразу после вычисления преобразования Фурье удобно нормализовать амплитудный спектр:
Это приведёт к тому, что величина значений амплитуды получится одного порядка не зависимо от размеров сэмпла.
Вычислив амплитудный и частотный спектры, легко производить обработку сигнала, например, применять частотную фильтрацию или производить сжатие. По сути, таким образом можно сделать эквалайзер: выполнив прямое преобразование Фурье, легко увеличить или уменьшить амплитуду определённой области частот, после чего выполнить обратное преобразование Фурье (хотя работа настоящих эквалайзеров обычно основана на другом принципе — фазовом сдвиге сигнала). Да и сжать сигнал очень просто — нужно всего лишь сделать словарь, где ключом является частота, а значением соответствующее комплексное число. В словарь нужно занести лишь те частоты, амплитуда сигнала на которых превышает какой-то минимальный порог. Информация о «тихих» частотах, не слышимых ухом, будет потеряна, но получится ощутимое сжатие при сохранении приемлемого качества звучания. Отчасти этот принцип лежит в основе многих кодеков.
4. Точное определение частоты
Дискретное преобразование Фурье даёт нам дискретный спектр, где каждое значение амплитуды отстоит от соседних на равные промежутки по частоте. И если частота в сигнале кратна шагу равному (частота дискретизации)/(количество отсчётов), то мы получим выраженный остроконечный пик, но если частота сигнала лежит где-то между границами шага ближе к середине у нас выйдет пик со «срезанной» вершиной и нам будет затруднительно сказать, что же там за частота. Очень может быть что в сигнале присутствуют две частоты лежащие рядом друг с другом. В этом и заключается ограничение разрешения по частоте. Так же как на фотоснимке с низким разрешением мелкие предметы склеиваются и становятся неразличимы, так же и тонкие детали спектра могут теряться.
Но частоты музыкальных нот лежат далеко не на сетке шагов преобразования Фурье, а для повседневных задач настройки музыкальных инструментов и распознавания нот необходимо знать именно точную частоту. Более того, на низких октавах при разрешении от 1024 отсчётов и ниже сетка частот Фурье становится настолько редкой, что попросту на одном шаге начинают умещаться несколько нот и определить какая же на самом деле из них играет становится фактически невозможно.
Чтобы как-то обойти это ограничение иногда применяют аппроксимирующие функции, например, параболические.
www.ingelec.uns.edu.ar/pds2803/Materiales/Articulos/AnalisisFrecuencial/04205098.pdf
mgasior.web.cern.ch/mgasior/pap/biw2004_poster.pdf
Но всё это искусственные меры, которые улучшая одни показатели могут давать искажения в других.
Существует ли более естественный путь для точного определения частоты?
Да, и скрыт он как раз-таки в использовании фазового спектра сигнала, которым часто пренебрегают.
Данный метод уточнения частоты сигнала, основан на вычислении задержки фаз у спектров двух кадров, наложенных друг на друга, но немного сдвинутых во времени.
На C# реализация метода выглядит довольно просто:
Применение также несложное:
Обычно исходные кадры сдвинуты на 1/16 или 1/32 своей длины, то есть ShiftsPerFrame равно 16 или 32.
В результате мы получим словарь частота-амплитуда, где значения частот будут довольно близки к реальным. Однако «срезанные пики» всё ещё будут наблюдаться, хоть и менее выражено. Чтобы устранить этот недостаток, можно просто «дорисовать» их.
Нотный анализ музыкальных произведений открывает ряд интересных возможностей. Ведь имея в наличии готовый нотный рисунок, можно осуществлять поиск других музыкальных композиций со схожим рисунком.
Например, одно и то же произведение может быть исполнено на другом инструменте, в различной манере, с другим тембром, либо транспонировано по октавам, однако нотный рисунок останется похожим, что позволит найти различные варианты исполнения одного и того же произведения. Это очень напоминает игру «угадай мелодию».
В некоторых случаях подобный анализ поможет выявить плагиат в музыкальных произведениях. Также по нотному рисунку, теоретически, можно искать произведения определённого настроения или жанра, что поднимает поиск на новый уровень.
В этой статье изложены основные принципы точного определения частот акустических сигналов и выделения нот. А также показана некоторая тонкая интуитивная связь дискретного преобразования Фурье с квантовой физикой, что подталкивает на размышления о единой картине мира.
Простыми словами о преобразовании Фурье
Я полагаю что все в общих чертах знают о существовании такого замечательного математического инструмента как преобразование Фурье. Однако в ВУЗах его почему-то преподают настолько плохо, что понимают как это преобразование работает и как им правильно следует пользоваться сравнительно немного людей. Между тем математика данного преобразования на удивление красива, проста и изящна. Я предлагаю всем желающим узнать немного больше о преобразовании Фурье и близкой ему теме того как аналоговые сигналы удается эффективно превращать для вычислительной обработки в цифровые.
(с) xkcd
Я буду исходить из предположения что читатель понимает что такое интеграл, комплексное число (а так же его модуль и аргумент), свертка функций, плюс хотя бы “на пальцах” представляет себе что такое дельта-функция Дирака. Не знаете — не беда, прочитайте вышеприведенные ссылки. Под “произведением функций” в данном тексте я везде буду понимать “поточечное умножение”
Начать надо, наверное, с того что обычное преобразование Фурье — это некая такая штука которая, как можно догадаться из названия, преобразует одни функции в другие, то есть ставит в соответствие каждой функции действительного переменного x(t) её спектр или фурье-образ y(w):
Если приводить аналогии, то примером аналогичного по смыслу преобразования может послужить например дифференцирование, превращающее функцию в её производную. То есть преобразование Фурье — такая же, по сути, операция как и взятие производной, и её часто обозначают схожим образом, рисуя треугольную “шапочку” над функцией. Только в отличие от дифференцирования которое можно определить и для действительных чисел, преобразование Фурье всегда “работает” с более общими комплексными числами. Из-за этого постоянно возникают проблемы с отображением результатов этого преобразования, поскольку комплексные числа определяются не одной, а двумя координатами на оперирующем действительными числами графике. Удобнее всего, как правило, оказывается представить комплексные числа в виде модуля и аргумента и нарисовать их по раздельности как два отдельных графика:
График аргумента комплексного значения часто называют в данном случае “фазовым спектром”, а график модуля — “амплитудным спектром”. Амплитудный спектр как правило представляет намного больший интерес, а потому “фазовую” часть спектра нередко пропускают. В этой статье мы тоже сосредоточимся на “амплитудных” вещах, но забывать про существование пропущенной фазовой части графика не следует. Кроме того, вместо обычного модуля комплексного значения часто рисуют его десятичный логарифм умноженный на 10. В результате получается логарифмический график, значения на котором отображаются в децибелах (дБ).
Обратите внимание что не очень сильно отрицательным числам логарифмического графика (-20 дБ и менее) при этом соответствуют практически нулевые числа на графике “обычном”. Поэтому длинные и широкие “хвосты” разнообразных спектров на таких графиках при отображении в “обычные” координаты как правило практически исчезают. Удобство подобного странного на первый взгляд представления возникает из того что фурье-образы различных функций часто необходимо перемножать между собой. При подобном поточечном умножении комплекснозначных фурье-образов их фазовые спектры складываются, а амплитудные — перемножаются. Первое выполняется легко, а второе — сравнительно сложно. Однако логарифмы амплитуды при перемножении амплитуд складываются, поэтому логарифмические графики амплитуды можно, как и графики фаз, просто поточечно складывать. Кроме того, в практических задачах часто удобнее оперировать не «амплитудой» сигнала, а его «мощностью» (квадратом амплитуды). На логарифмической шкале оба графика (и амплитуды и мощности) выглядят идентично и отличаются только коэффициентом — все значения на графике мощности ровно вдвое больше чем на шкале амплитуд. Соответственно для построения графика распределения мощности по частоте (в децибелах) можно не возводить ничего в квадрат, а посчитать десятичный логарифм и умножить его на 20.
Заскучали? Погодите, еще немного, с занудной частью статьи, объясняющей как интерпретировать графики, мы скоро покончим :). Но перед этим следует понять одну крайне важную вещь: хотя все вышеприведенные графики спектров были нарисованы для некоторых ограниченных диапазонов значений (в частности, положительных чисел), все эти графики на самом деле продолжаются в плюс и минус бесконечность. На графиках просто изображается некоторая “наиболее содержательная” часть графика, которая обычно зеркально отражается для отрицательных значений параметра и зачастую периодически повторяется с некоторым шагом, если рассматривать её в более крупном масштабе.
Определившись с тем, что же рисуется на графиках, давайте вернемся собственно к преобразованию Фурье и его свойствам. Существует несколько разных способов как определить это преобразование, отличающихся небольшими деталями (разными нормировками). Например в наших ВУЗах почему-то часто используют нормировку преобразования Фурье определяющую спектр в терминах угловой частоты (радианов в секунду). Я буду использовать более удобную западную формулировку, определяющую спектр в терминах обычной частоты (герцах). Прямое и обратное преобразование Фурье в этом случае определяются формулами слева, а некоторые свойства этого преобразования которые нам понадобятся — списком из семи пунктов справа:
Если взять функцию, состоящую из суммы множества синусоид с разными частотами, то согласно свойству линейности, фурье-образ этой функции будет состоять из соответствующего набора дельта-функций. Это позволяет дать наивную, но наглядную интерпретацию спектра по принципу “если в спектре функции частоте f соответствует амплитуда a, то исходную функцию можно представить как сумму синусоид, одной из которых будет синусоида с частотой f и амплитудой 2a”. Строго говоря, эта интерпретация неверна, поскольку дельта-функция и точка на графике — это совершенно разные вещи, но как мы увидим дальше, для дискретных преобразований Фурье она будет не так уж и далека от истины.
Второе свойство преобразования Фурье — это независимость амплитудного спектра от сдвига сигнала по времени. Если мы подвинем функцию влево или вправо по оси x, то поменяется лишь её фазовый спектр.
Третье свойство — растяжение (сжатие) исходной функции по оси времени (x) пропорционально сжимает (растягивает) её фурье-образ по шкале частот (w). В частности, спектр сигнала конечной длительности всегда бесконечно широк и наоборот, спектр конечной ширины всегда соответствует сигналу неограниченной длительности.
Четвертое и пятое свойства самые, пожалуй, полезные из всех. Они позволяют свести свертку функций к поточечному перемножению их фурье-образов и наоборот — поточечное перемножение функций к свертке их фурье-образов. Чуть дальше я покажу насколько это удобно.
Наконец последнее, седьмое свойство, говорит о том, что преобразование Фурье сохраняет “энергию” сигнала. Оно осмысленно только для сигналов конечной продолжительности, энергия которых конечна, и говорит о том, что спектр подобных сигналов на бесконечности быстро приближается к нулю. Именно в силу этого свойства на графиках спектров как правило изображают только “основную” часть сигнала, несущую в себе львиную долю энергии — остальная часть графика просто стремится к нулю (но, опять же, нулем не является).
Вооружившись этими 7 свойствами, давайте посмотрим на математику “оцифровки” сигнала, позволяющую перевести непрерывный сигнал в последовательность цифр. Для этого нам понадобится взять функцию, известную как “гребенка Дирака”:
Гребенка Дирака — это просто периодическая последовательность дельта-функций с единичным коэффициентом, начинающаяся в нуле и идущая с шагом T. Для оцифровки сигналов, T выбирают по возможности малым числом, T