This module is part of the collection, A First Course in Electrical and Computer Engineering. The LaTeX source files for this collection were created using an optical character recognition technology, and because of this process there may be more errors than usual. Please contact us if you discover any errors.
The simplest numerical filter is the simple averaging filter. This filter
is defined by the equation
x=1N∑n=1Nun
.x=1N∑n=1Nun.
(1)The filter output x is the average of the N filter inputs u1,u2,...u1,u2,... , uN. These
inputs may be real or complex numbers, and x may be real or complex. This
simple averaging filter is illustrated in Figure 1.
If the averaging filter is excited by the constant sequence u1=u2=⋯=uN=uu1=u2=⋯=uN=u, then the output is
x=1N∑n=1Nu=u.x=1N∑n=1Nu=u.
(2)The output is, truly, the average of the inputs. Now suppose the filter is
excited by the linearly increasing sequence
u
n
=
n
,
n
=
1
,
2
,
...
,
N
.
u
n
=
n
,
n
=
1
,
2
,
...
,
N
.
(3)This sequence is plotted in Figure 2. How do we sum such a sequence in
order to produce the average
x
x? For
N
N even, the average may be written as
x=1N(x1+xN)+1N(x2+xN-1)+⋯+1N(xN/2+x(N/2)+1).x=1N(x1+xN)+1N(x2+xN-1)+⋯+1N(xN/2+x(N/2)+1).
(4)Each pair-sum in parentheses equals N+1N+1, and there are N2N2 such pair-sums,
so the average is
x=1NN2(N+1)=N+12.x=1NN2(N+1)=N+12.
(5)This is certainly a reasonable answer for the average of a linearly increasing
sequence. See Figure 2.
Write x=1N∑n=1Nnx=1N∑n=1Nn as a sum of pair-sums for
N
N odd. What
does
x
x equal?
General Sum Formula. Suppose the input to the simple averaging filter is the polynomial sequence
u
n
=
n
k
,
n
=
1
,
2
,
...
,
N
u
n
=
n
k
,
n
=
1
,
2
,
...
,
N
(6)where
k
k is a non-negative integer such as k=0,1,2,...k=0,1,2,.... The output of the filter is
xN(k)=1N∑n=1Nnk.xN(k)=1N∑n=1Nnk.
(7)We rewrite
x
x as xN(k)xN(k) to remind ourselves that we are averaging
N
N numbers, each of which is
n
k
n
k
. For example, when N=8N=8 and k=2k=2,
x8(2)=18∑n=18n2=18(1+4+9+⋯+64).x8(2)=18∑n=18n2=18(1+4+9+⋯+64).
(8)Rather than study the average xN(k)xN(k), we will study the sum NxN(k)NxN(k) and divide by
N
N at the very end:
SN(k)=NxN(k)=∑n=1Nnk.SN(k)=NxN(k)=∑n=1Nnk.
(9)The sum SN(k)SN(k) may be rewritten as the sum
S
N
(
k
)
=
∑
n
=
1
N
-
1
n
k
+
N
k
=
S
N
-
1
(
k
)
+
N
k
.
S
N
(
k
)
=
∑
n
=
1
N
-
1
n
k
+
N
k
=
S
N
-
1
(
k
)
+
N
k
.
(10)This result is very important because it tells us that the sum SN(k)SN(k), viewed as
a function of
N
N, obeys a recursion in which SN(k)SN(k) is just the sum using one less
input, namely, SN-1(k)SN-1(k), plus
N
k
N
k
. Now, since polynomials are the most general
functions that obey such recursions, we know that sN(k)sN(k) must be a polynomial
of order k+1k+1 in the variable
N
N:
sN(k)=a0+a1N+a2N2+⋯+ak+1Nk+1.sN(k)=a0+a1N+a2N2+⋯+ak+1Nk+1.
(11)Let's check to see that this polynomial really can obey the required recursion.
First note that SN-1(k)SN-1(k) is the following polynomial:
sN-1(k)=a0+a1(N-1)+⋯+ak+1(N-1)k+1.sN-1(k)=a0+a1(N-1)+⋯+ak+1(N-1)k+1.
(12)The term (N-1)k+1(N-1)k+1 produces
(
0
k
+
1
)Nk+1(-1)0+
(
1
k
+
1
)Nk(-1)1+⋯
(
0
k
+
1
)Nk+1(-1)0+
(
1
k
+
1
)Nk(-1)1+⋯. (Remember the binomial expansion?) Therefore the difference between SN(k)SN(k) and SN-1(k)SN-1(k) is
SN(k)-SN-1(k)=c0+c1N+⋯+ckNk.SN(k)-SN-1(k)=c0+c1N+⋯+ckNk.
(13)This recursion is general enough to produce the difference Nk provided we can solve for a0,a1,...a0,a1,... , ak+1ak+1 to make c0=c1=⋯=ck-1=0c0=c1=⋯=ck-1=0 and ck=1ck=1. We know that SN(k)=0SN(k)=0 for N=0N=0, so we know that a0=0a0=0, meaning that the polynomial for SN(k)SN(k) can really be written as
SN(k)=a1N+a2N2+⋯+ak+1Nk+1.SN(k)=a1N+a2N2+⋯+ak+1Nk+1.
(14)In order to solve for the coefficients of this polynomial, we propose to
write out our equation for sN(k)sN(k) as follows:
(
N
=
1
)
S
1
(
k
)
=
a
1
+
⋯
+
a
k
+
1
(
N
=
2
)
S
2
(
k
)
=
2
a
1
+
⋯
+
2
k
+
1
a
k
+
1
(
N
=
3
)
s
3
(
k
)
=
3
a
1
+
⋯
+
3
k
+
1
a
k
+
1
⋮
⋮
(
N
=
k
)
S
k
(
k
)
=
k
a
1
+
⋯
+
k
k
+
1
a
k
+
1
(
N
=
k
+
1
)
S
k
+
1
(
k
)
=
(
k
+
1
)
a
1
+
⋯
+
(
k
+
1
)
k
+
1
a
k
+
1
.
(
N
=
1
)
S
1
(
k
)
=
a
1
+
⋯
+
a
k
+
1
(
N
=
2
)
S
2
(
k
)
=
2
a
1
+
⋯
+
2
k
+
1
a
k
+
1
(
N
=
3
)
s
3
(
k
)
=
3
a
1
+
⋯
+
3
k
+
1
a
k
+
1
⋮
⋮
(
N
=
k
)
S
k
(
k
)
=
k
a
1
+
⋯
+
k
k
+
1
a
k
+
1
(
N
=
k
+
1
)
S
k
+
1
(
k
)
=
(
k
+
1
)
a
1
+
⋯
+
(
k
+
1
)
k
+
1
a
k
+
1
.
(15)Using the linear algebra we learned earlier, we may write these equations
as the matrix equation
l
1
...
1
2
4
...
2
k
+
1
⋮
⋮
⋮
k
k
2
...
k
k
+
1
(
k
+
1
)
(
k
+
1
)
2
...
(
k
+
1
)
k
+
1
a
1
a
2
⋮
a
k
+
1
=
s
1
(
k
)
S
2
(
k
)
⋮
S
k
+
1
(
k
)
.
l
1
...
1
2
4
...
2
k
+
1
⋮
⋮
⋮
k
k
2
...
k
k
+
1
(
k
+
1
)
(
k
+
1
)
2
...
(
k
+
1
)
k
+
1
a
1
a
2
⋮
a
k
+
1
=
s
1
(
k
)
S
2
(
k
)
⋮
S
k
+
1
(
k
)
.
(16)The terms on the right-hand side of the equal sign are “initial conditions”
that tell us how the sum SN(k)SN(k) begins for N=1,2,...,k+1N=1,2,...,k+1. These initial
conditions must be computed directly. (For example, S2(k)=1k+2k.S2(k)=1k+2k.) Then
the linear system of (k+1)(k+1) equations in (k+1)(k+1) unknowns may be solved for
a1,a2,...,ak+1a1,a2,...,ak+1. The solution for SNkSNk is then complete, and we may use it to
solve for SNkSNk for arbitrary
N
N.
When k=2k=2, we have the following equation for the
coefficients a1,a2a1,a2, and
a
3
a
3
in the polynomial SN(2)=a1N+a2N2+a3N3SN(2)=a1N+a2N2+a3N3 :
1
1
1
2
4
8
3
9
27
a
1
a
2
a
3
=
1
2
1
2
+
2
2
1
2
+
2
2
+
3
2
=
1
5
14
·
1
1
1
2
4
8
3
9
27
a
1
a
2
a
3
=
1
2
1
2
+
2
2
1
2
+
2
2
+
3
2
=
1
5
14
·
(17)
Solve for a1,a2,a3a1,a2,a3 in the linear equation of Example 2. Show
that SN(2)=a1N+a2N2+a3N3SN(2)=a1N+a2N2+a3N3 obeys the recursion SN(2)-SN-1(2)=N2SN(2)-SN-1(2)=N2.
(MATLAB) Write a MATLAB program to determine the coefficients a1,a2,...,ak+1a1,a2,...,ak+1 for the polynomial SN(k)SN(k). Generate a table of formulas for the averages xN(k)xN(k) for k=1,2,...,5k=1,2,...,5. Evaluate these formulas for N=2N=2,
4, 8, and 16.
Exponential Sums. When the input to an averaging filter is the
sequence
un=an,n=0,1,2,...,N-1,un=an,n=0,1,2,...,N-1,
(18)we say that the input is exponential (or geometric). Typical sequences are
illustrated in Figure 6.5 for a=0.9,a=1a=0.9,a=1, and a=1.1a=1.1. Don't let it throw
you that we have changed the index to run from 0 to N-1N-1 rather than from
1 to
N
N. This change is not fundamentally important, but it simplifies our
study. The sum of the inputs is
SN=∑n=0N-1an.SN=∑n=0N-1an.
(19)How do we evaluate this sum? Well, we note that the sum aSNaSN is
a
S
N
=
∑
n
=
0
N
-
1
a
n
+
1
=
∑
k
=
1
N
a
k
=
∑
k
=
0
N
-
1
a
k
+
a
N
-
1
=
S
N
+
a
N
-
1
.
a
S
N
=
∑
n
=
0
N
-
1
a
n
+
1
=
∑
k
=
1
N
a
k
=
∑
k
=
0
N
-
1
a
k
+
a
N
-
1
=
S
N
+
a
N
-
1
.
(20)Therefore, provided a≠1a≠1, the sum
S
N
S
N
is
SN=1-aN1-a,
a≠1.SN=1-aN1-a,
a≠1.
(21)This formula, discovered already in the chapter covering the functions
e
x
e
x
and ejθejθ, works for a≠1a≠1. When a=1a=1,
then SN=NSN=N:
S
N
=
1
-
a
N
1
-
a
,
a
≠
1
N
,
a
=
1
.
S
N
=
1
-
a
N
1
-
a
,
a
≠
1
N
,
a
=
1
.
(22)When |a|<1|a|<1, then aN→0aN→0 for N→∞N→∞, and we have the asymptotic formula
limN→∞SN=11-a,|a|<1.limN→∞SN=11-a,|a|<1.
(23)
Evaluate SN=∑n=0N-1anSN=∑n=0N-1an and XN=1NSNXN=1NSN for a=0.9,1a=0.9,1, and 1.1
and for N=1,2,4,8,16N=1,2,4,8,16, and 32.
Prove that SN=∑n=0N-1anSN=∑n=0N-1an obeys the recursion
S
N
=
S
N
-
1
+
a
N
-
1
.
S
N
=
S
N
-
1
+
a
N
-
1
.
(24)Prove that SN=NSN=N obeys this recursion for a=1a=1 and that SN=1-aN1-aSN=1-aN1-a obeys
it for a≠1a≠1.
Recursive Computation. Every sum of the form
SN=∑n=0N-1unSN=∑n=0N-1un
(25)obeys the recursion
SN=SN-1+uN-1.SN=SN-1+uN-1.
(26)This means that when summing numbers you may “use them and discard them.” That is, you do not need to read them, store them, and sum them.
You may read
u
0
u
0
to form
S
1
S
1
and discard
u
0
u
0
; add
u
1
u
1
to
S
1
S
1
and discard
u
1
u
1
; add
u
2
u
2
to
S
2
S
2
; and continue.
This is very important for hardware and software implementations of running sums. You need only store the current sum, not the measurements that produced it. Two illustrations of the recursion Sn+1=Sn+unSn+1=Sn+un are provided in Figure 4. The diagram on the left is self-explanatory. The diagram on the right says that the sum
S
n
S
n
is stored in a memory location, to be added to
u
n
u
n
to produce Sn+1Sn+1, which is then stored back in the memory location to be added to un+1un+1, and so on.
(What does "Endorsed by" mean?)
"Reviewer's Comments: 'I recommend this book as a "required primary textbook." This text attempts to lower the barriers for students that take courses such as Principles of Electrical Engineering, […]"