Random Bit Generator

Do you want real random or just pseudo random?

If pseudo random is good enough, google for LFSR. With the right polynomial, you get a random sequence of (2^N)-1 bits. There are tables of polynomials that do that. Some of them need only 1 XOR gate.

Pseudo-random is just fine. I just need it to test an encoding/decoding chip design. A hundred bits or so before repeat would be quite adequate. No security involved... just testing to be sure of no decoding hiccups.

Thanks! ...Jim Thompson

How random do you need it to be?

If you want truly or statistically-close-to-really random, it's a Hard Problem. You'd probably want something like an avalanche or other noise diode, amplified, and then fed into a comparator... shield and filter the >bleep< out of it to keep it from being pulled around by external noise. Latch the output of the comparator on each clock pulse and you've got reasonably random bits.

If you're willing to accept pseudo-random bits (chaotic-looking, but actually predictable), a cheap and easy solution is a maximal-length linear feedback shift register. These require a shift register of suitable width (feel free to daisy-chain several 74HC595 or similar) and an N-input XOR. You simply XOR several of the parallel outputs of the shift register together and feed this back into the shift-register inputs. If you pick these tapped outputs correctly (creating a primitive polynomial mod 2), the output bitstream will have a period of 2^N-1 before it repeats (where N is the width of the shift register).

You have to be careful to pre-load the register with at least one "1" bit at reset time... it'll stick at zero, otherwise.

Schneier's "Applied Cryptography" has a table of suitable primitive polynomials on pages 376-377. Some of them are rather huge... if you want a 3217-bit shift register version, he's got two of them!

There are several which would be pretty easy to implement, and have a good long repeat period... 60 to 64 bits, with at most 5 inputs to the XOR.

For more sophisticated LFSRs, you can:

- Run several of them of different lengths (each with its own feedback chain), and XOR the results.

- Use an "alternating stop and go" generator, which uses three LFSRs of different lengths and feedback taps. One generator "A" is shifted on every clock; its output controls which of the other two "B" and "C" is shifted during that clock; the final output is taken by XORing the output bits of "B" and "C". This architecture has the effect of "hiding" the raw outputs of the LFSRs from visibility, and makes determining the LFSR feedback coefficients quite a bit harder.

OT:

Question: Why it is impossible to have sex in the middle of the Red Square in Moscow?

Answer: Because every idiot bystander will be eager to give his invaluable advice.

Here is my invaluable advice: make a ring of the odd number of invertors, compute a logical function from this ring.

Take a binary counter, compute some ugly logical function from its output.

Vladimir Vassilevsky DSP and Mixed Signal Design Consultant

Vladimir, What's your definition of "ugly" ?:-) ...Jim Thompson

"Jim Thompson" schreef in bericht news: snipped-for-privacy@4ax.com...

Ever saved the schematic below. FAIK it's from John Fields.

petrus bitbyter

Version 4 SHEET 1 1140 680 WIRE 1008 -496 -320 -496 WIRE -384 -480 -432 -480 WIRE -432 -448 -432 -480 WIRE -432 -448 -480 -448 WIRE 464 -432 -320 -432 WIRE -544 -400 -880 -400 WIRE -432 -384 -480 -384 WIRE 224 -368 -320 -368 WIRE -432 -352 -432 -384 WIRE -384 -352 -432 -352 WIRE -256 -304 -320 -304 WIRE 704 -224 96 -224 WIRE -880 -192 -880 -400 WIRE -880 -192 -928 -192 WIRE 464 -192 464 -432 WIRE 464 -192 96 -192 WIRE 32 -176 -784 -176 WIRE -16 -160 -784 -160 WIRE 224 -160 224 -368 WIRE 224 -160 96 -160 WIRE -992 -144 -1056 -144 WIRE -256 -144 -256 -304 WIRE -256 -144 -784 -144 WIRE -848 -128 -928 -128 WIRE -496 -128 -784 -128 WIRE -736 -112 -784 -112 WIRE 944 64 -1216 64 WIRE -864 112 -1136 112 WIRE -624 112 -864 112 WIRE -384 112 -624 112 WIRE -144 112 -384 112 WIRE 96 112 -144 112 WIRE 336 112 96 112 WIRE 576 112 336 112 WIRE 816 112 576 112 WIRE -864 160 -864 112 WIRE -624 160 -624 112 WIRE -384 160 -384 112 WIRE -144 160 -144 112 WIRE 96 160 96 112 WIRE 336 160 336 112 WIRE 576 160 576 112 WIRE 816 160 816 112 WIRE -1056 208 -1056 -144 WIRE -944 208 -1056 208 WIRE -736 208 -736 -112 WIRE -736 208 -784 208 WIRE -704 208 -736 208 WIRE -496 208 -496 -128 WIRE -496 208 -544 208 WIRE -464 208 -496 208 WIRE -256 208 -256 -144 WIRE -256 208 -304 208 WIRE -224 208 -256 208 WIRE -16 208 -16 -160 WIRE -16 208 -64 208 WIRE 16 208 -16 208 WIRE 224 208 224 -160 WIRE 224 208 176 208 WIRE 256 208 224 208 WIRE 464 208 464 -192 WIRE 464 208 416 208 WIRE 496 208 464 208 WIRE 704 208 704 -224 WIRE 704 208 656 208 WIRE 736 208 704 208 WIRE 1008 208 1008 -496 WIRE 1008 208 896 208 WIRE -976 256 -1056 256 WIRE -944 256 -976 256 WIRE -704 256 -736 256 WIRE -464 256 -496 256 WIRE -224 256 -256 256 WIRE 16 256 -16 256 WIRE 256 256 224 256 WIRE 496 256 464 256 WIRE 736 256 704 256 WIRE -1216 288 -1216 64 WIRE -1056 288 -1056 256 WIRE -976 352 -976 256 WIRE -736 352 -736 256 WIRE -736 352 -976 352 WIRE -496 352 -496 256 WIRE -496 352 -736 352 WIRE -256 352 -256 256 WIRE -256 352 -496 352 WIRE -16 352 -16 256 WIRE -16 352 -256 352 WIRE 224 352 224 256 WIRE 224 352 -16 352 WIRE 464 352 464 256 WIRE 464 352 224 352 WIRE 704 352 704 256 WIRE 704 352 464 352 WIRE -1216 384 -1216 368 WIRE -1136 384 -1136 112 WIRE -1136 384 -1216 384 WIRE -1056 384 -1056 368 WIRE -1056 384 -1136 384 WIRE -864 384 -864 304 WIRE -624 384 -624 304 WIRE -624 384 -864 384 WIRE -384 384 -384 304 WIRE -384 384 -624 384 WIRE -144 384 -144 304 WIRE -144 384 -384 384 WIRE 96 384 96 304 WIRE 96 384 -144 384 WIRE 336 384 336 304 WIRE 336 384 96 384 WIRE 576 384 576 304 WIRE 576 384 336 384 WIRE 816 384 816 304 WIRE 816 384 576 384 WIRE 944 384 944 64 WIRE 944 384 816 384 WIRE -1216 432 -1216 384 FLAG -1216 432 0 SYMBOL voltage -1056 272 R0 WINDOW 3 24 104 Invisible 0 WINDOW 123 0 0 Left 0 WINDOW 39 0 0 Left 0 SYMATTR Value PULSE(0 5 0 1e-6 1e-6 .001 .002) SYMATTR InstName V1 SYMBOL Digital\\dflop -864 160 R0 SYMATTR InstName A5 SYMATTR SpiceLine Td=10n tripdt=10n trise=30n vhigh=5 SYMBOL Digital\\xor -976 -96 R180 WINDOW 3 16 112 Invisible 0 SYMATTR Value trise 10e-9 vhigh 5v SYMATTR InstName A14 SYMBOL Digital\\dflop -624 160 R0 SYMATTR InstName A1 SYMATTR SpiceLine Td=10n tripdt=10n trise=30n vhigh=5 SYMBOL Digital\\dflop -384 160 R0 SYMATTR InstName A2 SYMATTR SpiceLine Td=10n tripdt=10n trise=30n vhigh=5 SYMBOL Digital\\dflop -144 160 R0 SYMATTR InstName A3 SYMATTR SpiceLine Td=10n tripdt=10n trise=30n vhigh=5 SYMBOL Digital\\dflop 96 160 R0 SYMATTR InstName A6 SYMATTR SpiceLine Td=10n tripdt=10n trise=30n vhigh=5 SYMBOL Digital\\dflop 336 160 R0 SYMATTR InstName A7 SYMATTR SpiceLine Td=10n tripdt=10n trise=30n vhigh=5 SYMBOL Digital\\dflop 576 160 R0 SYMATTR InstName A8 SYMATTR SpiceLine Td=10n tripdt=10n trise=30n vhigh=5 SYMBOL Digital\\dflop 816 160 R0 SYMATTR InstName A9 SYMATTR SpiceLine Td=10n tripdt=10n trise=30n vhigh=5 SYMBOL Digital\\xor -528 -352 R180 WINDOW 3 16 112 Invisible 0 SYMATTR Value trise 10e-9 vhigh 5v SYMATTR InstName A4 SYMBOL Digital\\xor -368 -528 M0 WINDOW 3 16 112 Invisible 0 SYMATTR Value trise 10e-9 vhigh 5v SYMATTR InstName A10 SYMBOL Digital\\xor -368 -400 M0 WINDOW 3 16 112 Invisible 0 SYMATTR Value trise 10e-9 vhigh 5v SYMATTR InstName A11 SYMBOL Digital\\or 64 -128 R180 WINDOW 3 -8 128 Invisible 0 SYMATTR Value trise 10e-9 vhigh 5v SYMATTR InstName A12 SYMBOL Digital\\or -816 -208 M0 WINDOW 3 -8 128 Invisible 0 SYMATTR Value trise 10e-9 vhigh 5v SYMATTR InstName A13 SYMBOL voltage -1216 272 R0 WINDOW 123 0 0 Left 0 WINDOW 39 0 0 Left 0 WINDOW 3 24 104 Invisible 0 SYMATTR InstName V2 SYMATTR Value PULSE(5 0 1e-6) TEXT -1192 408 Left 0 !.tran 0 .512 0

Xilinx XAPP052 - Efficient Shift Registers, LFSR Counters, and Long Pseudo-Random Sequence Generators. Gives tables for LFSR generators from 3 to 168 bits in length.

--

Can you feed this from a PC somehow? Write a little Perl script (or VB if you must) that generates the appropriate length pseudo random string.

I'd like to see somebody hack into one of those radioactive smoke detectors, and use the radioactive decay, maybe XOR it into a PSRG.

Cheers! Rich

If you're going hiking alone, be sure to bring along a deck of cards.

That way, if you get lost, you can sit down, start to play solitaire, and someone will show up to help. ;-)

Cheers! Rich

It's just FFs and an XOR gate. It's pretty easy to translate to 74HC.

The problem is that "ugly" functions have a long history of being not as random as you would like.

You could use a ROM and some software to generate the contents. But I don't know any 74HC parts that are ROMs.

LFSR is best solution to Jim's problem that I know of.

Try a 74hc164 and a 74hc7266. Connect QF and QG to A input through one of the gates in the 7266. Apply clear and clock to 164. You should get a 127 bit PRBS.

Horowitz and Hill's "the Art of Electronics" only gives the data for minimal PRBS implementaions from 3 to 40 bit lengths, but does also list the taps required to get a PRBS from 8-, 16-, and 24-bit shift registers (which are easy to realise in 74 series logic).

-- Bill Sloman, Nijmegen

This circuit generates a maximal length 127-bit PRBS:

--- View in Courier:

A-----------+ +--Y HC86 | | B--------+ | A--+ | | +---Y HC86 | | | B--+ | | | | A-----+ | | | +--Y HC86 | | | | B--+ | | | | /| | | | | | +--O< |--------|--|--|--|-------------+ | | \| | | | | | A B +-----------|--|--|--|---[DIODE>]--+ | | | | | | Y | +--------|--|--|--|---[DIODE>]--+ | | | | | | | | | | | +-----|--|--|--|---[DIODE>]--+ | | | | | | | | | | | | | +--|--|--|--|---[DIODE>]--+ | | | | | | | | | | | | | | | +--|--|--|---[DIODE>]--+ | | | | | | | | | | | | | | | | +--|--|---[DIODE>]--+ | | | | | | | | | | | | | | | | | +--|---[DIODE>]--+ | | | | | | | | | | | | | | | | | | | Vcc [10k] | +-+--+--+--+--+--+--+--+--+ | | | | Q0 Q1 Q2 Q3 Q4 Q5 Q6 Q7 | [1M] GND +--|D1 ___| | +--|D2 HC164 CLR|O---+ | | | CLOCK>-----|> | [100nF] +-------------------------+ | GND

The diodes and the inverter make a 7 input NOR which keeps the thing from latching up, ever, and gives you all 256 states from 00 to ff.

--- JF