Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-05-02
2001-11-27
Malzahn, David H. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06324560
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a system and method for computing modulated lapped transforms (MLT's), and in particular, a system and method for computing MLT's by decomposing a MLT into butterfly operators followed by a transform for fast computation of the MLT.
2. Related Art
In many engineering and scientific applications, it is desired to analyze a signal in the frequency domain or represent the signal as a linear superposition of various sinusoids. The analysis of the amplitudes and phases of such sinusoids (the signal spectrum) can be useful for operations such as noise reduction, compression, and pattern recognition, among other things. The Fourier transform is a classical tool used for frequency decomposition of a signal. The Fourier transform breaks a signal down to component frequencies. However, its usefulness is limited to signals that are stationary, i.e., spectral patterns of signals that do not change appreciably with time. Since most real-world signals, such as audio and video signals, are not stationary signals, localized frequency decompositions are used, such as time-frequency transforms. These transforms provide spectral information that is localized in time.
One such transform is the discrete cosine transform (DCT). The DCT breaks a signal down to component frequencies. For instance, a block of M samples of the signal can be mapped to a block of M frequency components via a matrix of M×M coefficients. To ensure a good energy compaction performance, the DCT approximates the eigenvectors of the autocorrelation matrix of typical signal blocks. Basis functions for the DCT (for type II) can be defined as:
a
nk
=
c
(
k
)
2
M
cos
[
(
n
+
1
2
)
k
π
M
]
where, a
nk
is the element of an A transformation matrix in the nth row and
kth column, or equivalently, the nth sample of the kth basis function. For orthonormality, the scaling factors are chosen as:
c
(
k
)
≡
{
1
/
2
if
k
=
0
1
otherwise
The transform coefficients X(k) are computed from the signal block samples x(n) by:
X
(
k
)
=
∑
n
≂
0
M
-
1
a
nk
x
(
n
)
The DCT can be used for convolution and correlation, because it satisfies a modified shift property. Typical uses of the DCT are in transform coding, spectral analysis, and frequency-domain adaptive filtering.
An alternative transform for spectral analysis is the discrete cosine transform, type IV (DCT-IV). The DCT-IV is obtained by shifting the frequencies of the DCT basis functions in eqn. (A) by
&pgr;
/2M, in the form:
a
nk
=
2
M
cos
[
(
n
+
1
2
)
(
k
+
1
2
)
π
M
]
Unlike the DCT, the scaling factor is identical for all basis functions. It should be noted that the DCT-IV basis functions have a frequency shift, when compared to the DCT basis. Nevertheless, these transforms still lead to orthogonal basis.
The DCT and DCT-IV are useful tools for frequency-domain signal decomposition. However, they suffer from blocking artifacts. In typical applications, the transform coefficients X(k) are processed in some desired way: quantization, filtering, noise reduction, etc. Reconstructed signal blocks are obtained by applying the inverse transform to such modified coefficients. When such reconstructed signal blocks are pasted together to form the reconstructed signal (e.g. a decoded audio or video signal), there will be discontinuities at the block boundaries. The modulated lapped transform (MLT) eliminates such discontinuities by extending the length of the basis functions to twice the block size, i.e. 2M. Their basis functions are obtained by extending the DCT-IV functions and multiplying them by an appropriate window, in the form:
a
nk
=
h
(
n
)
cos
[
(
n
+
M
+
1
2
)
(
k
+
1
2
)
π
M
]
where k varies from 0 to M−1, but n now varies from 0 to 2M−1.
Thus, MLTs are used because they can lead to orthogonal basis and can achieve short-time decomposition of signals as a superposition of overlapping windowed cosine functions. Such functions provide a more efficient tool for localized frequency decomposition of signals than the DCT or DCT-IV. The MLT is a particular form of a cosine-modulated filter bank that allows for perfect reconstruction. For example, a signal can be recovered exactly from its MLT coefficients. Also, the MLT does not have blocking artifacts, namely, the MLT provides a reconstructed signal that decays smoothly to zero at its boundaries, avoiding discontinuities along block boundaries. In addition, the MLT has almost optimal performance for transform coding of a wide variety of signals. Because of these properties, the MLT is being used in many applications, such as many modern audio and video coding systems, including Dolby AC-3, MPEG-2 Layer III, and others.
As such, fast and efficient computation of the MLT is desirable because it can reduce implementation costs of MLT computations. Current MLT computation systems attempt to improve the speed of the MLT computations. Although some current MLT computation systems have reduced multiplications as compared to a “standard” MLT computation system, the number of data memory locations has increased in these systems to achieve faster computations In other words, reduced multiplicative complexity has lead to the need for additional data storage.
Therefore what is needed is a new MLT computation system that can save multiplications without requiring additional data storage. What is also needed is a MLT computation system that leads to savings in operations for biorthogonal MLT's (those in which different windows are used for the direct and inverse transforms).
Whatever the merits of the above mentioned systems and methods, they do not achieve the benefits of the present invention.
SUMMARY OF THE INVENTION
To overcome the limitations in the prior art described above, and to overcome other limitations that will become apparent upon reading and understanding the present specification, the present invention is embodied in a system and method for fast computation of a spatial transform of an input signal.
The computation system includes a direct transform module having a window processor and a transform processor. The window processor has a window function and an operator having a first set of weights. The window processor receives the input signal as sample blocks and the operator is adapted to apply butterfly coefficients determined by the window function to produce resulting vectors. Also, the window processor maps the input signal to a cascade of butterflies using the first set of weights and reorders the cascade of butterflies. The transform processor has a transform module and a coefficient combination operator. The transform module computes a spatial transform from the reordered cascade of butterflies to produce a transform coefficient. The coefficient combination operator combines the transform coefficients to produce an encoded output corresponding to the input signal.
In addition, the computation system can include an inverse transform module for inverse transformation of the encoded output. The inverse transform module includes components that can be the exact inverse of the components of transform module, namely an inverse coefficient combination operator, an inverse transform operator, and an inverse window operator. The encoded output is received and processed by the inverse coefficient combination operator, sent to and processed by the inverse transform operator, and then received and processed by the inverse window operator to produce an output signal that substantially matches the input signal.
Further, the present invention is embodied in Type-I and Type-II systems and methods for more efficiently computing butterfly operators with direct and inverse transforms for biorthogonal modulated lapped transforms and orthogonal modulated lapped transforms with a sine window, respectively. The Type-I and Type-II denomination is spe
DeFrank Edmond A.
Fischer Craig S.
Lyon, Harr & DeFrank, L.L.P.
Malzahn David H.
Microsoft Corporation
LandOfFree
Fast system and method for computing modulated lapped... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast system and method for computing modulated lapped..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast system and method for computing modulated lapped... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2568982