Дискретизация и теорема Котельникова

Цели урока

• Понимать дискретизацию как взятие отсчётов и связь с периодичностью спектра
• Объяснять aliasing и почему он необратим
• Формулировать теорему Котельникова и применять её к практическим задачам
• Рассчитывать SNR через формулу 6.02B + 1.76 дБ

Предварительные знания

• Signals and Systems

MP3 убил CD-индустрию. JPEG убил плёночную фотографию. AAC в AirPods - 256 кбит/с вместо 1411 кбит/с. Всё это - дискретное преобразование Фурье. Алгоритм Кули-Тьюки 1965 года, который сжал мировую музыку в 8 раз. Но прежде чем сжать - нужно правильно дискретизировать.

• **Spotify/Apple Music:** вся цифровая музыка на 44.1 кГц - прямое следствие теоремы Котельникова (fmax = 20 кГц)
• **AirPods (Apple H2 chip):** 1-битный ΔΣ АЦП на 5 МГц -> цифровой фильтр -> 256 кбит/с AAC за 11ms latency
• **Tesla LiDAR:** 100K точек/сек при 905 нм -> АЦП на 1+ ГГц для ToF измерений
• **Медицинское УЗИ:** частота зонда 1-20 МГц -> fs = 40-100 МГц -> теорема Котельникова на мегагерцах
• **ЭКГ (Apple Watch):** fs = 512 Гц при максимальной частоте сердечного сигнала ~150 Гц - запас 3.4x

Джеймс Кули и Джон Тьюки: алгоритм, изменивший мир

В 1965 году Джеймс Кули и Джон Тьюки опубликовали в **Mathematics of Computation** статью «An Algorithm for the Machine Calculation of Complex Fourier Series» - алгоритм быстрого преобразования Фурье (FFT). Вычислительная сложность DFT снизилась с O(N^2) до O(N log N). Это сделало реальной обработку аудио и изображений в реальном времени. Позже выяснилось, что Гаусс знал этот алгоритм ещё в 1805 году - но не опубликовал.

Дискретизация (sampling)

MP3 убил CD-индустрию. JPEG убил плёночную фотографию. AAC в AirPods - 256 кбит/с вместо 1411 кбит/с. Всё это - дискретное преобразование Фурье. Алгоритм Кули-Тьюки 1965 года, который сжал мировую музыку в 8 раз. Но прежде чем сжать - нужно **дискретизировать**: взять отсчёты непрерывного звука через равные промежутки времени.

Математически: x[n] = x(nT), где T - период дискретизации, f_s = 1/T - частота дискретизации. В частотной области дискретизация - умножение на «расчёску Дирака», что приводит к **периодическому повторению спектра** с периодом f_s. Именно здесь прячется aliasing.

**44100 Гц - не случайное число!** Выбрано как 2 * 20000 + запас для слышимого диапазона. Точнее: 44100 = 2^2 * 3^2 * 5^2 * 7^2 - удобное число для делителей в форматах PAL и NTSC. Apple Music использует 44.1 кГц для совместимости с CD с 1982 года.

Наложение спектров (aliasing)

**Aliasing** - катастрофа: если f_s < 2 * f_max, копии спектра перекрываются и высокие частоты маскируются под низкие. Информация потеряна **безвозвратно**. Не «немного искажена» - именно уничтожена. Никакой постобработкой это не исправить.

Колёса в кино. Камера снимает 24 кадра/сек. Если колесо вращается быстрее 12 оборотов/сек, оно кажется вращающимся назад или стоящим на месте. Это aliasing - **стробоскопический эффект**. Та же математика в AudioDSP: высокая частота «прикидывается» низкой.

**Anti-aliasing фильтр** - аналоговый низкочастотный фильтр, применяемый ПЕРЕД АЦП. Он срезает частоты выше f_s/2, предотвращая наложение. Физически есть в каждом микрофоне, АЦП, камере. В компьютерной графике anti-aliasing решает ту же проблему - пространственный aliasing диагональных линий.

Aliasing необратим: после дискретизации 80 Гц и 20 Гц дают идентичные отсчёты. Единственная защита - фильтрация ДО дискретизации. Именно поэтому anti-aliasing фильтр должен быть аналоговым, а не цифровым.

Теорема Найквиста-Котельникова-Шеннона

**Теорема дискретизации:** сигнал с максимальной частотой f_max может быть ТОЧНО восстановлен из отсчётов, если f_s >= 2 * f_max. Частота 2 * f_max называется **частотой Найквиста**. Это не эмпирическое правило - это математическая теорема с доказательством.

Восстановление через sinc-интерполяцию: x(t) = sum(x[n] * sinc((t - nT)/T)), где sinc(x) = sin(pi * x) / (pi * x). Каждый отсчёт порождает sinc-импульс, и их сумма точно воссоздаёт исходный сигнал. На практике идеальный sinc-фильтр физически нереализуем - поэтому oversampling.

**На практике oversampling.** CD Audio: fmax = 20 кГц, fs = 44.1 кГц (коэффициент 2.2). Запас нужен для физически реализуемого anti-aliasing фильтра - идеальный прямоугольный фильтр невозможен. Студийная запись: 96-192 кГц для запаса при обработке.

Квантование

После дискретизации по времени значения всё ещё вещественные. **Квантование** округляет их до ближайшего из конечного набора уровней. B-битное квантование - 2^B уровней. **Ошибка квантования** равномерно распределена в [-Delta/2, Delta/2] - это «шум квантования».

**Золотая формула SNR:** SNR = 6.02 * B + 1.76 дБ. Каждый дополнительный бит даёт ~6 дБ. 16 бит CD - ~96 дБ динамический диапазон: от тихого шёпота до громкого концерта. 24 бита студии - ~146 дБ, что превышает физический предел слуха.

**Oversampling + noise shaping** - современные АЦП дискретизируют на очень высокой частоте с 1 битом, затем цифровой фильтр преобразует в стандартный формат. Это технология DSD (Direct Stream Digital): 1-битный поток на 2.8 МГц даёт SNR выше, чем 16-бит при 44.1 кГц.

Дискретизация + квантование = **аналого-цифровое преобразование (АЦП)**. Весь цифровой аудиомир: микрофон -> АЦП -> числа -> DSP обработка -> ЦАП -> динамик. Теорема Котельникова гарантирует: если частота дискретизации достаточна - потерь нет. AAC в AirPods сжимает 1411 кбит/с до 256 кбит/с - это уже работа кодека поверх теоремы.

Ключевые идеи

• **Дискретизация:** x[n] = x(nT), спектр периодически повторяется с периодом fs
• **Aliasing:** если fs < 2 * fmax, спектры перекрываются. Информация уничтожена безвозвратно
• **Теорема Котельникова:** fs >= 2 * fmax - необходимое и достаточное условие точного восстановления
• **Anti-aliasing фильтр:** аналоговый LPF перед АЦП - единственная защита от aliasing
• **Квантование:** B бит -> SNR = 6.02B + 1.76 дБ. 16 бит CD ~= 96 дБ динамического диапазона
• **Oversampling:** практически fs >> 2 * fmax из-за нереализуемости идеального фильтра

Связанные темы

Дискретизация - мост между аналоговым и цифровым мирами:

• Сигналы и системы — Дискретные сигналы - результат дискретизации непрерывных
• Z-преобразование — Z-преобразование анализирует дискретные сигналы, полученные после дискретизации

Вопросы для размышления

• Почему anti-aliasing фильтр должен быть аналоговым (до АЦП), а не цифровым (после)?
• Hi-Res Audio (96/192 кГц) - маркетинг или реальное улучшение? Человек не слышит выше 20 кГц - зачем fs > 44.1 кГц?
• ΔΣ-модуляция (1 бит, очень высокая fs) - как из 1 бита получить качество лучше 16 бит?

Связанные уроки

• dsp-01 — Сигналы, спектры и преобразование Фурье вводятся в предыдущем уроке
• dsp-03 — Z-преобразование анализирует дискретные сигналы, полученные после дискретизации
• dsp-04 — Цифровые фильтры работают с дискретными сигналами
• it-02 — Теорема Котельникова и теорема Шеннона о пропускной способности канала - одна математика
• calc-01-sequences — Последовательности и дискретные функции - математическая основа дискретных сигналов
• prob-11-normal — Шум квантования моделируется как равномерное распределение - связь с теорией вероятностей
• prob-06-random-vars