generating Gray code with an iterated function system

[Kragen Javier Sitaker]

A couple of things I just noticed:

On Mon, Nov 07, 2011 at 10:39:18AM -0500, Kragen Javier Sitaker wrote:
> # A plain counter: O(n log n) gates with O(n**(1/3)) latency #
> # Ring counters: O(2**n) gates with O(1) latency #
> # Many carry-save counters should work: O((log n)**2) gates, O(1) latency #

My use of `n` here is inconsistent: sometimes it meant the number of
bits, and sometimes it meant the number of distinct counter values.
Sorry.

The other thing is that claiming anything less than O(n**(1/3)) latency,
where `n` is the number of bits, is sort of a lie, because bringing all
those bits to one place necessarily implies O(n**(1/3)) latency.  You
could arrange for the delays to be skewed according to how far away they
are from a particular spot where you want to observe them, so that all
the state changes happen on your retrospective light cone, but if you're
willing to make that kind of sacrifice, it doesn't really matter what
the absolute latency is.

The third thing is that if you're really counting so fast that
lightspeed delay becomes a major factor in your calculations, you may be
able to dispense with a lot of the flip-flops and just use delay lines.
For example, you can generate the low-order bits of an RBGC just by
delaying the outputs of a dead-simple binary ripple counter by the
appropriate amount: delay the 2s bit by half a clock cycle, the 4s bit
by a whole cycle, the 8s bit by two cycles, and the 16s bit by four
cycles.  (I suspect that kind of deterministic routing delay is hard to
achieve in modern FPGAs, since synthesis tools treat routing delay as a
bug to squeeze out, right?)  The higher-order bits need longer-term
memory, but I think they can be generated with less concern for
propagation latency, since they change so slowly.

To have a four-cycle propagation delay on a 1cm-wide chip, you'd need a
clock period of 8.34 picoseconds, and thus a clock speed of 120 GHz (and
a counting speed of 240 GHz).  The 32s bit would "only" toggle at
3.7GHz.  This suggests that a few centimeters of off-chip coaxial
cables, for use as delay lines, would be needed to make this idea
practical with current FPGAs, since they can typically only run at a few
hundred MHz, even though their individual gates have deep-sub-nanosecond
delay times, right?

(Computationally, the idea of a short coaxial or fiber-optic delay line
with a 120Gbps bit rate seems promising; if you could manage 30cm, you
could circulate 120 bits in it, enough for a fairly beefy register.)

BTW, Michael, I realized that Ccing you here is going to expose your
email address to spambots; if you don't want that, I can falsify the
mbox archives of kragen-discuss to remove your address.

Kragen