Signal averaging circuit and method for sample averaging

An averaging circuit and method are provided to compute a running average over a number of samples without the need for maintaining a large sample queue or register. Generally, the method includes the steps of (i) receiving and accumulating data samples in a plurality of sample-accumulators while counting the number of samples received in a sample-counter; (ii) alternately selecting the sum of the samples accumulated in each of the sample-accumulators; (iii) dividing the sum of the samples accumulated in a selected sample-accumulator by the number of samples received to provide an average of the samples accumulated therein; and (iv) interleaving selection of the plurality of sample-accumulators and alternating reset of each to provide a running average over a number of samples.

TECHNICAL FIELD

The present invention relates generally to signal processing, and more particularly to a signal averaging circuit and method to compute a running average over a fixed number of samples without the need for maintaining large queues or queuing registers.

BACKGROUND OF THE INVENTION

Signal averaging circuits and methods are used in a wide range of applications including, for example, processing motion-sensitive output from a array of photo-detectors in an optical navigation system.

One common application of a signal averaging circuit is to compute a running average, weighted or un-weighted, over a fixed number of samples. A conventional method for computing a running average over a predetermined number (N) of samples is schematically illustrated inFIG. 1. Referring toFIG. 1, a queue100, such as one implemented using a first-in-first-out or FIFO register, of depth N is required for storing N samples. New or most recent sample values are loaded or pushed into a head of the queue, shown as address0, while simultaneously old sample is popped out from a tail of the queue, shown as address N-1, and discarded. A sum of all entries in queue is computed at every update of queue. Once the queue is full, the running average can be computed at every time a new sample is received by dividing the sum of the values in the queue by N.

A block diagram of a conventional signal averaging circuit for computing a running average over N samples according to the above method is shown inFIG. 2. Referring toFIG. 2, the averaging circuit200, includes a queue storage202, such as a FIFO register, of depth N, for storing N samples, a sum storage204for storing a sum of values stored in the queue, an adder206for adding a new sample to the sum in the sum storage, a subtractor208for subtracting the old, discarded sample value to generate an updated sum, which is stored in sum storage and divided by N in a divider210to compute the running or rolling average over N samples. The averaging circuit200shown inFIG. 2is accurate and relatively fast, since it is not necessary to sum all values stored in the queue202every time a new sample is received. However, the above circuit is not wholly satisfactory for a number of reasons.

In particular, the implementation ofFIG. 2requires a large number of transistors, often referred to as gate count, for implementation of the storage queue202. For example, one use for an averaging circuit, i.e., estimating average speed of the motion from an array of photo-detectors in an optical navigation system, typically requires a storage queue capable of storing about 64 samples, i.e., N=64, and has a gate count of from about 10 thousand to about 100 thousand gates. Because the averaging circuit is typically fabricated as an application specific integrated circuit (ASIC) along with the photo-detector array and a signal processor, this can account for as much as 10% of the IC or chip space, and significantly impact the power consumption of the optical navigation system in which it is included. This is especially of concern in battery operated devices, such as a wireless optical mouse.

Yet another problem with conventional averaging methods and circuits is an inability to vary the length or number of samples, N, over which the running average is computed. That is once the ASIC has been designed and fabricated for a specific value of N, it cannot be changed, rather a new ASIC must be designed and fabricated. Moreover, because the size of the storage queue increases linearly with N there are practical limits on the number of samples over which the running average can be computed.

Accordingly, there is a need for averaging circuit and method to compute a running average over a number of samples that eliminates the need for maintaining large queues or queuing registers. It is further desirable that the circuit and method enables adjustment of the averaging length (N) without significant impact if any on design of an ASIC in which the averaging circuit is included.

The present invention provides a solution to this and other problems, and offers further advantages over conventional signal averaging circuits and methods.

DETAILED DESCRIPTION

The present invention is directed generally to signal processing, and more particularly, to an averaging circuit and method to compute a running average over a fixed number of samples without the need for maintaining large queues or queuing registers.

In the following description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be evident, however, to one skilled in the art that the present invention may be practiced without these specific details. In other instances, well-known structures, and techniques are not shown in detail or are shown in block diagram form in order to avoid unnecessarily obscuring an understanding of this description.

Reference in the description to “one embodiment” or “an embodiment” means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment of the invention. The appearances of the phrase “one embodiment” in various places in the specification do not necessarily all refer to the same embodiment. The term “to couple” as used herein may include both to directly connect and to indirectly connect through one or more intervening components.

The averaging circuit and method are particularly advantageous for processing signals from a photo-detector, such as a photodiode or other light sensitive element, in a array used in an optical navigation system, such as an optical computer mouse or an optical trackball.

For purposes of clarity, many of the details of optical navigation systems in general and signal processing circuits for optical navigation systems in particular that are widely known and are not relevant to the present invention have been omitted from the following description. Speckle-based optical navigation systems are described, for example, in co-pending, commonly assigned U.S. patent application No. 11/129,967, entitled, “Optical Positioning Device Having Shaped Illumination,” filed on May 16, 2005 by Clinton B. Carlisle et al., and incorporated herein by reference in its entirety.

Briefly, the averaging method of the present invention involves: (i) receiving and accumulating digital samples of a signal in at least two sample-accumulators; (ii) counting the number of samples received in a sample-counter; (iii) alternately resetting the two sample-accumulators at regular intervals offset with respect to each other by a predetermined number (N) of samples and resetting the sample counter when it reaches N; (iv) dividing the sum of samples accumulated by the number of samples accumulated after at-least N samples have been received in sample-accumulator to compute and output an average; and (v) alternately selecting the average output from one sample-accumulator while the other has just been reset as a running average over (N+sample counter) samples, thereby eliminating the need for maintaining large queues or queuing registers.

In general the sample-counter is reset simultaneously with each sample-accumulator reset. That is the sample-counter should be reset following a predetermined number N of cycles, and N is the offset number of samples between sample-accumulator resets. Each sample accumulator resets after (M·N) samples, where M is the number of sample-accumulators, a whole number greater than or equal to two (≧2), the resets from the M sample accumulators are spaced out evenly so that each reset occurs N samples after the other. The sample accumulator that has accumulated at least ((M−1)·N) samples but less than (M·N) samples, will be used to compute the running average. So the equivalent running average length will be ((M−1)·N) samples. Alternatively, the offset number of samples (N) between sample accumulator resets can be selected in relation to the number of data bits supported by the sample-counter such that the sample-counter rolls over (automatically resets to zero) after the Nth sample has been received and counted thereby eliminating the need for resetting the sample-counter. For example, when the sample-counter is implemented as a 6-bit binary counter N can be selected as 64 so that after the counter has counted 64 samples from 0 to 63 it rolls over to 0.

Exemplary embodiments of the averaging circuit and method according to the present invention will now be described in greater detail with reference toFIGS. 3 through 6.

In one embodiment, shown inFIG. 3, the averaging circuit includes first and second sample-accumulator302,304, a sample-counter306, a reset circuit308, a dividing circuit309, and a selection circuit or selector, such as a multiplexer (MUX314). Generally, each sample-accumulator includes an adding circuit or adder316to which the new sample is applied over sampling line318, and a sum storage320storing, until reset, the sum of the previous samples to which the new sample is added. The sum storage has an input322coupled to an output324of the associated adder316, an output326coupled to an input of the adder, and a reset input or reset328coupled to the reset circuit308. InFIG. 3, the dividing circuit includes a divider310and adder311. The divider has a first or operand input coupled to an output of the MUX314and a second or divisor input coupled to the adder311. The adder311has a first input313coupled to an output of the sample-counter306and a second input315coupled to a fixed value N so that the divider310divides the sum from the selected sample-accumulator302,304, by the sum of N and the number of samples received since the last sample-counter reset. It will be appreciated that this number, the operand, will always be a whole number between N and 2N to produce or compute a running average over N once the first N samples have been received to the sample-counter306, and to the reset circuit308to divide the sum of the sample-accumulator302,304, by the number of samples received by the sample-accumulator302,304, since its reset. Although described in detail with respect to the embodiment shown inFIG. 3, it will be appreciated that other embodiments are possible, including those in which the dividing circuit includes one or more adders providing operands to multiple dividers, which are coupled between the adders316of the sample-accumulators302,304, and the MUX314to select the quotient or sample-accumulator average rather than the undivided sample-accumulator sum.

In the embodiment shown, the sample-counter306is an n-bit forward counter, where n is the number of bits needed to express in binary form the predetermined number of samples (N) over which the average is computed. The sample-counter306has a frame trigger or input330coupled to the sample line318to count up the samples received in the sample-accumulators302,304, from an initial value of 0 to (N−1). It will be appreciated that other embodiments are possible, including those in which the sample-counter306is a down counter, and/or is reset by the reset circuit308, thereby enabling the sample-counter to hold a value between 0 and a preselected multiple of N.

The reset circuit308generally includes a comparator (CMP332) having a first n-bit input334coupled to an output of the sample-counter306and a second n-bit input338coupled to a n-bit value, here zero (0), to which the sample-counter306rolls over after counting up to N. The reset circuit308further includes a flip-flop340, such as T flip-flop, having an input342coupled to an output of the comparator332, and at least one output346coupled to the selection circuit, MUX314, and to the reset inputs328of the sample-accumulators302and304. In the embodiment shown the reset circuit308further includes an inverter348through which the output346is also coupled to the second sample-accumulator304. However, it will be appreciated that the second sample-accumulator304may instead be coupled directly to a second, inverting output from the flip-flop340without departing from the scope of the invention, and thereby eliminating the inverter348.

The output of the selection circuit, MUX314, operates to select the output of the appropriate accumulator,302or304, at the appropriate time to provide a running average of the sampled signal over a predetermined number of samples, without the need for maintaining large queues or queuing registers.

A graph illustrating sample-accumulator averages output by the divider310is shown inFIG. 4. Referring toFIG. 4, graph segments402represent averages from the first sample-accumulator302, which is first reset after 2N samples have been received, and then every 2N samples thereafter. Graph segments404represent averages from the second sample-accumulator304, which is first reset after N samples have been received, and then every 2N samples thereafter.FIG. 5is a graph illustrating a running or rolling average502of the sampled signal over a predetermined number of samples computed by alternately selecting or interleaving the averages output by the first and second sample-accumulators over time.

A method of computing a running average of a sampled signal over a predetermined number of samples using the averaging circuit ofFIG. 3will now be described in greater detail with reference toFIG. 6.FIG. 6is a flowchart of a method for computing a running average over a number of samples according to a method of the present invention using two sample-accumulators, a sample counter and a divider. Referring toFIG. 6, the method begins with receiving and accumulating samples in both a first and a second sample accumulator while counting the number of samples received in a sample-counter in first step (step602). After N samples (and subsequent odd sets of N samples) have been received the second sample-accumulator and the sample-counter are reset (step604). After the reset the sum of samples in the first sample-accumulator is divided by the sum of N plus the new sample-counter value, and this quotient is selected as the running average for the next N samples (step606). After 2N samples (and subsequent even sets of N samples) have been received the first sample-accumulator and the sample-counter are reset (step608). After the reset the sum of samples in the second sample-accumulator is divided by the sum of N plus the new sample-counter value, and this quotient is selected as the running average for the next N samples (step610). The above steps, steps602-610, are then repeated to continue computing or estimating the running average of the sampled signal. That is, after each even set (second set, fourth set, . . . ) of N samples have been received the first sample-accumulator and the sample-counter are reset, and the quotient of the sum of the second sample-accumulator divided by N+new value in the sample-counter and is selected as the running average. After each odd set (first set, third set, . . . ) of N samples have been received the second sample-accumulator and the sample-counter are reset, and the quotient of the sum of the first sample-accumulator is divided by N+new value in the sample-counter and is selected as the running average.

The ability of an averaging circuit and method of the present invention to compute a running average over a number of samples without the need for maintaining a large sample queue or register is shown graphically inFIGS. 7 through 10. The data used in the following examples was processed from samples collected from COMB detector arrays of an optical navigation system, such as an optical computer mouse, moved by a testing stage or apparatus in a circular motion around a circle of 1 cm radius at a speed of about 40 cm/s.

FIG. 7is a graph showing the estimated velocities (in arbitrary units) along two orthogonal axes over time for data samples collected from the COMB photo-detector arrays and averaged using two sample-accumulators with alternating resets at every 64-frames according to an embodiment of the present invention.FIG. 8is a graph showing estimated velocities over time for data samples collected from the same COMB photo-detector arrays and averaged using conventional 64-frame queues.

FIG. 9shows a graph or trace of the circular motion of an optical mouse calculated from data samples collected from the COMB photo-detector arrays and averaged using an embodiment of the method of the present invention to estimate speed and displacements of the motion.FIG. 10shows the trace of the circular motion calculated from the same raw samples using the conventional averaging method with 64-frame queues to estimate the speed and displacements of the motion.

As can be seen from the graphs ofFIGS. 7 through 10, results obtained from samples averaged using an averaging circuit and method of the present invention are substantially identical with those averaged using a conventional method while providing a 70% or greater reduction in gate count.

The advantages of the signal averaging circuit and method of the present invention over previous or conventional circuits and methods include: (i) the ability to compute a running average over a number of samples without the need for maintaining large queues or queuing registers; (ii) reduced power consumption in a circuit or device including the averaging circuit due to reduced gate counts; and (iii) the ability to change the averaging length over which the running average is computed without significant impact if any on design of an application specific integrated circuit (ASIC) in which the averaging circuit is included.

The foregoing description of specific embodiments and examples of the invention have been presented for the purpose of illustration and description, and although the invention has been described and illustrated by certain of the preceding examples, it is not to be construed as being limited thereby. They are not intended to be exhaustive or to limit the invention to the precise forms disclosed, and many modifications, improvements and variations within the scope of the invention are possible in light of the above teaching. It is intended that the scope of the invention encompass the generic area as herein disclosed, and by the claims appended hereto and their equivalents.