Skip to content Skip to navigation Skip to collection information

OpenStax_CNX

You are here: Home » Content » A First Course in Electrical and Computer Engineering » Filtering: Simple Averages

Navigation

Table of Contents

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Endorsed by Endorsed (What does "Endorsed by" mean?)

This content has been endorsed by the organizations listed. Click each link for a list of all content endorsed by the organization.
  • IEEE-SPS

    This collection is included inLens: IEEE Signal Processing Society Lens
    By: IEEE Signal Processing Society

    Click the "IEEE-SPS" link to see all content they endorse.

  • College Open Textbooks display tagshide tags

    This collection is included inLens: Community College Open Textbook Collaborative
    By: CC Open Textbook Collaborative

    Comments:

    "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, […]"

    Click the "College Open Textbooks" link to see all content they endorse.

    Click the tag icon tag icon to display tags associated with this content.

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • Bookshare

    This collection is included inLens: Bookshare's Lens
    By: Bookshare - A Benetech Initiative

    Comments:

    "Accessible versions of this collection are available at Bookshare. DAISY and BRF provided."

    Click the "Bookshare" link to see all content affiliated with them.

  • NSF Partnership display tagshide tags

    This collection is included inLens: NSF Partnership in Signal Processing
    By: Sidney Burrus

    Click the "NSF Partnership" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

  • Featured Content display tagshide tags

    This collection is included inLens: Connexions Featured Content
    By: Connexions

    Comments:

    "A First Course in Electrical and Computer Engineering provides readers with a comprehensive, introductory look at the world of electrical engineering. It was originally written by Louis Scharf […]"

    Click the "Featured Content" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

Also in these lenses

  • UniqU content

    This collection is included inLens: UniqU's lens
    By: UniqU, LLC

    Click the "UniqU content" link to see all content selected in this lens.

  • Evowl

    This collection is included inLens: Rice LMS's Lens
    By: Rice LMS

    Comments:

    "Language: en"

    Click the "Evowl" link to see all content selected in this lens.

  • Lens for Engineering

    This module and collection are included inLens: Lens for Engineering
    By: Sidney Burrus

    Click the "Lens for Engineering" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.
 

Filtering: Simple Averages

Module by: Louis Scharf. E-mail the author

Note:

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=1Nn=1Nun .x=1Nn=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.

Figure 1: A Simple Averaging Filter
A box diagram that consist several expressions, arrows and a rectangle. The image starts on the left with the expression u_1,u_2,...u_n. Then an arrow extends to the right and ends at a rectagle box containing the expression 1/N sum_(n=1)^(N) U_n. On the right side of the box a line extends to the right and ends at the expression x.

Example 1

If the averaging filter is excited by the constant sequence u1=u2==uN=uu1=u2==uN=u, then the output is

x=1Nn=1Nu=u.x=1Nn=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.

Figure 2: Linearly Increasing Sequence
This Cartesian graph contains several dots in a line. The line starts at the origin and rises with a positive slope. To the right of the line is the expression U_n versus N. Along the left side of the y axis there are two vertical dashes labeled 1 and two and then above these ticks there are three consecutive dots with the expression (N+1)/2 directly above that. The x axis is labeled with dashes labeled 1-8. Below dash 8 is the expression (N) the x axis is labeled n.

Exercise 1

Write x=1Nn=1Nnx=1Nn=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)=1Nn=1Nnk.xN(k)=1Nn=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)=18n=18n2=18(1+4+9++64).x8(2)=18n=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.

Example 2

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)

Exercise 2

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.

Exercise 3

(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)
Figure 3: Exponential Sequences
Figure 3 (pic005.png)

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 a1a1, the sum S N S N is

SN=1-aN1-a, a1.SN=1-aN1-a, a1.
(21)

This formula, discovered already in the chapter covering the functions e x e x and ejθejθ, works for a1a1. 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 aN0aN0 for NN, and we have the asymptotic formula

limNSN=11-a,|a|<1.limNSN=11-a,|a|<1.
(23)

Exercise 4

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.

Exercise 5

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 a1a1.

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.

Figure 4: The Recursion Sn+1=Sn+unSn+1=Sn+un
Figure 4 (pic006.png)

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.

Collection Navigation

Content actions

Download:

Collection as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks