SplitRadixRealFft< Real > Class Template Reference

`#include <srfft.h>`

Inheritance diagram for SplitRadixRealFft< Real >:
Collaboration diagram for SplitRadixRealFft< Real >:

## Public Member Functions

void Compute (Real *x, bool forward)
If forward == true, this function transforms from a sequence of N real points to its complex fourier transform; otherwise it goes in the reverse direction. More...

void Compute (Real *x, bool forward, std::vector< Real > *temp_buffer) const
This is as the other Compute() function, but it is a const version that uses a user-supplied buffer. More...

## Private Member Functions

Private Member Functions inherited from SplitRadixComplexFft< Real >

void Compute (Real *xr, Real *xi, bool forward) const

void Compute (Real *x, bool forward)

void Compute (Real *x, bool forward, std::vector< Real > *temp_buffer) const

## Private Attributes

int N_

Private Attributes inherited from SplitRadixComplexFft< Real >
std::vector< Real > temp_buffer_

Private Types inherited from SplitRadixComplexFft< Real >
typedef MatrixIndexT Integer

## Detailed Description

### template<typename Real> class kaldi::SplitRadixRealFft< Real >

Definition at line 105 of file srfft.h.

## Constructor & Destructor Documentation

inline

Definition at line 107 of file srfft.h.

107  : // will fail unless N>=4 and N is a power of 2.
108  SplitRadixComplexFft<Real> (N/2), N_(N) { }

inline

Definition at line 111 of file srfft.h.

111  :

## ◆ Compute() [1/2]

 void Compute ( Real * x, bool forward )

If forward == true, this function transforms from a sequence of N real points to its complex fourier transform; otherwise it goes in the reverse direction.

If you call it in the forward and then reverse direction and multiply by 1.0/N, you will get back the original data. The interpretation of the complex-FFT data is as follows: the array is a sequence of complex numbers C_n of length N/2 with (real, im) format, i.e. [real0, real_{N/2}, real1, im1, real2, im2, real3, im3, ...].

Definition at line 356 of file srfft.cc.

356  {
357  Compute(data, forward, &this->temp_buffer_);
358 }
std::vector< Real > temp_buffer_
Definition: srfft.h:85
void Compute(Real *x, bool forward)
If forward == true, this function transforms from a sequence of N real points to its complex fourier ...
Definition: srfft.cc:356

## ◆ Compute() [2/2]

 void Compute ( Real * x, bool forward, std::vector< Real > * temp_buffer ) const

This is as the other Compute() function, but it is a const version that uses a user-supplied buffer.

Definition at line 364 of file srfft.cc.

365  {
366  MatrixIndexT N = N_, N2 = N/2;
367  KALDI_ASSERT(N%2 == 0);
368  if (forward) // call to base class
370
371  Real rootN_re, rootN_im; // exp(-2pi/N), forward; exp(2pi/N), backward
372  int forward_sign = forward ? -1 : 1;
373  ComplexImExp(static_cast<Real>(M_2PI/N *forward_sign), &rootN_re, &rootN_im);
374  Real kN_re = -forward_sign, kN_im = 0.0; // exp(-2pik/N), forward; exp(-2pik/N), backward
375  // kN starts out as 1.0 for forward algorithm but -1.0 for backward.
376  for (MatrixIndexT k = 1; 2*k <= N2; k++) {
377  ComplexMul(rootN_re, rootN_im, &kN_re, &kN_im);
378
379  Real Ck_re, Ck_im, Dk_re, Dk_im;
380  // C_k = 1/2 (B_k + B_{N/2 - k}^*) :
381  Ck_re = 0.5 * (data[2*k] + data[N - 2*k]);
382  Ck_im = 0.5 * (data[2*k + 1] - data[N - 2*k + 1]);
383  // re(D_k)= 1/2 (im(B_k) + im(B_{N/2-k})):
384  Dk_re = 0.5 * (data[2*k + 1] + data[N - 2*k + 1]);
385  // im(D_k) = -1/2 (re(B_k) - re(B_{N/2-k}))
386  Dk_im =-0.5 * (data[2*k] - data[N - 2*k]);
387  // A_k = C_k + 1^(k/N) D_k:
388  data[2*k] = Ck_re; // A_k <-- C_k
389  data[2*k+1] = Ck_im;
390  // now A_k += D_k 1^(k/N)
391  ComplexAddProduct(Dk_re, Dk_im, kN_re, kN_im, &(data[2*k]), &(data[2*k+1]));
392
393  MatrixIndexT kdash = N2 - k;
394  if (kdash != k) {
395  // Next we handle the index k' = N/2 - k. This is necessary
396  // to do now, to avoid invalidating data that we will later need.
397  // The quantities C_{k'} and D_{k'} are just the conjugates of C_k
398  // and D_k, so the equations are simple modifications of the above,
399  // replacing Ck_im and Dk_im with their negatives.
400  data[2*kdash] = Ck_re; // A_k' <-- C_k'
401  data[2*kdash+1] = -Ck_im;
402  // now A_k' += D_k' 1^(k'/N)
403  // We use 1^(k'/N) = 1^((N/2 - k) / N) = 1^(1/2) 1^(-k/N) = -1 * (1^(k/N))^*
404  // so it's the same as 1^(k/N) but with the real part negated.
405  ComplexAddProduct(Dk_re, -Dk_im, -kN_re, kN_im, &(data[2*kdash]), &(data[2*kdash+1]));
406  }
407  }
408
409  { // Now handle k = 0.
410  // In simple terms: after the complex fft, data[0] becomes the sum of real
411  // parts input[0], input[2]... and data[1] becomes the sum of imaginary
412  // pats input[1], input[3]...
413  // "zeroth" [A_0] is just the sum of input[0]+input[1]+input[2]..
414  // and "n2th" [A_{N/2}] is input[0]-input[1]+input[2]... .
415  Real zeroth = data[0] + data[1],
416  n2th = data[0] - data[1];
417  data[0] = zeroth;
418  data[1] = n2th;
419  if (!forward) {
420  data[0] /= 2;
421  data[1] /= 2;
422  }
423  }
424  if (!forward) { // call to base class
426  for (MatrixIndexT i = 0; i < N; i++)
427  data[i] *= 2.0;
428  // This is so we get a factor of N increase, rather than N/2 which we would
429  // otherwise get from [ComplexFft, forward] + [ComplexFft, backward] in dimension N/2.
430  // It's for consistency with our normal FFT convensions.
431  }
432 }
int32 MatrixIndexT
Definition: matrix-common.h:98
void Compute(Real *xr, Real *xi, bool forward) const
Definition: srfft.cc:136
void ComplexAddProduct(const Real &a_re, const Real &a_im, const Real &b_re, const Real &b_im, Real *c_re, Real *c_im)
ComplexMul implements, inline, the complex operation c += (a * b).
void ComplexMul(const Real &a_re, const Real &a_im, Real *b_re, Real *b_im)
ComplexMul implements, inline, the complex multiplication b *= a.
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:185
#define M_2PI
Definition: kaldi-math.h:52
void ComplexImExp(Real x, Real *a_re, Real *a_im)
ComplexImExp implements a <– exp(i x), inline.