Apparatus for Computing Two-Dimensional Discrete Fourier Transforms

1. Technical Field

This invention relates to data processing devices designed to compute complex mathematical functions and, more particularly, to an apparatus which relies upon the use of polynomial transforms to compute the two-dimensional discrete Fourier transforms to two-dimensional signals.

2. Background Art

A discrete Fourier transform (DFT) is a well-known mathematical function which is used to convert the representation in the time domain of a sampled signal into its representation in the frequency domain, and vice versa. The development of digital techniques has enabled many digital devices to be implemented for the purpose of computing DFTs. Such devices, which only permit computing the one-dimensional DFT to a one-dimensional signal, are extensively used at the present time to process digital signals and, more specifically, one-dimensional signals.

This is being accompanied by significant development work in the field of digital image processing. Image processing is characterized in that the image signal is two-dimensional. In image processing, there are many applications in which it is useful and often necessary to map the image signal into its representation in the frequency domain. This can be done by using a two-dimensional DFT. Examples of such applications include the two-dimensional filtering of an image as described in "Theory and Application of Digital Signal Processing", by L. R. Rabiner and B. Gold, Chapter 7, Prentice-Hall, Inc., 1975; the analysis of pictures of the Earth as supplied by Earth resources satellites; and the X-ray technique called tomography.

The computation of a two-dimensional DFT involves a very large number of simple arithmetic operations such as multiplications and additions. The computation of a two-dimensional DFT of dimension N.times.N usually requires computing 2 N one-dimensional DFTs of N terms. (The dimension N.times.N means that N.times.N is the number of terms whose DFT is to be computed, or, to put it another way, that the image to be mapped is defined by N.times.N samples). If the number of multiplications corresponding to a one-dimensional DFT of dimension N is designated M.sub.1, then the computation of the two-dimensional DFT will necessitate 2 NM.sub.1 multiplications.

An article by H. J. Nussbaumer and P. Quandalle entitled, "New Polynomial Transform Algorithms for Fast DFT Computation" in Proceedings of the 1979 IEEE International Conference on Acoustics, Speech and Signal Processing, Washington, D.C., Apr. 2-4, 1979, describes two methods of computing multi-dimensional DFTs by means of polynomial transforms. The article shows the manner in which a multi-dimensional DFT can be mapped efficiently into reduced one-dimensional DFTs by using polynomial transforms. It also shows that, by combining this approach with Rader-Brenner's fast Fourier transform algorithm, the number of operations necessary to compute a multi-dimensional DFT can be significantly reduced.

A disadvantage of the methods described in said article is that the complete mapping of a multi-dimensional DFT into one-dimensional DFTs requires a very large number of polynomial transforms and may therefore be difficult to implement.

It is the object of this invention to provide an apparatus for computing two-dimensional DFTs which does not require the use of a large number of polynomial transforms and is relatively simple to implement.

Generally, this invention provides an apparatus for computing the two-dimensional discrete DFT.

of N.sup.2 terms

arranged in N blocks of N terms each. The index n.sub.1 indicates the position of a given term within a block, and the index n.sub.2 the number of the block. The apparatus includes means for successively receiving the N blocks and means for multiplying the N terms within each block by N complex coefficients designated W.sup.-n.sbsp.1, respectively, thereby providing N blocks of N terms each which are then stored in a memory. The N block, designated X.sub.n.sbsb.2 (Z), are then applied to transformation means which derive therefrom N blocks written as

in accordance with the polynomial transform represented by the following relation: ##EQU1## wherein the multiplications by powers of Z correspond to rotations of the terms within the blocks followed by sign inversion of the overflow terms.

The apparatus of the present invention further includes means for respectively multiplying the N terms within each of the N blocks

by N complex coefficients W.sup.l, l=0, 1, . . . , N-1. The N.sup.2 terms of the two-dimensional DFT

are supplied by computation means which determine the N terms of the one-dimensional DFT of each of the N blocks

whose terms have been multiplied by the coefficients W.sup.l.

In another embodiment of the invention, the terms of the DFT X.sub.k.sbsb.1.sub.,k.sbsb.2 which correspond to k.sub.1 odd and k.sub.1 even are dealt with separately. Each of the N blocks of terms x.sub.n.sbsb.1.sub.,n.sbsb.2 becomes a couple of reduced blocks of N/2 terms respectively written as X.sub.n.sbsb.2.sup.1 (Z) and X.sub.n.sbsb.2.sup.2 (Z). The reduced blocks X.sub.n.sbsb.2.sup.2 (Z) are processed by an apparatus which is similar to the one used in the first embodiment of the invention and only differs therefrom in that the blocks being processed are only comprised of N/2 terms. The blocks X.sub.n.sbsb.2.sup.2 (Z) provide the N.sup.2 /2 terms of X.sub.k.sbsb.1.sub.,k.sbsb.2 which correspond to k.sub.1 even. The N reduced blocks X.sub.n.sbsb.2.sup.1 are applied to transformation means which derive therefrom N reduced blocks written as

in accordance with the polynomial transform ##EQU2## the N/2 terms of each of the blocks

are respectively multiplied by the coefficients w.sup.2l, l=0, 1, . . . , N/2-1. The N.sup.2 /2 terms of X.sub.k.sbsb.1.sub.,k.sbsb.2 which correspond to k.sub.1 odd are supplied by computation means which compute the N/2 terms of the one-dimensional DFT of each of the N blocks

whose terms have been multiplied by the coefficients W.sup.2l.

The foregoing and other objects, features and advantages of the invention will be apparent from the following more particular description of a preferred embodiment of the invention, as illustrated in the accompanying drawings.

FIG. 1 is a block diagram illustrating a first embodiment of the invention.

FIG. 2 illustrates an exemplary embodiment of the device 20 of FIG. 1 which operates to compute polynomial transforms.

FIG. 3 shows a second embodiment of the invention.

FIG. 4 illustrates an exemplary embodiment of the reduction device 81 of FIG. 3.

Polynomial transforms have been discussed in several publications and in particular in the following articles:

"Digital Filtering Using Polynomial Transforms", by H. J. Nussbaumer, In Electronics Letters, Vol. 13, No. 13, June 23, 1977;

"Computation of Convolutions and Discrete Fourier Transforms by Polynomial Transforms", by H. J. Nussbaumer and P. Quandalle, in IBM Journal of Research and Development, Vol. 22, No. 2, March 1978.

It may however be convenient at this point to restate the definition of a polynomial transform.

Let {P.sub.m (Z)} be a set of N polynomial each of which is defined by the following relation ##EQU3## The polynomial transform of the set {P.sub.m (Z)} is defined as a set of N polynomial {A.sub.k (Z)}, each of which is expressed as ##EQU4## Similarly, the inverse transform is defined as ##EQU5## The computation of a polynomial transform reduces to additions and to multiplications by powers of Z. For example, since relation (2) is defined modulo (Z.sup.N +1), we have Z.sup.N =-1, and multiplications of the polynomials P.sub.m (Z) by powers of Z correspond to simple rotations of the terms a.sub.n,m within the polynomials P.sub.m (Z) followed by sign inversion of the overflow terms. Polynomial additions are performed by adding separately the terms corresponding to the same power of Z. For a more detailed discussion, reference to the aforementioned articles is suggested.

Before describing the apparatus of the present invention, we shall discuss its principles of operation. Let us consider the two-dimensional DFT X.sub.k.sbsb.1.sub.,k.sbsb.2, of dimension N.times.N, of the samples x.sub.n.sbsb.1.sub.,n.sbsb.2, which is defined by the well-known relation ##EQU6## k.sub.1, k.sub.2 =0, . . . , N-1, where j=.sqroot.-1.

Note that since k.sub.1 and k.sub.2 can both assume N different values, the DFT X.sub.k.sbsb.1.sub.,k.sbsb.1 is comprised of N.sup.2 terms. If we put

we may write relation (4) in the form ##EQU7##

Relation (6) may also be written in the form ##EQU8##

Replacing the representation given by relation (7) with an equivalent polynomial representation, we get ##EQU9## Note that: since n.sub.1 and n.sub.2 can assume N different values, relation (8) defines N polynomials of N terms each;

since n.sub.2 and k.sub.2 can assume N different values, relation (9) defines N polynomials of N terms each; and

X.sub.k.sbsb.1.sub.,k.sbsb.2 defines the DFT of N.sup.2 terms.

Let us now assume that N is a power of 2. Since (2k.sub.1 +1) is odd, the product (2K.sub.1 +1) k.sub.2 modulo N maps all values of k.sub.2. Thus, (2k.sub.1 +1) k.sub.2 may be substituted for k.sub.2 in relations (9) and (10), which yields the equivalent relations (11) and (12), respectively: ##EQU10## Since, according to relation (12), X.sub.(2k.sbsb.1.sub.30 1)k.sbsb.2 (Z) is defined modulo (Z-W.sup.2k.sbsp.1.sup.+1), we get Z=W.sup.2k.sbsp.1.sup.+1 and we may substitute Z for W.sup.2k.sbsp.1.sup.+1 in relation (11), which becomes ##EQU11## X.sub.(2k.sbsb.1.sub.+1)k.sbsb.1 (Z) is a polynomial of N terms which may be written as ##EQU12## where Y.sub.(2k.sbsb.1.sub.+1)k.sbsb.2, l represents the N terms of the polynomial for a given value of (2k.sub.1 +1)k.sub.2, with the position of Y.sub.(2k.sbsb.1.sub.+1)k.sbsb.2, l within the polynomial being given by the variable Z.sup.l.

Substituting (14) into (12) yields ##EQU13## Since Z=W.sup.2k.sbsp.1.sup.+1, relation (15) may be written as ##EQU14## The terms of the DFT X.sub.k.sbsb.1.sub.,k.sbsb.2 are obtained through a simple permutation of the terms of the DFT X.sub.k.sbsb.1.sub.,(2k.sbsb.1.sub.+1)k.sbsb.2.sub., as a result of which the couple of indicates k.sub.1,(2k.sub.1 +1)k.sub.2 becomes k.sub.1,k.sub.2.

In summary, the computation of the DFT X.sub.k.sbsb.1.sub.,k.sbsb.2 of the samples x.sub.n.sbsb.1.sub.,n.sbsb.2 involves the steps of:

computing the polynomials x.sub.n.sbsb.2 (Z) from the samples x.sub.n.sbsb.1.sub.,n.sbsb.2 in accordance with relation (8),

computing the polynomials X.sub.(2k.sbsb.1.sub.+1)k.sbsb.2 (Z) in accordance with relation (13),

computing the DFT X.sub.k.sbsb.1.sub.,(.sub.2k.sbsb.1.sub.+1)k.sbsb.2 in accordance with relation (16), and

obtaining the terms of the DFT X.sub.k.sbsb.1.sub.,k.sbsb.2 through a simple permutation of the terms of X.sub.k.sbsb.1.sub.,(2k.sbsb.1.sub.+1)k.sbsb.2.

A first embodiment of the apparatus of the present invention will now be described with reference to FIG. 1.

Assume that it is desired to compute the two-dimensional DFT X.sub.k.sbsb.1.sub.,k.sbsb.2, with k.sub.1,k.sub.2 =0, 1, . . . , N-1 of N blocks of N terms each, where N is power of 2. These terms will be written as

where n.sub.1 denotes the position of a given term within a block, and n.sub.2 denotes that block.

These N blocks of N terms could represent, for example, an image defined by N.times.N samples, with each block making up a row of samples. For the sake of clarity, it will be assumed in the following description that an image is to be processed, and x.sub.n.sbsb.1.sub.,n.sbsb.2 will be termed a "sample" and a block a "row". Accordingly, the index n.sub.1 will indicate the position of a given sample within a row and the index n.sub.2 will indicate that row.

It will further be assumed that these samples are coded in digital form and stored in a memory 10.

The rows of samples are sequentially read out of the memory 10 and loaded in a N-stage shift register 12 under the control of a control memory 11. The memory 11 is conventionally comprised of a read-only memory which contains a microprogram controlling the sequence of readout operations performed in the memory 10. The sequence of operations is adapted to the capacity of the output bus of the memory 10, to the number N of samples and to the number of bits used to code each sample. For example, assuming that the capacity of the output bus is sixteen bits, that N is equal to 16 and that a single bit is used to code each sample, then the sixteen samples in a given row can be read out and loaded in the register 12 simultaneously. The N samples

within any row loaded in the register 12 are respectively applied to N multipliers 13, . . . , 14, . . . , 15 in which they are respectively multiplied by the quantities W.sup.0, . . . , W.sup.-n.sbsp.1, . . . , W.sup.-(N-1), where W=e.sup.-j.pi./N.

(In order to avoid using parentheses, the quantity W.sup.-(N-1) has been shown as W.sup.1-N in the FIG.).

It should be noted at this point that since W is a complex quantity and since the samples x.sub.n.sbsb.1.sub.,n.sbsb.2 may be complex quantities, the N multipliers 13, . . . , 14, . . . , 15 are conventional complex multipliers. These provide the following sequence of N terms

which are respectively loaded in the N stages of a register 16.

The sequence of N terms (17) may be expressed in polynomial algebra by means of the polynomial ##EQU15## which is the polynomial already given by relation (8). Note that the variable z.sup.n.sbsp.1 indicates the position of the term x within the sequence, and that, although relation (8) includes the summation sign .SIGMA., the various terms of the sequence are not actually summed together. Relation (8) is merely intended to enable the sequence (17) to be represented. Thereafter, the sequence (17) will be referred to as the polynomial X.sub.n.sbsb.2 (Z).

The N terms of the polynomial X.sub.n.sbsb.2 (Z) contained in the register 16 are then loaded in a memory 17 under the control of the memory 11. After all terms within the N rows of samples stored in the memory 10 have successively been multiplied by the quantities W.sup.0, . . . , W.sup.-n.sbsp.2, . . . , W.sup.-(N-1), the N polynomials x.sub.n.sbsb.2 (Z), with n.sub.2 varying between 0 and (N-1), are available in the memory 17. The polynomials X.sub.n.sbsb.2 (Z) are sequentially read out of the memory 17 and loaded in a N-stage register 18 under the control of the memory 11. The polynomials contained in the register 18 are sequentially applied through a bus 19 to a device 20 which computes the N polynomials X.sub.(2k.sbsb.1.sub.+1)k.sbsb.2 (Z) in accordance with the polynomial transform defined by relation (13), this being done under the control of the memory 11 via a bus 72. An exemplary embodiment of the device 20 will be described later with reference to FIG. 2.

The N polynomials X.sub.(2k.sbsb.1.sub.+1)k.sbsb.2 (Z) are stored in a memory 21 via a bus 22.

The terms of the polynomials X.sub.(2k.sbsb.1.sub.+1)k.sbsb.2 (Z) will be written Y.sub.(2k.sbsb.1.sub.+1)k.sbsb.2.sub.,l, with l=0, 1, . . . , N-1.

The polynomial X.sub.(2k.sbsb.1.sub.+1)k.sbsb.2 (Z) can therefore be expressed by means of relation (14), which is repeated below for convenience: ##EQU16## The N polynomials X.sub.(2k.sbsb.1.sub.+1)k.sbsb.2 (Z), with (2k.sub.1 +1)k.sub.2 =0, 1, . . . , n-1, are read out of the memory 21 and sequentially loaded in a N-stage register 23 under the control of the memory 11. The N terms

of each polynomial X.sub.(2k.sbsb.1.sub.+1)k.sbsb.2 (Z) are respectively applied to N complex multipliers 24, . . . , 25, . . . , 26, in which they are respectively multiplied by the quantities

The following N terms are respectively obtained at the output of the N multipliers and loaded in a N-stage register 27:

If we put

we may represent the sequence (18) by the polynomial of N terms ##EQU17## The N terms of each of the polynomials S.sub.(2k.sbsb.1.sub.+1)k.sbsb.2 (Z) available in the register 27 are fed to a device 28 which operates to compute one-dimensional DFTs. This device may be any of the many commercially available devices that use the fast Fourier transform technique for computing DFTs. An exemplary embodiment of such a device is described in "Theory and Application of Digital Signal Processing", by L. R. Rabiner and B. Gold, published by Prentice-Hall, Englewood Cliffs, N.J. 1975, Chapter 10, pp. 573-626.

From the N terms of each of the polynomials S.sub.(2k.sbsb.1.sub.+1)k.sbsb.2 (Z), the device 28 computes the N terms of the DFT ##EQU18## It will be noted that, since W=e.sup.-j.pi./N, relation (21) is in fact the DFT X.sub.k.sbsb.1.sub.(2k.sbsb.1.sub.+1)k.sbsb.2 already given by relation (16), which is repeated below for convenience: ##EQU19## The N terms of the DFT X.sub.k.sbsb.1.sub.,(2k.sbsb.1.sub.+1)k.sbsb.2 supplied by the device 28 are stored in a memory 29. More specifically, each of these N terms is stored in a memory location whose address is representative of the value of the couple of indices k.sub.1, (2k.sub.1 +1)k.sub.2 corresponding to the term involved. For example, the term X.sub.3,4 would be stored at an address representative of the couple of values 3, 4.

The device 28 supplies N terms from each of the N polynomials S.sub.(2k.sbsb.1.sub.+1)k.sbsb.2 (Z). After the polynomials have been sequentially applied to the device 28, the memory 29 contains the N.sup.2 terms of the DFT X.sub.k.sbsb.1.sub.,(2k.sbsb.1.sub.+1)k.sbsb.2.

As mentioned in the above discussion of the principles of operation of the present apparatus, all of the terms of the DFT X.sub.k.sbsb.1.sub.,k.sbsb.2 are obtained through a permutation of the terms of the DFT X.sub.k.sbsb.1.sub.,(2k.sbsb.1.sub.+1)k.sbsb.2. This permutation takes place as the latter terms are read out of the memory 29, with the index (2k.sub.1 +1)k.sub.2 being converted to k.sub.2.

This is achieved under the control of the memory 11 by means of tables such as the one shown below.

Assuming that N=8 and that it is desired to read out the eight terms corresponding to

the following table will be used:

This table shows that, for example, the term X.sub.1,2 of the DFT X.sub.k.sbsb.1.sub.,k.sbsb.2 will be found at the address 16 of the memory 29.

Referring now to FIG. 2, an exemplary embodiment of the device 20, which is used to compute polynomial transforms, will be described. For clarity, it has been assumed that N=4. The device of FIG. 2 includes three cascade-connected shift stages 30, 31, and 32. In the illustrated example, the output bus 19 of the register 18 (FIG. 1) comprises four lines 33-36 which are respectively connected to position I of four two-position switches 37-40, all of which are simultaneously controlled by a signal impressed on a line 41. The lines 33-35 are respectively connected to position II of the switches 38-40, and the line 36 is connected to position II of the switch 37 through an inverter 42. The outputs of the switches 37-40 are respectively connected via lines 43-46 to position I of four switches 47-50, all of which are simultaneously controlled by a signal received via a line 51. The lines 43 and 44 are respectively connected to position II of the switches 49 and 50, while the lines 45 and 46 are respectively connected to position II of the switches 47 and 48 through inverters 52 and 53. The outputs of the switches 47-50 are respectively connected via lines 54-57 to position I of four switches 58-61, all of which are simultaneously controlled by a signal traveling on a line 62. The lines 54-57 are respectively connected through four inverters 63-66 to position II of the switches 58-61, whose outputs are respectively applied to four accumulators 67-70 which have their outputs connected to the four lines in the buss 22 (FIG. 1). A decoder 71 receives the commands generated by the control memory 11 via the bus 72 and has three outputs respectively connected to the lines 41, 51, and 62. The operation of the device of FIG. 2 will now be described in relation to an exemplary situation. The device of FIG. 2 receives from the register 18 the successive polynomials defined by relation (8) and computes the polynomial transform ##EQU20## X.sub.(2k.sbsb.1.sub.+1)k.sbsb.2 is a polynomial transform of N.sup.2 terms whose computation involves multiplications by powers of Z and additions. Since relation (13) is defined modulo (Z.sup.N +1), we have Z.sup.N =-1, and the multiplications by powers of Z correspond to simple rotations of the terms of X.sub.n.sbsb.2 (Z) within the polynomial followed by sign inversion of the overflow terms.

Assume the following polynomials X.sub.n.sbsb.2 (Z), n.sub.2 =0, 1, 2, 3: ##EQU21## Using relations (22), the device of FIG. 2 should provide the following polynomials: ##EQU22## Since Z.sup.4 =-1, we have Z.sup.8 =1 and relations (23) may be written as ##EQU23## Still referring to FIG. 2, the polynomial X.sub.0 (Z) is available in the register 18. The decoder 71 receives from the control memory 11 a command representative of the value of the exponent modulo 8 of Z in relation (13), i.e., a command representative of the value of 2n.sub.2 k.sub.2 modulo 8. Initially, k.sub.2 =0, n.sub.2 =0, the command present on the bus 72 is representative of the value 0, and the signals on the lines 41, 51 and 62, which lines correspond to the binary weights 2.sup.0, 2.sup.1 and 2.sup.2, are at a down level, so that the switches 37-40, 47-50 and 58-61 are all set to position I. The terms b.sub.0,0, b.sub.1,0, b.sub.2,0, b.sub.3,0 of X.sub.0 (Z) are directly loaded in the accumulators 67-70.

The polynomial X.sub.1 (Z) thus becomes available in the register 18. We now have k.sub.2 =0 and n.sub.2 =1, the command present on the bus 72 still is representative of the value 0, and the terms b.sub.1,1, b.sub.2,1, b.sub.3,1 of X.sub.1 (Z) are respectively added to the terms b.sub.0,0, b.sub.1,0, b.sub.2,0 and b.sub.3,0 contained in the accumulators 67-70. The process continues and, after X.sub.3 (Z) has been loaded in the register 18, the terms of the polynomial X.sub.0 (Z) are obtained in the accumulators 67-70 in accordance with relations (24). These terms are then loaded in the memory 21 (FIG. 1) via the bus 22, and the accumulators 67-70 are reset to zero. Note, that the polynomials X.sub.n.sbsb.2 (Z) are read out of the memory 17 by means of conventional read/write operations to ensure that they will not be erased in the memory 17. The polynomials X.sub.0 (Z) is again read out of the memory 17 and loaded in the register 18. We now have k.sub.2 =1, n.sub.2 -0, the command present on the bus 72 is representative of the value 0, and the terms of S.sub.0 (Z) are loaded in the accumulators 67-70. The polynomials X.sub.1 (Z) thus, becomes available in the register 18. We now have k.sub.2 =1 and n.sub.2 =1 and the command on the bus 72 is representative of the value 2. The signals on the lines 41 and 62 are both at a down level and the signal on the line 51 is at an up level. The switches 37-40 and 58-61 are set to position I while the switches 47-50 are set to position II. The term b.sub.0,1 of X.sub.1 (Z) is loaded in the accumulator 69 through the line 33, the switch 37 (set to position I), the line 43, the switch 49 (set to position II), the line 56 and the switch 60 (set to position I). The term b.sub.1,1 is similarly loaded in the accumulator 70. The term b.sub.2,1 is inverted and loaded in the accumulator 67 through the line 35, the switch 39 (set to position I), the line 45, the inverter 52, the switch 47 (set to position II), the line 54, and the switch 58 (set to position I). Similarly, the term b.sub.3,1 is inverted and loaded in the accumulator 68. The polynomial S.sub.2 (Z) thus, becomes available in the register 18. We now have k.sub.2 =1 and n.sub.2 =2, and the command present on the bus 72 is representative of the value 4. The signals on the lines 41 and 51 are both at a down level and the signal on the line 62 is at an up level; the switches 37-40 and 47-50 are all set to position I and the switches 58-61 are all set to position II. The terms b.sub.0,2, b.sub.1,2, b.sub.2,2 and b.sub.3,3 are respectively inverted by the inverters 63-66 and loaded in the accumulators 67-70. The polynomial X.sub.3 (Z) is then available in the register 18. We now have k.sub.2 =1 and n.sub.2 =3 and the command present on the bus 72 is representative of the value 6. The signal present on the line 41 is at a down level and the signals present on the lines 51 and 62 are both at an up level. The switches 37-40 are all set to position I and the switches 47-50 and 58-61 are all set to position II. The term b.sub.0,3 is inverted by the inverter 65 and loaded in the accumulator 69. The term b.sub.1,3 is inverted by the inverter 66 and loaded in the accumulator 70. The term b.sub.2,3 is inverted twice by the accumulators 52 and 63 and is therefore loaded unchanged in the accumulator 67. The term b.sub.3,3 is inverted twice by the inverters 53 and 64 and is consequently loaded unchanged in the accumulator 68. The terms of the polynomial X.sub.2k.sbsb.1.sub.+1 (Z) are obtained in the accumulators 67-70 in accordance with relations (24). These terms are then loaded in the memory 21 via the bus 22 and the accumulators 67-70 are reset to zero.

It will be apparent to those skilled in the art that the terms of the polynomials

will similarly be obtained after two additional cycles.

The embodiment of the device 20 as illustrated in FIG. 2 is only given by way of example and it will be apparent to those skilled in the art that the polynomial transform defined by relation (13) could also be computed by means of a fast Fourier transform (FET) decomposition.

One of the advantages of the apparatus of FIG. 1 is that it uses a single polynomial transform instead of several as proposed in the aforementioned article by H. Nussbaumer and P. Quandalle published in "Proceedings of 1979 IEEE International Conference on Acoustics, Speech and Signal Processing". However, the greater simplicity of the apparatus of FIG. 1 is achieved at the cost of a slightly higher number of arithmetic operations. The second embodiment of the present invention shown in FIG. 3 is a compromise between the degree of complexity of the apparatus and the number of arithmetic operations required. The second embodiment uses the apparatus of FIG. 1 and the method of reducing polynomials discussed in the article just mentioned.

Before describing the apparatus of FIG. 3, its principles of operation will be discussed. To this end, the representation of the DFT X.sub.k.sbsb.1.sub., k.sbsb.2 given by relation (7) will be replaced by the following equivalent polynomial representation: ##EQU24## (Z.sup.N -1) is the product of the two polynomials (Z.sup.N/2 -1) and (Z.sup.N/2 +1). Each of the polynomials X.sub.n.sbsb.2 (Z) of the relation (25) is reduced modulo (Z.sup.N/2 +1) and modulo (Z.sup.N/2 -1) so as to obtain reduced polynomial of N/2 terms written as X.sub.n.sbsb.2.sup.1 (Z) and X.sub.n.sbsb.2.sup.2 (Z), respectively.

As stated earlier, reductions modulo (Z.sup.N/2 -1) and modulo (Z.sup.N/2 +1) of the polynomial X.sub.n.sbsb.2 (Z) of N terms will respectively yield the following polynomials of N/2 terms: ##EQU25## We also have ##EQU26## The polynomial representation of relations (25) to (27) can be split up as follows:

--for k.sub.1 odd: ##EQU27##

--for k.sub.1 even: ##EQU28##

We shall first consider the case of k.sub.1 odd. Since N is a power of 2 and k.sub.1 is odd, N and k.sub.1 are relatively prime and the product k.sub.1 k.sub.2 modulo N maps all values of k.sub.2. The product k.sub.1 k.sub.2 modulo N is a simple permutation of the indices k.sub.2. Thus, k.sub.1 k.sub.2 may be substituted for k.sub.2 in relations (29) and (30), and the equivalent relations (34) and (35) are respectively obtained: ##EQU29## Since X.sub.k.sbsb.1.sub.k.sbsb.2 is defined modulo (Z-W.sup.2k.sbsp.1) in accordance with relation (35), we have Z=W.sup.2k.sbsp.1 and we may substitute Z for W.sup.2k.sbsp.1 in relation (34), which becomes ##EQU30## X.sub.k.sbsb.1.sub.k.sbsb.2.sup.1 (Z) is a polynomial of N/2 terms which may be written as Substituting (37) into (35) yields ##EQU31## Since Z=W.sup.2k.sbsp.1, relation (38) may be written as ##EQU32## Since k.sub.1 is odd, we may put

Relation (39) may then be written as ##EQU33## Relation (40) corresponds to the one-dimensional DFT of the N/2 terms of

The N/2 terms of the DFT X.sub.(2p+1),k.sbsb.2 for p=0,1, . . . , N/2-1 and k.sub.2 =0, 1, . . . , N-1, that is, the terms of X.sub.k.sbsb.1.sub.,k.sbsb.2 that correspond to k.sub.1 odd, will be obtained through a simple permutation of the terms of

as a result of which the couple of indices (2p+1), (2p+1)k.sub.2 will become (2p+1), k.sub.2.

The case of k.sub.1 even will now be discussed.

To this end, the rperesentation given by relations (31) to (33) will be replaced by the following equivalent relations: ##EQU34## Since N is a power of 2 and (2k.sub.1 +1) is odd, as has been seen, (2k.sub.1 +1)k.sub.2 can be substituted for k.sub.2 in relations (42) and (43), which yields the equivalent relations ##EQU35## Since Z=W.sup.2(2k.sbsp.1.sup.+1) in accordance with (45), relation (44) becomes ##EQU36## X.sub.(2k.sbsb.1.sub.+1)k.sbsb.2 (Z) is a polynomial of N/2 terms which may be written ##EQU37## Substituting (47) into (45) yields ##EQU38## Since Z=W.sup.2(2k.sbsp.1.sup.+1), relation (48) may be written ##EQU39## Since k.sub.1 is even, we may put

and write relation (50) as ##EQU40## Relation (51) corresponds to the one-dimensional DFT of the N/2 terms v.sub.(2p+1)k.sbsb.2.sub.,l l.sup.W.sbsp.2l.

The N.sup.2 /2 terms of the DFT X.sub.2p,k.sbsb.2, for p=0, 1, . . . , N/2-1 and k.sub.2 =0, 1, . . . , N-1, that is, the terms of X.sub.k.sbsb.1.sub.,k.sbsb.2 which corresponds to k.sub.1 even, will be obtained through a simple permutation of the terms of X.sub.2p,(2p+1)k.sbsb.2 whereby the couple of indices 2p,(4p+1)k.sub.2 will be substituted for the couple of indices 2p,k.sub.2.

Referring next to FIG. 3, the second embodiment of the present invention will be described. As in the example illustrated in FIG. 1, it will be assumed that it is desired to compute the two-dimensional DFT

of an image defined by N.times.N samples

The N.sup.2 terms of the DFT X.sub.k.sbsb.1.sub.,k.sbsb.2 include the N.sup.2 /2 terms of the DFT written as

which correspond to k.sub.1 odd, and the n.sup.2 /2 terms of the DFT written as X.sub.2p,k.sbsb.2 which correspond to k.sub.1 even.

The rows of samples x.sub.n.sbsb.1.sub.,n.sbsb.2 stored, for example, in a memory, as they were in the apparatus of FIG. 1, are sequentially applied via a line 80 to a reduction device 81 to be described in detail with reference to FIG. 4. The device 81 operates to reduce each row of N samples to:

a polynomial of N/2 terms X.sub.n.sbsb.2.sup.1 (Z) as defined by relation (28), and

a polynomial of N/2 terms X.sub.n.sbsb.2.sup.2 (Z) as defined by relation (31).

The terms of the polynomials X.sub.n.sbsb.2.sup.1 (Z), n.sub.2 =0,1, . . . , N-1 from which the N.sup.2 /2 terms of the DFT X.sub.k.sbsb.1.sub.,k.sbsb.2 that correspond to k.sub.1 even will be derived, are stored in a memory 83 via a line 84.

The N polynomials X.sub.n.sbsb.2.sup.1 (Z) are sequentially read out of the memory 83 and loaded in a N/2-stage register 85. The polynomials X.sub.n.sbsb.2.sup.1 (Z) stored in the register 85 are sequentially applied to a device 86 which computes the polynomial transform X.sub.k.sbsb.1.sub.k.sbsb.2.sup.1 (Z) in accordance with relation (36), which is repeated below for convenience: ##EQU41## and may also be written ##EQU42## The device 86 is of course similar to the device 20 (FIG. 1) an exemplary embodiment of which has been described with reference to FIG. 2. As has been seen, X.sub.(2p+1)k.sbsb.2.sup.1 represents N polynomials of

N/2 terms each and each polynomial is in turn represented by the following relation, which is identical to relation (37): ##EQU43## The polynomials X.sub.(2p+1)k.sbsb.2.sup.1 (Z) are sequentially loaded in a N/2-stage register 87. The N/2 terms of a given polynomial X.sub.(2p+1)k.sbsb.2.sup.1 (Z), that is, the N/2 terms

contained in the register 89, are respectively applied to N/2 complex multipliers 88, . . . , 89, . . . , 90 in which they are respectively multiplied by the quantities

The following N/2 terms are respectively obtained at the output of these N/2 multipliers:

and loaded in a N/2-stage register 91. The N/2 terms contained in the register 91 are then applied to a device 92 which computes the N/2 terms of the one-dimensional DFT ##EQU44## which is the DFT X.sub.(2p+1), (2p+1)k.sbsb.2 of relation (40).

These N/2 terms are stored in a memory 93, with each term being stored in a memory location whose address is representative of the value of the couple of indices (2p+1), (2p+1)k.sub.2 corresponding to the term involved, as explained earlier with reference to FIG. 1. The device 92 supplies N/2 terms from each of the N polynomials successively stored in the register 91. After these N polynomials have been processed by the device 92, the N.sup.2 /2 terms of the two-dimensional DFT X.sub.k.sbsb.1.sub.,k.sbsb.2 that correspond to k.sub.1 off are available in the memory 93.

The method of processing the polynomials X.sub.n.sbsb.2.sup.2 (Z) from which the terms of the DFT X.sub.k.sbsb.1.sub.,k.sbsb.2 that correspond to k.sub.1 even are derived will now be described.

The polynomial X.sub.n.sbsb.2.sup.2 (Z) supplied by the reduction device 81 are processed by an apparatus similar to that of FIG. 1. In the interest of clarity, this apparatus has been shown in a dash box in FIG. 3 and a prime notation has been used to distinguish certain elements of FIG. 3 from corresponding elements of FIG. 1 identified with similar reference numerals. (For simplicity, the various registers 12, 16 . . . , of FIG. 1 have not been shown in the equivalent apparatus illustrated in FIG. 3). The polynomials X.sub.n.sbsb.2.sup.2 (Z) supplied by the reduction device 81 are stored in a memory 10' via a line 94.

The N/2 terms of a given polynomial X.sub.n.sbsb.2.sup.2 (Z) that are available in the memory 10' are respectively applied to the N/2 complex multipliers 13', . . . , 14'. . . , 15' in which they are respectively multiplied by the quantities

In the FIG., W.sup.-2(N/2-) has been written in the form W.sup.2-N).

After the respective terms have been multiplied by each of the above quantities, each of the polynomials X.sub.n.sbsb.2.sup.2 (Z) is converted to a polynomial X.sub.n.sbsb.2.sup.20 (Z) as defined by relation (41), which is repeated below ##EQU45## The polynomials X.sub.n.sbsb.2.sup.20 (Z) successively provided by the multipliers 13', . . . , 14', . . . , 15', are stored in a memory 17', and are sequentially applied to a device 20' which computes the polynomial transform X.sub.(2k.sbsb.1.sub.+1)k.sbsb.2.sup.2 (Z) in accordance with relation (46), which is repeated below: ##EQU46## Since k.sub.1 =2p, p=0,1, . . . , N/2-1, relation (46) is identical to the following relation: ##EQU47## The device 20' is of course similar to the device 20 of FIG. 1.

As has been seen, X.sub.(4p+1)k.sbsb.2.sup.2 (Z) represents N polynomials of N/2 terms each, and each polynomial can in turn be represented by means of the following relation, which is identical to relation (47): ##EQU48## The N/2 terms of each of the N polynomials X.sub.(4p+1)k.sbsb.2.sup.2 (Z) successively provided by the device 20' are respectively multiplied in the N/2 multipliers 24', . . . , 25', . . . , 26, by the quantities

In the FIG., W.sup.2(N/2-1) has been written as W.sup.N-2).

The following N/2 terms are respectively obtained at the output of these N/2 multipliers

and applied to a device 28' which computes the N/2 terms of the one-dimensional DFT ##EQU49## which is the DFT X.sub.2p,(4p+1)k.sbsb.2 of relation (52).

These N/2 terms are stored in the memory 93, each term being stored in a memory location whose address is representative of the value of the couple of indices 2p, (4p+1)k.sub.2 corresponding to that term, as explained earlier with respect to FIG. 1.

It will be apparent to those skilled in the art that the apparatus of FIG. 3 is controlled by a control memory (not shown, for simplicity). The term of X.sub.k.sbsb.1.sub.,k.sbsb.2 are read out of the memory 93 under the control of said control memory, taking into account the following permutations of indices:

for k.sub.1 odd:

with k.sub.1 =2p+1, p=0, 1, . . . , N/2-1.

for k.sub.1 even:

with k.sub.2 =2p, p=0, 1, . . . , N/2-1.

To this end, tables such as the one shown below by way of example are used by the control memory. Assuming that N=8 and that it is desired to read out the 8 terms of X.sub.k.sbsb.1.sub.,k.sbsb.2 that correspond to k.sub.2 =1 and k.sub.1 =0,1, . . . , 7, the following table will be used:

This table shows that, for example, the terms X.sub.1,1 and X.sub.6,1 of the DFT X.sub.k.sbsb.1.sub.,k.sbsb.2 will respectively be found at the address 11 and 65 of the memory 93.

Referring next to FIG. 4, an exemplary embodiment of the reduction device 81 of FIG. 2 will be described.

The samples x.sub.h.sbsb.1.sub.,n.sbsb.2 are applied via the line 80 to the input of a delay element 100 which introduces a delay equal to N/2 times the time interval elapsing between the transmission of two consecutive samples on line 80. This line is connected to the (-) input of a subtractor 101 which has its (+) input connected to the output of the delay element 100. The line 80 is also connected to an input of an adder 102 which has its other input connected to the output of the delay element 100. The output of the subtractor 101 is connected to an input of an AND gate 103 which has its other input connected to a line 104. The output of the adder 102 is connected to an input of an AND gate 105 which has its other input connected to the line 104. The outputs of the AND gates 103 and 105 are respectively connected to the lines 84 and 94 (FIG. 3).

In operation, the rows of samples are serially applied to the line 80.

While the first N/2 samples within each row, i.e., the samples x.sub.n.sbsb.1.sub.,n.sbsb.2 for n.sub.1 =0,1 . . . , N/2-1, are applied to the line 80, the line 104 is at a down level so that the AND gates 103 and 105 are inhibited. While the last N/2 samples within each row, i.e., the samples x.sub.n.sbsb.1.sub.,n.sbsb.2 for n.sub.1 =0, 1, . . . , N/2-1, are applied to the line 80, the line 104 is at an up level, so that the AND gates 103 and 105 are activated. When the sample x.sub.n.sbsb.1.sub.+N/2,n.sbsb.2 is applied to the line 80, the sample x.sub.n.sbsb.1.sub.,n.sbsb.2 available at the output of the delay element 100, and the terms (x.sub.n.sbsb.1.sub.,n.sbsb.2 -x.sub.n.sbsb.1.sub.+N/2,n.sbsb.2) and (x.sub.n.sbsb.1.sub.,n.sub.2 +x.sub.n.sbsb.1.sub.+N/2,n.sbsb.2) are respectively provided on the lines 84 and 94. Thus, the terms of the polynomials X.sub.n.sbsb.2.sup.1 (Z) and X.sub.n.sbsb.2.sup.2 (Z) respectively defined by relations (28) and (31) are sequentially obtained on the lines 84 and 94.

While the invention has been particularly shown and described with reference to a preferred embodiment thereof, it will be understood by those skilled in the art that numerous changes in form and detail may be made therein without departing from the spirit and scope of the invention.