Pulse or digital communications – Receivers – Interference or noise reduction
Reexamination Certificate
1999-05-03
2001-08-21
Pham, Chi (Department: 2631)
Pulse or digital communications
Receivers
Interference or noise reduction
C708S300000
Reexamination Certificate
active
06278753
ABSTRACT:
TECHNICAL FIELD
This invention relates in general to data spectral analysis and particularly to digital data filtering. Specifically, the invention relates to a method and apparatus that provides improved wavelet filter operation for digital data systems.
BACKGROUND
With the advent of technologies and services related to teleconferencing and digital image storage, considerable progress has been made in the field of digital signal processing. As will be appreciated by those skilled in the art, digital signal processing typically relates to systems, devices, and methodologies for generating a sampled data signal, compressing the signal for storage and/or transmission, and thereafter reconstructing the original data from the compressed signal. Critical to any highly efficient, cost effective digital signal processing system is the methodology used for achieving compression.
Methodologies capable of minimizing the amount of information necessary to represent and recover an original data are desirable, as well as those with lowest computational complexity and cost. In addition to cost, simplicity of hardware and software implementations capable of providing high quality data reproduction with minimal delay are likewise desirable.
To present, the next standard of JPEG 2000 (Joint Photographic Experts Group) systems for still images proposes algorithms, which use a wavelet to achieve spectral decomposition of an input signal. In systems utilizing a wavelet, the data is typically divided through low pass and high pass filters. The implementation of wavelet filters is typically achieved using a filter bank, and in many instances involves several levels of filtering preceded by decimation of the previous level results. Filter bank operation is often implemented through numerous multiplications and additions between the wavelet coefficients and the input data.
The typical wavelet is implemented as a full length filter. The disadvantage to the full length filter approach is that if a different wavelet is sought to be used for processing the various subband levels, an entirely new wavelet must be created. This may increase the number of operations, thereby increasing complexity, reducing efficiency, and lowering flexibility.
FIG. 1
, is a block diagram of a prior art two-channel, single-level, digital data filter bank system
100
. Multi-level, multi-channel systems also exist in the art. System
100
includes an encoder path
102
and a decoder path
104
. The encoder path
102
includes an analysis bank
106
consisting of two complementary filters, a low pass-like filter H
0
(z)
108
, and a high pass-like filter, H
1
(z),
110
. The decoder path
104
includes a synthesis filter bank
112
consisting of a low pass-like filter G
0
(z)
114
and a high pass-like filter G
1
(z)
116
. All filters are assumed to be causal, that is, the filters are dependent only on past or present samples and not on future samples. The filter banks
106
,
112
exhibit signal processing delay which can be canceled out.
Any discrete wavelet transform used in two-channel sub-band filtering systems can be decomposed into a finite sequence of filtering steps denoted as cascades. The decomposition corresponds to a factorization of the polyphase matrix of the wavelet or sub-band filter into elementary matrices. These elementary matrices are formed as lower or upper triangular matrices, which have diagonal entries equal to a delay. Any matrix with polynomial entries can be decomposed (i.e. factored) into elementary matrices. Examples of this process are described in an article by Danbechies, I. and Sweldens, W., entitled “Factoring Wavelet Transforms into shifting Steps,” J. Fourier Anal. Appl., Vol. 4, No. 3, pp. 245-267, 1998, which is incorporated herein by reference.
FIG. 2
is a block diagram of a two-channel filter bank
200
whose analysis and synthesis filters are represented in polyphase form. An analysis filter bank
202
is represented by a valid polyphase polynomial matrix H(z) having a determinant equal to a monomial in the variable “z”, the algebraic equivalent of the delay operator, namely det [H(z)]=cz
n
, with an “n” integer and a “c” constant (ideally unity). The analysis filter bank
202
receives even-odd input data samples
206
separated by a unit delay
210
and generates low pass sub-band and high pass sub-band outputs
208
. Based on the conditions set for the analysis filter bank
202
, the synthesis filters
204
are represented by the inverse filter bank having a polyphase matrix G(z) equal to the adjoint of matrix H(z), that is adj [H(z)]. The output of the synthesis filter
204
generates polyphase outputs
212
separated by another delay
214
, and which are recombined to obtain the original signal.
FIG. 2
describes a lossless system; in other words, one not involving processing such as quantization, coding, error correction, or channel transmission loss.
The adjoint of matrix H(z),that is adj [H(z)], provides the condition to meet perfect reconstruction capability. It is well known that the inverse of a matrix is the adjoint of that matrix divided by its determinant. For example, if x(z), y(z), q(z), and p(z) are polynomials in “z”, the general polyphase matrices for the analysis and synthesis
H
(
z
)
=
[
x
(
z
)
y
(
z
)
-
q
(
z
)
p
(
z
)
]
=
[
H
0
(
z
)
H
1
(
z
)
]
G
(
z
)
=
[
p
(
z
)
-
y
(
z
)
q
(
z
)
x
(
z
)
]
=
[
G
0
(
z
)
G
1
(
z
)
]
(
1
)
filters for a two-channel case are:
with the polynomials meeting:
x(z)p(z)+y(z)q(z)=Z
n
. (2)
This last equation may be referred to as the Bezout identity, forcing the determinant of the H(z) matrix to be a delay. Thus, G(z)H(z) will also be a delay ensuring perfect reconstruction of the input assuming no quantization (image compression) and lossless channel. From here, the analysis and synthesis filters can be related as:
G
0
(z)=−H
1
(−z) and G
1
(z)=H
0
(−z). (3)
Hence, the following zero moments are obtained:
G
0
(−1)=−H
1
(1)=0 and G
1
(1)=H
0
(−1)=0. (4)
The matrices of equation (1) can be interchanged. Thus, the dual of equation (1) is the matrix pair:
H
d
(
z
)
=
[
q
(
z
)
p
(
z
)
-
x
(
z
)
y
(
z
)
]
=
[
H
0
d
(
z
)
H
1
d
(
z
)
]
G
d
(
z
)
=
[
y
(
z
)
-
p
(
z
)
x
(
z
)
q
(
z
)
]
=
[
G
0
d
(
z
)
G
1
d
(
z
)
]
(
5
)
which interchanges the analysis with the synthesis filters in the following way:
H
0
d
(Z)=G
0
(z).
H
1
d
(Z)=−G
1
(z) (6)
For the most general case of bi-orthogonal filter banks which have the above properties, the interchange of the filters produces visible effects in the presence of quantization because of the different behavior (in time and frequency domains) of the two available low-pass filters which act as interpolators. This is more evident for some filter pairs where the filters are substantially different, such as the 2/6 pair where 2 represents the length of the low pass filter and 6 represents the length of the high pass filter. There are also differences in measured peak signal-to-noise ratio, even for similar pairs, such as the 7/9 pair(and its dual, the 9/7 pair).
There is a need for a method and apparatus, which provide improved wavelet filtering. A system having the flexibility to generate multiplierless filters without having to create an entirely new filter for each wavelet level would be highly desirable. Such wavelets would minimize computational intensity and improve system programming.
REFERENCES:
patent: 5802481 (1998-09-01), Prieto
patent: 5943642 (1999-08-01), Choi
patent: 5999656 (1999-12-01), Zandi et al.
Daubechies I. and Sweldens, W., “Factoring Wavelet Transforms into Lifting Steps,” J. Fourier Anal. Appl., vol. 4, No. 3, pp. 245-267, 1998.
Pirez Yolanda M.
Prieto Yolanda
Suarez Jose I.
Corrielus Jean B
Doutre Barbara R.
Motorola Inc.
Pham Chi
Scutch, III Frank M.
LandOfFree
Method and apparatus of creating and implementing wavelet... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus of creating and implementing wavelet..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus of creating and implementing wavelet... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2445140