New(?) fast binary counter for FPGAs without carry logic (e.g. Actel) -- Request For Comment

So, you've reinvented the ripple counter, only with deterministic carry?

I'm not sure what you'd call it, but a quick Google on "ripple counter", possibly with "synchronous" tossed in there, may find you some prior art.

--
My liberal friends think I'm a conservative kook.
My conservative friends think I'm a liberal kook.
Why am I not happy that they have found common ground?

Tim Wescott, Communications, Control, Circuits & Software
http://www.wescottdesign.com

yes, nothing more. (Only still unsure about that REinvention by means of easily accessible, documented prior art -- this is why I am bothering the newsgroup.)

Can you be more specific? I have found only asynchronous ripple counters. For synchronous counter searches, I constantly get, what also vendor tools offer: counters without pipeline, i.e. with combinatorial network, spanning over all of the outputs. THIS is what I meant to avoid within the design.

Example:

Here you can see AND gate spanning three output bits. For wider counter, that means n-1 input wide AND. Of course, may be solved by faster logic. However, do you know about any working solution on *slow* architectures, at least as good as my proposal?

I know only about Johnson/one-hot counter (exponential floorplan consumption) and LFSR (exponential lookup-table consumption). Am I missing something?

Thank you for your response, Marek

How about gray code counters? Maybe their only advantage is when sampling them, not the carry propagation, though.

Jon

Gray code counters have the same carry issues as regular binary counters.

I think the idea of a synchronous ripple counter is a clever one. I'd be surprised if it hasn't been thought of before, but it's still clever.

--
My liberal friends think I'm a conservative kook.
My conservative friends think I'm a liberal kook.
Why am I not happy that they have found common ground?

Tim Wescott, Communications, Control, Circuits & Software
http://www.wescottdesign.com

(snip)

(snip)

I think it is pretty neat. I wouldn't be surprised if it had been invented in the early days of computing, and then forgotten.

My first thought would have been a Gray code counter, and probably also my second thought.

For now, I will call it carry anticipation.

In generating modulon N counters where N isn't a power of two, it often takes more than one cycle to do the comparison against N-1 to generate a reset. One possible solution is to compare against N-2, then delay the reset.

Well, more specifically, pipeline the comparator such that the reset comes out at the right time. That requires a comparison against a smaller number such that the result is right.

Also reminds me of Peter Alfke's divide by 2.5 circuit used to build really fast dividers. (snip)

The usual ripple counter is asynchronous, but I almost see what you mean.

Hmm. OK, my description above isn't quite right. If it did do carry anticipation, then it would be an ordinary binary counter. If instead you delay the carry at each stage by one cycle, does that describe it?

I suppose I still think that it is possible to build a Gray code counter with similar delays in it.

-- glen

Well, your scheme does have the drawback that while the counter is fast, and the sampling thereof is fast, the algorithm to get from the sampled value to a binary one takes some clock cycles.

Still, it'd work well as a capture for a microprocessor, or as a compare (for something like a PWM). It'd be better yet if you could make it an up-down counter, but I bet that's harder.

If you have access to a university library, do a literature search -- I'd be astonished if this hasn't shown up before in something like the IEEE Circuit Society journal, or in a patent someplace.

--
My liberal friends think I'm a conservative kook.
My conservative friends think I'm a liberal kook.
Why am I not happy that they have found common ground?

Tim Wescott, Communications, Control, Circuits & Software
http://www.wescottdesign.com

(snip on fast counters)

(snip)

Are you sure? Having not designed one recently, I wouldn't be sure, but I thoght that they didn't. You do have to consider when each FF will change, though, and so synchronous logic tools might not be able to do the timing.

Yes, many strange things were invented in the early days.

One that seems to be forgotten is the Earle latch, which as best I can describe it, combines one level of logic with latch circuitry. But that was before edge triggered logic.

-- glen

Well, yes an no. Now that you mention it, it strikes me that the "only one thing changes at a time" may make it _easier_ to anticipate carries

-- but _when_ any bit in a gray code counter changes is still dependent on _all_ the other bits; if that has to propagate through a bunch of logic, then you're back to slows-ville.

--
My liberal friends think I'm a conservative kook.
My conservative friends think I'm a liberal kook.
Why am I not happy that they have found common ground?

Tim Wescott, Communications, Control, Circuits & Software
http://www.wescottdesign.com

(snip)

If you don't have such access, and are interested in the such, I recommend Earl Swartzlander's "Computer Arithmetic, vol. 1" (and then vol. 2).

They are IEEE published books with reprints of various papers that were important in the history of computer arithmetic. Volume 2 has more recent papers, many related to fast floating point.

I don't see a counter like this, so far, though.

-- glen

(after Tim wrote)

(then I wrote)

But if one input of an AND is zero, it doesn't matter if the other one changes. When that input goes from zero to one, what matters is that the other input isn't still changing. You might be able to get only one gate delay on any signal that actually changes, even though the gate chain is longer.

All that said without actually looking at any circuits, so it might not apply here.

-- glen

It's simple and elegant. If you only wanted a divide by 2^n count with a square wave output, you don't really need the inversion formula. It would also work with the initial 'en' input as a count enable, but that would mess up your inversion formula, as the carry propagates even when the input enable is false. In fact, for an n-bit version of this counter, it the input enable were off for n cycles (or more) the output would eventually settle on a normal binary pattern without the inversion.

-- Gabor

Yes, the bitword inversion calculation is the price paid. I understand fully, that for demanding, high-throughput applications this is an obstacle.

However, as you said, for less intensive applications like PWM or timestamping it may be useful. For now, we are going to use it within time interval meter.

I have uploaded the design to OpenCores, so anybody is welcome to send their improvements.

Thank you for recommending the journal, I will give a look.

Best regards, Marek

Right.

Really? I do not see that at the moment. (Maybe I should try it in a simulation, rather than force the brain to boot.)

Marek

It made sense to me because this is essentially a ripple carry counter with pipeline stages in the carry chain, so unless the pipeline is also dependent on the enable input, it should eventually settle on a binary output.

I tried it myself, and it works as I expected. Here's my version (VHDL is not my first language so I converted to Verilog). It holds en true for 100 cycles at a time, and the output (eventually) settles on a multiple of 100 (modulo 256 in this case as my pcounter is 8 bits).

`timescale 1 ns / 1 ps

// pdivtwo by Marek Peca //

// Verilog adapted from the schematic diagram

`default_nettype none

module pdivtwo ( input wire en, input wire clk, input wire rst, output reg p, output reg q );

always @ (posedge clk or posedge rst) if (rst) begin p

Just to see if this has some application in Xilinx FPGA's I gave it a whirl in a Spartan 6. For a 32-bit counter with registered inputs and only the final p and q going offchip (again with additional registers) the best I could do in the -3 speed grade was 425 MHz. The same size counter and architecture (including a carry out) using the built-in carry chain logic for a normal binary counter resulted in more than 470 MHz. Looking through the timing numbers it appears that routing delays for this counter negate any help you might get by losing the carry chain (in Spartan 6). I imagine it would be a win in a CPLD (if you have the extra macrocells for the 2x register count). In the past I have used LFSR's for long counters in CPLD's - partly for speed, but mostly because of the reduced connectivity requirements.

Regards, Gabor

I've seen this used before. They added delay lines after the counter bits to produce a count output that is simple binary. This was in a high speed network interface and the front end ran very fast relative to the now antiquated FPGA technology. The actual circuit may not have been a counter, it may have been an adder, but it did have a carry chain.

In essence, this circuit is a pipelined, bit serial counter. You still need to wait for all the bits to be counted or use the conversion formula.

Rick

It seems the dedicated carry logic is of real help there. OK, it makes no sense for these FPGAs.

It is certainly *much* better at Actel/MicroSemi, we have already put it into our recent design.

Thank you very much for the try. Marek

=20

=20

.

interesting!

1. *please*, could you find the original work?

1. Actually, my initial design containted a bank of delay lines, recovering th= e binary counting (maybe unnecessary -- I must check Gabor's post about des= ynchronizing bits to plain binary counting). The drawback is, there is O(n^=

2) DFFs if implemented using shift registers. The k-th bit has to be delaye= d by (n-k) mod 2^k bits, what is still O(n^2). In practice, it gives huge D= FF counts for 32..64bit counters.

The delayers may be also implemented using embedded counters -- since there= is no need to delay arbitrary signal, only a pulse "p" (and then divide :2= ). Such a counter may be of ordinary architecture, because it has only log(= n) bits. However, all this seem to me to be too complicated and resource us= age may asymptotically drop to O(n log(n)), but in practice, it can hardly = be less than using shift registers.

I must try Gabor's Verilog to see, what happens.

Thank you very much, Marek

binary counting (maybe unnecessary -- I must check Gabor's post about desynchronizing bits to plain binary counting). The drawback is, there is O(n^2) DFFs if implemented using shift registers. The k-th bit has to be delayed by (n-k) mod 2^k bits, what is still O(n^2). In practice, it gives huge DFF counts for 32..64bit counters.

no need to delay arbitrary signal, only a pulse "p" (and then divide :2). Such a counter may be of ordinary architecture, because it has only log(n) bits. However, all this seem to me to be too complicated and resource usage may asymptotically drop to O(n log(n)), but in practice, it can hardly be less than using shift registers.

This would not have been published. It was part of a design a colleague worked on and this just seemed like the obvious way to do it, but then once you have a solution it always seems obvious, no?

The delay lines can be large, but in this design the data was quickly culled and the data rates dropped significantly.

Have you thought about clumping bits by twos, threes or fours? I'm not familiar with the logic family you are using, but if it has four input LUTs a grouping of three bits will give a carry out in one LUT with the same delay as one bit of your approach. Then you can use a lot fewer delay line FFs even if it doesn't change the O(n^2) relationship.

I mean, it really comes down to the number of FFs needed. If the constant is small enough and your n is not too large, all is good!

I'm not sure I understand how delay counters would work. Each edge has to be delayed, but the edges will happen in less than the delay time. You would need to somehow pipeline the edges...

If the counter is free running, you really only need to phase each bit correctly. The first bit is 0, 1, 0, 1... so there are only two phases, either one or no FFs to delay it rather than n-1. The second bit has a pattern of four states so the delay is modulo 4 and can be 0, 1, 2 or 3 rather than n-2. Does that help? It should take some of the sting out of a long counter.

I think even with an input enable if you route it to all FFs in parallel a modulo delay will still work ok.

Have you thought of switching to a device with a built in carry chain?

Rick