1. Home
  2. Electronics Design
  3. Random Bit Generator
  4. Page 4

Random Bit Generator

I was wondering what that was trying to do. My first guess was that it was breaking out of the stuck-at state, but I didn't take the time to verify that.

I would normally avoid that wide input gate by using the system reset signal.

LFSRs with a good polynomial go through 2^N-1 states. It's normally not worth the effort to try to get that one extra possible state. If you want more states, it's much simpler to use a slightly larger polynomial. Each extra FF adds 2^N more states.

If you really want all 2^N states, I think it takes 2 clouds of gates or one cloud with an extra FF. The first cloud of gates detects a particular state and forces it into the otherwise missing state. The second cloud detects the missing state and forces it into the state it would have gone to if you hadn't done anything fancy. You can trade that second cloud of gates for a FF that remembers that the previous step was the special case.

Again, if you want more states, it's much simpler to use a bigger LFSR.

--
These are my opinions, not necessarily my employer's.  I hate spam.
Reply to
Hal Murray
Loading thread data ...

One CANNOT compute (or generate from logic) a truly random number. Now, quasi-random number generators are a dime a dozen, like you imply.

Reply to
Robert Baer

Those aren't very random. He keeps saying the same stuff, over and over.

John

Reply to
John Larkin

If you XOR enough of them, the typos add up into a random mess. :)

--
Politicians should only get paid if the budget is balanced, and there is
enough left over to pay them.
Reply to
Michael A. Terrell

y

Even more off the wall if you throw in Mike Terrell's imagined "facts" about my life.

-- Bill Sloman, Nijmegen

Reply to
Bill Sloman

Not exactly true. John Larkin does find a wide variety of different ways to get things wrong.

Today's special was his posting the URL a two-page version of Fairchild's eleven-page datasheet for the FSA3157

formatting link

I certainly didn't expect that.

-- Bill Sloman, Nijmegen

Reply to
Bill Sloman

Sure you can. Just make a long enough daisy chain of logic gates and compute a logic function from the input and the output of the chain. Now apply a clock to the input. As pulse propagates through the chain, the RMS jitter will add up and the output of the function will be truly random. Ring Oscillators are the other example, but they are asynchronous.

Oh, I forgot to mention the whole class of PRNGs where one counter acts as a source of the clock for the other counter. That is simple and allows generation of the variety of random looking sequencies.

Vladimir Vassilevsky DSP and Mixed Signal Design Consultant

formatting link

Reply to
Vladimir Vassilevsky

There are lots of digital chips, including some Intel processors, that have cryptographic-grade random number generators on-chip. One common technique is to use a bunch of asynchronous ring oscillators to scramble pseudo-random shift registers. Lots of references on the web.

I have a technique that uses an i/o pin as a noisy/chaotic RC ramp generator. Fun, but essentially useless.

John

Reply to
John Larkin

Good point.

John

Reply to
John Larkin

One of the main features of the cryptography grade RNG is the self test subsystem that continuously monitors that 1) RNG is in the good health

2) RNG had not been tampered with. If there is no such subsystem, the RNG is consumer or amateur grade, not cryptography grade.

Just to remember that a deterministic function over the random number don't add to the randomness. So the output hash should not generate more of the scrambled bits then the true entropy of the random source.

I used to measure the timing of self charge/discharge of the uncommited MCU input to set up the seed for the PRNG for the rolling code.

Vladimir Vassilevsky DSP and Mixed Signal Design Consultant

formatting link

Reply to
Vladimir Vassilevsky

I went to the web site, went to the analog switches table, found a part, clicked "datasheet." What I got was the official Fairchild 2010 data sheet, from the Fairchild web site. Well, one of the official datasheets.

I note that you got your datasheet from a non-Fairchild web site, and it's the 2003 version. So Fairchild deliberately stripped the data sheet.

Fairchild seems to have multiple 3157 datasheets on their own web site, and the links from various places to various datasheets are tangled and sometimes wrong.

Sloppy work, Bill, on their part and on yours.

And why are the chips with stunning, industry-best by 10:1 charge injections, obsolete?

They do make some nice silicon. This little critter switches like crazy:

formatting link

Of course, the datasheet has no dimensions, and the package has multiple names, so one can spend a little time, as we did on Friday, trying to figure that out.

John

Reply to
John Larkin

Post-hashing can remove any 1/0 (DC) bias and remove other autocorrelations as a physical source tends to have. Do all that a dozen times, as you can in an FPGA, and things get pretty good.

Things are more interesting if you XOR *into* a pseudo-random shift register, instead of merely with the output of one.

Similar idea, but I would keep using it. Hanging a cap on the pin helps. If the discharge time is short and is itself a function of random values, the combination of discharge time feedback, threshold uncertainty, dielectric absorption, and cap TC (use a really bad cap) add to the fun.

John

Reply to
John Larkin

Yes, the post processing obfuscates the obvious dependencies, but it can't generate more of the entropy then the entropy of the source.

Again, you can't make more randomness by mixing random states with deterministic states. Although this procedure adds some "salt" to the common PRNG.

VLV

Reply to
Vladimir Vassilevsky

I wouldn't be so sure about deliberately. Never attribute to malice what can be explained by stupidity, or something close to that.

--
These are my opinions, not necessarily my employer's.  I hate spam.
Reply to
Hal Murray

Hal,

Point of curiosity: Why do you strip out references?

I have no idea who said, "...Fairchild deliberately stripped...".

You're also killing "Newsgroups:", so I have to fill that back in on replies.

You do that all the time.

If deliberate, why are you doing that?

Or is it a bad newsreader client? ...Jim Thompson

--
| James E.Thompson, CTO                            |    mens     |
| Analog Innovations, Inc.                         |     et      |
| Analog/Mixed-Signal ASIC's and Discrete Systems  |    manus    |
| Phoenix, Arizona  85048    Skype: Contacts Only  |             |
| Voice:(480)460-2350  Fax: Available upon request |  Brass Rat  |
| E-mail Icon at http://www.analog-innovations.com |    1962     |

               I can see November from my house :-)
Reply to
Jim Thompson

The preferred method of guaranteeing ranDUMB bits, is make like a witch and HEX-or them...

Reply to
Robert Baer

Nope! An infinite number of gates has yet to be made. One of the attributes of a large set of truly random numbers is the fact that ANY sequence can be repeated, again and again - but not for an infinite period.

Reply to
Robert Baer

Ahh..you agree with me.."scramble pseudo-random shift registers".

------------------------------------^^^^^^

Reply to
Robert Baer

Relay pullin time and bounce would make a nice randomizer, too.

Unclocked ring oscillators are not deterministic. They will drift all over the place with time, temperature, tiny Vcc variations, thermal noise, and EMI from other sources. CMOS oscillators have ghastly phase noise.

The external RC thing can be made truly random, too.

Random, in this context, means that future states can't be predicted, even given total knowledge of the hardware and the current state. Which means that bad guys can never decode the pattern.

John

Reply to
John Larkin 

--
If a neverending sequence is truly random, then the possibility exists
that it can repeat forever.
Reply to
John Fields

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.