SplitRadixRealFft< Real > Class Template Reference

#include <srfft.h>

Inheritance diagram for SplitRadixRealFft< Real >:

Collaboration diagram for SplitRadixRealFft< Real >:

Public Member Functions
	SplitRadixRealFft (MatrixIndexT N)
	SplitRadixRealFft (const SplitRadixRealFft< Real > &other)
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
SplitRadixRealFft &	operator= (const SplitRadixRealFft< Real > &other)
Private Member Functions inherited from SplitRadixComplexFft< Real >
	SplitRadixComplexFft (Integer N)
	SplitRadixComplexFft (const SplitRadixComplexFft &other)
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
	~SplitRadixComplexFft ()

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

Additional Inherited Members
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

SplitRadixRealFft() [1/2]

SplitRadixRealFft ( MatrixIndexT  N )

inline

Definition at line 107 of file srfft.h.

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

SplitRadixRealFft() [2/2]

SplitRadixRealFft ( const SplitRadixRealFft< Real > &  other )

inline

Definition at line 111 of file srfft.h.

                                                         :
      SplitRadixComplexFft<Real>(other), N_(other.N_) { }

Member Function Documentation

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.

Referenced by kaldi::FFTbasedBlockConvolveSignals(), kaldi::FFTbasedConvolveSignals(), kaldi::UnitTestSplitRadixRealFft(), and kaldi::UnitTestSplitRadixRealFftSpeed().

                                                              {
  Compute(data, forward, &this->temp_buffer_);
}

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.

                                                                          {
  MatrixIndexT N = N_, N2 = N/2;
  KALDI_ASSERT(N%2 == 0);
  if (forward) // call to base class
    SplitRadixComplexFft<Real>::Compute(data, true, temp_buffer);

  Real rootN_re, rootN_im;  // exp(-2pi/N), forward; exp(2pi/N), backward
  int forward_sign = forward ? -1 : 1;
  ComplexImExp(static_cast<Real>(M_2PI/N *forward_sign), &rootN_re, &rootN_im);
  Real kN_re = -forward_sign, kN_im = 0.0;  // exp(-2pik/N), forward; exp(-2pik/N), backward
  // kN starts out as 1.0 for forward algorithm but -1.0 for backward.
  for (MatrixIndexT k = 1; 2*k <= N2; k++) {
    ComplexMul(rootN_re, rootN_im, &kN_re, &kN_im);

    Real Ck_re, Ck_im, Dk_re, Dk_im;
    // C_k = 1/2 (B_k + B_{N/2 - k}^*) :
    Ck_re = 0.5 * (data[2*k] + data[N - 2*k]);
    Ck_im = 0.5 * (data[2*k + 1] - data[N - 2*k + 1]);
    // re(D_k)= 1/2 (im(B_k) + im(B_{N/2-k})):
    Dk_re = 0.5 * (data[2*k + 1] + data[N - 2*k + 1]);
    // im(D_k) = -1/2 (re(B_k) - re(B_{N/2-k}))
    Dk_im =-0.5 * (data[2*k] - data[N - 2*k]);
    // A_k = C_k + 1^(k/N) D_k:
    data[2*k] = Ck_re;  // A_k <-- C_k
    data[2*k+1] = Ck_im;
    // now A_k += D_k 1^(k/N)
    ComplexAddProduct(Dk_re, Dk_im, kN_re, kN_im, &(data[2*k]), &(data[2*k+1]));

    MatrixIndexT kdash = N2 - k;
    if (kdash != k) {
      // Next we handle the index k' = N/2 - k.  This is necessary
      // to do now, to avoid invalidating data that we will later need.
      // The quantities C_{k'} and D_{k'} are just the conjugates of C_k
      // and D_k, so the equations are simple modifications of the above,
      // replacing Ck_im and Dk_im with their negatives.
      data[2*kdash] = Ck_re;  // A_k' <-- C_k'
      data[2*kdash+1] = -Ck_im;
      // now A_k' += D_k' 1^(k'/N)
      // We use 1^(k'/N) = 1^((N/2 - k) / N) = 1^(1/2) 1^(-k/N) = -1 * (1^(k/N))^*
      // so it's the same as 1^(k/N) but with the real part negated.
      ComplexAddProduct(Dk_re, -Dk_im, -kN_re, kN_im, &(data[2*kdash]), &(data[2*kdash+1]));
    }
  }

  {  // Now handle k = 0.
    // In simple terms: after the complex fft, data[0] becomes the sum of real
    // parts input[0], input[2]... and data[1] becomes the sum of imaginary
    // pats input[1], input[3]...
    // "zeroth" [A_0] is just the sum of input[0]+input[1]+input[2]..
    // and "n2th" [A_{N/2}] is input[0]-input[1]+input[2]... .
    Real zeroth = data[0] + data[1],
        n2th = data[0] - data[1];
    data[0] = zeroth;
    data[1] = n2th;
    if (!forward) {
      data[0] /= 2;
      data[1] /= 2;
    }
  }
  if (!forward) {  // call to base class
    SplitRadixComplexFft<Real>::Compute(data, false, temp_buffer);
    for (MatrixIndexT i = 0; i < N; i++)
      data[i] *= 2.0;
    // This is so we get a factor of N increase, rather than N/2 which we would
    // otherwise get from [ComplexFft, forward] + [ComplexFft, backward] in dimension N/2.
    // It's for consistency with our normal FFT convensions.
  }
}

operator=()

SplitRadixRealFft& operator= ( const SplitRadixRealFft< Real > &  other )

private

Member Data Documentation

N_

int N_

private

Definition at line 131 of file srfft.h.

---

The documentation for this class was generated from the following files:

• matrix/srfft.h
• matrix/srfft.cc