====== Лекция 3. Дискретное преобразование Фурье (ДПФ) ====== Подробный конспект третьей лекции: как компьютер считает спектр, что означает каждое число на выходе и какие свойства ДПФ превращаются в инструменты. Материал рассчитан и на подготовку преподавателя, и на самостоятельное чтение. ---- ===== О чём этот текст и как им пользоваться ===== * Это **подробный конспект** лекции 3 — от идеи спектра к конкретному алгоритму. * Лекция отвечает на вопросы: * зачем переходить от интеграла к сумме; * как записать ДПФ (прямое, обратное, матричное); * как связаны частоты, разрешение и длительность; * какие у ДПФ свойства и как ими пользоваться. * Формат — списки: удобно готовиться и объяснять. * Числовые примеры согласованы с ноутбуком ''lecture03.ipynb''. ---- ===== Цели лекции (что должен уметь студент) ===== - Понять, зачем нужно **ДПФ**: * интеграл заменяется суммой; * из ''N'' чисел получаем ''N'' чисел спектра. - Записать **прямое и обратное** ДПФ. - Записать ДПФ в **матричной форме** (''X = W·x''). - Связать ДПФ с **непрерывным спектром** и разрешением: * ''f_k = k·f_д/N''; * ''Δf = 1/T''. - Освоить **свойства** ДПФ (линейность, симметрия, сдвиг, свёртка, Парсеваль). - Понять **бины**, **утечку** и **круговую свёртку**. - Понять ограничение ''O(N²)'' и мотив к **БПФ**. **Зачем каждый пункт на практике:** * ДПФ — базовый «рабочий» спектр. * Матричная форма — язык линейной алгебры и понимания свойств. * Разрешение — что реально можно различить. * Свойства — инструменты (сдвиг, фильтрация). * Круговая свёртка — почему нельзя просто перемножить спектры. * ''O(N²)'' — зачем нужно БПФ. ---- ===== 1. Зачем нужно ДПФ ===== ==== 1.1 Проблема непрерывного спектра ==== * Непрерывный спектр — это **интеграл**. * Компьютер не берёт бесконечный интеграл. * На практике есть только ''N'' отсчётов: ''x[0], …, x[N−1]''. ==== 1.2 Идея ДПФ ==== * **ДПФ** — линейное преобразование: из ''N'' чисел делает ''N'' чисел. * Интеграл заменяется **суммой** по отсчётам. * Всё дальнейшее (БПФ, окна, спектрограммы) — надстройки над ДПФ. * ДПФ — «точный спектр» для данной конечной записи. ==== 1.3 Что ДПФ даёт ==== * Амплитуды и фазы на **сетке частот**. * Числа, пригодные для обработки и решений. * Основа для признаков: пики, отношения, энергия по полосам. ---- ===== 2. Математическое представление ===== ==== 2.1 Обозначения ==== * Индексы ''n = 0…N−1'' (время), ''k = 0…N−1'' (частота). * ''W_N = e^(−j·2π/N)'' — поворотный множитель. * ''j = √(−1)'' — инженерное обозначение (буква ''i'' занята током). ==== 2.2 Прямое ДПФ ==== * ''X[k] = Σ_n x[n]·W_N^(k·n) = Σ_n x[n]·e^(−j·2π·k·n/N)''. * Смысл: корреляция сигнала с синусоидой частоты ''k''. * Совпало — большое число; не совпало — почти ноль. ==== 2.3 Обратное ДПФ ==== * ''x[n] = (1/N)·Σ_k X[k]·e^(+j·2π·k·n/N)''. * Знак экспоненты другой и есть множитель ''1/N''. * Обратное восстанавливает сигнал из спектра без потерь (в рамках модели). ==== 2.4 Матричная форма ==== * ''X = W·x'', где ''W_(k,n) = W_N^(k·n)'' — матрица Вандермонда. * Обратное: ''x = (1/N)·W^H·X'' (''W^H'' — сопряжённое транспонирование). * Матрица симметричная; строки — разные частоты. * Удобно для анализа свойств (ортогональность, обратимость). ---- ===== 3. Геометрия: что такое ''e^(−jθ)'' ===== * Формула Эйлера: ''e^(jθ) = cosθ + j·sinθ''. * Это точка на **единичной окружности** под углом ''θ''. * Умножение на ''e^(−jθ)'' — поворот по часовой стрелке. * ''W_N^k'' — ''N'' равномерно расставленных «стрелок» на окружности. * ''X[k]'' — проекция сигнала на такую «стрелку» (корреляция). * Проекция = совпадение: совпало — пик, не совпало — ноль. ---- ===== 4. Связь с непрерывным спектром ===== ==== 4.1 Сетка частот ==== * ДПФ даёт **отсчёты** непрерывного спектра на частотах ''f_k = k·f_д/N''. * Разрешение: ''Δf = f_д/N = 1/T''. * Длительность записи: ''T = N/f_д''. * Число уникальных бинов: ''N'' (комплексный сигнал), ''N/2 + 1'' (вещественный). ==== 4.2 Двойственность время–частота ==== * Дискретность во времени → **периодичность** спектра (период ''f_д''). * Конечная длина записи → **дискретность** по частоте (шаг ''Δf''). * Периодичность во времени → дискретность по частоте. * Это «зеркало», которое помогает запомнить связи. ==== 4.3 Нормировка амплитуд ==== * Связь амплитуд: ''X[k] ≈ X_непр(f_k)·f_д''. * На практике: ''|X|/N'' или ''2|X|/N'' (для одностороннего спектра). ---- ===== 5. Комплексное представление синуса ===== * По Эйлеру: ''cosθ = (e^(jθ) + e^(−jθ))/2''. * Реальный синус ''A·cos(2πf₀t+φ)'' → **две** сопряжённые линии ''±f₀'' (амплитуды ''A/2'', фазы ''±φ''). * Комплексный (аналитический) сигнал → **одна** линия ''+f₀''. * Восстановление: ''A = 2·|X[k]|/N'', ''φ = arg X[k]''. * Для вещественного сигнала достаточно половины спектра (''rfft''). ---- ===== 6. Бины и примеры ===== ==== 6.1 Бины ==== * ДПФ «знает» сигнал только на частотах ''f_k = k·f_д/N''. * Шаг сетки — **разрешение** ''Δf''. * Между бинами спектр не определён «напрямую». ==== 6.2 On-bin и off-bin ==== * Частота совпала с бином → две чёткие линии. * Частота между бинами → энергия растекается (**утечка**). * Пример: ''f_д = 8000'', ''N = 8'', ''Δf = 1000''; 1.00 кГц против 1.25 кГц. ==== 6.3 Меандр и треугольник ==== * Оба содержат только **нечётные** гармоники. * Меандр: амплитуды ''≈ 1/k''. * Треугольник: ''≈ 1/k²'' (спектр «мягче»). * Мостик к ряду Фурье и явлению Гиббса (лекция 2). ==== 6.4 ДПФ реального сигнала ==== * Вибрация: база 50 Гц, дефект 120 Гц, шум. * Считаем ДПФ, переводим бины в герцы. * Дефект — отчётливая линия в спектре. * Спектр превращает «непонятную кривую» в числа. ---- ===== 7. Свойства ДПФ ===== ==== 7.1 Линейность ==== * ''ДПФ(a·x + b·y) = a·ДПФ(x) + b·ДПФ(y)''. * Основа для разложения задачи на части. ==== 7.2 Симметрия вещественного сигнала ==== * ''X[N−k] = conj(X[k])''. * Достаточно половины спектра. ==== 7.3 Сдвиг во времени ↔ фаза ==== * ''x[n−n₀] → X[k]·e^(−j2πkn₀/N)''. * Модуль не меняется, фаза линейна. ==== 7.4 Круговая свёртка ==== * ''ДПФ(x * y) = ДПФ(x)·ДПФ(y)''. * Основа быстрой фильтрации. ==== 7.5 Парсеваль ==== * ''Σ|x[n]|² = (1/N)·Σ|X[k]|²''. * Энергия сохраняется. ==== 7.6 Сводная таблица ==== ^ Свойство ^ Формула ^ Применение ^ | Линейность | ''a·x + b·y'' | суперпозиция | | Симметрия | ''X[N−k]=conj X[k]'' | половина спектра | | Сдвиг | ''X[k]·e^(−j2πkn₀/N)'' | задержки | | Свёртка | ''X·Y'' | фильтрация | | Парсеваль | `Σ | x | ²=(1/N)Σ | X | ²` | проверка | ---- ===== 8. Круговая свёртка и «заворачивание» ===== * ДПФ превращает свёртку в **умножение** — основа быстрой фильтрации. * Но свёртка получается **круговой**: индексы берутся по модулю ''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''. * Иначе линии спектра «накладываются» — типичная ошибка. ---- ===== 9. Ось частот и нормировка ===== * ''np.fft.fft'' — полный двусторонний спектр (''N'' точек). * ''np.fft.rfft'' — половина для вещественного сигнала. * Ось: ''fftfreq'' (двусторонняя) и ''rfftfreq'' (односторонняя). * Центрирование: ''fftshift''. * Амплитуда: ''|X|/N'' или ''2|X|/N''. * Типичная ошибка: забыть нормировку/центрирование — пик «уезжает». ---- ===== 10. Мотив к БПФ ===== * Прямое ДПФ: ''N²'' операций. * Для ''N = 10⁶'' это ''10¹²'' — неприемлемо. * Время растёт как квадрат длины записи. * Нужен быстрый алгоритм — **БПФ** (лекция 4). * БПФ даёт тот же результат за ''N·log₂N''. ---- ===== 11. Приложение: вывод формулы Эйлера ===== * Раскладываем ''e^(jθ)'' в ряд Тейлора. * Степени ''j'' идут циклом ''1, j, −1, −j''. * Члены делятся на две группы: ряд косинуса и ряд синуса. * Отсюда ''e^(jθ) = cosθ + j·sinθ'' — следствие рядов, а не постулат. * Это объясняет, почему комплексная экспонента «крутит» фазу. ---- ===== 12. Практические рецепты ===== * Для вещественного сигнала брать ''rfft'' и ''rfftfreq''. * Для «центрированного» спектра — ''fftshift''. * Не забывать нормировку амплитуд. * Для фильтрации через ДПФ — дополнять нулями до линейной свёртки. * Проверять себя через Парсеваль (энергия). ---- ===== 13. Шпаргалка (словарь) ===== ^ Термин ^ Что означает ^ | ДПФ | ''N'' чисел → ''N'' чисел спектра | | Обратное ДПФ | восстановление сигнала из спектра | | ''W_N'' | поворотный множитель ''e^(−j2π/N)'' | | Матрица Вандермонда | матрица ''W'' в ''X = W·x'' | | Бин | узел частотной сетки | | ''Δf'' | разрешение, ''1/T'' | | Симметрия | ''X[N−k]=conj X[k]'' | | Круговая свёртка | свёртка по модулю ''N'' | | Заворачивание | наложение хвоста свёртки | | Парсеваль | равенство энергий | | ''rfft'' | половина спектра вещественного сигнала | ---- ===== 14. Частые ошибки и заблуждения ===== * «ДПФ — приближение». * Для данной записи это точный спектр. * «Можно взять любой ''N'' без последствий». * Сетка частот зависит от ''N'' и ''f_д''. * «Перемножу спектры — получу свёртку». * Только **круговую**; для линейной нужно дополнение нулями. * «Забуду про ''1/N'' в обратном ДПФ». * Сигнал восстановится с неверным масштабом. * «Отрицательные частоты — ошибка». * Следствие вещественности; они сопряжены положительным. * «Утечка — дефект алгоритма». * Следствие конечной записи. ---- ===== 15. Вопросы и развёрнутые ответы ===== - **Зачем нужен переход от интеграла к сумме?** Компьютер работает с конечным набором отсчётов; сумма — вычислимая форма спектра. - **Запишите прямое и обратное ДПФ.** ''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''. ---- ===== 16. План рассказа на 2 академических часа ===== - **10 мин.** Зачем ДПФ; от интеграла к сумме. - **20 мин.** Прямое/обратное ДПФ; матрица Вандермонда. - **15 мин.** Геометрия ''e^(−jθ)'', ''W_N^k''; корреляция. - **15 мин.** Связь с непрерывным спектром; ''Δf=1/T''; двойственность. - **15 мин.** Бины, on/off-bin, меандр/треугольник, вибрация. - **15 мин.** Свойства; круговая свёртка и заворачивание. - **10 мин.** Ось частот, нормировка, мотив к БПФ, задание №3. * **Приём:** каждую формулу сопровождать картинкой и числом. * Давать «руками»: посчитать ДПФ маленького массива и сверить с ''numpy''. ---- ===== 17. Итог ===== * ДПФ — точный спектр из ''N'' отсчётов (сумма вместо интеграла). * Частоты дискретны; разрешение ''Δf = 1/T''. * Работают свойства: линейность, симметрия, сдвиг, свёртка, Парсеваль. * Матричная форма ''X = W·x''; обратное — через ''W^H''. * Круговая свёртка требует дополнения нулями. * ''O(N²)'' — мотив к БПФ. ---- ===== 18. Что дальше ===== * **Лекция 4**: БПФ, окна, разрешение, усреднение — практический спектральный анализ. * **Лекция 5**: модуляция и I/Q. * **Лекция 6**: свёртка, корреляция, согласованная фильтрация. ===== Материалы ===== * {{sp:lecture03.pdf|Слайды лекции 3 (PDF)}} * {{sp:lecture03_notebook.pdf|Ноутбук лекции 3 (PDF)}} * {{sp:lecture03_lecture.pdf|Текст лекции 3 (PDF)}} * {{sp:lecture03_essence.pdf|Конспект «Суть лекции 3» (PDF)}} * {{sp:sig-prog-lecture03-2026-10-01.zip|Раздаточный архив (ZIP, все исходники)}}