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

Функции

int dft (double *x, int n, complex_t *y)
 Дискретное преобразование Фурье вещественного сигнала. Подробнее...
 
int dft_cmplx (complex_t *x, int n, 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. Подробнее...
 

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

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

Функции

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) \exp \left( -j \frac{2\pi}{n} m 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 если ДПФ рассчитана успешно.
В противном случае код ошибки:
Автор
Бахурин Сергей. www.dsplib.org
Заметки
Данная функция выполняет расчет ДПФ наивным методом и требует $ n^2 $ комплексных умножений.
Для увеличения скорости расчета рекомендуется использовать алгоритмы быстрого преобразования Фурье.
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) \exp \left( -j \frac{2\pi}{n} m 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 если ДПФ рассчитана успешно.
В противном случае код ошибки:
Автор
Бахурин Сергей. www.dsplib.org
Заметки
Данная функция выполняет расчет ДПФ наивным методом и требует $ n^2 $ комплексных умножений.
Для увеличения скорости расчета рекомендуется использовать алгоритмы быстрого преобразования Фурье.
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
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