Основные алгоритмы компьютерной графики   БПФ   КГ   ДМ   ТПОИ   Теория сигналов  

Быстрое преобразование Фурье

Что такое эффект размазывания

В предыдущей главе мы рассматривали ситуацию, когда частота колебания равнялась m/T, где m - целое. Теперь рассмотрим ситуацию, когда это не так. Положим, что m = n + q, где n - целое и 0 < q < 1. Воспользуемся формулой (35). Поскольку первые несколько условий для нецелого m не выполняются, то остается последняя, самая сложная формула, помеченная словами "Для остальных k":

Подставим в эту формулу n + q вместо m и выполним упрощения, воспользовавшись формулой (34) и введя обозначение ρ = 2πj.

Итого:

  ,  ρ = 2πj    (37)

Теперь построим график функции, чтобы понять, как она себя ведет. Ниже показана трехмерная поверхность. По горизонтальной оси отложено k, по вертикальной |Xk| и по оси, уходящей вглубь плоскости, отложено q от 0.01 до 0.99.


Рис. 1.

На рисунке видно два ярко выраженных ребра. Первое из них всегда приходится на k = n и k = n + 1. Второе ребро получается в результате зеркального эффекта. Высота пика наименьшая в окрестности q = 0.5. А наибольшая в окрестности q = 1 и q = 0 - то есть при целочисленном m.

К сожалению, пик не является единственным ненулевым коэффициентом Фурье. Рядом с ним есть множество меньших, но не нулевых величин. Если при целочисленном m можно наблюдать единственную полоску, то при нецелом m = n + q эта полоска размазывается:


Рис. 2.

На рисунке приведена практическая ситуация. Это - ДПФ для звука, содержащегося в обычном WAV-файле. Высота синего штриха цвет соответствует |Xk|. Исходный сигнал содержал ноту "ля" второй октавы с частотой 440 гц и фазой в 90 градусов. ДПФ было выполнено для N = 1000. Однако частота дискретизации звука в WAV-файле составляла 44100 Гц, так что период дискретизации был равен T = 1000/44100 секунд и из формулы m/T = 440 получим m = 440*(1000/44100) = 9.97, то есть, не целое. В результате ярко выраженный пик окружают дополнительные ненулевые значения.

На следующем рисунке:


Рис. 3.

показана "хорошая" ситуация, когда частота исходного звука составляла 441 Гц, и m = 441*1000/44100 = 10, то есть целое. Вы видите только один ненулевой отсчет.

Этот эффект будем называть эффектом размазывания. Вы видите, что он определяет погрешность, с которой можно найти частоту исходного колебания. Погрешность равна 1/T. При достаточно большом отклонении m от целого эффект может быть очень заметен. Например ниже вы видите ДПФ для сигнала, соответствующего ноте "ля-бемоль":


Рис. 4.

Точнее можно попытаться определить параметры m, A и φ численными методами.

Для поиска φ следует учесть, что изменение A не повлияет на комплексную фазу (аргумент) коэффициентов Xk. В самом деле, мы можем представить коэффициенты в виде:

Xk = (A/2)Z(m,&phi)k,

где Z(m,&phi)k - комплексное число, не зависящее от действительного числа A, но зависящее от m и φ:

Z(m,&phi)k =

Также не зависит от A отношение коэффициентов Xk/Xl = Z(m,&phi)k/Z(m,&phi)l.

Это значит, что у нас есть две целевые функции, с помощью которых мы можем найти частоту m/T и фазу φ. Возьмем Xk, максимальное по модулю. Если соседние отсчеты Xk-1 и Xk+1 равны нулю, то у нас нет эффекта размазывания и параметры восстанавливаются так, как описано в предыдущей главе. На самом деле нам придется сравнивать не с нулем, а с некоторым малым числом, поскольку некоторая погрешность при вычислении ДПФ неизбежна.

Теперь, когда мы убедились в наличии эффекта размазывания, попробуем найти m и φ после чего восстановим A по формуле: A = |2Xk / Z(m,&phi)k|.

Сначала найдем два максимальных отсчета Xk и Xk+1. Теперь мы знаем, что искомое m лежит на интервале (k, k+1).

Для нахождения m и φ нужно численно решить систему уравнений:

|Z(m,&phi)k/Z(m,&phi)k+1| = |Xk/Xk+1|

Arg(Z(m,&phi)k) = Arg(Xk)

Здесь только две неизвестных - m и φ, неизвестная A исключена. Систему можно решить итерационно. Для этого сначала фиксируем φ и подбираем m, которое удовлетворяет первому уравнению системы. Потом - наоборот фиксируем найденное m и подбираем φ, которое удовлетворяет второму уравнению системы. Потом снова возавращаемся к первому уравнения - до тех пор, пока оба уравнения не окажутся сбалансированы с достаточной точностью.

Также существует метод вычисления частоты m, основанный на сопоставлении фаз. Стефан Бернси использует его в своем алгоритме транспонирования. Данный метод быстрее (не требует нескольких итераций для решения системы уравнений), однако требует двух преобразований Фурье для одного фрагмента с небольшим сдвигом на время ΔT. Этот алгоритм предполагает, что спектр не меняется за это короткое время - хотя бы в отношении частот.

Допустим, у нас есть фрагмент длиной T. Мы делаем преобразование Фурье не для всего этого фрагмента, а для двух перекрывающихся фрагментов [0, T - ΔT] и [ΔT, T]. Затем рассматриваем каждую получившуюся гармонику и ее фазу в первом и втором преобразовании. По величине сдвига фазы вносится поправка q и вычисляется точная частота (n + q)/T.

Наконец, эффект размазывания можно уменьшить, если применять оконные функции. Хотя в результате применения оконной функции, спектр может сильно исказиться, но все-таки форма пиков изменяется, сужается их "подошва". Вот пример для T = 1 сек, N = 44100, m/T = 440.2 Гц, φ = 0. Слева - спектр с "размазыванием", полученный обычным ДПФ. Справа - с применением оконной функции Хамминга.

Основные алгоритмы компьютерной графики   БПФ   КГ   ДМ   ТПОИ   Теория сигналов  

Болдырев, Бабурин, Филин, Новиков, Квачкова, Ивашов: Сила в единстве! ( МЭФ 2017)

ВСЕ ВИДЕО
Знаете ли Вы, что Программный сниппет (англ. snippet — фрагмент, отрывок) в практике программирования — небольшой фрагмент исходного кода или текста, пригодный для повторного использования. Сниппеты не являются заменой процедур, функций или других подобных понятий структурного программирования. Они обычно используются для более лёгкой читаемости кода функций, которые без их использования выглядят слишком перегруженными деталями, или для устранения повторения одного и того же общего участка кода. Интегрированные среды разработки (IDE) содержат встроенные средства для ввода конструкций языка. Например, в Microsoft Visual Studio, Borland Developer Studio, для этого необходимо ввести ключевое слово и нажать определённую клавишную комбинацию. В IDE Geany существует специальный файл snippets.conf (путь к файлу: /home/user/.config/geany) позволяющий создавать свои сниппеты. Другие программы, такие как Macromedia Dreamweaver и Zend Studio, позволяют использовать сниппеты в Веб-программировании.
НОВОСТИ ФОРУМАФорум Рыцари теории эфира
Рыцари теории эфира
 20.04.2018 - 20:37: СОВЕСТЬ - Conscience -> РУССКИЙ МИР - Карим_Хайдаров.
28.03.2018 - 18:15: СОВЕСТЬ - Conscience -> Проблема государственного терроризма - Карим_Хайдаров.
22.03.2018 - 09:33: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Ю.Ю. Болдырева - Карим_Хайдаров.
04.10.2017 - 15:26: ЭКОНОМИКА И ФИНАНСЫ - Economy and Finances -> ПРОБЛЕМА КРИМИНАЛИЗАЦИИ ЭКОНОМИКИ - Карим_Хайдаров.
04.10.2017 - 05:02: Беседка - Chatter -> "Зенит"ы с "Протон"ами будут падать - Карим_Хайдаров.
03.10.2017 - 18:16: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от О.Н. Четвериковой - Карим_Хайдаров.
03.10.2017 - 07:24: ЦИТАТЫ ЧУЖИХ ФОРУМОВ - Outside Quotings -> ЗА НАМИ БЛЮДЯТ - Карим_Хайдаров.
03.10.2017 - 05:48: Беседка - Chatter -> WHO IS WHO - КТО ЕСТЬ КТО - Карим_Хайдаров.
02.10.2017 - 19:04: АСТРОФИЗИКА - Astrophysics -> Апериодическая комета C/2014 Q2 Lovejoy - Карим_Хайдаров.
02.10.2017 - 14:57: СОВЕСТЬ - Conscience -> РАСЧЕЛОВЕЧИВАНИЕ ЧЕЛОВЕКА. КОМУ ЭТО НАДО? - Карим_Хайдаров.
01.10.2017 - 13:58: Беседка - Chatter -> ЭПИСТОЛЯРНАЯ ФИЗИКА - Карим_Хайдаров.
01.10.2017 - 07:23: СОВЕСТЬ - Conscience -> НАСАтые астропиндосы - Карим_Хайдаров.
Bourabai Research Institution home page

Боровское исследовательское учреждение - Bourabai Research Bourabai Research Institution