Optimal Unified Architectures for the Real-Time Computation of Time-Recursive Discrete Sinusoidal Transforms

The invention relates to transform processors, and more specifically, to real time discrete sinusoidal transform processors.

Discrete sinusoidal transforms play significant roles in various digital signal processing applications, such as spectrum analysis, image and speech signal processing, computer tomography, data compression, and signal reconstruction. Among different discrete sinusoidal transforms, the discrete cosine transform (DCT), the discrete sine transform (DST), discrete Hartley transform (DHT), and the discrete Fourier transform (DFT), are widely used because of their efficient performance. Recently, the Lapped Orthogonal Transform (LOT) and the Complex Lapped Transform (CLT) were introduced for transform coding with significantly reduced blocking effects and for motion estimation.

In the prior art, various special purpose computers and processor chips have been designed to accommodate specific operations. The algorithms specific to various transforms were implemented in hardware only designed to accommodate the handful of related algorithm transforms. This provided a simple solution to each transform problem, yet did not address the collective problem of solving a family of transforms. Examples of these include U.S. Pat. Nos. 4,760,543 (Ligtenberg et al.), 4,797,847 (Dunhamel), 4,679,163 (Arnould et al.), 4,831,574 (Dunhamel), 4,385,363 (Widergren et al.), 4,831,440 (Borgers et al.), 4,881,192 (Woudsma et al.), 4,791,598 (Liou et al.), 4,288,858 (Merola et al.), 4,674,125 (Carlson et al.), 4,849,922 (Riolfo), 5,053,985 (Friedlander et al.), and 4,449,194 (Wilhelm).

Various "fast" algorithms have been proposed in the past. Some of the more well-known in the art are disclosed in the following articles:

"A fast recursive algorithm . . . " published in the IEEE Transactions: Acoustic, Speech, Signal Processing, Vol. ASSP-35 on pages 1455-1461 in October 1987 and authored by H. S. Hou;

"A fast computational algorithm for the discrete cosine transform" published in the IEEE Transactions: Communication, vol. COM-25 on pages 1004-1009 in September 1977 and authored by W. H. Chen, C. H. Smith and S. C. Fralick;

"A new algorithm to compute the discrete cosine transform" published in the IEEE Transactions: Acoustics, Speech, Signal Processing, vol. ASSP-32 on pages 1243-1245 in December 1984 and authored by B. G. Lee.

Though these fast transforms have been implemented in hardware, the efficiency is reduced by architectural implementation and design constraints. Some factors retarding their functionality are large numbers of multipliers, latency and limitation on transform size N.

The prior art devices do not simultaneously produce both DCT and DST signals. In the past to provide DCT and DST a transposition was required. A single design for a transform processor wherein implementation in either lattice structure or infinite impulse response (IIR) filter structure has yet to be proposed. In past designs, the interconnections were global, not local, for optimal VLSI design. The past architectures have some limitations to the number of N-point data. The time-recursive nature of discrete sinusoidal transforms (DXT) was not used in the design and implementation of prior art devices.

In real-time signal processing applications, especially in speech and image communications and radar/sonar signal processing, input data arrives serially. In prior art fast Fourier transforms (FFT) based algorithms, serial data is buffered and then transformed using FFT scheme of complexity O(N log N), where is O is the order of complexity and N is the transform size. Buffering the data requires O(N) time. In the prior art, "fast" algorithm based architectures required O(log N) time using O(N log N) hardware. This increases complexity of the processor, reduces effectiveness of VLSI design implementation and slows down overall transform speed.

In recent years visualized communications have become an expanding market, due to recent advances of video/image data compression and maturity of very large scale integrated (VLSI) technology. Digital processing of video signals has come of age and their applications related to video signal processing such as video phone, high definition television (HDTV), video conferencing, and multimedia are of great interest.

In the field of digital video and its applications, various groups have been working on standardizing and simplifying the art. Many options have been proposed by the Joint Photographic Experts Group (JPEG)), the International Telegraph and Telephone Consultative Committee (CCITT), and the Moving Picture Experts Group (MPEG). None of the techniques proposed performed as well as the market needs.

The present invention may be implemented in either lattice structure (1) or IIR filter structure (2). The two structures are similar in every detail except were a lattice module is located, it is replaced by an IIR filter. The equivalent IIR is derived using the transfer function of the specific lattice structure. The transfer functions of various discrete transforms may be generalized and used to implement a universal filter module. The configuration of the architecture is dependent upon user requirements. In time-recursive lattice architecture, two transforms called dual generated pairs, are obtained simultaneously. The result is providing both DCT and DST simultaneously. A systematic approach to derive the time-recursive unified filter architecture for any discrete transform is disclosed. The resulting unified filter architectures have similar second order autoregressive structure with minimum number of multipliers. This time-recursive technique may be generalized to multi-dimensional transforms by using only a one-dimensional transform architecture and simple shift registers. The resulting design is asymptotically optimal in speed and area.

The present invention uses a 1-D transform processor as a building block for obtaining various transform processors. The 1-D DCT/DST Lattice structure (as shown in FIG. 3) comprises read only memory (ROM) (10 and 20), adders (30), shift register (40), latches (50 and 60) and feedback loops. The two output signals at nodes (2) and (3) are DCT and DST respectively of the input signal applied to node (1). The ROMs are used for both implementing the algorithm and multiplication functions. Clocking is provided so that computations are performed on both phases. The IIR filter equivalent can be obtained by replacing the lattice array with a filter array.

The present invention provides a universal transform processor using at least one 1-D transform processor to produce N dimensional transforms without transposition. The present invention also provides a fully pipelined structure with a throughput of N clock cycles for N X N successive serial inputs as well as parallel or serial outputs. Additionally, both DST and DCT are produced simultaneously.

The present invention merges buffering and transform operations into a single unit of total hardware complexity O(N). Therefore the present architecture needs only a constant time with O(N) hardware. The present architectures generate time-recursive transforms, not limited to block transforms. Further, unlike FFT's, the present invention has only local interconnections and thus, is better suited for VLSI design.

The present invention may be implemented to efficiently perform functions using only two one dimensional DCT processors with throughput rate of N clock cycles for N X N successive input data frames without boundary on N.

The present invention allows a family of sinusoidal transforms to be implemented in hardware and fabricated in VLSI with real time processor speed. Other objects and features of the present invention will be apparent from the following detailed description of the preferred embodiment.

FIGS. 1a and lb are block diagrams showing a universal lattice module constructed in accordance with a preferred embodiment of the invention;

FIG. 2 is a block diagram showing a universal IIR filter module constructed in accordance with an alternate embodiment of the invention;

FIGS. 3a through 3f are diagrams and schematics showing building blocks of a lattice module with clocks;

FIG. 4 is a graph of voltages v. time which illustrates ROM performance;

FIG. 5 is a diagram showing Lattice Array Block O;

FIG. 6 is a diagram of the structure for Lattice Array Block, where i=1,2,3, ... , n-1;

FIG. 7 is a diagram of a lattice module for 3-D analysis;

FIG. 8 is a block diagram of the architecture for a frame-recursive 3-D DCT transform;

FIG. 9 is a block diagram of the architecture for a 3-D DCT transform;

FIG. 10 is a graphical representation of a time-recursive based 3-D transform;

FIG. 11 is a block diagram of a configuration of a direct form filter 3-D block DCT transform;

FIG. 12 is a block diagram of a 2-D DXT transform;

FIGS. 13a and 13b are block diagrams of basic building structure of a moving frame DXT transform;

FIGS. 14a and 14b are block diagrams of basic structures of a block DXT transform;

FIG. 15 is a block diagram of a parallel IIR filter structure for 1-D DXT transform;

FIG. 16 is a block diagram of an IIR filter structure for DCT and DST

transforms;

FIG. 17 is a block diagram of an IIR filter structure for a DHT and DFT transforms;

FIG. 18 is a block diagram of an IIR filter structure for LOT and LCT transforms;

FIG. 19 is a block diagram of an IIR filter structure for real operation of LOT and CLT transforms;

FIG. 20 is a block diagram of a IIR filter structure for an IDCT transform;

FIG. 21 is a block diagram of a IIR filter structure for an IDST transform; and

FIG. 22 is a block diagram of a filter structure for a IDCLT transform.

A new scheme employing a time-recursive approach is presented. Since data arrives serially, in digital signal transmission, the orthogonal transforms are considered from a time-recursive point of view, instead of an entire block of data at a time. This is denoted as X.sub.c (k,t) and X.sub.s (k,t) as the DCT and DST of a data sequence. The time-recursive relation for the new transforms Xc(k,t+1) and Xs(k,t+1) in terms of the previous transforms X.sub.c (k,t) and X.sub.s (k,t) are given by: ##EQU1## The lattice module manifesting this approach is shown in FIG. 1, for k=0,1,2, ... , N-1. It should be noted that the transform domain data X(k,t) has been decomposed into N disjoint components that use similar lattice modules with different multipliers coefficients in them. This structure requires 6N-8 multipliers and 5N-1 adders. The total computational time is N clock cycles. It is important to note that the transformed data of subsequent input vectors may be generated every clock cycle.

Since the lattice module is the most important component in DCT/DST lattice structures, this discussion will focus on the VLSI implementation of the lattice module. Every lattice module in the DCT/DST structure is a modified normal form digital filter, which has the least roundoff noise and is less sensitive to coefficient inaccuracy. In the following discussion we will use an 8-point DCT with 8-bit input signals and 12-bit output signals using two's complement binary number system as an example.

The distributed-arithmetic scheme our VLSI implements was first disclosed in two publications "VLSI implementation of 16.times.16 Discrete Cosine Transform," published in IEEE Transactions on Circuits and Systems, vol. 36, No. 4 on pages 610-617 in April 1989 and "Application of Distributed Arithmetic to Digital Signal Processing-Tutorial Review," published in IEEE ASSP Magazine on pages 4-19 in July 1989. Multiplication results stored in ROM are computed using double precision numbers on a SUN workstation. Using this realization, roundoff errors due to multiplication are minimized since distributed-arithmetic, transforms explicit multiplication into implicit multiplication. Therefore, system errors are due to the quantization errors resulting from finite precision implementation and addition operations. Under the 12-bit two's complement realization, root mean square (RMS) error values are approximately 40 dB, which is satisfactory for most applications.

One way to implement the lattice module is to realize two multipliers with same input by one ROM, Using this method, the ROM size of each lattice array is 13824 bits and the number of adders needed is 10. When the number of bits of the input signal is reduced, ROM size is reduced but the number of adders is increased. The adder is a 12-bit carry look-ahead full adder/subtracter which is constructed using three 4-bit carry look-ahead adders. Since ROMS need less area than general purpose multipliers and can achieve a higher speed, circuit implementations using this approach can be used for very high speed video signal processing.

Turning now to FIG. 3a, the main building blocks of the lattice structure, ROMs 10 and 20, adders 30, shift registers 40, and latches 50 are illustrated. These components will be described individually in this section. The critical path in the lattice modules is the feedback loop which includes one ROM and three adders. A traditional two-phase clocking scheme would use one phase to perform these computations and a second phase to latch the results. In order to make the two phases of the clock more symmetric, computations are performed on both phases of the clock. As shown in FIG. 3a, one addition and a ROM lookup is performed during the first phase and two additions are performed during the second phase. Intermediate results are stored in half-latches as described below.

The main component of the distributed-arithmetic based lattice structure is ROMs 10 and 20. Most existing ROMs are implemented based on a precharge concept, that is, the bit lines are precharged high during a precharge phase, and then selected word lines discharge some of the bit lines according to coefficients stored during an evaluation phase. In order to reduce ROM access time, a specific ROM design is used. FIG. 3b shows the detail of each cell in the ROM. An invertor with a feedback transistor and a transmission gate controlled by phase .rho..sub.1 is used as a sense amplifier at the output of the bit-lines. The bit lines are precharged to an intermediate voltage between ground (GND) and a predetermined voltage (Vdd). N-channel transistors are used to either charge bit line from this intermediate voltage to Vdd-Vt or discharge it to GND, during the evaluation phase. In this scheme, the array is fully populated, whereby the number of n-channel transistors in the array is MN, where M is the number of word lines and N is the number of bit lines. A `zero` is stored at a particular location, by connecting the n-channel transistor at that location to Vdd; a `one` is stored by connecting the transistor to GND. The cell size is only 13.lambda..times.16.lambda..

In the distributed-arithmetic scheme, multiplication of a 12-bit input number with a 12-bit sine or cosine coefficient is performed by two ROMs 10 and 20, each with 6-bit inputs and two adders. This reduces chip area needed to implement multiplication with fixed coefficients. The ROM includes two 6-bit decoders and two small ROMs. This 12-bit input is divided into two parts; the most significant 6-bits of the input are used to generate the coefficients for small ROM1 and the least significant 6-bits are used for small ROM2. The final result of the multiplication is obtained by adding the outputs of small ROM1 with a shifted version of the outputs of small ROM2.

Only the most significant 7-bit result of the multiplication is stored in ROM2. The sizes of small ROM1 and ROM2 are 64 words by 24 bits and 64 words by 14 bits, respectively.

In order to improve ROM access time, each 6-bit decoder is implemented as a tree consisting of two 3-bit decoders and a linear array of 64 AND gates. The delay time for this 6-bit decoder is 8.55 ns, while a straight-forward implementation would have a delay of 20.40 ns. The outputs of the 64 AND gates form the word lines of the ROM array. The logical layout of the 6-bit decoder is shown in FIG. 3c. The physical size of the final ROM is 1292.lambda..times.1646.lambda. which is much smaller than the area need by a general purpose multiplier. The total ROM access time is 20 ns.

Since lattice modules are implemented based on a word-serial bit-parallel approach, high-speed bit-parallel adders are necessary. A 12-bit carry lookahead adder was built using three 4-bit carry lookahead adders. Two large invertors are placed at the outputs of the adders to supply sufficient drive capability. The physical size of the 12-bit adder is 1022.lambda..times.256.lambda. and has a propagation delay of 18 ns.

There are two kinds of latches 50 and one shift register 40 in the circuit. One of the latches is the half-latch which is controlled by phase .PHI..sub.2 and is used to store intermediate results obtained from the adders. The logical representation of the 12-bit half-latch is depicted in FIG. 3c. The other latch is the reset controlled half-latch located in the feedback loop. Its logical circuit is shown in FIG. 3d. When a reset signal goes low, outputs from ROM2 and ROM3 are set to zero. The shift register located at the input stage of the system is a regular two phase shift register which delays the input sequence by eight clock cycles.

One reset control signal and two clock phases .PHI..sub.1 and .PHI..sub.2 are required in this system. Phase .PHI..sub.1 is used to latch the computational results from one adder and the ROM, while phase .PHI..sub.2 is used to latch results from the remaining adders. Since propagation delay times for the ROM and adder are approximately the same, we may make both clock phases as depicted in FIG. 3e. The reset signal is active low. One of the attractive features of this chip is the very simple control signals used. No additional logical control circuitry is needed in the design,

Having realized the symbolic layout of the individual blocks, the next issue is to integrate all of these components efficiently. This includes three ROMs, eleven adders, four half-latches, two reset controlled half-latches and one shift register. ROM2 and ROM3 are rotated by 90 and 270 degrees respectively to simplify inter-component routing. The chip accepts 8-bit input signals and produces 12-bit DCT and DST coefficients every 100 ns. The physical layout of the lattice module chip is depicted in FIG. 3f. There are 18000 transistors in the chip, most of which are used in the three fully-populated ROMs. The total size of the active circuitry is 5400.lambda..times.3400.lambda.. This is fabricated in a die of size 6800.lambda..times.4600.lambda. and packaged in a 40-pin chip.

Both logical and timing simulations were performed on this chip. From the simulation results, the word length of the ROM must be at least 9 bits to ensure that the signal to noise ratio (SNR) is greater than 40 Db. To reduce errors due to recursive computations, the word length of the ROM is increased to 12 bits. IRSIM is used to perform logic simulations on the layout of the chip. The results from IRSIM were compared with the DCT and DST of the same input sequence obtained from a C program written on a SUN workstation. The results are accurate up to the least significant bit of the 12-bit representation. The SNR of this computation, from simulations, is about 41 dB, which is satisfactory for image an video processing applications. SPICE simulations indicate that the worst case rise and fall time for the ROM bit-lines are 8 ns and 9 ns respectively. FIG. 4 shows the timing simulation for the entire ROM which includes the decoder, cell array, and sense amplifier.

The algorithm and architecture were successfully implemented in the first chip that may generate the 1-D DCT and DSCT simultaneously. The implementation of the lattice module used a distributive arithmetic method with a data rate of 116 Mb/s under 2 .mu.m CMOS technology. Fabricating using .PHI..8 .mu.m technology will result in a data rate of 320 Mb/s. These results clearly show that VLSI implementation of the present invention is very practical and functional for real-time image processing. Further, Table 2, located below shows a comparison of the Liu-Chiu1 and Lui-Chui2 SIPO and SISO architectures to well known prior hardware implementations of "fast" algorithms. The Lui-Chiu1 and Lui-Chui2 are simply the FIG. 3a implementation with SIPO and SISO I/O configurations. The present invention architecture using time-recursive algorithms provides a substantial increased in flexibility and integration.

The time-recursive approach has been shown to be effective in both hardware and computational complexity for the computation of discrete sinusoidal transforms (DXT) of time series input data streams. This approach will be extended to problems of computing the discrete fourier transform (DFT), lapped orthogonal transform (LOT), and the complex lapped orthogonal transform (CLT). Further, a unified view of lattice structures for time recursive approach will be disclosed.

The discrete sinusoidal transform DXT of a data sequence of length N at time t is denoted as: ##EQU2## where P.sub.n-t (k) are transform basis functions and C(k) are constants used for normalization. Most discrete sinusoidal transforms have dual generated pairs. The lattice structure used for generating one transform automatically generates its dual. For example the dual discrete cosine transform (DCT) is the discrete sine transform (DST). Both the transform and its dual have similar updating relations. The dual generated pairs are denoted by X.sub.xc (k,t) and X.sub.xs (k,t). The time recursive relation between X.sub.x (k,t) and X.sub.x (k,t+1) may be obtained by eliminating the effect of the first term of the previous sequence and updating the effect of the last term of the current sequence. The dual generating properties between transform pairs X.sub.xc (k,t) and X.sub.xs k,t) are given by: ##EQU3## where D.sub.c and D.sub.s are the associated cosine and sine transform kernels of the DXT with fixed index n. Coefficients e(k) and f(k) depend on the definition of the transforms and are always equal to one except for the two transforms LOT and CLT. That is, two transforms may be usually generated from each other in a lattice form as shown in FIGS. 1a and 1 b. The definition of the various discrete sinusoidal transforms and state the equations will be described below.

The one-dimensional(1-D) DCT of an input data sequence is defined as: ##EQU4## and the 1-D DST is defined as: ##EQU5##

The updated DCT and DST of the input data may be generated from X.sub.c (k,t) and X.sub.s (k,t) by the following relations: ##EQU6##

That is, the DCT and DST may be dually generated time-recursively in a lattice form.

The definition of Discrete Hartley Transform (DHT) is given by: ##EQU7##

The Discrete Fourier Transform (DFT) of N samples is defined as: ##EQU8##

The DHT uses real expressions ##EQU9## as the transform kernel, while DFT uses the complex exponential expression ##EQU10## as the transform kernel. Since the kernel of the DHT is a summation of cosine and sine terms, the kernel may be separated into a combination of a DCT-like and a DST-like transforms as follows: ##EQU11##

The X'.sub.c (k,t) is the DCT-I and the X'.sub.S (k,t) is the DST-I. The X'.sub.c (k,t) and X'.sub.s (k,t) may be dually generated from each other with the corresponding coefficients listed in Table 3 located below. Therefore, the DCT-I and DST-I are dual pairs. From the lattice structure shown in FIG. 1, the DHTs are obtained by adding the dual pairs X'.sub.c (k,t) and X'.sub.s (k,t). The real part of the DFT is X'.sub.c (k,t) and the imaginary part is X'.sub.s (k,t).

The Complex Lapped Transform (CLT) of 2N samples is defined as: ##EQU12##

The Lapped Orthogonal Transform (LOT) of 2N samples is defined as: ##STR6##

Since the LOT is obtained from the even and odd value of k, we focus on the dual generation for the CLT only. An Auxiliary Complex Transform (ACLT) of 2N samples may be defined as: ##EQU13##

Then, the CLT and ACLT may be dually generated with the corresponding coefficients listed in table 3 above. All the transforms mentioned above may be realized by a lattice structure as shown in FIG. 1. Table 3 lists the coefficients in the unified lattice structure for different transforms.

Transfer Function Approach

Input data arrive serially in most real-time signal processing applications. If we view the transform operation as a linear shift invariant (LSI) system which transforms input sequences of samples into their transform coefficients then the transform operation is similar to a filtering operation. The general approach to tackle a digital filter problem is to look at its transfer function. The transfer functions of the DXT may be derived using several approaches. We will derive them from the unified time-recursive lattice structure as shown in FIG. 1. The time difference equations, where the time index t is an integer parameter, for the dually generated pairs are:

and

where

and y.sub.xc,k (t) and y.sub.xs,k (t) corresponds to X.sub.xc (k,t) and X.sub.xs (k,t). The z transform deduced form the above difference equations are:

and

Y.sub.xs,k (z) can be expressed in terms of Y.sub.xc,k (z) and X'(z) as: ##EQU14## it follows that the transfer function for Y.sub.c,k (z)/X(z) as: ##EQU15## Similarly, the transfer function for Y.sub.s,k (z)/X(z) is given by: ##EQU16##

From Table 3 and the transfer functions derived above, the transfer functions of different discrete sinusoidal transforms are given by: ##EQU17##

Since the size of the input data is 2N in the CLT, the updated vector is 1-z.sup.2N instead of 1-z.sup.N. The transfer function is obtained by substituting the corresponding coefficients in tables 3 through 6 resulting in: ##EQU18##

Therefore, it follows that for the LOT,

It is known that the transfer function of these transforms are of finite impulse response. Hence, the poles in the denominator will be canceled by the zeros of ((-1).sup.k -z.sup.-N)in the nominator. It is observed that when the updating vector (1-z.sup.-N) is factored out, the basic structure of all the transforms are composed of a FIR and an IIR filter with a second order denominator and a first order numerator, therefore we are using an IIR filter to realize a FIR filter. This realization may greatly reduce hardware complexity compared with the implementation consisting of FIR structures.

From the transfer functions derived above, it may be observed that the DXT may be realized using a single universal filter module consisting of a shift register array and a second order IIR filter. This structure is depicted in FIG. 2. The coefficients of the universal IIR module for different transforms are listed in Table 4, below.

It should be noted that the DCT and the DST share the same denominator and may be simultaneously generated using an IIR filter structure with three multipliers as depicted in FIG. 16. Compared with the lattice structure for the DCT and DST, the IIR realization requires only half as many multipliers. The difference is that the IIR structure implements the denominator of the transfer function in a direct form, while the lattice structure implements the poles in a normal form. It may also be observed that a single unified filter structure may be used to generate both the DHT and the DFT. This structure is depicted in FIG. 17.

The IIR filter architecture for the LOT and CLT is shown in FIG. 18. In the following it is shown how to realize the CLT using real operations. The definition of the CLT may be rewritten as: ##EQU19##

If we define another transform with basis functions only length N, ##EQU20## then the CLT may be expressed in the form of: ##EQU21##

This leads to the CLT architecture as shown in FIG. 19 in which the t.sub.mm are generated by using the DCT and DST dual generating circuit as depicted in FIG. 16. The number of multipliers and adders required for these IIR filter structures are summarized in Table 5, below.

The architecture to generate 1-D DXT is depicted in FIG. 15. This parallel structure consists of a shift register array of size N, two adders, and N IIR filter modules. Two sets of inputs x(t+N)-x(t) and -x(t+N)-x(t) are generated for the even and odd filter modules respectively. When a new datum x(t) arrives, a new set of transform coefficients are obtained in O(1) time, therefore the throughput rate is O(1).

Inverse transforms are important in retrieving original information in digital communication systems. The inverse DHT and DFT are given by: ##EQU22## We observe that the transfer function of the inverse DHT(IDHT) is exactly the same as its forward transform. The transfer function of the inverse DFT(IDFT) is given by: ##EQU23## which is same as the DFT except that the imaginary part is negated. Therefore, the IDHT and IDFT may be realized by using the same architecture as those depicted in FIG. 17 except that an invertor is added at the output of the ImX.sub.f (k,t).

The inverse DCT and DST (IDCT and TDST) are defined as follows: ##EQU24## Because C(k)is inside the transform, the architectures require some modification. Since C(k)=1 except for k=0 or k=N, we can rewrite the expression as: ##EQU25## It should be observed that the first part of the above equation is of the same form as that of DCT except for the leading constant coefficients C(k). Hence, the transfer function of the IDCT is that of the DCT plus one delay term specified as follows: ##EQU26## This implies that the IDCT may be implemented by using the same architecture as the DCT and adding the compensated term ##EQU27## The architecture is shown in FIG. 20. Similarly, the IDST may be rewritten as: ##EQU28## whose transfer function is ##EQU29## The architecture for IDST is shown in FIG. 21.

The Inverse Complex Lapped Transform (ICLT) of samples is defined as: ##EQU30## The architecture of the IDCLT is depicted in FIG. 22. From the previous derivation, it may be seen that the inverse transforms may be obtained by using the same architectures of the forward transforms with one additional branch of multiplier.

The basis functions of all the discrete sinusoidal transforms mentioned above corresponds to a set of orthogonal polynomials. One of the important characteristics of orthogonal polynomials is that any three consecutive polynomials are related by the Fundamental Recurrence Formula given by:

The discrete transforms discussed in the previous section satisfy a simpler version of the recurrence relation. More precisely, the parameters c.sub.n and .lambda..sub.n are independent of n and the basis function P.sub.n (k)is periodic in n and k of period N. In these cases, the Fundamental Recurrence Formula may be rewritten as:

For different discrete sinusoidal transforms, the corresponding parameters k, c, .lambda. in the Fundamental Recurrence Formula are stated in Table 6, below.

Lemma 1: For all discrete transforms whose basis functions satisfy the Fundamental Recurrence Formula, the z-transform of the basis functions {P.sub.n (k)} may be expressed as a rational function with a second order denominator that is the characteristic equation of the Fundamental Recurrence Formula.

Proof: Since any P.sub.n (k) depends only on the previous two terms, the first two polynomial terms, P.sub.-1 (k) and P.sub.-2 (k), uniquely specify the entire set of basis functions.

Applying a z transform on index n to both sides of the Fundamental Recurrence Formula and ##EQU31## factoring out P(z,k), we obtain: ##EQU32## Because of the second-order recurrence relation, the denominators of the z-transform of the basis functions are second-order polynomials in z.

The characteristic equation of the Fundamental Recurrence Formula is obtained by solving the homogeneous solutions of the difference equation. The homogeneous equation is given by:

Combining both sides of the equation, we have:

Since P(z,k) does not equal to zero, we have that (.lambda.-(k-c)z+z.sup.2) equals to zero and hence the characteristics equation is (.lambda.-(k-c)z+z.sup.2), which is the denominator.

The transfer function of the discrete transforms (DXT) may be rewritten as: ##EQU33## Performing the z-transform on the index t on both sides of the above equation, we have: ##EQU34## which is the z-transform of the basis orthogonal polynomials with index z replaced by z.sup.-1 and multiplied by C(k)z.sup.-(N-1). That is, the transfer function of the discrete transform may also be expressed as a rational function with a second order denominator: ##EQU35## Here we illustrate another way to derive the transfer function of the discrete sinusoidal transforms. Substituting the coefficients listed in Tables 5 and 6, we obtain the transfer functions derived above.

Lemma 2: To compute the discrete sinusoidal transforms time recursively, we have to factor out the updating component (1-z.sup.-N) or (1+z.sup.-N) in the filter realization. There exists an updating component (1+z.sup.-N) or (1-z.sup.-N) in the nominator of the transfer function of the discrete sinusoidal transform, if and only if the boundary conditions of the basis function satisfy P.sub.0 -+P.sub.N and P.sub.-1 =+P.sub.N-1.

Proof: If the updating vector can be realized by (1+z.sup.-N) or ( 1-z.sup.-N), then the nominator must contain the factor (1+z.sup.-N) or (1-z.sup.-N). That is, the nominator can be expressed as:

since it is a (-N-1) degree polynomial. By expanding the right side of the above equation, we have:

it follows that:

and

This proves the necessary condition. If P.sub.0 -+P.sub.N and P.sub.-1 =+P.sub.N-1, then the nominator becomes: ##EQU36## which means the nominator contains the factor (1+z.sup.-N). Lemma 3: All the transforms that satisfies Lemma 1 and Lemma 2 can be realized by an updating FIR filter with transfer function (1-z.sup.-N) or (1+Z.sup.-N), and an IIR filter with second order denominator and first order nominator whose coefficients are dependent on) .lambda.(k-c), P.sub.0 and P.sub.-1. Proof: If Lemma 1 and Lemma 2 are satisfied, the transfer function may be expressed as: ##EQU37## Therefore, the transform may be realized by the filter structure as shown in FIG. 2. The coefficients are:

Lemma 3 implies that if a transform may be computed time-recursively, a maximum of four multipliers required to realize the transform. FIG. 2 shows a good example of this case. Lemma 4: For the discrete sinusoidal transforms, the roots of the characteristic equating belong to the set of the root of 1+z.sup.-N.

Proof: Since the discrete sinusoidal transform is FIR in natural, the roots of the denominators should be canceled by the zeros of the nominator. In general, the roots of the denominator are complex conjugate poles because of (k-c).sup.2 -4.lambda.<O. Therefore, the poles should be canceled by the zeros of the (1+z.sup.-N), and the roots of the denominators are: ##EQU38## All the discrete sinusoidal transforms listed in Table 4 satisfies Lemmas 1 through 4. Therefore, these transforms may be computed time recursively and may be realized by a FIR filter with transfer function (1+z.sup.-N) and an IIR filter with second order polynomials. These facts support the results obtained above. Lemma 5: If two transforms can be dually generated, then they share the same autoregressive model in their IIR filter structure.

Proof: The basis polynomial p.sub.n and q.sub.n of the dual generated transform pairs satisfy the following equations:

Since p.sub.n and q.sub.n are dually generated and from (64), they have the same characteristic equation. That is:

where: ##EQU39## As shown in Lemma 1, the roots of the denominators are the roots of the characteristics equation. Since p.sub.n and q.sub.n have the same characteristic equation, they have the same denominator. Hence, both transforms have identical poles, and as a result, the same autoregressive filter form.

The DCT and DST are dual generated transform pairs and share the same second order denominator.

The DCT and DST satisfy: ##EQU40## it follows that: ##EQU41## The poles are the root the following equation, which is the same as the characteristic equation derived from the Lemma 1. This is why the CT, DST and DFT, DHT are the same second order autoregressive structure. From

Lemma 3, it is noted that a maximum of 4N multipliers is required to realize the transform. Due to .lambda.=1 and P.sub.N =+P.sub.N-1 for the case of the DCT and ST, we may see that 2N multipliers for the DCT and DST is minimum for this realization. Based on Lemma 5, we may combine the denominator together for the dual generation of DCT and DST. This gives an average 1.5N multipliers to realize the DCT or DST. We believe that this is the best we can achieve for real time computation.

Multi-dimensional transforms provide powerful tools for multi-dimensional signal processing. Some of the important applications are in the areas of signal reconstruction, speech processing, spectrum analysis, tomography, image processing, and computer vision. Specifically, in multispectral imaging, interframe video imaging, and computer tomography, we have to work with three or higher dimensional data. It is difficult to generalize the existing fast 1-D algorithms to 3-D or higher dimensional transforms. However, the time-recursive concept may be extended to multi-dimensional transforms resulting in architectures that are simple, modular, and hence suitable for large scale integration (LSI)implementation. The 3-D CT is very useful in processing interframe video imaging data, we first describe the filter architecture for the 3-D DCT, and then generalize it to any multi-dimensional sinusoidal transform.

The basic concept of time-recursive computation is to compute the new transform at time (t+1) based on the transform at time t. The operations may be divided into two parts, one consists of computing the difference of the input data between time t and (t+1) and the other consists of performing the recursive updating. Looking at the basic architecture of computing 1-D DXT as shown in FIG. 2, the basic structure consists of three components: shift registers, adders, and IIR arrays. The shift register is used to store the input data from x(t) to x(t+N); adders are used to compute the difference data x(t) and x(t+N) and the IIR arrays are used to perform the computation recursively. It may be shown that the d-D DXT may be computed by using d blocks consisting of shift registers, adders, and filter arrays, each performing the time-recursive computation along a dimension.

For 1-D time-recursive DXT, the input data window is moved one sample at a time. That is, the input data vector at time t is given by the vector, and at time (t+1) the input data consists of the vector. The time-recursive relation for the 2-D transforms is based on updating the input data row by row. The input data sequences for time-recursive 3-D transforms are as shown in FIG. 10. Here, it is assumed that input data is updated frame by frame in the third axis n.sub.3, that is, the range of the input data x(n.sub.1 n.sub.2, n.sub.3) is {n.sub.1 =0, . . . ,N-1;n.sub.2 =0, . . . ,N-1;n.sub.3 =0,1,2, . . . }. The input data frame x(n.sub.1, n.sub.2,t) for a specific index t as the t.sub.th frame input data. The 3-D DCT of the t the frame input data is defined as: ##EQU42## The 3-D DCT of the (t+1) frame input data {n.sub.1 =0, . . . ,N-1;n.sub.2 =0, . . . ,N-1;n.sub.3 =t+1, . . . ,t+N.} is: ##EQU43## The concept of time-recursive approach is to update the 3-D DCT of the (t+1) frame input data based on X.sub.c,(k.sub.1,k.sub.2,k.sub.3,t). The time-recursive relations between the 3-D DCT X.sub.c,(k.sub.1,k.sub.2,k.sub.3,t+1) of the (t+1) t.sub.th input frame and the 3-DCT X.sub.c,(k.sub.1,k.sub.2,k.sub.3,t)of the t.sub.th input frame are: ##EQU44## Here we introduce another 3-D transform X.sub.c.spsb.2.sub.s (k.sub.1,k.sub.2,k.sub.3,t) defined as: ##EQU45## A similar relation exists between the updated transform X.sub.c.spsb.2.sub.s (k.sub.1,k.sub.2,k.sub.3,t+1) and the previous transform X.sub.c.spsb.2.sub.s (k.sub.1,k.sub.2,k.sub.3,t), that is: ##EQU46## where t.sub..DELTA. in X.sub.c.spsb.2 [k.sub.1,k.sub.2,t.sub..DELTA. ] implies that the input data (here we denote as .DELTA.(t+N, t)) of the 2-D DCT are based on difference of two frames and .DELTA.(t+N, t) is given by:

which is a 2-D data frame obtained from the difference between the (t+N) t.sub.th and the t.sub.th input data frames as shown in FIG. 10. This is the first part of the time-recursive computation. The 2-D DCT X.sub.c.spsb.2 (k.sub.1,k.sub.2,.DELTA.(t+N,t)) may be rewritten as: ##EQU47## above equation suggests that the 2-DCT of each frame may be computed first and stored in a shift register array of size (N+1)xN.sup.2. The difference between the 2-D DCT of the t.sub.th frame and (t+N)th frame is then computed. Equations indicate that the 3-D DCT may be generated by feeding the 2-D DCT of the updating vector into a lattice module as shown in FIG. 12. The size of the shift register in the lattice module is N.sup.2 because for a specific k.sub.3 there are N.sup.2 values (k.sub.1 =0, ... ,N-1;k.sub.2 =0, . . . ,N-1) to be updated. A similar updating relation exists for the 2-D DCT and the 1-D DCT. The number of shift registers in the lattice module for 2-D and 1-D DCT are N and 1 respectively. In fact, any d-D DCT may be obtained from the 1-D DCT by repeated application of the above equations. Therefore, the time-recursive 3-D DCT lattice structure consists of three lattice arrays which are used to produce the 1-D, 2-D and 3-D DCT individually. The 3-D DCT may be implemented using either the lattice or the filter structures as described below.

The architecture of the frame-recursive lattice 3- DCT is depicted in FIG. 8. It consists of three Lattice Array Blocks (LAB0, LAB1, LAB2) whose configurations are depicted in FIGS. 5 and 6. The lattice array LABi consists of a shift register array, two adders, and a lattice array, the shift register array is of size (N+1)xN.sup.i and is used to store intermediate values. The function of the adders is to update the effect of new data and eliminate the effect of previous data. The structure of the lattice array is shown in FIG. 7. The difference between different lattice arrays is only in the number of delays in the feedback loop. There are N.sup.i delay elements in the (i)the array.

The operation of this architecture may be viewed as follows. Input data is scanned row by row and frame by frame and sent to the first module LAB0 which generates the 1-D DCT of each row on every input frame. When the last datum of each row is available, the 1-D DCT of each input row vector is obtained. The N 1-D DCT transformed data is loaded in parallel into the second module LAB1 every N clock cycles. The LAB1 module is used to generate the 2-D DCT of each data frame. After N.sup.2 clock cycles, when the last datum of each frame arrives, the 2-D DCT of each frame is available. These values are loaded in parallel into the LAB2 module to generate the 3-D DCT recursively. The difference between the 2-D DCT of the parity of the (t+N)t.sub.th and t.sub.th frame is used as the input to the LAB2 module. There are N.sup.2 shift registers in the feedback loop of LAB2 to store the transformed data of each frame. It takes N.sup.2 cycles to finish updating a new 3-D block and this is the period required to obtain a new 2-D DCT data block. It is easy to verify that the system is fully-pipelined.

In applications where only block multi-dimensional transforms are required, the above architecture may be simplified. Intermediate values stored in shift registers are not necessary. The purpose of the shift registers is to store the current data obtained from the filter arrays, hence its size is reduced to N.sup.i for Lattice Array Block i. Since updating is unnecessary, the two adders may be eliminated. The lattice block 3-D DCT structure is shown in FIG. 9.

The lattice structure may be realized as directly as a digital filter by considering the transfer function of each lattice module. This approach is used to convert the time-recursive lattice 3-D DCT structure into its direct form configuration. The only difference between lattice and IIR 3-D DCT architecture is that the lattice array i is replaced by direct for filter array i. The direct form of the lattice module in FIG. 7 is depicted in FIG. 11. The size of the shift register in direct form realization is the same as that of lattice modules. The configuration of the direct form filter 3-D block DCT is depicted in FIG. 11.

The time-recursive concept is generalized to any multi-dimensional DXT and then derive the fully-pipelined block structures. Denote by the [x(n.sub.d,t)] the input data file at time t, and by [x(n.sub.d,t)] the data file at time (t+1) which is obtained by shifting [x(n.sub.d,t)] in a direction of one of the axes by one unit. For simplicity, let us assume that the data file is shifted in the direction of the last axis, n.sub.d. The d-dimensional DXT of the input data file [x(n.sub.d,t)] is defined as: ##EQU48## Here, we assume that the transform kernel P.circle..sbsb.d(k.sub.d) is separable. That is:

From the analysis in above, it may be seen that the updated transform X.sub.x.spsb.d(k.sub.d,t+1) is related to the previous transform by:

where .DELTA.(t+N,t) is the difference between the data files at time t and (t+N) and D.sub.x (K) and .GAMMA..sub.x (k) are coefficients that depend only on the transform kernel and index k. The above equation indicates that the d-dimensional DXT may be updated recursively using the previous transformed data X.sub.x.spsb.d (k.sub.d,t) and (d-)-D DXT of .DELTA.(t+N,t). This relation may be used recursively such that any d-D DXT may be generated from the 1-D DXT using d filter blocks as shown in FIG. 12.

As described in the previous section, there are two kinds of time-recursive DXT architectures, the moving-frame 3-D DXT and the block d-D DXT. The structure of the basic building block in the moving-fame DXT is shown in FIG. 13, where the filter array may be either the lattice or the filter form. The function of each block is to shift the (d-1)-dimensional data into a data back, then distribute the difference of the first and last frame of the data back to the second stage DXT array. The dimension of the shift register array is (N+1)xN.sup.i and the delay in filter array is N.sup.i. The time required to obtain the (d-1)-dimensional DXT is N.sup.d-1, which is also the time required to obtain the N.sup.d elements of the transformed data.

In the case of block DXT, the size of the shift register array may be reduced and adders may be eliminated because intermediate transformed data do not have to be stored, The size of the shift register array is N.sup.i. The structure of the LAB is shown in FIG. 14. The lattice array i is reset very N.sup.i+1 cycles.

The present invention's architecture for computing the d-dimensional transform DXT over N.sup.d points consists of d blocks, each block is composed of a shift register array followed by a one-dimensional lattice or IIR structure made up of N DXT modules. The (i)the shift register array is of size (N+1)xN.sup.i b, where 0<i<d-1 and b is the number of bits used to represent each number. The output is generated in a shift register array of size N.sup.d b. Therefore the total number of multipliers and adders used is O(dN)=O(N), and the total amount of memory is O(N.sup.d b). The area of any chip that computes the d-dimensional DFT transform must be .OMEGA.(N.sup.d b), and hence our design asymptotically optimal in its use of area. The same holds true for the remaining transforms. Further, any VLSI system that computes the d-dimensional DFT on N.sup.d points requires area A=.OMEGA.)N.sup.d b), where b is the number of bits required to represent each input number.

Therefore the present invention's design uses the least amount of memory asymptotically. The speed of the VLSI design cannot be improved asymptotically since it processes the input in real time. Hence the present invention's design is asymptotically optimal in both speed and area.