ROM-Based Complex Multiplier Useful for FFT Butterfly Arithmetic Unit

1. U.S. Application Ser. No. 130,653 filed Mar. 17, 1980, for A ROM-BASED PARALLEL DIGITAL ARITHMETIC DEVICE by Stanley A. White.

2. U.S. Application Ser. No. 092,387, (now U.S. Pat. No. 4,275,452) filed Nov. 8, 1979 for SIMPLIFIED FAST FOURIER TRANSFORM BUTTERFLY ARITHMETIC UNIT by Stanley A. White.

1. Field of Invention

The concept of the invention relates to an improved complex multiplier for use in a simplified FFT butterfly arithmetic unit.

2. Description of the Prior Art

In the field of spectral analysis by digital machine means, and more particularly in sequency analyzers such as fast fourier transform devices, machine mechanizations of the algorithm to be solved have been quite complex and expensive, as to limit the applications of and markets for such machines. A key function in such mechanization is the multiplication of two complex values.

In the digital fast fourier processing of a sampled time history of say N samples over the sampled signal epoch of interest, successive samples are treated as complex quantities and are organized as two groups of sequences, each occurring in a mutually exclusive one of a first half and second half (A and B) of the sampled epoch. As is more fully explained in U.S. Pat. No. 4,158,888 to Shapiro for FAST FOURIER TRANSFORM PROCESSOR USING SERIAL PROCESSING AND DECODER ARITHMETIC AND CONTROL SECTION, the FFT processor may be characterized as a digital processor which repetitively performs the basic computations AW+B and AW-B, where A and B are complex digital words, each corresponding to a different one of N digital samples to be analyzed, and W is a complex digital word corresponding to a weighting function or "twiddle factor". Mechanization involves use of a multiplier to provide components of the complex product AW, storage means to store such product, and an adder/subtractor for combining such stored product to generate the complex product AW and to combine this complex product with the components of the complex variable B.

Detailed arithmetic processing of the sequential computations in a sequency analyzer or FFT machine, as a practical matter, involves reorganizing the discrete fourier transform data matrix into submatrices, each of which requires simpler arithmetic operations, and the results of which simpler operations may be merely simply combined, rather than multiplied. Such reorganization process is referred to generically as decimation, the two classical methods of reorganizing the data matrix being referred to as decimation-infrequency and decimation-in-time. The basic resultant computational operation is called a "butterfly".

A fuller discussion of the FFT "butterfly" arithmetic for both decimate-in-frequency and decimate-in-time applications, is provided in my co-pending Application Ser. No. 092,387 filed Nov. 8, 1979 for SIMPLIFIED FAST FOURIER TRANSFORM BUTTERFLY ARITHMETIC UNIT (now issued as U.S. Pat. No. 4,275,452). A yet more general discussion may be found in the text "Digital Signal Processing" by Peled and Liu, published by John Wiley and Sons, New York (1976). The above-noted co-pending patent application is directed to reducing the machine steps and arithmetic sequences involved in performing the bufferfly computation. Such reference discloses a simplified butterfly arithmetic unit employing a pair of registers for storing the respective sum and difference of the components, W.sub.R and W.sub.I, of the complex-butterfly twiddle factor, W, as phase-shifted cosine values. Controlled switching of two accumulators, responsive to alternate ones of the sum and difference registers, allows generation of the complex weighted butterfly output function, y=wz, without the necessity of discrete multipliers.

Such use of discrete multipliers has long been a source of machine complexity and limited machine speed. While the use of such discrete multipliers may be successfully avoided by means of my above-noted co-pending application, Ser. No. 092,387 (now U.S. Pat. No. 4,275,452), yet the use of discrete multipliers can be rendered less onerous by the use of a "lock-up table" type complex multiplier, employing square-function read-only memories (ROM's) in a quarter-square multiplier type configuration, in accordance with the inventive concept disclosed more fully hereinafter.

By means of the concept of the invention there is provided a four-port digital complex multiplier means for overcoming the above-noted limitations of the prior art and for enabling a more efficient performance of the FFT butterfly arithmetic. Such multiplier means employs ROM's as square function look-up tables. Each of the four ports is responsive to a respective one of the component values of two complex numbers. The square function lock-up memories are coupled to various ones of the input ports, and cooperate with quarter-square multiplier means to provide component complex products. An output subtractor and an output summer, responsive to mutually exclusive pairs of the quarter square multipliers, provide a respective real and imaginary component of the product of the two complex numbers.

In a preferred embodiment of the invention, a digital arithmetic device is provided for performing the multiplication of two complex values. There is included eight square function memories, a first, second, third and fourth one of the memories being responsive to at least a respective one of four input ports of the device for providing values indicative of the respective squares of the values supplied by such ports. A fifth, sixth, seventh and eighth one of the memories is responsive to a mutually exclusive pair of the four input pairs of the input ports for providing values indicative of the respective squares of a preselective combination of the mutually exclusive input pairs. A first quarter-square multiplier responsively coupled to the outputs of at least the first and fifth memories provides an output indicative of a first product; a second quarter-square multiplier responsively coupled to the outputs of at least the second and sixth memories provides an output indicative of a second product; a third quarter-square multiplier responsively coupled to the outputs of at least the third and seventh memories provides an output indicative of a third product; and a fourth quarter-square multiplier responsively coupled to the outputs of at least the fourth and eighth memories provides an output indicative of a fourth product. A first digital combiner is responsively coupled to the outputs of the first and third quarter-square multipliers provides an output indicative of the real component of the complex product AB of the two complex numbers of interest, and a second digital combiner responsively coupled to the output of said second and fourth quarter-square multipliers provides an output indicative of the imaginary component of such complex product.

In normal operation of the above-described arrangement, the squares of the component values are merely looked-up in response to the memories being addressed by such component values, the various squared values being selectively combined in the manner of quarter square multiplication to effect several component values of the real and imaginary components of the complex product. The combination of the several component values for each component of the complex product results in the determination of the complex product in resolved form.

Such parallel-addressed look-up table technique in combination with the quarter-square method provides a simplified mechanization for a complex multiplier which, in combination with a complex adder and complex subtractor, further provides convenience and simplification in the mechanization of a FFT butterfly arithmetic unit. Such simplification allows the processing of increased bandwidths with improved resolution, and reduced processing time.

Accordingly, it is an object of the invention to provide an improved device for performing complex multiplication.

It is another object of the invention to perform complex multiplication by means of a ROM-based quarter-square multiplier technique.

A still further object is to provide a simpler mechanization for performing FFT butterfly arithmetic.

These and other objects of the invention will become apparent from the following discription, taken together with the accompanying drawings in which:

FIG. 1 is a block diagram of a complex multiplier illustrating one aspect of the invention;

FIG. 2 is a block diagram of an alternate embodiment of complex multiplier illustrating a further aspect of the invention;

FIG. 3 is a block diagram of a fast fourier transform device employing a decimate-in-frequency-type butterfly arithmetic, and embodying the concept illustrated in FIG. 1;

FIG. 4 is a block diagram of a fast fourier transform device employing a decimate-in-time type butterfly arithmetic, and embodying the concept illustrated in FIG. 1;

FIG. 5 is a block diagram of a fast fourier transform device employing a decimate-in-frequency type butterfly arithmetic and embodying the concept illustrated in FIG. 2;

FIG. 6 is a block diagram of a fast fourier transform device employing a decimate-in-time type butterfly arithmetic and embodying the concept illustrated in FIG. 2;

FIG. 7 is a block diagram of a digital arithmetic device embodying a square-by-parts concept;

FIG. 8 is a block diagram of a quarter-square multiplier; and

FIG. 9 is a block diagram of the quarter-square multiplier of FIG. 8, embodying the square-by-parts concept of FIG. 7.

In the drawings, like reference characters refer to like parts.

Referring now to FIG. 1, there is schematically illustrated in block diagram form a digital signal processing system embodying an aspect of the inventive concept. There is provided a digital arithmetic device for performing multiplication of two complex values, A=(A.sub.R +jA.sub.I) and B=(B.sub.R +jB.sub.I), and comprising four input ports 11, 12, 13 and 14 and representing the applied complex component values, A.sub.R, B.sub.R, A.sub.I and B.sub.I, respectively; four input summing means 15, 16, 17 and 18. There is also provided eight square function memories 21, 22, 23, 24, 25, 26, 27 and 28, of which elements 21, 22, 23 and 24 represent a respective first, second, third and fourth one of said memories, responsive to a respective one of input ports 11, 12, 13 and 14, as illustrated, for providing values indicative of the respective squares thereof, A.sub.R.sup.2, A.sub.I.sup.2, B.sub.R.sup.2, B.sub.I.sup.2. Elements 25, 26, 27 and 28 represent a respective fifth, sixth, seventh and eighth one of said memories, responsive to a respective one of said four input summing means 15, 16, 17 and 18, each of said input summing means, in turn, being responsive to a mutually exclusive pair of the four input pairs of the input ports (A.sub.R, B.sub.R), (B.sub.R, A.sub.I), (A.sub.I, B.sub.I), and (B.sub.I, A.sub.R) for providing values indicative of the respective squares of said respective summed input pairs (A.sub.R +B.sub.R).sup.2, (B.sub.R +A.sub.I).sup.2, (A.sub.I +B.sub.I).sup.2 and (B.sub.I +A.sub.R).sup.2. A first three-input adder 31 is responsively coupled to the outputs of the first, second and fifth (i.e., elements 21, 22 and 25) for providing an output indicative of the product A.sub.R B.sub.R ; a second three-input adder 32 is responsively coupled to the outputs of the second, third and sixth memories (i.e., elements 22, 23 and 26) for providing an output indicative of the product A.sub.I B.sub.R ; a third three-input adder 33 is responsively coupled to the outputs of said third, fourth and seventh memories (i.e., elements 23, 24 and 27) for providing an output indicative of the product A.sub.I B.sub.I ; and a fourth three-input adder 34 responsively coupled to the outputs of said first, fourth and eighth memories (i.e., elements 21, 24 and 28) for providing an output indicative of the product A.sub.R B.sub.I. A subtractor 41 responsively coupled to the outputs of said first and third three-input adder provides an output indicative of the real component of the complex product AB, and an adder 42 responsively coupled to the output of said second and fourth three-input adders for providing an output indicative of the imaginary component of the complex product AB.

In normal operation of the arrangement of FIG. 1, the cooperation of each of digital combiners 31, 32, 33 and 34 with its three associated square function memories and input summing means as a multiplier is the same, an appreciation of which may be obtained by a consideration of first digital combiner 31, first, second and fifth memories 21, 22 and 25 and central memory input summing means 15. Such multiplier arrangement in FIG. 1 processes the two factors A.sub.R and B.sub.R by means of digital summer 15 to provide the value [A.sub.R +B.sub.R ], applied as an address input to square function memory 25. The readout of central memory 25 to such address is the square, [A.sub.R +B.sub.R ].sup.2. Similarly applying the inputs A.sub.R and B.sub.R as respective addresses to first and second memories 21 and 22 provides the respective read-outs A.sub.R.sup.2 and B.sub.R.sup.2. Digital combiner 31 differentially combines the output [A.sub.R +B.sub.R ].sup.2 of memory 25 with the sum [A.sup.2 +B.sup. 2 ] of the outputs of memories 21 and 22:

Accordingly, it is to be appreciated that the illustrated arrangement of digital combining means 31 in FIG. 1 functions to provide an output indicative of the scalar product of the two values on input ports 11 and 12, corresponding to one component of the value of the real portion (AB).sub.R of the complex product AR. Similarly, the digital combiner 33 in cooperation with elements 17, 23, 24 and 27 provide an output A.sub.I B.sub.I indicative of the scalar product of the two values on input ports 13 and 14, and corresponding to another component of the value of the real portion of the complex product AB. Thus, it may be appreciated that digital combining means 32 and 34, being similarly arranged as digital combining means 31 and 32, similarly cooperate to provide respective values, 2A.sub.I B.sub.R and 2A.sub.R B.sub.I, indicative of components of the value of the imaginary portion (AB).sub.I of the complex product AB, such value occurring as the output of adder 42. Subtractor 41 differentially combines the scalar components as (2A.sub.R B.sub.R -2A.sub.I B.sub.I) to provide an output indicative of the real component (AB).sub.R of the complex product AB=(A.sub.R +jA.sub.I) (B.sub.R +jB.sub.I).

An alternate arrangement of the complex multiplier device of FIG. 1 is shown in FIG. 2.

Referring now to FIG. 2, there is schematically illustrated in block diagram form an alternate embodiment of the concept of the invention. There is provided a digital arithmetic device for performing multiplication of the two complex values, A=(A.sub.R +jA.sub.I) and B=(B.sub.R +jB.sub.I) and comprising four input ports, 11, 12 13, and 14, eight square function memories, 21, 22, 23, 24, 25, 26, 27 and 28; and four output combining means 31, 32, 33 and 34, output subtractor 41 and output adder 42, as in FIG. 1, but with the following differences. Elements 21, 22, 23 and 24, representing a first, second, third and fourth one of the memories are each responsive to a respective sum of a pair of the input ports, as illustrated, for providing values indicative of the respective squares of said respective sums, (A.sub.R +B.sub.R).sup.2, (B.sub.R +A.sub.I).sup.2, (A.sub.I +B.sub.I).sup.2 and (B.sub.I +A.sub.R).sup.2. Also, elements 25, 26 27 and 28, representing a respective fifth, sixth, seventh and eighth one of the memories are each responsive to a difference between the ports of a mutually exclusive pair of the input ports for providing values indicative of the respective squares of the respective differences, (A.sub.R -B.sub.R).sup.2, (B.sub.R -A.sub.I).sup.2, (A.sub.I -B.sub.I).sup.2 and (B.sub.I -A.sub.R).sup.2. First digital combiner 31 is responsively coupled to the outputs of first and fifth memories 21 and 25 for providing an output indicative of the product A.sub.R B.sub.R ; a second digital combiner 32 is responsively coupled to the outputs of second and sixth memories 22 and 26 for providing an output indicative of the product A.sub.I B.sub.R ; a third digital combiner 33 is responsively coupled to the outputs of third and seventh memories 23 and 27 for providing an output indicative of the product A.sub.I B.sub.I ; and a fourth digital combiner 34 is responsively coupled to the outputs of fourth and eighth memories 24 and 28 for providing an output indicative of the product A.sub.R B.sub.R.

In normal operation of the arrangement in FIG. 2 as a complex multiplier, each pair of square function memories, set of adder and subtractor and associated one of output differential combining means 31, 32, 33 and 34 cooperate as a quarter-square multiplier, as shown more particularly in FIG. 8.

Referring to FIG. 8, there is shown a quarter-square multiplier comprising a parallel adder 131 and a parallel subtractor 132 having two common inputs A and B (each shown as being an exemplary 16-bit parallel input). A first square function memory 133, having an address input coupled to the output of adder 131, provides a read-out (A+B).sup.2 indicative of the square of the sum of the inputs to element 131. A second square function memory 133', having an address input coupled to the output of subtractor 132, provides a read-out (A-B).sup.2 indicative of the square of the difference between the inputs to element 132. An output subtractor 134, input coupled to the outputs of look-up memories 133 and 133', provides an output corresponding to the difference between the outputs of the two memories 133 and 133':

Such output (4AB) of element 134 is thus seen to be indicative of the product of the two inputs A and B, but for a scaling factor which may be applied by an attenuation element 135 or included in the scaling of subtractor 134 or by any other convenient means well understood in the art, as explained more fully in my co-pending application Ser. No. 130,653 filed Mar. 17, 1980 for A ROM-BASED PARALLEL DIGITAL ARITHMETIC DEVICE. As is also explained in such co-pending application, the size of the look-up memory capacity required to perform such square function in the quarter-square multipliers of FIGS. 1, 2 and 9 hereof may be substantially reduced by the use of the concept of a fully parallel arithmetic square-by-parts type of mechanization. An exemplary mechanization of such concept, as disclosed in the above-noted co-pending application, is shown in FIG. 7.

Referring to FIG. 7, there is provided a fully-parallel digital arithmetic device for obtaining the square, C.sup.2, of a value, C, via parts of the value C and involving a reduction in memory requirements. As illustrated, the device of FIG. 7 has 16 parallel inputs (corresponding to 2.sup.16 or 1024 unsigned addresses), although the concept is not so limited and any even number of unsigned addresses may be used. Three square function ROM's 211, 212 and 213, are employed, one (element 211) responsive to the most significant-bits half (C.sub.M) of a parallel input, the second ROM 112 responsive to the least-significant bits half (C.sub.1) of the parallel input, and the third one 133 responsive to the sum of said most significant bits and least-significant bits. The outputs of the square function ROM's are then combined and scaled to effect a square-by-parts of the applied input value, C, by means of elements 215, 216, 217 and 218.

That this output corresponds to the value, C.sup.2, may be seen as follows: First, define C as the sum of two component values, A and B, where A corresponds to the value contributed by the MSB half C.sub.M and B corresponds to the value contributed by LSB half, C.sub.l :

where:

A=2.sup.N/2 C.sub.M

B=C.sub.l and

N=the bit size or number of bits of C.

Therefore:

Squaring

The right hand member of Equation (7) is seen to be identical to the mechanization illustrated in FIG. 7, as to illustrate a novel square-by-parts method of mechanization. For the 16-bit input word size (i.e., N=16) 32-bit word size output illustrated in FIG. 7, two ROM's (elements 211 and 212), each require 2.sup.8 -1 or 255 addresses, with 16 bits per address, a total of 255.times.16 or 4,080 bits per ROM. The center ROM (element 213) requires a 2.sup.9 -1 or 511 addresses with 18 bits per address or a total of 9,198 bits. Thus, the three ROM's represent a memory requirement of only 17,358 bits, as compared to a corresponding single square function memory requirement of (2.sup.2N -1) addresses with 32 bits per address for a total of 1.4.times.10.sup.11 bits.

Still further economies may still be effected in the square function look-up memory requirements, as are also explained in my above-noted co-pending application Ser. No. 130,653 filed Mar. 17, 1980.

A pair of such arithmetic devices, each corresponding to the arrangement of FIG. 7, may be advantageously combined to economically effect the product AB of two values, A and B, in the manner of a quarter-square multiplier. For example, such a device may be substituted for each of elements 133 and 133' in FIG. 8, as shown in FIG. 9.Similarly, such device may be substituted for any square function look-up memory shown in FIGS. 1-6, whereby the advantages of high-speed parallel processing and reduced memory size may be realized, as disclosed more fully in my above-noted co-pending application Ser. No. 130,653 filed Mar. 17,1980.

Efficient digital arithmetic means, employing look-up square function memories, for performing complex multiplication, having been disclosed, application of such digital arithmetic means to fast fourier transform analyzers will now be shown, by aid of FIGS. 3, 4, 5 and 6. FIGS. 3 and 5 illustrate a decimate-in-frequency type FFT butterfly unit and FIGS. 4 and 6 illustrate a decimate-in-time type FFT butterfly unit. FIGS. 3 and 4 illustrate alternate embodiments of the complex multiplier arrangement disclosed in FIG. 1, while FIGS. 5 and 6 illustrate embodiments of the complex multiplier arrangement disclosed in FIG. 2.

Referring to FIG. 3, there is illustrated a decimate-in-frequency type FFT butterfly arithmetic for performing the complex arithmetic operations:

where u, v, w, x and y are all complex values. More particularly:

(10b)

The combination of elements for performing such arithmetic operation are a complex adder 51A and 51B for effecting the respective real and imaginary sums indicated by Equations (10a) and (10b); a complex subtractor 52A and 52B for effecting the respective real and imaginary differences (u.sub.R -v.sub.R) and (u.sub.I -v.sub.I): and a complex multiplier 44 for multiplying the resolved differences by the corresponding component values w.sub.R and w.sub.I of the resolved complex twiddle factor w. The result of such complex multiplication is the values of the components y.sub.R and y.sub.I of the resolved complex product, indicated by Equations (11a) and (11b).

In such arrangement, input terminals 11 and 12 of multiplier 44 are responsively coupled to the respective output of complex subtracting elements 52A and 52B, and input terminals 12 and 14 are responsively coupled to a respective input source indicative of the values w.sub.R and w.sub.I, whereby the resolved complex product thereof appears at the outputs of elements 41 and 42 as y.sub.R and y.sub.I, respectively, of the decimate-in-frequency FFT butterfly arithmetic process.

The alternate embodiment in FIG. 4 illustrates a decimate-in-time type FFT butterfly arithmetic unit, comprised of a complex multiplier 44, complex adder 51A and 51B, and complex subtractor 52A and 52B. By means of such arrangement, the following complex arithmetic operation is performed:

More particularly:

In such arrangement, input terminals 11 and 13 of multiplier 44 are respectively coupled to an input source indicative of the component values v.sub.R and v.sub.I, respectively, of the resolved complex number, v; and input terminals 12 and 14 are respectively coupled to an input source indicative of the component values w.sub.R and w.sub.I of the resolved twiddle factor, w, whereby the components (vw).sub.R and (vw).sub.I of the resolved complex product vw appear at the respective outputs of elements 41 and 42. Element 51A of the complex adder is responsively coupled to the output of element 41 and a source (not shown) indicative of the component value u.sub.R (of the resolved complex value u) to provide the output x.sub.R, while adder element 51B is responsively coupled to the output of element 42 and a source (not shown) indicative of the component value u.sub.I, to provide the output x.sub.I, whereby complex adder 51A and 51B is seen to cooperate to provide the respective real and imaginary sums indicated by Equations (14a) and (14b).

Element 52A of the complex subtractor is responsively coupled to the output of element 41 and to the source (not shown) of signal u.sub.R, while element 52B is responsively coupled to the output of element 42 and the source (not shown) of signal u.sub.I, whereby complex subtractor 52A and 52B cooperates to provide the respective real and imaginary differences indicated by Equations (15a) and (15b), of the decimate-in-time type FFT butterfly arithmetic process.

Although the decimate-in-time type device of FIG. 4 is illustrated as employing as element 44 that embodiment of complex multiplier shown in FIG. 1, it is to be understood that the concept illustrated by the arrangement in FIG. 4 is not so limited, and the complex multiplier embodiment of FIG. 2 may be substituted therefor, as shown in FIG. 6. Similarly, it is also to be understood that, while the decimate-in-frequency type device of FIG. 3 is illustrated as employing as element 44 that embodiment of complex multiplier shown in FIG. 1, the concept illustrated by the arrangement of FIG. 3 is not so limited and the complex multiplier embodiment of FIG. 2 may be substituted therein, as shown in FIG. 5.

Accordingly, there has been illustrated a highly useful improvement in digital arithmetic for effecting complex multiplication and for performing FFT butterfly arithmetic by means of look-up type square function memories in a quarter-square type multiplier arrangement. The utility of such square function look-up table type mechanization is, in turn, promoted by the square-by-parts parallel data processing concept disclosed in my above-noted co-pending Application Ser. No. 130,653 filed Mar. 17, 1980, whereby the density of the memory requirement may, as an extremely practical matter, be substantially reduced and significantly abbreviated, and the data processing speed correspondingly increased.

Although the invention has been described and illustrated in detail, it is to be clearly understood that the same is by way of illustration and example only and is not to be taken by way of limitation, the spirit and scope of this invention being limited only by the terms of the appended claims.