I love the these kinds of videos. They probably have a limited audience but they will keep being educational for as long as TH-cam is in business and there will probably be new nerds wanting to learn about this stuff.
Yup. They might as well just say... buy whatever the people in Cupertino tell you that you need, grow a beard , get rid of last year's model, shave off beard when it's no longer in style, jump on you electric longboard and go buy what the people in Cupertino say you need this year, etc.
At it's most basic level this is how data encryption works. Both parties have extremely long shift registers, and only they know the feedback taps to the xor gates. When data is transmitted in a binary form (even if it started life as sound) it is passed through the shift register and what comes out the other end is totally encrypted. The data can then be broadcast with confidence that even if it is intercepted, no one else knows the feedback xor feedback taps and the large length of the shift register. Just have to keep those xor taps and shift register length secret!
That will be fine for - as you say - basic encryption. However, the problem with keeping such configurations secret is that - once busted - EVERYbody's messages (both future AND past) are available for inspection and decryption at your opponent's leisure. It is much safer to maintain the unpredictability in the message sender's seed/initial state, which can be varied for both every user and for every message. Most encryption algorithms are quite happy to publish - for all to see - their 'internal wirings' (in the form of S-boxes and hashing tables). This also has the advantage that many researchers can then test how secure the algorithm really is. One ought to be instantly suspicious of any company claiming security by keeping their algorithm secret.
Paul Sampson I tend to disagree to an a small extent with your statement. The feedback loops (I'm keeping this deliberately vague since I retired from my countries intelligence service), should be changed on a irregular, but frequent basis. There is of course the chance to change the register length if both parties are "in the know". As was proved by Turning, it was human error in not changing the Enigma wheels, that allowed him to crack the German code (and the British to ultimately thank him by chemically castrating him when they found out he was gay !) Modern computer power allowed intense data manipulation such that many cracks at the code can be achieved giving a fair chance of a good hit. Hence the almighty N.S.A. They can get at anything.
Just downloaded and tried logisim (pretty nice - thanks for the heads-up) and reproduced Julian's results! Now have switched it up to a twelve bit shift register (to represent the on/off of 12 semitones in an octave) with a button to set an initial state (e.g. Fmaj7 with 100010010001) and taking 6 taps from the output into a 6 input xor gate to generate a sequence of hexachords. Shall now have to build it!
Woohoo!!!! Thank You For That Amazing Video!!!! I have been waiting for this video and I'm glad I did, it was absolutely wonderfully weird and extremely in depth, interesting, educational, and entertaining!!!! Thanks for taking my request for a follow up on Linear Shift Registers!!!! I actually understood what you were doing even with my entry level understanding of electronics and that is what makes you an extremely valuable resource for anyone who wants to know more about everything electronics has to offer!!!!
The data sheet for the 74hc595 says its fine to connect SHCP and STCP together. If both clocks are connected together, the shift register will always be one clock pulse ahead of the storage register. You effectively get a 9 bit shift register with bit 0 hidden inside the chip.
Great stuff! We need all possible methods of teaching today's kids (with their Rubik's cubes and Walkman cassette players) about binary math, and I bet these experiments are just the ticket for some of the less mathematically inclined ones. Can't wait to see the follow-up(s) to this one!
Nice video, and very nostalgic for me, Julian, It's been a few decades since I studied LFSRs as part of my Electrical Engineering degree, and I've now retired. There IS a method for working out which feedback scheme, or schemes, will produce a maximal (pseudo-random) sequence, but I don't recall it now... Actually, I vaguely remember it involved long division of complex polynomial expressions... Seemed weird at the time, but don't quote me on that.
shift register can be made with only xor gates and some way of extending the signal. And obviously a clock! Such simple circuits! (especially in minecraft where its stupidly easy to add delay) then you can tack on any kind of extra features that you want. it could even be the heart of a simple calculator or who knows what else you could come up with! And with multiple shift registers in parallel and in series you can generate binary numbers and convert it into decimal or whatever you want.
LFSRs are used in CDMA wireless networks to generate long sequences of pseudo random digits (spreading codes) so that multiple users can all use the same bandwidth at the same time, i.e. each user looks like a source of (pseudo) random noise to the other. Clever stuff.
I made something like this, out of 4 74hc595shift registers, 2 pairs in series and the 2 series in parallel, in a closed loop with the posibila of adding 1s and 0s but instead of a xor gate chip I used a hex inverter chip to invert the data ST_CP and SH_CP.
Great video. Thanks! When all 9 leds are lit, is the 7555 "maxed out" ? Or did your led resistors take account of the available current when you built them?
Try hooking two audio-frequency 555 astable circuits up to the inputs of an XOR gate and fiddle with the frequencies. You get some awesome sounds out of it if you tune the two oscillators to different intervals.
Just ported the code to Arduino and breadboarded it. Refined the algorithm using a table of XOR masks for any shift length. Will publish the code and maybe a video soon.
Random doesn't always look random. When Apple introduced the iPod, people complained that 'shuffle' mode sometimes played the same track twice in succession, so they changed it to prevent that. They made it less random!
This was/(is) used within the pseudo-random signal generators(=digital white noise). There was even a time where you could buy such a thing already done in a single chip solution where the last stages have been accessible.
Right. I remember that chip, though I can't recall the number offhand. It's apparently not being produced any more. From what I can recall in terms of discussions around the subject of electronic music synthesizers, you really didn't want to use one of those because the sequence they chose to implement that particular chip was *way* too short, and you could hear it repeat! Not the sort of thing that you want in a noise source...
Hi Julian! I really enjoy your channel, especially the post bags! I was just wondering what logic IC's you would recommend I should stock up on for learning digital logic? thanks, Dale
Thanks for that I really enjoyed it. I love seeing binary logic in action and you explained it very well. Hopefully there will be more videos on the same theme. Oh and when are the pic videos coming? looking forward to them.
Presumably if you start off the '6-stater' with a pattern already in one of the remaining nine possibilities, you'll end up in a new sequence. Which may be of length nine, or maybe another shorter one with a third possible sequence, or [etc]?
I tried another pattern - by powering off and feeding in 0001. Produces a completely different 6-state pattern. But that leaves 3 states unaccounted for - weird!
For a given shift length and feedback taps, the sequence is always the same, for any starting pattern, cycling back to the initial state after 2^n-1 steps. You must use a valid set of taps in order to get a maximal length shift. The sequence appears pseudo-random, but it repeats exactly the same sequence each time.
Will be interesting to see where you're going with this. Great introduction to binary logic. Someone else mentioned encryption and it kinda reminds me of the enigma machine. Did the end of the video get cut off mid-sentance or is that just me?
An unrelated question to anyone reading this.... is there a "breakout board" or such thing that I can put between the GPIO inputs of a Raspberry Pi and say 12 VDC? I need to know when a 12 VDC input is either on or off. I don't want to use relays with coils and I'm sure there is a more elegant method. Any help is appreciated!
Yes, opto-isolators....but wondering if there is a multi-channel (say 12) prepackaged board that had 12 volt input to 3.3 volt out to interface with the RasPi GPIO that anyone knows of.
golf-n-guns If you don't need isolation then just use resistor dividers; one for each input: 10k resistor from 12V source to Arduino I/P pin 3k6 resistor from Arduino I/P pin to ground, dropping the 12V to 3.2V, or you could replace 3k6 resistor with 1N4728 3.3V zener diode to clamp the input to 3.3V
Thank you for your reply. I'll keep searching a bit for an off-the-shelf solution...and if none is found, I'll have to cobble something up using your suggestions. Thanks again.
Hi Julian, Thanks for the channel, I find it quite informative and worth the subscription! :) I had a thought while watching this video - could one substitute the 16MHz crystal oscillator that is used with an ATMEGA328P (Arduino UNO) with a 555 timer. Thought this could be a very nice video for you to produce as it seems like it is very much up your alley. I know that the limit of a 555 timer is 500kHz, but perhaps some sort of multiplier circuit could be employed? Does it seem like a worthy/feasible investigation to you? Thanks, Dylan
What does the other clock phase do ? Is it two clocks for shift, load, shift, load, and so on ? I tried the 4 bit LFSR with taps on bits 0 and 2 like yours but in logisim. Got the same sequence. Wondered what happened if you feed in another number than what is in the sequence. If you put 1000, the 1 will just shift out and the LFSR stops. Makes sense :)
If you clock the shift register and the storage register together, the outputs don't show the current shift register data. I could have used a delayed pulse for the storage register - I was considering 6 inverters in series to produce a few nanoseconds of propagation delay, but inverting the clock was easier. Putting 1000 into the 4-bit LFSR (with taps at 0 and 2) produces a completely different 6-state sequence. That still leaves 3 states unaccounted for. Fascinating :)
bwack All possible numbers, except zero, are in the maximum length sequence. It makes no difference which number you start with. The sequence is always the same.
That's the point. Moving the wires to invalid tap positions is not maximal length, so it's just an ordinary shift register with a meaningless feedback loop and of no practical use.
No, it is still an LFSR with pseudo random sequence. My point was that some seeds outside this sequence and other than zero will not result in a loop. They can be practical. If you see one of Julians earlier videos on the subject he traded shorter machine code for maximum length. It was not critical for him to do that in anyway, but it was possible, and it didn't make any practical difference. That is good enough for me. Allthough I do agree about your previous post regarding that the sequence is always the same, but thats just a fact and another diversion from my original point. I would normally stop here, but you have stepped over one of my main principles in design practices, and that is to consider everything even if they may seem useless or not optimal at current time.
Too much for me to understand fully but guessing kurnaugh mapping patterns might fit into the subject somewhere also a difficult subject to understand.
Great Julian. Thanks! You don't happen to know the math behind this, do you? Not just looking up the taps in a table but to do the actual math... Complicated, indeed.
I'm not sure there is any formula for this - just observation and/or simulation. As you say, there are tables for maximal length sequences, but I've not seen any documentation for the shorter sequences (hence my surprise at witnessing a 6-state sequence). When you get to 8-bits, things get interesting - there are no maximal length sequences (255 states) using just 2 taps - you need 4 taps. It's mind boggling.
Right! Simulation was my best bet for making the tables. That it brute force. Perhaps this is like large prime numbers? "Impossible" to calculate (as of yet) without brute force. :)
Not quite true Julian. You can have as few as 2 stages and a sequence length of 3. With longer sequences, prime numbers start coming into it and you can reduce the polynomial terms. You never need more than 4 taps, sometimes only 2 or 3, at least as far as 168 stages - I need to check that as a different source gives conflicting information. All (?) the high number stages have many possible arrangements of (large numbers of) taps, all giving a maximal length sequence, but they all reduce to just a few taps. See: www.xilinx.com/support/documentation/application_notes/xapp052.pdf Page 5 gives the shortest taps for n=3 to n=168 using XNOR logic which is easier to implement.
Another interesting video as always. On an unrelated subject, have you ever used the 5V Mini USB Lithium Battery Charging Board Charger Module available from alice and if so are they any good?
That's the TP4056. Pretty good, although the 4.2V varies from device to device (maybe that's because they're fake chips). There's also a version with cell protection and another version with multiple chips in parallel.
Maybe you should make your life easier, and give yourself the option to interrupt the clock from the 555 and manually send the clock pulse with a second button instead...
Just need an Arduino, LEDs and some C code... include int main(void) { uint16_t start_state = 0xACE1u; /* Any nonzero start state will work. */ uint16_t lfsr = start_state; uint16_t bit; /* Must be 16bit to allow bit 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5) ) & 1; lfsr = (lfsr >> 1) | (bit
Peter D Morrison Gave you the thumbs up. Good choice of feedback terms, and spot on math. I don't know the Arduino but I cannot see any output to LED's. You probably left the code out because it was obvious. Two things did catch my eye though, and they may be processor based, a) what is "period" counting ? Once the subroutine has returned that value is lost. And b) why do you return a '0' or FALSE from your subroutine ? Would that not indicate that not indicate that it had failed ? Please don't take this as harsh judgement, I like to understand other people's code, especially if it has been written for a processor I'm unfamiliar with. Thanks.
Returning 0 as an OK status is very common in the unix/linux universe. A large number of failure modes may be distinguished by a correspondingly large number of possible return values, often by setting bits, as opposed to the only one way you care about something's success. The 'main' subroutine will return only when lfsr reaches start_state again. Which - with the suitable feedback 'wiring' - will happen when the entire de Bruijn sequence (of all possible binary values) has been traversed. LED lighting on an arduino is - as you surmise - fairly simple but may require a multiplexer if done on an uno (not so great with the number of available pins). It would of course also require an i/o method to xor (in and out) an actual source message if you wanted to use it for encryption.
Not really. In Gray Code, successive numbers differ by only one binary digit. It was originally designed to prevent 'noise' from electromechanical switches causing spurious output states.
'exclusive or' can be nicely translated into human language, it is essentially 'either, or'. _Either_ the first _or_ the second input is set, then there is a one output. If both are set or none is set, then this does not fulfill the either/or criteria.
Hi in the OR gate one of the input should be 1 at least to get 1 at the output. Let's say x and y are inputs so the truth table will be: x y output 1 1 1 1 0 1 1 1 0 0 0 0 but the XOR gate the input should be different from each other to get 1 at the output. Let's say x and y are input so: x y output 0 1 1 1 0 1 1 1 0 0 0 0 I hope I helped you :)
Julian Ilett Henner Zeller xAbdulRhman X Thank You. That helped me a lot. Now i know what i'm goig to do tomorrow :) And for excclusive and it is: 0 0 > 1 0 1 > 0 1 0 > 0 1 1 > 1 am I right?
I love the these kinds of videos. They probably have a limited audience but they will keep being educational for as long as TH-cam is in business and there will probably be new nerds wanting to learn about this stuff.
Agreed. Videos about the iPhone 7 (for example) must have a very short shelf life.
Yup. They might as well just say... buy whatever the people in Cupertino tell you that you need, grow a beard , get rid of last year's model, shave off beard when it's no longer in style, jump on you electric longboard and go buy what the people in Cupertino say you need this year, etc.
At it's most basic level this is how data encryption works.
Both parties have extremely long shift registers, and only they know the feedback taps to the xor gates.
When data is transmitted in a binary form (even if it started life as sound) it is passed through the shift register and what comes out the other end is totally encrypted. The data can then be broadcast with confidence that even if it is intercepted, no one else knows the feedback xor feedback taps and the large length of the shift register.
Just have to keep those xor taps and shift register length secret!
That will be fine for - as you say - basic encryption. However, the problem with keeping such configurations secret is that - once busted - EVERYbody's messages (both future AND past) are available for inspection and decryption at your opponent's leisure. It is much safer to maintain the unpredictability in the message sender's seed/initial state, which can be varied for both every user and for every message. Most encryption algorithms are quite happy to publish - for all to see - their 'internal wirings' (in the form of S-boxes and hashing tables). This also has the advantage that many researchers can then test how secure the algorithm really is. One ought to be instantly suspicious of any company claiming security by keeping their algorithm secret.
Paul Sampson I tend to disagree to an a small extent with your statement. The feedback loops (I'm keeping this deliberately vague since I retired from my countries intelligence service), should be changed on a irregular, but frequent basis. There is of course the chance to change the register length if both parties are "in the know".
As was proved by Turning, it was human error in not changing the Enigma wheels, that allowed him to crack the German code (and the British to ultimately thank him by chemically castrating him when they found out he was gay !)
Modern computer power allowed intense data manipulation such that many cracks at the code can be achieved giving a fair chance of a good hit. Hence the almighty N.S.A. They can get at anything.
:)
There are a lot of others ways of designing a cipher. For example I made one (with Logisim) that uses RAM blocks, counters, and a lot of XORs
Just downloaded and tried logisim (pretty nice - thanks for the heads-up) and reproduced Julian's results! Now have switched it up to a twelve bit shift register (to represent the on/off of 12 semitones in an octave) with a button to set an initial state (e.g. Fmaj7 with 100010010001) and taking 6 taps from the output into a 6 input xor gate to generate a sequence of hexachords. Shall now have to build it!
Woohoo!!!! Thank You For That Amazing Video!!!! I have been waiting for this video and I'm glad I did, it was absolutely wonderfully weird and extremely in depth, interesting, educational, and entertaining!!!!
Thanks for taking my request for a follow up on Linear Shift Registers!!!! I actually understood what you were doing even with my entry level understanding of electronics and that is what makes you an extremely valuable resource for anyone who wants to know more about everything electronics has to offer!!!!
Thank you. You made it easy to understand what was happening while it was happening.
i wish i understood shift registers and and/or/nor gates better. thanks for the video, Julian.
Great video! The applications for this are wonderful for me! Thanks for making this.
The data sheet for the 74hc595 says its fine to connect SHCP and STCP together. If both clocks are connected together, the shift register will always be one clock pulse ahead of the storage register. You effectively get a 9 bit shift register with bit 0 hidden inside the chip.
Great stuff! We need all possible methods of teaching today's kids (with their Rubik's cubes and Walkman cassette players) about binary math, and I bet these experiments are just the ticket for some of the less mathematically inclined ones. Can't wait to see the follow-up(s) to this one!
Julian, I really find this type of tutorial very interesting. Thank you for presenting.
Nice video, and very nostalgic for me, Julian, It's been a few decades since I studied LFSRs as part of my Electrical Engineering degree, and I've now retired. There IS a method for working out which feedback scheme, or schemes, will produce a maximal (pseudo-random) sequence, but I don't recall it now... Actually, I vaguely remember it involved long division of complex polynomial expressions... Seemed weird at the time, but don't quote me on that.
If you crank up the clock speed and connect a speaker, you can get some interesting sounds and noises out of it
this was a good and informative video. I liked it. will look forward for more of these
Nice channel,,,
find so rare video that explains shift register..
Thank you..
shift register can be made with only xor gates and some way of extending the signal. And obviously a clock! Such simple circuits! (especially in minecraft where its stupidly easy to add delay)
then you can tack on any kind of extra features that you want. it could even be the heart of a simple calculator or who knows what else you could come up with! And with multiple shift registers in parallel and in series you can generate binary numbers and convert it into decimal or whatever you want.
LFSRs are used in CDMA wireless networks to generate long sequences of pseudo random digits (spreading codes) so that multiple users can all use the same bandwidth at the same time, i.e. each user looks like a source of (pseudo) random noise to the other. Clever stuff.
From the title I thought this was going to be a CRC calculator! We simulated one in my VHDL course using a shift register and several xor gates.
Julian - any chance you could show a clear photo of that layout. Wouldn't mind building it myself. Thanks :)
I made something like this, out of 4 74hc595shift registers, 2 pairs in series and the 2 series in parallel, in a closed loop with the posibila of adding 1s and 0s but instead of a xor gate chip I used a hex inverter chip to invert the data ST_CP and SH_CP.
Great video. Thanks! When all 9 leds are lit, is the 7555 "maxed out" ?
Or did your led resistors take account of the available current when you built them?
Alun Wall the 7555 doesn't drive the LEDs, just provides the clock for the shift register. That drives the LEDs, one per stage, through resistors.
Peter D Morrison Of course, I see that now. Thanks a lot.
love this stuff - takes me back 30 years or more. Encryption needs randomness...
Try hooking two audio-frequency 555 astable circuits up to the inputs of an XOR gate and fiddle with the frequencies. You get some awesome sounds out of it if you tune the two oscillators to different intervals.
That sounds like fun :)
amazing video! thank you very much!
iv played alot with the 74hc595 with ardiunos and led displays neat little chip
Just ported the code to Arduino and breadboarded it. Refined the algorithm using a table of XOR masks for any shift length. Will publish the code and maybe a video soon.
That would be interesting - I'd like to watch that :)
In your opinion what is the best 6 cell 18650 battery bank that doesn't require soldering? Thanks and keep making these awesome videos
The decimal numbers look random, but the binaries don't.
Yeah, true. The LFSR produces "runs" of ones and zeros - these are very visible as they shift upwards through the shift register.
You could always change the order of the LEDs to avoid those runs.
Random doesn't always look random. When Apple introduced the iPod, people complained that 'shuffle' mode sometimes played the same track twice in succession, so they changed it to prevent that. They made it less random!
Could you do this with an 8 bit counter, and add a resistor to each leg of a different value, then feed them into an LED for a realistic flicker?
of course :)
Nice : D , I use the C6C595 version in most of my numitron clocks along with the 74HC595 in some
This was/(is) used within the pseudo-random signal generators(=digital white noise). There was even a time where you could buy such a thing already done in a single chip solution where the last stages have been accessible.
Right. I remember that chip, though I can't recall the number offhand. It's apparently not being produced any more. From what I can recall in terms of discussions around the subject of electronic music synthesizers, you really didn't want to use one of those because the sequence they chose to implement that particular chip was *way* too short, and you could hear it repeat! Not the sort of thing that you want in a noise source...
Hi Julian! I really enjoy your channel, especially the post bags! I was just wondering what logic IC's you would recommend I should stock up on for learning digital logic?
thanks,
Dale
Thanks for that I really enjoyed it. I love seeing binary logic in action and you explained it very well. Hopefully there will be more videos on the same theme. Oh and when are the pic videos coming? looking forward to them.
Thanks Colin. PIC videos coming soon, just got to get my shizzle together.
If memory serves me right, LFSRs are used to generate pseudo random binary digits for encryption, right?
Presumably if you start off the '6-stater' with a pattern already in one of the remaining nine possibilities, you'll end up in a new sequence. Which may be of length nine, or maybe another shorter one with a third possible sequence, or [etc]?
I tried another pattern - by powering off and feeding in 0001. Produces a completely different 6-state pattern. But that leaves 3 states unaccounted for - weird!
Looks like (using logisim - thanks Integrated Electronics!) you get your two hexacycles and a tricycle (6 11 13) to pick up the remaining three.
Julian Ilett if it's a Maximum Length LFSR, with the correct XOR terms then you will always get n2-1 unique states.
For a given shift length and feedback taps, the sequence is always the same, for any starting pattern, cycling back to the initial state after 2^n-1 steps. You must use a valid set of taps in order to get a maximal length shift. The sequence appears pseudo-random, but it repeats exactly the same sequence each time.
Will be interesting to see where you're going with this. Great introduction to binary logic.
Someone else mentioned encryption and it kinda reminds me of the enigma machine.
Did the end of the video get cut off mid-sentance or is that just me?
James Searle Just you. He ends with "For the moment, cheerie-o!"
Windshield Thanks, must have just been TH-cam playing up for me, it's fine now.
An unrelated question to anyone reading this.... is there a "breakout board" or such thing that I can put between the GPIO inputs of a Raspberry Pi and say 12 VDC? I need to know when a 12 VDC input is either on or off. I don't want to use relays with coils and I'm sure there is a more elegant method. Any help is appreciated!
Opto-isolators?
Resistors? :-)
Yes, opto-isolators....but wondering if there is a multi-channel (say 12) prepackaged board that had 12 volt input to 3.3 volt out to interface with the RasPi GPIO that anyone knows of.
golf-n-guns If you don't need isolation then just use resistor dividers; one for each input:
10k resistor from 12V source to Arduino I/P pin
3k6 resistor from Arduino I/P pin to ground, dropping the 12V to 3.2V,
or you could replace 3k6 resistor with 1N4728 3.3V zener diode to clamp the input to 3.3V
Thank you for your reply. I'll keep searching a bit for an off-the-shelf solution...and if none is found, I'll have to cobble something up using your suggestions. Thanks again.
Hi Julian, I followed it all meticulously. Very interesting. Had you prepared this for one of your projects ?
What happens in the mode "keeping the button pressed"?
Hi Julian,
Thanks for the channel, I find it quite informative and worth the subscription! :)
I had a thought while watching this video - could one substitute the 16MHz crystal oscillator that is used with an ATMEGA328P (Arduino UNO) with a 555 timer. Thought this could be a very nice video for you to produce as it seems like it is very much up your alley. I know that the limit of a 555 timer is 500kHz, but perhaps some sort of multiplier circuit could be employed?
Does it seem like a worthy/feasible investigation to you?
Thanks,
Dylan
What does the other clock phase do ? Is it two clocks for shift, load, shift, load, and so on ? I tried the 4 bit LFSR with taps on bits 0 and 2 like yours but in logisim. Got the same sequence. Wondered what happened if you feed in another number than what is in the sequence. If you put 1000, the 1 will just shift out and the LFSR stops. Makes sense :)
If you clock the shift register and the storage register together, the outputs don't show the current shift register data. I could have used a delayed pulse for the storage register - I was considering 6 inverters in series to produce a few nanoseconds of propagation delay, but inverting the clock was easier.
Putting 1000 into the 4-bit LFSR (with taps at 0 and 2) produces a completely different 6-state sequence. That still leaves 3 states unaccounted for. Fascinating :)
bwack All possible numbers, except zero, are in the maximum length sequence. It makes no difference which number you start with. The sequence is always the same.
Peter D Morrison the not maximum length sequence. 17:50
That's the point. Moving the wires to invalid tap positions is not maximal length, so it's just an ordinary shift register with a meaningless feedback loop and of no practical use.
No, it is still an LFSR with pseudo random sequence. My point was that some seeds outside this sequence and other than zero will not result in a loop. They can be practical. If you see one of Julians earlier videos on the subject he traded shorter machine code for maximum length. It was not critical for him to do that in anyway, but it was possible, and it didn't make any practical difference. That is good enough for me. Allthough I do agree about your previous post regarding that the sequence is always the same, but thats just a fact and another diversion from my original point. I would normally stop here, but you have stepped over one of my main principles in design practices, and that is to consider everything even if they may seem useless or not optimal at current time.
I would've liked to know where this bus was going.
Give us a whole TTL porn series
from very basic to astronomical circuits!
Too much for me to understand fully but guessing kurnaugh mapping patterns might fit into the subject somewhere also a difficult subject to understand.
nice.
Great Julian. Thanks! You don't happen to know the math behind this, do you? Not just looking up the taps in a table but to do the actual math... Complicated, indeed.
I'm not sure there is any formula for this - just observation and/or simulation. As you say, there are tables for maximal length sequences, but I've not seen any documentation for the shorter sequences (hence my surprise at witnessing a 6-state sequence). When you get to 8-bits, things get interesting - there are no maximal length sequences (255 states) using just 2 taps - you need 4 taps. It's mind boggling.
Right! Simulation was my best bet for making the tables. That it brute force. Perhaps this is like large prime numbers? "Impossible" to calculate (as of yet) without brute force. :)
Not quite true Julian. You can have as few as 2 stages and a sequence length of 3. With longer sequences, prime numbers start coming into it and you can reduce the polynomial terms. You never need more than 4 taps, sometimes only 2 or 3, at least as far as 168 stages - I need to check that as a different source gives conflicting information. All (?) the high number stages have many possible arrangements of (large numbers of) taps, all giving a maximal length sequence, but they all reduce to just a few taps. See: www.xilinx.com/support/documentation/application_notes/xapp052.pdf
Page 5 gives the shortest taps for n=3 to n=168 using XNOR logic which is easier to implement.
Another interesting video as always. On an unrelated subject, have you ever used the 5V Mini USB Lithium Battery Charging Board Charger Module available from alice and if so are they any good?
The 2A charger?
That's the TP4056. Pretty good, although the 4.2V varies from device to device (maybe that's because they're fake chips). There's also a version with cell protection and another version with multiple chips in parallel.
Okay thanks Julian, I just bought a couple to play with as they are so cheap, I'll check out the other versions as well.
thanks Glebs Litvjaks, that is exactly what I was thinking of using them for, thanks for the heads up regarding polarity.
I hope you swiped up all the ones that dropped out the end and made a mess on the workshop floor!
That's what the bit bucket is for...! :-)
8:13 sequense is 1,3,2. you cant input 3 in that on first clock, but its same anyway :) 8:41 after click 1,3,2 :)
How do you shape and cut your wire that neatly? #wireworkmaster
Maybe you should make your life easier, and give yourself the option to interrupt the clock from the 555 and manually send the clock pulse with a second button instead...
did you just say 755 timer? confused by all the 74xx series logic? :P
ah okay I was confused by the 7 for a 'bit'!
🤔 yep thats the roots of PRBS (pseudo random binary sequence) , imagine going to the 31st power, that is some seriously insane material for yall
Standard PRBS for testing digital line transmission is 2^23-1.
Twotone we use prbs31 for otn testing though 😉
otn?
Twotone Optical Transport Network , you know , nothing fancy, 40, 100 , 400 Gbps
Oh yeah, that stuff. ;) Only done 1Gig myself. Whose network?
I bet you think the world is a globe and gravity exists too :-)
Do you smell that silver button?
// Just one line of code inside the loop:
lfsr = (lfsr >> 1) ^ (-(lfsr & 1u) & xorMask);
// Galois Algorithm - more efficient than Fibonacci
How about a finite state machine next?
It would be great to make a state machine (Turing machine) out of a 2716 EPROM and registers.
Just need an Arduino, LEDs and some C code...
include
int main(void)
{
uint16_t start_state = 0xACE1u; /* Any nonzero start state will work. */
uint16_t lfsr = start_state;
uint16_t bit; /* Must be 16bit to allow bit 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5) ) & 1;
lfsr = (lfsr >> 1) | (bit
Peter D Morrison Gave you the thumbs up. Good choice of feedback terms, and spot on math. I don't know the Arduino but I cannot see any output to LED's. You probably left the code out because it was obvious.
Two things did catch my eye though, and they may be processor based, a) what is "period" counting ? Once the subroutine has returned that value is lost. And b) why do you return a '0' or FALSE from your subroutine ? Would that not indicate that not indicate that it had failed ?
Please don't take this as harsh judgement, I like to understand other people's code, especially if it has been written for a processor I'm unfamiliar with.
Thanks.
Returning 0 as an OK status is very common in the unix/linux universe. A large number of failure modes may be distinguished by a correspondingly large number of possible return values, often by setting bits, as opposed to the only one way you care about something's success.
The 'main' subroutine will return only when lfsr reaches start_state again. Which - with the suitable feedback 'wiring' - will happen when the entire de Bruijn sequence (of all possible binary values) has been traversed. LED lighting on an arduino is - as you surmise - fairly simple but may require a multiplexer if done on an uno (not so great with the number of available pins).
It would of course also require an i/o method to xor (in and out) an actual source message if you wanted to use it for encryption.
Nigel James thanks for the 👍. All points well taken. The code is just a proof of concept. Needs refining for an actual working model.
4th.... Binary subject, right?
so... confused... watermelons...
So close.
Loom bands at the ready ;)
You didn't say "eleven"!
You're learning :P
I didn't say "fleventy five" either, but it's gonna happen :)
Julian Ilett I look forward to it! :D
Almost like gray code
Not really. In Gray Code, successive numbers differ by only one binary digit. It was originally designed to prevent 'noise' from electromechanical switches causing spurious output states.
Ver interesting.
A not so random encoding technique in hardware.
Great video, not spooky at all.
Can you tell me what the difference between an _or_ and a _xor_ gate is?
Thanks.
And if you want to make cirquit diagrams try easyeda.com
Yeah
OR
00 - 0
01 - 1
10 - 1
11 - 1
XOR
00 - 0
01 - 1
10 - 1
11 - 0
So they only differ for the 11 input combination
'exclusive or' can be nicely translated into human language, it is essentially 'either, or'. _Either_ the first _or_ the second input is set, then there is a one output. If both are set or none is set, then this does not fulfill the either/or criteria.
Hi
in the OR gate one of the input should be 1 at least to get 1 at the output. Let's say x and y are inputs so the truth table will be:
x y output
1 1 1
1 0 1
1 1 0
0 0 0
but the XOR gate the input should be different from each other to get 1 at the output. Let's say x and y are input so:
x y output
0 1 1
1 0 1
1 1 0
0 0 0
I hope I helped you :)
Julian Ilett Henner Zeller xAbdulRhman X Thank You. That helped me a lot. Now i know what i'm goig to do tomorrow :)
And for excclusive and it is:
0 0 > 1
0 1 > 0
1 0 > 0
1 1 > 1
am I right?
There is no logic gate called XAND. But the truth table that you wrote is for XNOR gate
0 0 > 1
0 1 > 0
1 0 > 0
1 1 > 1
Ah, a quick look into the "mind" of a Cylon scanning unit. Anyone up for a Knight ride?
Kitt built of course.
Mike (o\!/o)
first
I'm afraid your videos are starting to get boring