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

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

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 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. Подробнее...
 

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

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

Функции

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 $ комплексных умножений.
Для увеличения скорости расчета рекомендуется использовать алгоритмы быстрого преобразования Фурье.
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 $ комплексных умножений.
Для увеличения скорости расчета рекомендуется использовать алгоритмы быстрого преобразования Фурье.
int fft_create ( fft_t pfft,
int  n 
)

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


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

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

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

Заметки
Некоторые компиляторы при создании структуры не обнуляют ее содержимое. Поэтому рекомендуется произвести обнуление структуры после ее объявления:
1 fft_t pfft; // объявляем объект fft_t
2 int n = 64; // Размер БПФ
3 
4 // обнуляем все поля и указатели.
5 // Данные шаг рекомендуется ввиду того, что некоторые
6 // компиляторы при создании переменной не инициализируют ее нулем.
7 memset(&pfft, 0, sizeof(fft_t));
8 
9 int err;
10 
11 //создаем объект для 64-точечного БПФ
12 err = fft_create(&pfft, n);
13 
14 // .....
15 
16 //очистить память объекта БПФ
17 fft_free(&pfft);
Перед выходом из программы выделенную в структуре память необходимо очистить функцией fft_free .
Автор
Бахурин Сергей. www.dsplib.org
void fft_free ( fft_t pfft)

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


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

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