Лекция 3. Дискретное преобразование Фурье (ДПФ)

Подробный конспект третьей лекции: как компьютер считает спектр, что означает каждое число на выходе и какие свойства ДПФ превращаются в инструменты. Материал рассчитан и на подготовку преподавателя, и на самостоятельное чтение.

• Это подробный конспект лекции 3 — от идеи спектра к конкретному алгоритму.
• Лекция отвечает на вопросы:
  • зачем переходить от интеграла к сумме;
  • как записать ДПФ (прямое, обратное, матричное);
  • как связаны частоты, разрешение и длительность;
  • какие у ДПФ свойства и как ими пользоваться.
• Формат — списки: удобно готовиться и объяснять.
• Числовые примеры согласованы с ноутбуком lecture03.ipynb.

1. Понять, зачем нужно ДПФ:
   • интеграл заменяется суммой;
   • из N чисел получаем N чисел спектра.
2. Записать прямое и обратное ДПФ.
3. Записать ДПФ в матричной форме (X = W·x).
4. Связать ДПФ с непрерывным спектром и разрешением:
   • f_k = k·f_д/N;
   • Δf = 1/T.
5. Освоить свойства ДПФ (линейность, симметрия, сдвиг, свёртка, Парсеваль).
6. Понять бины, утечку и круговую свёртку.
7. Понять ограничение O(N²) и мотив к БПФ.

Зачем каждый пункт на практике:

• ДПФ — базовый «рабочий» спектр.
• Матричная форма — язык линейной алгебры и понимания свойств.
• Разрешение — что реально можно различить.
• Свойства — инструменты (сдвиг, фильтрация).
• Круговая свёртка — почему нельзя просто перемножить спектры.
• O(N²) — зачем нужно БПФ.

• Непрерывный спектр — это интеграл.
• Компьютер не берёт бесконечный интеграл.
• На практике есть только N отсчётов: x[0], …, x[N−1].

• ДПФ — линейное преобразование: из N чисел делает N чисел.
• Интеграл заменяется суммой по отсчётам.
• Всё дальнейшее (БПФ, окна, спектрограммы) — надстройки над ДПФ.
• ДПФ — «точный спектр» для данной конечной записи.

• Амплитуды и фазы на сетке частот.
• Числа, пригодные для обработки и решений.
• Основа для признаков: пики, отношения, энергия по полосам.

• Индексы n = 0…N−1 (время), k = 0…N−1 (частота).
• W_N = e^(−j·2π/N) — поворотный множитель.
• j = √(−1) — инженерное обозначение (буква i занята током).

• X[k] = Σ_n x[n]·W_N^(k·n) = Σ_n x[n]·e^(−j·2π·k·n/N).
• Смысл: корреляция сигнала с синусоидой частоты k.
• Совпало — большое число; не совпало — почти ноль.

• x[n] = (1/N)·Σ_k X[k]·e^(+j·2π·k·n/N).
• Знак экспоненты другой и есть множитель 1/N.
• Обратное восстанавливает сигнал из спектра без потерь (в рамках модели).

• X = W·x, где W_(k,n) = W_N^(k·n) — матрица Вандермонда.
• Обратное: x = (1/N)·W^H·X (W^H — сопряжённое транспонирование).
• Матрица симметричная; строки — разные частоты.
• Удобно для анализа свойств (ортогональность, обратимость).

• Формула Эйлера: e^(jθ) = cosθ + j·sinθ.
• Это точка на единичной окружности под углом θ.
• Умножение на e^(−jθ) — поворот по часовой стрелке.
• W_N^k — N равномерно расставленных «стрелок» на окружности.
• X[k] — проекция сигнала на такую «стрелку» (корреляция).
• Проекция = совпадение: совпало — пик, не совпало — ноль.

• ДПФ даёт отсчёты непрерывного спектра на частотах f_k = k·f_д/N.
• Разрешение: Δf = f_д/N = 1/T.
• Длительность записи: T = N/f_д.
• Число уникальных бинов: N (комплексный сигнал), N/2 + 1 (вещественный).

• Дискретность во времени → периодичность спектра (период f_д).
• Конечная длина записи → дискретность по частоте (шаг Δf).
• Периодичность во времени → дискретность по частоте.
• Это «зеркало», которое помогает запомнить связи.

• Связь амплитуд: X[k] ≈ X_непр(f_k)·f_д.
• На практике: |X|/N или 2|X|/N (для одностороннего спектра).

• По Эйлеру: cosθ = (e^(jθ) + e^(−jθ))/2.
• Реальный синус A·cos(2πf₀t+φ) → две сопряжённые линии ±f₀

(амплитуды A/2, фазы ±φ).

• Комплексный (аналитический) сигнал → одна линия +f₀.
• Восстановление: A = 2·|X[k]|/N, φ = arg X[k].
• Для вещественного сигнала достаточно половины спектра (rfft).

• ДПФ «знает» сигнал только на частотах f_k = k·f_д/N.
• Шаг сетки — разрешение Δf.
• Между бинами спектр не определён «напрямую».

• Частота совпала с бином → две чёткие линии.
• Частота между бинами → энергия растекается (утечка).
• Пример: f_д = 8000, N = 8, Δf = 1000; 1.00 кГц против 1.25 кГц.

• Оба содержат только нечётные гармоники.
• Меандр: амплитуды ≈ 1/k.
• Треугольник: ≈ 1/k² (спектр «мягче»).
• Мостик к ряду Фурье и явлению Гиббса (лекция 2).

• Вибрация: база 50 Гц, дефект 120 Гц, шум.
• Считаем ДПФ, переводим бины в герцы.
• Дефект — отчётливая линия в спектре.
• Спектр превращает «непонятную кривую» в числа.

• ДПФ(a·x + b·y) = a·ДПФ(x) + b·ДПФ(y).
• Основа для разложения задачи на части.

• X[N−k] = conj(X[k]).
• Достаточно половины спектра.

• x[n−n₀] → X[k]·e^(−j2πkn₀/N).
• Модуль не меняется, фаза линейна.

• ДПФ(x * y) = ДПФ(x)·ДПФ(y).
• Основа быстрой фильтрации.

• Σ|x[n]|² = (1/N)·Σ|X[k]|².
• Энергия сохраняется.

• ДПФ превращает свёртку в умножение — основа быстрой фильтрации.
• Но свёртка получается круговой: индексы берутся по модулю N.
• Хвост линейной свёртки (индексы ≥ N) складывается с началом:
  • y_circ[n] = y_lin[n] + y_lin[n+N] + ….
• Пример [1,2,3,4] * [1,1,1] при N = 4:
  • y_lin = [1,3,6,9,7,4];
  • хвост [7,4] заворачивается → [8,7,6,9].
• Чтобы получить линейную свёртку, дополняем нулями до N ≥ N_a + N_b − 1.
• Иначе линии спектра «накладываются» — типичная ошибка.

• np.fft.fft — полный двусторонний спектр (N точек).
• np.fft.rfft — половина для вещественного сигнала.
• Ось: fftfreq (двусторонняя) и rfftfreq (односторонняя).
• Центрирование: fftshift.
• Амплитуда: |X|/N или 2|X|/N.
• Типичная ошибка: забыть нормировку/центрирование — пик «уезжает».

• Прямое ДПФ: N² операций.
• Для N = 10⁶ это 10¹² — неприемлемо.
• Время растёт как квадрат длины записи.
• Нужен быстрый алгоритм — БПФ (лекция 4).
• БПФ даёт тот же результат за N·log₂N.

• Раскладываем e^(jθ) в ряд Тейлора.
• Степени j идут циклом 1, j, −1, −j.
• Члены делятся на две группы: ряд косинуса и ряд синуса.
• Отсюда e^(jθ) = cosθ + j·sinθ — следствие рядов, а не постулат.
• Это объясняет, почему комплексная экспонента «крутит» фазу.

• Для вещественного сигнала брать rfft и rfftfreq.
• Для «центрированного» спектра — fftshift.
• Не забывать нормировку амплитуд.
• Для фильтрации через ДПФ — дополнять нулями до линейной свёртки.
• Проверять себя через Парсеваль (энергия).

• «ДПФ — приближение».
  • Для данной записи это точный спектр.
• «Можно взять любой N без последствий».
  • Сетка частот зависит от N и f_д.
• «Перемножу спектры — получу свёртку».
  • Только круговую; для линейной нужно дополнение нулями.
• «Забуду про 1/N в обратном ДПФ».
  • Сигнал восстановится с неверным масштабом.
• «Отрицательные частоты — ошибка».
  • Следствие вещественности; они сопряжены положительным.
• «Утечка — дефект алгоритма».
  • Следствие конечной записи.

1. Зачем нужен переход от интеграла к сумме?

Компьютер работает с конечным набором отсчётов; сумма — вычислимая форма

 спектра.
- **Запишите прямое и обратное ДПФ.**
 ''X[k]=Σx[n]W_N^(kn)''; ''x[n]=(1/N)ΣX[k]W_N^(−kn)''.
- **Что такое матрица Вандермонда?**
 Матрица ''W'' с элементами ''W_N^(kn)'', задающая ДПФ как ''X=W·x''.
- **Как связаны ''f_k'', ''Δf'', ''T''?**
 ''f_k=k·f_д/N'', ''Δf=f_д/N=1/T''.
- **В чём симметрия вещественного спектра?**
 ''X[N−k]=conj X[k]''; хватает половины.
- **Что такое круговая свёртка и заворачивание?**
 Свёртка по модулю ''N''; хвост линейной свёртки складывается с началом.
- **Почему нужна нормировка?**
 Чтобы амплитуды и энергии соответствовали физическим величинам.
- **Как получить линейную свёртку через ДПФ?**
 Дополнить нулями до ''N ≥ N_a + N_b − 1''.
- **Откуда берётся формула Эйлера?**
 Из рядов Тейлора для ''e^(jθ)'', ''cosθ'', ''sinθ''.
- **Почему ''O(N²)'' ведёт к БПФ?**
  Квадратичное время неприемлемо для больших ''N''; БПФ ускоряет до ''N·log₂N''.

1. 10 мин. Зачем ДПФ; от интеграла к сумме.
2. 20 мин. Прямое/обратное ДПФ; матрица Вандермонда.
3. 15 мин. Геометрия e^(−jθ), W_N^k; корреляция.
4. 15 мин. Связь с непрерывным спектром; Δf=1/T; двойственность.
5. 15 мин. Бины, on/off-bin, меандр/треугольник, вибрация.
6. 15 мин. Свойства; круговая свёртка и заворачивание.
7. 10 мин. Ось частот, нормировка, мотив к БПФ, задание №3.

• Приём: каждую формулу сопровождать картинкой и числом.
• Давать «руками»: посчитать ДПФ маленького массива и сверить с numpy.

• ДПФ — точный спектр из N отсчётов (сумма вместо интеграла).
• Частоты дискретны; разрешение Δf = 1/T.
• Работают свойства: линейность, симметрия, сдвиг, свёртка, Парсеваль.
• Матричная форма X = W·x; обратное — через W^H.
• Круговая свёртка требует дополнения нулями.
• O(N²) — мотив к БПФ.

• Лекция 4: БПФ, окна, разрешение, усреднение — практический спектральный

анализ.

• Лекция 5: модуляция и I/Q.
• Лекция 6: свёртка, корреляция, согласованная фильтрация.

• Слайды лекции 3 (PDF)
• Ноутбук лекции 3 (PDF)
• Текст лекции 3 (PDF)
• Конспект «Суть лекции 3» (PDF)
• Раздаточный архив (ZIP, все исходники)