izvolov / fftpp

БПФ с человеческим лицом / FFT done C++ way

🇬🇧 English version

FFT++

БПФ (быстрое преобразование Фурье), приготовленное по-плюсовому.

О проекте

FFT++ — это заголовочная библиотека, реализующая классическое БПФ на C++ так, как это должно быть сделано на C++. Интерфейс, красота и понятность кода, а также простота в подключении и использовании не приносятся в жертву эффективности.

Текущая функциональность включает прямое и обратное БПФ в комплексных числах и в модульной арифметике. Для целочисленного преобразования реализован класс fftpp::basic_ring и его специализации: fftpp::ring8, fftpp::ring16, fftpp::ring30.

Содержание

1. Комплексное БПФ
2. Целочисленное БПФ
3. Установка
   1. Вариант 1: CMake FetchContent
   2. Вариант 2: Установить с помощью CMake
   3. Вариант 3: Скопировать исходники
   4. Вариант 4: Подключить папку с проектом в CMake
4. Требования

Комплексное БПФ

Примечание: В алгоритме используются комплексные числа из STL. Заголовок fftpp/complex.hpp нужен для специальных функций, требуемых для БПФ:

• Получения единицы;
• Получения первообразного корня степени n из единицы;
• Получения обратного элемента к n.

#include <fftpp/complex.hpp>
#include <fftpp/fft.hpp>
#include <fftpp/inverse_fft.hpp>

#include <complex>
#include <vector>

int main ()
{
    const auto in = std::vector{1, 2, 3, 4};

    // Фунциональный объект, хранящий (при необходимости) предпосчитанные
    // значения, необходимые для эффективной работы алгоритма.
    const auto fft = fftpp::fft_t<std::complex<double>>(in.size());

    // Прямое БПФ
    auto out = std::vector<std::complex<double>>(in.size());
    fft(in.begin(), out.begin());

    // Обратное БПФ
    auto inv = std::vector<std::complex<double>>(out.size());
    inverse(fft)(out.begin(), inv.begin());
}

Целочисленное БПФ

Примечание: Для БПФ в модульной арифметике необходимо подключить класс, реализующий кольцо по простому модулю, а также все необходимые для БПФ специальные функции. Удобнее всего это сделать с помощью подключения заголовка fftpp/ring.hpp.

#include <fftpp/ring.hpp>
#include <fftpp/fft.hpp>
#include <fftpp/inverse_fft.hpp>

#include <cstdint>
#include <vector>

int main ()
{
    const auto in = std::vector{1, 2, 3, 4};

    // Фунциональный объект, хранящий (при необходимости) предпосчитанные
    // значения, необходимые для эффективной работы алгоритма.
    const auto fft = fftpp::fft_t<fftpp::ring30>(in.size());

    // Прямое БПФ
    auto out = std::vector<fftpp::ring30>(in.size());
    fft(in.begin(), out.begin());

    // Обратное БПФ
    auto inv = std::vector<fftpp::ring30>(out.size());
    inverse(fft)(out.begin(), inv.begin());
}

Установка

Возможны следующие четыре варианта установки.

Вариант 1: CMake FetchContent

Начиная с версии CMake 3.14 можно скачать и подключить репозиторий с зависимостью прямо во время сборки с помощью модуля FetchContent. В случае с FFT++ это можно записать тремя командами:

include(FetchContent)
FetchContent_Declare(fftpp GIT_REPOSITORY https://github.com/izvolov/fftpp.git)
FetchContent_MakeAvailable(fftpp)

Этот набор команд породит интерфейсную библиотеку fftpp::headers, которую можно использовать при подключении библиотек:

add_executable(program program.cpp)
target_link_libraries(program PRIVATE fftpp::headers)

Вариант 2: Установить с помощью CMake

cd path/to/build/directory
cmake -DCMAKE_BUILD_TYPE=Release path/to/fftpp
make
make install

После этого в системе сборки CMake будет доступен пакет fftpp:

find_package(fftpp)

Эта команда породит интерфейсную библиотеку fftpp::headers, которую можно использовать при подключении библиотек:

add_executable(program program.cpp)
target_link_libraries(program PRIVATE fftpp::headers)

Вариант 3: Скопировать исходники

Поскольку FFT++ — полностью заголовочная библиотека, то достаточно скопировать в нужную директорию все заголовки из папки include из репозитория и подключить их в свой проект.

Вариант 4: Подключить папку с проектом в CMake

add_subdirectory("path/to/fftpp")

После этого в системе сборки CMake будет доступна цель fftpp::headers, которую можно использовать при подключении библиотек:

add_executable(program program.cpp)
target_link_libraries(program PRIVATE fftpp::headers)

Требования

0. Система сборки CMake версии 3.25 или выше;
1. Любой компилятор, который сносно поддерживает стандарт C++20, например, GCC 10 или Clang 13. Заведомо работающие конфигурации перечислены в интеграционных скриптах;
2. Библиотека FFTW для проведения замеров [не обязательно*].
3. Библиотека тестирования doctest [Не обязательно**];
4. Doxygen [Не обязательно].

*) Можно включить сравнительные замеры с библиотекой FFTW. Для этого нужно при сборке с помощью CMake включить опцию FFTPP_BENCH_FFTW (по умолчанию она выключена):

cmake -DCMAKE_BUILD_TYPE=Release path/to/fftpp -FFTPP_BENCH_FFTW=ON

**) Можно миновать этап сборки и тестирования, если при сборке с помощью CMake выключить опцию FFTPP_TESTING:

cmake -DCMAKE_BUILD_TYPE=Release path/to/fftpp -DFFTPP_TESTING=OFF

Также тестирование автоматически отключается в случае, если FFT++ подключается в качестве подпроекта.

fftpp's Issues

Специализации для колец

Сделать специализации fftpp::ring_t для разных типов со своими простыми модулями.
Например, для uint8 — 257, хранить в uint16, для uint16 — 65537, хранить в uint32.

Добить покрытие до 100%

Сейчас покрытие тестами 83%.
Нужно, чтобы было 100%.

БПФ в исходном массиве

Реализовать вариант БПФ, когда преобразование происходит прямо во входном массиве.

auto signal = std::vector{...};
fft(signal.begin());

В этом случае исходный массив должен сразу содержать элементы, к которым применимо БПФ (концепция field).

Вариант с упрощённым предпосчётом

Можно посчитать w_nk только для n = size, а все остальные брать из этого множества:

• При n = size / 2: w_n^2k
• При n = size / 4: w_n^4k
• и т.д.

Замерить результат. Если будет лучше, то исправить. Если хуже, то оставить текущий.

Сделать английскую справку

И заполнить README.en.md.

Подумать о расчёте таблиц на этапе компиляции

Сейчас существует несколько заранее посчитанных и прибитых гвоздями таблиц:

• Таблицы первообразных корней из единицы;
• Таблицы обратных к степени двойки.

Их можно было бы высчитывать на этапе компиляции исходя из заданного простого модуля.
Можно рассчитать их на этапе компиляции, если это не сильно ухудшит время компиляции.

Завести инструменты для обобщённых замеров с графиками

Запускать все алгоритмы с разным размером БПФ и строить график.

Поправить сборку на некоторых компиляторах

• Сделать дружественную функцию вывода класса ring_t более локальной;
• Поправить сравнение на равенство для плавучки;
• Устранить неявные преобразования;
• Прочие мелочи.

Поддержать conan