This is way off topic, but since you mentioned cryptography and random numbers I think it might be possible to build an unbreakable encryption sheme based on Bell's theorum.

The short story is that if you generate two simultaneous photons from the same source they will have the same phase at a later time regardless of the paths traveled.  The phase of a photon can be rendered completely random by repeated scattering events.

Here's the encryption scheme:

A central source generates two phase-entangled photons and sends one to each of our computers down their respective optical cables. The phase of the photons are randomized by scattering in the cable, but are measured to be the same by ploarizers at the point where the photons reach our computers.

We use the phase of the photon as an encryption key.

This effectively creates 2 identical private keys for RSA encryption without the need of a public key, and nothing, not even the source that generated the photons, could predict what the phase would be at the time of measurement.

Another way to captialize on ground bounce noise in the threshold,  is an RCTIME command, where the capacitor and resistor are purposely poor, and the wiring to the ground connection loops around to form a good (bad!) ground loop, calculated to pick up a lot of AC,  processor emi, and the local radio station.    For a long RCTIME that approaches the threshold asymtotically, the slop in the least significant bits can be a random seed.

Hi Tracy,
That sounds like it might be a better idea then what I am doing since it uses only one pin and doesn't require elaborate timing.

The unfortunate thing about both methods is that you have to waste a a lot of time waiting for the signal level to be near the logical voltage threshold and then only get a few random bits.

What if we set an input pin for CMOS level and then piped in Vdd/2 from a voltage divider?
I suppose it would be a little over or under Vdd/2 because of the resistor tolerances, but it may be close enough.
Maybe adding a bit of ringing from something like a ground bounce or coupling unlike inductors in series would mess the signal up enough that we could read random bits at will.

Yes, it should be possible to bias the input near the threshold.   Remember, there is a sharp peak in current consumption by the SX chip when the pin passes within 0.1 volt of the threshold, so it would be a good idea to have means to force it to an output when it is not being used for noise.  Hi resistances.  The nice thing about the capacitor is that is assure that the system passes through the threshold.  Maybe a combination scheme where the capacitor is connected to a V divider that puts the initial voltage near the treshold to save time.

Another idea would be to hook up the comarator with direct positive feedback from the output to (+), and with (-) at V//2.   The propagation delay in the comparator makes it oscillate with lots of jitter at around 40 mhz.  In any case, sampling the comparator output would be a pretty fair crap shoot.

I tried sampling the comparator by itself with nothing attached to the pins but it just chose one pin as the high one and stuck with it.

I will try feeding in the input from a voltage divider when I get home.

As far as pushing the pin off the threshold when it's not in use for noise detection,  a transistor could control the voltage into the noisemaker so it can be turned off when not in use.

I got home after midnight tonight, but had to try it.

With the comparator hooked up to nothing it actually generates pretty random bits, but it seems to favor 0 a little over 1.

I have the port A registers attached to 4 diodes and am sampling the comparator output with the following code:

GetNumber sb rb.0
jmp BlueGreen
jmp RedYellow
BlueGreen
sb rb.0
jmp Blue
jmp Green
RedYellow
sb rb.0
jmp Red
jmp Yellow
Blue
mov LIT, #%0001
ret
Red
mov LIT, #%0010
ret
Green
mov LIT, #%0100
ret
Yellow
mov LIT, #%1000
ret
After returning it moves the value in LIT to ra and lights whatever diode corresponds to the bit that is set.

The favoritism of zero over one manifests itself as the blue diode being lit a little bit more than the others.

Grounding one of the two comparator inputs will consistently cause it to choose the other input as high.

Now here's the odd part:

When I momentarily tap Vdd to pin rb.2 (through a resistor) it correctly lights the yellow diode, but then it stays lit for about 24 seconds before returning to semi-randomness. This is at 4Mhz with the SX key detached.
It takes longer for slower clock speeds out to around 38 seconds at 32kHz.

If I tap rb.2 with Vdd/2, it stays lit for about half the time before rb.0 starts flickering again.

Just in case you thought this couldn't get any more bizzarre, when I tap rb.3 with Vdd/2 the comparator output goes to zero and stays there indefinitely.

I have attached the rest of the code.
The circuit is nothing more than an SX18AC/75 powered by an L7805 and Guenther's recommended capacitance circuit (without the back EMF protection diodes). There is also a programming header and 4 diodes hooked up to the ra register. with a 570 ohm resistor on the ground side to keep them from frying. The voltage divider is constructed from 2 4.7k resistors, and there is a 10k resistor plugged into Vdd.

-Electronegativity signing off.

[Quoting: "Electronegativity"]
 
With the comparator hooked up to nothing it actually generates pretty random bits, but it seems to favor 0 a little over 1.

I'm not clear to me on how the pins were connected for the test you described.  Was at least one of the inputs floating, not connected to anything?  
The comparator can be made into a high frequency oscillator, by connecting a wire from RB0 to RB1, and by connecting RB2 to a medium voltage.  That could be ~Vdd/2 from a potentiometer between Vdd and Vss.  The oscillator frequency is determined by the comparator propagation delay. It has lots of jitter and probably 1/f noise and temperature dependence too.    It would be like having a madman sitting there pushing a button. The program could sample that occasionally to get  random bits or to spice up a psuedo random sequence.  
I looked back at some old notes, reported in this thread,
http://forums.parallax.com/forums/default.aspx?f=7&m=58271
and the period of the oscillation was around 40 nanoseconds on a 5 volt supply, an oscillation frequency of around 25 megahertz.  The period is determined by the two propagation delays, how long it stays in the "1" state vs how long in the "0" state.  
-- The ratio of high to low  is affected by the threshold applied to RB2 and becomes highly asymmetric if the potentiometer takes the rb2 threshold near Vss or Vdd. One way to equalize 1s and 0s would be to feed the oscillator output into the RTCC and sample the /2 bit of that.   Or there may be some way to equalize in software like Paul suggested.

-- A program sampling at anywhere near the 40nS period could run into serious aliasing problems.  But for occasional samples (at  more than 10 microsecond apart, say), the statistical correlation should drop practically to zero.

Another way to use the comparator, instead of a direct wire connection from rb0 to rb1, would be a high value resistor (~1M) there.   That more gentle negative feedback should bias the comparator as an op amp without the oscillation.  Couple in an intrinsic or external noise source, and it would be amplified up  to digital level for sampling.

Hi, first a correction: rb.3 should be rb.1 in the post above.

Paul, that is a reasonable suggestion but it would make it difficult to port the code from one chip to the next since I suspect that each chip would require a slightly different transform, and even within a given chip the local temperature and electromagnetic environments could affect the weighting towards 1 or 0.

Tracy, there is nothing connected to any of the comparator pins. rb.1 and rb.2 are initialized as inputs and set low.
rb.0 is initialized as an output, set low, and is configured to output the comparator value.

I will try your oscillating comparator trick when I get home.

Does anyone have a clue why the strange behavior I described at the end of my last post occurs?

Report from last night:

Tracy's "Madman circuit proved more random than leaving the comparator pins open, and seened to improve a bit further by using a lower voltage on pin rb.2, but showed a slight favoritism of 1 over zero.

This could probably be cleaned up nicely by Paul's binomial stochastic transform.

Whenever the device resets it could run a calibration cycle where it samples a large number of bits and determines the proper number of high or low results to throw away.

If using up 3 valuable pins on port B is a problem then the madman circuit can be connected or disconnected by a transistor that is actuated from one of the port A pins.

The symmetry wrt 0 and 1 could be improved by connecting rb.0 comparator output to the rtcc input configured as a counter (no prescaler), and sample the /2 bit of rtcc.   The divide by two (~12 megahertz) would render it symmetric (equal probability of 0 and 1 without math tricks).  Assuming you don't need rtcc for something else!!

Sampling it rapidly would lead to aliasing with the processor clock.   The longer the program waits between sample bits, the less the correlation between them.

I ordered a few inductors, and when they come I am going to add an asymmetric coupled LC circuit in the hopes that the added complexity will lead to true chaos.

Even as it is it's good enough to generate a sufficently random seed values.

One could easily imagine a Psuedo-random generator that used 3 or 4 variables that were all randomly seeded.

Good enough for game purposes, but maybe not aerospace engineering  :smilewinkgrin:

Ok, I know I'm beating this topic to death, but I have one more thing to say.

There is a simple way to avoid having to normalize the data for a process that favors either zero or one.

You collect 2 bits in a row.
If they are both positive or both negative you throw them out and collect 2 more bits.
If the first one is negative and the second positive then the result is zero.
If the first one is positive and the second one is negative then the result is one.
I think this will yield random bits even for a semi random system that is more likely on the average to be high or low.

Ive heard of that algorithm, I think random.org talks about it.

Hi Paul.

Yes, that is true, and I realized it when I came up with the algorithm, but I think it works if you poll at a rate which is slower than and asynchronous to the rate at which the bits are generated.
Tracey estimated that the comparator would oscillate at ~40 Mhz. I am clocking the SX at 32kHz and not even sampling every cycle.

The logic is as follows:

Imagine a source that generates more zeros than ones.
This could happen if the crossover point of a sinusoidal voltage is lower than the logical transition voltage.
In this case the sine wave would spend most of its time below the transition threshold and only occasionally peep above into the region corresponding to a one.

If you sample a source like the one above at a rate which is slower than and asynchronous to the period of the sine wave you would get a lot of zeros and a smattering of randomly distributed ones.

Applying the "two-bit" algorithm to a case in which nine times as many zeros as ones are randomly generated would have the following effect.

81% of the time you would get two zeros in a row and discard the result.
1% of the time you woulg get 2 ones in a row and discard the result.
9% of the time you would get first a zero then a one  (90% X 10%)  = 0.
9% of the time you would get first a one then a zero (10% X 90%)   = 1.

I have it up and running on a breadboard at home and at least to my eye it appears perfectly random.

Electronegativity,
You mention that you have it wired up and running, and it appears random to your eye.  Well, take your eye out of the loop and let a computer tell you if you have a random number generator or not.  On your testbed, add some RS-232 code (and whatever level shifting hardware you need) and have your testbed send the values from the random number generator to your PC.  On the PC side, write a small program to receive the numbers from the SX and create a histogram from them.  
The program is pretty much dead simple - for each number that comes in, use it as an index into an array of 32 bit integers which you increment.  Run the program for some finite length of time.  For example, try running the program for a minute, ten minutes, and an hour.  Better yet, use the data rate to calculate a number of samples that takes close to those times to collect, but which is evenly divisible by 256.

At the end of each run, have the program write out a simple comma or tab delimited text file of the final value of each entry in the array.  You can now open that text file into Excel and do things like graph it, or calculate the min, max, and mean values, etc, etc.  Since you have collected a number of samples evenly divisible by 256, you should have (theoretically) the same value in each of your PC's array entries.  If not, you can see which way you are weighted.

[list]Thanks,
PeterM[/list]
PS - I did something similar to this to verify that the pseudo-random number generators on SxList.com provided an even distribution.

You know, the pseudo-random routines on sxlist ( at http://www.sxlist.com/techref/ubicom/lib/math/rand_sx.htm ) really do work pretty darn well and don't require any io pins...

Electro,
I was recalling fuzzily.  The comparator with direct feedback oscillates with a period of about 40 microseconds, a frequency of around 25 megahertz.  What do you plan to do with the inductors to make it more chaotic?  
Donald Knuth's volume, "Seminumerical Algorithms", goes into great depth on different random number generators and statistical tests that they should pass.   The  introductory lesson that sticks in my mind is, paraphrased, " never choose a random number algorithm randomly".

PJ, I intend to use this to create a table of random color sequences for a tiny hand-held Simon Sez game.
As long as the user cannot perceive any divergence from randomness it is good enough.

James, even if the Pseudo-random code is perfect I still need to generate a random seed or the colors will always be the same. I know I could have the user press a button and read a seed value of the RTCC, but I want them to be able to start a new game by pressing only a single reset button instead of having to reset and then press a second button.

Tracey, my plan was to randomly choose a random number generator.  :tongue:
I figured that by slapping enough mismatched inductors and capacitors together I could build something completely chaotic.

I don't think I will need to do that though, since your oscillating capacitor idea can be implemented here in a very simple way.

I can bridge rb.0 and rb.1 with the emitter and collector of a transistor. The base is hooked up to ra.3.
Rb.0 and rb.1 are also hooked up to blue diodes, while rb.2 is attached to a red diode. When ra.3 turns on the transistor it sets up the oscillation of the comparator.

The "marginal voltage" on rb.2 is supplied by the fact that there is a higher forward voltage drop accross the blue diodes than the red. Once the table of random numbers is generated, I drop the voltage on ra.3 which disconnects the bridge. In this way I can use your method without using up any pins at all since ra.3 is subsequently set as an input and used to read a button.

I may be wrong on this, but I'm pretty darn sure you can just read the RTCC after you get started up. The startup time is NEVER going to be exactly the same after each startup. Minor changes in supply voltage will guarrenty that the chip will have a different value in RTCC every time.

Try it?

Electronegativity,
I figured that since you wanted a true random number generator, you needed to be sure it was truly random.  Since you're just making a game, any old psuedo-random number generator will be more than adequate.  You're killing yourself with all this extra effort.

James' suggestion will work fine, but can be made even better.  Run a pseudo-random number generator in the RTCC.  Assuming a reasonably fast interrupt rate, you will be generating hundreds or thousands of random numbers per second.  Whenever the user presses a button to start a new game, there's basically no way they will ever be accurate enough to predictably get the same random seed each time.  I used this exact technique on a project and it works great.

I agree with others that a psuedo random generator seeded from RTCC would be adequate for your game application.

I was pursuing the comparator idea as a curiousity.   Pursuing it a little further, I don't understand the need for the transistor. I was trying to minimize the amount of external parts required down to basically two resistors.  Why not just turn the comparator on and off via the comparator mode bits, CMP_B?  You could even use it then for other i/o.

Hi Tracy, I have each of the port b registers hooked up to a diode, and each of the port a registers hooked up to a switch.

There are 2 blue diodes on top, 2 red on the right, 2 green on the bottom, and 2 yellow on the left.
I plan to have the game produce little light shows to celebrate the players progress every time the length of the memorized sequence increases by 4 colors.

Since it is an SX20 there are no more I/O pins available.
If I bridge the rb.0 and rb.1 pins then I will not be able to light the 2 blue diodes independently, so the transistor is there to let me open or close the bridge.

PJ, I like the idea of running the Psuedo-random generator in the RTCC.
If I understand you correctly the output of the generator is input into the RTCC and incremented some number of times before being pulled out to use as a new seed. This seems like it would take care of the problem that a psuedo-random generator always produces the same series of numbers from a given initial value.

James, I always assumed that the RTCC starts at zero and increments along with the program counter.

Is this wrong?

If I ran the following program:

RESET Start
Start nop
nop
nop
Wouldn't the RTCC hold a value of 3?

Electronegativity,
Actually, what I do is run the random number generator in the RTCC interrupt itself.  I store the result (an 8 bit number) in a variable.  Since the RTCC is running at a (presumably) fast rate, the pseudo-random sequence is being run through hundreds or thousands of times a second.  Given that there is no way to predict when the human will push the button to start the game, and also given that no human is going to be accurate enough to push the button the exact same time after starting the device, there is essentially zero chance for the same random number to appear.

Furthermore, your code could test the condition of the button at start up and not accept the button as being pushed until it has at least seen it not pushed once in the primary loop.  This would prevent the user from holding the new game button down at startup.  
In addition, the whole time your game is being played, the RTCC is still running and the pseudo-random number generator is still cranking out new values on each interrupt.  Because of this, even if the user were able to somehow get the unit to give the same game each time they started it up, they would never be able to get the same second game unless they took the exact same amount of time to play the game and hit the "New Game" button.

Basically, imagine a roulette wheel behind a curtain.  It's turning at high speed and someone is watching it.  Periodically, someone in front of the curtain asks what number the wheel is at, and the person in back notes the number and passes it to the front.  This is what is happening by simpy having the pseudo random number generator running on each interrupt all the time.  Periodically, the user will push the "New Game" button and the foreground code will look at the variable with the current random number, but there is zero correlation between the current state of the generator and the time the user pushes the button, hence the human variable guarantees a truly random number generator since they themselves are the true random element.