A neat trick for high-speed addressing of RAM modules

Anything not related to a specific project.

A neat trick for high-speed addressing of RAM modules

Postby nickjohnson » Fri Nov 30, 2012 4:50 pm

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?
nickjohnson
Sr. Member
Sr. Member
 
Posts: 295
Joined: Mon Nov 26, 2012 4:32 am

Re: A neat trick for high-speed addressing of RAM modules

Postby matseng » Fri Nov 30, 2012 9:43 pm

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.
User avatar
matseng
Hero Member
Hero Member
 
Posts: 876
Joined: Sat Oct 15, 2011 12:29 pm
Location: Kuala Lumpur, Malaysia

Re: A neat trick for high-speed addressing of RAM modules

Postby nickjohnson » Sat Dec 01, 2012 3:57 am

matseng wrote: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.
nickjohnson
Sr. Member
Sr. Member
 
Posts: 295
Joined: Mon Nov 26, 2012 4:32 am

Re: A neat trick for high-speed addressing of RAM modules

Postby voidptr » Sat Dec 01, 2012 4:19 am

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 :-)
voidptr
Full Member
Full Member
 
Posts: 247
Joined: Fri Oct 08, 2010 5:58 am

Re: A neat trick for high-speed addressing of RAM modules

Postby nickjohnson » Sat Dec 01, 2012 4:49 am

voidptr wrote: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. :)
nickjohnson
Sr. Member
Sr. Member
 
Posts: 295
Joined: Mon Nov 26, 2012 4:32 am

Re: A neat trick for high-speed addressing of RAM modules

Postby dps » Sat Dec 01, 2012 12:20 pm

Just toss a Virtex-7 FPGA on there. :)
dps
Jr. Member
Jr. Member
 
Posts: 55
Joined: Thu Jul 21, 2011 8:29 pm

Re: A neat trick for high-speed addressing of RAM modules

Postby matseng » Sat Dec 01, 2012 1:02 pm

nickjohnson wrote: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....
User avatar
matseng
Hero Member
Hero Member
 
Posts: 876
Joined: Sat Oct 15, 2011 12:29 pm
Location: Kuala Lumpur, Malaysia

Re: A neat trick for high-speed addressing of RAM modules

Postby nickjohnson » Sat Dec 01, 2012 1:06 pm

matseng wrote:
nickjohnson wrote: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.
nickjohnson
Sr. Member
Sr. Member
 
Posts: 295
Joined: Mon Nov 26, 2012 4:32 am

Re: A neat trick for high-speed addressing of RAM modules

Postby udif » Sat Dec 01, 2012 8:07 pm

nickjohnson wrote: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.
udif
Newbie
Newbie
 
Posts: 27
Joined: Sat Mar 20, 2010 6:12 pm


Return to General discussion