Moving Sum

Hi to all,



The sum or average of a certain number of samples (for ex. the last 100
values received) have to be checked constantly against a threshold.



I thought of implementing this by keeping a "Moving Sum" which will work by
adding the new value and subtracting the oldest. I think that can be
implemented by adding to a register the value just arriving and subtracting
the value coming out of an 100 word deep shift register.



Now, if a longer sum has to be checked then there is a memory problem
because a lot of values have to be stored. In addition more than one "Moving
Sums" is needed so if I use the above implementation I will have in addition
to store the same data more than once (for ex. the 1000 word Shift Register
will include the 100 word S.R. data).



Any idea of how this could be implemented?



The final system will have to keep 10 moving sums with the largest being
250,000 (8-bit) values for each of the 16 independent input channels.



Help to the design problem will be appreciated and acknowledged.


Christos

__________________________________________________

Christos Zamantzas
CERN, European Organization for Nuclear Research
Div. AB/BDI/BL                         tel: +41 22 767 3409
CH-1211 Geneva 23                  fax: +41 22 767 9560
Switzerland                                 christos.zamantzas@cern.ch
__________________________________________________

In article <bil9f7$4o2$1@sunnews.cern.ch>,
Christos <chris_saturnNOSPAM@hotmail.com> wrote:
>
>I thought of implementing this by keeping a "Moving Sum" which will work by
>adding the new value and subtracting the oldest. I think that can be
>implemented by adding to a register the value just arriving and subtracting
>the value coming out of an 100 word deep shift register.
>
>Now, if a longer sum has to be checked then there is a memory problem
>because a lot of values have to be stored. In addition more than one "Moving
>Sums" is needed so if I use the above implementation I will have in addition
>to store the same data more than once (for ex. the 1000 word Shift Register
>will include the 100 word S.R. data).
>
>Any idea of how this could be implemented?

Can you cheat?  That is, instead of having a 250,000 deep moving sum,
have it be 250,000 deep but only at intervals of every 1000 samples?  

The other option is once you have to go off-chip for memory for the
FIFO's, the size doesn't matter much because you can easily just throw
~1GB of DRAM on the other side.
-- 
Nicholas C. Weaver                                 nweaver@cs.berkeley.edu

Look for "CIC filter".  CIC is a Cascaded integrator Comb filter.  It is a
recursive implementation of a moving sum.   In your case, it sounds like you are
sampling the output once for every input sample, so you don't get the benefit of
decimation (if you could decimate, then the delay queue is shortened by a ratio
equal to the decimation ratio).  The CIC consists of an integrator, a subtractor
and a delay queue.  For a moving sum, you are stuck with the storage and the key
is to minimize the number of transactions you need to do with the storage per
sample.  In the case of the CIC, you need to do one read and one write per
sample.  For the depth you are looking at, you'll need to use off chip memory
for the storage (you might fit it into the bulk storage on an Altera Stratix).
You did not mention the sample rate.  If the data rate is sufficiently low, you
can time multiplex the data in/out of the external memory so that you can trade
memory width for depth, which might get you a lower parts count.

Christos wrote:

> Hi to all,
>
> The sum or average of a certain number of samples (for ex. the last 100
> values received) have to be checked constantly against a threshold.
>
> I thought of implementing this by keeping a "Moving Sum" which will work by
> adding the new value and subtracting the oldest. I think that can be
> implemented by adding to a register the value just arriving and subtracting
> the value coming out of an 100 word deep shift register.
>
> Now, if a longer sum has to be checked then there is a memory problem
> because a lot of values have to be stored. In addition more than one "Moving
> Sums" is needed so if I use the above implementation I will have in addition
> to store the same data more than once (for ex. the 1000 word Shift Register
> will include the 100 word S.R. data).
>
> Any idea of how this could be implemented?
>
> The final system will have to keep 10 moving sums with the largest being
> 250,000 (8-bit) values for each of the 16 independent input channels.
>
> Help to the design problem will be appreciated and acknowledged.
>
> Christos
>
> __________________________________________________
>
> Christos Zamantzas
> CERN, European Organization for Nuclear Research
> Div. AB/BDI/BL                         tel: +41 22 767 3409
> CH-1211 Geneva 23                  fax: +41 22 767 9560
> Switzerland                                 christos.zamantzas@cern.ch
> __________________________________________________

--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930     Fax 401/884-7950
email ray@andraka.com
http://www.andraka.com

 "They that give up essential liberty to obtain a little
  temporary safety deserve neither liberty nor safety."
                                          -Benjamin Franklin, 1759

Another option, if you're using Xilinx parts, is to take advantage of those
SRL16's.  In V2P parts (and I think V2) there are 2 per slice.  With 64 of
these guys cascaded together, you've got a 1-bit wide, 1024-bit long moving
sum (barrel shift down for the average).  That's 32 slices, or 8 CLB's per
bit-width, depending on the level of abstraction you like to think about.

--Josh


"Nicholas C. Weaver" <nweaver@ribbit.CS.Berkeley.EDU> wrote in message
news:bilbs8$1ck0$2@agate.berkeley.edu...
> In article <bil9f7$4o2$1@sunnews.cern.ch>,
> Christos <chris_saturnNOSPAM@hotmail.com> wrote:
> >
> >I thought of implementing this by keeping a "Moving Sum" which will work
by
> >adding the new value and subtracting the oldest. I think that can be
> >implemented by adding to a register the value just arriving and
subtracting
> >the value coming out of an 100 word deep shift register.
> >
> >Now, if a longer sum has to be checked then there is a memory problem
> >because a lot of values have to be stored. In addition more than one
"Moving
> >Sums" is needed so if I use the above implementation I will have in
addition
> >to store the same data more than once (for ex. the 1000 word Shift
Register
> >will include the 100 word S.R. data).
> >
> >Any idea of how this could be implemented?
>
> Can you cheat?  That is, instead of having a 250,000 deep moving sum,
> have it be 250,000 deep but only at intervals of every 1000 samples?
>
> The other option is once you have to go off-chip for memory for the
> FIFO's, the size doesn't matter much because you can easily just throw
> ~1GB of DRAM on the other side.
> --
> Nicholas C. Weaver                                 nweaver@cs.berkeley.edu

Whoops, probably won't work in your case-- I didn't read that last
paragraph.  But the SRL's are still good for less gigantic moving sums.

--Josh
"Josh Model" <model@ll.mit.edu> wrote in message
news:cBs3b.78$Y5.41@llslave.llan.ll.mit.edu...
> Another option, if you're using Xilinx parts, is to take advantage of
those
> SRL16's.  In V2P parts (and I think V2) there are 2 per slice.  With 64 of
> these guys cascaded together, you've got a 1-bit wide, 1024-bit long
moving
> sum (barrel shift down for the average).  That's 32 slices, or 8 CLB's per
> bit-width, depending on the level of abstraction you like to think about.
>
> --Josh
>
>
> "Nicholas C. Weaver" <nweaver@ribbit.CS.Berkeley.EDU> wrote in message
> news:bilbs8$1ck0$2@agate.berkeley.edu...
> > In article <bil9f7$4o2$1@sunnews.cern.ch>,
> > Christos <chris_saturnNOSPAM@hotmail.com> wrote:
> > >
> > >I thought of implementing this by keeping a "Moving Sum" which will
work
> by
> > >adding the new value and subtracting the oldest. I think that can be
> > >implemented by adding to a register the value just arriving and
> subtracting
> > >the value coming out of an 100 word deep shift register.
> > >
> > >Now, if a longer sum has to be checked then there is a memory problem
> > >because a lot of values have to be stored. In addition more than one
> "Moving
> > >Sums" is needed so if I use the above implementation I will have in
> addition
> > >to store the same data more than once (for ex. the 1000 word Shift
> Register
> > >will include the 100 word S.R. data).
> > >
> > >Any idea of how this could be implemented?
> >
> > Can you cheat?  That is, instead of having a 250,000 deep moving sum,
> > have it be 250,000 deep but only at intervals of every 1000 samples?
> >
> > The other option is once you have to go off-chip for memory for the
> > FIFO's, the size doesn't matter much because you can easily just throw
> > ~1GB of DRAM on the other side.
> > --
> > Nicholas C. Weaver
nweaver@cs.berkeley.edu
>
>

"Christos" <chris_saturnNOSPAM@hotmail.com> wrote in message news:<bil9f7$4o2$1@sunnews.cern.ch>...
> The sum or average of a certain number of samples (for ex. the last 100
> values received) have to be checked constantly against a threshold.

Do you require that each of the previously recieved values are
considered equally in the average calculation? If you can assume that
the current samples are more important than those recieved a long time
ago then you can calculate an "average" via an exponentially weighted
moving average filter. Or in other words, us a 1st-order LPF.

 a_k = (1/(n+1))*s_k + (n/(n+1))*a_k-1

where:
 s_k   = sample input at instant k,
 n     = number of samples in moving-average window,
 a_k   = average at instant k, and
 a_k-1 = average at instant k-1

As you can see this is quite easy to implement, requiring to
multiplies, one addition, and one register for a_k-1 storage. If you
choose n+1 do be a power of two then one of the multiplications (or I
guess it is a divide) becomes a simple shift operation.

-Jack Stone

Initializing the whole mess must also be considered. While the starting sum
can be zero, all the values in memory must be preset to zero and the
comparison to a threshold must be declared invalid until 'n' new values have
been accumulated.

-- 
Greg
readgc.invalid@hotmail.com.invalid
(Remove the '.invalid' twice to send Email)


"Christos" <chris_saturnNOSPAM@hotmail.com> wrote in message
news:bil9f7$4o2$1@sunnews.cern.ch...
> Hi to all,
>
>
>
> The sum or average of a certain number of samples (for ex. the last 100
> values received) have to be checked constantly against a threshold.
>
>
>
> I thought of implementing this by keeping a "Moving Sum" which will work
by
> adding the new value and subtracting the oldest. I think that can be
> implemented by adding to a register the value just arriving and
subtracting
> the value coming out of an 100 word deep shift register.
>
>
>
> Now, if a longer sum has to be checked then there is a memory problem
> because a lot of values have to be stored. In addition more than one
"Moving
> Sums" is needed so if I use the above implementation I will have in
addition
> to store the same data more than once (for ex. the 1000 word Shift
Register
> will include the 100 word S.R. data).
>
>
>
> Any idea of how this could be implemented?
>
>
>
> The final system will have to keep 10 moving sums with the largest being
> 250,000 (8-bit) values for each of the 16 independent input channels.
>
>
>
> Help to the design problem will be appreciated and acknowledged.
>
>
> Christos
>
> __________________________________________________
>
> Christos Zamantzas
> CERN, European Organization for Nuclear Research
> Div. AB/BDI/BL                         tel: +41 22 767 3409
> CH-1211 Geneva 23                  fax: +41 22 767 9560
> Switzerland                                 christos.zamantzas@cern.ch
> __________________________________________________
>
>

"Nicholas C. Weaver" <nweaver@ribbit.CS.Berkeley.EDU> wrote in message
>
> Can you cheat?  That is, instead of having a 250,000 deep moving sum,
> have it be 250,000 deep but only at intervals of every 1000 samples?

I have thought also of this but the idea was rejected as it increases the
total system error.
In order to make an interval you have to wait to receive all of its samples
before you add the interval to the sum. Thus, you update the sum slower
which increases the system error.

For a similar reason it is not possible to use a Low-Pass Filter. I guess to
have an average of the 250,000 values you need as many taps.

>
> The other option is once you have to go off-chip for memory for the
> FIFO's, the size doesn't matter much because you can easily just throw
> ~1GB of DRAM on the other side.

A sync. SRAM (probably 2Mx36b) will be available to the board. I have been
calculating and I think that it is enough.

----------------------------------------------------------------------------
---

"Ray Andraka" <ray@andraka.com> wrote in message
news:3F4E55BB.FC8A993A@andraka.com...
> Look for "CIC filter".  CIC is a Cascaded integrator Comb filter.  It is a
> recursive implementation of a moving sum.

I have never heard of the CIC filter I will investigate.

> For the depth you are looking at, you'll need to use off chip memory
> for the storage (you might fit it into the bulk storage on an Altera
Stratix).
> You did not mention the sample rate.  If the data rate is sufficiently
low, you
> can time multiplex the data in/out of the external memory so that you can
trade
> memory width for depth, which might get you a lower parts count.

The FPGA will be a Stratix, the sample rate is slow enough: 25 KHz
(acquisition every 40us) and external SRAM. The data are already received
multiplexed, but I don't get why it is better storing with larger width than
depth. Probably because I have no idea how to implement the Sratix - SRAM
communication.
Any Ap.Note or book?

Thanks a lot to all,
Christos

[exponential weighted averaging]

> a_k = (1/(n+1))*s_k + (n/(n+1))*a_k-1

>As you can see this is quite easy to implement, requiring to
>multiplies, one addition, and one register for a_k-1 storage. If you
>choose n+1 do be a power of two then one of the multiplications (or I
>guess it is a divide) becomes a simple shift operation.

The other multiply/divide turns into a shift and subtract.

-- 
The suespammers.org mail server is located in California.  So are all my
other mailboxes.  Please do not send unsolicited bulk e-mail or unsolicited
commercial e-mail to my suespammers.org address or any of my other addresses.
These are my opinions, not necessarily my employer's.  I hate spam.

The exponential weighted averaging cannot be used because all data into the
window have to be treated equally as all have the same importance.
If using a LPF and n is the number of samples in the window then if you want
to have an average of the last 100 values received then your filter has to
be 100 tap long.
Correct? I am asking just in case I have not understood fully how  digital
filters are implemented. The truth is that I have never done it, just read
about it.

Christos



"Hal Murray" <hmurray@suespammers.org> wrote in message
news:vl1tm7725v2310@corp.supernews.com...
> [exponential weighted averaging]
>
> > a_k = (1/(n+1))*s_k + (n/(n+1))*a_k-1
>
> >As you can see this is quite easy to implement, requiring to
> >multiplies, one addition, and one register for a_k-1 storage. If you
> >choose n+1 do be a power of two then one of the multiplications (or I
> >guess it is a divide) becomes a simple shift operation.
>
> The other multiply/divide turns into a shift and subtract.
>
> -- 
> The suespammers.org mail server is located in California.  So are all my
> other mailboxes.  Please do not send unsolicited bulk e-mail or
unsolicited
> commercial e-mail to my suespammers.org address or any of my other
addresses.
> These are my opinions, not necessarily my employer's.  I hate spam.
>