digital-signal-processing

Технологии и ограничения:

Языки программирования: Java, Python, C++;
Дополнительные библиотеки: Apache math3;

Общие требования по выполнению:

Код должен быть написан понятно и аккуратно, с соблюдением табуляции и прочих элементов написания, без лишних элементов и функций, не имеющих отношения к функционалу тестового задания, снабжен понятными комментариями.
Чистота и оформление кода — не менее важный фактор. Код должен быть написан в едином стиле (желательно в рекомендуемом для конкретного языка). Также к чистоте относятся отсутствие копипаста и дублирования логики.
Исходные коды должны быть в Git. Желательно делать частые информативные коммиты, активно использовать ветки.
Должна быть инструкция по сборке и разворачиванию, а также должен быть описан порядок развертывания и запуска проекта в среде разработки (включая настройку БД, дамп схемы БД, настройку сервера приложения для запуска и т.д.)
Сервисы (серверная часть) должны быть максимально покрыты модульными тестами
Интерфейс должен отвечать требованиям usability

Зависимости

Для С++ присутствует единственная зависимость The Fastest Fourier Transform in the West (FFTW) - это библиотека для вычисления дискретного преобразования Фурье (ДПФ) в одном или нескольких измерениях, произвольного входного размера и как действительных, так и комплексных данных(а также четных/нечетных данных, то есть дискретных косинусных/синусных преобразований). Для Python, который используется для визуализации данных требуется matplotlib.

Сборка

Необходимо заранее установить самостоятельно FFTW и matplotlib перед сборкой проекта

mkdir build
cd build
cmake ..
make

Запуск

Для запуска необходимо запустить исполняемый файл digital-signal-processing/digital-signal-processing.exe и выполнить run-plotter.sh/run-plotter.cmd, которому при необходимости выдать права на исполнение с помощью команды

chmod +x run-plotter.sh

Выполнение работы

NoiseGenerator, NoiseSignalGenerator, SignalFunction, и SignalGenerate
- Сигналы генерируются по формуле: $$ A\sin{\pi t * \nu + offset}, $$ где t - время, A - амплитуда, $\nu$ - частота, $offset$ - сдвиг.
WindowingFilter
- Сглаживание скользящим окном происходит по формуле: $$ x_i = \frac{\sum\limits_{j = i - w}^{i + w} x_j}{w}, $$ где $x_i$ - i-ый элемент, w - размер окна сглаживания.
- Также отдельно рассматриваются случаи, когда размер окна слева или справа больше количества элементов.
AutocorrelationFunction, FFTAutoCorrelation и RingShiftFunction
- Кольцевая автокорреляция вычисляется с помощью: $$ cross_correlation = (product - mean_original * mean_shifted) / (rms_original * rms_shifted), $$ где $product$ - это сумма произведений элементов соответствующих сигналов, $mean_original$ и $mean_shifted$ - средние значения элементов в каждом сигнале, $rms_original$ и $rms_shifted$ - среднеквадратичные значения элементов в каждом сигнале.
- Автокорреляционная функция с использованием быстрого преобразования Фурье (БПФ) использует формулы: $$ \Phi(\tau) = Re fft^{-1}(|fft(\Vec{x})|^2), $$ где fft и $fft^{-1}$ - прямое и обратное БПФ, Re - вещественная часть комплексного числа.
- Также необходима формула вычисления комплексного модуля: $$ |\Vec{a}|^2 = {Re^2a_i + Im^2a_i}, $$ где Re и Im - вещественная и мнимая части комплексного числа.
- Если нет погрешностей вычисления, мнимая часть будет равна нулю. Также необходимо поделить на коэффициент пропорциональности $\Phi(0)$.
- Однако перед всем этим необходимо вычесть из ряда среднее арифметическое и преобразовать в комплексные числа. После дополнить нулями до $2^k$. Затем дописать в конец ещё $2^k$ нулей.
DistributionFunction
- Стандартная реализация функции распределения, заданная по формуле: $$ F(x) = P(X < x), $$ где X - величина сигнала.