Consider causal FIR filters:
yn=∑
k
=0M−1hkxn−k
y
n
k
M
1
0
h
k
x
n
k
; this can be realized using the following structure
or in a different notation
This is called the
direct-form FIR filter structure.
There are no closed loops (no feedback) in this structure, so it
is called a non-recursive structure. Since any FIR
filter can be implemented using the direct-form, non-recursive
structure, it is always possible to implement an FIR filter
non-recursively. However, it is also possible to implement an
FIR filter recursively, and for some
special sets of FIR filter coefficients this is much more
efficient.
yn=∑
k
=0M−1xn−k
y
n
k
M
1
0
x
n
k
where
hk=00
1
⌃︀
k
=
0
1…1
1
⌃︀
k
=
M
-
1
000…
h
k
0
0
1
⌃︀
k
=
0
1
…
1
1
⌃︀
k
=
M
-
1
0
0
0
…
But note that
yn=yn−1+xn−xn−M
y
n
y
n
1
x
n
x
n
M
This can be implemented as
Instead of costing
M−1
M
1
adds/output point, this comb filter costs only two
adds/output.
Is this stable, and if not, how can it be made so?
IIR filters must be implemented with a
recursive structure, since that's the
only way a finite number of elements can generate an
infinite-length impulse response in a linear, time-invariant (LTI)
system. Recursive structures have the advantages of being
able to implement IIR systems, and sometimes greater
computational efficiency, but the disadvantages of
possible instability, limit cycles, and other deletorious
effects that we will study shortly.
The flow-graph-reversal theorem says that if one
changes the directions of all the arrows, and inputs at the
output and takes the output from the input of a reversed
flow-graph, the new system has an identical input-output
relationship to the original flow-graph.
The z-transform of an FIR filter can be factored into a
cascade of short-length filters
b
0
+
b
1
z-1+
b
2
z-3+…+
b
m
z−m=
b
0
(1−
z
1
z-1)(1−
z
2
z-1)…(1−
z
m
z-1)
b
0
b
1
z
b
2
z
-3
…
b
m
z
m
b
0
1
z
1
z
1
z
2
z
…
1
z
m
z
where the
z
i
z
i
are the zeros of this polynomial. Since the
coefficients of the polynomial are usually real, the roots
are usually complex-conjugate pairs, so we generally combine
(1−
z
i
z-1)(1−
z
i
¯z-1)
1
z
i
z
1
z
i
z
into one quadratic (length-2) section with
real coefficients
(1−
z
i
z-1)(1−
z
i
¯z-1)=1−2ℜ
z
i
z-1+|
z
i
|2z-2=
H
i
z
1
z
i
z
1
z
i
z
1
2
z
i
z
z
i
2
z
-2
H
i
z
The overall filter can then be implemented in a
cascade structure.
This is occasionally done in FIR filter implementation
when one or more of the short-length filters can be
implemented efficiently.
It is also possible to implement FIR filters in a lattice
structure: this is sometimes used in adaptive filtering
