1. Сначала включим все необходимые заголовочные файлы и объявим об использовании пространства имен
std
:
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
2. Точка графика сигнала представляет собой комплексное число, которое будет выражено с помощью типажа
std::complex
, специализированного для типа double
. Таким образом, псевдоним типа cmplx
будет расшифровываться в виде двух связанных значений типа double
, которые представляют действительную и мнимую части комплексного числа. Весь сигнал представляет собой вектор, содержащий подобные элементы; назовем этот тип csignal
:
using cmplx = complex;
using csignal = vector;
3. Чтобы проитерировать по возрастающей численной последовательности, мы возьмем численный итератор из соответствующего примера. Переменные
k
и j
и формулы преобразования будут итерировать по подобным последовательностям.
class num_iterator {
size_t i;
public:
explicit num_iterator(size_t position) : i{position} {}
size_t operator*() const { return i; }
num_iterator& operator++() {
++i;
return *this;
}
bool operator!=(const num_iterator &other) const {
return i != other.i;
}
};
4. Функция преобразования Фурье будет принимать сигнал и возвращать новый. Последний представляет собой преобразование Фурье, выполненное для входного сигнала. Обратное преобразование Фурье выполняется аналогично прямому, поэтому предоставим необязательный параметр булева типа, который указывает на направление преобразования. Обратите внимание: наличие подобных параметров зачастую указывает на плохой стиль программирования, особенно если в сигнатуре функции их несколько. Здесь мы для краткости применили всего один параметр булева типа.
Первое, что нужно сделать, — это выделить память для нового вектора сигналов, имеющего размер исходного сигнала:
csignal fourier_transform(const csignal &s, bool back = false)
{
csignal t (s.size());
5. В формуле имеются два множителя, которые всегда выглядят одинаково. Поместим их в отдельные переменные:
const double pol {2.0 * M_PI * (back ? -1.0 : 1.0)};
const double div {back ? 1.0 : double(s.size())};
6. Алгоритм
std::accumulate
отлично подходит для выполнения формул, которые складывают элементы. Мы воспользуемся им для диапазона увеличивающихся численных значений. На основе этих значений можно сформировать отдельные слагаемые для каждого шага. Алгоритм std::accumulat
e на каждом шаге вызывает бинарную функцию. Первым параметром данной функции будет текущее значение части суммы, которая уже была подсчитана на предыдущих шагах, а второй параметр — следующее значение диапазона. Мы выполняем поиск значения сигнала s
в текущей позиции и умножаем его на комплексный множитель, pol
. Затем возвращаем новую частичную сумму. Бинарная функция обернута в другое лямбда-выражение, так как мы станем использовать разные значения переменной j
при каждом вызове алгоритма accumulate
. Поскольку этот алгоритм цикла двумерный, внутреннее лямбда-выражение применяется для внутреннего цикла, а внешнее — для внешнего.
auto sum_up ([=, &s] (size_t j) {
return [=, &s] (cmplx c, size_t k) {
return c + s[k] *
polar(1.0, pol * k * j / double(s.size()));
};
});
7. Внутренняя часть преобразования Фурье теперь выполняется алгоритмом
std::accumulate
. Для каждой позиции алгоритма, кратной j
, подсчитываем сумму всех слагаемых для позиций i = 0...N. Эта идея оборачивается в лямбда-выражение, которое мы будем выполнять для каждой точки графика полученного вектора преобразования Фурье:
auto to_ft ([=, &s](size_t j){
return accumulate(num_iterator{0},
num_iterator{s.size()},
cmplx{},
sum_up(j))
/div;
});
8. До этого момента мы не выполняли код самого преобразования Фурье. Мы лишь подготовили множество вспомогательного кода, который сейчас и задействуем. Вызов
std::transform
сгенерирует значения j = 0...N для внешнего цикла. Преобразованные значения будут помещены в вектор t, который мы и вернем вызывающей стороне:
transform(num_iterator{0}, num_iterator{s.size()},
begin(t), to_ft);
return t;
}
9. Реализуем отдельные функции, которые позволяют создать объекты функций для генерации сигналов. Первая из них представляет собой генератор косинусоидального сигнала. Она возвращает лямбда-выражение, способное сгенерировать косинусоидальный сигнал на основе заданной длины периода. Сам сигнал может иметь произвольную длину, но его длина периода будет фиксированной. Длина периода N означает, что сигнал повторит себя спустя N шагов. Лямбда-выражение не принимает никаких параметров. Можно постоянно вызывать его, и для каждого вызова оно будет возвращать точку графика сигнала для следующего момента времени.
static auto gen_cosine (size_t period_len){
return [period_len, n{0}] () mutable {
return cos(double(n++) * 2.0 * M_PI / period_len);
};
}
10. Вторым сигналом будет прямоугольная волна. Она колеблется между значениями
–1
и +1
и не имеет других значений. Формула выглядит сложной, но она попросту преобразует линейное увеличивающееся значение n
в +1
или –1
, а изменяющаяся длина периода равна period_len
.Обратите внимание: в этот раз мы инициализируем n значением, не равным
0
. Таким образом, наша прямоугольная волна начинается в фазе, где ее выходные значения начинаются с +1
.
static auto gen_square_wave (size_t period_len)
{
return [period_len, n{period_len*7/4}] () mutable {
return ((n++ * 2 / period_len) % 2) * 2 - 1.0;
};
}
11. Сгенерировать сам сигнал с помощью указанных генераторов можно, выделив память для нового вектора и заполнив его значениями, сгенерированными на основе повторяющихся вызовов функции-генератора. Это делает функция
std::generate
. Она принимает пару итераторов (начальный и конечный) и функцию-генератор. Для каждой корректной позиции итератора она выполняет операцию *it = gen()
. Обернув данный код в функцию, мы легко сможем сгенерировать векторы сигналов.
template
static csignal signal_from_generator(size_t len, F gen)
{
csignal r (len);
generate(begin(r), end(r), gen);
return r;
}