提升在前计算处理演算法应用於即时频谱分析范围的研究

1、提升在前計算處理演算法應用於即時頻譜分析範圍的研究Increasing the range of application for real-time spectrum analysis based on the algorithm of pre-calculation process執行期間：910801 920731計畫編號：NSC 91-2213-E-027-027主持人 ：嚴文方國立台北科技大學電子工程系教授7中文摘要即時FFT演算法的處理方式係在輸入資料陸續收到時，就開始進行可以運算的單元，由於在收到所有資料以前，已經完成很多單元的運算，所以確實可以提升傳統FFT的效率。但是對一個N點

2、的FFT而言，即時演算法在最後一個輸入資料收到後，會有(N-1)個乘法及2(N-1)個加法無法進行。作者已發展出一種所謂的在前計算法，可以將前述最後一個輸入資料收到後所需的乘法及加法各減為一半，以進一步提升計算效率。本計畫為擴大在前計算法的應用範圍，完成的工作有二。其一是瞭解在前計算法在已知的計算效率前提下，其可以工作的取樣頻率範圍為何。其二則是在維持既有的計算效率下，如欲提升其工作的頻率範圍，則在前計算法的演算法需如何修改，以及演算法修改的最終限制為何。AbstractReal-time FFT algorithm is developed on the consideration of s

3、aving the computational time of the conventional FFT if we simultaneously build some butterfly structures while the sampled input data coming in. Therefore, lots of computation can be processed before collecting all the input data. When this algorithm is used, however, complex multiplications and co

4、mplex additions cannot be accomplished until the last input data is collected. An algorithm pre-calculation process proposed by the author can reduce half of the arithmetic operations required by the real-time FFT algorithm when all the input data are received. For increasing the application capacit

5、y of the pre-calculation process, two major topics have been carried out in this research work：1to investigate the appropriate range of sampling frequency of the pre-calculation process in terms of the derived computational efficiency. 2 to consider the modification and the limit of the modification

6、 of the presented algorithm of pre-calculation process so that higher sampling frequency can still be acceptable without sacrificing the derived computational efficiency.1. IntroductionAfter the Fast Fourier Transform (FFT) proposed by Cooley and Tukey 1, various FFT algorithms 2 8 have been develop

7、ed for achieving the better efficiency of computation or the less complexity of structure. Real-time FFT algorithm 2, is developed on the consideration of saving the computational time of the conventional FFT if we simultaneously build some butterfly structure while the sampled input data coming in.

8、 However, when this algorithm is used, the butterfly modules in the last block at each stage cannot be accomplished until the last input data is collected. Fig.1 is an example of 8-point FFT to express the restriction of computation in the radix-2 real-time FFT algorithm. In Fig.1, the butterfly mod

9、ules illustrated by the solid lines represent computational branches that can be accomplished upon receipt of the first 7 input data. On the other hand, the butterfly modules with dotted lines in the last block of every stage represent computational branches that can not be processed due to the unco

10、llected last input data. For -point real-time FFT, the number of butterfly modules left to be accomplished after receiving all the input data will be. This means that complex multiplications and complex additions are still required when the last input data appears in the N-point real-time FFT algori

11、thm. The presented method pre-calculation process in this paper focuses on reducing the number of arithmetic operations left to be accomplished upon receipt of the last input data so as to further improve the efficiency of computation when real-time FFT algorithm is used. The results show that almos

12、t half of the arithmetic operations in the real-time FFT algorithm can be reduced by using the proposed pre-calculation process after all the input data are received. The deviation of output , , through the decimation in time FFT flow graph illustrated in Fig.1 in terms of the input data ,can be exp

13、ressed as eqn. (1)(1)When radix-2 real-time FFT algorithm is considered in Fig.1,every arithmetic operation, except and , in the 2nd of in eqn. (2) can not be processed before receipt of although the inputs , , and have already been received. Eqn. (2) is derived by the principle of moving out from t

14、he 2nd of in eqn. (1). In eqn. (2), the proposed pre-calculation process before receipt of ,in contrast to the restriction of computation of real-time FFT algorithm, can thus include the arithmetic operation in the 2nd as well as the addition of the first two s insince all the input data in the two

15、s are collected. (2)where When the concept of pre-calculation process in eqn. (2) is applied in real-time FFT of Fig.1, the arithmetic operations of the last butterfly module with dotted lines at stage 1 can actually be started right after receipt of if 0 is substituted for the data point .Consequen

16、tly, the process of derivation of in eqn. (2) based on pre-calculation real-time FFT can be composed of two steps as shown in Fig. 2. In step1, butterfly modules are all illustrated by soild lines with input point = 0 for representing the computational branches accomplished upon receipt of the first

17、 7 input data . After is collected, the result of multiplication with the consideration of the symmetry and periodicity properties of the weighting factor is always added to , the result of step1 for each of ,to form the step2. Now is easy from Fig. 2 to deduce that the derivation of the -pointbased

18、 on the proposed pre-calculation real-time FFT algorithm can be written as (3)It is easy to see that there are N/2 multiplications and N additions will be required in eqn. (3) for deriving the-point after is received. In comparison with real-time FFT algorithm, almost half of the number of arithmeti

19、c operations after collecting all the input data is required when pre-calculation real-time FFT algorithm is employed.Fig.1 8-point real-time FFTFig.2 8-point pre-calculation real-time FFT2. Relationships between and based on pre-calculation processDefinitions:Time for computing the results of step1

20、 ( i.e. the pre-calculation step) with input point.Time interval between receiving input data and ( i.e. ).If is moved out from the pre-calculation step, where , with input point . stands for the time of computing together with the results from the previous step after is received.It is clear from th

21、e definitions and eqn.(3) that is the necessary condition to avoid the delay of computation in step 2 when is received. This reveals that the highest sampling frequency can thus be decided without sacrificing the efficiency of pre-calculation process for every number of when. For pre-calculation pro

22、cess, if we go further on moving out from the pre-calculation step with the input data , the computational complexity in step 1 will be reduced, and eqn (2) can be rewritten as eqn. (4).(4) Step1 | Step2 | Step3 For -point pre-calculation FFT, eqn. (3) is rewritten as eqn. (5) when is moved out from

23、 step 1. (5) The highest frequency for each of with full efficiency of pre-calculation is then decided by .Theoretically, the for each of can be increased by moving out from step 1, because less arithmetic operations are required for deriving. The procedure of moving out from the pre-calculation ste

24、p can be continued until the certain input data with which can not be increased again. That is (6)and (7)where is the highest sampling frequency for all the situations of pre-calculation process based on the method of moving out .3. Discussion and conclusion Since the range of application for the re

25、al-time spectrum analysis highly depends on the sampling frequency, an experimental work has been done with P4 1.6G to investigate the relationships between and based on the condition of keeping the efficiency of pre-calculation process with the criterion of and eqn.(6). Results of are shown separat

26、ely with smaller number of ( from 8 to 128 ) in Fig.3 and larger number of ( from 256 to 4096 ) in Fig.4, respectively. The curve of fundamental pre-calculation process derived by moving out from step1 shows that the pre-calculation process has very wide range of application with about 200 at small

27、number of based on the system P4 1.6G. Then tends to gradually decrease to the very low frequency, which may not be useful in application, as is increasing from 8 towards 4096. When is moved out from the pre-calculation step, as expected, the curve is better than the curve in terms of the in both Fi

28、g.(3) and Fig.(4). In addition, the curve and the curve in Fig.(3) and Fig.(4), respectively, can be thought of as the best situations, in general, among all the curves. Further moving out beyond this stage will not benefit the , and may even decrease the as the curve shown in both figures. Conseque

29、ntly, and will be the in eqn. (7) for Fig.(3) and Fig. (4), respectively. Here we can conclude with the results of the two figures that the can be decided for every specific as far as the efficiency of pre-calculation is concerned. And the method of moving out from the pre-calculation step can gener

30、ally increase the range of application for real-time spectrum analysis. As for the consideration of when can be derived during the moving out process, it is really a matter depending on what kind of the signal processor is employed. N-1N-2N-3N-5N-7Fig.3 Relationships between and ( 8128 ) N-1N-2N-3N-

31、5N-7Fig.4 Relationships between and ( 256 4096 )Reference ：1 J.W. Cooley, J.W. Tukey, An algorithm for machine computation of complex Fourier series, Mathematics Computation, April 1965, 19, pp. 297-3012 Pei-chen Lo, Yu-yun Lee, Real-time implementation of the split-radix FFT, Elsevier Science, Signal Processing, 1998