This is rather interesting, and you do appear to be having great time playing with them. This morning caught me a bit by surprise, you see I had a rather sleepless night and gave in to the sleep gremlins, raising at 4:55AM I took my morning meds (includes a narcotic) and had my bowl of cereal, put on the coffee, and sat down in my recliner, turned on my laptop and the side notification deal popped up with your new video. Of course in my nummed, sleep deprived state of mind, I saw LEFSA, Well the scene of you rolling out Lefsa and cooking in on your Lefsa cooker! For the uninitiated in Scandinavian cooking, Lefsa is a sort of tortilla made with potato's, eaten with butter and brown sugar or jelly rolled up inside. Wonderful Christmas fare in the Dakota's where many from Northern Europe settled.
It is called pseudo random for a reason. It is not really random. To improve the appearance of randomness you need to seed the register with a number from some random input like white noise from a radio not tuned to a station or something like that.
Better yet, seed it at intervals. LNFRs are good ways to turn a low-bitrate, high-entropy stream from a hardware RNG (like a white noise receiver) into a very high bitrate, high-enough-entropy-for-practical-use stream. If you only seed the initial value then you are half-way to inventing the stream cypher.
Peter D Morrison yes it will but if the sequence is long enough starting it at a different point will make it appear more random. Appear not actually be truly random.
They may appear to be random when running, but in practice they are completely predictable. Given sufficient computing power they can be cracked, particularly if you know anything about the feedback settings. Note that, in order to get maximum length you must include the last bit in the feedback, the one on the right in Julian's videos. Anything less and you are just shifting the sequence out through a shift register that has no effect on the input. I believe they are still used as encryption devices. Alice and Bob agree on a common starting setting of, say, 41 bits then as long as they stay in sync, x-oring the message with the pseudo-random bit-stream will encode it and decoding is just the same process of x-orwith the same bit-stream since double xor gets you back to where you started. This would be useful if you only wanted your message to remain secret for a short time. "bomb goes off in 5 minutes" would be OK, but "meet me in 3 weeks time on Hampstead Heath" will probably be a very crowded meeting! I thought that they were no longer used in serious cryptography, but if you go on Amazon and search for "Shift Register Sequences" in books you will get quite a few hits. Unfortunately all the books seem extremely expensive, none less than £42. Back in the 70's when I was using LFSRs I had a book of that name, but today I couldn't find it. It still may be around. In order to get the shift register to start at the pattern you want, you obviously have to be able to force all the bits to a given state. Similarly, if you want to use it as a counter, you need to detect state N (Sn) and use this to reset the register back to state 1 (S1). Neither of these states needs be a single 1, they just need to satisfy the requirement of being N apart.
The phenomenon of patterns with few ones not looking very random happens in a big way with the Mersenne Twister PRNG. If you start it in a state that's mostly zeroes, it takes thousands of cycles before it starts producing decently distributed outputs. Typically one uses another small PRNG to seed it.
I think a great follow up would be to make an avalanche RNG and put it in front of your 40 bit shift register. Maybe look at with nd without a Von Neumann filter.
I know that pattern! I'd recognise it anywhere. Do you realise you've designed a circuit to draw a Sierpinski triangle? The more bits in your register, the longer it'll carry on generating that Sierpinski triangle pattern - until it runs out of bits and starts generating pseudorandom goodness.
Try breaking it up into 40-bit lengths and putting them one above the other. What naturally emerges is the odd/even shaded form of the Pascal triangle - which is not at all surprising, as that triangle is constructed by each line taking the XOR of adjacent elements of the line above. The odd/even pascal triangle is in turn an approximation of the Sierpinski triangle.
Yeah I think it's related - several mentions in stephen wolframs book on cellular automata www.wolframscience.com/nks/notes-7-5--random-number-generators/ second half of the page
There are interesting similarities here to Conways game of life, the patterns even appear similar. Not surprising I suppose as they both use XOR to generate the next state based on the current state.
Worth pointing out that the stages of "building the pattern up" are just a part of the "main" pattern anyway. In other words the series of states with a single bit plus all subsequent states will re-occur after 2^41-1 steps. Put another way, if you started with a random set of bits on and off, then the series with just a single bit will turn up naturally some time between the start and 2^41 steps later. It will also be preceded by an interesting non-random sequence running down from lots of bits to just the single being on.
Just repeating what I said on the earlier video, you can get a near-enough-to-random number from a scientific calculator by entering a decimal point followed by some random digits, then taking the natural antilogarithm followed by the reciprocal. You will get a decimal number which, unless you're a mathematical savant or you've cheated, will be effectively random. I notice some people have compared the output to The Game Of Life. In case anyone doesn't know The Game Of Life, it's a game where you use a grid of dots, where each dot can be lit (alive) or unlit (dead). Each generation, you check how many "living" (lit) neighbours the pixel has. If it has less than 2 living neighbours, it dies of loneliness for the next generation. If it has 2 living neighbours, it remains unchanged in the next generation. If it has 3 living neighbours, it is alive in the next generation. Any more than 3 living neighbours and it dies of overcrowding for the next generation.
I figured out last video at 1Hz it would take almost 70000 years before it would start to repeat, and at about 1MHz it would take a little over 25 days before it would start the pattern again, so at 2MHz, I am guessing about 12.5 days? A shockingly long time considering how fast its running. Even at 1GHz, its going to be longer then a half hour. Although it helps put into perspective the amount of 1's and 0's a computer can wrangle.
coincidently today I learnt LFSRs produced the space invaders explosion according to Grant Searle's awesome website. Its 3 ganged '374's for me first chance I get.
Could you connect the shift register outputs to a DAC, hook the analog signal up to an oscilloscope (or a speaker trough an amplifier), increase the clock frquenzy and study what happens? Maybe not all 40 bits, but it would be interesting to see.
It would sound similar to white noise. This is how noise is generated in some synthesizers such as the EDP Wasp which uses a 4006 (18 bits) clocked at about 25kHz.
You can connect any of the outputs of the exact circuit Julian was using to a volume potentiometer (5V is a bit too loud) and into an amp if you want. At fast clock speeds it will sound like "shhhhhhhh". If you change the taps to something that only gives you a much shorter sequence you will get different sounds very similar to Atari 2600 background whooshes and thruster noises especially if you sweep the speed of the clock up and down. It always reminds me of Haunted House, Dragster and stuff like that .
So, by that assertion, is 'driving too fast' constantly accelerating? Not necessarily; you could also be decelerating, or experiencing no horizontal acceleration at all.
I can't stop wondering if this could produce (almost real) pseudo random numbers; well maybe an almost random seed for a pseudo random number generator. Now if this thing was started at the same time as the cpu, but at a different frequency to the cpu wouldn't the probability of this thing producing the same pattern at the execution of the code seeding the RNG be rather on the low side? Or have I got this whole "project" A over T? I couldn't stop giggling at the little strips of paper, BUT they did illustrate the process perfectly. Thank you, Julian.
I don't think seeding one prng from another actually makes the output any 'more random' Some uc's implement true RNG - according to STMs application note AN4230 they're using our other good friend... the ring oscillator to do it.
Michael Keegan , different freq doesn't matter, 'cos the LFSR will still have run for a known consistent period of time when the CPU reaches the code instruction to read the LFSR's value.
The finger means nothing in the U.K. Two fingers is the equivalent. In Australia, the hitch-hiker's thumb is bad; you use one finger to flag a lift. It's a convoluted world.
To be as bright as you, all that knowledge i wish i had. Its going to take me quite some time to catch up. Thanks again for anothet facinzting video. It is fortold that the answer to life and everything is " 00110100 00110010" and tnen Julian had to build a bigger and bdtter computet to find what th question was.
According to Hex, the magical computer, the answer is "Because" (the question was "Why?") Or, if you want a more comprehensive answer, "Because everything" (the question was "Why anything?") :D
Can you implement a mode where it quickly takes 41 steps, pauses for a second and repeats? That way we would be able to see the pattern emerging in another dimension, so to speak.
Let's just put this to rest. A LFSR does not generate random numbers. Arguably, it does not even produce pseudo-random numbers, because the pattern repeats, identically, after 2n − 1 states. Knowing the current state, you also know the next state.
The latter is true for every PRNG. (LFSRs are still not very good for other reasons, for example they have Sierpinski Triangles all over them all the time.)
Press a single 1 digit. then use a potentiometer or something to speed up the pattern TO MANY MANY ORDERS OF MAGNITUDE FASTER to see what happens to the pattern!!!!! PLEASE TRY IT MAKE A VIDEO ON IT!!!!!
I disagree, these numbers are still random(although what you're calling random is really pseudo-random). Just because they have a lot of zeros and you can predict the next number doesn't mean they're not pseudo-random; all the patterns from an LFSR are predictable, these numbers are the same as any other ones you generate.
I think you need to read that feedback table in the Xilinx app note more carefully. The feedback function should be XNOR not XOR. You are not creating a maximal length series
XNOR is just inverted XOR. If an XNOR was used, then it would be 1s by default and you'd inject a 0 (the opposite of what he did), because 0 XNOR 0 = 1 and 1 XNOR 1 = 1, so all you'd get is 1s.
For a 2Mhz clock to count to 2199023255551 will take 12 days, 17 hours and 25 minutes plus 11.623 seconds, I doubt your RC circuit is that precise ;P What needs random numbers at that speed? You could seed with a large prime number or do it with hardware. Also to Arduino users that use millis/micros you will want to be aware of the variable overflow if you do software delays
I'm beginning to wonder if I should have told you about LFSRs now. You appear to be hooked on them. (I can't blame you. they're great.)
And they have many applications in telecommunication or in other engineering fields.
You are mixing the size of the space of possibilities (2^41) and the length of the sequence generated from a seed and a operation repeted modulo 2^41.
Why absolutely yes, you should have!
If I'm right you took informations from xapp052 app note that uses Xnor not Xor... you need to add an inverter after your xor.
Who wouldn't get hooked on something with 40 flashing blue LEDs?
This breadboard has better programme running on it than any channel on British TV.
This is rather interesting, and you do appear to be having great time playing with them. This morning caught me a bit by surprise, you see I had a rather sleepless night and gave in to the sleep gremlins, raising at 4:55AM I took my morning meds (includes a narcotic) and had my bowl of cereal, put on the coffee, and sat down in my recliner, turned on my laptop and the side notification deal popped up with your new video. Of course in my nummed, sleep deprived state of mind, I saw LEFSA, Well the scene of you rolling out Lefsa and cooking in on your Lefsa cooker! For the uninitiated in Scandinavian cooking, Lefsa is a sort of tortilla made with potato's, eaten with butter and brown sugar or jelly rolled up inside. Wonderful Christmas fare in the Dakota's where many from Northern Europe settled.
this is one of my new favorite youtube series. great job, thanks Julian
It is called pseudo random for a reason. It is not really random. To improve the appearance of randomness you need to seed the register with a number from some random input like white noise from a radio not tuned to a station or something like that.
Better yet, seed it at intervals. LNFRs are good ways to turn a low-bitrate, high-entropy stream from a hardware RNG (like a white noise receiver) into a very high bitrate, high-enough-entropy-for-practical-use stream.
If you only seed the initial value then you are half-way to inventing the stream cypher.
Bruce Friend whatever you seed it with, the sequence will be the same
Peter D Morrison yes it will but if the sequence is long enough starting it at a different point will make it appear more random. Appear not actually be truly random.
I love this. Such a fun tactile implementation of a wide category of algorithms
This kind of binary logic is deeply satisfying for my brain. I love such doohickery when coding too. Thanks, Julian!
Oh! Outtakes! Haha! So joy. Much funny. :)
They may appear to be random when running, but in practice they are completely predictable. Given sufficient computing power they can be cracked, particularly if you know anything about the feedback settings. Note that, in order to get maximum length you must include the last bit in the feedback, the one on the right in Julian's videos. Anything less and you are just shifting the sequence out through a shift register that has no effect on the input.
I believe they are still used as encryption devices. Alice and Bob agree on a common starting setting of, say, 41 bits then as long as they stay in sync, x-oring the message with the pseudo-random bit-stream will encode it and decoding is just the same process of x-orwith the same bit-stream since double xor gets you back to where you started. This would be useful if you only wanted your message to remain secret for a short time. "bomb goes off in 5 minutes" would be OK, but "meet me in 3 weeks time on Hampstead Heath" will probably be a very crowded meeting!
I thought that they were no longer used in serious cryptography, but if you go on Amazon and search for "Shift Register Sequences" in books you will get quite a few hits. Unfortunately all the books seem extremely expensive, none less than £42. Back in the 70's when I was using LFSRs I had a book of that name, but today I couldn't find it. It still may be around.
In order to get the shift register to start at the pattern you want, you obviously have to be able to force all the bits to a given state. Similarly, if you want to use it as a counter, you need to detect state N (Sn) and use this to reset the register back to state 1 (S1). Neither of these states needs be a single 1, they just need to satisfy the requirement of being N apart.
The phenomenon of patterns with few ones not looking very random happens in a big way with the Mersenne Twister PRNG. If you start it in a state that's mostly zeroes, it takes thousands of cycles before it starts producing decently distributed outputs. Typically one uses another small PRNG to seed it.
I think a great follow up would be to make an avalanche RNG and put it in front of your 40 bit shift register. Maybe look at with nd without a Von Neumann filter.
I know that pattern! I'd recognise it anywhere. Do you realise you've designed a circuit to draw a Sierpinski triangle? The more bits in your register, the longer it'll carry on generating that Sierpinski triangle pattern - until it runs out of bits and starts generating pseudorandom goodness.
Next step: Add another row of LEDs that latches the picture of every 40th cycle to make it plain to see!
Sierpinski triangle? Nothing like it.
Try breaking it up into 40-bit lengths and putting them one above the other. What naturally emerges is the odd/even shaded form of the Pascal triangle - which is not at all surprising, as that triangle is constructed by each line taking the XOR of adjacent elements of the line above. The odd/even pascal triangle is in turn an approximation of the Sierpinski triangle.
Is that a kind of Turing machine?
At 2MHz the cycle would repeat every 305.42 hours, or 12.72 days
It's not fair to use the term "random" at all, no matter where in the stream - it's ALL deterministic! "Complex" rather than random, maybe?
"Pseudorandom" is often used, because it appears to be random, but is not random.
I think if you print out the initial pattern in rows with the right alignment you'll get a Sierpinski triangle. Try it!
Why does this remind me of the Game Of Life?
Yeah I think it's related - several mentions in stephen wolframs book on cellular automata www.wolframscience.com/nks/notes-7-5--random-number-generators/ second half of the page
My feelings exactly
Probably because the effects appear visually similar and there's some math involved (albeit different math) in each case.
There are interesting similarities here to Conways game of life, the patterns even appear similar. Not surprising I suppose as they both use XOR to generate the next state based on the current state.
Worth pointing out that the stages of "building the pattern up" are just a part of the "main" pattern anyway. In other words the series of states with a single bit plus all subsequent states will re-occur after 2^41-1 steps. Put another way, if you started with a random set of bits on and off, then the series with just a single bit will turn up naturally some time between the start and 2^41 steps later. It will also be preceded by an interesting non-random sequence running down from lots of bits to just the single being on.
I'd be interested to see if there is some way to 'reverse' the sequence and watch a random-looking sequence turn in to a single bit.
I guess the lead up to the roll over may look random
Considering that the rules for "creating a lot from a little" still apply, one should be able to derive that lead-up as an exercise, no?
Paul Grimshaw All states will re-occur after 2^42-1 steps
Just repeating what I said on the earlier video, you can get a near-enough-to-random number from a scientific calculator by entering a decimal point followed by some random digits, then taking the natural antilogarithm followed by the reciprocal.
You will get a decimal number which, unless you're a mathematical savant or you've cheated, will be effectively random.
I notice some people have compared the output to The Game Of Life.
In case anyone doesn't know The Game Of Life, it's a game where you use a grid of dots, where each dot can be lit (alive) or unlit (dead).
Each generation, you check how many "living" (lit) neighbours the pixel has. If it has less than 2 living neighbours, it dies of loneliness for the next generation. If it has 2 living neighbours, it remains unchanged in the next generation. If it has 3 living neighbours, it is alive in the next generation. Any more than 3 living neighbours and it dies of overcrowding for the next generation.
I figured out last video at 1Hz it would take almost 70000 years before it would start to repeat, and at about 1MHz it would take a little over 25 days before it would start the pattern again, so at 2MHz, I am guessing about 12.5 days? A shockingly long time considering how fast its running. Even at 1GHz, its going to be longer then a half hour. Although it helps put into perspective the amount of 1's and 0's a computer can wrangle.
I enjoyed the bloopers at the end
Julian, this reminds me of a linear "game of life"!
coincidently today I learnt LFSRs produced the space invaders explosion according to Grant Searle's awesome website. Its 3 ganged '374's for me first chance I get.
Could you connect the shift register outputs to a DAC, hook the analog signal up to an oscilloscope (or a speaker trough an amplifier), increase the clock frquenzy and study what happens? Maybe not all 40 bits, but it would be interesting to see.
It would sound similar to white noise. This is how noise is generated in some synthesizers such as the EDP Wasp which uses a 4006 (18 bits) clocked at about 25kHz.
I actually thought about that. Interesting fact. Thanks!
You can connect any of the outputs of the exact circuit Julian was using to a volume potentiometer (5V is a bit too loud) and into an amp if you want. At fast clock speeds it will sound like "shhhhhhhh".
If you change the taps to something that only gives you a much shorter sequence you will get different sounds very similar to Atari 2600 background whooshes and thruster noises especially if you sweep the speed of the clock up and down.
It always reminds me of Haunted House, Dragster and stuff like that .
High clock speeds, not fast speeds. A fast speed is a quickly changing speed, which is a high acceleration.
So, by that assertion, is 'driving too fast' constantly accelerating? Not necessarily; you could also be decelerating, or experiencing no horizontal acceleration at all.
I can't stop wondering if this could produce (almost real) pseudo random numbers; well maybe an almost random seed for a pseudo random number generator. Now if this thing was started at the same time as the cpu, but at a different frequency to the cpu wouldn't the probability of this thing producing the same pattern at the execution of the code seeding the RNG be rather on the low side? Or have I got this whole "project" A over T?
I couldn't stop giggling at the little strips of paper, BUT they did illustrate the process perfectly. Thank you, Julian.
I don't think seeding one prng from another actually makes the output any 'more random'
Some uc's implement true RNG - according to STMs application note AN4230 they're using our other good friend... the ring oscillator to do it.
Michael Keegan , different freq doesn't matter, 'cos the LFSR will still have run for a known consistent period of time when the CPU reaches the code instruction to read the LFSR's value.
Does it need robust ECC ideally? Can cosmic rays suddenly change a bit making it predictable?
Happy New Year Julian...
Very cool =)
I'm looking this a lot. I'll make a board of that. With jumpers from the XORs. Yes, I like that a lot.
is that kinda how random seeding worked in basic?
populate with a random seed and let randomize go from there in its psudo random order
Counting sheep is for amateurs!
Love the out takes haha
12:47 DEMONETISED
What? Usually you end with cheerio.
We got a swear this time.
plus, he's been giving us the finger the entire video
The finger means nothing in the U.K. Two fingers is the equivalent. In Australia, the hitch-hiker's thumb is bad; you use one finger to flag a lift. It's a convoluted world.
To be as bright as you, all that knowledge i wish i had. Its going to take me quite some time to catch up. Thanks again for anothet facinzting video. It is fortold that the answer to life and everything is " 00110100 00110010" and tnen Julian had to build a bigger and bdtter computet to find what th question was.
Neither of which == 42
According to Hex, the magical computer, the answer is "Because" (the question was "Why?")
Or, if you want a more comprehensive answer, "Because everything" (the question was "Why anything?")
:D
The corollary is 'Mostly harmless.'.
Interesting that you seem to do some video editing. I thought your videos were pretty much just a stream of consciousness type of thing.
Can you implement a mode where it quickly takes 41 steps, pauses for a second and repeats? That way we would be able to see the pattern emerging in another dimension, so to speak.
can you show us the general circuit diagram
pseudo random is not random, nobody ever said it was, but in randomness, all possible patterns are possible...
Let's just put this to rest. A LFSR does not generate random numbers. Arguably, it does not even produce pseudo-random numbers, because the pattern repeats, identically, after 2n − 1 states. Knowing the current state, you also know the next state.
The latter is true for every PRNG. (LFSRs are still not very good for other reasons, for example they have Sierpinski Triangles all over them all the time.)
Press a single 1 digit. then use a potentiometer or something to speed up the pattern TO MANY MANY ORDERS OF MAGNITUDE FASTER
to see what happens to the pattern!!!!!
PLEASE TRY IT MAKE A VIDEO ON IT!!!!!
You would end up looking at an almost solidly lit array of LEDs with the faintest of a shimmer. Not terribly exciting, if you ask me.
About 12.75 days.
I don't suppose you'd care to post a circuit diagram?
that screen be good for battery level lol
I'm 8 minutes late!
I disagree, these numbers are still random(although what you're calling random is really pseudo-random). Just because they have a lot of zeros and you can predict the next number doesn't mean they're not pseudo-random; all the patterns from an LFSR are predictable, these numbers are the same as any other ones you generate.
it's the life game in hardware
I think you need to read that feedback table in the Xilinx app note more carefully. The feedback function should be XNOR not XOR. You are not creating a maximal length series
XNOR is just inverted XOR. If an XNOR was used, then it would be 1s by default and you'd inject a 0 (the opposite of what he did), because 0 XNOR 0 = 1 and 1 XNOR 1 = 1, so all you'd get is 1s.
@@GRBtutorials This is even explained in the same data sheet.
For a 2Mhz clock to count to 2199023255551 will take 12 days, 17 hours and 25 minutes plus 11.623 seconds, I doubt your RC circuit is that precise ;P What needs random numbers at that speed? You could seed with a large prime number or do it with hardware. Also to Arduino users that use millis/micros you will want to be aware of the variable overflow if you do software delays