Abstract:
A modular digital signal processor system for calculating &#34;wavelet-analysis transformations&#34; and &#34;wavelet-synthesis transformations&#34; of one-dimensional numerical data and multi-dimensional numerical data for solving speech processing and other problems. The system includes one or more &#34;dual-convolver&#34; components, &#34;analyzer-adjunct&#34; components, &#34;synthesizer-adjunct&#34; components, &#34;de-interleaver components&#34; and &#34;interleaver components&#34;, and specific configurations of these components for implementing specific functions. Each dual-convolver is capable of loading a finite number of numerical values into its coefficient registers and subsequently performing two convolution operations on input sequences of numerical values to produce an output sequence of numerical values. Two dual-convolvers are configured with an analyzer adjunct or synthesizer adjunct to respectively build a single stage analyzer or synthesizer. Analyzers and synthesizers are configured in conjunction with interleavers and de-interleaver components to build wavelet sub-band processors capable of decomposing one-dimensional sequences of numerical data or multi-dimensional arrays of numerical data into constituent wavelets and to synthesize the original sequences or arrays from their constituent wavelets. Synthesizers are configured with interleavers to build function generators capable of calculating functions including wavelet functions to within any specified degree of detail.

Description:
BACKGROUND OF THE INVENTION 
     The invention is directed to a digital signal processor system, and more particularly to a system for processing one dimensional numerical data and multi-dimensional numerical data for solving speech and image processing problems, differential equation problems and the like, by transforming the data into a wavelet form for analysis and then synthesizing the original data, using modular elements to perform specific operations, including wavelet transforms, on input sequences and arrays of numerical data. 
     The text Multirate Digital Signal Processing, Crochiere et al, 1983 at pages 378-392 and references cited therein at pages 396-404 describe generic digital hardware realizations for implementing (i) a class of elementary digital signal processing operations known in the art of digital signal processing as quadrature mirror filters, and (ii) single side-band filter bank operations employing quadrature mirror filters. 
     The hardware realizations described in Crochiere et al consist of hardware components together with specific configurations of these components that are capable of performing single-side band quadrature mirror filter bank operations on input sequences of numerical data, herein called input signals. Filter bank operations consist of analysis operations that decompose input signals into constituent component signals and of synthesis operations that reconstruct the input signal from its constituent component signals. Filter bank operations have great utility in speech data compression and other digital signal processing applications. The hardware components described in Crochiere et al are described generically as low pass filters, high pass filters, downsamplers, and upsamplers. Specific designs for these component are not described in detail. 
     One useful type of analysis is performed using wavelet transforms. Mallat in a paper entitled &#34;A Theory for Multiresolution Signal Decomposition: The Wavelet Representation&#34;, Department of Computer and Information Science, School of Engineering and Applied Science, University of Pennsylvania Report No. MS-CIS-87-22, GRASP LAB 103, May 1987 (hereinafter &#34;Mallat 1&#34;, discusses a generic class of mathematical wavelet transforms and describes a pyramid architecture using quadrature mirror filters for efficiently calculating wavelet transforms. These pyramid architectures consist of: 
     (i) the single-side band quadrature mirror filter bank described in Crochiere et al for analyzing and for synthesizing one-dimensional signals, and 
     (ii) a pyramid architecture utilizing the same components as the architecture in (i) that are configured for computing two-dimensional wavelet transforms. The components described in Mallat 1 are described generically as low-pass filters, high-pass filters, downsamplers, and upsamplers. Specific designs for these components are not described in detail, and neither Crochiere et al or Mallat 1 describe configurations of hardware components for generation wavelet basis functions nor solving differential equations. 
     The use of wavelet theory and its associated transforms for performing useful digital signal processing and digital image processing is well established and specific applications in such fields as signal processing in seismic signal analysis, acoustics and speech compression and synthesis are discussed in Goupillaud et al, &#34;Cycle-octave and Related Transforms in Seismic Signal Analysis&#34;, J. Math Phys., Vol. 26, p. 2473, 1985; Kronland-Martinet et al, &#34;Analysis of Sounds Through Wavelet Transforms,&#34; Int&#39;l J. Pattern Analysis and Artificial Intelligence, Vol 1, January 1987 (hereinafter &#34;Kronland-Martinet&#34;) and Tuteur, &#34;Wavelet Transformations in Signal Detection&#34;, Proc. 1988 Int&#39;l Conf on Acoustics, Speech and Signal Processing, pp 1435-1438, 1988. It has been observed that the properties of wavelets are advantageous for (i) dealing with local properties of signals and images and (ii) for performing multiresolution analysis for signals and images. The importance of both of these tasks and the advantageous use of wavelets in this regard are generally acknowledged among those accomplished in the art. See, for example, Mallat 1; Mallat, Steven G., &#34;Multiresolution Approximation and Wavelets,&#34; Department of Computer and Information Science, School of Engineering and Applied Science, University of Pennsylvania Report No. MS-CIS-87-87, GRASP LAB 80, September 1987 (hereinafter &#34;Mallat 2&#34;); Marr, Vision, H. Freeman &amp; Co. 1982; and Pratt, Image Processing, J. Wiley &amp; Sons, 1987. 
     SUMMARY OF THE INVENTION 
     It is therefore an object of the invention to provide an efficient and economical design of a system for transforming one dimensional numerical data and multi-dimensional numerical data for solving speech and image processing problems, differential equation problems and the like by transforming the data into a wavelet form for analysis and then synthesizing the original data, using novel modular elements to perform specific operations, including wavelet transforms, on input sequences and arrays of numerical data. 
     It is another object of the invention to provide a modular design for such a system whereby a system may be built using large numbers of identical IC chips and the chips may be composed of large numbers of identical circuits, thereby to substantially reduce the costs of manufacture. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     These and other aspects of the invention will be more fully understood from the following detailed description of the preferred embodiment with reference to the accompanying drawings in which: 
     FIG. 1 shows the signal flow graph symbols used in FIGS. 2, 3 and 4; 
     FIG. 2 is a block and signal flow diagram of the dual-convolver in accordance with the invention; 
     FIG. 3 is a block and signal flow diagram of the analyzer-adjunct in accordance with the invention; 
     FIG. 4 is a block and signal flow diagram of the synthesizer-adjunct in accordance with the invention; 
     FIG. 5 is a block diagram of a single-stage wavelet analyzer circuit in accordance with the invention; 
     FIG. 6 is a block diagram of a single-stage wavelet synthesizer circuit in accordance with the invention; 
     FIGS. 7a and 7b are respectively block representations of the de-interleaver and interleaver components in accordance with the invention; 
     FIGS. 8a and 8b are signal flow diagrams of modular digital signal processing systems which decompose a signal and then synthesize the signal, according to two embodiments of the invention; 
     FIG. 9 is a block and signal flow diagram of a modular digital signal processing system which calculates sampled approximations to a signal in terms of its coefficients in terms of scaling functions and associated wavelets, according to another embodiment of the invention; 
     FIGS. 10a, 10b, 10c and 10d are block circuit diagrams respectively of a two-dimensional single stage wavelet analyzer, a two-dimensional single stage wavelet synthesizer, a two-dimensional de-interleaver and a two-dimensional interleaver, according to the invention; 
     FIGS. 11a and 11b are block signal flow diagrams of wavelet sub-band processors in accordance with two further embodiments of the invention; and 
     FIG. 12 is a block and signal flow diagram of a differential equations integrator according to still another embodiment of the invention. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     Digital circuit arrangements in accordance with the invention include one or more circuit components to be described below and which are illustrated in FIGS. 2, 3 and 4 below with the aid of certain signal flow graph symbols for a K-sample delay element, a gain and delay element, an adder, a multiplier and a commutator. These symbols are standard among those versed in the art and are illustrated in FIG. 1. 
     The circuit components illustrated in the figures include what may be called a &#34;dual convolver&#34;, an &#34;analyzer adjunct&#34;, a &#34;synthesizer adjunct&#34;, an &#34;interleaver&#34; and a &#34;de-interleaver&#34;. 
     Referring first to FIG. 2, the dual convolver is a circuit component which operates on an input sequence of digital values X(m) with some given number L of real numerical values e 0 , e 1 , . . . , e L-1 , loaded therein, and outputs an output sequence Y(m) according to the following relation: ##EQU1## 
     This operation is conveniently performed by two-sample delay elements, gain elements, adders and commutators of the circuit represented by the flow graph shown in FIG. 2. As can be seen from the circuit and the above equations, the output Y of the dual convolver has alternate even and odd components, and they are separated. If the circuit were to be formed on a chip the number of outputs and thus the number of pins would be minimized in relation to a circuit in which the odd and even components were separately output (each output at half the rate). The circuit performs two different convolutions at once and is therefore useful in mirror filtering. Also the circuit minimizes the required number of multiplications and therefore minimizes the required amount of circuitry. 
     Referring to FIG. 3, the analyzer adjunct is a circuit component which operates on a pair of input sequences of digital values Y 1  (m) and Y 2  (m), and outputs a single output sequence Y(m) according to the following relation: 
     
         Y(m)=Y.sub.1 (m-2)+Y.sub.2 (m-1) for m even 
    
     
         Y(m)=-Y.sub.1 (m)+Y.sub.2 (m-1) for m odd                  (2) 
    
     This operation is conveniently performed by the 1 and 2-sample delay elements, -1 gain element, adder and commutator of the circuit represented by the flow graph shown in FIG. 3. 
     Referring to FIG. 4, the synthesizer-adjunct is a circuit component which operates on a pair of input sequences of digital values Z 1  (m) and Z 2  (m), and outputs a single output sequence Z(m) according to the following relation: 
     
         Z(m)=Z.sub.1 (m)+Z.sub.2 (m-1) for m even 
    
     
         Z(m)=-Z.sub.1 (m-2)+Z.sub.2 (m-1) for m odd                (3) 
    
     This operation is conveniently performed by the 1-sample delay element, -1 gain and 1-sample delay element, adder and commutator of the circuit represented by the flow graph shown in FIG. 4. 
     An input sequence of digital data may be wavelet transformed for analysis with a single stage wavelet analyzer formed of a combination of the two dual convolvers and an analyzer-adjunct, as illustrated in FIG. 5. Ordered real numerical values a 0 , a 2 , . . . , a N-2  are loaded into the first dual-convolver DC1 and the reverse ordered numerical values a N-1 , a N-3 , . . . , a 1  are loaded into the second dual-convolver DC2. The input sequence X(m) is input to each of the two dual-convolvers in parallel, and the respective outputs of the dual convolvers Y 1  (m) and Y 2  (m) are input to the analyzer-adjunct which outputs the wavelet signal Y(n) ready for analysis. The dual convolvers and the analyzer-adjunct operate on their inputs as summarized by the equations (1) and (2), to produced the following results: ##EQU2## 
     Thus, when a given data sequence is input to the wavelet analyzer, two sequences are output, an even part and an odd part which are functions of the input data and the circuit is equivalent to a low pass filter and a high pass filter, each followed by a respective 2:1 downsampler. These are functions performed in a mirror filter, performed here in a more efficient way. 
     It may be demonstrated that if the numerical values a 0 , . . . , a N-1 , loaded into the dual-convolvers DC1 and DC2 are suitably selected as will be described below, then a single stage wavelet synthesizer formed of a parallel combination of two dual-convolvers DC3 and DC4 and a synthesizer-adjunct as shown in FIG. 6 may be used to reverse the signal decomposition performed by the single-stage wavelet analyzer (with a delay of N). The dual-convolver DC3 of the single stage wavelet synthesizer is loaded with ordered real or complex numerical values a N-2 , a N-4 , . . . , a 0  and the ordered real or complex numerical values a N-1 , a N-3 , . . . , a 1  are loaded into the second dual-convolver DC4. The input sequence generally designated W(m) is input to each of the two dual-convolvers DC3 and DC4 in parallel, and the respective outputs of the dual convolvers Z 1  (m) and Z 2  (m) are input to the synthesizer-adjunct which outputs the wavelet signal Z(m). The dual convolvers and the synthesizer-adjunct operate on their inputs as summarized by the equations (1) and (3), to produced the following results: ##EQU3## 
     Thus, the wavelet synthesizer performs a single function which in the case of an input sequence consisting of the odd and even parts output by the wavelet analyzer, is the combination of the even and odd parts, that is, the reversal of the functions performed by the wavelet analyzer, to produce the original signal In other words, whereas the analyzer takes a single sequence and decomposes the same into an even part and an odd part that represent in some sense high and low frequency components, the synthesizer takes such components and recombines them. The two parts are maintained in a single sequence so that the analyzer and the synthesizer each have one input and one output so that with a master clock, all the processing can be kept at a single rate within a circuit and the number of physical connections is minimized. 
     The simplicity of the analyzer and synthesizer is based on the fact that each performs a complicated function with two identical hardware elements and a trivial element, namely two dual convolvers and an adjunct, and that the hardware of the dual convolvers of the analyzer are identical to the dual convolvers of the synthesizer. Only the numbers or the order thereof, loaded into the various dual convolvers, differ. 
     Referring to FIG. 7a, the de-interleaver is a circuit component such as a demultiplexer which operates on an input sequence of digital values X(m), and outputs a pair of output sequences E(n) and O(n) according to the following relation 
     
         E(n)=X(2n) 
    
     
         O(n)=X(2n+1)                                               (8) 
    
     Referring to FIG. 7b, the interleaver is a circuit component such as a multiplexer which operates on a pair of input sequences of digital values O(n) and E(n), and outputs a single output sequence W(m) according to the following relation: 
     
         W(m)=E(m/2) for m even 
    
     
         W(m)=O((m-1)/2) for m odd                                  (9) 
    
     The above novel interleaver, de-interleaver, analyzer and synthesizer components may be combined to construct a number of useful data processing circuits including (1) wavelet sub-band processors capable of decomposing one-dimensional sequences of numerical data or multi-dimensional arrays of numerical data into constituent wavelets and to synthesize the original sequences or arrays from their constituent wavelets after processing, (2) function generators capable of calculating functions including wavelet functions to within any specified degree of detail, and (3) differential equation integrators for calculating the time evolution of a spatial function defined through a differential equation in conjunction with an initial value. 
     Referring to FIG. 8a, there is schematically illustrated a wavelet sub-band processor formed in stages i, i a positive integer 1 to J, in a ladder configuration. Each stage includes in series connection a single stage wavelet analyzer A i  as illustrated in FIG. 5, a de-interleaver, D i , as illustrated in FIG. 7a, an interleaver I i  as illustrated in FIG. 7b and a single stage wavelet synthesizer S i  as illustrated in FIG. 6, except stage J which does not include an interleaver or de-interleaver. Each analyzer A i  receives an input stream of digital data X.sup.(i) (m) from a data source in the case of stage i=1 and from one of the outputs of the de-interleaver D i  for stages i≠1, and outputs a data stream Y.sup.(i) (m). Each de-interleaver D i , i=1, . . . , J-1, receives the corresponding data stream Y.sup.(i) (m) and outputs each at half the data rate of the data stream Y.sup.(i) (m) a data stream S.sup.(i) (m) to be input to a corresponding processor P i , and a data stream X.sup.(i+1) (m) to be input to the analyzer A i+1  of the next stage. The output Y.sup.(J) (m) of the Jth stage is input as data stream Y.sup.(i) (m) of the same data rate directly to a corresponding sub-band processor P J . Thus the data rate of each of the successive data streams S.sup.(i) (m) is one half that of the data stream S.sup.(i-1) (m) of the preceding stage, except for data stream S.sup.(J) (m) which has the same data rate as data stream S.sup.(J-1) (m), and thus for i=1, . . . , J-1, the data rate of S.sup.(i) (m) is equal to 2 -i  times the data rate of the input data stream X.sup.(1) (m). The relationships between the inputs and outputs of the de-interleavers D i  may thus be expressed: 
     
         X.sup.(i) (m)=Y.sup.(i-1) (2m) for 2≦i≦J     (10) 
    
     
         S.sup.(i) (m)=Y.sup.(i) (2m+1) for 1≦i≦J-1   (11) 
    
     
         S.sup.(J) (m)=Y.sup.(J) (m)                                (12) 
    
     Thus, in each stage i, the de-interleaver D i  separates the odd (high frequency) part S.sup.(i) (m) and even (low frequency) part X.sup.(i) (m) of the respective output Y.sup.(i) (m) of that stage&#39;s wavelet analyzer A i . The analyzer portion of the wavelet sub-band processor (the left hand portion of the configuration shown in FIG. 8a) therefore removes the higher frequencies first and then successively decreasing frequencies in the data streams S.sup.(i) (m), that is, the frequencies of the data streams S.sup.(i) (m) decrease (geometrically by a factor of two) with increasing values of i, for i=1, . . . , J-1. 
     The processors P i  may perform any process on the particular data sequence input thereto, for example a frequency analysis for pattern recognition, data compression or data coding, transmission and decoding, or a combination of these. If the data streams are not altered too much, that is, S.sup.(i) (m)≅T.sup.(i) (m), then with appropriate selection of coefficients a.sup.(i) k as will be described, the output signals Z.sup.(i) (m) will have certain desirable properties as will be explained below. 
     In each stage i, i=1, . . . , J-1, the output data stream T.sup.(i) (m) of the sub-band processor P i  is input to the corresponding interleaver I i . Also input to the interleaver I i  is the output data stream Z.sup.(i+1) (m) of the single stage wavelet synthesizer S i+1  of the next stage i+1, and the output data stream W.sup.(i) (m) of the stage&#39;s interleaver I i  is input to the corresponding single stage wavelet synthesizer S i . The relationships between the inputs and outputs of the interleavers I i  may thus be expressed: ##EQU4## 
     The relationships between X.sup.(i) (m) and Y.sup.(i) (m) and between Z.sup.(i) (m) and W.sup.(i) (m) are defined by ordered numerical values loaded into the analyzers A i  and the synthesizers S i  and the equations (13) above. The ordered numerical values loaded into each analyzer A i  and each synthesizer S i  may be designated a.sup.(i) k, i=1, . . . , J, k=0, . . . , N i  -1, where N i  is the number of numerical values loaded into the analyzer A i  and the synthesizer S i  (the numerical values loaded into the analyzer A i  and those loaded into the corresponding synthesizer S i  being the same). These numerical values are selected so that if the processors P i  pass through input signals without significant alteration but with a &#34;delay&#34; of N i+1  +N i+2  + . . . +N J , that is so that 
     
         T.sup.(i) (m)≅S.sup.(i) (m-N.sub.i+1 - . . . -N.sub.J), (14) 
    
     then 
     
         Z.sup.(i) (m)≅X.sup.(i) (m-N.sub.i -N.sub.i-1 - . . . N.sub.1 for 1≦i≦J                                       (15) 
    
     so that the system output Z.sup.(1) (m)≅X.sup.(1) (m-N 1  -N 2  -, . . . -N J ), that is, the system input &#34;delayed&#34; by N 1  + N 2  + . . . +N J . In the case of stored data X.sup.(1) (m), the &#34;delays&#34; may not be time delays but merely indexing delays The &#34;delays&#34; provided by the processors P i  are necessary to maintain synchronism as a result of the &#34;delays&#34; in the analyzers A i . 
     That the output is approximately equal to the input delayed, can be shown to be satisfied by selection of a.sup.(i) k to perform a wavelet transformation, in particular so that, for each i, and for all even integers j: ##EQU5## A sequence of values which satisfy the above equation are hereinafter referred to as &#34;compatible&#34;. 
     This relationship may be better understood from the following proof of the proposition that the equations which define the wavelet transform: ##EQU6## 
     where Y and W are the same, give Z(M)=X(m-N) for the sequence of real numbers a 0 , a 1  . . . , a N-1 , if and only if a 0 ,a 1 , . . . , a N , are compatible, that is, for all even integers j, they satisfy the equation ##EQU7## 
     Assuming that m is even, by using the first, respectively second, equality in equation (17) to express the value for W in the first, respectively second, term on the right in the first equality in equation (18) the following equation is obtained: ##EQU8## where the sequence d n  is defined by ##EQU9## where it is assumed that a p  =0 for p&lt;0 and p&gt;N-1. If n is odd, then the first and second terms above cancel and d n  =0. Therefore, the condition that d n  =δ(n) is equivalent to the condition that a 0 ,a 1  . . . , a N-1  be a compatible sequence. This proves the theorem for even values of m. 
     If it is assumed that m is odd, then by using the second, respectively first, equality in equation (17) to express the value for W in the first, respectively second, equality in equation (18) the following equation is obtained: ##EQU10## Therefore the theorem is proven. 
     Important advantages of the arrangement shown in FIG. 8a are obtained where the number of numerical values N i  loaded into the analyzer A i  and the synthesizer S i  is the same for all stages i, i=1 to J. Then, the J wavelet analyzers A i  may all be identical and the J wavelet synthesizers S i  may all be identical, and thus the 4J dual-convolvers thereof may all be identical, differing only in the respective coefficients a.sup.(i) k input thereto. This of course substantially reduces manufacturing costs of IC chips of a system with these circuits on the chips, as a result of the economies of scale. 
     It should also be noted that the analyzer portion of the wavelet sub-band processor shown on the left hand side of FIG. 8a is useful independently of the synthesizer portion shown on the right hand side. For example, the analyzer portion could be used independently for pattern recognition. 
     It should be additionally noted that although the input data X.sup.(1) (m) is referred to as a data stream or sequence, the processing on the respective input data X.sup.(1) (m) may be performed for all m entirely in parallel if the data is previously stored. 
     FIG. 8b illustrates an embodiment of the wavelet subband processor illustrated in FIG. 8a and having the identical functionality described by the equations corresponding thereto However, the functionality of the plurality of single stage analyzers denoted by A 1 , . . . , A J  in FIG. 8a is obtained by one single stage analyzer in FIG. 8b by buffering or, equivalently, temporarily storing the inputs X 1  (m), . . . , X J  (m) to A 1 , . . . , A J  respectively in FIG. 8a and then alternately processing the inputs X 1  (m), . . . , X J  (m) to obtain the outputs Y 1  (m), . . . , Y J  (m) by using one single stage wavelet analyzer. Furthermore, the plurality of de-interleavers, denoted by D 1 , . . . , D J-1  in FIG. 8a is replaced by a single de-interleaver D in FIG. 8b. Likewise, the functionality of the plurality of single stage wavelet synthesizers, denoted by S 1 , . . . , S J  in FIG. 8a is achieved by one single stage wavelet synthesizer and by one interleaver in FIG. 8b by buffering or, equivalently, temporarily storing the inputs W 1  (m), . . . , W J  (m) to S 1 , . . . S J  respectively in FIG. 8a and then alternately processing the inputs W 1  (m), . . . , W J  (m) to obtain the outputs Z 1  (m), . . . , Z J  (m) by using one single stage wavelet synthesizer. Furthermore, the plurality of interleavers, denoted by I 1 , . . . , I J-1  in FIG. 8a is replaced by a single de-interleaver I in FIG. 8b. In an alternate embodiment, two or more, but less than J each of analyzers, synthesizers, de-interleavers and interleavers may be used. In a further simplification of the circuit shown in FIG. 8b, the analyzer circuit and the synthesizer may share a common pair of dual-convolvers, alternatively connectable to an analyzer adjunct and a synthesizer adjunct. 
     In accordance with another embodiment of the invention, an alternate arrangement of single stage wavelet synthesizers S i  as illustrated in FIG. 6 and interleavers I i  as illustrated in FIG. 7b, is provided for performing calculations of sampled approximations to a function in terms of coefficients of scaling functions and associated wavelets 
     Scaling functions (φ(u-k)) and wavelet functions (Ψ(u-k)), are related well known functions which form orthonormal sets (k and j integers). Thus, 
     
         ƒφ(u)du=1                                     (22) 
    
     
         ƒφ(u-j)φ(u-k)du=δ(j-k)              (23) 
    
     
         ƒΨ(u-j)Ψ(u-k)du=δ(j-k)              (24) 
    
     
         ƒΨ(u-j)φ(u-k)du=0                         (25) 
    
     The theory of orthonormal wavelets is described in the following publications: Coifman, R., Meyer, Y. &#34;The discrete wavelet transform,&#34; Preprint, 1987; Daubechies, I., Grossman, A., Meyer, Y., &#34;Painless nonorthogonal expansions,&#34; J. Math. Phys., Vol. 27, p. 1271, 1986; Daubechies, Ingrid, &#34;Orthonormal basis of compactly supported wavelets,&#34; Technical Report, Room 2C-371, AT&amp;T Bell Laboratories 600 Mountain Avenue, Murray Hill, N.J. 07974, 1987; Goupillaud, P., Grossman, A., Morlet, J., &#34;Cycle-octave and related transforms in seismic signal analysis,&#34; Geoexploration, Vol. 23, p. 85, 1984; Grossman, A., Morlet, J., Paul, T., &#34;Transforms associated to square-integrable group representations, I: general results,&#34; J. Math. Physics, Vol. 26, p. 2473, 1985; Grossman, A., Morlet, J., Paul, T., &#34;Transforms associated to square-integrable group representations, II: examples,&#34; Ann. Inst. H. Poincare, Vol. 45, p. 293, 1986; Grossman, A., Morlet, J., &#34;Decomposition of Hardy functions into square integrable functions of constant shape,&#34; SIAM J. Math. Anal., Vol. 15, p. 723, 1984; Grossman, A., Morlet, J., &#34;Decomposition of functions into wavelets of constant shape and related transforms,&#34; Center for Interdisciplinary Research and Research Center Bielefeld-Bochum-Stochastics, University of Bielefeld. Report No. 11, December 1984 also in Mathematics and Physics 2, L. Striet, editor, World Scientific Publishing Co., Singapore, pp. 135-165, 1987; Kronland-Martinet; Mallat 1; Mallat 2; and Meyer, Y., Jaffard, S., Rioul, O., &#34;L&#39;analyse par ondelettes,&#34; Pour la Science, pp. 28-87, September 1987; and are related to the theory of quadrature mirror filters for sideband signal processing which is described in Crochiere et al. 
     Referring to FIG. 9, if an input sequence of digital values W.sup.(1) is provided to wavelet synthesizer S 1 , null sequences null (m) consisting of zero values are provided to one of each of the inputs of the interleavers I i  for each of J stages, and the output sequence of the Jth stage, Z.sup.(J) (m), may be expressed according to the following equations: 
     
         Z.sup.(J) (m)≅2.sup.-J/2 S(m/2.sup.J -N/2)       (26) 
    
     where ##EQU11## where φ is a scaling function and Ψ is the associated wavelet function. In particular, if 
     
         W.sup.(1) (m)=δ(m) then φ(m/2.sup.J)≅2.sup.J/2 Z.sup.(J) (m) 
    
     and if 
     
         W.sup.(1) (m)=δ(m-1) then Ψ(m/2.sup.J)≅2.sup.J/2 Z.sup.(J) (m+2.sup.J N/2). 
    
     The scaling function φ(u) has the characteristic that for some sequence of real numbers a 0 , . . . a k  . . . , a N-1  which is &#34;compatible&#34; as defined above, the set of real numbers c 0 , . . . c k  . . . , c N-1  where c k  =√2a k , i=0, . . . N-1, interrelates φ(u), Ψ(u) and φ(2u) as follows: ##EQU12## 
     The collection of functions {Ψ j ,k (u)=2 j/2  Ψ(2 j  u-k)} forms an orthonormal basis for L 2  (R), that is, the space of square integrable functions on R (the real line). 
     Therefore, a function which can be expressed or approximated by a linear combination of these orthonormal functions φ and Ψ as follows ##EQU13## 
     where W(m) is a sequence of numerical values of finite length, can also be expressed or identically approximated by a linear combination of the scaling function φ(2u) as follows ##EQU14## 
     where Z(m) is another sequence of numerical values of finite length which is related to the sequence W(m) as follows: ##EQU15## 
     where a k  is the compatible sequence whose values are those from equations (27) and (28), with a k  =c k  /√2. 
     It will be noted that equation (31) above is identical to equation (18) which defines the output of a single stage wavelet synthesizer having the numerical values a k  loaded thereinto. Therefore, if the numerical values a k  (=c k  /√2), defining a scaling function and corresponding wavelet function, are loaded into such a single stage wavelet synthesizer S, and a W(m) representation of a function S(u) as coefficients of the scaling and wavelet functions φ(u-n) and Ψ(u-n) (see eqn. 29) is input thereto, the output sequence Z(m) will also represent the function S(u) (see eqn. 30), but as the coefficients of a linear combination of the scaling functions φ(2u-m) only. Thus, the synthesizer of the invention provides a simple and convenient manner of converting from one wavelet representation of a given function to another. 
     Also, it can be shown mathematically, that if φ and Ψ are defined as above, if X(m) is a numerical sequence, and if Y(m) is defined in terms of X(m) as in eqn. 17 wherein the numerical values a k  are related to φ as above, then the function ##EQU16## may be expressed as ##EQU17## 
     But equation (17) also expresses the relationship between the input sequence and output sequence of a single stage wavelet analyzer as is illustrated in FIG. 5, having the numerical values a k . Therefore, the analyzer provides a means for decomposing or analyzing a signal S(u) which is expressed as a linear combination of the orthonormal set {φ p+1 ,j (u)=2.sup.(p+1)/2 φ(2 p+1  u-j), p an integer, j any integer}, into a base band component equal to a linear combination of the orthonormal set {φ p ,j (u),j any integer}, and a sub-band component equal to a linear combination of {Ψ p ,j (u), j any integer}. This means can be applied iteratively to the successive base-band components to express S(u) in terms of wavelet basis functions {Ψq,j(u), j any integer and q≧p}. Furthermore, any continuous function can be expressed as ##EQU18## and can therefore be approximated with unlimited precision by an analysis as above. Conversely, the above shows that the synthesizer can be used to reconstruct or synthesize a signal from its base-band and sub-band components (inputting their respective component values W(m) to the synthesizer). 
     In this regard, it is noted that in many applications in which wavelets are used the exact values (a plot) of the wavelets is not known; only the parameters a k  or c k  are known (typically selected to give the functions φ and or Ψ some desirable properties such as a relation to a physical phenomenon being investigated). Thus, the present invention provides a means by which the wavelet and scaling functions may be plotted (as with a display device) at whatever scale is desired (the larger is J the smaller is the scale). 
     In this respect equation (27) is noted. This equation shows that while φ(u) is supported on 0 to N, on the right side of the equation is a summation of functions with φ(2u-k) as factor, and these factors will of course be supported on an interval half the length of that of φ(2u-k), that is 0 to N/2. In other words, a graph of φ(2u-k) would have the same amplitudes but would be narrower by a factor of 2 than that of φ(u). 
     The most elementary example of this relationship is given by the Haar scaling function H(u) which is a scaling function equal to 1 from u=0 to 1 and 0 elsewhere. The Jth order Haar scaling function H(2 J  u) is equal to 1 from u=0 to 1/2 J  and 0 elsewhere and H(2 J  u-k) is equal to 1 from u=k to k+1/2 J  and 0 everywhere else. It can be seen that a multitude of various functions can be constructed from a linear combination of Haar functions and in fact, a Haar scaling function of a lower order can be constructed from a linear combination of Haar scaling functions of a higher order. 
     Thus, wavelets provide a powerful tool which permits physical phenomena such as superconductivity, crystal formation, music, heartbeat patterns, seismic signals and speech to be analyzed at different scales, and the analyzers and synthesizers of the invention provide improved circuitry which facilitates such analysis. 
     The present invention is also applicable to processing of multi-dimensional data such as the performance of a two-dimensional wavelet analyzer function and a two-dimensional wavelet synthesizer function. These functions are performed with circuit arrangements consisting of one or more sets of two-dimensional single stage wavelet analyzers and synthesizers and two-dimensional interleavers and de-interleavers, as schematically illustrated in FIGS. 10a-10d for plural sets. 
     As shown in FIG. 10a, the two-dimensional single stage wavelet analyzer consists of two one-dimensional single stage wavelet analyzers such as is illustrated in FIG. 5, connected in series so that a first one-dimensional single stage wavelet analyzer A 1  transforms the rows (for each m, transform mth row) of a two-dimensional array of data X(m,n) and a second one-dimensional single stage wavelet analyzer A 2  transforms the columns (for each n, transform nth column) of the intermediate output array U(m,n) of the analyzer A 1 , to obtain an output array Y(m,n). The relationships between the inputs and outputs of the analyzers A 1  and A 2  are therefore as follows: ##EQU19## where α j , j=0 to M-1 and β k , k=0 to N-1, M and N being positive even integers, are &#34;compatible sequences&#34; as defined above. 
     As a consequence, the output Y(m,n) of the two-dimensional analyzer as a function of the input X(m,n) is as follows: ##EQU20## 
     Similarly, as shown in FIG. 10b, the two-dimensional single stage wavelet synthesizer consists of two one-dimensional single stage wavelet synthesizers such as is illustrated in FIG. 6, connected in series so that a first one-dimensional single stage wavelet analyzer S 1  transforms the rows (for each m, transform mth row) of a two-dimensional array of data W(m,n) and a second one-dimensional single stage wavelet synthesizer S 2  transforms the columns (for each n, transform nth column) of the intermediate output array V S  (m,n) of the synthesizer S 1 , to obtain an output array Z(m,n). The relationships between the inputs and outputs of the synthesizers S 1  and S 2  are therefore as follows: ##EQU21## 
     As a consequence, the outputs of two-dimensional synthesizers as a function of its input is as follows: ##EQU22## 
     As shown in FIG. 10c, the two-dimensional de-interleaver consists of three one-dimensional de-interleavers such as is illustrated in FIG. 7a, including a first one-dimensional de-interleaver D 1  which receives a two-dimensional array of data Y(m,n) and de-interleaves the rows (m=1, . . . , J), and second and third de-interleavers D 2  and D 3  which receive the respective intermediate output arrays of the de-interleaver D 1 , U D  (m,n) and V D  (m,n) and de-interleave the respective columns (n=1, . . . , J), to obtain respective pairs of output arrays V OO  (m,n), Y EO  (m,n) and Y OE  (m,n), Y EE  (m,n). 
     The relationships between the inputs and outputs of the de-interleavers D 1 , D 2  and D 3  are therefore as follows: ##EQU23## As a consequence the output of the two-dimensional de-interleaver as a function of its input is as follows:  Similarly, but in reverse, the two-dimensional interleaver consists of three one-dimensional interleavers such as is illustrated in FIG. 7b, including a first one-dimensional de-interleaver I 1  which outputs a two-dimensional array of data Y(m,n) after interleaving the rows (m=1, . . . , J) of two intermediate arrays of data U I  (m,n) and V I  (m,n) respectively output by second and third interleavers I 2  and I 3  which interleave the respective columns (N=1, . . . , J) of respective pairs of input arrays Y OO  (m,n), Y EO  (m,n) and Y OE  (m n) Y EE  (m,n). The relationships between the inputs and the outputs of the interleavers I 1 , I 2  and I 3  are as follows ##EQU24## 
     As a consequence the output of the two-dimensional interleaver as a function of its inputs is as follows: ##EQU25## 
     These two-dimensional data processing components may be combined to form a two-dimensional wavelet sub-band processor. 
     Referring to FIG. 11a, there is schematically illustrated a two-dimensional wavelet sub-band processor formed in stages i, i a positive integer 1 to J, in a ladder configuration. Each stage includes in series connection a two-dimensional single stage wavelet analyzer AA i  as illustrated in FIG. 10a, a de-interleaver, DD i  as illustrated in FIG. 10c, an interleaver II i  as illustrated in FIG. 10d and a single stage two-dimensional wavelet synthesizer SS i , except stage J which does not include an interleaver or de-interleaver. Each analyzer AA i  received a two-dimensional input array of digital data X.sup.(i) (m,n) from a data source in the case of stage i=1 and from one of the outputs of the de-interleaver DD i  for stages i≧1, and outputs a two-dimensional data array Y.sup.(i) (m,n). Each de-interleaver DD i , i=1, . . . , J-1, receives the corresponding data stream Y.sup.(i) (m,n) and outputs each at one fourth the data rate of the data array Y.sup.(i) (m,n) data arrays S.sup.(i) OO  (m,n), S.sup.(i) OE  (m,n), S.sup.(i) EO  (m,n) to be input to a corresponding processor P i , and a data stream S.sup.(i) EE  (m,n) as X.sup.(i+1) (m,n) to be input to the analyzer AA i+1  of the next stage. The output Y.sup.(J) (m,n) of the Jth stage is input as data stream Y.sup.(i) (m,n) of the same data rate directly to a corresponding processor P J . Thus, the data rate of the successive data arrays S.sup.(i) OO  (m,n), S.sup.(i) OE  (m,n), S.sup.(i) EO  (m,n) are all one quarter of the data rate of the array S.sup.(i-1) EE  (m,n) of the preceding stage, except for data array S.sup.(J) (m,n) which has the same data rate as data array S.sup.(J-1) EE  (m,n), and thus for i=1, . . . , J-1, the data rate of the array S.sup.(i) (m,n) is equal to 2 -i  times the data rate of the input data array X.sup.(1) (m,n). The relationships between the inputs and outputs of the de-interleavers DD i  may thus be expressed: ##EQU26## 
     In each stage i, i=1, . . . , J-1, the output data arrays T.sup.(i) OO  (m,n), T.sup.(i) EO  (m,n) of the sub-band processor P i  are input to the corresponding interleaver II i . Also input to the interleaver II i  is the output data array Z.sup.(i+1) (m) as T.sup.(i) EE  (m,n) of the two-dimensional single stage wavelet synthesizer SS i+1  of the next stage i+1 and the output data array W.sup.(i) (m,n) of the stage&#39;s interleaver II i  is input to the corresponding two-dimensional single stage wavelet synthesizer SS i . The relationships between the inputs and outputs of the interleavers II i  may thus be expressed: ##EQU27## 
     The relationships between X.sup.(i) (m,n) and Y.sup.(i) (m,n) and between Z.sup.(i) (m,n) and W.sup.(i) (m,n) are defined by ordered numerical values loaded into the analyzers AA i  and the synthesizers SS i  and the equations (43) and (44) above. The ordered numerical values loaded into each analyzer AA i  and each synthesizer SS i  may be designated α.sup.(i) j and β.sup.(i) k, i=1, . . . , J, j=0 to M i  -1, k=0, . . . , N i  -1, where M i  is the number of rows and N i  the number of columns, of numerical values loaded into the analyzer AA i  and the synthesizer SS i . The numerical values loaded into the analyzer AA i  and those loaded into the corresponding synthesizer SS i  are each compatible, that is, they define wavelet transforms or their inverse and meet the definition defined in equation (19) above, and they are the same compatible sequences or different sequences. These numerical values are selected so that if the processors P i  pass through input signals without significant alteration, that is, ##EQU28## so that the system output Z.sup.(1) (m,n) is the delayed system input. 
     FIG. 11b illustrates an embodiment of the two-dimensional wavelet sub-band processor having the identical functionality of the embodiment of FIG. 11a as defined by the equations relating thereto as described above in which a plurality of two-dimensional single stage wavelet analyzers, two-dimensional single stage wavelet analyzers, two-dimensional de-interleavers and two-dimensional interleavers are used. However, the embodiment of FIG. 11b uses only a single item of each component by buffering data. Moreover, similar alterations and simplifications as are described above with respect to the one-dimensional embodiment would also be possible for the two-dimensional embodiment. 
     In another embodiment of the invention, a combination of a wavelet analyzer, a wavelet synthesizer, an adder, a multiplier and a function construction component are combined to form a differential equations integrator. Such an integrator can be used, for example, to determine a temperature distribution as a function of time t. Referring to FIG. 12, if u is an n dimensional variable and a solution S(u,t) is to be determined, and the time derivative of S is known as a function F(S,u,t) of S, u and t and an initial value S(u,0) of S, is known to be some function G(u), then the value of S at some future time t can be calculated by iteratively computing wavelet coefficients C a  (t) of a wavelet representation of S(u,t). Thus, representing S(u,t) by: 
     
         S(u,t)=ΣC.sub.a (t)X.sub.a (u)                       (45) 
    
     where {X a  (u)} is an orthonormal wavelet basis for functions from R m  to R 1 , the initial values of C a  (t)(C a  (0)) is given by ##EQU29## Iterative calculation of C a  (t) is based on the approximation: ##EQU30## In FIG. 12, the wavelet analyzer computes  .sbsb.R m  X a  (u)F(S,u,t)du. The wavelet analyzer and wavelet synthesizer may be respectively as shown in FIGS. 5 and 6 for m=1 and as shown in FIGS. 10a and 10b for m=2. 
     The invention now being fully described, it will be apparent to one of ordinary skill in the art that many changes and modifications can be made thereto without departing from the spirit or scope of the invention as set forth herein and the same are intended to be comprehended within the meaning and range of equivalents of the appended claims.