JPH0516618B2 - - Google Patents

Description

[Detailed description of the invention]

[Industrial Application Field] The present invention relates to a butterfly arithmetic circuit used for arithmetic processing of digital sample values by, for example, fast Fourier transform, and in particular, the present invention relates to a butterfly arithmetic circuit used for arithmetic processing of digital sample values by fast Fourier transform, etc. and the address of the data memory for storing digital data obtained by butterfly calculation are the same. [Background Art and Problems Therein] A butterfly arithmetic circuit is used when digital sample values are to be subjected to arithmetic processing using, for example, fast Fourier transform (FFT). In the butterfly operation of digital data x ₁ and x ₂ , if the coefficient is k and the operation result is digital data y ₁ and y ₂ , then y ₁ = x ₁ + kx ₂ y ₂ = x ₁ − kx ₂ ...(1 ) can be expressed as Furthermore, in the butterfly arithmetic circuit, if the numerical values handled are expressed in a fixed point system and negative numbers are expressed in two's complement, the numerical value N in the arithmetic circuit has a range of -1≦N<1. Therefore, if the digital data y ₁ , y ₂ obtained as a result of the butterfly operation overflows, the numerical values are halved as shown in the following formula.
After multiplication, a butterfly operation is performed. y ₁ = 1/2x ₁ +k/2x ₂ y ₂ = 1/2x ₁ -k/2x ₂ ...(2) When attempting to execute a large number of butterfly operations at high speed using the above butterfly operation circuit,
So-called pipeline processing is performed. This pipeline processing does not wait for the completion of one butterfly operation before starting the next butterfly operation, but rather starts the next butterfly operation while the butterfly operation is being executed. This is a processing method that processes in parallel. The above butterfly operation circuit includes, for example, two multipliers, two adders/subtractors, k for the operation of equation (1), or 1/2 and k/ for the operation of equation (2).
2, two data memories that store x ₁ , x ₂ and y ₁ , y ₂ , and one address generator that calculates the addresses of the coefficient memory and data memory. ing. The reason why two multipliers, adders/subtracters, and data memories are provided is that the digital data x ₁ and x ₂ are complex numbers, and operations are performed on the real and imaginary parts, respectively. With this butterfly arithmetic circuit, equation (1) or
If the butterfly operation in equation (2) is executed in parallel as much as possible using pipeline processing, the next butterfly operation will be performed 4 steps after the start of one butterfly operation, unless the number of memory accesses is taken into consideration. be able to. That is, the signal processing efficiency in this case is such that one butterfly operation can be executed in substantially four steps. However, considering the number of accesses to the coefficient memory and data memory to perform one butterfly operation, in the case of the operation of equation (1) or (2), k
or twice to specify k/2 twice, and x ₁ ,
It is necessary to access the x ₂ , y ₁ , and y ₂ specifications four times, six times in total. Here, the coefficient k is generally k=cosθ
−isinθ is used, and cosθ or cosθ/2, sinθ or sinθ/2 are accessed twice, and the real and imaginary parts of complex numbers x ₁ , x ₂ , y ₁ , y ₂ are at the same address in different memories. 4.
accesses are made twice. In this way, in order to access the coefficient memory twice and the data memory four times, the address generation section requires six steps for one butterfly calculation to perform address calculation. For this reason, in the butterfly operation circuit described above, which has only one address generation unit, when considering memory access, the signal processing efficiency drops to 6 steps per butterfly operation, and the next one has to wait for 6 steps. cannot perform butterfly operations. Therefore, in order to increase the signal processing efficiency to 4 steps per butterfly operation, it is necessary to provide two address generators. in this way,
Increasing the number of address generators by one means that the required IC
The drawback is that the number of integrated circuits (integrated circuits) increases significantly and the number of microprogram instructions increases. As described above, the conventional butterfly arithmetic circuit has the disadvantage that the signal processing rate is low, and in order to increase the efficiency, the number of elements must be increased or the number of microprogram instructions must be increased. [Object of the Invention] The present invention was proposed in view of the above circumstances, and an object of the present invention is to provide a butterfly calculation circuit that can perform butterfly calculations at high speed without adding one address generation unit. purpose. [Summary of the Invention] To achieve this object, the butterfly calculation circuit of the present invention includes a data memory for storing digital data x ₁ , x 2 , etc. based on digital sample values, and a data memory for storing digital data x 1 , x _{2 ,} etc. based on digital sample values, and a coefficient k or a coefficient 1/2 and k /2, an address generation unit that calculates address data indicating addresses of the data memory and the coefficient memory, and a multiplier and an adder/subtractor that perform multiplication and addition/subtraction on the digital data, at least one pair of said digital data stored in said data memory;
Butterfly operation is performed on x ₁ and x ₂ (y ₁ = x ₁ + kx ₂ , y ₂ = x ₁
−kx ₂ , or y ₁ =x ₁ /2+kx ₂ /2, y ₂ =x ₁ /
2-kx ₂ /2) to obtain the digital data y ₁ and y ₂ as the calculation results, the butterfly calculation circuit stores the address data generated by the address generation section and uses the stored address data. an address data storage section selectively supplying the data memory as address data, the address data storage section storing and holding address data when the digital data x ₁ and x ₂ are read from the data memory; By supplying the stored address data to the data memory when the digital data y ₁ , y ₂ which is the calculation result is written to the data memory, the digital data x ₁ , x ₂ can be written to the data memory.
The digital data y ₁ and y ₂ which are the calculation results are written to the same address as the address from which the data were read. [Example] Hereinafter, an example of the present invention will be described based on the drawings. As mentioned above, in the butterfly operation of a pair of digital data x ₁ and x ₂ based on digital sample values, if the coefficient is k and the pair of digital data obtained by the butterfly operation is y ₁ and y ₂ , then y ₁ = x ₁ + kx ₂ y ₂ = x ₁ − kx ₂ ...(1) Also, if the digital data y ₁ and y ₂ that are the calculation results overflow,
To prevent overflow, a butterfly operation is performed using the following equation. y ₁ = 1/2x ₁ + k/2x ₂ y ₂ = 1/2x ₁ - k/2x ₂ ...(2) Here, the digital data x ₁ and x may be multiplied by 1/2, but If the numerical value N of the butterfly calculation circuit in which the butterfly calculation is performed has a range of -1≦N<1, the range of the coefficient k is -1.
If the real part or imaginary part of ≦k≦1, a problem arises in calculation within the butterfly calculation circuit. To avoid this inconvenience, instead of multiplying the digital data x ₂ by 1/2, k is multiplied by 1/2. The domain is -1≦x _i , real part or imaginary part <1, i=
Digital data that is 1, 2, 3, 4, etc.
Digital data y ₁ , y ₂ , y ₃ , y ₄ , . . . can be obtained by performing butterfly calculations on x ₁ , x ₂ , x ₃ , x ₄ , . Furthermore, the digital data that is the result of this calculation is
If you perform butterfly operations step by step, such as performing butterfly operations on y ₁ , y ₂ , y ₃ , y ₄ , ... and then performing butterfly operations on the results of the operations,
Using butterfly operation, digital data x ₁ ,
For example, fast Fourier transforms (FFT) for x ₂ , x ₃ , x ₄ , . . . are calculated. For example, when attempting to perform fast Fourier transform using a butterfly arithmetic circuit, if an overflow occurs in the arithmetic circuit, the butterfly operation of equation (2) is used. By the way, since data subjected to fast Fourier transform has a very small numerical value (absolute value), when attempting to calculate inverse Fourier transform using butterfly computation, overflow in the butterfly computation circuit does not occur. Therefore, the butterfly operation of equation (1) is used to calculate the inverse Fourier transform. By the way, the above digital data x ₁ , x ₂ , x ₃ ,
_For example, if we use digital audio sample value data α ₁ , _{α 2} , α _{3 ,} α ₄ , etc. ^as 〓, If the new pair of digital data obtained by butterfly calculation is β ₁ and β ₂ , then β ₁ = α ₁ +e ^-i 〓・α ₂ β ₂ = α ₁ −e ^-i 〓・α ₂ … ...(3) Or, β ₁ = 1/2α ₁ +e ^-i 〓/2・α ₂ β ₂ = 1/2α ₁ −e ⁻ⁱ 〓/2・α ₂ ...(4). By repeating the butterfly operation on this digital audio sample value data α ₁ , α ₂ , α ₃ , α ₄ , … and performing fast Fourier transform,
For example, frequency spectrum data, which is the final calculation result, can be obtained. Here, the above digital data α ₁ , α ₂ , β ₁ , β ₂
The real part of is expressed as A ₁ , A ₂ , B ₁ , B ₂ , and the imaginary part is expressed as a ₁ ,
If expressed as a ₂ , b ₁ , b ₂ , the data α ₁ , α ₂ , β ₁ , β ₂
α ₁ =A ₁ +ia ₁ α ₂ =A ₂ +ia ₂ β ₁ =B ₁ +ib ₁ β ₂ =B ₂ +ib ₂ . Also, if we use the fact that e ^-i 〓=cosθ−isinθ, equation (3) becomes β ₁ = (A ₁ +ia ₁ )+(cosθ−isinθ)・(A ₂ +i
a ₂ ) β ₂ = (A ₁ + ia ₁ ) + (cosθ−isinθ)・(A ₂ + ia ₂ ). From this equation, the real parts B _{1 and} B ₂ and the imaginary parts b ₁ and b 2 of β ₁ and β ₂ are calculated as follows. B ₁ = A ₁ + (cosθ・A ₂ + sinθ・a ₂ ) b ₁ = a ₁ + (cosθ・a ₂ + sinθ・A ₂ ) B ₂ = A ₁ − (cosθ・A ₂ + sinθ・a ₂ ) b ₂ = a ₁ − (cos θ・a ₂ + sin θ・A ₂ ) ……(5) Also, calculate the equation (4) in the same way, and calculate the real parts of β ₁ and β _2.
Calculating B ₁ , B ₂ and the imaginary parts b ₁ and b ₂ is as follows. B ₁ = A ₁ /2 + (cosθ/2・A ₂ + sinθ/2・a ₂ ) b ₁ = a ₁ /2+ (cosθ/2・a ₂ −sinθ/2・A ₂ ) B ₂ = A ₁ /2 −(cosθ/2・A ₂ +sinθ/2・a ₂ ) b ₂ =a ₁ /2−(cosθ/2・a ₂ −sinθ/2・A ₂ ) ……(6) Figures 1 and 3 1 is a block diagram of a butterfly arithmetic circuit according to the present invention. The butterfly calculation circuit 1 shown in FIG. 1 is designed to perform the calculation shown in equation (5), and by performing this calculation, the butterfly calculation in equation (3) is executed. In addition, the calculation shown in equation (6) is performed by the butterfly calculation circuit 2 shown in FIG.
The butterfly operation of equation (4) involving multiplication is now performed. In the butterfly operation circuits 1 and 2, the digital data α ₁ and α ₂ to be subjected to the butterfly operation and the digital data β ₁ and β ₂ obtained by performing the butterfly operation are stored in the data memories DMA and DMB. ing. Also, data β ₁ ,
β ₂ is stored at the same address in the data memories DMA and DMB where data α ₁ and α ₂ were stored. The above digital data α ₁ ,
The real parts A ₁ , A ₂ , B ₁ , B ₂ of α ₂ , β ₁ , β ₂ are stored in the data memory DMA, and the imaginary parts a ₁ , a ₂ , b ₁ , b ₂ are stored in the data memory DMB. It's becoming like that. In addition, the coefficient memory CM provided in the butterfly arithmetic circuit 1 stores the real part and imaginary part cosθ of the coefficient k.
and sin θ are stored. In addition, the coefficient memory CM of the butterfly calculation circuit 2 stores the coefficient 1/2 for multiplying α ₁ by 1/2, and the real part and imaginary part of the coefficient k/2, cosθ/2 and sinθ/2. It is becoming more and more common. Next, the configuration of the butterfly calculation circuit 1 shown in FIG. 1 will be explained. The data memory DMA of the butterfly arithmetic circuit 1 is connected to register R2A and register R3A, register R2A is connected to register R4A and multiplier MPYA, and register R3A is connected to multiplier MPYB.
Also, data memory DMB is connected to register R2B and register R3B, and register R2B
is connected to register R4B and multiplier MPYB,
Register R3B is adapted to be connected to multiplier MPYA. Also, the coefficient memory CM is a multiplier
Connected to MPYA and multiplier MPYB.
This multiplier MPYA and the register R4A are connected to an adder/subtractor ALUA, and the adder/subtractor ALUA is connected to a register R1A.
Furthermore, this register R1A is a data memory
Connected to DMA. Also, the above multiplier
MPYB and register R4B are adder/subtractor ALUB
and the adder/subtractor ALUB is connected to the register R1B.
It is becoming connected to. Further, this register R1B is connected to the data memory DMB. In addition, the above data memory
One address generation unit AG is provided to calculate addresses for the DMA, DMB, and coefficient memory CM. This address generator AG is a register RCM
1 and the register group RDM1. This register RCM1 is connected to the above coefficient memory CM, and the register group RDM1 is connected to the above data memory.
It is now connected to DMA and DAM.
Here, the registers R1A, R1B, R2A,
R2B, RCM1, and register group RDM1 are designed so that data import signals to these registers can be controlled by a microprogram. Further, FIG. 2 shows the structure of the butterfly calculation circuit 1 shown in FIG.
In FIG. 2, a control signal, which is the output of the OR circuit 10 to which the capture signal and the clock signal are input, is input to the register RCM1, and at an appropriate timing, the address output from the address generator AG is sent via the register RCM1. hand,
It is now sent to the coefficient memory CM. In addition, the above-mentioned register group is a storage means for temporarily storing the address when reading digital data stored in the data memories DMA and DMB.
RDM1 is a 4-stage shift register.
It is composed of registers 11, 12, 13, and 14 and a multiplexer 15. Each of the registers 11, 12, 13, and 14 receives a control signal that is the output of an OR circuit 16 that receives the capture signal and the clock signal. In addition, each register 11, 12, 13, 14
are connected to a multiplexer 15, respectively. In addition, the multiplexer 15 has a data memory
Connected to DMA and DMB. Selection signals S ₁ , S ₂ , S ₃ , and S ₄ made up of, for example, 2 bits are input to this multiplexer 15 so that the outputs of registers 11 , 12 , 13 , and 14 are selected, respectively. . Then, at an appropriate timing, the address output from the address generator AG is sent to the data memory via the registers 11, 12, 13, 14 and the multiplexer 15.
It is now being sent to DMA and DMB. Tables 1 and 2 show means for calculating equation (5) using the butterfly calculation circuit 1 shown in FIG. In the butterfly calculation circuit 1, data A ₁ is stored at address P ₁ of the data memories DMA and DMB,
a ₁ is stored respectively, and data is also stored at address P ₂ .
A ₂ and a ₂ are stored respectively. Also, the real part of coefficient k is at address Q ₁ of coefficient memory CM.
cos θ is stored, and the imaginary part, sin θ, is stored at address _Q2 . Also, the calculation results B ₁ , b ₁ , B ₂ , obtained by performing the butterfly calculation once,
b ₂ is the above data in data memory DMA, DMB
Data B ₁ is stored at address P ₁ where A ₁ and a ₁ were stored.
b ₁ is stored, respectively, and data B ₂ and b ₂ are stored at address P ₂ where data A ₂ and a ₂ were stored, respectively.

【table】

【table】

[Table] Based on Tables 1 and 2, first, we will explain the procedure for calculating the real parts B ₁ and B 2 shown in equation (5) of digital data β ₁ and β ₂ , which are the calculation results obtained by _butterfly calculation. explain. First, in the first step, the address generator
The output P ₂ calculated by the AG is input to the OR circuit 16 at the same time as the clock signal for sequentially advancing the steps and the acquisition signal.
It is configured to be sent to register 11 of RDM1. In the next second step, the address generator AG
The address output _Q2 of is sent to the register RCM1 by simultaneously inputting the clock signal and the capture signal to the OR circuit 10. Furthermore, in the third step, the address output _P1 of the address generator AG is sent to the register 11 of the register group RDM1 in synchronization with the capture signal, but it is input to the multiplexer 15 of the register group RDM1 at an earlier time than the capture signal. register 1 by selection signal S ₁
One address signal _P2 is selected and the address signal _P2 is sent to the data memories DMA and DMB. At this time, the address signal _P2 is sent to the register 12 in synchronization with the above-mentioned take-in signal. Also, in this same step, the data _A2 of the data memory DMA addressed and read by the address signal _P2 is transferred to the register R2A.
sent to. Similarly, the data a ₂ of the data memory DMB read out by the address signal P ₂
is sent to register R3B. Also, in the next fourth step, the address output _Q1 from the address generator AG is sent to the register.
At the same time as being sent to RCM1, address signal _Q2 in register RCM1 is sent to coefficient memory CM.
The coefficient memory CM addressed by the address signal _Q2 is adapted to send sin θ corresponding to the imaginary part of the coefficient k to the multiplier MPYA. Also, in the same step, data _a2 stored in register R3B is sent to multiplier MPAY. Here, at the same time as the step advances to the next fifth step, the digital data α ₁ ,
For example, a pair of data α ₃ , α 2 , α ₃ , α _{4 ,} …
The next butterfly operation for α ₄ is started from the first step. by the way,
In the fifth step, the address signal _P1 stored in the register 11 of the register group RDM1 is selected by the selection signal _S1 in the multiplexer 15 and sent to the data memory DMA. In the data memory DMA, data A ₁ is read by being addressed by the address signal P ₁ .
This data _A1 is sent to register R2A. Also, in the same step, register
The address signal _Q1 stored in RCM1 is sent to the coefficient memory CM, and the real part cosθ of the coefficient k from the coefficient memory CM is addressed and read out.
is sent to multiplier MPYA. Also, the data stored in register R2A in the same step
A ₂ is sent to multiplier MPYA. Furthermore, the output of sin θ·a ₂ , which has already been multiplied in the multiplier MPYA, is sent from the multiplier MPYA to the adder/subtractor ALUA in the same step. Furthermore, in the next sixth step, data _A1 stored in register R2A is sent to register R4A. Also, the output of cos θ·A ₂ , which has already been multiplied in the multiplier MPYA, is sent to the adder/subtractor ALUA in this same step. Also, the following 7th
At step 6, data A1 stored in register R2A is sent to register R4A, but data _A1 stored in register R2A is sent to register R4A.
Data _A1 , which was sent to register R4A in the step, is sent to adder/subtractor ALUA. Also, from this data A ₁ , adder/subtractor
W=cosθ・A ₂ +sinθ・a ₂ which has already been added in ALUA is subtracted, and in this same step, the calculation output obtained by subtraction is B ₂ =A ₁
-W is sent to register R1A. Here, in the fifth and seventh steps, the first and third steps of the butterfly calculation are executed for the data α ₃ and α ₄ to be calculated next. Therefore, in the fifth and seventh steps, the address signals related to the data α ₃ and α ₄ are taken into the register group RDM1, and in the seventh step, the address signal P ₁ is sent to the register 13, and the address signal P ₂ is sent to the register group RDM1. 1
It is now being sent to 4th. By the way, in the next eighth step, the address signal _P2 stored in the register 14 of the register group RDM1 is
It is selected by the multiplexer 15 by the selection signal _S4 and sent to the data memory DMA. Data memory DMA addressed by address signal _P2 receives data _B2 , which is the calculation output stored in register R1A.
It is now stored at the same address where data _A2 was stored. This digital data
B ₂ corresponds to the real part of data β ₂ which is the butterfly calculation output of digital data α ₁ and α ₂ . Also, in this same step, data _A1 stored in register R4A is sent to adder/subtractor ALUA. Also, this data A ₁ has an adder/subtractor
W stored in ALUA is added, and the calculated output B ₁ =A ₁ +W obtained by the addition is sent to register R1A in the same step. The next ninth step is an empty step in order to match the number of steps, and nothing is executed. From this ninth step, for example, the first step of the next butterfly calculation for the pair of digital data α ₅ and α ₆ is started. Therefore, in this ninth step, the address signal for, for example, data α ₆ is taken into the register group RDM1, so that the address signal P ₁ is moved to the register 14. Next 10th
In the step, register 1 of register group RDM1
The address signal _P1 stored in the data memory DMA is selected by the multiplexer 15 in accordance with the selection signal _S4 and sent to the data memory DMA.
Data memory DMA addressed by address signal _P1 stores data _B1 , which is the calculation output stored in register R1A, as data.
It is now stored at the same address where _A1 was stored. This digital data _B1 is
It corresponds to the real part of data β ₁ which is the butterfly calculation output. The next 11th step and 12th step are empty steps for matching the number of steps, and nothing is executed. In this way, the real parts B ₁ and B ₂ of the data β ₁ and β ₂ which are the butterfly operation outputs are calculated. For the final butterfly calculation, the address signal may be selected using the selection signal _S2 or the like in the eighth and tenth steps. By the way, the calculation to obtain the imaginary parts b ₁ and b ₂ of the data β ₁ and β ₂ is performed using the multiplier MPYB and the adder/subtractor
This is performed using ALUB, register R1B, etc., and is performed by the same means as the calculation procedure for obtaining the real parts B ₁ and B ₂ described above. Therefore, the explanation of the procedure for calculating the imaginary parts b ₁ and b ₂ will be omitted. Note that in Table 2, X represents X=cosθ·a ₂ −sinθ·A ₂ . In this way, in the butterfly calculation circuit 1,
Addresses P ₁ of data memories DMA and DMB in which digital data α ₁ and α ₂ to be subjected to butterfly calculation are stored in the first step and third step,
P ₂ is calculated by the address generator AG. Also,
In the second and third steps, addresses Q ₁ and Q ₂ of the coefficient memory CM in which the coefficient k is stored are calculated by the address generation section AG. The addresses P ₁ and P ₂ are stored in the register group RDM1.
Therefore, the calculation of the addresses P ₁ and P ₂ stored in the data memories DMA and DMB of the digital data β ₁ and β ₂ , which are the butterfly operation results, is not performed again in the address generation unit AG, and the eighth step and In the tenth step, it is selected by a selection signal and reused. Therefore, although the data memories DMA, DMB, and coefficient memory CM need to be accessed six times per butterfly operation, the address generator AG only needs to perform address calculations four times. . Therefore, it is possible to increase the signal processing efficiency to 4 steps per butterfly operation without reducing it to 6 steps. In this way, register group RDM1
In the butterfly calculation circuit 1, the first step of the next butterfly calculation can be started when the first four steps are completed, and as described above, the butterfly calculation circuit 1 starts from the fifth step. In the 8th step, the 1st to 4th steps of the next butterfly calculation are performed, and in the 9th to 12th steps, the 5th to 8th steps of the next butterfly calculation, and the next butterfly calculation are performed. The first to fourth steps are each processed in parallel. Next, the configuration of the butterfly calculation circuit 2 shown in FIG. 3, which calculates the butterfly calculation involving 1/2, will be explained. This butterfly calculation circuit 2 is
It has the same configuration as the butterfly calculation circuit 1, except that the registers R4A and R4B provided in the butterfly calculation circuit 1 are not provided, and the register RCM1 is replaced with a register group RCM2. ing. FIG. 4 shows the configuration of the dashed-dotted line portion of the butterfly calculation 2 shown in FIG. In FIG. 4, the register group RCM2 is composed of two registers 20 and 21 forming a two-stage shift register and a multiplexer 22.
0 and 21 are connected to a multiplexer 22, respectively. Further, a control signal, which is the output of the OR circuit 23 to which the capture signal and the clock signal are input, is transmitted to each register 20, 21.
has been entered. The multiplexer 22 receives selection signals t ₁ and t 2 made up of, for example, 1 bit, and the registers 20 and t ₂ are inputted to the multiplexer 22, respectively.
21 outputs are selected. As a result, the address output from the address generator AG is output to the register 20 and
21 and multiplexer 22, it is sent to the coefficient memory CM. Also,
The register group RDM2, which is composed of four registers 24, 25, 26, and 27 constituting a four-stage shift register and a multiplexer 28, has a configuration exactly similar to the register group RDM1 of the butterfly operation circuit 1. ing. These registers 24, 25, 26, and 27 receive a control signal from an OR circuit 29, and send the address output of the address generator AG to the data memories DMA and DMB at appropriate timings via a multiplexer 28. It's starting to become easier. Tables 3 to 5 show the procedure for calculating the butterfly operation with 1/2 times as shown in equation (4) using equation (6) using the butterfly calculation circuit 2 shown in FIG. In this butterfly operation 2, data memory
Digital data α ₁ stored in DMA, DMB,
α ₂ , β ₁ , and β ₂ are designated by addresses P ₁ and P ₂ similarly to the butterfly calculation circuit 1. Also, the coefficient is stored at address Q ₁ of coefficient memory CM.
The real part cos θ/2 of k/2 is stored, and the imaginary part sin θ/2 is stored at address _Q2 . Also, the value 1/2 is stored in another address in the coefficient memory CM, and the register group
The address can be specified at any time without using RCM2.

【table】

【table】

【table】

【table】

〔Effect of the invention〕

As is clear from the above description, according to the present invention, there is provided a data memory for storing digital data based on digital sample values, a coefficient memory for storing coefficients, and address data indicating addresses of the data memory and the coefficient memory. an address generation unit that calculates by calculation, a multiplier and an adder/subtractor that perform multiplication and addition/subtraction on the digital data, and performs a butterfly operation on at least a pair of digital data x ₁ and x ₂ stored in the data memory, In the butterfly calculation circuit that obtains digital data y ₁ and y ₂ as the calculation results, a group of registers (1) which is a storage means for temporarily storing the address signal of the data memory calculated by one address generation part in the address data storage part ( By providing a register group (including a multiplexer) or a register that is a storage means for temporarily storing the address signal of the coefficient memory CM, the address signal used when reading data memory is stored in the register group for a while. , and can be used again without calculating the same address twice, despite requiring 6 accesses to data memory and coefficient memory per butterfly operation.
It is now possible to complete address calculations in the address generation section four times, increasing signal processing efficiency to four steps. Further, the present invention can be realized by adding a much smaller hardware scale than adding one more address generation unit, and can be realized by adding a very small microprogram instruction.

[Brief explanation of the drawing]

FIG. 1 is a block diagram of a butterfly calculation circuit according to the present invention, FIG. 2 is a block diagram showing the portion shown by the dashed-dotted line in FIG. A block diagram of a butterfly calculation circuit for performing butterfly calculations. FIG. 4 is a block diagram showing the portion shown by the chain line in FIG. 3, and FIG. 5 is a block diagram showing another embodiment of the portion shown by the chain line in FIG. 3. CM... Coefficient memory, DMA, DMB... Data memory, MPYA, MPYB... Multiplier, ALUA,
ALUB……Adder/subtractor, R1A, R1B, R2A,
R2B, R3A, R3B, R4A, R4B...Register, AG...Address generation section, RDM1,
RDM2, RDM3...Register group, RCM1,
RCM3...Register, RCM2...Register group,
10, 16...OR circuit, 11, 12, 13, 1
4...Register, 15...Multiplexer, 2
3, 29...OR circuit, 20, 21, 24, 2
5, 26, 27... register, 22, 28... multiplexer, 31, 32, 33, 34... register, 36... multiplexer.

Claims (1)

[Claims] 1. A data memory that stores digital data based on digital sample values, a coefficient memory that stores coefficients, and an address generation unit that calculates address data indicating addresses of the data memory and the coefficient memory by calculation. , has a multiplier and an adder/subtractor that perform multiplication and addition/subtraction on the digital data, performs a butterfly operation on at least a pair of digital data x ₁ and x ₂ stored in the data memory, and obtains digital data y ₁ as a result of the operation. , y ₂ , an address data storage section that stores the address data generated by the address generation section and selectively supplies the stored address data to the data memory as address data. The address data storage section stores and holds address data when the digital data x ₁ and x ₂ are read from the data memory, and the digital data y ₁ and y ₂ that are the calculation results are stored in the data memory. By supplying the stored address data to the data memory when written, the digital data y ₁ that is the result of the operation is stored at the same address as the address from which the digital data x ₁ and x ₂ were read. , y ₂ is written therein.