I love how around 7:42 the command history goes "cls" followed by "clear". It makes me feel comfortable knowing that the legend Dr. Mike Pound himself also still types clear on Windows
Due to their simplicity and ease of implementing in hardware, LFSRs were used as noise generators in a lot of early synths. Notably, the percussion sounds in NES games come from one of these. The shift register in NES APU is 15 bits long and can be tapped from either the two low bits, just like the 4-bit example in the video, or from bits 0 and 6. Otherwise, it works exactly as described, and because the signal is periodic, by changing how frequently you sample from LFSR, you can adjust the pitch of the simulated percussion. Add an envelope, and you can have pretty cool sound FX from a handful of transistors.
Also, digital noise is, due its nature, great for using as a quasi random clock/trigger source for other components of a synth. For example, in an analog modular synth, you could patch a digital noise source (like the Doepfer A-117, which is a LFSR) into the gate input of an amplitude envelope generator, which would result in musical notes being heard at random intervals. Further / My favorite example regarding synths and LFSRs: As before, DigiNoise / LSFR, but this time with a very low clock rate (less than 10-15 Hz) into the gate/trig in of an envelope, patch the env (with extremely short time constants, basically a quick impulse) directly into the audio input of a resonant filter (low or band pass, preferably), with the resonance setting being high, but shortly before self-oscillation, gently modulate the filter cutoff frequency with low-frequency analog noise (or heavily LP-filtered white noise) and you've got a simulation of falling raindrops, a dripping water tap or, if you add tons of delay and reverb effects on top, a dripstone cave soundscape.
Did a lot of this 40 years ago in device drivers on PDP11s to create Cyclic Redundancy Checks (CRCs) for communications protocols, to protect data in transmission. Every vendor had proprietary systems with different seed values, taps, and which bytes of the message headers to include or ignore! PDP11 assembler language made the ‘bit twiddling’ easy! Happy memories…
I remember trying to look up LFSR last year and there were no good videos online. I had missed that day of my cryptology class and I struggled to figure it out for a few hours before finally getting it. And now this super good video is going to be helping future students for a long time
I missed this lovely English voice, it definitely makes it easier to understand pretty much anything, loved your Data analysis course Dr Mike Pound, always a pleasure.
I once had to write a UUID4 generator and had to look into this stuff. It would be really interesting to see an episode talking about how RNG's can be classified and evaluated, because it really affects what you need them for. For example, different RNG's have different: - memory requirements - performance characteristics - periodicity - probability of collision within the period. - seeding requirements (and sensitivity to seed) - entropy at different points in the period And so on. And it's really interesting how these requirements can conflict, e.g. you can't avoid collisions without reducing entropy. My UUID generator was for a big data system so it had to have exceedingly high period and low probability of collision, but I could use as much system resources as I wanted, didn't need high entropy, and it didn't have to be cryptographically strong. Whereas an RNG for a game can usually be pretty crap, because all that matters is it's fast.
RNG in games can be fascinating. In Doom, the RNG was a counter and a table of 256 values, the same in every copy of Doom. I suppose they thought it was worth the memory over the CPU time. Plus it makes it very easy to synchronize RNG in demos and multiplayer.
The predictable RNG is important for demo playback. The demo doesn't contain anything about AI actions; those are precisely recreated by running the RNG from the start of the table (starting a recording restarts the RNG, too). And 256 bytes isn't that much overhead for a game like Doom, which needed XMS (didn't fit 640k). Don't forget that part of those 256 bytes would be used for RNG purposes anyway, e.g. the code for the calculations and an internal state that's more complex than a simple 8-bit index.
Thank you for this great video! As an engineer I am often confronted with people using "only" random numbers to test their algorithms. E.g. communication through a channel and measure the bit error ratio. Often they underestimate the randomness of "randomness" and gather different results in different runs of the same test. And I always need to explain them to use LFSR (or more basic "pseudo-random binary sequences"), which pseudo-randomly output every possible bit combination exactly a single time. This video, dear Computerphile, helps me a lot to explain the need for this sequences!
Pretty sure the valid numbers that repeat are always prime numbers within the width. In this case he used bits 2,3 to update 0 so b1101=13. The LFSR represents some generating polynomial which is prime. I could have that backwards but been a while since I did the math in college. I think it comes down to using a GF field of the length of the LFSR and when you generate these numbers once you exceed that width you divide by the generating polynomial to get within that field, and dividing by prime number will replicate all possible values
@@wesrichards6349 Yes you're correct on the GF field, (it's a GF(2) field), and if the polynomial which has exponents corresponding to the taps is primitive in the field (so for length 4, we had taps at positions 1 and 4, giving the polynomial x^4 + x + 1), the LFSR cycle length is maximal If I remember my crypto course correctly lol
The condition for maximal length is that the polynomial formed by the taps be primitive in GF(2). The first LFSR in the video has polynomial x^4 + x + 1. A sequence of maximal length generated by a given LFSR is an m-sequence.
Sorry, but I have to ask: WHO? ... needs to ask for "the math" on this subject/video? Did they fast forward through some of it? Why not just watch it over one more time???
"The math" [sic] is not readily presentable even in a Numberphile video. There's too much of it. You'd first have to define Galois fields, then show how to do polynomial arithmetic in them, and then introduce primitive polynomials in GF(2). There's also spectral analysis, auto- and cross-correlation properties, Hadamard transforms etc.. A non-trivial chunk of my MSc. research was getting to grips with LFSRs.
@@davidgillies620 That would be a fantastic addendum. Especially since he could build off of the math already done when he explained how Galois fields are used for AES encryption.
I used LFSRs over finite fields in my PhD thesis to generate a family of combinatorial designs for prime powers using primitive polynomials that gave much better bounds on their sizes than the previously known bounds. That was nearly 10 years ago and it's fascinating to see how people have taken my idea and adapted it to other related or completely unrelated combinatorial designs, but still, our records remain unbeaten in the online catalogue of these designs.
Oh sir thank you soooo much! You've just saved one student living in the Far East who had had no idea how to solve & what should I do & what does it mean and where to start from but already got the programming assignment!
How nostalgic. In a Dilbert cartoon, a demon was charged with creating random numbers. These were 9, 9, 9, 9, 9, .... Which is 1001 in binary! Now we know what program he was using!!!
There are some cool properties of the output of these LFSRs that were not mentioned. For example, if you skip one bit every time, you will still get the same bit-sequence in the end(but at a different "start" location). Also, if you XOR any number of bit-streams for an LFSR, the result will still be the same bit-sequence. The self-synchronizing property is also very useful. You can imagine that after receiving 4 bits into your receiving LFSR, you can calculate the next bit and hence use it as a bit-error-checker.
The Atari 2600 game "Pitfall" is probably the most famous example of an LFSR, it used the bits from a random byte, to build 256 different rooms! Not bad, when the whole game ROM was limited to 4KB!
Speaking of games. How about the strangest use of an LFSR in games. A lot of LCD handheld games (like the Tiger games) used a Sharp SM510 (or variant) processor. The Program Counter was confusingly made up of 3 registers (Pu, Pm, and Pl) with Pl being a 5-bit LFSR with taps on bits 0 and 1 but with a twist -- it always included a 1, so on each iteration, bit 5 was bit1^bit0^1. This had the effect of including 0 in the sequence! For the curious, the PC incremented in a weird way, first Pl was advanced to the next iteration: Pl = (Pl>>1) | (((bit1^bit0)^1)
That's a 6 bit LFSR ... d'oh! ... I'll bet that had a few heads scratching! Also, I should probably point out, as you've noticed that Pu and Pm don't change when PC is incremented. Those needed to be set separately. You can think of them as setting the memory "page". It's a very strange processor.
Pls give us a 2nd inteveriew with the math behind this! And i could listen to Dr. Mike Pound for hours and hours. To bad i'm not living in the uk, so i can't study in Nottingham :D
Remarkable coincidence. We just went over LFSRs in my class today and you guys released a video to help me understand better. Are you guys spying on me? Lol
Fun fact: another popular use of LFSRs is in GPS (rather, GNSS). They use a form of Gold Codes to generate psuedo-random identifiers for every satellite so that receivers (i.e. your phone) can identify, lock on, and track the signals to compute a position
LFSRs were often used in place of counters for very large terminal counts in the days of PALs or PLAs. Simply preload a specific value and wait for the terminal count of all 1s. Or detect the proper bit patterns to generate precision sync pulses and reset count. LFSRs can run very fast without having to worry about complex counter logic or fast carry logic.
These are used in radio as well. GPS uses many 10 bit LFSRs. Funny thing is at 10 bits, there are quite a few tap patterns which will produce an M-sequence. And each bit sequence is seemingly uncorrelated with one another. What GPS does, is each satellite transmits on the same frequency, but uses a unique tap pattern with the repeat aligned exactly with an atomic clock. So not only can you differentiate which satellite you are picking up by it's code (multiple at a time) but you can also determine the time delay based on when the code starts.
In hardware we use these as the basis for communications testing, where they are sometimes referred to as a PRBS generator (psuedo-random binary sequence). The advantage of them is that you only need n bits in a row to determine the remaining outputs of a n shift-register PRBS. The feedback taps are standardized for different protocols, and with that you can use different brands of test equipment to do bit-error-rate testing over the link, because they all use the same PRBS to do so.
You should mention that software implementations can be accelerated by generating multiple bits in one iteration using a lookup table. For example, if you need pseudorandom 8-bit values, you might use a 32-bit generator, but shift out 8 bits and look up the next value for the xor in a 256-word table.
I've been researching these on and off for nearly a decade! I'm trying to add more randomness to the register as a whole. I've made a little progress by shifting normally for a set number of times and then "subshifting" where I shift only half of the register. I have animations and write ups but RUclips isn't letting me post links.
Was once involved with making a hardware RNG for a gambling service. The gambling company used insurance against the risk of too many big prize wins, which meant the insurer had to audit their stuff. Having passed the audit before implmenting our hardware RNG, they were not allowed to make any changes without repeating the audit, so the gambling company chose to never use the hardware RNG. Instead they went back to using their dev tool's built in LSFR RNG. As the video mentions, despite the long sequence, if you know a part of the sequence you can predict where you are along that sequence and therefore know every number that will be generated, this meant they would go live with a RNG that had a deterministic repeatable pattern, and knowing recent winning numbers anyone who knew or guessed the RNG could predict future winning numbers. Luckily for the insurer, the company failed for other reasons before it was ever live! I would've been interested to follow the results had it gone live in that form.
If I recall correctly, this is used in the noise generator for gen 1 pokemon roars. The more metallic noises also fudges with a bit in the middle of the register.
Playing around with using this for a dissolve screen effect. Since it hits every combination between 1 and 15 you just blank out pixels in a 15 pixel shape each loop- no memory needed to keep track. This has been done before but what I'm doing is using a equilateral right triangle of pixels, 5,4,3,2,1 with pixel ids numbered randomly and blanked by an offset based upon the xy location of the triangle (two triangles actually in a 6x5 rectangle). The reason for the triangles is 1: They are 15 pixels, and 2: They move the blanking into an area of the screen as opposed to the easy way which would be a horizontal line of pixels and that would leave more artifacts on the screen.
Something these are very commonly used for is noise generation in arcade machines, home computers, and some game consoles. You wouldn't need any flip flops, there are actual 74 series shift registers out there to use.
Fun fact: Wolfenstein 3D used a 17-bit Galois LFSR (more efficient to implement in software) to produce its famous fade to red effect when you died or defeated a boss. It could guarantee a linear time psuedo random fade with no memory needed to keep track of which pixels were already set to red.
7:30 Python conveniently offers fstrings by going print(f"{state:b}") you could have done the same thing. They are both easier to use and faster to execute!
@@truestopguardatruestop164 of course using C or something would no doubt be faster. This still is faster *by python standards* though. "faster" != "fast"
The easiest way is to get a table of primitive polynomials that is published in an academic journal. That’s what I did, long ago, but I’ve forgotten where it came from. I might have a reference to it somewhere in my poorly organized files.
I needed this video about 6 years ago i was implementing game of life on my tandy color computer in assembly. I needed random numbers to initialize the cells, eventually someone pointed me to LFSRs
I found that grabbing the last several digits off of the computer's clock was pretty reliable as a random seed. There's probably some obscure reason that it's not truly random, but it served.
Dr. Mike, thank you as always! Could Computerphile revisit this topic in terms of cellular automata? I've been experimenting with using CAs as a PRNG/stream cipher components. I've been dying to see more attention to them for encryption or compression. Like LFSRs, they can be implemented extremely efficiently on hardware.
I took a cryptography course ages ago meant for math majors, where we delved into the mathematics of finite fields which underpins how LFSRs work. I was looking forward to a nice review/refresher of that material. It's a shame this video didn't go into that. Definitely a topic for Numberphile.
@@cybisz2883 Ben Eater made a fantastic series on error correction in which he delves to CRC to do polynomial divisions in GF(2) and its use of LFSR's in hardware to achieve that
I would imagine tap originates from beer or wine production (tapping a barrel or keg) which is pretty much what these taps are doing. The faucet in a sink is that same kind of tap into a water main. So they're related by a common ancestor.
I think the period might be the maximum entropy or order - something like that - for a 4 bit shift register without the all 0's i.e. 15! Really nice example.
Now forever called the LDBW algorithm (or sing it with me) "Let's do the bit warp, yeah!" (Rocky Horror Picture Show reference in verse form? You rock, sir. Made my day)
@@jones1618 Thanks Stephen. Dr Pound made me think of Rocky Horror when he used the first two lines in the video at 04:12 , I felt like I should add the last lines. Press 3 when watching the video to get those lines.
@@FlyNAA FAUCET n. a metal piece of equipment that you turn to control the flow of water or other liquid from a pipe, especially on a sink or bathtub. The British word is tap.
For a more low-level implementation you can replace a bunch of taps & xor with a mask and bitcount: I.e. for the 128-bit lfsr with taps at 0,1,2 & 7 you could have rdx:rax as the shift reg, then do mov rbx,rax ; save bottom half and rbx,128+7 ; taps mask shrd eax,edx,1 ; shift bottom half down, fill from top popcnt rbx,rbx ; how many taps were set? shrd edx,ebx,1 ; shift top half and bring in the parity of the count and get a new state in about 5-6 clock cycles
LFSRs are a great way to add uncorrelated noise to a signal. This lets you take advantage of a sigma delta ADC's inherent noise shaping abilities, where adding noise can actually produce less noisy converted data.
Both Type 1 and Type 2 LFSRs can use the same polynomial and shift either left or right so your coding example could be simplified by changing from right to left shifting. It can also be helpful to use the carry bit as rotate through carry instructions are fast and efficient.
One great use of LFSRs is random number generators in sandboxy games like minecraft. They're very easy to build from redstone or whatever system the game has.
From the video, I came to two insights: one tap must be at the units digit, or you're wasting length, and if the distances to the insertion point share a common factor (say, you put bit #0 XOR bit #2 into position #4), you produce two separate sequences which never mix. Both of these "insights" might be trivial, but they fix one tap and eliminate some choices for others. I'd also avoid stuff like "bit #0 XOR bit #1 XOR bit #3 XOR bit #4" -- because XOR is associative and "bit #0 XOR bit #1" is the same as "bit #3 XOR bit #4" three shifts ago. That eliminates #0 XOR #1 XOR #4 XOR #6, too, because that can be taken XOR bit #3 twice, and then you have #3 XOR #4 XOR #6 both now and 3 cycles ago.
Interesting talk. Decades ago I had a Maplin 3600 synth which used an LFSR as a white noise generator. After a short while your brain could hear it cycling. I also built one using TTL 32 bit to flash lights in a sculpture that never happened.
I fully tested a 40 bit LSFR which did indeed go through all combinations: ulong lsb = state & 0x01; state >>= 1; if (lsb) { state ^= 0x9C00000000; } You are right it's so simple the code is in this comment!
I suspect that the deterministic observation of how many iterations it takes to return back to your original state based on the number of xor gates you have within your circuitry might be related to the properties of the polynomial functions in regards to their even and odd properties. For example 1 & 3 xor gates will behavior similarly while producing different results in the same manner that 2 & 4 xor gates will where the odd amount of gates and even amount of gates will behavior quite differently or almost opposite of each other kind of like two vectors and how close they are being either orthogonal or perpendicular to each other are. The steps of the algorithm with in the hardware are shift by 1 bit, then apply xor to n-arbitrary gates. The first instruction is a physical movement as in a linear transformation as we are moving the bits along a line or a stream by some defined stride and here in this case by 1. The second instruction is an arithmetic logical operation. The reason I state arithmetic logical as opposed to just logical is that even though xor is still a comparison gate, it is closely related to addition in that xor is the building blocks of your adder circuitry due to the properties of its truth table, however for xor to be considered a proper half adder other required gates are missing from the circuitry yet xor two single bits is still applying binary arithmetic without any carry bits. So we aren't just comparing two bits based on their 0 and 1 state we are also adding them in a binary fashion and disregarding any carry over. So in truth I suspect that after an x amount of iterations to return back to the original state based on the seeded bit pattern is that for each time we reach that duplicate state it is a multiple of that original state. One way to test this is that every time we shift the bits and a bit falls off the register... push it into a different shift register to keep track of all of the values and when we reach repeated state combine both registers as a single bit pattern with the working register as the MSBs and the stored register as the LSBs. I haven't tested this so I could be wrong on some of the details, but mathematically speaking this algorithm appears to exhibit these properties and behaviors.
Two xor streams running at slightly different frequencies and then xor'd together is impressively random. Especially when the frequency offset is inherently unpredictable.
2^128 is around 3.4*10^38 Yes, if you're watching the digits print on the screen you'll be there for a very long time, but I don't feel like 10^38 is big enough to be truly "secure". That's probably 256-bit encryption is more common.
I think we can use this similar kind of idea in cracking passwords if they consist only of numbers but it become a little bit steep when the password has larger no of digits in this case we can use recursion which can be used as a side guy during the brute force.
funny enough, the "taps" terminology actually does come from plumbing. the taps in your house are "tapping off" from the main water line. and the inputs to the XOR are "tapping off" from whichever bits you choose.
I had to write a random number generator and what I found was the random function wasn’t statistically random. It appeared to be linked to the clock and the time the program took to get to the function. I had to seed the generator with the clock (time since computer epoch) portion of the PSW (Program Status Word). The fun part is to read the PSW you have to get in to supervisor status. The real fun began when application programming teams wanted to use the code, as it meant their code would also need to run in supervisor state (a huge no-no). I ended up putting this in part of the Control Program (for TPF), which was then called by a macro.
LFSRs are also useful when you need a counter or timer in hardware to count up to some fixed value, since LFSRs need much less hardware logic than a binary counter. So by using a LFSR instead of a binary counter, you save silicon area, increase max operating frequency, and lower the power consumption.
@@monkatraz if you need to count some event, and generate a signal when you have seen 10 events. For example. Just reset the LFSR to a known state, execute the LFSR on every event, and generate the output signal when the LFSR has reached the 10th state.
This is very cool! I guess it's harder to use this in cryptographic applications because by listening to n consecutive output bits, you can determine the rest of the output.
Very interesting ; I was looking for a way to quickly generate a big stream of random data (testing a framebuffer with random pixels) and I think this will do! :-)
For people who like ansi c examples instead, here's what I just threw together: ulong rng_lsfr( ulong *seed ) { size_t i; ulong value = 0; for ( i = 0; i < bitsof(ulong); ++i ) { value = 1; *seed |= ((*seed ^ value) & 1u)
Interesting video as usual :) However, at one million bits per second it'd take much, much longer than "10 to 20 times the lifetime of the universe" to exaust 2^128. More like one million billion times. Also, saying "the statistical randomness of these streams [LFSR] is really, really good", without further qualifications, seems very naive; I'm pretty sure the 128-bit generator he presented would fail all randomness test suites, such as TestU01 and PractRand. In the original 2007 TestU01 paper the authors tested some LFSR (more modern and sophisticated than the one in the video) and they failed randomness tests. Marsaglia tried with his xorshift generator but today we know they have relevant flaws. You can make good generator using this approach, such as the recent ones by Vigna (xoroshiro etc) but it's not so easy. It it were, we would have got good random number generators in 1965 and not in 1997 or so with the MT.
All PRNGs depend on a “seed”. If you are using it for non-adversarial purposes (simulations, games), use the current time. If you are using it for crypto (literally “hidden”) and are facing a potential attack, use a REAL random-number generator, like rolling dice, to generate the seed.
I implimented s 32-bit maximum LFSR for rand() in he 1970 C libfary for SDWTPc 6809 hobby omputer, and got roundly fritidised for not using a "proper" linear ongruential pseudorandom number generator. As you pointed out LFSR's are stati9sically excellent and more to he pointk very vey fast, particularly on s processor hat didn't have a hardware DIV iinstruction.
If you didn't catch the reference at 6:22 he's likely referring to Steve Mould, who explained flip flop chain logic.... Using actual flipflops on a chain.
I'm more inclined to interpret that as Steve Bagley (frequently seen on this channel too, works at the same university). I remember a video explaining computer memory by him as well from many years ago, featured a breadboard, some components and LEDs that light up along with a more schematic overview and tables explaining what the various gates do etc. But such a project done by Steve Mould would certainly be interesting and weird as well.
Great video. Just want to point out that in the third line of the first set if operations, ~2:13 it says 1 xor 1 = 1. I could be wrong, but pretty sure that should be 0. It is still correct on the paper, just wrong in the animation so not a big deal.
No, I thought that too, but if you watch it once more, you will notice, that last line in animation is output of previous line, which has 1 and 0 -> output is one. Zero as product of 1 and 1 is supposed to be on next line, which is not animated. It's just confusing at this speed, but it's correct.
It’s cool that you guys talk about something random from time to time
_ba-dum tsssss_
*pseudo-random
> pseudo make me a sandwich ;)
' Achtsekundenfurz' is not in the sudoers file. This incident will be reported.
No presents for you this Christmas
I see what you did there
I love how around 7:42 the command history goes "cls" followed by "clear". It makes me feel comfortable knowing that the legend Dr. Mike Pound himself also still types clear on Windows
fwiw, if you use msys on Windows, then you can type clear and it will work just the same as cls.
@@Tahgtahv Powershell accepts "clear" too. I think it's an alias to the actual command though.
The exact moment is at 7:37
Yeah, I think everyone who switches between OSes has at some point typed "ls" into the Windows terminal ^^
@@pointerish and ls too, I believe it even understands the -l and -A flags
Due to their simplicity and ease of implementing in hardware, LFSRs were used as noise generators in a lot of early synths. Notably, the percussion sounds in NES games come from one of these. The shift register in NES APU is 15 bits long and can be tapped from either the two low bits, just like the 4-bit example in the video, or from bits 0 and 6. Otherwise, it works exactly as described, and because the signal is periodic, by changing how frequently you sample from LFSR, you can adjust the pitch of the simulated percussion. Add an envelope, and you can have pretty cool sound FX from a handful of transistors.
This comment is incredible. Thanks.
this is very cool to know, thank you!
They were used to generate "starfields" in the arcade shoot-em-ups like Galaga as well.
Also, digital noise is, due its nature, great for using as a quasi random clock/trigger source for other components of a synth. For example, in an analog modular synth, you could patch a digital noise source (like the Doepfer A-117, which is a LFSR) into the gate input of an amplitude envelope generator, which would result in musical notes being heard at random intervals.
Further / My favorite example regarding synths and LFSRs:
As before, DigiNoise / LSFR, but this time with a very low clock rate (less than 10-15 Hz) into the gate/trig in of an envelope, patch the env (with extremely short time constants, basically a quick impulse) directly into the audio input of a resonant filter (low or band pass, preferably), with the resonance setting being high, but shortly before self-oscillation, gently modulate the filter cutoff frequency with low-frequency analog noise (or heavily LP-filtered white noise) and you've got a simulation of falling raindrops, a dripping water tap or, if you add tons of delay and reverb effects on top, a dripstone cave soundscape.
That moment when you found something about sound design hardware in an unexpected place 👀
Did a lot of this 40 years ago in device drivers on PDP11s to create Cyclic Redundancy Checks (CRCs) for communications protocols, to protect data in transmission. Every vendor had proprietary systems with different seed values, taps, and which bytes of the message headers to include or ignore! PDP11 assembler language made the ‘bit twiddling’ easy! Happy memories…
I approve this comment :)
RSTS/E
@@Wombbatts RSX-11M actually
@@Richardincancale I used RSTS/E for bank accounting and general ledger in '83.
Dear lord when i was busy not being born yet, my father was busy repairing CRT TVs in Polish People Republic you were busy doing this. Incredible.
I remember trying to look up LFSR last year and there were no good videos online. I had missed that day of my cryptology class and I struggled to figure it out for a few hours before finally getting it. And now this super good video is going to be helping future students for a long time
Julian Ilett did a series on hardware LFSRs 4 years ago... I thought it was fun but your mileage may vary
There is a great treatment of them in TAoCP. It’s somewhere around page 20 in one of the volumes.
I missed this lovely English voice, it definitely makes it easier to understand pretty much anything, loved your Data analysis course Dr Mike Pound, always a pleasure.
Yeah this dude and prof brailsford are my fav computerphile guys
I once had to write a UUID4 generator and had to look into this stuff. It would be really interesting to see an episode talking about how RNG's can be classified and evaluated, because it really affects what you need them for. For example, different RNG's have different:
- memory requirements
- performance characteristics
- periodicity
- probability of collision within the period.
- seeding requirements (and sensitivity to seed)
- entropy at different points in the period
And so on. And it's really interesting how these requirements can conflict, e.g. you can't avoid collisions without reducing entropy. My UUID generator was for a big data system so it had to have exceedingly high period and low probability of collision, but I could use as much system resources as I wanted, didn't need high entropy, and it didn't have to be cryptographically strong. Whereas an RNG for a game can usually be pretty crap, because all that matters is it's fast.
RNG in games can be fascinating. In Doom, the RNG was a counter and a table of 256 values, the same in every copy of Doom. I suppose they thought it was worth the memory over the CPU time. Plus it makes it very easy to synchronize RNG in demos and multiplayer.
The predictable RNG is important for demo playback. The demo doesn't contain anything about AI actions; those are precisely recreated by running the RNG from the start of the table (starting a recording restarts the RNG, too). And 256 bytes isn't that much overhead for a game like Doom, which needed XMS (didn't fit 640k). Don't forget that part of those 256 bytes would be used for RNG purposes anyway, e.g. the code for the calculations and an internal state that's more complex than a simple 8-bit index.
Thank you for this great video! As an engineer I am often confronted with people using "only" random numbers to test their algorithms. E.g. communication through a channel and measure the bit error ratio. Often they underestimate the randomness of "randomness" and gather different results in different runs of the same test. And I always need to explain them to use LFSR (or more basic "pseudo-random binary sequences"), which pseudo-randomly output every possible bit combination exactly a single time.
This video, dear Computerphile, helps me a lot to explain the need for this sequences!
I’m going to need a video on that math.
Yes
Pretty sure the valid numbers that repeat are always prime numbers within the width. In this case he used bits 2,3 to update 0 so b1101=13. The LFSR represents some generating polynomial which is prime. I could have that backwards but been a while since I did the math in college. I think it comes down to using a GF field of the length of the LFSR and when you generate these numbers once you exceed that width you divide by the generating polynomial to get within that field, and dividing by prime number will replicate all possible values
@@wesrichards6349 Yes you're correct on the GF field, (it's a GF(2) field), and if the polynomial which has exponents corresponding to the taps is primitive in the field (so for length 4, we had taps at positions 1 and 4, giving the polynomial x^4 + x + 1), the LFSR cycle length is maximal
If I remember my crypto course correctly lol
@you- tube Check out the videos and extra bits on the AES encryption videos.
I would love a video that dives deep into the math of finding optimal taps.
Love all of this, but it's really time for Dr Mike to use f-strings in python!
I guess it's not possible to format a number as binary using an f-string
@@rami4933 print(f"{state:04b}")
@@MattRose30000 Thanks, I didn't know this
Dr Mike Pound, man I miss your cryptography teaching. Best lecturer I ever had.
I could listen to this man for hours, all of his computerphile videos are pure gold.
The condition for maximal length is that the polynomial formed by the taps be primitive in GF(2). The first LFSR in the video has polynomial x^4 + x + 1. A sequence of maximal length generated by a given LFSR is an m-sequence.
At this point a video about the math is like an encore, he's just waiting for us to ask for it.
@you- tube not necessarily, he’s done math videos on Computerphile as well.
Well I'd be down!!
Sorry, but I have to ask: WHO? ... needs to ask for "the math" on this subject/video? Did they fast forward through some of it? Why not just watch it over one more time???
"The math" [sic] is not readily presentable even in a Numberphile video. There's too much of it. You'd first have to define Galois fields, then show how to do polynomial arithmetic in them, and then introduce primitive polynomials in GF(2). There's also spectral analysis, auto- and cross-correlation properties, Hadamard transforms etc.. A non-trivial chunk of my MSc. research was getting to grips with LFSRs.
@@davidgillies620 That would be a fantastic addendum. Especially since he could build off of the math already done when he explained how Galois fields are used for AES encryption.
Imagine having classes with these guys, it would be amazingly exciting to learn!
I used LFSRs over finite fields in my PhD thesis to generate a family of combinatorial designs for prime powers using primitive polynomials that gave much better bounds on their sizes than the previously known bounds. That was nearly 10 years ago and it's fascinating to see how people have taken my idea and adapted it to other related or completely unrelated combinatorial designs, but still, our records remain unbeaten in the online catalogue of these designs.
Finally a video on random numbers, i love this, last time it was like 9 years ago when -phile channels made video on RNG (using radiation)
Oh sir thank you soooo much! You've just saved one student living in the Far East who had had no idea how to solve & what should I do & what does it mean and where to start from but already got the programming assignment!
I learn so much with Dr. Pound! Thank you for the videos! I wish his courses were available online
Useless trivia: The "SID" sound chip in the Commodore 64 used LFSRs to approximate the logarithmic ramp of the ADSRs and filters.
Also used on the Game Boy to generate noise sounds (although probably not as exciting as the SID).
Also used in Pitfall on the Atari 2600 to generate the screen layouts.
Also used in the UK to generate government policy....
Also used in River Raid to generate screen layouts.
@@deviljelly3 lol
How nostalgic. In a Dilbert cartoon, a demon was charged with creating random numbers. These were 9, 9, 9, 9, 9, .... Which is 1001 in binary! Now we know what program he was using!!!
I remember LFSR from my hardware course work. It would have been nice to see the math for choosing the taps because I've forgotten that part.
There are some cool properties of the output of these LFSRs that were not mentioned. For example, if you skip one bit every time, you will still get the same bit-sequence in the end(but at a different "start" location). Also, if you XOR any number of bit-streams for an LFSR, the result will still be the same bit-sequence. The self-synchronizing property is also very useful. You can imagine that after receiving 4 bits into your receiving LFSR, you can calculate the next bit and hence use it as a bit-error-checker.
Wow! This is your first video I've seen a live demo in... I love it!
The Atari 2600 game "Pitfall" is probably the most famous example of an LFSR, it used the bits from a random byte, to build 256 different rooms!
Not bad, when the whole game ROM was limited to 4KB!
Speaking of games. How about the strangest use of an LFSR in games.
A lot of LCD handheld games (like the Tiger games) used a Sharp SM510 (or variant) processor. The Program Counter was confusingly made up of 3 registers (Pu, Pm, and Pl) with Pl being a 5-bit LFSR with taps on bits 0 and 1 but with a twist -- it always included a 1, so on each iteration, bit 5 was bit1^bit0^1. This had the effect of including 0 in the sequence!
For the curious, the PC incremented in a weird way, first Pl was advanced to the next iteration: Pl = (Pl>>1) | (((bit1^bit0)^1)
That's a 6 bit LFSR ... d'oh! ... I'll bet that had a few heads scratching! Also, I should probably point out, as you've noticed that Pu and Pm don't change when PC is incremented. Those needed to be set separately. You can think of them as setting the memory "page". It's a very strange processor.
Pls give us a 2nd inteveriew with the math behind this! And i could listen to Dr. Mike Pound for hours and hours. To bad i'm not living in the uk, so i can't study in Nottingham :D
I designed a hardware cryptography module using LFSRs in 1972, the year the first 8-bit microprocessor, the Intel 8008, was released.
Remarkable coincidence. We just went over LFSRs in my class today and you guys released a video to help me understand better. Are you guys spying on me? Lol
These are really handy.
Very simple, but you do have to check for the "ALL ZERO" state when you first power up.
welcome back my favourite professor
"What's the actual use for this series?"
>> Hacking montages in 99% of movies.
This is awesome, I have just started with my master's program in Cyber Security and we had to learn this for the basics in cryptography!
Fun fact: another popular use of LFSRs is in GPS (rather, GNSS). They use a form of Gold Codes to generate psuedo-random identifiers for every satellite so that receivers (i.e. your phone) can identify, lock on, and track the signals to compute a position
LFSRs were often used in place of counters for very large terminal counts in the days of PALs or PLAs. Simply preload a specific value and wait for the terminal count of all 1s. Or detect the proper bit patterns to generate precision sync pulses and reset count. LFSRs can run very fast without having to worry about complex counter logic or fast carry logic.
These are used in radio as well. GPS uses many 10 bit LFSRs. Funny thing is at 10 bits, there are quite a few tap patterns which will produce an M-sequence. And each bit sequence is seemingly uncorrelated with one another. What GPS does, is each satellite transmits on the same frequency, but uses a unique tap pattern with the repeat aligned exactly with an atomic clock. So not only can you differentiate which satellite you are picking up by it's code (multiple at a time) but you can also determine the time delay based on when the code starts.
I love when Dr. Pound explains stuff!
In hardware we use these as the basis for communications testing, where they are sometimes referred to as a PRBS generator (psuedo-random binary sequence). The advantage of them is that you only need n bits in a row to determine the remaining outputs of a n shift-register PRBS. The feedback taps are standardized for different protocols, and with that you can use different brands of test equipment to do bit-error-rate testing over the link, because they all use the same PRBS to do so.
You should mention that software implementations can be accelerated by generating multiple bits in one iteration using a lookup table. For example, if you need pseudorandom 8-bit values, you might use a 32-bit generator, but shift out 8 bits and look up the next value for the xor in a 256-word table.
I've been researching these on and off for nearly a decade! I'm trying to add more randomness to the register as a whole. I've made a little progress by shifting normally for a set number of times and then "subshifting" where I shift only half of the register. I have animations and write ups but RUclips isn't letting me post links.
Was once involved with making a hardware RNG for a gambling service.
The gambling company used insurance against the risk of too many big prize wins, which meant the insurer had to audit their stuff. Having passed the audit before implmenting our hardware RNG, they were not allowed to make any changes without repeating the audit, so the gambling company chose to never use the hardware RNG. Instead they went back to using their dev tool's built in LSFR RNG.
As the video mentions, despite the long sequence, if you know a part of the sequence you can predict where you are along that sequence and therefore know every number that will be generated, this meant they would go live with a RNG that had a deterministic repeatable pattern, and knowing recent winning numbers anyone who knew or guessed the RNG could predict future winning numbers.
Luckily for the insurer, the company failed for other reasons before it was ever live! I would've been interested to follow the results had it gone live in that form.
If I recall correctly, this is used in the noise generator for gen 1 pokemon roars. The more metallic noises also fudges with a bit in the middle of the register.
Playing around with using this for a dissolve screen effect. Since it hits every combination between 1 and 15 you just blank out pixels in a 15 pixel shape each loop- no memory needed to keep track. This has been done before but what I'm doing is using a equilateral right triangle of pixels, 5,4,3,2,1 with pixel ids numbered randomly and blanked by an offset based upon the xy location of the triangle (two triangles actually in a 6x5 rectangle). The reason for the triangles is 1: They are 15 pixels, and 2: They move the blanking into an area of the screen as opposed to the easy way which would be a horizontal line of pixels and that would leave more artifacts on the screen.
Great video, as usual! Brings up fond memories of working on signal processing algorithms using pseudo noise signals based on M-sequences. 🙂
the general quality of the video has improved! congrats!!
Something these are very commonly used for is noise generation in arcade machines, home computers, and some game consoles.
You wouldn't need any flip flops, there are actual 74 series shift registers out there to use.
Fun fact: Wolfenstein 3D used a 17-bit Galois LFSR (more efficient to implement in software) to produce its famous fade to red effect when you died or defeated a boss. It could guarantee a linear time psuedo random fade with no memory needed to keep track of which pixels were already set to red.
Thanks for yet another clear, engaging, and interesting talk and video!
7:30 Python conveniently offers fstrings by going print(f"{state:b}") you could have done the same thing. They are both easier to use and faster to execute!
Dont put “fast” and “python” together?
@@truestopguardatruestop164 of course using C or something would no doubt be faster. This still is faster *by python standards* though. "faster" != "fast"
5:44 There are ways... that is an extremely interesting statement and I would very much enjoy hearing about those ways.
The easiest way is to get a table of primitive polynomials that is published in an academic journal. That’s what I did, long ago, but I’ve forgotten where it came from. I might have a reference to it somewhere in my poorly organized files.
I needed this video about 6 years ago i was implementing game of life on my tandy color computer in assembly. I needed random numbers to initialize the cells, eventually someone pointed me to LFSRs
I found that grabbing the last several digits off of the computer's clock was pretty reliable as a random seed. There's probably some obscure reason that it's not truly random, but it served.
Dr. Mike, thank you as always! Could Computerphile revisit this topic in terms of cellular automata? I've been experimenting with using CAs as a PRNG/stream cipher components. I've been dying to see more attention to them for encryption or compression. Like LFSRs, they can be implemented extremely efficiently on hardware.
"We won't dwell on some maths". That's a shame because the maths behind LFSR is very interesting.
Numberphile don't like their territory being being encroached upon.... they send round the heavies ...
It could be a thrilling crossover!
@@heaslyben it could... just don't tell the physicists or the chemists
I took a cryptography course ages ago meant for math majors, where we delved into the mathematics of finite fields which underpins how LFSRs work. I was looking forward to a nice review/refresher of that material. It's a shame this video didn't go into that. Definitely a topic for Numberphile.
@@cybisz2883 Ben Eater made a fantastic series on error correction in which he delves to CRC to do polynomial divisions in GF(2) and its use of LFSR's in hardware to achieve that
The frequency at which D.R Pound flicks his left hand sleeve would be a great seed for a random number generator
I would imagine tap originates from beer or wine production (tapping a barrel or keg) which is pretty much what these taps are doing. The faucet in a sink is that same kind of tap into a water main. So they're related by a common ancestor.
I think the period might be the maximum entropy or order - something like that - for a 4 bit shift register without the all 0's i.e. 15! Really nice example.
I love the fact that Mike is using Dell XPS. great machine.
It's a shift to the right
And a little xor
With your taps on your bits
You bring your loops in tight
Now forever called the LDBW algorithm (or sing it with me) "Let's do the bit warp, yeah!"
(Rocky Horror Picture Show reference in verse form? You rock, sir. Made my day)
@@jones1618 Thanks Stephen. Dr Pound made me think of Rocky Horror when he used the first two lines in the video at 04:12 , I felt like I should add the last lines. Press 3 when watching the video to get those lines.
“Tap” has everything to do with plumbing - you are tapping into the stream of bits just as a faucet taps into a stream of water.
@Michael Lorton No. A faucet may stop the stream and it never feeds back.
@@MrCuddlyable3 It doesn’t but it can, and in the animation in the video it does just that.
@@FlyNAA FAUCET n. a metal piece of equipment that you turn to control the flow of water or other liquid from a pipe, especially on a sink or bathtub. The British word is tap.
@@MrCuddlyable3 yes, agreed. So what's your disagreement with Michael Lorton's comment?
@@FlyNAA Come back when you can make an LFSR using a faucet.
What an amazing video with great and clear explanations.
Keep it up and way to go !
For a more low-level implementation you can replace a bunch of taps & xor with a mask and bitcount:
I.e. for the 128-bit lfsr with taps at 0,1,2 & 7 you could have rdx:rax as the shift reg, then do
mov rbx,rax ; save bottom half
and rbx,128+7 ; taps mask
shrd eax,edx,1 ; shift bottom half down, fill from top
popcnt rbx,rbx ; how many taps were set?
shrd edx,ebx,1 ; shift top half and bring in the parity of the count
and get a new state in about 5-6 clock cycles
I’m not sure I’d trust this. Seems shifty
Don't worry, it's going to be more of the same
Thanks a lot. I'm rather picky about random number generators. This is a great low-cost approach.
LFSRs are a great way to add uncorrelated noise to a signal. This lets you take advantage of a sigma delta ADC's inherent noise shaping abilities, where adding noise can actually produce less noisy converted data.
this was one of my favourite parts of the digital electronics units I did
Two key quotes from this video that sun up all of computer science 1) “that’s all just 0s and 1s” and 2) “let’s make this more complicated”
Both Type 1 and Type 2 LFSRs can use the same polynomial and shift either left or right so your coding example could be simplified by changing from right to left shifting. It can also be helpful to use the carry bit as rotate through carry instructions are fast and efficient.
One great use of LFSRs is random number generators in sandboxy games like minecraft. They're very easy to build from redstone or whatever system the game has.
I wish I had teachers like you in my computer class
I would love to understand the maths of getting the taps right for maximum period lengths!
From the video, I came to two insights: one tap must be at the units digit, or you're wasting length, and if the distances to the insertion point share a common factor (say, you put bit #0 XOR bit #2 into position #4), you produce two separate sequences which never mix. Both of these "insights" might be trivial, but they fix one tap and eliminate some choices for others. I'd also avoid stuff like "bit #0 XOR bit #1 XOR bit #3 XOR bit #4" -- because XOR is associative and "bit #0 XOR bit #1" is the same as "bit #3 XOR bit #4" three shifts ago. That eliminates #0 XOR #1 XOR #4 XOR #6, too, because that can be taken XOR bit #3 twice, and then you have #3 XOR #4 XOR #6 both now and 3 cycles ago.
You need a primitive irreducible polynomial of the right order for the number of bits.
Interesting talk. Decades ago I had a Maplin 3600 synth which used an LFSR as a white noise generator. After a short while your brain could hear it cycling. I also built one using TTL 32 bit to flash lights in a sculpture that never happened.
I fully tested a 40 bit LSFR which did indeed go through all combinations: ulong lsb = state & 0x01; state >>= 1; if (lsb) { state ^= 0x9C00000000; } You are right it's so simple the code is in this comment!
I suspect that the deterministic observation of how many iterations it takes to return back to your original state based on the number of xor gates you have within your circuitry might be related to the properties of the polynomial functions in regards to their even and odd properties. For example 1 & 3 xor gates will behavior similarly while producing different results in the same manner that 2 & 4 xor gates will where the odd amount of gates and even amount of gates will behavior quite differently or almost opposite of each other kind of like two vectors and how close they are being either orthogonal or perpendicular to each other are. The steps of the algorithm with in the hardware are shift by 1 bit, then apply xor to n-arbitrary gates. The first instruction is a physical movement as in a linear transformation as we are moving the bits along a line or a stream by some defined stride and here in this case by 1. The second instruction is an arithmetic logical operation. The reason I state arithmetic logical as opposed to just logical is that even though xor is still a comparison gate, it is closely related to addition in that xor is the building blocks of your adder circuitry due to the properties of its truth table, however for xor to be considered a proper half adder other required gates are missing from the circuitry yet xor two single bits is still applying binary arithmetic without any carry bits. So we aren't just comparing two bits based on their 0 and 1 state we are also adding them in a binary fashion and disregarding any carry over. So in truth I suspect that after an x amount of iterations to return back to the original state based on the seeded bit pattern is that for each time we reach that duplicate state it is a multiple of that original state. One way to test this is that every time we shift the bits and a bit falls off the register... push it into a different shift register to keep track of all of the values and when we reach repeated state combine both registers as a single bit pattern with the working register as the MSBs and the stored register as the LSBs. I haven't tested this so I could be wrong on some of the details, but mathematically speaking this algorithm appears to exhibit these properties and behaviors.
Two xor streams running at slightly different frequencies and then xor'd together is impressively random. Especially when the frequency offset is inherently unpredictable.
2^128 is around 3.4*10^38
Yes, if you're watching the digits print on the screen you'll be there for a very long time, but I don't feel like 10^38 is big enough to be truly "secure". That's probably 256-bit encryption is more common.
1 min since upload, 13 min video, two downvotes. WTF
People jealous of him handsomeness, probably
I think we can use this similar kind of idea in cracking passwords if they consist only of numbers but it become a little bit steep when the password has larger no of digits in this case we can use recursion which can be used as a side guy during the brute force.
We will love to see a video on APIs
funny enough, the "taps" terminology actually does come from plumbing. the taps in your house are "tapping off" from the main water line. and the inputs to the XOR are "tapping off" from whichever bits you choose.
I had to write a random number generator and what I found was the random function wasn’t statistically random. It appeared to be linked to the clock and the time the program took to get to the function. I had to seed the generator with the clock (time since computer epoch) portion of the PSW (Program Status Word). The fun part is to read the PSW you have to get in to supervisor status.
The real fun began when application programming teams wanted to use the code, as it meant their code would also need to run in supervisor state (a huge no-no). I ended up putting this in part of the Control Program (for TPF), which was then called by a macro.
LFSRs are also useful when you need a counter or timer in hardware to count up to some fixed value, since LFSRs need much less hardware logic than a binary counter.
So by using a LFSR instead of a binary counter, you save silicon area, increase max operating frequency, and lower the power consumption.
How would it work as a counter? It goes through every arrangement of bits, but not in order obviously, so how does that work?
@@monkatraz if you need to count some event, and generate a signal when you have seen 10 events. For example.
Just reset the LFSR to a known state, execute the LFSR on every event, and generate the output signal when the LFSR has reached the 10th state.
On average Dr Mike's videos has highest view count.
This is very cool! I guess it's harder to use this in cryptographic applications because by listening to n consecutive output bits, you can determine the rest of the output.
It is called pseudo-random because the random output pattern is repeatable given the same initial random seed.
It's got a *lot* to do with plumbing. The (plumbing) tap is called a cap because it taps into the (water) line.
Very interesting ; I was looking for a way to quickly generate a big stream of random data (testing a framebuffer with random pixels) and I think this will do! :-)
I just love me some Dr Mike Pound
Why has it taken me so long to realize that if you flip 8 coins, you've mechanically generated a random number between 0 and 255?
For people who like ansi c examples instead, here's what I just threw together:
ulong rng_lsfr( ulong *seed )
{
size_t i;
ulong value = 0;
for ( i = 0; i < bitsof(ulong); ++i )
{
value = 1;
*seed |= ((*seed ^ value) & 1u)
Interesting video as usual :)
However, at one million bits per second it'd take much, much longer than "10 to 20 times the lifetime of the universe" to exaust 2^128. More like one million billion times.
Also, saying "the statistical randomness of these streams [LFSR] is really, really good", without further qualifications, seems very naive; I'm pretty sure the 128-bit generator he presented would fail all randomness test suites, such as TestU01 and PractRand. In the original 2007 TestU01 paper the authors tested some LFSR (more modern and sophisticated than the one in the video) and they failed randomness tests. Marsaglia tried with his xorshift generator but today we know they have relevant flaws. You can make good generator using this approach, such as the recent ones by Vigna (xoroshiro etc) but it's not so easy. It it were, we would have got good random number generators in 1965 and not in 1997 or so with the MT.
Maybe he meant to say 10 to 20 orders of magnitude.
Maybe (10 ^ 20) ???
closer to 10 to *the* 20 *th power* i guess
He literally did qualify it
"I'm going to initialize this at random." Hey look, you got your random number! I agree, the code was simple.
All PRNGs depend on a “seed”. If you are using it for non-adversarial purposes (simulations, games), use the current time. If you are using it for crypto (literally “hidden”) and are facing a potential attack, use a REAL random-number generator, like rolling dice, to generate the seed.
I implimented s 32-bit maximum LFSR for rand() in he 1970 C libfary for SDWTPc 6809 hobby omputer, and got roundly fritidised for not using a "proper" linear ongruential pseudorandom number generator. As you pointed out LFSR's are stati9sically excellent and more to he pointk very vey fast, particularly on s processor hat didn't have a hardware DIV iinstruction.
If you didn't catch the reference at 6:22 he's likely referring to Steve Mould, who explained flip flop chain logic.... Using actual flipflops on a chain.
I'm more inclined to interpret that as Steve Bagley (frequently seen on this channel too, works at the same university). I remember a video explaining computer memory by him as well from many years ago, featured a breadboard, some components and LEDs that light up along with a more schematic overview and tables explaining what the various gates do etc.
But such a project done by Steve Mould would certainly be interesting and weird as well.
That’s the content i’m looking for
Awww yiss I finally learned to implement an algorithm on my own *before* Computerphile had a video on it xD
Great video. Just want to point out that in the third line of the first set if operations, ~2:13 it says 1 xor 1 = 1. I could be wrong, but pretty sure that should be 0.
It is still correct on the paper, just wrong in the animation so not a big deal.
No, I thought that too, but if you watch it once more, you will notice, that last line in animation is output of previous line, which has 1 and 0 -> output is one. Zero as product of 1 and 1 is supposed to be on next line, which is not animated. It's just confusing at this speed, but it's correct.
Quite a fitting output given the release of the new Matrix trailer yesterday...
It's great at being totally random yet easy to break cryptographically.....that is an important distinction...thnx for pointing that out.
Legends say that XPS15 is still printing 1s and 0s today.
Had to implement this in System Verilog for an intro EE class!