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

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

Выполнил студент группы
МФИ – 301
Павлюшкевич Вероника

2. Введение

Быстрое преобразование Фурье (Fast
Fourier Transform, FFT) — это
эффективный алгоритм вычисления
дискретного преобразования Фурье
(ДПФ).

3. Идея быстрого преобразования Фурье

Алгоритм FFT был
популяризирован в 1965 году
Джеймсом Кули и Джоном
Тьюки (алгоритм Кули–Тьюки).
Основная идея: Разделить задачу
на подзадачи меньшего размера
(метод «разделяй и властвуй»).
• элементы с чётными индексами
Если N — степень двойки:
• элементы с нечётными индексами
N=2^m
то последовательность разбивается на:

4.

Xk​=Ek​+Wk⋅Ok​
Xk+N/2​=Ek​−Wk⋅Ok
где:
Ek — ДПФ от чётных элементов
Ok​ — ДПФ от нечётных элементов
Wk​=e^−2πik/N

5. Пример

Музыка — это звук, а звук — это волна, которая меняется со
временем.
Мы можем смотреть на звук двумя способами:
Во времени
– как громкость меняется по секундам
По частотам
– из каких “нот” (частот) состоит звук и насколько они сильные
Преобразование Фурье — это способ перейти
от “что происходит со временем”
к “какие частоты есть в сигнале”.

6. Пример из жизни

ты слышишь аккорд на пианино
На слух это один звук,
но на самом деле он состоит из: до,
ми, соль
Преобразование Фурье делает
примерно то же самое:
• берёт сложный сигнал
• раскладывает его на простые волны
(частоты)

7.

Преобразование Фурье широко
используется в обработке звука.
Файлы с музыкой хранятся не просто
как набор звуков, а как информация о
частотах. Это позволяет значительно
уменьшить размер файлов.
Например, формат MP3 удаляет те
частоты, которые человек почти не
слышит, тем самым снижая объём
данных без заметной потери качества.
Именно благодаря преобразованию
Фурье работают современные
музыкальные форматы.

8.

Музыка — не единственная
область применения. Графические
форматы JPG также используют
идеи преобразования Фурье. Они
сжимают изображения, удаляя
незначимые детали, которые
человеческий глаз почти не
замечает. Благодаря этому
изображения занимают меньше
места на диске.

9.

Также на основе преобразования
Фурье можно построить аналог
приложения Shazam, которое находит
музыку по короткому отрывку.
Анализируя частоты звука, программа
сравнивает их с базой данных и
определяет композицию.

10.

Где используется БПФ
• музыка
(эквалайзеры,
шумоподавление)
• изображения
(фильтры,
размытие, резкость)
• радиосвязь и Wi-Fi
• анализ данных и
сигналов
• машинное обучение
• быстрое умножение
больших чисел

11.

Дискретное преобразование Фурье
(ДПФ)
В компьютере всё хранится в виде
чисел.
Например, сигнал:
[1.2, 0.5, -0.7, -1.1, ...]
Дискретное преобразование Фурье
(ДПФ): берёт массив чисел, считает, какие
частоты в нём есть
Но проблема в том, что:
ДПФ работает очень медленно
если чисел много, компьютер долго
считает
Сложность: O(N²)

12.

Зачем нужно быстрое преобразование
Фурье (БПФ)
Быстрое преобразование Фурье (FFT /
БПФ) —
это умный и быстрый способ посчитать то
же самое, но:намного быстрее, вместо
O(N²) → O(N · log N)
Пример:
1 000 000 чисел
ДПФ — почти невозможно
БПФ — считается за доли секунды

13.

Главная идея БПФ (очень просто)
БПФ использует принцип: Разделяй и
властвуй
Что это значит:
1.Берём большой сигнал
2.Делим его на две части:
•чётные элементы
•нечётные элементы
3.Считаем преобразование для
маленьких частей
4.Аккуратно соединяем результат
Этот шаг повторяется много раз,
пока всё не станет очень маленьким и
простым.

14.

Почему БПФ такое быстрое
1. не считает одно и то же много
раз
2. использует симметрии и
повторения
3. работает “по слоям”
Поэтому почти все программы:
обработки звука, изображений,
видео - используют БПФ, а не
обычное преобразование Фурье.

15.

Очень простой пример на Java

16. Вывод

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

17.

Спасибо за внимание!!!

18. Приложение 1

class SimpleFFTExample {
public static void main(String[] args) {
// Пример сигнала
double[] signal = {1, 0, -1, 0};
System.out.println("Исходный сигнал:");
for (double v : signal) {
System.out.print(v + " ");
}
// В реальности здесь вызывается
System.out.println("\n\nПосле FFT мы получаем частоты (условно):");
System.out.println("Частота 0: сильная");
System.out.println("Частота 1: слабая");
System.out.println("Частота 2: сильная");
}
}

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

Выполнил студент группы
МФИ – 301
Павлюшкевич Вероника