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 
)

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


Функция рассчитывает \form#8-точечное  дискретное преобразование Фурье 
вещественного сигнала \form#9, \form#10.<BR>

\[ 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].
Память должна быть выделена.

\return
`RES_OK`        если ДПФ рассчитана успешно. <BR>
                В противном случае \ref ERROR_CODE_GROUP "код ошибки".

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

\include dft_test.c

Результат работы программы:
    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
\author
    Бахурин Сергей.                                                         
    www.dsplib.org 
\note
Данная функция выполняет расчет ДПФ наивным методом 
и требует \form#16 комплексных умножений.<BR>
Для увеличения скорости расчета рекомендуется 
использовать алгоритмы быстрого преобразования Фурье.

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

◆ dft_cmplx()

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

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


Функция рассчитывает \form#8-точечное  дискретное преобразование Фурье 
комплексного сигнала \form#9, \form#10.<BR>

\[ 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].
Память должна быть выделена.

\return
`RES_OK`        если ДПФ рассчитана успешно. <BR>
                В противном случае \ref ERROR_CODE_GROUP "код ошибки".




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

\include dft_cmplx_test.c

Результат работы программы:
    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 строка 197

◆ fft_free()

void fft_free ( fft_t pfft)

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


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

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

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

◆ 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 строка 362

◆ 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`.

\param[in]  x               Указатель на вектор вещественного входного сигнала.<BR>
                                    Размер вектора `[n x 1]`.<BR><BR>

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

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

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


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

\return
            `RES_OK`        Функция выполнена успешно. <BR>
                        В противном случае \ref ERROR_CODE_GROUP "код ошибки".<BR>

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


\author
    Бахурин Сергей.
    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`.

\param[in]  x               Указатель на вектор комплексного входного сигнала.<BR>
                                    Размер вектора `[n x 1]`.<BR><BR>

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

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

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


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

\return
            `RES_OK`        Функция выполнена успешно. <BR>
                        В противном случае \ref ERROR_CODE_GROUP "код ошибки".<BR>

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


\author
    Бахурин Сергей.
    www.dsplib.org  

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