Public Types | Public Member Functions | Protected Attributes | Private Member Functions | Private Attributes | List of all members
SplitRadixComplexFft< Real > Class Template Reference
%Matrix and vector classes » Miscellaneous matrix/vector library functions and classes

#include <srfft.h>

Inheritance diagram for SplitRadixComplexFft< Real >:
Inheritance graph
[legend]
Collaboration diagram for SplitRadixComplexFft< Real >:
Collaboration graph
[legend]

Public Types

typedef MatrixIndexT Integer
 

Public Member Functions

 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 ()
 

Protected Attributes

std::vector< Real > temp_buffer_
 

Private Member Functions

void ComputeTables ()
 
void ComputeRecursive (Real *xr, Real *xi, Integer logn) const
 
void BitReversePermute (Real *x, Integer logn) const
 
SplitRadixComplexFft & operator= (const SplitRadixComplexFft< Real > &other)
 

Private Attributes

Integer N_
 
Integer logn_
 
Integer * brseed_
 
Real ** tab_
 

Detailed Description

template<typename Real>
class kaldi::SplitRadixComplexFft< Real >

Definition at line 48 of file srfft.h.

Member Typedef Documentation

◆ Integer

typedef MatrixIndexT Integer

Definition at line 50 of file srfft.h.

Constructor & Destructor Documentation

◆ SplitRadixComplexFft() [1/2]

SplitRadixComplexFft ( Integer  N)

Definition at line 35 of file srfft.cc.

Referenced by SplitRadixComplexFft< float >::SplitRadixComplexFft().

35  {
36  if ( (N & (N-1)) != 0 || N <= 1)
37  KALDI_ERR << "SplitRadixComplexFft called with invalid number of points "
38  << N;
39  N_ = N;
40  logn_ = 0;
41  while (N > 1) {
42  N >>= 1;
43  logn_ ++;
44  }
45  ComputeTables();
46 }
KALDI_ERR
#define KALDI_ERR
Definition: kaldi-error.h:147

◆ SplitRadixComplexFft() [2/2]

SplitRadixComplexFft ( const SplitRadixComplexFft< Real > &  other)

◆ ~SplitRadixComplexFft()

~SplitRadixComplexFft ( )

Definition at line 126 of file srfft.cc.

126  {
127  delete [] brseed_;
128  if (tab_ != NULL) {
129  for (MatrixIndexT i = 0; i < logn_-3; i++)
130  delete [] tab_[i];
131  delete [] tab_;
132  }
133 }
kaldi::MatrixIndexT
int32 MatrixIndexT
Definition: matrix-common.h:98

Member Function Documentation

◆ BitReversePermute()

void BitReversePermute ( Real *  x,
Integer  logn 
) const
private

Definition at line 185 of file srfft.cc.

185  {
186  MatrixIndexT i, j, lg2, n;
187  MatrixIndexT off, fj, gno, *brp;
188  Real tmp, *xp, *xq;
189 
190  lg2 = logn >> 1;
191  n = 1 << lg2;
192  if (logn & 1) lg2++;
193 
194  /* Unshuffling loop */
195  for (off = 1; off < n; off++) {
196  fj = n * brseed_[off]; i = off; j = fj;
197  tmp = x[i]; x[i] = x[j]; x[j] = tmp;
198  xp = &x[i];
199  brp = &(brseed_[1]);
200  for (gno = 1; gno < brseed_[off]; gno++) {
201  xp += n;
202  j = fj + *brp++;
203  xq = x + j;
204  tmp = *xp; *xp = *xq; *xq = tmp;
205  }
206  }
207 }
kaldi::MatrixIndexT
int32 MatrixIndexT
Definition: matrix-common.h:98
rnnlm::n
struct rnnlm::@11::@12 n

◆ Compute() [1/3]

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

Definition at line 136 of file srfft.cc.

Referenced by SplitRadixRealFft< float >::Compute(), SplitRadixRealFft< float >::SplitRadixRealFft(), kaldi::UnitTestSplitRadixComplexFft(), and kaldi::UnitTestSplitRadixComplexFft2().

136  {
137  if (!forward) { // reverse real and imaginary parts for complex FFT.
138  Real *tmp = xr;
139  xr = xi;
140  xi = tmp;
141  }
142  ComputeRecursive(xr, xi, logn_);
143  if (logn_ > 1) {
144  BitReversePermute(xr, logn_);
145  BitReversePermute(xi, logn_);
146  }
147 }
kaldi::SplitRadixComplexFft::BitReversePermute
void BitReversePermute(Real *x, Integer logn) const
Definition: srfft.cc:185
kaldi::SplitRadixComplexFft::ComputeRecursive
void ComputeRecursive(Real *xr, Real *xi, Integer logn) const
Definition: srfft.cc:211

◆ Compute() [2/3]

void Compute ( Real *  x,
bool  forward 
)

Definition at line 180 of file srfft.cc.

180  {
181  this->Compute(x, forward, &temp_buffer_);
182 }
kaldi::SplitRadixComplexFft::temp_buffer_
std::vector< Real > temp_buffer_
Definition: srfft.h:85
kaldi::SplitRadixComplexFft::Compute
void Compute(Real *xr, Real *xi, bool forward) const
Definition: srfft.cc:136

◆ Compute() [3/3]

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

Definition at line 150 of file srfft.cc.

151  {
152  KALDI_ASSERT(temp_buffer != NULL);
153  if (temp_buffer->size() != N_)
154  temp_buffer->resize(N_);
155  Real *temp_ptr = &((*temp_buffer)[0]);
156  for (MatrixIndexT i = 0; i < N_; i++) {
157  x[i] = x[i * 2]; // put the real part in the first half of x.
158  temp_ptr[i] = x[i * 2 + 1]; // put the imaginary part in temp_buffer.
159  }
160  // copy the imaginary part back to the second half of x.
161  memcpy(static_cast<void*>(x + N_),
162  static_cast<void*>(temp_ptr),
163  sizeof(Real) * N_);
164 
165  Compute(x, x + N_, forward);
166  // Now change the format back to interleaved.
167  memcpy(static_cast<void*>(temp_ptr),
168  static_cast<void*>(x + N_),
169  sizeof(Real) * N_);
170  for (MatrixIndexT i = N_-1; i > 0; i--) { // don't include 0,
171  // in case MatrixIndexT is unsigned, the loop would not terminate.
172  // Treat it as a special case.
173  x[i*2] = x[i];
174  x[i*2 + 1] = temp_ptr[i];
175  }
176  x[1] = temp_ptr[0]; // special case of i = 0.
177 }
kaldi::MatrixIndexT
int32 MatrixIndexT
Definition: matrix-common.h:98
kaldi::SplitRadixComplexFft::Compute
void Compute(Real *xr, Real *xi, bool forward) const
Definition: srfft.cc:136
KALDI_ASSERT
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:185

◆ ComputeRecursive()

void ComputeRecursive ( Real *  xr,
Real *  xi,
Integer  logn 
) const
private

Definition at line 211 of file srfft.cc.

211  {
212 
213  MatrixIndexT m, m2, m4, m8, nel, n;
214  Real *xr1, *xr2, *xi1, *xi2;
215  Real *cn = nullptr, *spcn = nullptr, *smcn = nullptr, *c3n = nullptr,
216  *spc3n = nullptr, *smc3n = nullptr;
217  Real tmp1, tmp2;
218  Real sqhalf = M_SQRT1_2;
219 
220  /* Check range of logn */
221  if (logn < 0)
222  KALDI_ERR << "Error: logn is out of bounds in SRFFT";
223 
224  /* Compute trivial cases */
225  if (logn < 3) {
226  if (logn == 2) { /* length m = 4 */
227  xr2 = xr + 2;
228  xi2 = xi + 2;
229  tmp1 = *xr + *xr2;
230  *xr2 = *xr - *xr2;
231  *xr = tmp1;
232  tmp1 = *xi + *xi2;
233  *xi2 = *xi - *xi2;
234  *xi = tmp1;
235  xr1 = xr + 1;
236  xi1 = xi + 1;
237  xr2++;
238  xi2++;
239  tmp1 = *xr1 + *xr2;
240  *xr2 = *xr1 - *xr2;
241  *xr1 = tmp1;
242  tmp1 = *xi1 + *xi2;
243  *xi2 = *xi1 - *xi2;
244  *xi1 = tmp1;
245  xr2 = xr + 1;
246  xi2 = xi + 1;
247  tmp1 = *xr + *xr2;
248  *xr2 = *xr - *xr2;
249  *xr = tmp1;
250  tmp1 = *xi + *xi2;
251  *xi2 = *xi - *xi2;
252  *xi = tmp1;
253  xr1 = xr + 2;
254  xi1 = xi + 2;
255  xr2 = xr + 3;
256  xi2 = xi + 3;
257  tmp1 = *xr1 + *xi2;
258  tmp2 = *xi1 + *xr2;
259  *xi1 = *xi1 - *xr2;
260  *xr2 = *xr1 - *xi2;
261  *xr1 = tmp1;
262  *xi2 = tmp2;
263  return;
264  }
265  else if (logn == 1) { /* length m = 2 */
266  xr2 = xr + 1;
267  xi2 = xi + 1;
268  tmp1 = *xr + *xr2;
269  *xr2 = *xr - *xr2;
270  *xr = tmp1;
271  tmp1 = *xi + *xi2;
272  *xi2 = *xi - *xi2;
273  *xi = tmp1;
274  return;
275  }
276  else if (logn == 0) return; /* length m = 1 */
277  }
278 
279  /* Compute a few constants */
280  m = 1 << logn; m2 = m / 2; m4 = m2 / 2; m8 = m4 /2;
281 
282 
283  /* Step 1 */
284  xr1 = xr; xr2 = xr1 + m2;
285  xi1 = xi; xi2 = xi1 + m2;
286  for (n = 0; n < m2; n++) {
287  tmp1 = *xr1 + *xr2;
288  *xr2 = *xr1 - *xr2;
289  xr2++;
290  *xr1++ = tmp1;
291  tmp2 = *xi1 + *xi2;
292  *xi2 = *xi1 - *xi2;
293  xi2++;
294  *xi1++ = tmp2;
295  }
296 
297  /* Step 2 */
298  xr1 = xr + m2; xr2 = xr1 + m4;
299  xi1 = xi + m2; xi2 = xi1 + m4;
300  for (n = 0; n < m4; n++) {
301  tmp1 = *xr1 + *xi2;
302  tmp2 = *xi1 + *xr2;
303  *xi1 = *xi1 - *xr2;
304  xi1++;
305  *xr2++ = *xr1 - *xi2;
306  *xr1++ = tmp1;
307  *xi2++ = tmp2;
308  // xr1++; xr2++; xi1++; xi2++;
309  }
310 
311  /* Steps 3 & 4 */
312  xr1 = xr + m2; xr2 = xr1 + m4;
313  xi1 = xi + m2; xi2 = xi1 + m4;
314  if (logn >= 4) {
315  nel = m4 - 2;
316  cn = tab_[logn-4]; spcn = cn + nel; smcn = spcn + nel;
317  c3n = smcn + nel; spc3n = c3n + nel; smc3n = spc3n + nel;
318  }
319  xr1++; xr2++; xi1++; xi2++;
320  // xr1++; xi1++;
321  for (n = 1; n < m4; n++) {
322  if (n == m8) {
323  tmp1 = sqhalf * (*xr1 + *xi1);
324  *xi1 = sqhalf * (*xi1 - *xr1);
325  *xr1 = tmp1;
326  tmp2 = sqhalf * (*xi2 - *xr2);
327  *xi2 = -sqhalf * (*xr2 + *xi2);
328  *xr2 = tmp2;
329  } else {
330  tmp2 = *cn++ * (*xr1 + *xi1);
331  tmp1 = *spcn++ * *xr1 + tmp2;
332  *xr1 = *smcn++ * *xi1 + tmp2;
333  *xi1 = tmp1;
334  tmp2 = *c3n++ * (*xr2 + *xi2);
335  tmp1 = *spc3n++ * *xr2 + tmp2;
336  *xr2 = *smc3n++ * *xi2 + tmp2;
337  *xi2 = tmp1;
338  }
339  xr1++; xr2++; xi1++; xi2++;
340  }
341 
342  /* Call ssrec again with half DFT length */
343  ComputeRecursive(xr, xi, logn-1);
344 
345  /* Call ssrec again twice with one quarter DFT length.
346  Constants have to be recomputed, because they are static! */
347  // m = 1 << logn; m2 = m / 2;
348  ComputeRecursive(xr + m2, xi + m2, logn - 2);
349  // m = 1 << logn;
350  m4 = 3 * (m / 4);
351  ComputeRecursive(xr + m4, xi + m4, logn - 2);
352 }
M_SQRT1_2
#define M_SQRT1_2
Definition: kaldi-math.h:56
kaldi::SplitRadixComplexFft::ComputeRecursive
void ComputeRecursive(Real *xr, Real *xi, Integer logn) const
Definition: srfft.cc:211
kaldi::MatrixIndexT
int32 MatrixIndexT
Definition: matrix-common.h:98
rnnlm::n
struct rnnlm::@11::@12 n
KALDI_ERR
#define KALDI_ERR
Definition: kaldi-error.h:147

◆ ComputeTables()

void ComputeTables ( )
private

Definition at line 75 of file srfft.cc.

75  {
76  MatrixIndexT imax, lg2, i, j;
77  MatrixIndexT m, m2, m4, m8, nel, n;
78  Real *cn, *spcn, *smcn, *c3n, *spc3n, *smc3n;
79  Real ang, c, s;
80 
81  lg2 = logn_ >> 1;
82  if (logn_ & 1) lg2++;
83  brseed_ = new MatrixIndexT[1 << lg2];
84  brseed_[0] = 0;
85  brseed_[1] = 1;
86  for (j = 2; j <= lg2; j++) {
87  imax = 1 << (j - 1);
88  for (i = 0; i < imax; i++) {
89  brseed_[i] <<= 1;
90  brseed_[i + imax] = brseed_[i] + 1;
91  }
92  }
93 
94  if (logn_ < 4) {
95  tab_ = NULL;
96  } else {
97  tab_ = new Real* [logn_-3];
98  for (i = logn_; i>=4 ; i--) {
99  /* Compute a few constants */
100  m = 1 << i; m2 = m / 2; m4 = m2 / 2; m8 = m4 /2;
101 
102  /* Allocate memory for tables */
103  nel = m4 - 2;
104 
105  tab_[i-4] = new Real[6*nel];
106 
107  /* Initialize pointers */
108  cn = tab_[i-4]; spcn = cn + nel; smcn = spcn + nel;
109  c3n = smcn + nel; spc3n = c3n + nel; smc3n = spc3n + nel;
110 
111  /* Compute tables */
112  for (n = 1; n < m4; n++) {
113  if (n == m8) continue;
114  ang = n * M_2PI / m;
115  c = std::cos(ang); s = std::sin(ang);
116  *cn++ = c; *spcn++ = - (s + c); *smcn++ = s - c;
117  ang = 3 * n * M_2PI / m;
118  c = std::cos(ang); s = std::sin(ang);
119  *c3n++ = c; *spc3n++ = - (s + c); *smc3n++ = s - c;
120  }
121  }
122  }
123 }
kaldi::MatrixIndexT
int32 MatrixIndexT
Definition: matrix-common.h:98
rnnlm::n
struct rnnlm::@11::@12 n
M_2PI
#define M_2PI
Definition: kaldi-math.h:52

◆ operator=()

SplitRadixComplexFft& operator= ( const SplitRadixComplexFft< Real > &  other)
private

Referenced by SplitRadixRealFft< float >::SplitRadixRealFft().

Member Data Documentation

◆ brseed_

Integer* brseed_
private

Definition at line 94 of file srfft.h.

Referenced by SplitRadixComplexFft< float >::SplitRadixComplexFft().

◆ logn_

Integer logn_
private

Definition at line 92 of file srfft.h.

Referenced by SplitRadixComplexFft< float >::SplitRadixComplexFft().

◆ N_

Integer N_
private

Definition at line 91 of file srfft.h.

Referenced by SplitRadixComplexFft< float >::SplitRadixComplexFft().

◆ tab_

Real** tab_
private

Definition at line 98 of file srfft.h.

Referenced by SplitRadixComplexFft< float >::SplitRadixComplexFft().

◆ temp_buffer_

std::vector<Real> temp_buffer_
protected

Definition at line 85 of file srfft.h.

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