A new radix-3 fast algorithm for computing the DST-II

Author

Wu, Yiquan ; Zhu, Zhaoda

Author_Institution

Dept. of Electron. Eng., Nanjing Univ. of Aeronaut. & Astronaut., China

Volume

1

fYear

1995

Firstpage

324

Abstract

In this paper a new radix-3 fast algorithm for the length-3^m Discrete Sine Transform (DST-II) is proposed, to further extend the applicability of the Fast Sine Transform (FST) algorithm. First, the basic 3-point DST is considered. Then, the formulae of the new radix-3 FST algorithm are derived. Next, a block diagram of the radix-3 FST algorithm is shown and the signal flowgraph for length-3² FST is given to illustrate the proposed algorithm. Finally, the computational complexity is analysed. The proposed algorithm requires arithmetic and allows in-place computation. The simple and regular structure makes it easy to implement. One can compute effectively the length-2¹·3^m DST-II using this length-3^m algorithm together with the existing length-2¹ algorithm by prime factor decomposition

Keywords

computational complexity; data compression; digital arithmetic; filtering theory; image coding; signal flow graphs; transforms; DST-II; computational complexity; discrete sine transform; fast sine transform algorithm; in-place computation; prime factor decomposition; radix-3 fast algorithm; signal flowgraph; Adaptive filters; Algorithm design and analysis; Arithmetic; Computational complexity; Costs; Data compression; Discrete transforms; Equations; Image coding;

fLanguage

English

Publisher

ieee

Conference_Titel

Aerospace and Electronics Conference, 1995. NAECON 1995., Proceedings of the IEEE 1995 National

ISSN

0547-3578

Print_ISBN

0-7803-2666-0

Type

conf

DOI

10.1109/NAECON.1995.521959

Filename

521959