Лабораторная 3.5 — Сложность FFT и selected-bin detection

Эта лабораторная усиливает фундамент DSP без notebook-подхода. Это детерминированная script-driven работа, которая связывает вычислительную сложность спектрального анализа с SDR-измерениями и FPGA-архитектурой.

Цель

Сравнить три стратегии анализа:

Стратегия	Когда полезна	Инженерное следствие
Direct DFT	Малые эталонные векторы и обучение.	Простая, но плохо масштабируется.
Full FFT	Spectrum display, measurement dashboard и неизвестные сигналы.	Эффективный полный спектр, но появляются требования к памяти, порядку данных и архитектуре.
Selected-bin detection	Известные тоны, пилоты, узкополосные проверки.	Может быть дешевле FFT, если нужны только несколько частот.

Команда запуска

Из корня репозитория:

python blocks/block_03_dsp_basics/python/lab_3_5_fft_complexity.py

Или через общий reproducibility suite:

python tools/run_all_labs.py

Генерируемые артефакты

Артефакт	Назначение
docs/assets/lab35_dft_fft_complexity.png	Рост вычислительных затрат Direct DFT и FFT.
docs/assets/lab35_selected_bin_tradeoff.png	Full-spectrum FFT против selected-bin detector.
docs/assets/lab35_fft_complexity_metrics.json	Машиночитаемые отношения сложности для CI и отчёта.

Инженерные вопросы

1. Начиная с каких размеров N direct DFT становится непрактичной для SDR-анализа?
2. Когда оправдан полный FFT, а когда selected-bin detection?
3. Как изменится выбор при FPGA streaming design?
4. Какие компромиссы по памяти и latency возникают при переходе от скрипта к RTL?

Что включить в отчёт

• Оба сгенерированных графика.
• Отношение сложности DFT/FFT на максимальном N.
• Отношение FFT/selected-bin на максимальном N.
• Обоснование выбора метода для:
• мониторинга спектра;
• обнаружения одиночного pilot tone;
• wideband unknown-signal search;
• FPGA-реализации с ограниченными ресурсами.

Связь со следующими блоками

Эта лабораторная напрямую связана с:

• Block 05: ресурсы FFT и streaming architecture;
• Block 08: обнаружение pilot/synchronization;
• Block 09: анализ спектра записанных IQ;
• Block 11: measurement dashboard design.

Чего ожидать

DFT/FFT ratio at N=65536: 4096.0
FFT/selected-bin ratio at N=65536: 4.0

• Числа операций это нормированные модели: прямое ДПФ стоит N^2, БПФ это N/2 * log2(N), а вычисление K выбранных бинов это K * N.
• При N = 65 536 прямое ДПФ в 4096 раз дороже БПФ (2N / log2 N). Это отношение растёт неограниченно: поэтому полный спектр прямым ДПФ никто не считает.
• Четыре выбранных бина всё ещё в 4 раза дешевле полного БПФ при этом размере. Точка равенства это K = log2(N) / 2 = 8 бинов: выше неё полное БПФ выигрывает, даже если нужно лишь несколько частот. Это ровно то решение «Гёрцель или БПФ», которое принимают при обнаружении пилотов или тонов.

Упражнения

1. Посчитайте отношение ДПФ/БПФ для N = 64, 1024 и 65 536 вручную и сверьте с графиком.
2. Сколько выбранных бинов можно позволить при N = 4096, прежде чем полное БПФ станет дешевле?
3. Модель не учитывает память. Потоковому БПФ нужен буфер на N комплексных слов, детектору Гёрцеля: два слова на бин. Что вы выберете для обнаружения 3 известных пилотов в FPGA с малым объёмом блочной памяти и почему?

Ответы (проверены запуском скрипта лабораторной)

1. При модельных стоимостях N² и N/2·log2 N отношение равно 2N / log2 N: 21,3 при N = 64, 204,8 при 1024, 4096 при 65 536.
2. K выбранных бинов стоят K·N, FFT: N/2·log2 N, поэтому точка равенства: K = log2(N)/2 = 6 бинов при N = 4096. Пять бинов и меньше дешевле считать по одному.
3. Goertzel: трём детекторам нужно 6 слов состояния вместо буфера на 4096 слов и 3·N умножений на блок, меньше одного FFT. При малом объёме блочной RAM и немногих известных частотах он выигрывает по обоим пунктам.