Differences

This shows you the differences between two versions of the page.

--- sp:lec3 [2026/10/08 17:13] – created - external edit 127.0.0.1
+++ sp:lec3 [2026/10/09 12:22] (current) – external edit 127.0.0.1
@@ Line 1: / Line 1: @@
 ====== Лекция 3. Дискретное преобразование Фурье (ДПФ) ======
-**Курс:** Обработка сигналов · 4 курс · 01.03.02 «Прикладная математика и информатика» · ИИ и системная аналитика
+Подробный конспект третьей лекции: как компьютер считает спектр, что означает
+каждое число на выходе и какие свойства ДПФ превращаются в инструменты.
+Материал рассчитан и на подготовку преподавателя, и на самостоятельное чтение.
 ----
-===== О чём лекция =====
+===== О чём этот текст и как им пользоваться =====
-  * **зачем нужно ДПФ**: непрерывный спектр — интеграл, а у компьютера только N отсчётов; интеграл → сумма;
+  * Это **подробный конспект** лекции 3 — от идеи спектра к конкретному алгоритму.
-  * **прямое и обратное ДПФ**, обозначение W<sub>N</sub> = e<sup>−j2π/N</sup>; j = √(−1) — инженерное обозначение;
+  * Лекция отвечает на вопросы:
-  * **матричная форма** X = W·x (матрица Вандермонда); обратное — через W<sup>H</sup>/N;
+    * зачем переходить от интеграла к сумме;
-  * связь с непрерывным спектром: f<sub>k</sub> = k·f<sub>д</sub>/N, разрешение Δf = 1/T;
+    * как записать ДПФ (прямое, обратное, матричное);
-  * **свойства ДПФ**: линейность, симметрия вещественного сигнала, сдвиг ↔ фаза, круговая свёртка (и «заворачивание» конца), Парсеваль;
+    * как связаны частоты, разрешение и длительность;
-  * комплексное представление синуса: две сопряжённые линии ±f₀ против одной у аналитического сигнала; on-bin и off-bin;
+    * какие у ДПФ свойства и как ими пользоваться.
-  * примеры: меандр и треугольник (нечётные гармоники, 1/k и 1/k²);
+  * Формат — списки: удобно готовиться и объяснять.
-  * ДПФ реального сигнала (вибрация) и ось частот;
+  * Числовые примеры согласованы с ноутбуком ''lecture03.ipynb''.
-  * стоимость O(N²) → **мотив к БПФ** (лекция 4).
-===== Ключевые понятия =====
+----
-  * Х[k] — комплексная амплитуда частоты f<sub>k</sub>; |Х| — амплитуда, arg Х — фаза;
+===== Цели лекции (что должен уметь студент) =====
-  * бины, разрешение, утечка;
-  * круговая свёртка ↔ умножение спектров; дополнение нулями до линейной свёртки.
+  - Понять, зачем нужно **ДПФ**:
+    * интеграл заменяется суммой;
+    * из ''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**: свёртка, корреляция, согласованная фильтрация.
 ===== Материалы =====
@@ Line 28: / Line 363: @@
   * {{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, все исходники)}}
-===== Задание =====
-Посчитать ДПФ сигнала своего проекта, правильно построить ось частот, отметить Δf, проверить симметрию, показать утечку и сравнить с непрерывной теорией.