JPS6027069A - Fourier transform processor - Google Patents

Abstract

PURPOSE:To perform simply a Fourier transform at a high speed and less memory capacity to a data train having the optional bit width, by providing a sequence information generator to a rearranging device to produce the sequence information needed for rearrangement. CONSTITUTION:An output data train delivered from a Fourier transform part 1 is stored to an input memory 2. In this case, the sequence is exchanged with a prescribed relation for said data train. In this respect, the data on the memory 2 are extracted sequentially from the first one and delivered to a rearrangement processor 3 for rearrangement. Furthermore the data delivered from the memory 2 are rearranged and fed to an output memory 4. In this case, the prescribed addresses of the memory 4 are delivered sequentially to the processor 3 from an address generator 6. The procesor 3 writes the data delivered from the memory 2 to the memory 4 by means of the address given from the generator 6. Then the data are rearranged in a regular order.

Description

DETAILED DESCRIPTION OF THE INVENTION Field of Industrial Application The present invention relates to a processing device using a fast Fourier transform algorithm, which plays an important role in the field of digital signal processing. This invention relates to a Fourier transform processing device that reduces the memory capacity of a computer and can be executed simply and at high speed.

Conventional configuration and its problems The fast Fourier transform algorithm performs discrete Fourier transform at high speed. In this algorithm, as a result of conversion, the order of the output data string is reversed with respect to the input data string in a predetermined relationship. Therefore, it is necessary to rearrange this swapped data string into a regular data string.

A conventional method of sorting will be described below. FIG. 1 is a block diagram showing a conventional sorting device.

In FIG. 1, 1 is a Fourier transform unit that performs fast Fourier transform, and 2 is an input memory that stores an output data string after Fourier transform and inputs the data to rearrangement processing device 3. This rearrangement processing device 3 rearranges the data string from the input memory 2 into the output memory 4 based on the address obtained from the address memory 5. Output memory 4 is sorted
The data string from the processing device 3 is stored. The address memory 5 sequentially stores the rearranged addresses and outputs them to the rearrangement processing device 3.

I-E like 11! The operation of the rearranging device thus constructed will be explained below. Now, assuming that the number of data output from the Fourier transform unit 1 is 8 and that the data are stored starting from address 0 in the human memory 2, the data are obtained in the following order, which is not a normal order.

X), X(4), X(2), gravel 5. X(IL
), X(3)', X(7) However, this order needs to be in the regular order as shown below.

X(C), X(1) + X(2) + X(3)
, X(4), X(5), X,(6),
X(7) Then, in order to perform this conversion, addresses at which each data in the input memory 2 should be input to the output memory 4 are sequentially stored in the address memory 5 as shown in FIG.

In rearranging, the data in the input memory 2 is taken out in order starting from address O, and the address where the data should go into the output storage 4 is taken out in order from the address memory 5, and both are rearranged and output to the processing device 3. The rearrangement processing device 3 transfers the data from the input memory 2 to the output memory 4 using the address input from the address memory 5.
write to. In this way, the data string in the input memory 2 becomes a data string in the normal order in the output memory 4, and the rearrangement is completed.

However, in the above-mentioned device, the address memory 6 is required to obtain addresses for sorting, and therefore, as the number of output data increases, the capacity of the memory to store the data must be increased. In addition, it is necessary to increase the capacity of the address memory 5, and a large amount of memory is required. For example, high speed two 1 with 1024 points
, in order to perform one-step conversion, a memory capacity of (1 Kyzo) is required as the address memory 5 just for exchanging data. This is, for example, an LSI (La
rge 5cale Integrated circ
It was not suitable for the development of small-sized signal processing devices, such as those that attempted to perform calculations, control, and storage on a single chip (large-scale integrated circuit). By generating the addresses necessary for sorting using software and inputting the results to the address memory 6 or the sorting processing device 3,
Is there a known method to generate a normally ordered output data string? If such a method is used, complex operations must be performed to generate the address, which results in a loss of speed. had.

In addition, address generation for this sorting can be done by performing bit inversion corresponding to the bit width of a given data string, but if only a bit inversion circuit with a fixed bit width is used, the bit width of the data string cannot be generated. , 7) The width is fixed, so there is a drawback that only a fixed number of data can be Fourier transformed.

OBJECT OF THE INVENTION The present invention solves the above-mentioned conventional problems, and allows the operation of rearranging the output data string whose order has been changed as a result of fast Fourier transform to the original order at high speed and with a small memory capacity. Moreover, it is an object of the present invention to provide a novel Fourier transform processing device that can easily perform a data string of any bit width.

Composition of the Invention The present invention includes a Fourier transform unit that performs fast Fourier transform on an input data string, and stores the input data string or the processed data string obtained in each step of the Fourier transform or the output data string after the Fourier transform process. a memory, a rearranging device for rearranging the data string in the memory so that it becomes an output data string after Fourier transformation or a data string in a normal order, and generating order information necessary for rearranging to the rearranging device. A sequence information generating device 9111 is installed, and the sequence information generating device, an address register, an increment register table for modifying the address register, and the outputs of the address register and increment register are used as inputs to perform addition, and the result is added to the address register again. and a bit inverting circuit that performs bit inversion by symmetrically exchanging the negative bit and the least significant bit in order from the most significant bit and the least significant bit with respect to the output of the adder, and Information regarding the number of bits to be bit-inverted is input to the register, and i, j: v is input to the address register.
The feature is that information regarding the address to be entered when the first data string in the memory is arranged in the order of first glance is inputted as the J period value, and fast Fourier transform is performed. Embodiments of the present invention have the advantage that the procedure for rearranging data that has been swapped by An example will be explained with reference to the drawings. FIG. 2 is a block diagram of a Fourier transform processing device in one embodiment of the present invention. In FIG. 2, 1 is a Fourier transform unit that performs fast Fourier transform, and 2 is an input memory that stores the output gator sequence after Fourier transform and inputs the data to rearrangement processing device 3. This rearrangement processing device 3 rearranges the gators based on addresses obtained from an address generation device 6, which will be described later. 4 is an output memory for storing data from the rearrangement processing device 3, and 6 is an address generator that sequentially generates rearranged addresses.

The operation of the Fourier transform processing device configured as above will be explained below. The output data string outputted from the Fourier transform unit 1 (d is stored in the input memory 2. This data string has the order changed in a certain predetermined relationship.
Therefore, when rearranging the data, the data on the input memory 2 is taken out in order from the most side data, and the rearrangement processing device 3
The predetermined addresses which should be outputted from the input memory 2 and entered into the output memory 4 after the h gaters are exchanged are sequentially outputted from the address generation device 6 to the rearrangement processing device 3. In the rearrangement processing device 3, the gator outputted from the input storage 2 is written into the output memory 4 using the address also outputted from the address generation device 6. In this way, the gator strings whose order has been changed in the input memo 1) and 2 are rearranged in the output memory 4 into the normal order.

Next, the address generation device 6, which is a feature of the present invention, will be explained. The third part is a detailed block diagram of this address generator 6. In Figure 3, 7 is an address register, 8
is an increment register for modifying address register 7,
9 is an adder that inputs the outputs of address register 7 and increment register 8 and adds to both; 10 is a lunch that holds the output of adder 9 and inputs the value to address register 7; 11 is an adder This is an address generating node which carries the output data of the converter 9 and gives an address to the rearrangement processing device 3 through the digital inversion circuit 12. Inferior throat inversion circuit 1
2 symmetrically swaps the upper focus and lower bits of the address generation node 11 in order from the least significant bit and the least significant bit.

Regarding the bit inversion circuit 12, if the address generation bus 11 is, for example, 1Q bits, the circuit will be as shown in FIG. In Figure 4, 12a is the most significant bit on the input side, 12b is the least significant bit on the input side, 12C is the most significant bit on the output side, and 12d is the least significant bit on the output side. The most significant bit 12C and the least significant bit 12d75 on the output side; respectively the least significant bit (by hand) 1
2b and the highest second position on the input side) 12a.

The operation of this embodiment configured as above will be described below.

Now, it is assumed that the number of data that is Fourier transformed and outputted by the Fourier transform unit 1 is s (= 23) pieces, the bit width of each block of the address generator 6 shown in FIG. 3 is 1Q bits, and the input memory 2 is - Set the address of the first data of L2 to address 0. Regarding bit inversion, let's write the value obtained by inverting 10 bits of the 10-bit value a as d, for example, a = 1110000000 (2
) then (2). (Here, (2) indicates a binary number) This is the fourth
It can be easily realized using the inverting circuit shown in the figure.

At this time, the data string in input memory 2 before the swapping is as shown in Figure 2, and it is necessary to rearrange it into the normal order as shown in output memory 40 in Figure 2. Focusing on the lower bits of a certain 1° address, one piece of data in input memory 2 before rearrangement is transferred to output memory 3 by bit-inverting the lower 3 bits of the address 1/s that contains that data in input memory 2. You can see what you need to do by entering the address. Therefore, the address generator 6 generates "ooo, 1oo, olo, ilo, ool, 1o1.
oll, 111'' (2) must be generated in this order. Therefore, the address generator 6 generates this address by the following operation.

Enter the following value in the address register 7 as the initial 1st shift, x=1110000000e) At the same time, input the following value y into the increment register 8, y=o○1000oOoo(2) In this way, X and y are added by adder 9,
As a result, xy is held in chip 10 and then input to address register 7, and the value of the address register becomes a new value X+7-0000000000 B). on the other hand,
The output x + y of the adder 9 is input to the bit inversion circuit 12, and the output x + y is as follows.

X + y=OOOOOOOOOOOO0 (2) This is the address at which the first data enters the output memory 4''2.

Furthermore, the next address output can be seen as follows. That is, the value of address register 7 at this point is x+y-0000
0000〇0(2) is newly added to X + 2 V after the value y of the increment register 8 is added again by the power generator 9 and held in the latch 10.
= OO10000000 (2>. At the same time, the output x + 27 of the adder 9 passes through the bit inversion circuit 12, and the next output of the address generator 6 is x + 2' y = OOOOOOOO'1 0 0
(2) becomes.

In this way, the value y of the increment register 8 is added one after another to the value of the new address register 7, and as a result, all bits are passed through the inversion circuit 12, and the address outputs are generated in the following order. Understand X + 37-0000000010(2)X +47
= OOOOOOOl) 110(2)x + 5y
= OOOO00°) t) Q 1 (2)x+6
y=ooo○OOt') 101 (2)X+7; =
OOOO000011(2) x 187 = OOO
O(1') 011 '1(2) In the above description of this embodiment, the initial address of the output memory 4 was set to Q, but the present invention is not limited to this, and the number of data to be Fourier transformed is set to 8. However, it is not limited to this.

In this embodiment, if the number of data to be Fourier transformed is generally N (-2m), in order to generate the address necessary for the rearrangement performed by the rearrangement device 3, it is necessary to perform bit inversion of the lower m bits. Therefore, in this case,
Incremental register 8Vc vs. y-210-m (23m≦1
Q) is input and the output data is hidden by 11 strokes (from address 1-4 of output memo 1-4 in Figure 2 to address (k-1-N-1)). The value x = k - Y is assigned as the initial shift.Then, as mentioned above, the value of the address register 7 and the value of the increment register 8 are added by the adder 9, and the output of the adder 9 is used as the address. This is used as a new value in the register 7, and is also used as an address output to the rearrangement processing device 3 through the bit inversion circuit 12.

As described above, according to this embodiment, the address generation device 6 is provided with the address register 7, the increment register 8, the adder 9, and the bit inversion circuit 12, thereby performing one bit inversion edge generation of an arbitrary number of bits. Kokichi is created, and even in arbitrary scale Fourier transform processing, for the rearrangement processing device 3,
Addresses necessary for rearrangement can be generated quickly, without requiring any memorization, and moreover, easily.

In this embodiment, the bit width of each block of the address generating device 6 was explained as 1Q bits, but these bit widths are limited to this value. It can be set to any value depending on the scale etc.

In this embodiment, a case has been described in which the data string after Fourier transform is rearranged, but the present invention is not limited to this, and the data before Fourier transform may be rearranged (also, fast Fourier transform). Processing data at each step during conversion may be rearranged 1. This is because:
This is because in fast Fourier transform, a Fourier coefficient sequence in the normal order is finally obtained no matter what stage of the process the rearrangement is performed.

Furthermore, although the case of fast Fourier transform has been described as an application example of the present invention, the present invention is not limited to this.
It can also be applied to the case of fast Fourier inverse transform.

Effects of the Invention As described above, the Fourier transform processing device of the present invention includes a Fourier transform unit that performs fast Fourier transform, and a memory that stores data strings whose order needs to be rearranged by performing fast Fourier transform. a rearrangement device that rearranges the data string in the memory so that the output data string after Fourier transform becomes a data string in a normal order; and an order information generator that generates order information necessary for rearrangement to the rearrangement device. a device, the order information generating device modifies an address register and the address register. It has an increment register, an adder that inputs the address register name and the output of the increment register, performs addition, and inputs the result back to the address register, and a bit inversion circuit that performs bit inversion on the output of the adder. However, the bit reversal operation for rearranging the data string permuted by Fourier transform into the normal order can be performed for any bit width by simply performing addition and bit reversal1.The Fourier transform of the present invention The processing device can perform the above-mentioned reordering process at a high speed and with less energy consumption, without requiring a memory for storing reordering addresses like the conventional 1+lJ, regardless of the bit width of the data to be converted. It has extremely excellent advantages.

[Brief explanation of the drawings] Figure 1 is a block diagram of a conventional sorting device;
FIG. 3 is a block diagram of a Fourier transform processing device according to an embodiment of the present invention, FIG. 3 is a block diagram of an address generation device in the same embodiment, and FIG. 4 is a circuit diagram of a bit inversion circuit in the address generation device. 1...Fourier transform unit, 2 m/input memory,
3'... Sorting device, 6... Address generator, '7... Address register, 8...
Increment register, 9... Adder, 11...
Address generation bus, 12...Bit inversion same section. Name of agent: Patent attorney Toshio Nakao (1st person)
Figure 3 Figure 3 4 [゛, □1 Procedural amendment 1985 ξ Month 〆 O day % i'F Jr &"'Zゝ Representation of 1 case to the 1980 1h Permit No. 1.34587. 2. Name of the invention Fourier transform processing device 3. Person doing the correction 1. Relationship with 1. Patent application Col. Tomari Kadoma City, Osaka Bold key y < too 6 jya Name (582) Representative of Matsushita Electric Industrial Co., Ltd. Person: Toshihiko Yamashita 4 Agent Address: 1006 IF, Bold Kadoma, Kadoma City, Osaka Prefecture 571 IF!! Matsushita Electric Industrial Co., Ltd., Figure 4

Claims (1)

[Claims] a Fourier transform unit that performs fast Fourier transform on an input data string; a memory that stores the input data string or the processed data string obtained in each step of the Fourier transform process or the output data string after the Fourier transform process; a reordering device that rearranges the data strings so that the output data strings after Fourier transform become data strings in a regular order; and a sequence information generating device that generates order information required for the reordering for the reordering device. The order information generating device includes an address register, an increment register that modifies the address register, and an adder that receives the outputs of the address register and the increment register as input, performs addition, and outputs the result to the address register again. A bit inversion circuit is provided for performing bit inversion by symmetrically exchanging the upper and lower bits in order from the most significant bit and the least significant bit for the output of the adder, and the increment register contains bits to be bit inverted. Information regarding the number is inputted, and information regarding the address to be entered when the first data string in the memory is in the correct order is input to the address register as an initial value. Fourier transform device.