Цифровая обработка сигналов
Дискретное преобразование Фурье (DFT)
Spotify анализирует 100 миллионов треков для рекомендаций по BPM, тональности и жанру. Всё это начинается с DFT - преобразования 44 100 чисел в секунду в список частот. Без DFT не было бы ни Shazam, ни голосовых ассистентов, ни MP3.
- **Shazam** вычисляет DFT каждые 100 мс, ищет характерные пики спектра и сопоставляет их с базой из 100 млн треков за <1 секунду
- **MP3 / AAC:** MDCT (модифицированный DFT) разбивает звук на частоты, психоакустическая модель определяет что не слышит ухо, кодек убирает это - сжатие 10:1 без слышимых потерь
- **Кардиограф:** ЭКГ сигнал содержит компоненту 50 Гц (помеха сети). DFT определяет её амплитуду и фазу, notch фильтр вычитает её из сигнала
Исторический контекст
В 1965 году Кули и Тьюки опубликовали алгоритм FFT (Fast Fourier Transform) в журнале Mathematics of Computation. До этого DFT вычислялся за O(N²) - анализ сигнала из 1024 точек требовал миллиона операций. FFT сократил это до N*log₂(N) = 10 240 операций - ускорение в 100 раз. Позже выяснилось, что Гаусс знал этот алгоритм ещё в 1805 году, но не опубликовал. FFT признан одним из 10 важнейших алгоритмов XX века и сделал возможной цифровую обработку сигналов в реальном времени.
DFT: разложение сигнала на частоты
**1965 год, Bell Labs. Инженер записывает речь на магнитофон. Чтобы убрать шум на 400 Гц, нужно знать - а есть ли там этот шум? С временным представлением сигнала - массивом 44 100 сэмплов в секунду - ответить невозможно.** Нужно перейти в frequency domain. DFT делает именно это: превращает N временных сэмплов в N комплексных коэффициентов, каждый описывает одну частотную составляющую.
**Формула DFT:** X[k] = Σ(n=0..N-1) x[n] * e^(-j*2π*k*n/N). Здесь k - номер частоты (bin), X[k] - комплексный коэффициент, |X[k]| - амплитуда на частоте k*Fs/N Гц. Прямая вычислительная сложность: O(N²).
| Параметр | Формула | Пример при Fs=44100, N=1024 |
|---|---|---|
| Частотное разрешение | Δf = Fs / N | 44100 / 1024 ≈ 43 Гц на bin |
| Макс. частота (Найквист) | Fs / 2 | 22050 Гц |
| Временное разрешение | T = N / Fs | 1024 / 44100 ≈ 23 мс |
| Сложность наивного DFT | O(N²) | N=1024: ~1 000 000 операций |
Сигнал записан при Fs=8000 Гц, взят блок N=1024 сэмплов. Какое частотное разрешение DFT?
Частотная область: что значат коэффициенты
DFT возвращает N комплексных чисел X[k]. Каждое - проекция сигнала на синусоиду частоты k*Fs/N. Комплексное число кодирует сразу амплитуду (|X[k]|) и фазу (arg(X[k])). Для действительного сигнала: X[N-k] = X[k]* (комплексное сопряжение) - левая половина спектра зеркалит правую, поэтому смотрят только на k=0..N/2.
**DC компонент X[0]:** среднее значение сигнала (постоянная составляющая). Если сигнал симметричен вокруг нуля - X[0] ≈ 0. **X[N/2]:** компонента на частоте Найквиста. Для реального сигнала X[N/2] всегда вещественный.
DFT действительного сигнала из N сэмплов даёт N комплексных коэффициентов. Сколько независимых частотных компонент содержит результат?
Спектр: амплитудный и фазовый
Амплитудный спектр |X[k]| показывает «силу» каждой частоты. Фазовый спектр arg(X[k]) показывает сдвиг. Для большинства практических задач (EQ, noise reduction, pitch detection) достаточно амплитудного спектра. Фаза критична при модификации сигнала с последующим обратным IDFT - иначе возникают артефакты.
**Нормировка:** сырой |X[k]| масштабирован на N. Для single-sided спектра (только положительные частоты): amplitude = 2*|X[k]|/N. Для DC (k=0) и Найквиста (k=N/2) множитель 2 не нужен. Без нормировки сравнение спектров разных размеров блоков некорректно.
Амплитуда сигнала 1000 Гц равна 0.5. После DFT блока N=1024 при Fs=44100 Гц, какое значение |X[k]| на bin k=23 (1000 Гц)?
Spectral Leakage: артефакт конечного окна
**Главный артефакт DFT:** если частота сигнала не попадает точно в bin (k*Fs/N), энергия «вытекает» в соседние bins. Тон 441 Гц при Fs=8000, N=1024 попадает между бинами 56 (440.6 Гц) и 57 (448.4 Гц). Спектр показывает размазанный пик с боковыми лепестками, а не острый пик на 441 Гц.
| Оконная функция | Уровень лепестков | Ширина пика | Применение |
|---|---|---|---|
| Прямоугольная | -13 dB | 1 bin | Нет leakage если частота точно в bin |
| Hanning | -31 dB | 2 bins | Аудио обработка, спектральный анализ |
| Hamming | -41 dB | 2 bins | Фильтрация, речевая обработка |
| Blackman | -58 dB | 3 bins | Когда нужно максимально подавить leakage |
| Kaiser | -80+ dB | настраивается | DSP-фильтры высшей точности |
Оконная функция устраняет spectral leakage полностью
Окно лишь уменьшает leakage, перераспределяя энергию боковых лепестков. При этом расширяется главный лепесток - теряется частотное разрешение.
Это фундаментальный trade-off: узкий пик (хорошее разрешение) vs низкие лепестки (меньше leakage). Прямоугольное окно - максимальное разрешение, максимальный leakage. Blackman - минимальный leakage, минимальное разрешение. Нет окна, которое выигрывает по обоим параметрам.
Анализируем спектр и видим широкий смазанный пик вместо острого на 1000 Гц. В чём причина и как исправить?
DFT: главное
- DFT преобразует N временных сэмплов в N комплексных частотных коэффициентов: X[k] = Σ x[n] * e^(-j2πkn/N)
- Частотное разрешение Δf = Fs/N; максимальная частота = Fs/2 (Найквист)
- Амплитуда частоты k: |X[k]|, нормировка: 2*|X[k]|/N для single-sided спектра
- Spectral leakage возникает когда частота сигнала не кратна Fs/N - применять оконные функции
- Прямое DFT O(N²); FFT (Кули-Тьюки, 1965) вычисляет то же за O(N log N)
Вопросы для размышления
- Shazam распознаёт песню за <1 секунду даже при шуме. Как думаете - почему для распознавания используют пики амплитудного спектра, а не всю информацию о фазе? Что теряется при игнорировании фазы?