XOR & the Half Adder - Computerphile
XOR, an essential logic operation, explained by Professor Brailsford. Continues our series on logic gates/operations.
AND OR NOT - Logic Gates Explained: • AND OR NOT - Logic Gat...
Binary Addition & Overflow: • Binary Addition & Over...
Capturing Digital Images (The Bayer Filter) : • Capturing Digital Imag...
Flip Flops, Latches & Memory Details: • Flip Flops, Latches & ...
The Virtual Reality Cave: • The Virtual Reality Ca...
XOR Easter Egg: • XOR Easter Egg - Compu...
The Professor's Notes: bit.ly/1BZARJI
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com
Пікірлер: 323
"XOR and the Half Adders" is surely a good name for a band.
@natb007
5 жыл бұрын
Darren Landrum but would the members play anything else than keys?
@MikeOnYoutube123
5 жыл бұрын
MAsYna Tutnga
@MikeOnYoutube123
5 жыл бұрын
Mi do nit czree
@MikeOnYoutube123
5 жыл бұрын
He is on
@MikeOnYoutube123
5 жыл бұрын
Dlaczego?
He came so close but I wish he would have explained that a 'full adder' is basically two half-adders plus an OR gate.
I spent 40 minutes of a lecture completely lost on this until my professor threw this video on "since he finished early" (he was lecturing at Mach 10, no wonder). Professor Brailsford is absolutely charming and explains things perfectly, with just enough fluff to hold interest but without veering off track. Thank you for the video, and I'm looking forward to binge-watching this channel in the near future.
@theuseraccountname
4 жыл бұрын
@PIYUSH YADAV Someone doesn't understand hyperbole.
@grn1
3 жыл бұрын
I am currently in the process of binge watching this channel.
This better explained in 9 minutes what a half adder is than my professor could explain in 60.
@vivienne_lavida
8 жыл бұрын
yep
@EngineeringNibbles
7 жыл бұрын
gotta go fast
@alenp6335
7 жыл бұрын
same
@rockydo2307
7 жыл бұрын
ikr, youtube has taught me more about for major than the teachers have at my uni for sure.
@coltonshoquist9077
7 жыл бұрын
YES! I agree!!!
1:35 Drawing the XOR gate in a logic diagram 2:30 Different names for an XOR gate 2:40 3-bit binary adder example 3:10 Example binary adder (without carrying) 3:45 Considering XOR with carry over 4:10 Drawing a logic diagram for a 1-bit part binary adder (or 'half adder') 5:05 How to generate the carry out bit 6:45 Full 1-bit adder 8:17 Overall truth table for all 8:53 Summary and round-up
Good lord I love this man! Great energy and zeal. I wish i had professors like Prof. Brailsford in my formative years.
I could listen to this guy all day!
@woodywoodlstein9519
4 жыл бұрын
Same.
@woodywoodlstein9519
4 жыл бұрын
I can’t believe how Smart the guy is. How much is in that head.
@TheGamer-hd4ef
3 жыл бұрын
yeah you could but obviously you're not :P
Wait a minute. I'm out of redstone.
@asaffisher8890
8 жыл бұрын
Lol
@billyanderson2858
3 жыл бұрын
ÀAAaaàÀà@@asaffisher8890
@t-rex1488
3 жыл бұрын
i have like two stacks of torches though...
This professor does an outstanding job of explaining. I used to program in 8080 and Z-80 assembly language and I learned a few things here myself. That's a very nice, clean way to do a half-adder.
@DennisHolmberg-sl1hz
8 ай бұрын
6502 on my side, they chose EOR, a carry over from Motorola's 6800 instruction set when Chuck Peddle skunk-worked MOS Technology from them; same instruction though.
Computerphile makes my brain happy.
bad memories came to my mind while watching this Video... just 2 month before I build an 8 bit binary full adder only with BC547 transistors, 10 and 1k resistors as a school project. I have to say: So many things can go wrong. It's just a pain in the back. especially when you only have 3 weeks and have to go to school. but in the end it worked. Now I'm worried about my grade :DUpdate: got an A+ :DD
@yousorooo
9 жыл бұрын
Fortunately I only had to build a 32bit ALU in verilog.
@GregoMorgan
9 жыл бұрын
Derek Leung Just got out of a 16 bit carry lookahead adder in VHDL
@NerdNordic
9 жыл бұрын
Heh, do "From nand to tetris" -that's fun. "Oh, just build a computer"...
@BGBTech
9 жыл бұрын
Markus Mines I have done a small amount of transistor logic using 2N3904 transistors, but they are rated for slightly higher current (NPN, 250mA);also some 2N2222A transistors (NPN, 800mA);and MJE3055T (NPN, 8A);and IRF540N (N-MOSFET, 33A).usually, the smaller transistors are for signaling and logic, and bigger transistors are for driving loads (such as electric motors).a lot of it is mixed digital and analog electronics, with parts operating at different voltages (3.3v, 5v, 12v, and sometimes higher, ex, 15v-24v).transistor logic isn't really fun, much easier to do any non-trivial logic using microcontrollers or a Raspberry Pi or similar... (leaving the discrete electronics mostly to non-logic tasks).wouldn't look forward to building complex digital circuits with transistors.most complex I built was a circuit for running bipolar stepper motors with transistors (sadly/ironically, thus far works better than my attempts at using driver ICs).NPNs are good for small digital circuits, and have good properties for analog, but the drawback of generating considerable amounts of heat. a few of my NPN-based circuits (simple analog logic) are actually insulated with silicone caulk and run while submerged in water for this reason, and may actually cause the water to start boiling off the transistors while running (yes, actually built the thing to run underwater...).MOSFETs, however, are more expensive and don't deal as well with analog signals (in a simple sense, they like to behave more like on/off switches).well, and of course, a lot of this stuff is wire-wrap (typically with 24 gauge wire, or thicker for higher loads), and a lot of resistors, capacitors, and a few ICs and other things in the mix as well...but, it is worthwhile I guess...
@ntwede
8 жыл бұрын
+Brendan Bohannon The npn transistors you use for digital logic that give off heat, are you using resistors for that? It shouldn't overheat like that for simple digital logic.
This guy is AWESOME, I love his explanations, and his demeanor all together great.
I just love this professor. After all these years, he is still so excited about computers.
Every video with Prof. Brailsford in it gets an instant thumbs up from me :)
I just wanted to thank you for taking the time to do this. I really appreciate this video.
Perfectly constructed video, well done Prof!
Taking a class where we have to build these and test them on a circuit. Very helpful video. Thank you!
Wow, this is an amazing description of the half adder. Really enjoyed this video!
I've implemented a 8bits full-adder in Minecraft, that helped me A LOT ! :)
@NerdNordic
9 жыл бұрын
I did a 24 bit full - adder, why 24? Because it got real boring after 23... ;)
@jena_thornwyrd
9 жыл бұрын
hmmm, without mod, I doubt, you would have been out of chunk loaded area :)
@NerdNordic
9 жыл бұрын
Ya, you're probably right, must have been half-adders, I don't remember, my bad (Still got boring after 24):)
@jena_thornwyrd
9 жыл бұрын
XD
@NerdNordic
9 жыл бұрын
kanethornwyrd On second thought, I think I got a full adder to work in like 9x5 blocks or something. But I might be mistaken ;)
This guy is the best. Putting in my application for Grandson right now.
Fantastic communicator and teacher -- thank you
Excellent video for basic logic gates.
This guy is such an amazing teacher
I never been so excited about a Half Binary Adder :)
I remember learning about XOR in electronics and graphics when I was a kiddie. I thought it was SO amazing. Drawing moire-patterns and trying to make a full adder... oh happy days.
this video changed my life
beautiful beautiful video understood straight away
thanks, you are such a great proffesor
so helpful, best explanation ever- really going to help with my exams :))
this video is a gem 💎
I think it will be a great followup to this series if it is explained why a four bit adder is more efficient than adding up four full adders and what is the most efficient adder.
This is a fantastic video
Absolutely fantastic! Thank-you for sharing! :)
I've started working with assembly about a month ago. Learned to love the xor operation. swap 2 registers? xor that shit. set a register to 0? xor that shit. modulo(2^n)? xor that shit! Also if you look at the table for the fulladder you can actually read it as binary number. bin:1 1 1 = 11 dec:1+1+1 = 3 bin:1 0 1 = 10 dec:1+0+1 = 2 So you can very easily see that the circuit is in fact a fulladder :)
My jaw dropped when he did the addition. I can't believe that works
Brilliant teacher
This is the best thing ever
yess!!!! my favorite topic logic gate how the magic works!!!! i subscribed because of this video! and liked!
Loved this video!! Loved Loved LOVED this video. ❤️👍🏻😁
I'm surprised there was no mention that XOR on {0, 1} forms an abelian group. It is the only logical operation that has such a nice structure afaik
Love this guy.
Such a nice way of presenting these logical operations. Unfortunately, at least for me, in school ,they didn't get presented as nice, felt a bit more complicated than it really is and less interesting.
My only complaint is HE ALWAYS GETS HIS HANDS IN THE WAY WHEN I TRY TO PAUSE TO SEE THE SCHEMATIC lol
@airthrow
7 жыл бұрын
wishcraft4u2 LOL I had to pause the truth table a few times to make sure I understood it all too. He's an excellent teacher!
@AdrX003
3 жыл бұрын
hehe i can get it if i watch for like 2 to 4 times
@CreeperSlenderman
3 жыл бұрын
Blame camera's pos
this guy is great.
I love this professor :D
demasiado claro!!
For over a year I have been playing a video game with logic gates in it and I made a bunch of simple games like tic tac toe and dots and boxes but I could never figure out how to make a calculator and now just looking at videos for fun I see this explaining how to do simple addition with logic gates.
Nice. Now blow everyone's minds with the SR and type D latches.
I've thought of a way to make a half adder using only 3 gates. A xor gate is made from a or gate with the inputs tied to a Nand gate controlling the output. If you replace the carry out with a signal from the and gate before it is inverted. I have tested this shortcut in Minecraft with success.
@dojelnotmyrealname4018
7 ай бұрын
I know it's 5 years later, but the problem with this idea is that an or gate in itself is 4 nand gates(you need to invert both inputs and output) or 2 nor gates(invert the output). There is no way to electronically do an or gate directly. So while you are correct in a sense that an half-adder can be done in three operations, unfortunately one of those operations requires 4 gates to do. TL;DR Yes, as long as you ignore the fact that the OR gate is actually 4 NAND gates, since we can't make an OR gate directly, unlike a NAND or NOR gate.
I love the video thumbnail with the half snake (indeed a half adder) :D :D
I've often seen XOR notation use the '^' symbol, e.g. A ^ B. I'm surprised that one was left out. It's very common in programming languages.
@cmyk8964
2 жыл бұрын
@Connor Gaughan Actually, that’s (A∨B)∧¬(A∧B). ∧ and ^ are different symbols.
Is Bill Gates a logic gate?
@mousefrust
7 жыл бұрын
Yeah, whatever input goes through it always comes out much larger.
@mann5861
7 жыл бұрын
lol
@igrewold
7 жыл бұрын
a set of gateS; And, Or, Xor, Not, Nand, & Nor.
@kishankokal5155
5 жыл бұрын
And gate , Or gate, Nor gate, nand gate,.........,bill gate 😂
@jaydipbalasara4510
4 жыл бұрын
😂😂😂
If you want to know the 'equivalency' gate, its XNOR. XOR with a NOT(inverter) tacked on. It returns a 1 if both inputs are the same.
I really wish you were teaching my courses!
i was bored so a coded a little binary converter, thanks for the easter egg
I built an 8 bit adder on my own PCB once, so satisfying
Best easter egg ever :D
Thanks sir ❤️
Brings back the memories of hours spend on redstone machinery
I know all this things but still I hear this things as a story , when professor explains...
I'm not even religious but GOD BLESS THIS GUY!!!! He is so amazing.
I love this man!
Lol, speaking of binary adders I managed to make a 4 bit binary adder in Minecraft without knowing any logical operations other than AND and OR... I literally just brute forced it for like 10 hours and found a design that was highly impractical but worked, and then I found out that the inputs were the wrong way round and it was carrying the wrong way round too XD so I had to rewire a load of stuff.
@MrTurkmenistan1000
9 жыл бұрын
Gg
@klikkolee
9 жыл бұрын
tl;dr: a⊕b = (a+b)&¬(a&b) and a⊕b = (a&¬b)+(b&¬a) you can actually construct xor from and and or by starting with an approximation and refining it. I can start with approximating a⊕b with a+b. this gets 3 out of four correct. I can then look at what the incorrect one should be(0) and what conditions make that case(a=b=1) I can take the result of my first approximation and and it with 0 to force it to be zero, but I only want this to happen for this fourth case. so now I have a⊕b as (a+b)&c where c is zero if and only if a=b=1. sounds a lot like not and, doesn't it? then we have a⊕b = (a+b)&¬(a&b) another way to construct boolean functions for any arbitrary truth table is to find all of the cases where the result is one, create an expression that is only true under those circumstances, and or those expressions together. that ends up with a⊕b=(a&¬b)+(b&¬a)
@livedandletdie
9 жыл бұрын
faissialoo well here's a XOR in Boolean. A⊕B = (A∨B) ∧ ¬(A∧B).But if you're gonna make a XOR in Minecraft I'd prefer (A ∧ ¬B) ∨ (¬A ∧ B) as it's simpler to understand.The second one is easier to follow in my opinion. ∨ = OR ∧=AND ¬=NOT ⊕=XOR
@Nickster258
9 жыл бұрын
Merthalophor every logical function is derived from OR and NOT. All computational can be done with just those two and all other gates are derivations of them.
@Merthalophor
9 жыл бұрын
Nickster258 Both work. You're _wrong_. "All other gates *can be devirated from them".
Isn't it easier to think of the circuit as two half adders with the carry outputs OR-ed together ? Provided you convince yourself that it is impossible for both half adders to produce a carry, I think this gives more insight.
You explained that so elegantly, I couldn't of explained it that well
Konrad Zuse realized his first (mechanical!) computer Z1 in 1938 which could add and subtract numbers. Not just integer numbers, but also floating point numbers. The machine consists of 30.000 parts. It was the first working computer having input, output, memory and a central processing unit.
Yes; we all knew immediately and without thinking about it all that binary 101 is 5, because only awesome people like us watch this channel!
@the1exnay
8 жыл бұрын
we did? of course we did! .>
Will or did you guys do a video on Karnaugh maps?
This makes it easy to do subtraction with 2's complement: Invert the bits for B and carry in a 1.
Also explaining the peculiar way that multiplication is done in a computer will be fascinating.
This dude is hardcore!
A full adder can be done as follows: first bit: xor them & and them together, carry the and gate result to the next bit. All other bits: is there a carry bit? If so, xnor them together and or them together. Carry the or result. Otherwise, repeat the first bit process.
Gotta love the 1980s printer paper pad
The title should include the Full Adder as well since it was mentioned as well ;-)
Great
Briljant!
do n=np problem :)
8:25 cin تعني ما أحمله باليد واحد a,b حاصل جمع عددين عاديين فإذا كان صفر أضف ما كان لديك في اليد واحد (cin) إلى الأحاد كما في الحالة الثانية إذا كان a+b=2 اي 10 في النظام العشري قم بحملها في الcout الحالة قبل النهائية
How do you do an Xor on two whole numbers or base 10 numbers?
I like to think of the xor giving an output if the number of inputs on is odd and it doesn't give an output if the number of inputs on is even. That way it works for if you have a lot of inputs into a single xor gate.
Can someone give me the link to the concept of carrying, if they did a video on it. Or an external link perhaps. Or just a brief run down. Thanks.
What is carry? what does it used for?
What is the purpose of the "carry in" shown at the end? How does it exactly fit into a mathematical expression?
@RedBloodChannel
8 жыл бұрын
I think a carry in, is if you carry 1 but in he number, so you have to add it to the next column wich already exists. But i'm not sure.
I remember building that in Minecraft "Redstone logic"...
Could the third OR gate be an XOR as well?
7:16 "easter egg"?
Ive learnt both logical gates and adder in this magic video. Love this stuff. But is this realy what happens when we ads two numbers in a PC?
it is interesting that, if you have a xor gate it is synonymous with a 1 bit quarter adder, in the same way that if you have 1 proton particle it is synonymous with a atom hydrogen
can you show me the circuit of a full adder attached to an output and an input
I made a 2-bit binary multiplier, here's how it works: CA DB A AND B = S1 B AND C = S2 A AND D = S3 C AND D = S4 S2 XOR S3 = S5 S2 AND S3 = C1 S4 XOR C1 = S6 S4 AND C1 = C2 And to write the answer: Eight's: C Fours': S6 Two's: S5 One's: S1
One important thing that you forgot to talk about is that XOR is not just a way to have output 1 only if you have 1 input signal. In fact, if we have 6 input XOR gate, 1 on the output will apprear only, when the sum of input signals is not even. For example: 1 signal on input gives us 1 on output, but if we apply 3 signals on input, it still gives us 1 on the output. 5 signals on the input - still 1 on the output. 0,2,4,6 - even numbers - so there is no signal on the output.
@Improbabilities
9 жыл бұрын
I'm pretty sure they stuck to two inputs for simplicity, and because it ties into their earlier logic addition content. Besides, a 6 input XOR is just five regular two input XOR gates stuck together. You start by putting three pairs through, and getting three outputs. You put outputs 1 and 2 through another XOR, and then take that result, along with you third output through the last XOR. I'm sure there is a smarter (at least less transistor heavy) way to do it, but you don't need dedicated 6 input XOR gates, just like you don't need more than two inputs on any other logic gate. AND and OR gates combine into their respective 6 input versions the same way as XOR.
@tiuk23
9 жыл бұрын
Improbabilities You are certainly right.
So how do you use it in a situation where you can't carry a bit?
It's 4:30am, I'm tired as hell, and this still made sense. There's something wrong with me.
Super hardcore? We made this full adder the first semester of computer science at Uni. First on paper, then implemented it on a circuit board. Granted, it wasn't a walk in the park.
XDRAW ftw!
Tower of Hanoi in the background?
Thank you for the 'eastter egg'
Why the last stage of carry out is an OR and not a XOR? It can't have two 1 at the same time as input
One thing that always kind of irks me is that people usually show the diagram... and then the table. When, in most cases, you model your diagram after that table. It's like showing a house, giving me a full tour, then showing me the blueprints to assure me the outlets actually work. Let me put it like this: The table is the 'what it needs to do' and the diagram the 'how do you do it'. I don't know how you're doing what if I don't know what it needs to do.
The OR gate before C(out) could be an XOR as well, because both inputs can never be one, since for the bottom wire to be on I this diagram, A AND B has to be on, and for the top wire, C(in) and the output of A XOR B has to be on, but A XOR B will not be on since A AND B was on. So you only need two types of logic gates for this!