How many levels of digital logic does it take to implement a counter in logarithmic space?
We wish to avoid the long worst-case ripple of a naive implementation of a binary counter. Avoid the shifter counter which can only count as high its width. Avoid an exponentially huge circuit.
Conceptually, we wish to amortize the cost of the bad ripple over many increments.
Gray codes are probably the way to go. This has almost certainly already been investigated. There seems to something "deep" about whether or not you can count "infinitely" large while only making "local" modifications to bits of the counter. P=NP?
No comments :
Post a Comment