Databases Reference
In-Depth Information
Furthermore, we assume that the
sequence is zero outside the segment for which we are
calculating the filter parameters. Therefore, the autocorrelation function is estimated as
{
y
n
}
n
0
+
N
R
yy
(
k
)
=
y
n
y
n
−
k
(8)
n
=
n
0
+
1
+
k
and the
M
equations of the form of (
6
) can be written in matrix form as
R
A
=
P
(9)
where
⎡
⎤
R
y
y
(
0
)
R
yy
(
1
)
R
yy
(
2
)
···
R
yy
(
M
−
1
)
⎣
⎦
R
yy
(
1
)
R
yy
(
0
)
R
yy
(
1
)
···
R
yy
(
M
−
2
)
R
yy
(
2
)
R
yy
(
1
)
R
yy
(
0
)
···
R
yy
(
M
−
3
)
R
=
(10)
.
.
.
.
R
yy
(
M
−
1
)
R
yy
(
M
−
2
)
R
yy
(
M
−
3
)
···
R
yy
(
0
)
⎡
⎤
a
1
a
2
a
3
.
a
M
⎣
⎦
A
=
(11)
and
⎡
⎣
⎤
⎦
R
yy
(
1
)
R
yy
(
2
)
R
yy
(
3
)
P
=
(12)
.
R
yy
(
M
)
This matrix equation can be solved directly to find the filter coefficients:
R
−
1
P
A
=
(13)
However, the special form of the matrix
R
obviates the need for computing
R
−
1
. Note that not
only is
R
symmetric, but also each diagonal of
R
consists of the same element. For example,
the main diagonal contains only the element
R
yy
(
0
)
, while the diagonals above and below
the main diagonal contain only the element
R
yy
(
. This special type of matrix is called a
Toeplitz matrix
, and there are a number of efficient algorithms available for the inversion of
Toeplitz matrices [
228
]. Because
R
is Toeplitz, we can obtain a recursive solution to (
9
) that is
computationally very efficient and that has an added attractive feature from the point of view
of compression. This algorithm is known as the Levinson-Durbin algorithm [
229
,
230
]. We
describe the algorithm without derivation. For details of the derivation, see [
231
,
119
].
In order to compute the filter coefficients of an
M
th-order filter, the Levinson-Durbin
algorithm requires the computation of all filters of order less than
M
. Furthermore, during
the computation of the filter coefficients, the algorithm generates a set of constants
k
i
known
1
)