18-07-2012, 11:23 AM
A Low-Cost, Low-Complexity, and Memory-Free Architecture of Novel Recursive DFT
Low-Cost, Low-Complexit.pdf (Size: 488.36 KB / Downloads: 28)
Abstract
A low-computational complexity and low-cost recursive
discrete Fourier transform (RDFT) design using the Chinese
remainder theorem is proposed in this brief. The proposed algorithm
reduces multiplications by 74% and additions by 73%
compared to the latest RDFT algorithms. For computing the 212-
and 106-point DFT coefficients, the proposed design can shorten
computing cycles by 47% compared with the latest architectures.
The hardware resources for the proposed design only require
2 multipliers and 12 adders. The coefficient read-only memory
storing the sine and cosine values can be reduced by 100% compared
with other recursive algorithms. Therefore, the proposed
algorithm is more suitable than other very large scale integration
realizations.
INTRODUCTION
THE discrete Fourier transform (DFT) has been widely
applied in the field of signal processing. Dual-tone multifrequency
(DTMF) approaches [1], [2] to the voice-over-packet
(VoP) network [3] use Goertzel’s algorithm [4] to compute
the interested frequency. To meet the International Telecommunications
Union frequency specifications [5], Felder et al.
[1] suggest using two different frame sizes for both the highgroup
(a frame size of 212) and low-group (a frame size of 106)
frequency specifications.
These architectures [6]–[11] for recursive DFT (RDFT) algorithms
have been completely developed and have the advantages
of high data throughput, low power use, and small
area requirement compared to digital-signal-processing-based
designs. Recently, Van and Yang [7] and Van et al. [8] have
proposed a high-performance and power-efficient very-largescale
integration (VLSI) architecture.
COMPARISON AND DISCUSSION
There are four performance indexes for comparisons of
RDFT algorithms: computational complexity, computing cycles,
hardware costs, and accuracy. Table I shows the number
of multiplications that the proposed algorithm requires, i.e.,
23 774 and 11 872 for the 212- and 106-point frame sizes,
respectively. The multiplications of the proposed algorithm can
be reduced to 74% less than others.
CONCLUSION
This brief has presented low-complexity low-cost fastcomputing
architecture for RDFT and IDFT algorithms. The proposed algorithm and architecture not only outperform previous
works but can also be implemented using simple hardware.
This design is suitable for DTMF detecting in VoP applications.