How to position the twiddle factors in each stage while drawing the signal flow graph?
Dear Ann
Yes, that is a tricky problem when mixed radix FFTs are considered.
To understand that you need to know where the twiddle factors come from. Let's start with a single radix-2 FFT... For a radix-2 DIT FFT the idea is to split the samples into 2 sets in the time domain, the even numbered ones, x0, x2, x4, x6,... and the odd numbered ones, x1, x3, x5, x7,... Now think, what decides if the sample is even or odd in the original sequence? The answer is: the last digit in the binary counting: 000, 001, 010, 011, ... Then for the previous step you need to split the even of the even and the odd of the even (for the top half) and the even of the odd and the odd of the odd (for the bottom half). What decides? The penultimate digit in the binary counting, and so on. With a little thinking you get to the full digit reverse idea. For base 4, you need to take 2 digits at a time, but the overall idea is the same. Please see details on the paper attached for a mixed-radix (R-2 and R4) FFT. The full references are:
. “Real-time spectral analysis of Doppler signals using a digital signal processor and a microcomputer”. Schlindwein, F.S. and Evans, D.H, In: Physics in Medical Ultrasound II, chapter 15, pp.112-118. The Institute of Physical Sciences in Medicine, report N.57, 1988.
. “Spectral analysis of Doppler signals and computation of the normalized first moment in real time using a digital signal processor”, Schlindwein, F.S.; Smith, M.J. and Evans, D.H. - Medical & Biological Engineering & Computing, vol.26, pp. 228-232, 1988.
- Badges
- Science topic