[Entry] Random Number Generator

[Entry] Random Number Generator

Postby NiHaoMike » Thu Oct 11, 2012 8:22 pm

Generating truly random numbers using a purely digital circuit is not possible - after all, digital logic is supposed to give the same results given the same input! This circuit cheats a little - a 4049 is used in an analog manner, amplifying and digitizing diode noise. Due to imperfections, the output will be "colored", that is, it will have slightly more 0s than 1s or vice versa, enough to cause it to fail being truly random. To solve that, the output is sent through a LFSR to debias it. It is then gated by a counter and two flip flops to frame the data for sending over a serial line. Two outputs of the prescaler counter are used to drive a charge pump in order to obtain enough voltage to get a diode-connected transistor to generate noise.
http://i50.tinypic.com/2jdkxoo.jpg
http://i47.tinypic.com/1j6hsk.png
Image
NiHaoMike
Newbie
Newbie
 
Posts: 26
Joined: Sun Sep 30, 2012 12:12 am

Re: [Entry] Random Number Generator

Postby ian » Fri Oct 12, 2012 8:19 am

Nice work, thanks for submitting!
User avatar
ian
Crew
Crew
 
Posts: 10577
Joined: Mon Jul 06, 2009 6:14 am

Re: [Entry] Random Number Generator

Postby mwilson » Tue Oct 23, 2012 9:21 am

A common way to remove bias is to read successive pairs of output bits until they differ, then take one -- either always the first or always the second. It has the sad effect of cutting the data rate to slightly under one-quarter (depending on the degree of bias), but it provably removes the bias.
mwilson
Newbie
Newbie
 
Posts: 22
Joined: Thu Jun 16, 2011 9:31 am
Location: Toronto, Canada

Re: [Entry] Random Number Generator

Postby t0mpr1c3 » Tue Oct 23, 2012 1:12 pm

That technique is known as the von Neumann extractor and relies on the absence of autocorrelation, which I would not think is guaranteed in this case.
Magic Smoke projects
Tindie store
User avatar
t0mpr1c3
Full Member
Full Member
 
Posts: 200
Joined: Mon Sep 17, 2012 4:51 am


Return to Open 7400 Competition