libdspl-2.0
Алгоритмы дискретного и быстрого преобразования Фурье

Структуры данных

struct  fft_t
 Структура данных объекта быстрого преобразования Фурье Подробнее...
 

Функции

int dft (double *x, int n, complex_t *y)
 Дискретное преобразование Фурье вещественного сигнала. Подробнее...
 
int dft_cmplx (complex_t *x, int n, complex_t *y)
 Дискретное преобразование Фурье комплексного сигнала. Подробнее...
 
int fft_create (fft_t *pfft, int n)
 Заполнение структуры fft_t для алгоритма БПФ Подробнее...
 
void fft_free (fft_t *pfft)
 Очистить структуру fft_t алгоритма БПФ Подробнее...
 
int fft_shift (double *x, int n, double *y)
 Перестановка спектральных отсчетов дискретного преобразования Фурье Подробнее...
 
int fourier_series_dec (double *t, double *s, int nt, double period, int nw, double *w, complex_t *y)
 Расчет коэффициентов разложения в ряд Фурье Подробнее...
 
int fourier_series_rec (double *w, complex_t *s, int nw, double *t, int nt, complex_t *y)
 Восстановление сигнала при усечении ряда Фурье Подробнее...
 
int goertzel (double *x, int n, int *ind, int k, complex_t *y)
 Алгоритм Герцеля для расчета отдельных спектральных отсчетов дискретного преобразования Фурье вещественного сигнала x. Подробнее...
 
int goertzel_cmplx (complex_t *x, int n, int *ind, int k, complex_t *y)
 Алгоритм Герцеля для расчета отдельных спектральных отсчетов дискретного преобразования Фурье комплексного сигнала x. Подробнее...
 

Подробное описание

Алгоритмы дискретного и быстрого преобразования Фурье.

Функции

◆ dft()

int dft ( double *  x,
int  n,
complex_t y 
)

Дискретное преобразование Фурье вещественного сигнала.


Функция рассчитывает $ n $-точечное дискретное преобразование Фурье вещественного сигнала $ x(m) $, $ m = 0 \ldots n-1 $.

\[ Y(k) = \sum_{m = 0}^{n-1} x(m) \cdot \exp \left( -j \cdot \frac{2\pi}{n} \cdot m \cdot k \right), \]

где $ k = 0 \ldots n-1 $.

Аргументы
[in]xУказатель на вектор вещественного входного сигнала $x(m)$, $ m = 0 \ldots n-1 $.
Размер вектора [n x 1].

[in]nРазмер ДПФ $n$ (размер векторов входного сигнала и результата ДПФ).

[out]yУказатель на комплексный вектор результата ДПФ $Y(k)$, $ k = 0 \ldots n-1 $. Размер вектора [n x 1].
Память должна быть выделена.

Возвращает
RES_OK если ДПФ рассчитана успешно.
В противном случае код ошибки.

Пример использования функции dft:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "dspl.h"
#define N 16
int main()
{
void* handle; // DSPL handle
handle = dspl_load(); // Load DSPL function
double x[N]; // real input signal
complex_t y[N]; // DFT
for(int k = 0; k < N; k++)
x[k] = (double)k;
dft(x, N, y);
for(int k = 0; k < N; k++)
printf("y[%2d] = %9.3f%9.3f\n", k, RE(y[k]), IM(y[k]));
dspl_free(handle); // remember to free the resource
return 0;
}

Результат работы программы:

      y[ 0] =   120.000    0.000
      y[ 1] =    -8.000   40.219
      y[ 2] =    -8.000   19.314
      y[ 3] =    -8.000   11.973
      y[ 4] =    -8.000    8.000
      y[ 5] =    -8.000    5.345
      y[ 6] =    -8.000    3.314
      y[ 7] =    -8.000    1.591
      y[ 8] =    -8.000    0.000
      y[ 9] =    -8.000   -1.591
      y[10] =    -8.000   -3.314
      y[11] =    -8.000   -5.345
      y[12] =    -8.000   -8.000
      y[13] =    -8.000  -11.973
      y[14] =    -8.000  -19.314
      y[15] =    -8.000  -40.219
Автор
Бахурин Сергей. www.dsplib.org
Заметки
Данная функция выполняет расчет ДПФ наивным методом и требует $ n^2 $ комплексных умножений.
Для увеличения скорости расчета рекомендуется использовать алгоритмы быстрого преобразования Фурье.

См. определение в файле dft.c строка 31

◆ dft_cmplx()

int dft_cmplx ( complex_t x,
int  n,
complex_t y 
)

Дискретное преобразование Фурье комплексного сигнала.


Функция рассчитывает $ n $-точечное дискретное преобразование Фурье комплексного сигнала $ x(m) $, $ m = 0 \ldots n-1 $.

\[ Y(k) = \sum_{m = 0}^{n-1} x(m) \cdot \exp \left( -j \cdot \frac{2\pi}{n} \cdot m \cdot k \right), \]

где $ k = 0 \ldots n-1 $.

Аргументы
[in]xУказатель на вектор комплексного входного сигнала $x(m)$, $ m = 0 \ldots n-1 $.
Размер вектора [n x 1].

[in]nРазмер ДПФ $n$ (размер векторов входного сигнала и результата ДПФ).

[out]yУказатель на комплексный вектор результата ДПФ $Y(k)$, $ k = 0 \ldots n-1 $. Размер вектора [n x 1].
Память должна быть выделена.

Возвращает
RES_OK если ДПФ рассчитана успешно.
В противном случае код ошибки.

Пример использования функции dft_cmplx:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "dspl.h"
#define N 16
int main()
{
void* handle; // DSPL handle
handle = dspl_load(); // Load DSPL function
complex_t x[N]; // complex input signal
complex_t y[N]; // DFT
for(int k = 0; k < N; k++)
{
RE(x[k]) = (double)k;
IM(x[k]) = 0.0;
}
dft_cmplx(x,N,y);
for(int k = 0; k < N; k++)
printf("y[%2d] = %9.3f%9.3f\n", k, RE(y[k]), IM(y[k]));
dspl_free(handle); // remember to free the resource
return 0;
}

Результат работы программы:

      y[ 0] =   120.000    0.000
      y[ 1] =    -8.000   40.219
      y[ 2] =    -8.000   19.314
      y[ 3] =    -8.000   11.973
      y[ 4] =    -8.000    8.000
      y[ 5] =    -8.000    5.345
      y[ 6] =    -8.000    3.314
      y[ 7] =    -8.000    1.591
      y[ 8] =    -8.000    0.000
      y[ 9] =    -8.000   -1.591
      y[10] =    -8.000   -3.314
      y[11] =    -8.000   -5.345
      y[12] =    -8.000   -8.000
      y[13] =    -8.000  -11.973
      y[14] =    -8.000  -19.314
      y[15] =    -8.000  -40.219
Автор
Бахурин Сергей. www.dsplib.org
Заметки
Данная функция выполняет расчет ДПФ наивным методом и требует $ n^2 $ комплексных умножений.
Для увеличения скорости расчета рекомендуется использовать алгоритмы быстрого преобразования Фурье.
Примеры:
dft_indexation.c.

См. определение в файле dft.c строка 65

◆ fft_create()

int fft_create ( fft_t pfft,
int  n 
)

Заполнение структуры fft_t для алгоритма БПФ


Функция производит выделение памяти и рассчет векторов поворотных коэффициентов n-точечного БПФ для структуры fft_t.

Аргументы
[in,out]pfftУказатель на структуру fft_t.
Указатель не должен быть NULL.

[in]nРазмер БПФ $n$ (должен быть равен целой степени двойки).
Возвращает
RES_OK если структура заполнена успешно.
В противном случае код ошибки.

Заметки
Некоторые компиляторы при создании структуры не обнуляют ее содержимое. Поэтому рекомендуется произвести обнуление структуры после ее объявления:
fft_t pfft; // объявляем объект fft_t
int n = 64; // Размер БПФ
// обнуляем все поля и указатели.
// Данные шаг рекомендуется ввиду того, что некоторые
// компиляторы при создании переменной не инициализируют ее нулем.
memset(&pfft, 0, sizeof(fft_t));
int err;
//создаем объект для 64-точечного БПФ
err = fft_create(&pfft, n);
// .....
//очистить память объекта БПФ
fft_free(&pfft);
Перед выходом из программы выделенную в структуре память необходимо очистить функцией fft_free .
Автор
Бахурин Сергей. www.dsplib.org

См. определение в файле fft.c строка 205

◆ fft_free()

void fft_free ( fft_t pfft)

Очистить структуру fft_t алгоритма БПФ


Функция производит очищение памяти промежуточных данных и векторов поворотных коэффициентов структуры fft_t.

Аргументы
[in]pfftУказатель на структуру fft_t.
Автор
Бахурин Сергей. www.dsplib.org

См. определение в файле fft.c строка 445

◆ fft_shift()

int fft_shift ( double *  x,
int  n,
double *  y 
)

Перестановка спектральных отсчетов дискретного преобразования Фурье


Функция производит перестановку спектральных отсчетов ДПФ и переносит нулевую частоту в центр вектора ДПФ.
Данная функция обрабатывает вещественные входные и выходные вектора и может применяться для перестановки амплитудного или фазового спектра.

Аргументы
[in]xУказатель на исходный вектор ДПФ.
Размер вектора [n x 1].

[in]nРазмер ДПФ $n$ (размер векторов до и после перестановки).

[out]yУказатель на вектор результата перестановки.
Размер вектора [n x 1].
Память должна быть выделена.

Возвращает
RES_OK если перестановка произведена успешно.
В противном случае код ошибки:
Автор
Бахурин Сергей. www.dsplib.org
Примеры:
dft_indexation.c.

См. определение в файле fft.c строка 485

◆ fourier_series_dec()

int fourier_series_dec ( double *  t,
double *  s,
int  nt,
double  period,
int  nw,
double *  w,
complex_t y 
)

Расчет коэффициентов разложения в ряд Фурье


Функция рассчитывает спектр периодического сигнала при усечении ряда Фурье

Аргументы
[in]tУказатель на массив моментов времени дискретизации исходного сигнала s
размер вектора вектора [nt x 1].
Память должна быть выделена.

[in]sУказатель на массив значений исходного сигналаs
размер вектора вектора [nt x 1].
Память должна быть выделена.

[in]ntразмер выборки исходного сигнала.
Значение должно быть положительным.

[in]periodПериод повторения сигнала.

[in]nwРазмер усеченного ряда Фурье.

[out]wУказатель на массив частот спектра периодического сигнала.
Размер вектора [nw x 1].
Память должна быть выделена.

[out]yУказатель массив комплексных значений спектра периодического сигнала.
Размер вектора [nw x 1].
Память должна быть выделена.

Возвращает
RES_OK Массивы нулей и полюсов рассчитаны успешно.
В противном случае код ошибки.
Заметки
Для расчета спектра сигнала используется численное интегрирование исходного сигнала методом трапеций. Данная функция не является эффективной. Для увеличения скорости расчета спектра сигнала целесообразнее использовать алгоритмы дискретного и быстрого преобразования Фурье.
Автор
Бахурин Сергей www.dsplib.org
Примеры:
fourier_series_pimp_spectrum.c и fourier_series_rec.c.

См. определение в файле fourier_series.c строка 31

◆ fourier_series_rec()

int fourier_series_rec ( double *  w,
complex_t s,
int  nw,
double *  t,
int  nt,
complex_t y 
)

Восстановление сигнала при усечении ряда Фурье


Функция рассчитывает восстановленный сигнал при усечении ряда Фурье:

\[ s(t) = \sum\limits_{n = 0}^{n_{\omega}-1} S(\omega_n) \exp(j\omega_n t) \]

Аргументы
[in]wУказатель на массив частот $\omega_n$ усеченного ряда Фурье.
Размер вектора [nw x 1].
Память должна быть выделена и заполнена.

[in]sУказатель на массив значений спектра $S(\omega_n)$.
Размер вектора [nw x 1].
Память должна быть выделена и заполнена.

[in]nwКоличество членов усеченного ряда Фурье.
Значение должно быть положительным.

[in]tУказатель на массив временных отсчетов восстановленного сигнала.
Размер вектора [nt x 1].
Память должна быть выделена и заполнена.



[in]ntРазмер вектора времени и восстановленного сигнала.

[out]yУказатель на массив восстановленного сигнала.
Размер вектора [nt x 1].
Память должна быть выделена.

Возвращает
RES_OK Массивы нулей и полюсов рассчитаны успешно.
В противном случае код ошибки.
Заметки
Выходной восстановленный сигнал в общем случае является комплексным. Однако при соблюдении свойств симметрии векторов w и s относительно нулевой частоты получим мнимую часть элементов вектора y на уровне ошибок округления числа с двойной точностью. Ничтожно малую мнимую часть в этом случае можно игнорировать.
Автор
Бахурин Сергей www.dsplib.org
Примеры:
fourier_series_rec.c.

См. определение в файле fourier_series.c строка 129

◆ goertzel()

int goertzel ( double *  x,
int  n,
int *  ind,
int  k,
complex_t y 
)

Алгоритм Герцеля для расчета отдельных спектральных отсчетов дискретного преобразования Фурье вещественного сигнала x.


Данный алгоритм позволяет рассчитать k спектральных отсчетов n-точечного ДПФ, заданных вектором индексов ind.

Аргументы
[in]xУказатель на вектор вещественного входного сигнала.
Размер вектора [n x 1].

[in]nРазмер вектора входного сигнала.

[in]indУказатель на вектор индексов спектральных отсчетов для расчета которых будет использоваться алгоритм Герцеля.
Размер вектора [k x 1].

[in]kРазмер вектора индексов спектральных отсчетов ind.

[out]yУказатель на вектор спектральных отсчетов, соответствующих номерам ind.
Размер вектора [k x 1].
Память должна быть выделена.

Возвращает
RES_OK Функция выполнена успешно.
В противном случае код ошибки.
Заметки
Алгоритм Герцеля эффективен когда необходимо рассчитать несколько спектральных отсчетов сигнала большой длительности.
Однако, размер k вектора индексов ind может быть произвольным, в том числе больше длины сигнала n. В этом случае некоторые спектральные отсчеты будут повторяться, но это не повлечет за собой ошибки выполнения.
Значения индексов спектральных отсчетов ind также могут быть произвольными целыми, в том числе и отрицательными. В этом случае будут рассчитаны спектральные отсчеты с индексами по модулю n.
Автор
Бахурин Сергей. www.dsplib.org

См. определение в файле goertzel.c строка 29

◆ goertzel_cmplx()

int goertzel_cmplx ( complex_t x,
int  n,
int *  ind,
int  k,
complex_t y 
)

Алгоритм Герцеля для расчета отдельных спектральных отсчетов дискретного преобразования Фурье комплексного сигнала x.


Данный алгоритм позволяет рассчитать k спектральных отсчетов n-точечного ДПФ, заданных вектором индексов ind.

Аргументы
[in]xУказатель на вектор комплексного входного сигнала.
Размер вектора [n x 1].

[in]nРазмер вектора входного сигнала.

[in]indУказатель на вектор индексов спектральных отсчетов для расчета которых будет использоваться алгоритм Герцеля.
Размер вектора [k x 1].

[in]kРазмер вектора индексов спектральных отсчетов ind.

[out]yУказатель на вектор спектральных отсчетов, соответствующих номерам ind.
Размер вектора [k x 1].
Память должна быть выделена.

Возвращает
RES_OK Функция выполнена успешно.
В противном случае код ошибки.
Заметки
Алгоритм Герцеля эффективен когда необходимо рассчитать несколько спектральных отсчетов сигнала большой длительности.
Однако, размер k вектора индексов ind может быть произвольным, в том числе больше длины сигнала n. В этом случае некоторые спектральные отсчеты будут повторяться, но это не повлечет за собой ошибки выполнения.
Значения индексов спектральных отсчетов ind также могут быть произвольными целыми, в том числе и отрицательными. В этом случае будут рассчитаны спектральные отсчеты с индексами по модулю n.

Автор
Бахурин Сергей. www.dsplib.org

См. определение в файле goertzel.c строка 70