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 invention relates to devices for calculating transform of
• Cooley-Tuckey algorithm uses a calculation graph showing a structure in the shape of a butterfly, well known to those skilled in the art, and commonly known in English as the "butterfly".
• a first solution consists in making a hardware operator capable of performing a butterfly type calculation, by butterfly of the graph.
• a hardware operator capable of performing a butterfly type calculation, by butterfly of the graph.
• such a solution is only possible for the implementation of small Fourier transforms.
• a second solution consists in carrying out only one material operator of the butterfly type, and intended to carry out successively the calculations corresponding to all the butterflies of all the stages of the graph.
• Such a solution has the drawback of requiring on the one hand a very fast hardware operator, and on the other hand an input memory distinct from the memory used to write the intermediate calculation results in order to avoid access conflicts when a data block enters the operator. that the previous block is still being processed. It is therefore necessary to provide two memories of N complex words, where N denotes the size of the Fourier transform, which leads to a global circuit with a large surface area in particular when N is large.
• An intermediate solution consists in producing a material operator of the butterfly type per stage of the graph, as well as a memorization element whose function is to present at the operator input the data in the correct order taking into account the butterflies of the graph of the floor considered.
• a circuit for computing a Fou ⁇ rier transform of predetermined initial size includes a plurality of successive processing stages connected in series between the input and the output of the circuit by internal data paths.
• Each stage comprises elementary processing means (of the butterfly type) capable of carrying out Fourier transform treatments of predetermined elementary sizes smaller than the initial size, on data blocks of sizes successively reduced from one stage to the next.
• These elementary sizes can be identical and equal to the radix of the Fourier transform. We then speak of Fourier transforms with "uniform" radix. They can be different from one stage to another in the case of Fourier transforms with "mixed" ra ⁇ ten.
• dynamic value of a data item means the range of values in which this data is located, that is to say for example between - 0.5 and + 0.5 or between - 0.05 and + 0.05 etc.
• a first solution consists in globally extending a priori the dynamics of the data, that is to say that a priori is estimated the necessary dynamics on the data at the output of the circuit so as not to lose too much precision on the significant bits , assuming of course that there is no saturation on the internal calculations, and then the size of the words of the input data is increased by the estimated number of additional bits.
• the intermediate data and the output data will therefore also be represented with words of this size. This leads to an increase in the size of the circuit's internal data paths which can be significant in the case of large Fourier transforms requiring several processing stages, and therefore to a penalizing increase in the total surface of the circuit for example implanted. a silicon wafer.
• Another solution also consists in extending the dynamics of the data paths a priori, but this time stage by stage. Such a solution is certainly more advantageous than the first but it also leads to an artificial increase in the size of the internal data paths of the circuit and therefore of its surface.
• the BI and JONES article cited above does not mention any solution to this problem of data dynamics.
• the invention aims to provide a more satisfactory solution to this problem.
• An object of the invention is to propose a device for calculating a Fourier transform of the type with constant dynamics and in which the size of the internal data paths is not artificially increased.
• the subject of the invention is therefore, an electronic device for calculating a Fourier transform of predetermined initial size, comprising a plurality of successive processing stages connected in series between the input and the output of the device by paths of internal data and respectively comprising elementary processing means capable of carrying out Fourier transform treatments of predetermined sizes smaller than the initial size, on data blocks of sizes successively reduced from one stage to the next.
• the device comprises:
• the invention provides for an adaptive cropping, that is to say taking into account an effectively calibrated dynamic value. abutment, on data blocks of sizes successively reduced from one stage to another.
• the input data are received sequentially according to an input frequency determined by a basic clock signal.
• the elementary processing means of the stage of rank t are capable of performing an elementary processing of Fourier transform of size r t on successive blocks of data at the frequency of the basic clock signal.
• the time delay means comprise first switchable delay means capable of temporarily storing data blocks drawn from those delivered by the elementary processing means of the current stage, and of delivering to the elementary processing means of the following stage, at the rate of the basic clock signal, and with a predetermined time delay, for each block received, successive groups of given r t ordered in a predetermined order.
• the time delay means also include second delay means connected to the first and also clocked by the basic clock signal.
• the first and second delay means are able together to store all the data of each block from the elementary processing means of the previous stage.
• the memory size of the first and second delay means is at least equal to the number of these data.
• the first switchable delay means of the stage of rank t advantageously comprise r t outputs connected to the elementary processing means of this stage, as well as two sets of r t - l delay elements connected in series.
• the output of the last delay element of the first set is directly connected to one of the r t outputs of the first delay means while the outputs of the delay elements of the second set are respectively connected to the other outputs of the first delay means by l 'through one of the inputs of switching means controllable with two inputs.
• the inputs of the delay elements of the first set are also respectively connected to the other inputs of the switching means controllable with two inputs.
• the second delay means also include a delay element connected to the input of the first delay means. All the delay elements advantageously also have the same memory size.
• the delay elements preferably include dynamic delay lines.
• the means for determining the overall dynamic value of each block include means for determining the number of duplicate sign bits of each datum of the block, said overall dynamic value associated with the block being the most small numbers of duplicate sign bits.
• the intermediate cropping means advantageously include means for shifting the bits of the word of each data in the block to the most significant bit, these shifting means being connected to the means for determining the value of overall dynamics.
• the time delay means are advantageously located between the elementary processing means of each pair of consecutive stages, while the means for determining global dynamic values are connected to the output of the elementary processing means of each stage.
• the elementary processing means of each stage comprise a set of adders / subtractors followed by a multiplier; the shifting means are arranged before the set of adders / subtractors or advantageously between this set and the multiplier.
• the means for determining final dynamic values may comprise a succession of registers, of the same size, respectively clocked by clock signals of higher frequency from one stage to the next, and respectively connected on the one hand to the determination means. of values of global dynamics of the corresponding stage and on the other hand to the preceding register by an adder.
• the subject of the invention is also a method for minimizing the size of the internal data paths of a device for calculating a Fourier transform of a predetermined initial size, with a so-called series or "pipelined" architecture, in which one performs within the device a succession of elementary Fourier transform treatments of predetermined elementary sizes plus smaller than the initial size, on data blocks of size successively reduced from one elementary processing to the next.
• a global dynamic value is determined for each data block resulting from a current elementary processing, from the dynamic values of all the data of the block and the data of the block are cropped, account given the overall dynamic value, before performing the following elementary processing completely on this data.
• each elementary processing is clocked by said base clock and the delays the start of the next elementary processing on the data of the block resulting from the current elementary processing, at least by a number of basic clock cycles equal to the number of data of the block, after obtaining the first of the data resulting from the elementary processing current.
• the overall dynamic value of each block is advantageously determined from the detection of the number of sign bits of all the data in the block, the global dynamic value being the minimum number of duplicate sign bits of said data.
• the data of the block is preferably cropped by an offset of all the bits of the word of each data towards the most significant bit by a number of bits equal to said minimum number of duplicate sign bits.
• each global dynamic value of a block is incremented giving rise to an elementary processing, by the global dynamic value of each block originating from this block after said elementary processing, so as to obtain at the end of processing a final dynamic value for each output data. It is then possible to perform a final cropping of each output data from the associated final dynamic value if it is desired to output data on a predetermined number of bits. One can possibly refrain from such a cropping if one adopts a representation of the floating type. However in this case, it is nevertheless advisable to associate with the value of the output data, its final dynamic value to avoid an erroneous result.
• Each elementary processing comprising a set of additions / subtractions followed by a multiplication, it is possible to reframe the data before performing the additions / subtractions or else after having performed these additions / subtractions but before performing the multiplication.
• FIG. 1 illustrates the calculation graph with butterfly-based structure implemented in a device with pipelined architecture with three stages
• FIGS. 2 and 3 illustrate in more detail the architecture of the device corresponding to the graph of FIG. 1,
• FIG. 4 schematically illustrates the hardware architecture of a hardware operator of the butterfly type such as that used in the graph of FIG. 1,
• FIGS. 5 and 6 respectively illustrate two data words before and after intermediate cropping
• FIG. 7 illustrates a timing diagram corresponding to the calculation graph of FIG. 1 and to the operation of the device of FIGS. 2, 3 and 4, and
• FIG. 8 illustrates a schematic hardware embodiment of a memory point of a dynamic delay line usable in a device according to the invention.
• the initial size N of the Fourier transform is equal to 32, and is reduced to the calculation of three Fourier transforms of elementary sizes r j , r 2 and r 3 respectively equal to 4, 4 and 2
• Each input data is a complex word having a real part and a imaginary part coded on n bits in representation in addition to 2, and framed between - 1 and 1.
• the first processing stage ETl performs an elementary Fourier transform processing of size 4 on a block of 32 data, which are in fact the input data .
• the stage of rank t performs elementary processing of Fourier transforms of size r t on successive blocks of r t N t given with
• N t N / ⁇ r t - f ⁇ t
• EL denotes the "product" function
• the first processing stage ET1 performs processing of the "butterfly" type on groups of 4 data.
• the intermediate output data set Xi obtained after processing by the butterflies and multiplication by a coefficient m N equal to the complex number e "J 2m ⁇ / N , can be subdivided into four blocks of 8 data. On each of these blocks, is performed a "butterfly" type treatment on groups of 4 data. After multiplication by the coefficient Wq the output data Yi can be divided into 16 blocks of two data on each of which operates a butterfly type operator of a Fourier transform of size 2. In FIG. 1, this butterfly operator of size 2, of structure well known to those skilled in the art and for example illustrated in the work of Lawrence R.
• a global dynamic value E1-E20 is determined for each data block B1-B20, from the dynamic values of all the data of the block. This allows you to crop the block data before processing in the butterfly operator.
• FIGS. 2 to 4 The hardware architecture of a circuit D implementing the calculation graph of FIG. 1 is illustrated more particularly in FIGS. 2 to 4.
• This circuit advantageously made in a wired manner, that is to say integrated on a silicon wafer, for example, and comprising discrete elements, can be broken down into a succession of successive processing stages ET1, ET2, ET3, connected together and between the data input ES and the data output OUT by internal data paths, or buses, of size n bits.
• Each processing stage for example the processing stage of rank 2, ET2, comprises elementary processing means EAS2,
• the elementary processing means EAS1, MCI of the stage of rank 1, ET1 will carry out a Fourier transform processing of size 4, on successive groups of four input data, ordered according to a predetermined order, and taken from the block of 32 input data.
• the elementary processing means of the stage of rank 2, ET2 will likewise carry out a Fourier transform processing of size 4 on successive groups of 4 data of block Bl, ordered according to a predetermined order, and corresponding to the corresponding butterflies of the calculation graph then another elementary processing of Fourier transform of size 4 on successive groups of 4 data of block B2 and so on to the data of block B4.
• the elementary processing means of each stage, in particular the stage of rank 2, ET2, are clocked by a basic clock signal H delivered by an appropriate circuit BH2.
• These EAS2 elementary processing means, MC2 of stage ET2 are associated with first switchable delay means MRA2 capable of delivering to elementary processing means EAS2.MC2, at the rate of the basic clock signal H, and with a predetermined time delay, for each block received, the successive groups of r t data ordered in a predetermined order.
• These first switchable delay means MRA2 of the current stage of rank 2, ET2, comprise 4 outputs S21, S22, S23, S24 connected to the elementary processing means EAS2, MC2. They also include two sets of three delay elements connected in series. These delay elements are referenced ER1-2 to ER6-2 and the first set of elements comprises the elements ER1-2 to ER3-2 while the second set comprises the elements ER4-2 to ER6-2.
• the output of the last delay element ER3-2 of the first set is directly connected to the output S21.
• the outputs of the delay elements ER4-2 to R6-2 of the second set are respectively connected to the other outputs S23, S23, S24 via one of the inputs of switching means controllable with two inputs Ca, Cb, Ce .
• the inputs of the delay elements of the first set are respectively connected to the other inputs of the switching means Ca, Cb and Ce.
• the switching means Ca, Cb and Ce are controlled by control signals from an LC2 control logic.
• An example of ordering these switches is provided in the aforementioned article of BI and JONES, which is for all intents and purposes incorporated into the content of this description.
• the size of each of these delay elements i.e. the number of data which they can each store momentarily, is with regard to the stage of rank 2, ET2, equal to 2. More generally, in a succession of processing stages, the size of each of the delay elements is equal to
• each datum is a complex datum composed of two words representing respectively the imaginary part and the real part of the datum.
• Second delay means MRB2 are also provided, comprising a delay element of the same size as the delay elements of the first delay means MRA2, and the output of which is connected to the input EN2 of these first delay means MRA2, therefore in this case at the entry of the first delay element ER1-2 of the first set.
• All these delay elements are generally sequential access memory means clocked by the basic clock signal H. Materially, they can be produced for example by shift registers or else memories of the First Input type. , Premier Sorti (FIFO in English). However, it is particularly advantageous, for reasons of space, to provide dynamic delay lines whose different memory points are produced from three transistors as illustrated in FIG. 8.
• the two transistors T1 and T2 are respectively controlled on their grids by write and read control signals. They are also respectively connected between on the one hand a write bus BEC and a read bus BLE, and on the other hand the ground via a third transistor T3. The stored value is memorized at the transistor T3.
• the elementary processing means of each stage comprise a set EAS2 of complex adders / subtractors (here three) AS 1, AS2, AS3 followed by a complex multiplier MC2.
• the elementary processing means comprise r t inputs, (here four) which are connected to the two adders / subtractors AS l,
• CD1 for framing on n bits, on the left for example, of the data Xi coming from the elementary processing means of the stage ET1.
• means CD1 of the stage ETl At the output of the means CD1 of the stage ETl are also connected means DBS2 capable of determining for each block of data coming from the multiplier MCI a global dynamic value for this block from the dynamic values of all the data of this block.
• the detection of the dynamic value of each datum is carried out from the detection of the number of duplicate sign bits. of the word of this data.
• the means DBS2 then comprise means for comparing the value of the most significant bit of the word of the data, with a certain number of immediately adjacent bits, for example three. The number of neighboring bits equal to the sign bit thus determines the number of duplicate sign bits.
• S denotes the sign bit
• BT1 to BT6 the significant bits
• the three bits on the left are identical, which corresponds to two duplicate sign bits.
• the DBS2 means also include means for determination of the smallest of the numbers of duplicate sign bits of all the data of the block considered. This smallest number, which represents the overall dynamic value of the block, is then stored in a register RGb2, controlled by a clock signal H2 drawn from the basic clock signal H.
• Means for cropping the data delivered by the delay means MRA2 are then arranged between the output of these delay means and the input of the assembly EAS2 of adders / subtractors of the elementary processing means of the stage ET2.
• These data cropping means here comprise a DL2 shifter capable of shifting to the left, that is to say towards the most significant bit, all the data of a block, by a value equal to the number stored in the RGbl register.
• the shifted data word now includes as high-order bit the sign bit S followed by the six significant bits BT1 and BT6.
• the output of the means DBS2 is also connected to an adder A2 whose other input is connected to a data transmission bus BS1 and whose output is connected to another register RGa2 also controlled by the clock signal H2.
• the output of this register RGa2 is connected to another part BS2 of the data transmission bus.
• the clock signal H2 of stage ET2 whose rising edges are synchronous with the start of the data blocks from the multiplier MCI, has a frequency eight times lower than the frequency of the basic clock sign H.
• the data XO - X7 form the first data block B 1 coming from the elementary processing means of the stage ET1.
• the detection of the number of duplicate sign bits of each of these data is carried out in the means DBS2 and the value E1 of global dynamics of this block, that is to say the smallest of the numbers of duplicate sign bits, is stored in the register RGb2 on the next rising edge of the clock H2.
• the data of the block are delivered by the multiplier MCI, they are stored in the memory means MRB2 and MRA2 then delivered sequentially in a predetermined order in groups of 4 to the four outputs S21, S22, S23 and S24.
• the first group of data XO, X6, X4, X2 is only presented at the outputs S21, S22, S23 and S24 of the means time delay (and therefore can only be processed by the elementary processing means of stage ET2), after all the data in block XO - X7 have been delivered by the multiplier MCI.
• stage ET2 In other words, generally in a succession of stages of Fourier transform, one delays the beginning of the following elementary processing (that is to say here in stage ET2) on the data of a block resulting from the current elementary processing (stage ETl), of a number of basic clock cycles at least equal to r t N t , after obtaining the first data of this block resulting from the multiplier MCI.
• the eight successive groups G1-G8 of four data presented at the output of the time delay means MRA2 are then shifted to the left by the value El in the shifter DL2 before delivery to the set of EAS2 adders / subtractors of the elementary processing means. of floor ET2.
• the presence of the delay element MRB2 is essential. In fact, in the absence of this element, some of the data from the MCI multiplier would have been presented to the input of the EAS2 assembly before all of the data in block B 1 had been delivered by the MCI multiplier. It would therefore have been impossible to reframe the first group Gl of four data delivered by the * time delay means MRA2 and MRB2 to the assembly EAS2.
• E2 is also stored in the register RGb2 for the purpose of shifting the data of this block before processing in the EAS2 assembly.
• the data Yi will be divided into 16 blocks B5 - B20 of two data, giving rise respectively to 16 values of global dynamics E5 - E20, used for cropping these data, in a manner analogous to that which was exposed previously, before their processing in the elementary processing means of stage ET3.
• the data blocks B5 to B8 come from the data block B l, while the data blocks B9 to B 12 come from the data block B2.
• the data blocks B 13 to B16 come from the data block B3 and the data blocks B17 to B20 from the data block B4.
• The, sixteen values E5 - E20 will be delivered to the register RGa3 of stage ET3 (figure 2).
• the first four values of this register will be respectively equal to the global dynamic value El of block B l incremented by the four global dynamic values E5 - E8 associated with blocks B5 - B8 coming from block B l, while the other values will be respectively equal to the sum of the other global dynamic values E2 to E4 incremented by the global dynamic values of the blocks resulting from the other three blocks B2 - B4.
• the size in number of words of the register RGa3 is identical to the size of the register RGa2. However, since it is clocked by the clock signal H3 which is four times faster than the clock signal H2, it makes it possible to store four times more values.
• each pair of output data delivered by the elementary processing means of the last stage is associated with the same final dynamic value.
• detection and offset are only carried out in practice for the intermediate processing stages. Also in the case of a Fourier transform of 32 points with mixed radix (4, 4, 2), only the second stage will include detection and offset. With regard to the final dynamic values, if an offset and detection processing is carried out on the last stage, a final dynamic value will be associated with a block of length equal to the radix of this stage. On the other hand, in the absence of processing on this stage, a final dynamic value will be associated with a larger block of number of values (16 values in the case where the last two stages are of radix 4, and 8 values for radix equal to 4 and 2 respectively).
• the invention makes it possible to work at constant dynamics by minimizing the size of the internal data paths of the circuits, that is to say by limiting this size to n bits, without losing too much precision on intermediate data.
• This therefore makes it possible in particular to produce integrated circuits capable of carrying out Fourier transforms of 8192 complex points in 1 millisecond in a submicronic CMOS technology, usable in terrestrial digital television applications, without unnecessary and penalizing increase in the surface area. such a circuit.

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)
• Image Analysis (AREA)

Applications Claiming Priority (3)

Publications (1)

Family

ID=9450119

Family Applications (1)

Country Status (5)

Families Citing this family (9)

Family Cites Families (6)

• 1993
  • 1993-08-11 FR FR9309865A patent/FR2709007B1/fr not_active Expired - Fee Related
• 1994
  • 1994-08-10 WO PCT/FR1994/000996 patent/WO1995004963A1/fr not_active Application Discontinuation
  • 1994-08-10 US US08/416,907 patent/US5774388A/en not_active Expired - Fee Related
  • 1994-08-10 JP JP7506262A patent/JPH08503322A/ja active Pending
  • 1994-08-10 EP EP94924344A patent/EP0667969A1/de not_active Withdrawn

Non-Patent Citations (1)

Also Published As

Similar Documents

Legal Events