Random Bit Generator

Unlabeled gate below....

My 'HC164 has A, B as inputs, which I assumed were your D1, D2 inputs until I noticed the unlabeled device.

WHAT IS THIS ===> | | | | | |

...Jim Thompson

OK. Thanks! ...Jim Thompson

Knuth's "Art of Computer Programming" Vol 2 (iirc) has everything you'd ever want to know about PRBSes as well as other sorts of RNGs, such as linear congruential generators. Knuth goes all the way from number theory to cookbook tables.

Cheers

Phil Hobbs

rs

ends with a list of possible taps for 3 to 168 bit maximum length LFSRs

-Lasse

I posted some pages of Applied Cryptography here:

The pages contain the information you need to build dozens of different LFSR's of maximum period using a couple of 74... series. IIRC you can replace the XOR function with NXOR and get a maximal period LSFR that will self start (the all zero startup state becomes a valid state for the LSFR)

I'm only getting 52 before a repeat :-(

(I'm looking at the serial stream.) ...Jim Thompson

Jim,

Look at the pages I just posted. They will give you the taps for the maximum length sequence (should be 4,3,2,0)

Link times out :-( ...Jim Thompson

Send PM - I'll PM the zip file (0.5 Mb)

Get rid of that reset kludgery.

LFSRs with the right taps will cycle through 2^N-1 states. The other state is stable.

The stable state is all 0s or all 1s. You can switch to the other one with an inverter.

I did :-)

...Jim Thompson

It will click when you see it. The key idea is Finite State Machine. With N flip-flops, the best you can do is 2^N states. A counter gets them all, but it's not random.

A LFSR with the right taps gets 2^N-1, and they happen to be a "nice" random pattern. They are widely used in gear for testing communication links.

Horowitz and Hill, Art of Electronics, has a nice section starting on page 655. It's only 3 pages, no hairy math.

The Wikipedia article on LFSRs is good:

OK. Got it working. Repeats at 255.

What was confusing me was the double-talk about numbering the shift-register stages. Must be Physics majors who still have their direction of current reversed ;-)

Thanks again, David! ...Jim Thompson

Yep, That's a good one. Thanks! ...Jim Thompson

No problem. "Breadboarded" instantly in PSpice ;-)

I'm currently running with taps at 8,4,3,2 and getting a 255-long sequence. ...Jim Thompson

Nah - it's a digital nerd thing - Typically, for a binary output, Q0, Q1, ... Qn, the bit position corresponds to that power of two. As far as which way you shift, there's a holy war between little-endian and big-endian, but ssentially, it's a coin toss. :-)

Cheers! Rich