2
\$\begingroup\$

How does one efficiently implement a windowed counter, counting ones on a input line in the last say e.g. 10000 clk cycles (in VHDL for use on an FPGA)?

My idea: take a shift register (to delay the input line by 10000) and a special counter, incrementing when the input is high and decrementing if the shift register output is high.

For large windows (e.g. 2**20), this seems rather inefficient to me. Any suggestions on how to do this in a smarter way? I am not asking for a full implementation, just a pointer to some resources or an idea!

\$\endgroup\$
5
  • \$\begingroup\$ You could change the counters only every N clockcycles, reducing the need for saved values by factor N,but you always need to save the values you later subtract somehow \$\endgroup\$
    – PlasmaHH
    Sep 29, 2016 at 8:25
  • \$\begingroup\$ @user5880052 Both your suggestion and Botnic's answer are good ideas. The most area-efficient one depends on the maximum number of events you can get during the 10000 clock cycles. If you can potentially have all 10000 cycles set to one, your solution is obviously a much better choice. If you can have only a few ones, Botnic's suggestion is best. I don't think there are alternative ways to achieve this (except from minor variations like what PlasmaHH suggested). \$\endgroup\$
    – dim
    Sep 29, 2016 at 9:03
  • \$\begingroup\$ Does the sliding window have to move one bit at a time, or could you add some granularity to it? If yes, you could buffer e.g. 16 bits in a shift register, and when data has been shifted in 16 times you would clear the shift register and push the number of occurrences (4 bits) on a queue. \$\endgroup\$
    – jms
    Sep 29, 2016 at 9:19
  • \$\begingroup\$ What is the purpose of the windowed counter? There may be different more efficient implementations. If you need an exact count, with single cycle accuracy, you are stuck with either your suggestion or Botnik's. If some approximation is allowed, either in the time resolution, count accuracy or both, there may be some IIR filters that provide a good enough approximation with much reduced resources. \$\endgroup\$
    – Neil_UK
    Sep 29, 2016 at 9:28
  • \$\begingroup\$ like an up-down counter over time? \$\endgroup\$ Sep 29, 2016 at 11:20

1 Answer 1

3
\$\begingroup\$

You could store a time-stamp of each occurrence and remove it after a certain time. The memory needs now depends on the maximal number of occurrences during the window.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You could also store transitions and their timestamp, this way repetitive "ones" wouldn't load the timestamp system so much. \$\endgroup\$
    – jms
    Sep 29, 2016 at 13:13
  • \$\begingroup\$ This would save some memory if you have a lot of repetitive, but waste memory if you have a lot of single "ones" as you need to store both transitions. \$\endgroup\$
    – Botnic
    Sep 29, 2016 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.