Преобразование Фурье: почему MP3 весит мало

Теория

Дискретное преобразование Фурье (ДПФ) раскладывает сигнал из $N$ отсчётов $x[0], \dots, x[N-1]$ на сумму синусоид с частотами $f = 0, 1, \dots, N - 1$:

$$ X[f] = \sum_{n=0}^{N-1} x[n] \, e^{-2\pi i f n / N}, \qquad x[n] = \frac{1}{N} \sum_{f=0}^{N-1} X[f] \, e^{2\pi i f n / N}. $$

Модуль $|X[f]|$ — амплитуда частоты $f$, аргумент — её фаза. Для вещественного сигнала спектр симметричен: $X[N - f] = \overline{X[f]}$, поэтому достаточно хранить частоты от $0$ до $N/2$.

Сжатие. Энергия реальных сигналов сосредоточена в небольшом числе частот. Если оставить $K$ коэффициентов с наибольшей амплитудой, обнулить остальные и выполнить обратное преобразование, получится приближение $\hat x$. Каждая сохранённая гармоника требует трёх чисел: номера частоты, вещественной и мнимой части. Степень сжатия равна $N / 3K$, качество оценивается относительной ошибкой:

$$ \mathrm{RMSE} = \sqrt{\frac{\sum_n (x[n] - \hat x[n])^2}{\sum_n x[n]^2}}. $$

Гладкий сигнал восстанавливается по нескольким гармоникам. Сигнал с резкими перепадами (меандр, пила) требует многих гармоник; при малом $K$ около скачков возникают колебания — явление Гиббса.

Быстрое преобразование Фурье (БПФ) вычисляет ДПФ за $O(N \log N)$ операций вместо $O(N^2)$.