[go: up one dir, main page]

WO2011102291A1 - 高速フーリエ変換回路 - Google Patents

高速フーリエ変換回路 Download PDF

Info

Publication number
WO2011102291A1
WO2011102291A1 PCT/JP2011/052844 JP2011052844W WO2011102291A1 WO 2011102291 A1 WO2011102291 A1 WO 2011102291A1 JP 2011052844 W JP2011052844 W JP 2011052844W WO 2011102291 A1 WO2011102291 A1 WO 2011102291A1
Authority
WO
WIPO (PCT)
Prior art keywords
data
memory
fourier transform
fast fourier
stage
Prior art date
Application number
PCT/JP2011/052844
Other languages
English (en)
French (fr)
Inventor
剛 橋本
Original Assignee
日本電気株式会社
株式会社エヌ・ティ・ティ・ドコモ
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 日本電気株式会社, 株式会社エヌ・ティ・ティ・ドコモ filed Critical 日本電気株式会社
Priority to US13/579,184 priority Critical patent/US20130046806A1/en
Priority to EP11744578A priority patent/EP2538345A1/en
Priority to JP2012500571A priority patent/JPWO2011102291A1/ja
Priority to CN2011800097694A priority patent/CN102763101A/zh
Publication of WO2011102291A1 publication Critical patent/WO2011102291A1/ja

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/10—Complex mathematical operations
    • G06F17/14—Fourier, Walsh or analogous domain transformations, e.g. Laplace, Hilbert, Karhunen-Loeve, transforms
    • G06F17/141—Discrete Fourier transforms
    • G06F17/142—Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm

Definitions

  • the present invention relates to a fast Fourier transform circuit that processes a Fourier transform at high speed.
  • Cooley-Tukey-type fast Fourier transform In the Cooley-Tukey-type fast Fourier transform (hereinafter simply referred to as “fast Fourier transform”), generally, a calculation is performed using a two-point DFT (Digital Fourier Transform Discrete Fourier Transform) as a constituent element (cited documents 1 to 3). reference).
  • a two-point DFT Digital Fourier Transform Discrete Fourier Transform
  • radix-4 fast Fourier transform an operation using a 4-point DFT as a constituent element
  • the data number N needs to be a power of 2
  • the data number N needs to be a power of 4.
  • An object of the present invention is to solve such problems and to provide a fast Fourier transform circuit capable of reading and writing data processed at individual stages of fast Fourier transform at high speed without dividing a memory.
  • the fast Fourier transform circuit of the present invention includes a computation unit that performs a fast Fourier computation including a plurality of digital Fourier transforms, a memory that stores input / output data of the computation unit, and a computation unit for processing target data. And a means for controlling the writing of the calculation result to the memory by the calculation unit so that the reading order of the data from the memory is the same in each stage for a plurality of stages of calculations to be performed.
  • the present invention it is possible to read and write data processed by individual stages of fast Fourier transform at high speed without dividing the memory, and to increase the speed while suppressing an increase in LSI area.
  • FIG. 1 is a block configuration diagram showing a fast Fourier transform circuit according to a first embodiment of the present invention. It is a signal flow figure explaining operation
  • FIG. 5 is a diagram illustrating a flow of processing for writing data from a write buffer to a memory. It is a figure explaining the flow of the process of the data by the fast Fourier transform circuit shown in FIG.
  • FIG. 5 is a diagram illustrating a flow of processing for writing data from a write buffer to a memory. It is a figure explaining the flow of the process of the data by the fast Fourier transform circuit shown in FIG.
  • FIG. 5 is a diagram illustrating a flow of processing for writing data from a write buffer to a memory. It is a figure explaining the flow of the process of the data by the fast Fourier-transform circuit shown in FIG.
  • FIG. 5 is a diagram illustrating a flow of processing for writing data from a write buffer to a memory. It is a figure explaining the flow of the process of the data by the fast Fourier transform circuit shown in FIG.
  • FIG. 5 is a diagram illustrating a flow of processing for writing data from a write buffer to a memory. It is a figure explaining the flow of the process of the data by the fast Fourier transform circuit shown in FIG. 1, and is a figure which shows the flow of the process of writing the data from the write buffer to the memory when the process of the first stage is completed.
  • FIG. 20 is a diagram illustrating a calculation configuration example of a 2-point / 4-point DFT calculation unit in the fast Fourier transform circuit illustrated in FIG. 19.
  • FIG. 19 performs the first stage operation, data is read from the memory, stored in the read buffer, and 2-point / 4-point DFT operation section. It is a figure which shows the flow of a process of the calculation by, and the storage of the calculation result to the write buffer.
  • FIG. 20 is a diagram illustrating a flow of a process of writing data from the write buffer to the memory when the 2-point / 4-point DFT operation unit in the fast Fourier transform circuit illustrated in FIG. 19 performs the first stage operation.
  • the 2-point / 4-point DFT operation section in the fast Fourier transform circuit shown in FIG. 19 performs the second stage operation, data is read from the memory, stored in the read buffer, and 2-point / 4-point DFT operation section.
  • FIG. 20 is a diagram showing a flow of processing of writing data from the write buffer to the memory when the 2-point / 4-point DFT operation unit in the fast Fourier transform circuit shown in FIG. 19 performs the second stage operation.
  • the 2-point / 4-point DFT computation unit in the fast Fourier transform circuit shown in FIG. 19 performs the third stage computation
  • the computation result of the 2-point / 4-point DFT computation unit is stored in the write buffer, and the write buffer
  • the write buffer It is a figure which shows the flow of a process of writing the data from memory to memory. It is a figure which shows the example of whole structure of the communication system using an OFDM system, and is a figure which shows only the structure regarding communication of one direction.
  • the fast Fourier transform circuit includes a four-point DFT operation unit 1, memories 2A and 2B, a read buffer 3, a write buffer 4, a selector 5, a rotator generation unit 6, and a control unit 7.
  • the read buffer 3 has a configuration of B complex data ⁇ (N / B) ⁇ 2 banks, stores data read from the memories 2A and 2B, and stores 4-point DFT operation unit 1 for each radix B data. Output to. Since the read buffer 3 has a 2-bank configuration for N complex data, the data is output to the 4-point DFT operation unit 1 in the other bank while data is read from the memories 2A and 2B in one bank. Can do.
  • the write buffer 4 has a B complex data ⁇ (N / B) ⁇ 2 bank configuration, stores the calculation results of each stage by the 4-point DFT calculation unit 1, and writes them in the memories 2A and 2B. Since the write buffer 4 is composed of two banks for N complex data, the calculation result from the four-point DFT operation unit 1 is received in the other bank while writing to the memories 2A and 2B in one bank. Can do.
  • the selector 5 selects the read / write destination of the memories 2A and 2B. That is, control is performed so that one of the memories 2A and 2B is a reading side and the other is a writing side. Reading and writing to the same memory 2A or 2B do not occur at the same time.
  • the rotor generation unit 6 generates a rotor that multiplies the output of the 4DFT calculation unit 1.
  • the rotor is a well-known matter in the field of fast Fourier transform, and the description thereof is omitted here.
  • the multiplication of the rotor, which is the output of the rotor generation unit 16, and the output of the 4-point DFT calculation unit 15 is performed before writing to the write buffer 4. It may be done when writing.
  • the control unit 7 performs reading of the memories 2A and 2B, generation of a write address, generation of addresses of the read buffer 3 and the write buffer 4, and a plurality of stages of calculations performed by the calculation unit on the processing target data.
  • the calculation unit writes data to the memory so that the reading order of data from the memory is the same in each stage.
  • the control unit 7 also performs the generation control of the rotor in the rotor generation unit 6, and the management and control of the number of times and the processing stage of the 4-point DFT calculation unit.
  • an input memory and an output memory can be provided separately.
  • the selector 12 is configured to be able to access these memories.
  • One DFT operation processing group is called a stage, and is designated as a first stage, a second stage,..., A P stage from the input side.
  • the number of stages P 2
  • four 4-point DFT operations are performed at each stage.
  • Cooley-Tukey-type fast Fourier transform can take two types of configurations, a time-thinning type and a frequency-thinning type, depending on how it is decomposed into two-point or four-point DFT.
  • a fast Fourier transform which is a radix-4 frequency decimation type configuration, will be described as an example.
  • FIG. 3 is a diagram for explaining the configuration of a four-point DFT in a radix-4 fast Fourier transform.
  • the output complex data X ′ (m) is expressed as follows.
  • j is an imaginary unit.
  • FIG. 4 is a diagram for explaining a general example of storing complex data in a memory.
  • Data is stored in one physical address of the memory (the contents of a plurality of addresses can be read continuously by designating one address).
  • four complex data A i , A i + 1 , A i + 2 , and A i + 3 from the right are stored in one physical address B (i / 4). If it does not become complicated, the storage place is not particularly limited.
  • description will be made assuming that the data is stored as shown in FIG.
  • the following write address WA (S, k, m) and read address RA (S, k, m) will be described as addresses where individual complex data are stored.
  • the write address WA (S, k, m) is calculated by the following formula.
  • a mod b indicates that a remainder is obtained when a is divided by b.
  • the converted data is rearranged in ascending order by using the address calculated in this way and taking out the address stored in the memory after the end of the final stage (P stage) by bit reverse.
  • FIG. 6 is a diagram for explaining a method of calculating a write address to the memories 2A and 2B in the fast Fourier transform circuit shown in FIG.
  • control unit 1 sets the write address and the read address of the memories 2A and 2B, and the 4-point DFT operation unit 1 performs the data number N to the power of the radix B.
  • writing to the memories 2A and 2B is performed in the order of addresses that can be read from the memory at the same address.
  • data for N / 4 addresses of the memories 2A and 2B can be stored in one bank.
  • these banks are referred to as bank # 0 and bank # 1.
  • the 4-point DFT processing is performed by the 4-point DFT calculation unit 1 using the data stored in the read buffer 3 in this way.
  • the read buffer 3 holds data for N / 4 times of four-point DFT processing.
  • the next four-point DFT processing N / 4 times of data are read from the memories 2A and 2B and stored in the other bank of the read buffer 3. Since four complex data are stored in one address of the memories 2A and 2B, data corresponding to one 4-point DFT process can be read from the memories 2A and 2B in one cycle. Since data for one 4-point DFT process can be read from the memories 2A and 2B simultaneously with the DFT process, the 4-point DFT process can be executed in one cycle.
  • the address of the write buffer 4 is wn
  • the data for N / 4 times of the 4-point DFT processing in the 4-point DFT operation unit 1 needs to be stored in the read buffer 3. For this reason, in the four cycles immediately after the start of each stage, the processing by the 4-point DFT operation unit 1 is not performed, and data necessary for the processing is read from the memories 2A and 2B and stored in the read buffer 3. After reading 4 ⁇ (N / 4) complex data, the bank of the read buffer 3 is switched, and data is read from the memories 2A and 2B and stored in the read buffer 3. At the same time, data is read from the other bank of the read buffer 3 and processing by the 4-point DFT operation unit 1 is executed.
  • the write buffer 4 does not write to the memories 2A and 2B until the results of four times of the 4-point DFT processing are stored. After the start of processing, when the results for 4 points DFT processing N / 4 times are stored, the write buffer 4 switches the bank and stores the DFT processing result following the bank after switching. In parallel with this, the write buffer 4 writes the DFT processing result stored in the other bank into the memories 2A and 2B.
  • the minimum execution cycle is N / 4 + 4 ⁇ 2 cycles.
  • control unit 7 controls each unit and starts processing from the first stage.
  • the selector 5 switches the connection so as to read from the memory 2A in which the input data is stored.
  • FIG. 7 is a diagram showing a flow of processing for reading data from the memory 2A to be read and storing it in the read buffer 13.
  • data required for calculation in the 4-point DFT calculation unit 1 is not complete until 4 words (16 complex data) are read from the memory 2A. For this reason, the calculation by the 4-point DFT calculation unit 1 is not performed, and only the data is stored in the read buffer 3.
  • FIG. 8 to FIG. 11 are diagrams showing the flow of processing of reading data from the memory 2A, storing it in the read buffer 3, calculating by the 4-point DFT calculation unit 1, and storing the calculation result in the write buffer 4, respectively. is there.
  • the 4-point DFT operation unit 1 sequentially performs 4-point DFT operations (FIG. 8).
  • the calculation results z (1, 0) to z (1, 3) of the 4-point DFT operation are stored in the write buffer 4, and at the same time, the data necessary for the next 4-point DFT operation is read from the memory 2A word by word, and the read buffer 3 is stored. It is assumed that at least one word (4 complex data) is read from the memory 2A and stored in the read buffer 3 for one 4-point DFT operation.
  • the read buffer 3 has a memory. Data x (4) to x (7) for at least one word from 2A is stored.
  • FIG. 16 is a diagram showing a flow of a process of writing data from the write buffer 4 to the memory 2B when the first stage process is completed.
  • N the number of 4-point DFT operations
  • data z (1,48) to z (1,60) not yet written in the memory 2B is stored in the write buffer 4 for 4 words (16 complex). Data) is left. This data is sequentially written into the memory, and the first stage processing is completed (FIG. 16).
  • FIG. 17 is a diagram for explaining the writing of data to the memory 2A in the second stage.
  • FIG. 18 is a diagram for explaining the writing of data to the memory 2B in the third stage.
  • the selector 5 switches the connection for each stage, reads data from the memory 2B or 2A in which the calculation result is stored in the previous stage, performs the calculation, and stores the result in the other memory 2A or 2B. Store. Therefore, in this case, data is written in the memory 2A in the second stage, and data is written in the memory 3A in the third stage.
  • the method of writing the calculation result of the 4-point DFT to the write buffer 4 is different from the first stage.
  • the data write address to the memory 2A or 2B is N / 4 PS + 1 interval according to the equation (3).
  • the address (address for storing one complex data) interval is 4 in the second stage and 16 in the third stage.
  • the read buffer 3 and the write buffer 3 and the write buffer can be obtained by devising a method for arranging complex data in the memories 2A and 2B and a method for writing the output of the 4-point DFT operation unit 1 to the memories 2A and 2B.
  • a buffer 4 is introduced. This eliminates the need to unnecessarily divide the memories 2A and 2B even when performing a four-point DFT in one cycle.
  • a decoding circuit and a test circuit added to the memories 2A and 2B are not required, and the circuit scale can be reduced. For example, when each of the memories 2A and 2B is divided into four, a decoding circuit and a test circuit for six memories are required, but according to the present embodiment, such a circuit can be reduced.
  • the number of memories can be reduced to about 1/4 when performing physical placement at the time of LSI manufacture, and the layout becomes easy. Thereby, area saving (reduction of chip cost) can be realized.
  • FIG. 19 is a block diagram showing a fast Fourier transform circuit according to the second embodiment of the present invention.
  • the fast Fourier transform circuit shown in FIG. 19 includes memories 2A and 2B, a read buffer 3, a write buffer 4, a selector 5, a rotator generation unit 6, a 2-point / 4-point DFT calculation unit 11, and a control unit 12.
  • the memories 2A and 2B, the read buffer 3, the write buffer 4, the selector 5, and the rotator generation unit 6 are the same as those shown in FIG.
  • the 2-point / 4-point DFT calculation unit 11 can execute one 4-point DFT calculation or two 2-point DFT calculations in one cycle. The control is performed by the control unit 12.
  • FIG. 20 is a diagram illustrating a calculation configuration example of the 2-point / 4-point DFT calculation unit 11 in the fast Fourier transform circuit illustrated in FIG.
  • the first stage is composed of two two-point DFTs, and the second and subsequent stages are composed of four-point DFT operations.
  • FIG. 21 is a diagram showing a configuration diagram of a two-point DFT used in the first stage processing.
  • the outputs X ′ (m) of the two two-point DFTs are expressed as follows.
  • X ′ (m) and x ′ (m) are complex numbers, and j is an imaginary unit.
  • the value obtained by dividing the number of data N by the value P ⁇ S + 1 to the power of m, and the value obtained by dividing the value of B by the power of S ⁇ 1 and dividing the value twice the order k by the power of B Is set to a value obtained by multiplying the value obtained by multiplying the half of the value of B by the value obtained by dividing the value of k in order by the half of the value obtained by multiplying B to the S-1 power.
  • the control unit 12 is configured to multiply the read address RA (S, k, m) from the memories 2A and 2B in each of all P stages by the value obtained by dividing the number of data N by the value of B and m, A value obtained by adding the value of the order k is set.
  • the write address is as follows, unlike Equation (3).
  • the read address is the same as in equation (4).
  • the storage address of the data read from the memories 2A and 2B in the read buffer 3 is the same as that in Expression (6).
  • the write address to the write buffer 4 varies depending on the processing stage as follows. a) Write address to the write buffer 4 in the first stage b) Write address to the write buffer in the second stage c) Write address to the write buffer in the third stage and thereafter The same as the equation (8).
  • FIG. 26 is a diagram showing a flow of processing for writing data from the write buffer 4 to the memory 2B in the first stage.
  • the word stored in the write buffer 4 is stored in the memory 2B in one word in parallel with the writing of the results of the fifth to eighth 2-point DFT operations by the 2-point / 4-point DFT operation unit 11 into the write buffer 4.
  • Write (4 complex data) one by one. After the eight 2-point DFT operations are completed, the data stored in the write buffer is written into the memory B. At this time, the write address interval to the memory 2B is 1.
  • FIGS. 22 to 26 are diagrams equivalent to FIGS. 22 to 26 for explaining the operation in the second stage, respectively. Since the operation of the second stage is the same as the operation of the first stage described with reference to FIGS. 22 to 26 except that the write address to the write buffer 4 is different, the description is omitted.
  • FIG. 32 is a diagram showing a flow of processing of storing the calculation result of the 2-point / 4-point DFT calculation unit 11 in the write buffer 4 and writing data from the write buffer 4 to the memory 2B in the third stage.
  • the operation in this case is the same as the operation of the first embodiment described with reference to FIGS. 8 to 16 except that the interval of the write address to the memory 2B is expressed by the following equation. Is omitted.
  • frequency decimation type fast Fourier transform has been described as an example, but the present invention can also be implemented by time decimation type fast Fourier transform.
  • orthogonal frequency division multiplexing which is a radio access method with high frequency utilization efficiency, has been used to improve communication speed.
  • wireless LAN Local Area Network
  • mobile communication LTE (Long Term Evolution), which is being standardized with a new communication method in 3GPP (Third Generation Partnership Project), and OFDM. Is adopted.
  • FIG. 33 is a diagram illustrating an example of the overall configuration of a communication system using the OFDM method. Here, for the sake of simplicity, only the configuration related to one-way communication is shown.
  • This communication system includes a base station 101.
  • the base station 101 includes an encoder 102, a modulator 103, an OFDM signal generator, a D / A converter 105, and a plurality of antennas 106 (only one is shown in the figure).
  • the communication system also includes a mobile station 111 such as a user terminal that communicates with the base station 101.
  • the mobile station 111 includes a decoding unit 112, a demodulation unit 113, an OFDM signal demodulation unit 114, an A / D conversion unit 115, and a plurality of antennas 116 (only one is shown in the figure).
  • a CPU (not shown) of the base station 101 inputs data to be transmitted to the encoding unit 102 as information bits.
  • the encoding unit 102 performs CRC (Cyclic Redundancy Check) addition and convolutional encoding on the input information bits.
  • the modulation unit 103 modulates the input code data.
  • the OFDM signal generation unit 104 maps the modulated data on the frequency axis, and converts the data on the frequency axis into data on the time axis by inverse digital Fourier transform.
  • the converted data is output to the D / A converter 105.
  • the D / A conversion unit 105 converts the digital signal output from the OFDM signal generation unit 104 into an analog signal. Then, the modulated data converted into the analog signal is transmitted via the plurality of antennas 106.
  • the mobile station 111 on the receiving side receives data transmitted from the antenna 106 on the transmitting side 101 via the plurality of antennas 116.
  • the data received by the antenna 116 is affected by noise when propagating through space after being output from the antenna 106.
  • Data received by the antenna 116 is input to the A / D converter 115.
  • the A / D converter 115 converts input data from an analog signal to a digital signal.
  • a / D conversion section 115 outputs the converted digital signal to OFDM signal demodulation section 114.
  • the OFDM signal demodulator 114 converts the digital signal on the time axis output from the A / D converter 115 into data on the frequency axis by digital Fourier transform and maps it on the IQ plane.
  • the demodulator 113 demodulates the data output from the OFDM signal demodulator 114.
  • Demodulation section 113 outputs the demodulated data obtained by demodulation to decoding section 112.
  • the decoding unit 112 performs error correction decoding on the input demodulated data. Using the decoded data obtained as a result, a processing circuit such as a CPU at a subsequent stage performs a predetermined process.
  • DFT digital Fourier transform
  • LTE the number of subcarriers in the 20 MHz band is 1200.
  • DFT it is necessary to perform 1,199 complex multiplications and complex additions 1200 times. Moreover, this must be done within 66.67 microseconds of one OFDM symbol period.
  • Cooley-Tukey type fast Fourier transform As an algorithm for reducing the amount of calculation, for example, the above-described Cooley-Tukey type fast Fourier transform is used.
  • the amount of computation in the case of 1200 subcarriers is 2048 complex multiplications and complex additions + (3 complex additions and 1 complex multiplication 2048 times) ⁇ 5 times It becomes.
  • the number of data needs to be a power of 2. Therefore, 2048 which is larger than 1200 and the smallest power of 2 is the number of data.
  • the rotator that is subject to complex multiplication may be represented by only the real part or only the imaginary part, so the number of multiplications may be smaller. However, there is still no change in the amount of computation.
  • the amount of calculation can be reduced by performing a fast Fourier transform with a 4-point DFT as a component.
  • input / output data is generally stored in a memory.
  • the four-point DFT it is necessary to take out four complex data serving as inputs from the memory.
  • the memory is a single port, four cycles are required.
  • the former increases the area of the memory cell itself, and the latter leads to an increase in area due to the test circuit or decoder circuit associated with the memory macro.
  • dividing the memory increases the number of wirings by four times, increasing the difficulty of layout design at the time of manufacturing the LSI, and may increase the LSI area so that wiring is possible.
  • the present invention can be used for a measuring apparatus that performs Fourier transform, such as a spectrum analyzer.

Landscapes

  • Physics & Mathematics (AREA)
  • Mathematical Physics (AREA)
  • Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Computational Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • Data Mining & Analysis (AREA)
  • Theoretical Computer Science (AREA)
  • Discrete Mathematics (AREA)
  • Algebra (AREA)
  • Databases & Information Systems (AREA)
  • Software Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • Complex Calculations (AREA)

Abstract

メモリを分割することなく、高速フーリエ変換の個々のステージの演算で処理されるデータを高速に読み出し・書き込みできる高速フーリエ変換回路を提供する。複数のデジタルフーリエ変換を構成要素とする高速フーリエ演算を行う演算部（１）と、演算部（１）の入出力データを格納するメモリ（２Ａ、２Ｂ）と、処理対象のデータに対して演算部（１１）が行う複数ステージの演算に対して、メモリ（２Ａ、２Ｂ）からのデータの読み出し順が各ステージで同じとなるように、演算部（１１）による演算結果のメモリ（２Ａ、２Ｂ）への書き込みを制御する手段（７）とを有する。

Description

高速フーリエ変換回路
　本発明は、フーリエ変換を高速に処理する高速フーリエ変換回路に関する。
　クーリー・チューキー型の高速フーリエ変換（以下、単に「高速フーリエ変換」という）では、一般的に、２点ＤＦＴ（デジタルフーリエ変換Ｄｉｓｃｒｅｔｅ　Ｆｏｕｒｉｅｒ　Ｔｒａｎｓｆｏｒｍ）を構成要素として演算が行われる（引用文献１～３参照）。また、さらに高速に処理を行うために、４点ＤＦＴを構成要素とする演算（基数４の高速フーリエ変換）も可能である。ただし、基数２の高速フーリエ変換は、データ数Ｎが２のべき数である必要があり、基数４の高速フーリエ変換は、データ数Ｎが４のべき数である必要がある。
　高速化のために、データ数Ｎが２のべき乗の場合には、２点ＤＦＴと４点ＤＦＴとを組み合わせて処理することも可能である。
特開２００６－１５５４８７号公報 特開２００７－１４８６２３号公報 特表２００４－５１６５５１号公報
　高速フーリエ変換において、メモリ上に格納されている複素データを処理する場合、基数４の高速フーリエ変換では、１回の４点ＤＦＴにつき４複素データをメモリから読み取り、演算の結果出力される４複素データをメモリに書き込む必要がある。
　一般的な高速フーリエ変換処理では、各ステージの演算において、メモリに対する読み出し、書き込みのアドレス間隔が変わるため、４データを同時に読み出し、書き込みを行うことができない。このため、１回の４点ＤＦＴを処理するのに必要なサイクル数として、シングルポートメモリを使用した場合には、４サイクルが必要になる。
　シングルポートメモリでも、４個のデータを同時に読み書きできるように、４分割することも考えられる。しかし、ＬＳＩ化する際は、メモリマクロに付加されるテスト回路などにより、分割する個数が多いほど必要面積が大きくなると同時に、配置の難易度が上がってしまう。このため、実装率が上がらず、チップ面積が大きくなってしまう。
　本発明は、このような課題を解決し、メモリを分割することなく、高速フーリエ変換の個々のステージの演算で処理されるデータを高速に読み出し・書き込みできる高速フーリエ変換回路を提供することを目的とする。
　本発明の高速フーリエ変換回路は、複数のデジタルフーリエ変換を構成要素とする高速フーリエ演算を行う演算部と、演算部の入出力データを格納するメモリと、処理対象のデータに対して演算部が行う複数ステージの演算に対して、メモリからのデータの読み出し順が各ステージで同じとなるように、演算部による演算結果のメモリへの書き込みを制御する手段とを有することを特徴とする。
　本発明によると、メモリを分割することなく、高速フーリエ変換の個々のステージの演算で処理されるデータを高速に読み出し・書き込みでき、ＬＳＩ面積の増加を抑えつつ高速化を図ることができる。
本発明の第１の実施の形態に係る高速フーリエ変換回路を示すブロック構成図である。 図１に示す高速フーリエ変換回路中の４点ＤＦＴ演算部の動作を説明するシグナルフロー図である。 基数４の高速フーリエ変換における４点ＤＦＴの構成を説明する図である。 複素データのメモリへの格納例を説明する図である。 メモリへの書き込みアドレスの従来の計算方法を説明する図である。 図１に示す高速フーリエ変換回路中のメモリへの書き込みアドレスの計算方法を説明する図である。 図１に示す高速フーリエ変換回路によるデータの処理の流れを説明する図であり、読み出し対象となるメモリからデータを読み出してリードバッファに格納する処理の流れを示す図である。 図１に示す高速フーリエ変換回路によるデータの処理の流れを説明する図であり、メモリからのデータの読み出し、リードバッファへの格納、４点ＤＦＴ演算部による演算、および演算結果のライトバッファへの格納の処理の流れを示す図である。 図１に示す高速フーリエ変換回路によるデータの処理の流れを説明する図であり、メモリからのデータの読み出し、リードバッファへの格納、４点ＤＦＴ演算部による演算、および演算結果のライトバッファへの格納の処理の流れを示す図である。 図１に示す高速フーリエ変換回路によるデータの処理の流れを説明する図であり、メモリからのデータの読み出し、リードバッファへの格納、４点ＤＦＴ演算部による演算、および演算結果のライトバッファへの格納の処理の流れを示す図である。 図１に示す高速フーリエ変換回路によるデータの処理の流れを説明する図であり、メモリからのデータの読み出し、リードバッファへの格納、４点ＤＦＴ演算部による演算、および演算結果のライトバッファへの格納の処理の流れを示す図である。 図１に示す高速フーリエ変換回路によるデータの処理の流れを説明する図であり、メモリからのデータの読み出し、リードバッファへの格納、４点ＤＦＴ演算部による演算、演算結果のライトバッファへの格納およびライトバッファからメモリへのデータの書き込みの処理の流れを示す図である。 図１に示す高速フーリエ変換回路によるデータの処理の流れを説明する図であり、メモリからのデータの読み出し、リードバッファへの格納、４点ＤＦＴ演算部による演算、演算結果のライトバッファへの格納およびライトバッファからメモリへのデータの書き込みの処理の流れを示す図である。 図１に示す高速フーリエ変換回路によるデータの処理の流れを説明する図であり、メモリからのデータの読み出し、リードバッファへの格納、４点ＤＦＴ演算部による演算、演算結果のライトバッファへの格納およびライトバッファからメモリへのデータの書き込みの処理の流れを示す図である。 図１に示す高速フーリエ変換回路によるデータの処理の流れを説明する図であり、メモリからのデータの読み出し、リードバッファへの格納、４点ＤＦＴ演算部による演算、演算結果のライトバッファへの格納およびライトバッファからメモリへのデータの書き込みの処理の流れを示す図である。 図１に示す高速フーリエ変換回路によるデータの処理の流れを説明する図であり、第１ステージの処理完了時におけるライトバッファからメモリへのデータの書き込み処理の流れを示す図である。 図１に示す高速フーリエ変換回路によるデータの処理の流れを説明する図であり、第２ステージにおけるメモリへのデータの書き込みを説明する図である。 図１に示す高速フーリエ変換回路によるデータの処理の流れを説明する図であり、第３ステージにおけるメモリへのデータの書き込みを説明する図である。 本発明の第２の実施の形態に係る高速フーリエ変換回路を示すブロック構成図である。 図１９に示す高速フーリエ変換回路中の２点／４点ＤＦＴ演算部の演算構成例を示す図である。 図１９に示す高速フーリエ変換回路中の２点／４点ＤＦＴ演算部が第１ステージの処理で使用する２点ＤＦＴの構成図を示す図である。 図１９に示す高速フーリエ変換回路中の２点／４点ＤＦＴ演算部が第１ステージの演算を行う際の、メモリからのデータの読み出し、リードバッファへの格納、２点／４点ＤＦＴ演算部による演算、および演算結果のライトバッファへの格納の処理の流れを示す図である。 図１９に示す高速フーリエ変換回路中の２点／４点ＤＦＴ演算部が第１ステージの演算を行う際の、メモリからのデータの読み出し、リードバッファへの格納、２点／４点ＤＦＴ演算部による演算、および演算結果のライトバッファへの格納の処理の流れを示す図である。 図１９に示す高速フーリエ変換回路中の２点／４点ＤＦＴ演算部が第１ステージの演算を行う際の、メモリからのデータの読み出し、リードバッファへの格納、２点／４点ＤＦＴ演算部による演算、および演算結果のライトバッファへの格納の処理の流れを示す図である。 図１９に示す高速フーリエ変換回路中の２点／４点ＤＦＴ演算部が第１ステージの演算を行う際の、メモリからのデータの読み出し、リードバッファへの格納、２点／４点ＤＦＴ演算部による演算、および演算結果のライトバッファへの格納の処理の流れを示す図である。 図１９に示す高速フーリエ変換回路中の２点／４点ＤＦＴ演算部が第１ステージの演算を行う際の、ライトバッファからメモリへのデータの書き込みの処理の流れを示す図である。 図１９に示す高速フーリエ変換回路中の２点／４点ＤＦＴ演算部が第２ステージの演算を行う際の、メモリからのデータの読み出し、リードバッファへの格納、２点／４点ＤＦＴ演算部による演算、および演算結果のライトバッファへの格納の処理の流れを示す図である。 図１９に示す高速フーリエ変換回路中の２点／４点ＤＦＴ演算部が第２ステージの演算を行う際の、メモリからのデータの読み出し、リードバッファへの格納、２点／４点ＤＦＴ演算部による演算、および演算結果のライトバッファへの格納の処理の流れを示す図である。 図１９に示す高速フーリエ変換回路中の２点／４点ＤＦＴ演算部が第２ステージの演算を行う際の、メモリからのデータの読み出し、リードバッファへの格納、２点／４点ＤＦＴ演算部による演算、および演算結果のライトバッファへの格納の処理の流れを示す図である。 図１９に示す高速フーリエ変換回路中の２点／４点ＤＦＴ演算部が第２ステージの演算を行う際の、メモリからのデータの読み出し、リードバッファへの格納、２点／４点ＤＦＴ演算部による演算、および演算結果のライトバッファへの格納の処理の流れを示す図である。 図１９に示す高速フーリエ変換回路中の２点／４点ＤＦＴ演算部が第２ステージの演算を行う際の、ライトバッファからメモリへのデータの書き込みの処理の流れを示す図である。 図１９に示す高速フーリエ変換回路中の２点／４点ＤＦＴ演算部が第３ステージの演算を行う際の、２点／４点ＤＦＴ演算部の演算結果のライトバッファへの格納、およびライトバッファからメモリへのデータの書き込みの処理の流れを示す図である。 ＯＦＤＭ方式を用いた通信システムの全体構成例を示す図であり、一方向の通信に関する構成のみを示す図である。
　以下、図面を参照して本発明の実施の形態について説明する。
　［第１の実施の形態］
　図１は本発明の第１の実施の形態に係る高速フーリエ変換回路を示すブロック構成図である。ここでは、高速フーリエ変換の基数Ｂ＝４の場合の構成例を示す。
　この高速フーリエ変換回路は、４点ＤＦＴ演算部１、メモリ２Ａ、２Ｂ、リードバッファ３、ライトバッファ４、セレクタ５、回転子生成部６および制御部７を備える。
　４点ＤＦＴ演算部１は、基数Ｂ＝４のデジタルフーリエ変換を構成要素とする高速フーリエ演算を行う。
　メモリ２Ａ、２Ｂは、データ数Ｎが基数Ｂのべき数のデータに対して４点ＤＦＴ演算部１が行うＰ＝ｌｏｇＢＮステージの演算のそれぞれの入出力データ、および中間値を格納する。これらのメモリ２Ａ、２Ｂは、Ｎ複素データ分を格納する容量をもち、１アドレスに４複素データを格納することができる。
　リードバッファ３は、Ｂ個の複素データ×（Ｎ／Ｂ）×２バンク構成を有し、メモリ２Ａ、２Ｂから読み出されたデータを格納し、基数Ｂのデータごとに４点ＤＦＴ演算部１に出力する。リードバッファ３がＮ個の複素データに対して２バンク構成なので、一方のバンクでメモリ２Ａ、２Ｂからデータを読み出している間に、他方のバンクで４点ＤＦＴ演算部１へデータを出力することができる。
　ライトバッファ４は、Ｂ複素データ×（Ｎ／Ｂ）×２バンク構成を有し、４点ＤＦＴ演算部１による各ステージの演算結果を格納し、メモリ２Ａ、２Ｂに書き込む。ライトバッファ４がＮ複素データに対して２バンク構成なので、一方のバンクでメモリ２Ａ、２Ｂへの書き込みを行っている間に、他方のバンクで４点ＤＦＴ演算部１からの演算結果を受け取ることができる。
　セレクタ５は、メモリ２Ａ、２Ｂの読み出し、書き込み先を選択する。すなわち、メモリ２Ａ、２Ｂの一方が読み出し側で、他方が書き込み側となるように制御する。同一のメモリ２Ａまたは２Ｂに対して同時に読み出しと書き込みが生じることはない。
　回転子生成部６は、４ＤＦＴ演算部１の出力に乗じる回転子を生成する。回転子については、高速フーリエ変換の分野ではよく知られた事項であり、ここでは説明を省略する。図６に示す例では、回転子生成部１６の出力である回転子と４点ＤＦＴ演算部１５の出力との乗算を、ライトバッファ４に書き込む前に行っているが、ライトバッファ４からメモリに書き込むときに行ってもよい。
　制御部７は、メモリ２Ａ、２Ｂの読み出し、書き込みアドレスの生成、リードバッファ３およびライトバッファ４のアドレスの生成を行い、処理対象のデータに対して演算部が行う複数ステージの演算に対して、メモリからのデータの読み出し順が各ステージで同じとなるように、演算部による演算結果のメモリへの書き込みを制御する。制御部７はまた、回転子生成部６における回転子の生成制御、および４点ＤＦＴ演算部の回数および処理ステージの管理ならびに制御を行う。
　メモリＡ１０、メモリＢ１１の他に、入力メモリ、出力メモリを別々に設けることもできる。その場合、セレクタ１２は、それらのメモリに対してアクセスできるような構成をとる。
　［高速フーリエ変換の説明］
　図２は、図１に示す高速フーリエ変換回路中の４点ＤＦＴ演算部１の動作を説明するシグナルフロー図である。ここでは、基数Ｂ＝４、データ数Ｎ＝１６の場合を示す。
　クーリー・チューキー型の高速フーリエ変換は、データ数をＮ（Ｎは基数Ｂのべき乗）とすると、Ｐ＝ｌｏｇＢＮ回のＤＦＴ演算処理群に分解される。１回のＤＦＴ演算処理群をステージと呼び、入力側から第１ステージ、第２ステージ、・・・、第Ｐステージとする。基数Ｂ＝４、データ数Ｎ＝１６の場合には、ステージ数Ｐ＝２であり、それぞれのステージで４つの４点ＤＦＴ演算が行われる。
　クーリー・チューキー型の高速フーリエ変換は、２点あるいは４点ＤＦＴへの分解のしかたによって、時間間引き型と周波数間引き型の２種類の構成をとりうることが知られている。ここでは、基数４の周波数間引き型の構成である高速フーリエ変換を例にとって説明する。
　図３は、基数４の高速フーリエ変換における４点ＤＦＴの構成を説明する図である。４点ＤＦＴでは、４点の複素データｘ’（ｍ）、ｍ＝０，１，２，３に対して、４点の複素データＸ’（ｍ）を出力する。出力される複素データＸ’（ｍ）は、以下の通り表されるものとする。ここで、ｊは虚数単位である。
Figure JPOXMLDOC01-appb-M000001
  
 
　なお、図２および図３を参照して説明した高速フーリエ変換は、一般的なものである。
　［メモリへのデータ格納方法］
　図４は、複素データのメモリへの一般的な格納例を説明する図である。１複素データを１アドレスに格納した場合のアドレスをＡｉ（ｉ＝０，１，…，（Ｎ－１）、Ｎはデータ数（ＦＦＴポイント数））とするとき、連続する４個の複素データをメモリの１物理アドレス（ひとつのアドレスを指定することで、複数のアドレスの内容を連続的に読み出すことができる）に格納する。図４に示す例では、右からＡｉ，Ａｉ+1，Ａｉ+2，Ａｉ+3の４複素データを１物理アドレスＢ（ｉ／４）に格納しているが、回路構成が複雑にならなければ、格納する場所は特に限定されるものではない。以下では、簡単のため、図４に示すとおりに格納されるものとして説明する。
　［メモリへの書き込み・読み出しアドレス］
　図５は、メモリへの書き込みアドレスの従来の計算方法を説明する図である。ここでは、基数Ｂ＝４に対してデータ数Ｎ＝１６の場合を示す。
　周波数間引き型高速フーリエ変換において、第Ｓ（Ｓ＝１，２，…，Ｐ）ステージにおけるＤＦＴ演算の出力データは、一般的には以下のように格納される。入力データ系列ｘ（ｎ）は、時間軸上で昇順になるように、メモリの最下位アドレス側から格納されているものとする。ここで、以降の書き込みアドレスＷＡ（Ｓ，ｋ，ｍ）、読み出しアドレスＲＡ（Ｓ，ｋ，ｍ）は、個々の複素データが格納されるアドレスとして説明する。ｋは４点ＤＦＴ演算の順番を示すもので、ｋ＝０～（Ｎ／４－１）とする。
　書き込みアドレスＷＡ（Ｓ，ｋ，ｍ）は、以下の式で算出される。ここで、ｍ＝０，１，２，３であり、４点ＤＦＴのため、１回のＤＦＴ演算で４複素データが出力される。
Figure JPOXMLDOC01-appb-M000002
 　（ａ　ｍｏｄ　ｂ）は、ａをｂで割ったときの余りを取ることを示す。Ｎ＝１６の例は図２に示したとおりである。このとき、読み出しアドレスＲＡ（Ｓ，ｋ，ｍ）は、ＲＡ（Ｓ，ｋ，ｍ）＝ＷＡ（Ｓ，ｋ，ｍ）となる。
　このように計算されるアドレスを用い、最終ステージ（Ｐステージ）終了後のメモリに格納されているアドレスをビットリバースして取り出すことによって、変換後のデータが昇順に並べ替えられる。
　図６は、図１に示す高速フーリエ変換回路中のメモリ２Ａ、２Ｂへの書き込みアドレスの計算方法を説明する図である。
　図１に示す実施の形態において、制御部１は、メモリ２Ａ、２Ｂの書き込みアドレスおよび読み出しアドレスを設定し、データ数Ｎが基数Ｂのべき数のデータに対して４点ＤＦＴ演算部１が行うＰ＝ｌｏｇＢＮステージの演算に対して、次のステージでの演算対象となるデータが高速フーリエ演算の順番ｋ＝０，１,・・，Ｎ／Ｂ－１に対してデータ数Ｎを基数Ｂで割った値ごとに同じアドレスでメモリから読み出すことのできるアドレス順に、メモリ２Ａ、２Ｂへの書き込みを行う。
　具体的には、制御部１は、第Ｓ＝１，２，・・，Ｐステージのそれぞれにおけるライトバッファ４からメモリ２Ａまたは２Ｂへの書き込みアドレスＷＡ（Ｓ，ｋ，ｍ）、ただしｍ＝０，１，・・，Ｂ－１、を、基数Ｂを残りステージ数に１を加えた値Ｐ－Ｓ＋１乗した値でデータ数Ｎを割った値にｍを乗じた値と、基数ＢをＳ－１乗した値で順番ｋの値を割った値に基数ＢのＳ乗を乗じた値と、基数ＢをＳ－１乗した値で順番ｋの値を割っときの余りの値とを加算した値に設定する。また、第Ｓ＝１，２，・・，Ｐステージのそれぞれにおけるメモリ２Ｂまたは２Ａからリードバッファ３への読み出しアドレスＲＡ（Ｓ，ｋ，ｍ）を、基数Ｂでデータ数Ｎを割った値にｍを乗じた値と、順番ｋの値とを加算した値に設定する。
　基数Ｂ＝４の場合の書き込みアドレスＷＡ（Ｓ，ｋ，ｍ）を式で表すと、次のようになる。
Figure JPOXMLDOC01-appb-M000003
　また、基数Ｂ＝４の場合の読み出しアドレスＲＡ（Ｓ，ｋ，ｍ）を式で表すと、次のようになる。
Figure JPOXMLDOC01-appb-M000004
　このように計算されるアドレスを用いることで、ビットリバース処理が不要となり、各ステージでのＤＦＴ演算の読み出しアドレスを一定にすることができ、リードバッファ３およびライトバッファ４の導入が可能になる。また、基数Ｂ＝２のＤＦＴと基数Ｂ＝４のＤＦＴとを組み合わせた構成を容易にとることができる。
　［リードバッファ、ライトバッファ］
　リードバッファ３およびライトバッファ４は、それぞれともに２バンク構成で、１バンク当たり、Ｎ個の複素データを格納できる容量を有し、基数Ｂ＝４で４複素データをメモリ２Ａ、２Ｂの１アドレスに格納する場合に、１バンクにメモリ２Ａ、２ＢのＮ／４アドレス分のデータを格納できる構成となっている。説明のため、これらのバンクをバンク＃０、バンク＃１とする
　１ステージ分のＤＦＴ処理を開始するに際し、メモリ２Ａ、２Ｂの４アドレス分のデータを読み出し、リードバッファ３の一方のバンクに格納しておく。メモリ２Ａ、２ＢのアドレスＢｉに対する読み出しデータをＲＤ（Ｂｉ’）とするとき、ＲＤ（Ｂｉ’）には、４複素データが含まれる。これを、図３に示すＡｉを用いて、以下のように表現するものとする。
Figure JPOXMLDOC01-appb-M000005
　リードバッファ３のバンク番号をｒｂ（＝｛０，１｝）、リードバッファ３のアドレス（１複素データ分）をｒｎとするとき、ｋ番目のＤＦＴ処理実行時のリードバッファ３のデータＲＢ（ｒｂ，ｒｎ）は、以下で表される。
Figure JPOXMLDOC01-appb-M000006
　このように格納されたリードバッファ３のデータを使用して、４点ＤＦＴ演算部１で４点ＤＦＴ処理を行う。リードバッファ３には、４点ＤＦＴ処理Ｎ／４回分のデータが保持されている。４点ＤＦＴ処理を実行するのと並行して、次の４点ＤＦＴ処理Ｎ／４回分のデータをメモリ２Ａ、２Ｂから読み出し、リードバッファ３のもう一方のバンクに格納する。メモリ２Ａ、２Ｂの１アドレスに４複素データを格納しているため、１サイクルで４点ＤＦＴ処理１回分に相当するデータをメモリ２Ａ、２Ｂから読み出すことができる。４点ＤＦＴ処理１回分のデータを、ＤＦＴ処理と同時にメモリ２Ａ、２Ｂから読み出すことが可能となるため、４点ＤＦＴ処理を１サイクルで実行することが可能となる。
　書き込み側も同様である。１回の４点ＤＦＴ処理で出力される４複素データをライトバッファ４の一方のバンクに格納し、もう一方のバンクに格納されている４複素データ分をメモリ２Ａ、２Ｂに書き込む。１回のＤＦＴ処理実行中に、１回のメモリへの書き込みが実現できる。
　ライトバッファ４のバンク番号をｗｂ（＝｛０，１｝）、ライトバッファ４のアドレスをｗｎ、ｋ番目のＤＦＴ処理の出力データをＸ’（ｋ、ｍ）（ｍ＝｛０，１，２，３｝）とするとき、ライトバッファ４のデータＷＢ（ｗｂ，ｗｎ）は、以下で表される。
（ａ）Ｓ＝１のとき
Figure JPOXMLDOC01-appb-M000007
 （ｂ）Ｓ≧２のとき
Figure JPOXMLDOC01-appb-M000008
　各ステージとも、４点ＤＦＴ演算部１における４点ＤＦＴ処理Ｎ／４回分のデータが、リードバッファ３に格納されている必要がある。このため、各ステージの開始直後の４サイクルは、４点ＤＦＴ演算部１による処理は行わず、その処理に必要なデータをメモリ２Ａ、２Ｂから読み出して、リードバッファ３に格納する。４×（Ｎ／４）複素データ分の読み出し終了後、リードバッファ３のバンクを切り替え、メモリ２Ａ、２Ｂからのデータの読み出しと、リードバッファ３への格納を行う。これと同時に、リードバッファ３のもう一方のバンクからデータを読み出し、４点ＤＦＴ演算部１による処理を実行する。
　ライトバッファ４は、４点ＤＦＴ処理４回分の結果が格納されるまで、メモリ２Ａ、２Ｂへの書き込みは行わない。処理開始後、４点ＤＦＴ処理Ｎ／４回分の結果が格納されたら、ライトバッファ４は、バンクを切り替え、切り替え後のバンクに続くＤＦＴ処理結果を格納していく。それと並行して、ライトバッファ４は、もう一方のバンクに格納されているＤＦＴ処理結果をメモリ２Ａ、２Ｂに書き込む。
　１ステージ分の処理では、メモリ２Ａ、２Ｂからリードバッファ３への読み出しと、メモリ２Ａ、２Ｂへのライトバッファ４の書き込みとに、それぞれ４サイクルが必要である。このため、最小の実行サイクルは、Ｎ／４＋４×２サイクルとなる。
　［詳細な動作の説明］
　図７から図１８は、図１に示す高速フーリエ変換回路によるデータの処理の流れを説明する図である。これらの図を参照して、高速フーリエ変換回路の動作を詳細に説明する。ここでは、Ｎ＝６４の場合を例に説明する。以下の動作は、制御部７が各部を制御することにより実行される。処理の対象となる入力データは、メモリ２Ａに格納されているものとする。
　メモリ２Ａに入力データが格納されると、制御部７は、各部を制御し、第１ステージから処理を開始する。セレクタ５は、入力データが格納されているメモリ２Ａから読み出しを行うように、接続を切り替える。
　図７は、読み出し対象となるメモリ２Ａからデータを読み出して、リードバッファ１３に格納する処理の流れを示す図である。処理開始直後、メモリ２Ａから４ワード分（１６複素データ）が読み出されるまでは、４点ＤＦＴ演算部１での演算に必要なデータは揃わない。このため、４点ＤＦＴ演算部１による演算は行わず、リードバッファ３へのデータの格納のみを行う。
　図８から図１１はそれぞれ、メモリ２Ａからのデータの読み出し、リードバッファ３への格納、４点ＤＦＴ演算部１による演算、および演算結果のライトバッファ４への格納の処理の流れを示す図である。
　メモリ２Ａから最初の４ワード分のデータｘ（０）～ｘ（３）、ｘ（１６）～ｘ（１９）、ｘ（３２）～ｘ（３５）、ｘ（４８）～ｘ（５１）が読み出されてリードバッファ３に格納されたら、４点ＤＦＴ演算部１により、４点ＤＦＴ演算を順次行う（図８）。４点ＤＦＴ演算の演算結果ｚ（１，０）～ｚ（１，３）をライトバッファ４に格納すると同時に、メモリ２Ａから次の４点ＤＦＴ演算に必要なデータを１ワードずつ読み出し、リードバッファ３に格納する。１回の４点ＤＦＴ演算につき、メモリ２Ａから最低１ワード(４複素データ)分のデータを読み出し、リードバッファ３に格納するものとする。すなわち、４点ＤＦＴ演算部１が最初の４点のデータｘ（０）、ｘ（１６）、ｘ（３２）、ｘ（４８）の処理を行っているときに、リードバッファ３には、メモリ２Ａからの最低１ワード分のデータｘ（４）～ｘ（７）を格納する。
　以下同様に、４点ＤＦＴ演算部１による演算と、その演算結果のライトバッファ４への格納と、メモリ２Ａからの読み出しと、リードバッファ３への格納を順次行う（図９～図１１）。
　図１２から図１５はそれぞれ、メモリ２Ａからのデータの読み出し、リードバッファ３への格納、４点ＤＦＴ演算部１による演算、演算結果のライトバッファ４への格納およびライトバッファ４からメモリ２Ｂへのデータの書き込みの処理の流れを示す図である。処理開始時点からライトバッファ４にＮ／４＝１６複素データ分の結果が格納された後、ライトバッファ４からメモリ２Ｂに、書き込みを行う。４複素データ分を、メモリ２Ｂの１ワードに順次書き込む。この際、４点ＤＦＴ演算処理、メモリ２Ａからのデータの読み出しおよびリードバッファ３への格納は、並行して行うものとする。
　以上の動作を、４点ＤＦＴ演算回数がＮ／４回になるまで繰り返す。
　図１６は、第１ステージの処理完了時におけるライトバッファ４からメモリ２Ｂへのデータの書き込み処理の流れを示す図である。４点ＤＦＴ演算回数がＮ／４回に達したとき、ライトバッファ４には、メモリ２Ｂにまだ書き込まれていないデータｚ（１，４８）～ｚ（１，６０）が、４ワード(１６複素データ)分残っている。このデータを順次メモリに書き込み、第１ステージの処理を完了する（図１６）。
　以上にて説明した動作を、第２ステージから第Ｐステージまで繰り返し、ＦＦＴ処理を完了する。
　図１７は、第２ステージにおけるメモリ２Ａへのデータの書き込みを説明する図である。また、図１８は、第３ステージにおけるメモリ２Ｂへのデータの書き込みを説明する図である。第２ステージ以降は、ステージごとにセレクタ５が接続を切り替え、その前のステージで演算結果が蓄えられたメモリ２Ｂまたは２Ａからデータを読み出して演算を行い、その結果を他方のメモリ２Ａまたは２Ｂに格納する。したがって、この場合には、第２ステージではメモリ２Ａにデータが書き込まれ、第３ステージではメモリ３Ａにデータが書き込まれる。
　第２ステージ以降は、式（８）に示したとおり、４点ＤＦＴの演算結果のライトバッファ４への書き込み方が、第１ステージとは異なる。そして、メモリ２Ａまたは２Ｂへのデータの書き込みアドレスは、式（３）にしたがって、Ｎ／４Ｐ－Ｓ+１間隔となる。この例ではＮ＝６４であり、Ｐ＝ｌｏｇ４６４＝３なので、第２ステージではアドレス（１複素データを格納するアドレス）間隔は４となり、第３ステージでは１６となる。
　なお、図８～図１８中のｚ（Ｓ，４×ｋ＋ｉ）、ただしｋ＝０～（Ｎ／４－１）、ｉ＝０～３は、ｋ番目の４点ＤＦＴの出力であることを示す。
　図７から図１８を参照した説明では、処理の対象となる入力データが、メモリ２Ａに格納されているものとしたが、入力データがメモリ２Ｂに格納されている場合にも、演算結果をメモリ２Ａに書き込むものとして、同様に処理することができる。また、図１に示す高速フーリエ変換回路は、４点ＤＦＴ演算部１の出力をライトバッファに書き込む際に、回転子生成部６の生成した回転子を乗算しているが、これに関しては、高速フーリエ変換の分野では自明のことであるため、説明は省略した。
　［効果］
　以上説明した実施の形態においては、複素データのメモリ２Ａ、２Ｂへの配置方法と、４点ＤＦＴ演算部１の出力のメモリ２Ａ、２Ｂへの書き込み方法を工夫することで、リードバッファ３およびライトバッファ４を導入している。これによって、１サイクルで４点ＤＦＴを行う場合においても、メモリ２Ａ、２Ｂを不必要に分割する必要がなくなる。メモリ２Ａ、２Ｂに付加するデコード回路やテスト回路が不要となり、回路規模削減が可能となる。たとえば、メモリ２Ａ、２Ｂをそれぞれ４分割した場合、メモリ６個分のデコード回路とテスト回路が必要となるが、本実施の形態によれば、そのような回路を削減することが可能となる。
　さらに、メモリ個数を減らすことによって、ＬＳＩ製作時の物理配置を行う際、配線数を約１／４にすることができ、レイアウトが容易になる。これにより、省面積性（チップコストの削減）を実現することができる。
　［第２の実施の形態］
　図１９は、本発明の第２の実施の形態に係る高速フーリエ変換回路を示すブロック構成図である。この実施の形態の基本的な構成は、第１の実施の形態と同等である。ただし、Ｂ／２＝２のべき乗ではあるが、Ｂ＝４のべき乗ではないデータ数Ｎ（ｌｏｇ２Ｎが奇数）の高速フーリエ変換処理を実行できる構成となっていることが異なる。
　図１９に示す高速フーリエ変換回路は、メモリ２Ａ、２Ｂ、リードバッファ３、ライトバッファ４、セレクタ５、回転子生成部６、２点／４点ＤＦＴ演算部１１および制御部１２を備える。メモリ２Ａ、２Ｂ、リードバッファ３、ライトバッファ４、セレクタ５、回転子生成部６は図１に示したものと同じであり、以下では説明を省略する。２点／４点ＤＦＴ演算部１１は、１回の４点ＤＦＴ演算、または２回の２点ＤＦＴ演算を１サイクルで実行できる。その制御は、制御部１２により行う。
　図２０は、図１９に示す高速フーリエ変換回路中の２点／４点ＤＦＴ演算部１１の演算構成例を示す図である。データ数Ｎの高速フーリエ変換は、Ｐ＝ｌｏｇ2（Ｎ／２）＋１回のＤＦＴ演算処理群（ステージ）に分解される。図２０に示す例では、第１ステージをふたつの２点ＤＦＴで構成し、第２ステージ以降を４点ＤＦＴ演算で構成する。
　図２１は、第１ステージの処理で使用する２点ＤＦＴの構成図を示す図である。ここで、ふたつの２点ＤＦＴの出力Ｘ’（ｍ）は、以下の通りに表すものとする。Ｘ’（ｍ）、ｘ’（ｍ）は複素数であり、ｊは虚数単位である。
Figure JPOXMLDOC01-appb-M000009
　この構成において、制御部１２は、Ｐ＝ｌｏｇＢ/２（Ｎ／２）＋１ステージのそれぞれにおいて、次のステージでの演算対象となるデータが高速フーリエ演算の順番ｋ＝０，１,・・，Ｎ／Ｂ－１に対してデータ数ＮをＢの値で割った値ごとに同じアドレスでメモリから読み出すことのできるアドレス順に、メモリへの書き込みを行う。
　具体的には、制御部１２は、Ｂ／２点のデジタルフーリエ変換を２組実行するステージにおけるメモリ２Ａ、２Ｂへの書き込みアドレスＷＡ（Ｓ，ｋ，ｍ）、ただしｍ＝０，１，・・，Ｂ－１、を、ｍ＝０，１，．．，Ｂ／２－１のときにはｋの２倍にｍを加算した値、ｍ＝Ｂ／２，．．，Ｂ－１のときにはＮ／２とｋの２倍とｍ－Ｂ／２とを加算した値に設定する。また、制御部１２は、Ｂ点のデジタルフーリエ変換を実行するステージのそれぞれにおけるメモリ２Ａ、２Ｂへの書き込みアドレスＷＡ（Ｓ，ｋ，ｍ）を、Ｂの値を残りステージ数に１を加えた値Ｐ－Ｓ＋１乗した値でデータ数Ｎを割った値にｍを乗じた値と、Ｂの値をＳ－１乗した値で順番ｋの２倍の値を割った値にＢのＳ乗の半分の値を乗じた値と、ＢをＳ－１乗した値の半分の値で順番ｋの値を割ったときの余りの値とを加算した値に設定する。さらに、制御部１２は、全Ｐステージのそれぞれにおけるメモリ２Ａ、２Ｂからの読み出しアドレスＲＡ（Ｓ，ｋ，ｍ）を、Ｂの値でデータ数Ｎを割った値にｍを乗じた値と、順番ｋの値とを加算した値に設定する。
　図２０に示す構成の場合には、第１ステージでは２組の２点ＤＦＴ演算を行うため、書き込みアドレスが、式（３）とは異なり、以下の通りとなる。読み出しアドレスは式（４）と同じである。
Figure JPOXMLDOC01-appb-M000010
　第２ステージ以降は４点ＤＦＴによる演算であるが、書き込みアドレスは式（３）と異なり、以下の通りとなる（Ｓ≧２）。読み出しアドレスは、第１ステージ同様、式（４）と同じである。
Figure JPOXMLDOC01-appb-M000011
　メモリ２Ａ、２Ｂから読み出したデータのリードバッファ３への格納アドレスは、式（６）と同じである。ライトバッファ４への書き込みアドレスは、以下のように、処理ステージによって異なる。
ａ）第１ステージにおけるライトバッファ４への書き込みアドレス
Figure JPOXMLDOC01-appb-M000012
 ｂ）第２ステージにおけるライトバッファへの書き込みアドレス
Figure JPOXMLDOC01-appb-M000013
 ｃ）第３ステージ以降におけるライトバッファへの書き込みアドレス
　式（８）と同じ。
　［動作例］
　これらのアドレスを用いた動作例を図２２から図３２を参照して説明する。以下の説明では、データ数Ｎ＝３２とする。
　図２２から図２５はそれぞれ、第１ステージにおけるメモリ２Ａからのデータの読み出し、リードバッファ３への格納、２点／４点ＤＦＴ演算部１１による演算、および演算結果のライトバッファ４への格納の処理の流れを示す図である。
　まず、２点ＤＦＴ処理開始前に、メモリ２Ａから最初の４ワード分のデータｘ（０）～ｘ（３）、ｘ（８）～ｘ（１１）、ｘ（１６）～ｘ（１９）、ｘ（２４）～ｘ（２７）を読み出して、リードバッファ３に格納する。この後、これらのデータに対して２点／４点ＤＦＴ演算部１１により２点ＤＦＴ演算を行うとともに、メモリ２Ａから次のデータｘ（４）～ｘ（７）を読み出し、リードバッファ３に格納する。２点／４点ＤＦＴ演算部１１の演算結果は、ライトバッファ４に格納する（以上、図２２）。以下同様に、メモリ２Ａから１ワード（４複素データ）ずつ読み出してリードバッファ３に格納し、２点／４点ＤＦＴ演算部１１により２点ＤＦＴ演算を行い、演算結果をライトバッファ４に格納する（図２３から図２５）。
　図２６は、第１ステージにおけるライトバッファ４からメモリ２Ｂへのデータの書き込みの処理の流れを示す図である。
　２点／４点ＤＦＴ演算部１１による５回目から８回目の２点ＤＦＴ演算の結果をライトバッファ４に書き込むのと並行して、メモリ２Ｂに、ライトバッファ４に格納されているデータを１ワード（４複素データ）ずつ書き込む。８回の２点ＤＦＴ演算終了後、メモリＢにライトバッファに格納されているデータを書き込む。このとき、メモリ２Ｂへの書き込みアドレス間隔は１となっている。
　図２７から図３１はそれぞれ、第２ステージにおける動作を説明する図２２から図２６と同等の図である。第２ステージの動作は、ライトバッファ４への書き込みアドレスが異なることを除いて、図２２から図２６を参照して説明した第１ステージの動作と同じであるので、説明を省略する。
　図３２は、第３ステージにおける２点／４点ＤＦＴ演算部１１の演算結果のライトバッファ４への格納、およびライトバッファ４からメモリ２Ｂへのデータの書き込みの処理の流れを示す図である。この場合の動作は、メモリ２Ｂへ書き込みアドレスの間隔が次式で表されることを除いて、図８から図１６を参照して説明した第１の実施形態の動作と同じであるので、説明を省略する。
Figure JPOXMLDOC01-appb-M000014
　以上の説明では、周波数間引き型の高速フーリエ変換を例に説明したが、時間間引き型の高速フーリエ変換でも本発明を実施することができる。
　近年、無線通信分野では、通信速度向上のため、周波数利用効率の高い無線アクセス方式である直交波周波数分割多重（ＯＦＤＭ；Ｏｒｔｈｏｇｏｎａｌ　Ｆｒｅｑｕｅｎｃｙ　Ｄｉｖｉｓｉｏｎ　Ｍｕｌｔｉｐｌｅｘｉｎｇ）が用いられている。地上波デジタル放送、無線ＬＡＮ（Ｌｏｃａｌ　Ａｒｅａ　Ｎｅｔｗｏｒｋ）をはじめとし、移動体通信においても、３ＧＰＰ（Ｔｈｉｒｄ　Ｇｅｎｅｒａｔｉｏｎ　Ｐａｒｔｎｅｒｓｈｉｐ　Ｐｒｏｊｅｃｔ　）において新しい通信方式での標準化が進められているＬＴＥ（Ｌｏｎｇ　Ｔｅｒｍ　Ｅｖｏｌｕｔｉｏｎ）でも、ＯＦＤＭが採用されている。
　図３３は、ＯＦＤＭ方式を用いた通信システムの全体構成例を示す図である。ここでは、説明を簡単にするため、一方向の通信に関する構成のみを示す。
　この通信システムは、基地局１０１を備える。基地局１０１は、符号化部１０２、変調部１０３、ＯＦＤＭ信号生成部、Ｄ／Ａ変換部１０５および複数のアンテナ１０６（図ではひとつのみ示す）を備える。この通信システムはまた、基地局１０１と通信を行うユーザ端末などの移動局１１１を備える。移動局１１１は、復号部１１２、復調部１１３、ＯＦＤＭ信号復調部１１４、Ａ／Ｄ変換部１１５および複数のアンテナ１１６（図ではひとつのみ示す）を備える。
　基地局１０１では、たとえば基地局１０１のＣＰＵ（不図示）が、送信したいデータを情報ビットとして符号化部１０２に入力する。符号化部１０２は、入力された情報ビットに対し、ＣＲＣ（Ｃｙｃｌｉｃ　Ｒｅｄｕｎｄａｎｃｙ　Ｃｈｅｃｋ）付加や畳み込み符号化を施す。変調部１０３は、入力された符号データを変調する。ＯＦＤＭ信号生成部１０４は、変調後のデータを周波数軸上にマッピングし、デジタルフーリエ逆変換によって、周波数軸上のデータを時間軸上のデータに変換する。変換後のデータをＤ／Ａ変換部１０５に出力する。Ｄ／Ａ変換部１０５は、ＯＦＤＭ信号生成部１０４が出力したデジタル信号をアナログ信号に変換する。そしてアナログ信号に変換された変調データは、複数のアンテナ１０６を介して送信される。
　受信側の移動局１１１は、複数のアンテナ１１６を介して、送信側１０１のアンテナ１０６から送信されたデータを受信する。ただし、アンテナ１１６が受信したデータは、アンテナ１０６から出力された後、空間を伝播する際のノイズの影響を受けていることに留意する。アンテナ１１６が受信したデータは、Ａ／Ｄ変換部１１５に入力される。Ａ／Ｄ変換部１１５は、入力されたデータをアナログ信号からデジタル信号に変換する。Ａ／Ｄ変換部１１５は、変換後のデジタル信号をＯＦＤＭ信号復調部１１４に出力する。ＯＦＤＭ信号復調部１１４は、Ａ／Ｄ変換部１１５から出力される時間軸上のデジタル信号を、デジタルフーリエ変換によって周波数軸上のデータに変換し、ＩＱ平面上にマッピングする。復調部１１３は、ＯＦＤＭ信号復調部１１４が出力したデータを復調する。復調部１１３は、復調して得た復調データを復号化部１１２に出力する。復号化部１１２は、入力された復調データに対して、誤り訂正復号化を行う。その結果得られる復号データを使用して、後段のＣＰＵなどの処理回路が所定の処理を実施する。
　このＯＦＤＭ方式を用いた通信システムのＯＦＤＭ信号生成部１０４、およびＯＦＤＭ信号復調部１１４では、デジタルフーリエ変換が用いられる。ＤＦＴは、演算量が非常に大きい。ＬＴＥでは、２０ＭＨｚ帯域のサブキャリア数は１２００である。これをＤＦＴで演算するには、１１９９回の複素乗算と複素加算を、１２００回行う必要がある。しかかも、これを、１ＯＦＤＭシンボル期間６６．６７マイクロ秒以内に行う必要がある。
　演算量を小さくするためのアルゴリズムとして、たとえば、上述したようなクーリー・チューキー型の高速フーリエ変換が用いられる。２点ＤＦＴと４点ＤＦＴを組み合わせることによって、サブキャリア数１２００の場合の演算量は
　２０４８回の複素乗算と複素加算＋（３回の複素加算と１回の複素乗算を２０４８回）×５回
となる。ここで、クーリー・チューキー型の高速フーリエ変換ではデータ数が２のべき乗であることが必要であるため、１２００より大きく、かつ最も小さな２のべき乗である２０４８がデータ数となる。
　実際の演算では、複素乗算の対象となる回転子が実数部のみ、あるいは虚数部のみで表される場合もあるため、乗算回数はこれより少なくてよいこともある。しかし、それでも、演算量が多いことにかわりはない。
　４点ＤＦＴを構成要素とした高速フーリエ変換を行うことによって、演算量を小さくできる。しかし、これをハードウェアで実現する場合は、一般的に、入出力データはメモリに格納する構成となる。４点ＤＦＴを実行する場合、その入力となる４つの複素データをメモリから取り出す必要があるが、メモリがシングルポートである場合は、４サイクルを要する。複数ポートのメモリ、あるいは、シングルポートのメモリを４分割することで、１サイクルで４複素データをメモリから読み出すことが可能となる。しかし、前者はメモリセルそのものの面積が大きくなり、後者はメモリマクロに付随するテスト回路、あるいはデコーダ回路により面積の増加に繋がる。また、メモリを分割することによって配線数が４倍となり、ＬＳＩ作製時のレイアウト設計の難易度が上がり、配線が出来るようにＬＳＩ面積を大きくしなければならない場合も考えられる。
　このような場合に、上述の実施の形態で示した高速フーリエ変換回路を用いることで、複数ポートのメモリを用いたり、メモリを分割したりすることなく、１サイクルで１回の４点ＤＦＴ演算が可能となり、処理時間を短縮することができる。
　また、スペクトラムアナライザなど、フーリエ変換を行う測定装置に本発明を利用することもできる。
１　４点ＤＦＴ演算部
２Ａ、２Ｂ　メモリ
３　リードバッファ
４　ライトバッファ
５　セレクタ
６　回転子生成部
７、１２　制御部
１１　２点／４点ＤＦＴ演算部

Claims (8)

  1. 　複数のデジタルフーリエ変換を構成要素とする高速フーリエ演算を行う演算部と、
    　上記演算部の入出力データを格納するメモリと、
    　処理対象のデータに対して上記演算部が行う複数ステージの演算に対して、上記メモリからのデータの読み出し順が各ステージで同じとなるように、上記演算部による演算結果の上記メモリへの書き込みを制御する手段と
    　を有することを特徴とする高速フーリエ変換回路。
  2. 　請求項１記載の高速フーリエ変換回路において、
    　前記演算部は、基数Ｂ、ただしＢは２以上の整数、のデジタルフーリエ変換を構成要素とし、
    　前記制御する手段は、データ数Ｎが上記基数Ｂのべき数のデータに対して前記演算部が行うＰ＝ｌｏｇＢＮステージの演算に対して、次のステージでの演算対象となるデータが前記高速フーリエ演算の順番ｋ＝０，１,・・，Ｎ／Ｂ－１に対してデータ数Ｎを上記基数Ｂで割った値ごとに同じアドレスでメモリから読み出すことのできるアドレス順に、前記メモリへの書き込みを行う
    　ことを特徴とする高速フーリエ変換回路。
  3. 　請求項２記載の高速フーリエ変換回路において、
    　前記制御する手段は、第Ｓ＝１，２，・・，Ｐステージのそれぞれにおける前記メモリへの書き込みアドレスＷＡ（Ｓ，ｋ，ｍ）、ただしｍ＝０，１，・・，Ｂ－１、を、前記基数Ｂを残りステージ数に１を加えた値Ｐ－Ｓ＋１乗した値で前記データ数Ｎを割った値にｍを乗じた値と、前記基数ＢをＳ－１乗した値で前記順番ｋの値を割った値に前記基数ＢのＳ乗を乗じた値と、前記基数ＢをＳ－１乗した値で前記順番ｋの値を割っときの余りの値とを加算した値に設定し、
    　第Ｓ＝１，２，・・，Ｐステージのそれぞれにおける前記メモリからの読み出しアドレスＲＡ（Ｓ，ｋ，ｍ）を、前記基数Ｂで前記データ数Ｎを割った値にｍを乗じた値と、前記順番ｋの値とを加算した値に設定する
    　ことを特徴とする高速フーリエ変換回路。
  4. 　請求項１記載の高速フーリエ変換回路において、
    　前記演算部は、４以上の複数Ｂ点またはＢ／２点のいずれかのデジタルフーリエ変換を１サイクルで実行する構成であり、
    　データ数Ｎが上記Ｂ／２のべき乗であるが上記Ｂのべき乗ではないデータに対して、前記演算部による演算が、Ｂ／２点のデジタルフーリエ変換を２組実行するひとつのステージと、Ｂ点のデジタルフーリエ変換を実行するｌｏｇＢ（Ｎ／２）ステージとに分解され、
    　前記制御する手段は、上記ひとつのステージおよび上記ｌｏｇＢ（Ｎ／２）ステージのそれぞれにおいて、次のステージでの演算対象となるデータが前記高速フーリエ演算の順番ｋ＝０，１,・・，Ｎ／Ｂ－１に対してデータ数Ｎを上記Ｂの値で割った値ごとに同じアドレスでメモリから読み出すことのできるアドレス順に、前記メモリへの書き込みを行う
    　ことを特徴とする高速フーリエ変換回路。
  5. 　請求項４記載の高速フーリエ変換回路において、
    　前記制御する手段は、
    　前記ひとつのステージにおける前記メモリへの書き込みアドレスＷＡ（Ｓ，ｋ，ｍ）、ただしｍ＝０，１，・・，Ｂ－１、を、ｍ＝０，１，．．，Ｂ／２－１のときにはｋの２倍にｍを加算した値、ｍ＝Ｂ／２，．．，Ｂ－１のときにはＮ／２とｋの２倍とｍ－Ｂ／２とを加算した値に設定し、
    　前記ｌｏｇＢ（Ｎ／２）ステージのそれぞれにおける前記メモリへの書き込みアドレスＷＡ（Ｓ，ｋ，ｍ）を、前記Ｂの値を残りステージ数に１を加えた値Ｐ－Ｓ＋１乗した値で前記データ数Ｎを割った値にｍを乗じた値と、前記Ｂの値をＳ－１乗した値で前記順番ｋの２倍の値を割った値に前記基数ＢのＳ乗の半分の値を乗じた値と、前記基数ＢをＳ－１乗した値の半分の値で前記順番ｋの値を割ったときの余りの値とを加算した値に設定し、
    　前記ひとつのステージおよびｌｏｇＢ（Ｎ／２）ステージのそれぞれにおける前記メモリからの読み出しアドレスＲＡ（Ｓ，ｋ，ｍ）を、前記Ｂの値で前記データ数Ｎを割った値にｍを乗じた値と、前記順番ｋの値とを加算した値に設定する
    　ことを特徴とする高速フーリエ変換回路。
  6. 　請求項１から５のいずれか１項に記載の高速フーリエ変換回路において、
    　前記メモリから読み出されたデータを格納し、前記演算部に出力するリードバッファと、
    　前記演算部による演算結果を格納し、前記メモリに書き込むライトバッファと
    　をさらに有する
    　ことを特徴とする高速フーリエ変換回路。
  7. 　請求項６記載の高速フーリエ変換回路において、
    　前記演算部の構成要素である前記複数のデジタルフーリエ変換を、前記リードバッファおよび前記ライトバッファの１サイクルのデータ転送で実行する
    　ことを特徴とする高速フーリエ変換回路。
  8. 　請求項２から５のいずれか１項に記載の高速フーリエ変換回路において、前記Ｂの値は４であることを特徴とする高速フーリエ変換回路。
PCT/JP2011/052844 2010-02-16 2011-02-10 高速フーリエ変換回路 WO2011102291A1 (ja)

Priority Applications (4)

Application Number Priority Date Filing Date Title
US13/579,184 US20130046806A1 (en) 2010-02-16 2011-02-10 Fast fourier transform circuit
EP11744578A EP2538345A1 (en) 2010-02-16 2011-02-10 Fast fourier transform circuit
JP2012500571A JPWO2011102291A1 (ja) 2010-02-16 2011-02-10 高速フーリエ変換回路
CN2011800097694A CN102763101A (zh) 2010-02-16 2011-02-10 快速傅里叶变换电路

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP2010030796 2010-02-16
JP2010-030796 2010-02-16

Publications (1)

Publication Number Publication Date
WO2011102291A1 true WO2011102291A1 (ja) 2011-08-25

Family

ID=44482878

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2011/052844 WO2011102291A1 (ja) 2010-02-16 2011-02-10 高速フーリエ変換回路

Country Status (6)

Country Link
US (1) US20130046806A1 (ja)
EP (1) EP2538345A1 (ja)
JP (1) JPWO2011102291A1 (ja)
CN (1) CN102763101A (ja)
TW (1) TW201209602A (ja)
WO (1) WO2011102291A1 (ja)

Families Citing this family (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2013097236A1 (zh) * 2011-12-31 2013-07-04 中国科学院自动化研究所 多粒度并行fft计算装置
WO2017053986A1 (en) 2015-09-25 2017-03-30 Microsoft Technology Licensing, Llc Method and system for approximate quantum circuit synthesis using quaternion algebra
WO2016164325A1 (en) * 2015-04-10 2016-10-13 Microsoft Technology Licensing, Llc Method and system for quantum circuit synthesis using quaternion algebra
CN113569189B (zh) * 2021-07-02 2024-03-15 星思连接(上海)半导体有限公司 一种快速傅立叶变换计算方法及装置
TWI863789B (zh) * 2024-01-02 2024-11-21 財團法人工業技術研究院 數論轉換運算電路

Citations (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS62273440A (ja) * 1986-05-21 1987-11-27 Hitachi Ltd 核磁気共鳴装置
JPS63292267A (ja) * 1987-05-25 1988-11-29 Nippon Telegr & Teleph Corp <Ntt> 高速フ−リエ変換用アドレス生成回路
JPH11110370A (ja) * 1997-01-22 1999-04-23 Matsushita Electric Ind Co Ltd 高速フーリエ変換装置および方法、可変ビットリバース回路、逆高速フーリエ変換装置および方法、並びにｏｆｄｍ受信および送信装置
JP2004166083A (ja) * 2002-11-14 2004-06-10 Matsushita Electric Ind Co Ltd 符号化装置及び方法
JP2006155487A (ja) 2004-12-01 2006-06-15 Sony Corp 高速フーリエ変換処理装置および演算処理用制御装置
JP2008186396A (ja) * 2007-01-31 2008-08-14 Mitsubishi Electric Corp 高速フーリエ変換装置
JP2008533873A (ja) * 2005-03-11 2008-08-21 クゥアルコム・インコーポレイテッド 高速フーリエ変換トゥイドル乗算
JP2008217359A (ja) * 2007-03-02 2008-09-18 Fujitsu Ltd 高速フーリエ変換装置及び高速フーリエ変換処理方法
JP2009095008A (ja) * 2007-09-20 2009-04-30 Mitsubishi Electric Corp ターボ符号復号装置、ターボ符号復号方法及び通信システム

Family Cites Families (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6081821A (en) * 1993-08-05 2000-06-27 The Mitre Corporation Pipelined, high-precision fast fourier transform processor
WO2002091221A2 (en) * 2001-05-07 2002-11-14 Jaber Associates, L.L.C. Address generator for fast fourier transform processor
TWI298448B (en) * 2005-05-05 2008-07-01 Ind Tech Res Inst Memory-based fast fourier transformer (fft)

Patent Citations (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS62273440A (ja) * 1986-05-21 1987-11-27 Hitachi Ltd 核磁気共鳴装置
JPS63292267A (ja) * 1987-05-25 1988-11-29 Nippon Telegr & Teleph Corp <Ntt> 高速フ−リエ変換用アドレス生成回路
JPH11110370A (ja) * 1997-01-22 1999-04-23 Matsushita Electric Ind Co Ltd 高速フーリエ変換装置および方法、可変ビットリバース回路、逆高速フーリエ変換装置および方法、並びにｏｆｄｍ受信および送信装置
JP2004166083A (ja) * 2002-11-14 2004-06-10 Matsushita Electric Ind Co Ltd 符号化装置及び方法
JP2006155487A (ja) 2004-12-01 2006-06-15 Sony Corp 高速フーリエ変換処理装置および演算処理用制御装置
JP2008533873A (ja) * 2005-03-11 2008-08-21 クゥアルコム・インコーポレイテッド 高速フーリエ変換トゥイドル乗算
JP2008186396A (ja) * 2007-01-31 2008-08-14 Mitsubishi Electric Corp 高速フーリエ変換装置
JP2008217359A (ja) * 2007-03-02 2008-09-18 Fujitsu Ltd 高速フーリエ変換装置及び高速フーリエ変換処理方法
JP2009095008A (ja) * 2007-09-20 2009-04-30 Mitsubishi Electric Corp ターボ符号復号装置、ターボ符号復号方法及び通信システム

Also Published As

Publication number Publication date
CN102763101A (zh) 2012-10-31
JPWO2011102291A1 (ja) 2013-06-17
EP2538345A1 (en) 2012-12-26
TW201209602A (en) 2012-03-01
US20130046806A1 (en) 2013-02-21

Similar Documents

Publication Publication Date Title
Lin et al. A dynamic scaling FFT processor for DVB-T applications
EP0855657B1 (en) Fast fourier transforming apparatus and method
JP2009535678A (ja) パイプラインｆｆｔのアーキテクチャおよび方法
CN112100568B (zh) 定点傅里叶变换fft处理器及处理方法
CN112800386B (zh) 傅里叶变换处理方法和处理器、终端、芯片及存储介质
WO2011102291A1 (ja) 高速フーリエ変換回路
US9250996B2 (en) Multicore type error correction processing system and error correction processing apparatus
CN111737638A (zh) 基于傅里叶变换的数据处理方法及相关装置
CN101937423B (zh) 一种流水式fft/ifft的处理系统
KR100989797B1 (ko) Ｆｆｔ/ｉｆｆｔ 연산코어
US9727531B2 (en) Fast fourier transform circuit, fast fourier transform processing method, and program recording medium
US8838661B2 (en) Radix-8 fixed-point FFT logic circuit characterized by preservation of square root-i operation
CN115544438A (zh) 数字通信系统中的旋转因子生成方法、装置和计算机设备
US20140365547A1 (en) Mixed-radix pipelined fft processor and fft processing method using the same
EP2144173A1 (en) Hardware architecture to compute different sizes of DFT
CN101938442B (zh) Dft处理器的预检测基运算方法、混合基运算方法和系统
US20140219374A1 (en) Efficient multiply-accumulate processor for software defined radio
JP3065979B2 (ja) 高速フーリエ変換装置および方法、可変ビットリバース回路、逆高速フーリエ変換装置および方法、並びにｏｆｄｍ受信および送信装置
Lin et al. Low-cost FFT processor for DVB-T2 applications
Yang et al. A novel design of pipeline MDC-FFT processor based on various memory access mechanism
CN113094639B (zh) 一种dft并行处理方法、装置、设备及存储介质
KR20120101807A (ko) 메모리 기반 고속 푸리에 변환 프로세서
Vishwanath Efficient Hardware Architecture for Ultra-High Sampling Rate FFT Analysis of Acoustic Emission Signals
Locharla et al. Implementation of input data buffering and scheduling methodology for 8 parallel MDC FFT
Jung et al. Low-complexity multi-mode memory-based FFT processor for DVB-T2 applications

Legal Events

Date Code Title Description
WWE Wipo information: entry into national phase

Ref document number: 201180009769.4

Country of ref document: CN

121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 11744578

Country of ref document: EP

Kind code of ref document: A1

WWE Wipo information: entry into national phase

Ref document number: 2012500571

Country of ref document: JP

WWE Wipo information: entry into national phase

Ref document number: 2011744578

Country of ref document: EP

NENP Non-entry into the national phase

Ref country code: DE

WWE Wipo information: entry into national phase

Ref document number: 7936/CHENP/2012

Country of ref document: IN

WWE Wipo information: entry into national phase

Ref document number: 13579184

Country of ref document: US