A neat trick for high-speed addressing of RAM modules

[nickjohnson]

So, here's a trick that occurred to me the other day that might come in handy for a logic analyzer (for instance).

Suppose you have a parallel RAM or ROM module that you want to stream data into and out of at high speed. You need to be able to jump to any arbitrary address, but your normal mode of operation is streaming.

It'd be nice to be able to address the module using a shift register, since that requires far fewer GPIOs. But now you have to clock addresses into the shift register serially for every address you want to read or write - for an n bit memory module, that's n clocks before you can do the read or write operation.

However, it's possible to stream data in and out with only a single clock per address. Here's how: Instead of addressing the memory sequentially, use an LFSR. External LFSRs have two very useful properties here. First, each state can be generated by shifting the previous state one bit to the left (something our shift register already does) and computing the next bit with a straightforward XOR operation. Second, it iterates through every n bit combination before returning to its initial address. Thus, we can stream data by repeatedly evaluating the next bit of the LFSR, but we can still jump to an arbitrary address by shifting an entire address in at once.

I think this could be pretty useful for building a logic analyzer: you can hook the probes up to the data lines of the memory module via a tristate buffer, then iterate through the RAM at high speed to take samples. To output the samples, you do the same thing, but use parallel reads or another shift register to read the data out.

Of course, doing streaming analysis with a buffer isn't really practical unless you use a dual port RAM chip or add additional mux/demux hardware to interleave reads and writes.

What do you think? Useful trick?

[matseng]

Hmm... So what is gained here in this solution compared to using a chain of regular presettable 4-bit binary counters? The counters can be set either directly 4 bits at a time directly from the mcu of from a series of shiftregisters.

To increment to the next address simply toggle the clock input to the counters.

[nickjohnson]

Hmm... So what is gained here in this solution compared to using a chain of regular presettable 4-bit binary counters? The counters can be set either directly 4 bits at a time directly from the mcu of from a series of shiftregisters.

To increment to the next address simply toggle the clock input to the counters.

A smaller BOM, basically. Instead of n/4 counters and n/8 shift registers, you only need n/8 shift registers. You also need fewer GPIOs.

[voidptr]

just my 2 cents :oP
how about a small cpld, where you can have all those things (counters , shift reg in out etc ) inside plus some other glue interface, and even small state machine to drive stuff instead of the cpu :-)

[nickjohnson]

just my 2 cents :oP
how about a small cpld, where you can have all those things (counters , shift reg in out etc ) inside plus some other glue interface, and even small state machine to drive stuff instead of the cpu :-)

Yup, if you're in a position to use a CPLD, of course, then all this goes out the window. :)

[dps]

Just toss a Virtex-7 FPGA on there. :)

[matseng]

A smaller BOM, basically. Instead of n/4 counters and n/8 shift registers, you only need n/8 shift registers. You also need fewer GPIOs.

But unless you're doing the polynomial xor thingie in hardware the clock rate will be very low. Xoring together the taps and shifting it all in software will take a lot of cycles but most likely it will still be faster than shifting out 20 new bits for each count.

For this method to make sense the calculations and feedback must be done in hardware and then let the software calculate a new value when you want to go directly to a particular address. But unless you've got pre-calculated values to shift out for common memory locations it can take a very long time for the cpu to calculate the bits corresponding to one of the last values of a 20 or 24 bit counter.

But I'm sure that this method has its advantages for special cases - I'll definitely keep it in the back of my head....

[nickjohnson]

A smaller BOM, basically. Instead of n/4 counters and n/8 shift registers, you only need n/8 shift registers. You also need fewer GPIOs.

But unless you're doing the polynomial xor thingie in hardware the clock rate will be very low. Xoring together the taps and shifting it all in software will take a lot of cycles but most likely it will still be faster than shifting out 20 new bits for each count.

It will certainly be a lot faster than clocking out 20 bits - or even 2 or 3. Xoring the taps can be done in a few clock cycles.

That said, you _could_ do it with a single xor IC and a tristate buffer, or with two XORs, and still be able to override the output and shift out a new address.

For this method to make sense the calculations and feedback must be done in hardware and then let the software calculate a new value when you want to go directly to a particular address. But unless you've got pre-calculated values to shift out for common memory locations it can take a very long time for the cpu to calculate the bits corresponding to one of the last values of a 20 or 24 bit counter.

Yes, but it's far more common to know the address you're jumping to. And if you just want to skip a few values, it's still quicker to shift out 4 or 5 bits than it is to send the entire new address.

[udif]

Yup, if you're in a position to use a CPLD, of course, then all this goes out the window. :)

Not necessarily.
I've used this technique for creating a simple clock divider in my 7400 contest entry (game of life in CPLD).
The benefit of using a LFSR vs a counter (I wanted a ~1:1000 divider) is that a LFSR-based counter takes far less product terms.