How to develop a random number generation device

That gets into the philosophical issue: should we attempt to detect and correct for transient hardware errors in digital systems? That can apply to config bits in FPGAs (do we check them on a regular basis?), registers in uPs (including PC, SP, etc), values in counters, whatever.

We generally assume that if it's broke, it's broke.

John

I generally do. Check or refresh (sometimes checking has side effects or refreshing has side effects, unfortunately).

If power cycling doesn't happen regularly or cheaply then a flipped bit can have almost the same cost as a hardware failure. Since soft errors are more common than hardware problems, IME, why not try to increase the reliabilty of your product? Of course for bench instruments or if there's a power switch within easy reach, it's not so important, but consider a microcontroller-based signal conditioner sitting out in an inaccessible area of a large plant and powered 24/7 for years and years. For space stuff there's generally a way of recovering from that sort of thing, which is good because single event upsets are more likely in that enviroment.

Best regards, Spehro Pefhany

It follows that the 0 0 0 0 0 0 0 0 sequence isn't a lock-up state for your generator. Presumably, one or more of of your XORs is actually an XNOR and the actual lock-up state is something different.

-- Bill Sloman, Nijmegen

In most of our recent products, the big heap of dynamic bits are FPGA config bits, sometimes 5 million per chip [1]. They are also, probably, the worst as regards being flipped by neutrons or whatever. And we can't read them back to see if they're OK, and we can't afford to regularly reset the FPGAs and reprogram them.

John

What's wrong with using the regular XOR feedback but simply invert the output? Surely that eliminates the possibility of lockups (allowing all zero state) and uses just one extra NOT gate:

_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ .--|>o--|_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _| | | | | | '------------------------X---X-----X---'

Then all 1's is the lockup state.

John

I agree. I've built pseudo-random noise generators from basic parts (I used chips but today a FPLA would be the thing) and they work. But assuming the "research" doesn't require true random numbers there are chips out there that already do the job and are quite optimized within their parameters.

Of course if you DO need random numbers then things get quit a bit more sticky. In that case you first need a truly random source. Candidates are atomic decay (geiger counters or other detectors of radioactivity), noise diodes (there are chips that do this) or natural noice (the sound between stations) or at very low frequencies one can simply use a keystroke recording a system clock as a randomizer. The problem with all these methods is you MUST check the system output statistics for true randomness. Often things that appear random are not. (a pseudo random noise generator for example) Testing for true randomness is not as simple as you might think!

On Sat, 08 Sep 2007 08:08:10 -0500, John Fields wrote:

--- Aarghhh!!!

_Here's_ the corrected circuit list:

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

-- JF

And my point is that it shouldn't "accidentally" get into a broken state, any more than the program counter of a CPU should accidentally find itself in never-never land.

If a digital system is unreliable, the cause should be found and fixed. The problem with kluges like this is the same problem with watchdog timers: they hide the real problem, so keep it from getting fixed.

I always turn off the watchdog timer on test units, and protos delivered to customers. I only enable it after we're sure we don't need it.

John

The Xilinx app note says that using the all 1's lockup state is recommended, (i.e., XNOR) because the flip-flops' default powerup state is 0, which is in the sequence, so it doesn't lock up by default. ;-)

Cheers! Rich

Shift registers are very cheap in Xilinx chips (you can use the cell config bits) so you can make huge sequences. And you can initialize any shift register to any pattern, so an xor or xnor is equally safe, as long as you init it to something random-ish.

We just did an FPGA that contains eight channels of Gaussian noise generator. Each channel uses, as I recall, eight *long* shift registers of different sequence lengths, with a 16 bit random number manufactured by scrambling bits from various registers. Every shift register is initialized to something different. Clocked at 128 MHz, no channel will repeat a pattern in the life of the universe.

The 16-bit random words are digitally lowpass filtered to produce a nearly-Gaussian probability distrib and programmable -3 dB point, from mHz to 2 MHz.

John

Watch dogs don't always recover the system from a glitch. If you are storing data in battery back RAM or flash, you need to be sure that wrong values don't cause things to hang in some non-recoverable way.

For that matter it is not actually possible. Any string of bits no matter how long may just be part of a longer repeated string. You have to assume things about what the circuit is doing to be able really test for it being random. This is where you can get into serious trouble because what you assume my blind you to a problem with a random generator.

The odds of getting 10 zeros in a row vs the odds of 100 zeros and etc depends on the low frequency content of the noise. Ac coupling in the circuit messes with this.

I have seen engineers get into trouble that would have been avoided had they only followed the above advice.

Another problem-hider is filling unused ROM with jumps to the reset vector. I only do that on the production units; for the prototype (and sometimes for the pilot run) I like to fill unused ROM with stop instructions.

A technique that I sometimes use when designing toys is to have the button / switch that tells the toy to start moving and making noise cause a hardware reset, and the timeout at the end of play that tells the toy to stop moving and conserve power to invoke the deepest available sleep mode -- usually with the clock stopped entirely -- to be woken up by the next hardware reset. In industrial control applications you sometimes see the same sort of thing but with a counter causing the resets to occur every N seconds. This techniques isn't always applicable (check to see how fast the oscillator can come up, for example; some are annoyingly slow) but in some limited cases it works well.

On Sep 9, 8:56 am, Guy Macon wrote: [....]

On the 8051 an erased cell is a worthless instruction that will let the PC count off the end of code space and back in at 0000H. This has the same effect.

I sometimes put a break point at 0FFFFH and run the code just to make sure it doesn't happen.

An external watchdog to force the hardware into a safe state is a very useful thing for making faults less costly. Here's an example of something I have suggested humorously but would never in fact implement:

Micros today commonly have an ADC so they can measure their own supply voltage if the supply is not the reference for the ADC.

A very low parts count bucker regulator could be made if the micro measured its supply voltage and turned off the pass transistor if the voltage was more than the set point. The hardware would have to default to turning the pass transistor on so that the system starts up.

Some things have to run continuously, with microsecond response to inputs, so can't be periodically reset. Most of my products have long startup times, too, as long a 5 seconds, so a true system reset is pretty traumatic.

The reliability of a good digital system should be dominated by classic hardware MTBF, not by bugs or glitches. It should have *no* bugs or glitches.

John