Title: Class of transform digital processors for compression of multidimensional data

• Summary
• Claims
• Description
• View all

Abstract: A method and apparatus is presented for digitally implementing a class of transforms for the purpose of processing data in real time based on decomposing data vectors into sets of coefficients associated with matrices of transformations in the class with each transform in the class being made up of an ordered cascade of elementary transformations. Each state of the cascade is composed of the product of a weighting transformation (diagonal weighting matrix) and a generating transformation (sparse matrix composed of +1, -1, and zero elements). The inverse generating transform is obtained as the adjoint of the generating transform (transpose of the generating matrix). The invention is implemented by cascading one or more modules composed of adder/subtractors, delays, and multipliers with all modules having the same structure and the number of modules at any stage being twice the number in the preceding stage. A class of inverse transforms is implemented using the same basic filter module structure as for the direct transforms with the number of filter modules at any stage being one half the number in the preceding stage. Any member transform in the class requires at most 2N log.sub.2 N real computations where N is the dimension of the data vector and is an integral power of two. BACKGROUND OF THE INVENTION The present invention provides a method and apparatus for implementing a class of transforms for the purpose of processing data in real time and more particularly a method and apparatus for generating a class of transforms for the processing of data: filtering, redundancy reduction, correlation, spectral analysis, smoothing, coding, pattern recognition, multiplexing, signal characterization, signal synthesis, statistical analysis, and the like. A digital apparatus for implementing the class of transforms for real time processing of sampled data at sample rates up to 150 mega-bits per second (1.5 .times. 10.sup.8 B/S) is described. The class of transforms provides a way of optimizing a transform processor for a given class of data. The current trend in information processing (computing, communications, data processing, etc.) is to digital. The reasons for the trend to digital processing are as follows: 1. Digital transmission of data minimizes the effects of channel noise. 2. Digital signals are easily and predictably regenerated. 3. Digital processor parameters are stable. 4. Errors in digital processors are easily predicted and controlled. 5. Digital processors tend to be more versatile than analog processors. 6. Digital processors can be easily interfaced with the ubiquitous digital computer. Transformations are the foundation upon which data processing rests. Such data processing functions as signal classification, coding, redundancy reduction, etc., all involve transformations of one kind or another. The Fourier transform is an example of a well-known transform which has played a central role in filtering, spectral analysis, and pattern classification. Another example is the eigenvector, Hotelling, or Karhunen-Loeve transformation which has been extensively used for data characterization and statistical analysis. Other transforms, such as Laplace, Hilbert, Bessel, Laguere, Hermite, and Chebyshev have found wide use in all types of data analysis. Digital implementation of any of the above-mentioned transforms requires multiplication of the input data. With the exception of the Fourier transform, all require on the order of N.sup.2 computational operations for an N dimensional input data vector. These two requirements in computing these transforms require digital hardware mechanism that is relatively complex. These two requirements further require long, transform computation times. Recently, a number of transforms have been proposed which can be computed without multiplication of the input data and which require only on the order of N log.sub.2 N computations. Included in the group are the well known Walsh-Hadamard and Haar transforms. These transforms, being binary or tertiary in nature, are ideally suited to simple digital implementation and rapid computation. These transforms have been used for data filtering, multiplexing, redundancy reduction, signal characterization spectral analysis, pattern classification, and many other data processing operations. SUMMARY OF THE INVENTION The present invention provides a method and apparatus for digitally implementing a class of transforms having the following important features: 1. The class has a simple digital structure and is capable of operating at high throughput rates. The same structure exists for both the direct and inverse members of the class. The invention provides for simplified mechanization and high speed operation by using only a few logic elements such as shift registers and adder/subtractors, with the option of including multipliers. The structure of the class is built up from a plurality of identical simple modules composed of these logic elements. 2. The number of computations required to compute a member transform does not exceed 2N log N. 3. the options exist for generating member transforms using only add and subtract operations, as well as transforms using add, subtract, and multiply operations. 4. All currently used binary and tertiary transforms such as Walsh-Hadamard and Haar, belong to the class. A class of transforms with the above properties provides the particularly important novel and nonobvious result that the entire class can be implemented on a single digital transform processor, which is capable of being optimized for almost any particular class of data, (e.g., landscape scenes, typewritten material, speech, radar signatures, telemetry signals, etc.) and data processing operation. Such a transform processor is capable of being implemented in simple, low cost, highly reliable digital hardware operating in real time at high throughput rates (greater than 150 mega-bits per second). The class of transforms utilized by the present invention is defined mathematically for transforms of dimension N = 2.sup.M, where M = 1, 2 - - - . A member transform T in the class is defined by the matrix cascade. T = T.sub.M T.sub.M.sub.-1 - - - T.sub.1, where ##EQU1## with ##EQU2## and ##EQU3## j = 1, - - - , M, k = 1, - - - , 2.sup.j.sup.-1 Several important members of the class are described more fully in the following examples: EXAMPLE 1 One member of the class is given by M = 3 and N 2.sup.M = 8, and T.sub.jk not identify matrices. ##EQU4## If all w's are set to one, then T = T.sub.3 T.sub.2 T.sub.1 is the matrix of the Walsh transform. PRETEXTREPLACED EXAMPLE 2 Another member of the class known as the rationalized Haar transform is generated for M = 3 and N = 2.sup.M = 8 by making T.sub.22, T.sub.32, T.sub.33, T.sub.34 identity matrices and setting all w's to one. ##EQU5## The inverse of a member transform T in the class is given by the matrix cascade T.sup..sup.-1 = T.sub.1.sup..sup.-1 T.sub.2.sup..sup.-1 - - - T.sub.M.sup..sup.-1, where __________________________________________________________________________ W.sub.j1.sup.-.sup.1 0 T.sub.j1.sup.-.sup.1 0 T.sub.j.sup.-.sup.1 = W j2.sup.-.sup.1 T.sub.j2.sup.-.sup.1 0 W.sub.j2.sup.-.sup.1 (j-1) 0 T.sub.j2.sup.-.sup.1 (j-1) N.times.N N.times.N __________________________________________________________________________ with ##EQU6## and __________________________________________________________________________ 1 1 1 0 -1 0 1 1 1 -1 T.sub.jk.sup.-.sup.1 = 1/2 0 1 0 1 1 1 N N .times. 2.sup.j.sup.-1 2.sup.j.sup.-1 __________________________________________________________________________ or ______________________________________ 1 0 1 0 1 , ______________________________________ j = 1, - - - , M, k = 1, - - - , 2.sup.j.sup.-1 EXAMPLE 3 The inverse of T in Example 2 is: __________________________________________________________________________ 1 1 1 1 0 1 -1 0 1 1 1 T.sub.1.sup.-.sup.1 = 1/2 1 1 -1 1 0 1 1 1 -1 1 0 1 1 1 0 1 -1 1 1 1 0 1 0 1 0 1/2 1 0 -1 0 0 1 0 1 0 1 T.sub.2.sup.-.sup.1 = 1 0 1 0 -1 1 1 1 1 0 1 0 1 1 1 1 1 0 1/2 1 1 1 1-1 0 T.sub.3.sup.-.sup.1 = 1 1 1 1 1 1 0 1 1 1 0 1 1 __________________________________________________________________________ t.sup..sup.-1 = t.sub.1.sup..sup.-1 t.sub.2.sup..sup.-1 t.sub.3.sup..sup.-1 the total number of transforms in the class formed from the different T.sub.jk matrices is 2.sup.2(m.sup.-1), , M = 0, 1, 2, - - - For M = 5, there are 2.sup.2.spsp.4 = 2.sup.16 = 65,536 different space transforms in the class. It is seen that the method of the present invention is based on decomposing data vectors into sets of coefficients associated with matrices of transformations in the class. Each transform in the class is made up of an ordered cascade of elementary transformations. Each state of the cascade is composed of the product of a weighting transformation (diagonal weighting matrix) and a generating transformation (sparse matrix composed of +1, -1, and zero elements). The inverse generating transform is obtained as the adjoint of the generating transform (transpose of the generating matrix). Any member transform in the class requires at most 2N log.sub.2 N real computations where N is the dimension of the data vector and N is an integral power of two. Depending on the choice of weight transformations, member transformations in the class can be orthogonal transformations. The invention may be digitally implemented for the class of forward transforms by cascading adder/subtractor modules in stages with the number of modules in each stage being twice the number in the preceding stage. The modules all have the same structure and are constructed of adder/subtractors, delays, and multipliers. The class of inverse transforms is implemented using the same basic structure of adder/subtractor modules as is used in the class of direct transforms. The number of modules in each stage is one half the number in the preceding stage.


Do you think this is a good invention? Vote now: