TW201017529A - Computation and addressing method of a eneral sized memory-based FFT processor - Google Patents

Abstract

For a large size FFT computation, the present invention decompose it into several smaller sizes FFT by decomposition equation and then transform the original index from one dimension into multi-dimension vector. By controlling the index vector, the present invention could distribute the input data into different memory banks such that both the in-place policy for computation and the multi-bank memory for high-radix structure could be supported simultaneously without memory conflict. Besides, in order to keep memory conflict-free when the in-place policy is also adopted for I/O data, the present invention reverse the decompose order of FFT to satisfy the vector reverse behavior. The proposed approach can minimize the area and reduce the necessary clock rate effectively for general sized memory-based FFT processor design. Further, the present invention applies the proposed to the 3780-point DFT processor for the Chinese DTV application. Compared with all the prior arts, the present invention only needs 2N words memory to achieve the in order I/O data requirement for continuous data flow. However, all the current patents need at least 3N words memory to achieve this system requirement. Here, N is the DFT size, 3780.

Description

201017529 IX. Description of the Invention: [Technical Field] The present invention relates to a fast Fourier transform calculation and addressing method and a memory-based arbitrary point forward/reverse fast Fourier transform processor design using the same. The memory-based discrete fast Fourier transform processor design for any number of points can effectively reduce the processor area and the required operating clock. [Prior Art] Φ According to the prior art of the fast Fourier transform calculation and addressing method of the present invention and the memory-based forward/reverse fast Fourier transform processor using the method, the disadvantages are as follows: (1) Since US Patent No. 4,477,878 is called "Discrete Fourier transform with non-tumbled output", it cannot support multi-bank memory structure. Therefore, for base r (radix-r) calculation, it is necessary. There are r clock cycles to read data from memory or write beta-completed data back into memory. This will cause the FFT to require more clock cycles in the calculation process and for immediate application. Higher clock speed. The present invention can read or write a r-pen data such as a base in a clock cycle by supporting multi-memory addressing without a memory access conflict. Solving the problems of the prior art. (2) U.S. Patent No. 5,091,875 is entitled "Fast Fourier transform (FFT) addressing apparatus and method", U.S. Patent Publication No. 2006 0253514 is called "Memory-based Fast Fourier Transform device" and academic paper L. G. 6 201017529

Johnson "Conflict free memory addressing for dedicated FFT hardware, M IEEE Trans. Circuits Syst. II, Analog Digit. Signal Process., vol. 39, no. 5, pp. 312-316, May 1992, etc., all support only fixed The base r, therefore, can only be applied to FFTs with N = rn size. If considering the 3780-point FFT applied to Chinese digital TV or the 3072-point FFT of PLC application, the above two prior techniques cannot be operated. However, the present invention can support the mixing of any base r. Therefore, it can be used in FFT applications of any size. (3) US Patent No. 7062523 named "Method for efficient computing a fast Fourier transform" only supports fixed bases. r, therefore can not support applications such as Chinese DTV or PLC. In addition, he can't support multi-bank memory structure, which requires r clock cycles to access data from memory during radix-r operations. Therefore, a higher clock is required than the processor using the multi-memory architecture to complete the FFT calculation. In addition to supporting the variable base of FFT applications of any size, the present invention supports multiple memory architectures to reduce the required clock without creating memory access violations. (4) US Patent No. 7, 164, 723 entitled "Modulation apparatus using mixed-radix fast Fourier transform", and paper BG Jo, and Μ. H. Sunwoo, "New continuous-flow mixed-radix (CFMR) FFT processor Using novel in-place strategy, '' IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 52, ηο·5, pp. 911-919, May 2005 only for the base 2/4 hybrid 201017529 algorithm ( Algorithm) 'The FFT that can only work at N=2n size cannot be applied to other sizes of FFT applications such as n=3780 China DTV. 'The present invention can support any mixed base number' so that the above requirements can be met. In addition, for longer processor designs such as 8192, the present invention allows the processor design to be more flexible, as the present invention can support algorithms larger than base 4. (5) US Patent Publication No. 20080025199 A possible decomposition of 3780 is proposed for "Method and device for high throughput n-point forward and • inverse fast Fourier transform", for example, 3780 =

3x3x3x2x2x5x7. It implements an FFT module for each small point in the MDC architecture to reduce the larger internal registers of some of the Chinese patents mentioned later. However, since this method requires an operation for each module in one clock cycle, a large amount of hardware is required. In addition, in actual system applications, it is necessary to output data sequentially, but the output of this patent is not output in order, so some problems remain unresolved. (6) Chinese Patent No. 01140060.9 "3780-point discrete Fourier transform spring processor system and its structure", Chinese Patent No. 03107204. 6 name "Multi-carrier system with 3780 IDFT/DFT processor and its method" , Chinese Patent Publication No. 200410090873.2 name "3780 point discrete Fourier transform using upsampling processing method", Chinese Patent Publication No. 200610104144.7 name "3780 point discrete Fourier transform processor" and Chinese patent publication number 200710044716. 1 name "pipeline structure 3780" The above-mentioned patents such as the point fast Fourier transform processor can perform 3780 points of an FFT processor with a pipelined architecture, and the proposed architecture requires a large amount of scratchpads or memory to rearrange the data. . In addition, for the actual system application requirements, sequential input and output data and support for continuous data flow are all necessary. In order to achieve this, the Chinese patent number 011400060. 9 name "3780 point discrete Fourier transform processor system and its "Structure" and Chinese Patent No. 03107204. 6 "Multi-carrier system with 3780-point IDFT/DFT processor and its method" requires at least 3N characters of memory space; Chinese Patent Publication No. 200410090873. 2, name" adopted The upsampling processing method realizes 3780-point discrete Fourier transform", Chinese Patent Publication No. 200710044716. 1. The 3780-point fast Fourier transform processor with the name "pipeline structure" requires at least 5N characters of memory space; China ^ Patent Disclosure No. 200610104144. 7 Name "3780-point discrete Fourier transform processor" requires at least 6N characters of memory space. Compared to the foregoing, the present invention requires only 2N characters of memory space. Also, please note that the output data in Chinese Patent No. 01140060.9, Chinese Patent No. 03107204.6, and Chinese Patent Publication No. 200710044716.1 are not orderly, so they need at least one N-character memory space with additional control logic 9 201017529 To reorder the output data for sequential output. (7) In the paper Z.-X. Yang, Y.-P. Hu, C. -Y. Pan, and L. Yang, "Design of a 3780-point IFFT processor for TDS-OFDM, 5, IEEE Trans. Broadcast., vol. 48, no. 1, pp· 57-61, Mar. 2002 The output data of the 3780-point FFT processor is not arranged in order. In order to be able to arrange in sequence, it needs a buffer to go. The output data is rearranged, so that it requires at least 3N characters of memory space to achieve this requirement on the premise that the continuous data stream can be processed, but the present invention has only 2N character space memory as described above. In view of the above-mentioned shortcomings of the prior art, the present invention proposes a fast Fourier transform calculation and addressing method and an arbitrary-point forward/reverse fast Fourier transform processor design based on the memory using the method, the method first The feature of the term is: Decomposing the calculation of the long-point discrete Fourier transform into a discrete Fourier transform of several short points by the decomposition equation, and simultaneously mapping its index from a single dimension to a multi-dimensional index vector. The second method of the method of the present invention special By controlling these multi-dimensional 201017529 indicator vectors, the present invention distributes the original input data into a plurality of memories so that the data replacement and the memory during the calculation are simultaneously achieved without causing memory access conflicts. The purpose of the complete butterfly point access is as follows. The third feature of the method of the present invention is that when the data replacement is used, the old data sequentially output and the new data are sequentially input, and can be continued for the subsequent calculation period. There is no memory conflict when accessing data. The calculation of new data takes the reverse operation with the previous data calculation to achieve the purpose. This method is a memory-based discrete fast Fourier transform for any number of points. The processor design can effectively reduce the processor area and the required operating clock. This month's FT-based fast Fourier transform processor design includes: - the main memory for storing data a processing element for short-point number fast-changing after decomposing, and a depressing unit, wherein the control unit It has the functions of controlling the following items: (Γ) the memory for the input data and the butterfly operation, (2) the calculation order of the short-point final Fourier transform after decomposition, and (3) the data access method for data access. The memory address is set to perform the above-described method. [Embodiment] In order to achieve the above object, the present invention will be described as follows: X{k)^NZx(ji)W^ Discrete Fourier transform Defined as "=0 ". The method of decomposing long-point discrete Fourier transform into several short-point discrete Fourier transforms has been published in the paper "IEEE TRANSACTIONS ON ACOUSTICS, SPEECH, AND SIGNAL PROCESSING, VOL. ASSP-25, NO. 3, JUNE 1977" For Multidimensional m

Proposed in Formulation of the DFT and Convolution. The present invention is described herein by the decomposition equation (1) of the point length N = N1N2: \n = N2nl + A2n2 modA^ =0, 1, , .., TV, -1 [k = + Nxk2 modN -1 ( 1) Equation (1) maps the indices n and k into index vectors (nl, n2) and (kl, k2), which are mapped from a single dimension [0, Nl] to a two-dimensional [0, Nl-1] X [ 0, N2-1]. The choice of coefficients A2 and B1 depends on the relationship between N1 and N2. In the method proposed by the present invention, the coefficient selection rule of equation (1) is as follows: Case 1: If N1 and N2 are mutually prime, A2 and B1 satisfying the following conditions are selected as coefficient A2: =plNl and A2 = dlN2 + 1 B1 : =p2N2 and B1 = q2Nl + 1 12 201017529 Here, pi, ql, n9 0 ^ ^ P and q2 are all positive integers. Therefore, the definition of the discrete Fourier transform can be determined by the following equation (2): ^, A2) = ^ X〇c(«l,n2)»^*'^ «I is called 12 =Σ{ Σχ («ι»«2)^^} =ΣΜ.«ί) ^ (2) Condition 1. If Nl and M2 are not mutually prime, then use A2 = B1 = Buin &H# it leaf transformation definition Can be written as the following equation (3): =Σ{ w^ (3)

The present invention can be known from equations (2) and (8), and the long-point (N-point) fast Fourier transform can be calculated by using two shorter points (N1 point and N2 point) fast-changing Fourier transform in the first and second stages, respectively. . For the fixed value n2, the original round entry data of the first stage N1 point fast Fourier transform is x(nl, n2), nl-Ο, 1,·.., N1-1. The output data corresponding to the first stage of this n2 is y(kl, must, kl=G, i ..., N Bu is the fixed value u, the original round entry of the second stage N2 point fast Fourier transform is y (kl' 112), n2=0' 1, 1.·., N2 卜 corresponds to the second stage output data of this kl is X(kl, k2), k2 = 〇, i, ..., N2h. Equation 13 201017529 The difference between (2) and (3) is that if N1 and N2 are not mutually prime, there is a rotation factor as shown in equation (3) between the first and second stages. Note: In case of case 1, the coefficient The selection may also be as in case two, and the subsequent process of the present invention is the same as the first stage calculates the N1 point discrete Fourier transform and the second stage calculates the N2 point discrete Fourier transform to obtain the first discrete Fourier transform symbol. First, the original input data is dispersed into several memory banks. Assuming N22N1 and the number of memory banks is N2 ', the original input data can be distributed to N2 memory banks by equation (4). Avoid memory conflicts. bank = nl + n2 mod N2 (4) The key to avoiding memory conflicts is to pass the equation Equations (1) and (4) distribute the data in the memory. Once the memory is selected, the data needs to be addressed. Any two data in the same memory should be mapped to different addresses within the range of N1_l. For the sake of simplicity, the following equation (5) is used to perform data addressing. address = nl (5) After completing the calculation of the first discrete Fourier transform symbol, the data should be output in order. The output index is determined by the equation (1). The mapping is obtained by inputting the input data of the second symbol in the order of the fourth discrete Fourier transform symbol data of 201017529, which is also replaced by (4). That is, the new original input data, Convert the position of the output 枓X(1). The order of the calculation: is the opposite of the calculation of the first discrete Fourier transform symbol, that is, the N2 point discrete Fourier transform is calculated in the first stage, and the I point discrete Fourier transform is calculated in the stage. Take the second (four) vertical leaf transform symbol. After the second discrete Fourier transform symbol is calculated, the old data calculated by the data is sequentially output and the new data is sequentially input. The third discrete Fourier transform symbol is calculated according to the first discrete Fourier transform symbol. 以下 The following will be explained in detail by the fast Fourier transform required by the Chinese digital TV. The decomposition sequence described below For the only possible example, since 3780=4x3x3x3x5x7, the present invention can perform fast Fourier transform calculation of 3 points, 4 points, 5 points and 7 points respectively. Here, the data is distributed in 7 memory banks. Calculations are performed at 3, 3, 3, 5, and 7. The first segment (4-point fast Fourier transform) is performed using the decomposition equation; 15 201017529 f» = 945„1+2836«2mod3780 [*: = 945^,+ 4^2mod3780 «, ί ' '2',.·,944 ( 6) The above equations illuminate the indicator η 咏 去 为 为 为 向量 向量 向量 , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 944], as shown in Table 1. The index map of the first stage of Table 1 - nl=〇nl = l η1=2 η1=3 —---—— — «2 =〇χ[〇] χ[945] χ[18 χ[2835 90] ] «2 =1 χ[2836] χ[ΐ] χ[94 χ[1891 6] ] »2=2 χ[1892] χ[2837 ] χ[2] χ[947] • · · • · · • · · • · • · · ^2 =944 χ[944] χ[28 χ[3779 χ[1889] 34] ] The data in each column of Table 1 is the original round entry for each 4-point Fast Fourier Transform. The order of input depends on the indicator nl. For example, & = 1 column 16 201017529 'The input order is (nl, (〇, 1), (1, 1), (2, 丨) and (3, D 'the corresponding data is χ [2836] χ[1], χ[_], as shown in Table--J. Since the original input data of each 4-point fast Fourier transform has the same index "2", the data can be distributed by equation (7). Different 3 memory pools to avoid the first phase of memory conflicts.

Bank = nl + x mod7 (7) After the first stage, the original data has been decomposed into four independent groups of 9-point fast Fourier transforms, corresponding to kl=〇, H and 3. Similarly, the present invention can also decompose the above-mentioned 945-point fast Fourier transform in the order of 945 = 3χ3χ3χ5χ7, and map the index & to the vector ❿(η2, η3' η4, η5, π6), that is, [〇, 944] Map to [〇, 2]x[〇, 2]x[0,2]χ [〇,4]χ[〇,6]. Combining all the decomposition equations of each stage, we can obtain the complete index mapping equation of 378〇 fast Fourier transform according to this decomposition order, as shown in equations (8) and (9), using equations when selecting memory. 〇) To avoid memory conflicts, the equation (11) can be used for the address equation. n = 945nl + 1260n2 + 2940n3 + 980n4 + 1512n5 + 17 201017529 540n6 mod3780 (8) k = 945kl + 2380k2 + 3360k3 + 2520k4 + 2268k5 + 540k6 mod3780 (9) bank = nl + n2 + n3 + n4 + n5 + n6 mod7 (10) address = 135nl + 45n2 + 15n3 + 5n4 + n5 • (11) Following the calculation of the first fast Fourier transform symbol, ie the singular fast Fourier transform symbol, in equations (1〇) and (11) All indicator 111 will be converted to ki. For the second input fast Fourier transform symbol, that is, the double-number fast-forward Fourier transform symbol, the input data xeven[n] of the double-number fast Fourier transform symbol should be placed into the singular discrete Fourier transform symbol The position of the data XQd❿], the relationship between the two is its mapping index, memory and silk should be determined by equations (8), (ίο) and οι). The following discussion discusses how to continue to avoid memory crying during data access during the calculation period under the current double-numbered fast Fourier transform symbol. The present invention is calculated using the reverse order of the calculation of the singular fast Fourier transform symbol for calculating the double fast Fourier transform symbol 201017529, that is, let = 7 χ 5 χ 3 χ 3 χ 3 χ 4, in other words, the present invention is 7

*', 5, 3, 3, 3, and 4 points of the fast Fourier transform are executed sequentially. By (4) financial formula, the present invention can obtain the complete input-output index mapping equations (12) and (13) of the double-number fast Fourier transform symbol, and the result is similar to the complete index mapping equation (8) of the singular fast Fourier transform symbol and (9) Equations (12) and (13) map the input index η and the output index k to vectors (ai, a2, a3, a4, a5, a6) and (bl, b2, b3, b4, b5, b6, respectively). ), that is, [〇,3779] is mapped to [〇,6]x[0, 4]χ[0' 2]χ[0,2]x[〇,2]x[0,3] to calculate the double number Fast Fourier transform symbol. n = 540al + 2268a2 + 2520a3 + 3360a4 + 2380a5 + 945a6 mod3780 (12) k = 540bl + 1512b2 + 980b3 + 2940b4 + 1260b5 + 945b6 mod3780 (13) Input and output indicator equations (9) and (12) and (8) Corresponding to (13), it can be found that the two sets of equations match each other in the inverse vector relationship, as shown in equations (14) and (15). (al, a2, a3, a4, a5, a6) = (k6, k5, k4, k3, k2, 201017529 kl) (14) (nl, n2, n3, n4, n5, n6) = (b6, b5, B4, b3, b2, bl) (15) The input data of the double-numbered fast Fourier transform symbol xeven[n] is placed in the calculated singular fast Fourier transform symbol output data.

The position of Xodd [ k ] and the relationship between the two is k = n, thereby obtaining the memory selection and memory addressing equations (16) and (17) of the double number 10 fast Fourier transform symbol. Bank = technique 1 + + technique 3 + a4 + + technique 6 mod7 (16) address = 135a6 + 45a5 + 15a4 + 5a3 + a2 (17) Note that the input mapping equation (12) is the same as the output mapping equation (9). And the memory selection equations (10) and (16) remain the same. It is recalled that during the calculation of the double-numbered fast Fourier transform symbol, the memory is always free of access conflicts by reversing the calculation of the singular fast Fourier transform symbol decomposition order. In addition, the present invention finds that the output mapping equation (13) is the same as the input mapping equation (8), meaning that the third fast Fourier transform input data xthirdU] is placed in the calculated double-number fast Fourier transform output data xeven When the position of [k] is such that k=n, the third 20 201017529 fast Fourier transform input data can be stored in the same manner as those determined by equations (8), (10) and (11), that is, the third The data storage location of the fast Fourier transform symbol is the same as the data storage location of the singular fast Fourier transform symbol, and returns to the state of the initial discussion, xthird[n]= x〇dd[n]. According to the above embodiments, the present invention can design a variable base fast Fourier transform processor without memory conflict by reversing the previous fast Fourier transform symbol decomposition sequence, which can simultaneously achieve butterfly output and data input and output. Data replacement. The first picture is a memory-based 3780-point discrete Fourier transform processor design block diagram, in which MEM-1 and ME12 are two memory blocks (each block contains 7 memory banks (memory reference bank) Each memory bank has a size of 540 words, and the FFT_C0RE includes a processing unit that can separately process the discrete-point Fourier transform of the short-point number, and the number of clock cycles required for calculating the discrete Fourier transform of each short-point number is determined by the designer according to the requirement. This also determines the number of hardware required for the computing unit, and the control unit controls the data access and processing unit calculations. The operation of the discrete Fourier transform processor will be explained below. For convenience of explanation, the decomposition and calculation order of the first type is defined as 4 21 201017529 points, 3 points, 3 points, 3 points, 5 points and 7 points. Discrete Fourier transform, and define its reverse order as the second order, followed by '(', 5, 3, 3, 3, and 4 discrete Fourier transforms. Suppose the first and second discrete Fourier The conversion symbols are stored in the memory blocks MEM-1 and _~2, respectively, and it is assumed that the decomposition and calculation order of the first and second discrete Fourier transform symbols are in the order of the first type, then the above description, this According to the invention, (1) the first, fifth, ninth, thirteenth... discrete Fourier transform symbol is stored in the memory block MEM-1 and is calculated in the first order. (2) Second, sixth, ten, fourteen·discrete Fourier The conversion symbol is stored in the memory block MEM-2 and is calculated in the first type of order. (3) The third, seventh, eleventh, and + five miscellaneous traps a fifteen... the discrete Fourier transform symbol is stored in memory Block MEM_1 is calculated in the second order. (4) Fourth, person, Ten:16. The discrete Fourier transform symbol is stored in the memory block MEM-2 and is calculated in the second order. For the sake of explanation, only the discrete Fourier transform of length (10) is shown in the second figure. As an example, the hardware implementation of the indicator vector required for data access is described. As shown in the second figure, it is composed of several accumulators Αι, A2, ..., A5. The control unit contains 3 groups of this hard. Body design, 22 201017529 Two groups are used to generate the index vector required for data input and output, and the parameters ΙΠ, U2, U3, 114, q and r are determined by the decomposition equation (1) of each stage, while the third group is It is an index vector used to generate the data required for each short point Fourier to two. It is different from the previous two groups. The parameter q'r at this time is 〇', ie, a4, A5 can be removed. Table 2 below shows Comparison of different real-time application methods for memory-based discrete Fourier transform processing. All of the projects, only the method of this case and [US Patent 4, 477, 878] can support the integration of any general base. Make any points faster Fourier transform. However, as described above, [[US Pat. No. 4,477,878] fails to implement a multi-bank mem ry structure without memory conflict, and thus cannot reduce the operational clock required for immediate application. A memory-based fast Fourier transform processor design method is proposed, which can satisfy the following three items: (1) data replacement during butterfly operation and input and output data; (2) mixing of any base; and (3) support for multiple memories 23 201017529 Table 2 Comparison of the present invention and different methods [A1] [A2] [B2] [A5] [A3] [A4] B[3] The cardinality of the invention, all general fixed bases - r fixed base - r base _ 2/4 All general data replacement is yes or no memory 2N words 2N words 2N words 2N words 2N words multiple memory banks whether it is yes [A1]: US Patent 4,477,878 [A2]: US patent 5, 091, 875 [A3]: U.S. Patent 7,062,523 [A4]: U.S. Patent 7,164,723 [A5]: U.S. Patent Publication No. 20060253514 24 201017529 [B2]: Paper LG Johnson "Conflict free memory addressi Ng for dedicated FFT hardware,” IEEE Trans. Circuits Syst. II, Analog Digit. Signal Process., vol. 39, no. 5, pp. 312-316, May 1992. B[3]: Paper BG Jo, and Μ H. Sunwoo, "New continuous-flow mixed-radix (CFMR) FFT processor ❿ using novel in-place strategy," IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 52, no. 5, pp. 911 -919, May 2005. In summary, when the method of the present invention is applied to the 3780-point discrete Fourier transform required for Chinese digital television, only 2N words of memory can be used to meet the system requirements while achieving continuous data flow. The purpose of inputting and outputting with the data in sequence. If you want to achieve the same effect as the case, [US Patent Publication 9 20080025199], [Chinese Patent 0114060], and [Chinese Patent 03107204.6] require at least 3N words of memory, [Chinese Patent Publication 200410090873.2] and [Chinese Patent] Public 200710044716. 1] Memory of at least 5N words is required, [Chinese Patent Publication 200610104144.7] requires 6N words of memory, and [Thesis 2.-Yang Yang, Y. -P. Hu, C. -Y. Pan, and L. Yang, ^Design of 25 201017529

a 3780-point IFFT processor for TDS-OFDM,” IEEE

Trans. Broadcast., vol. 48, no. 1, pp. 57-61, Mar. 2002] also requires at least 3N words of memory. Therefore, for this application, if the 3780-point discrete Fourier transform processor is designed in the present method, the chip area can be greatly reduced compared to the prior art designer. The invention further provides a memory-based (forward/reverse) fast ❿ Fourier transform processor for performing the above method, which comprises: a main memory for storing data, and a short point after decomposition A fast Fourier transform processing component and a control unit, wherein the control unit has the function of controlling the following items: (1) input and output data and memory for butterfly operation, and (2) short point fast Fourier transform after decomposition The order of calculation, and (3) the memory-based win address required for data access by means of data replacement. Used to perform the above method. The main memory includes two memory blocks, namely MEM_1 and MEM-2. When MEM_1 is used for fast Fourier transform operation, MEM_2 is used for input and output data, and vice versa; and, each memory The block contains a memory bank, and the size of each memory bank is N/M, where N is the length of the point of the fast Fourier transform, and the number of memories is set by the system designer. The unit FFT_C0RE is designed to perform individual calculations on the decomposed short point fast Fu 26 201017529 Fourier transform. The number of clock cycles required to calculate the discrete Fourier transform of each short point is determined by the designer according to the requirements. The number of hardware required. The control function of item (1) of the control unit controls the memory blocks as described above to switch their functions to fast Fourier transform calculations or input and output data. The control function of item (2) of the control unit controls the processing element to perform short-point fast Fourier transform calculation in the reverse order of the previous fast-speed Fourier transform symbol decomposition order of the same memory block, thereby obtaining a fast Fourier transform symbol; that is, if the fast Fourier transform symbol is in a memory block with a ni point fast Fourier transform, an N2 point fast Fourier transform .... to the Nk point fast Fourier transform sequence calculation ' The order of calculation of the next fast Fourier transform symbol stored in the same memory block is Nk point fast Fourier transform called 〇•point fast Fourier transform...to N1 point fast Fourier transform. The control function of item (3) of the control unit controls the data access by means of data replacement, thereby performing the butterfly operation and data input wheel of each memory block, and the operation principle of the three groups is as shown in FIG. The body design, in which two groups are used to generate the index vector required for data input and output, the parameters 111(10), 113, M, q and r are determined by the decomposition equations of each stage. The third red limb is used to generate the 27 201017529 index vector of the data required for each short-point Fourier transform. The only difference from the previous two sets is that the parameter q, r is 0 at this time. In the above, the above embodiments are only intended to illustrate the specific embodiments of the present invention, and the scope of the invention should be determined by the scope of the patent application. [Simple diagram of the drawing] ❿The first figure is a block diagram of the design of the fast Fourier transform processor of the present invention. The second figure shows the hardware implementation diagram of the indicator vector generator of the present invention. [Main component symbol description] None

28

Claims (1)

201017529 X. Application for patents: 1. The calculation of ant arbitrage method for arbitrary reduction of fast side-lobe conversion. The ship consists of the following steps: (1) Decomposing the calculation of long-point discrete Fourier transform into discrete Fourier transforms of several ship points. 'And at the same time map its indicators from a single dimension to a multi-dimensional indicator vector; • (2) by controlling these multi-dimensional indicator vectors, the original input data is scattered into several memories' so that no memory access conflicts are generated In the case of simultaneous data replacement during the calculation period and the purpose of accessing the complete butterfly point of the memory; (3) When the New Zealand replacement system is in the order of (10), the data is sequentially output and the new data is sequentially input. After the calculation _ can continue to maintain the data access without the conflict of the person's memory conflict 'for the calculation of the new data to take the reverse of the previous data calculation i to achieve the purpose; in this way, for the design of any number of memory Based on the fast Fourier transform processor, you can reduce the processor area and the required operating clock. 2. Including: a positive/reverse fast Fourier transform processor based on 6 recalls. Leaf and spine exchange: the main memory of the discharge material, Zhao Yi, after decomposition, short point number, fast Fourier =: processing · and - control unit The control unit has the function of controlling the following items. (1) Input and output data and memory for butterfly operation (2 Guang 29 201017529 short point number fast fan Fourier transform calculation order, and (3) data replacement method The address of the memory required for data access. 3. If you apply for a special (4) 2 meal, the positive/reverse fast Fourier transform processor of the domain body, where the main memory contains two memory blocks, which are MEM. —1 and MEM~2, when MEM_1 is used for fast Fourier transform operation, Xihe-2 is used to input the wheeled data, and vice versa. • 4. As described in the patent application 帛3, the memory is The basic positive/reverse fast Fourier transform processor', wherein each memory block contains one memory, and the size of each hidden library is jV/jVl 'the towel# is the length of the point of the fast Fourier transform, Μ For system designers The number of memory banks set. 5. The positive/reverse fast Fourier transform processor based on the memory of the second aspect of the patent application scope, wherein the processing unit is designed to be faster for the short points after decomposition The idling Fourier transform is performed for individual calculations. 6. If the application is for the general purpose, the second is the memory of the basics... the reverse fast Fourier transform processor', where the control unit (1) (4) Wei system control is applied The two ugly blocks described in the third paragraph of the patent paradigm are used to convert the Wei to the fast Fourier transform to calculate the money ^^ data. If the application is specifically for the second item, the ship-based forward/reverse fast Fourier The conversion processor, the control function of the (2) item of the control unit is controlled by the control unit of the h control unit, and the step (3) step is executed to make use of the same---- The order of the miscellaneous lobes and the meta-decomposition order is reduced by 顺序, that is, 'if the fast Fourier transform symbol is in the memory block, the fast point is used in the % point, and the miscellaneous discussion..... .W Lai increase the order of calculation, then store _- remember _ The second is the calculation sequence of the fast Fourier ride symbol. The fast Fourier transform point is fast Fourier transform to fast Fourier transform. 1 ” 8. As described in the second paragraph of the patent application, the memory-based positive, An inverse fast Fourier transform processor, wherein the control function of the '(_) element is addressed by the memory and controls data access by means of data replacement, thereby performing each memory block Butterfly operation and data input output. This control Wei is the implementation of patent (2). 1 item 9 · The memory-based forward/reverse fast Fourier transform processor as described in item 8 of the patent application scope, wherein the 'memory library for performing data access is determined by the indicator vector' «2, ··, “k) is determined by equation (ai), where the equation (τ __ constant is uniform and the indicator vector corresponds to each short point fast Fourier transform, that is, the % point described in item 6 of the profit range is fast Fourier transform, % point fast application for exchange...···To point fast Fourier transform., Zero-leaf turn 31 201017529 όαι认=叫+ 叱+ ... + „k + em〇d M ^ Memory-based forward/reverse according to item 9 of the scope. The conversion processor 'where' equation (6) divides all the data into one seam library of each-four (four) block, and the contact material can be fine index Sub-Uk)-function, the indicator vector can set two data in the same group to two different addresses; when the number of memory M = Μ, #helmet λ,, enter Lu 1 Μ, '...drink one of them. And (tA, t/2,..., like =(H ...,# t·1 ' M+1,..., k) * (Wi » U2 > ... » Mk-l) = ( «1 5 «2 * ... » ru, yn -t+i ' ..· ' 叫). The decomposition and calculation order is l-point fast Fourier transform, point fast Fourier transform. To I point fast Fourier transform or In the reverse order, we use equation (6) to determine the data address. k-2 k~\ ^={Σ(Π^}+^ mod^/M) (a3) • 11. As described in item 9 of the patent application A memory-based forward/reverse fast Fourier transform processor, wherein the index vector is generated by decomposing the following equations (6) and (6) at each stage, where the chest is defined as a 'discrete Fourier transform' ', 〇转' 'The decomposition equations (6) and (a5) can decompose the JV point discrete Fourier transform into two discrete records, (4) stray Fourier transform and I-point discrete Fourier transform; decomposition equations (6) and (6) Coefficient wood and 怂32 201017529 is a positive integer 'input money out indicators are respectively compiled by the input and output equations) and (6) conversion; η = Λ^«ι + Λ2η2 k — B\k\ + N\k2 Mod TV W1, moxibustion 1=0,1,·..,Λ^-1 «2, ^2 = 0, 1, ..., N2-\ (34) (a5) ° 12. As claimed The memory-based forward/reverse fast Fourier transform processor described in the nine items, the thief of the thief The domain vectors ~, (4) of the output equation can be obtained by the hardware of the accumulator. A memory-based forward/reverse fast Fourier transform processor as described in the application for full-time, wherein the index vector ^2, , is used to be accessed by the fourth-order discrete Fourier transform. Every two materials of the material: =::, and the calculation of the completed transmission is the hardware application and the rotation side (10) gamma accumulator 33