welcome to topic 15 in the a-level computer science curriculum so this video is going to be split into two parts and now we're going to take a look at the first part first part is going to focus on processor architectures and specifically we're going to talk about what risk and cisk processors are then we're going to move to what pipelining is and then we're going to talk about parallel comp Computing we're going to discover exactly what parallel Computing is and also talk about a variety of different parallel computing architectures finally we'll finish with virtual machines and then just go over a few practice questions relating to this material first thing you want to talk about are processor architectures now processor architectures are also just kind of how a processor is designed and the way it's designed can have an important impact on how it functions remember that processors act as the sort of brain of a computer when we write any programs in a higher level programming language that gets translated to a set of instructions or a set of commands that will then be executed by the processor the type of processor that we have whether it's cisk risk or any of the other variety of processes that are possible can affect the different types and the number of commands that can be executed by a CPU so this highle programming language gets translated to simpler commands and the type of processor can affect effect what types of commands these can be translated into and how many of those are possible this can affect the complexity of operations that can easily easily be executed on the processor moreover the type of processor architecture can also affect how quickly certain operations can be executed now we're going to talk about two specific types of pro processor architectures CIS and risk cisk is complex instruction set computer and risk stands for reduced instructions at computer and these are good indicators of the functions of both these processor architectures now in order to understand what these are we're also going to compare them so cisk is meant for large and complex sets of instructions so basically with a cisk processor we can do complex operations using a small a small number of instructions because we have so many possible instructions and they're so complex this means that cisk processors are typically used in desktop and laptop computers and basically just larger Computing devices risk on the other hand has a smaller set of possible instructions this allows for very simple and specific tasks this means that risk processors are often used in Mobile phones or embedded devices like let's say for example uh your refrigerator or a car something like that because we don't need to complete the same variety or range of op operations that we would on a computer although this is increasingly changing given how complex mobile phones are today but the point is that risk generally can be used in simpler devices than CIS can now to get more technical an instruction can take multiple clock Cycles so remember the fetch decode execute process you learned about with regards to processors so in order to execute one command it may take uh more cycles of this process in order to complete the task versus a risk processor usually only takes one clock cycle to complete any given instruction or command submitted to the processor what this means is that generally we can execute operations in a shorter amount of time in under risk processor than a cisk processor obviously with the trade-off being that risk is usually used for simpler operations and the next point of comparison is something called pipelining which involves how we can chain together tasks um we're not going to talk about this yet we're going to talk about this in our next slide but all you need to know is that pipelining is something that's more typically used with risk processors uh because risk processors use registers to store data that will then be used for further processes versus CIS operates directly on memory directly in our Ram now this is an important distinction risk uses registers so any data that's going to be used in an operation must be loaded into registers first in Risk processors and with cisk we can directly change and use data in Ram so these are some similarities and differences as well as general characteristics of cisk and risk processors and having gone through this again I do think that the um the description of cisk as a complex instruction set computer and risk as a as a reduce instruction set computer makes a lot more sense now that we've had a chance to compare risk and CIS process and understand what they are I want to talk about something called pipelining which is more commonly used with risk processors now generally when we do pipelining or when we when we're processing commands we tend to process commands sequentially now when I talk about processing I mean that for example we have a command like add one and that command is going to go through the fetch decode execute cycle in a processor so the CPU is going to fetch it uh decode it into something that can be read by the CPU it's executed and the results are written to memory so fetch decode execute and then memory access and results are kind of part of the right portion so let's say that we have we have two different commands we have add one and we have load two I don't even think these makes sense according to like the rules of Assembly Language but whatever remember that these commands are have been translated from um from a high level programming language and now this is what's going to be decoded and then executed in a processor or maybe they're just Assembly Language and they haven't been decoded but generally we would start with some programming language decode it and then that's going to be executed anyways if we are going if we're inputting this into the CPU for processing let's say that this right here is instruction one so this is instruction we'll just give a different color this is instruction one and this is instruction two basically what's going to happen is for instruction one we're going to start with instruction one we're going to fetch then we're going to decode then we're going to execute uh add one and then we're going to write the results to memory or to register or we're going to do something only once we've gone through all four stages then we can start processing our second command so then we're going to uh loow we're going to fetch the load command uh then decode it then execute it and then write the results to memory right here so that's going to take eight eight Cycles eight clock Cycles in a processor now pipeline using pipeline we can make this a lot more efficient so we're going to start with our first command our add one command and I think for this stage I think for this right here um I'm just going to give these two different colors to make it a bit clearer so rather than making this blue um I think I'll go ahead and I'll make this yellow now basically what's happening is we're going to start with fetching the add command so that's going to be in our first clock cycle so our first unit of time and then once it's done fetching we're going to decode it but because the fetching stage is no longer taking place on any instruction in pipelining what we can do is we can start processing the uh the load command simultaneously so basically while we're decoding the First Command the add command we can fetch the load command then uh when we go and we're done with decoding the First Command we can go ahead and execute it so we're moving it to the execute stage but now the decode stage is free so we can go ahead and move the second command load to to the decode stage so basically we have different things going on simultaneously the first command is being decoded while the second command is being fetched and the first command is being executed while the second command is being decoded we can continue with that so we're going to write the results for the First Command or the first instruction and while we're doing that we're going to be executing the second instruction and then the first uh command is pretty much over but we're still going to continue with the second instruction and we may even have another instruction that's coming into the pipeline so as you can see with pipelining right here we're able to process both commands in five clock Cycles five units of Time Versus with a non-pipelined processor or processor that doesn't employ pipelining it required eight Cycles so the result is basically that when we are when we do use pipelining we reduce the CPU downtime because the CPU is now handling multiple stages for different instructions at the same time we can get more instructions processed in a given period of time overall execute instructions are executed more quickly so pipelining allows us to increase the efficiency of a processor so now what I want to do is talk about register is talk about registers because this actually does have somewhat of an impact on pipelining itself now registers are specifically used with risk processors so risk temporarily stores data in registers versus cisk processors operate directly on memory directly on the ram now a risk processor has several general purpose registers that can hold multiple data types so in think integers floats Etc now what this means is that we can we can access data or we can fetch data more quickly uh for memory because we're continually moving memory from Ram to registers so there's always some command or instruction in a register that is ready to go and this basically means that we can in we can decrease the execution time of processes because of the fact um because of the fact because of the fact that registers are closer to the processor and are generally faster than Ram they can also be used as temporary storage for intermediate results during execution which makes pipelining easy so this actually does make pipelining easier because if we have some data that we need to access uh during the execution stage for example it is a lot easier to just go to register than go all the way back to Ram that might throw off the the process and kind of slow everything down overall now the next concept I want to talk about is parallel Computing so parallel Computing is basically when we connect a large number of computers or processors uh to collaboratively work together to complete a task so put we're putting them all together we're giving the collective computers or processors a task and they contribute their resources and work together to complete that task so these computers or processors are working at the same time which means they're working in parallel this is opposed to serial Computing where we would break down a task into a series of steps and those steps to be completed one by one with parallel Computing those steps can be completed at the same time as as needed now as a part of parallel Computing we can pass messages between computers or processors to coordinate operations and they're usually connected by some sort of network infrastructure so they're connected on a local area network or some type of network that can be used to pass messages and and to collaborate with each other now if we're talking about massively parallel Computing really the main difference is that on a massive scale rather than having tens or dozens of computers working together we have hundreds or thousands of computers working together so now that we've had a chance to take a look at parallel Computing I want to look at four basic architectures or four basic schemes for processing data using multiple processors first one we have is sisd single instruction single data the next is simd single instruction multiple data MISD multiple instruction single data and mimd multiple instruction multiple data let's look more in depth at what each of these are and how they work so B so basically what we're looking at is we have a set of data right here we have a set of instructions right here and we have our processing unit right here basically our CPU now what's going to happen at each iteration is we're going to have a single integer it may not necessarily be an integer but we're going to have some value coming from our data pool and at the same time we're going to have some instruction coming from our instruction pool so that value may be an integer like 54 and that instruction it's probably going to look something like this like Assembly Language or something like that but we can say that instruction in this case is X2 so in single instruction single data we have one we have one piece of data or one value at a time that is being executed in our processing unit using one instruction at a time so these would meet right here and we'd have 54 squar and that would just be one clock cycle so just one unit of time now next we might have 29 and our next instruction might be like X cubed and those intersect at our processing unit and then we'd have 29 cubed and so forth so having one piece of data or one value at a time and one instruction at a time and using that instruction to process that single data value is basically how single instruction single data works we have single processor utilizing one piece of data from our data set and one instruction from our set of instructions at a time single instruction single data now if you look at single instruction multiple data again I'm going to use different colors for this this time we have our data pool right here and we have our instruction pool right here now we have a single instruction at a time that's coming coming from our instruction pool so again we can call that X2 but from our data pool we have multiple instructions going to multiple processing units at a time so these could either be processors or cores in a processor or multiple computers it could be a variety of things but so for example maybe we have 54 29 31 51 Etc so every single clock cycle we're not doing one operation we're doing four operations we're using this one instruction on four different values at the same time so right here for example we're going to have 54 squar then we're going to have at the same time we're going to have 29 squ 31 squ 51 squ and these are all happening all four of these operations are happening in the uh in the same clock cycle so you can see how single instruction multiple data would be more efficient or be at least be able to process more data in the same amount of time as a um a single instruction single data set up would would be able to process a single unit of data we just have more volume of data going through uh in this particular setup now next if we look at multiple instruction single data here in a single clock cycle we have a single value coming from our data pool or a data set so just for example we'll call that 29 we'll just say again it's an integer but we have multiple instructions that are coming from our instruction pool so simultaneously we might have x^2 and X cubed so simultaneously we might have X2 and X cubed now right here we only have two instructions but it could be four five six instructions this is just an example and in every single clock cycle we're going to do not only 29 squ but 29 cubed I want to reiterate that these aren't like normal operations again a normal operation might be like load something and our uh values in our data set could be anything they could be they don't have to be an integer they could be a um a different data type this is just a very very simple example anyways with multiple instruction multiple data and a single clock cycle or unit of time we have multiple instructions that are operating on the same uh single piece of data at the same time then moving on to multiple instruction multiple data we have multiple instructions and multiple pieces of data so maybe we might have X2 so we might have X2 and X cubed and we might also have like multiple pieces of data at the same time so you might have like 54 uh 39 21 22 and basically what's happening is we're using multiple instructions to process multiple pieces of data at the same time so right here we might have 54 squar uh 39 squar 212 and 22 2 and at the same time right here we're going to have 54 cubed uh 39 cubed sorry 39 cubed uh 21 cubed and 23 Cub sorry 22 cubed and all of this is happening in the same clock cycle so if we compare if we compare this to our other setups first of all we're probably going to be using a lot more processors in this setup but also we're going to be able to execute more instructions and more data than any of in any of our other uh schemes or setups so it's difficult again I don't want to talk in terms of efficiency but really you can move more data through more instructions with multiple instruction multiple data than any of the other setups now I just want to go back to our explanation of all of these and basically I want to go over when we would would use these so sisd is perhaps the most common and we're just sequentially completing tasks uh we can see this in all sorts of Pro in all sorts of computing uh paradigms or like phones maybe very simple chips maybe not phones phones are a lot more complex these days but very simple chips um maybe embedded systems chips that are embedded in different devices we use it's extremely common simd where we have a single instruction being executed on multiple pieces of data it's often used in graphical applications especially if we have uh pixels of data on a screen and we want to transform those all in the same way for example like in a game or anything any sort of Graphics so SD is very often used in graphical applications MISD is very very rarely used in fact I I don't even think there's like a good example of when we would use it and uh M and mimd is often used in multi-core systems so if you have processors with multiple cores that's when we use MD so again MD especially nowadays with lots of small multi-core processors and all sorts of devices is a very commonly used architecture now these are all computer architectures I know I use the term setup I guess those are synonymous but we would want to group these and call them architectures now let's move on to our next topic which is virtual machines you've probably used virtual machines before I actually use Virtual a virtual machine quite often I have a Mac and I like to play games that can only run on windows so I have a piece of software called parallels in which which basically simulates a another computer on which I installed Windows so that I can basically run like an imaginary virtual Windows PC inside my Mac and in nutshell that's a virtual machine virtual machines emulate a computer system on another host computer system usually with a different operating system that's quite often I think that the use case that people are familiar with now for example you could do do what I did and run a Windows PC on a Mac system or you could run a Linux system on a Windows PC now when we're talking about emulating a a computer system it's not just like we're opening a program and just running a new operating system basically we're creating virtual uh imaginary versions of a hard drive graphic card memory and all the other components associated with a computer and these can be edited like their size can be changed we can change their settings Etc so it's literally like creating an imaginary computer inside another computer now there are various pieces of software to make this possible the one I was referring to is parallels uh boot camp is another common one on Mac uh VMware is one that's been used for a long time as well now there are a couple of reasons why we would and we wouldn't use these now one of the biggest Pros for using virtual machines is that we can run multiple operating systems on the same machine so we don't need to buy a new computer to run Windows if we have a Mac also a popular usage of virtual machines is in cyber security so if we have a virus that we want to work with we can just load it onto a virtual machine and because that virtual machine acts as its own computer as its own separate computer that virus can't leave the virtual machine so we can use it to kind of secure host computer system from any any cyber security related experiments we're doing or if we need to access some data or webs sites that are insecure so in Virtual machines are a secure environment that we can use for a variety of tasks additionally we can use Virtual machines to run Legacy applications so these are older applications that are no longer uh compatible with our modern operating system so for example like I have some old games that I love to play that only run on Windows XP and let's say like even if I had a Windows computer like Windows 10 I would still need to use a virtual machine to play those games because those are technically Les Legacy applications and finally because we're not just like emulating an operating system or emulating a computer as a whole we can actually emulate different processor architectures so maybe our processor architecture in our computer is uh cisk but we want to um maybe develop uh we want to develop some software for a small device that has a risk processor well we can use Virtual Machine software to emulate or create a virtual computer that has that risk processor and then we can run our software on that virtual computer and do some testing so we can easily emulate or rather simulate uh other processor architectures as well as other pieces of Hardware now I'm using these words emulate simulate uh imaginary virtual the point is this computer is not real the software is just pretending that we have another computer and that that has all these components now some of the trade-offs of virtual machines are that because we're effectively running one computer on another computer the host computer that like basically the real computer is going to get slowed down virtual machines take tend to take up a lot of processing power memory and also hard drive storage um moreover virtual machine performance is limited by the host computer so if I have a Mac that has a certain number of gigahertz and memory I can a virtual machine whose specs or specifications exceed that processing power um Ram or uh or hard drive storage additionally some Hardware cannot be emulated so there might be certain types of Hardware that we can't emulate using our software or um our virtual machine so there are some limited capabilities and finally virtual machines can be expensive to implement um first firstly because we need more powerful Hardware to efficiently use them but also because we need specialized software like parallels boot camp Etc that can often be expensive now that brings us to the end of our first part most of the questions associated with this content are theoretical but I want to take a look at a at a question involving um pipelining that is less theoretical perhaps so right here we have this question so the processing instructions is divided into five stages we saw four stages in our diagram but here we have five stages instruction fetch code operand fetch instruction execute right back result this is one we didn't really look at but it doesn't really matter um what the stages are in this question it says that each stage is carry out carried out using a different register when pipelining is used complete the table to show how a program consisting of six instructions would be completed using pipelining so you've got six instructions and we can label these all A B C D E and F with a being the first instruction and all of these need to go through all five of these stages if ID o f i e WB and we need to show how that's going to happen if we're using Pipeline and right here we have our clock cycle so our units of time so basically how we're going to approach this is we're going to start with a because that's the first instruction and at the first clock cycle we are just going to have a being executed now now as soon as we move to the next CL clock cycle or sorry then we're going to be at the instruction decode stage and as a is going through that stage then we can start with b right here now in our next stage we're going to have a so a is at o and that means that b is now at ID but then we can put C right here C can go into our instruction fet fet stage then we're going to have a right here and then we're going to have um so then we'll have B uh c and d and then we're going to have a right here so a is going to finish its last stage and then B is going to be at the uh previous stage then C D and E and just keep in mind I know we still have one instruction left right here but then a is pretty much done so we're going to move on to instruction B so instruction B is going to be right here then we're going to have C above that d e and now f is getting started and then B is done so c d uh e uh and then see yeah am I getting these letters right B CDE e f yeah e and then F uh C's done d e f D's done e f and then we just got F left remember all of these instructions are like add something load something something that would be executed by a processor right so in a nutshell that's how we would Express how pipelining works with six instructions now if you see a question like this in the exam it might have a Vari uh number of instructions might also have a varied number of uh stages depending on how the stages are defined so it might be four or five but this is basically how you would work through them another thing I want to point out is that right here it mentions a different register being used and that means that basically anytime uh any of these stages is executed the result can be stored in register now I didn't highlight that that much when we went to pipelining but I think this is a great example of how important registers are in pipelining and how the usage of risk or how the usage of registers in Risk more easily enables pipeline to take place anyways let's look at the Mark scheme and here we have 1.1 .2 1.3 it's basically the same thing we're just using numbers we're using numbers and then uh and and the stage that that particular task is at and right here this looks more like what we did anyways that brings us to the end of part one let's move on to part two which just going to look at uh at logic circuits Boolean algebra and carau Maps now that we've covered that let's take a look at part two of this video for topic 15 on the a level computer science exam in this section we're going to focus on buan algebra kaps and logic circuits the content in this section coupled with the other section generally makes up one five to seven point question on paper three now the first topic we're going to cover is going to be Boolean algebra in your previous studies particularly for paper one you should have covered logic gates now with logic gates we learned about different types of uh circuits that involve not and nand or and nor Gates we also learned about exor and perhaps in your class you learned about some other Gates as well we're going to be working with these again in this particular section but things are going to look a little bit different we're going to look at some new notation for how we can represent circuits using Boolean Expressions let's say that we want to create a not gate and write that an input is going to be subject to a not gate so let's say we have something like this and the input is an a that's going to be our one or zero so we have not a a now that's going to look like this we're simply going to have a bar over what is being knotted over what is going to go through the not gate next let's say we have another circuit so you have something we have a and b as input and that's going to go through a an and gate so we have a and b what that's going to look like now is going to be A.B or in subsequent slides and questions we're going to see it written like this with the B looking more like a period alternatively we might also see A and B looking like this without any dots finally let's say that we want to create an orgate so we have a as one of our inputs B is one of our inputs and now we're creating an orgate it's going to look something like this then we would just do a + b so A or B would just be a plus b now when we're using this notation in the section we're actually not going to be working with exor or exclusive or Gates so that's not really something that you need to worry about but this notation is something you do need to be aware of because most questions in this section are going to involve buan Expressions written in this format so if you look back here um and we just have not so if we have a as our input then in our new notation not a is just going to be like this just going to be a so we can just represent this as being a and is just going to be so let's say this is a and b and this is going to be AB or a do B now nand is interesting because nand combines not and N so if you have a nand b then that would be something like we could just say a and then we can just put a not bar over it it's a and b and there's a knot over it with or let's say we have a and b as our inputs we're going to have a plus b and if we had nor then we would simply have a plus b with a bar over it now that being said let's look at some Boolean question Boolean related questions to kind of refresh our memories and how we can work with Boolean problems so firstly here a logic is shown we need to write the logic expression for the circuit so we're going to write it in our conventional notation and then we're going to go ahead and write it in our um new notation so right here we've got um AB going through an and gate so we obviously have a and b and right here so right here through this gate we have a and b going through this end gate and then the the result of this end gate right here is going to go through so this one right here it's going to go through another uh it's going to be an X orgate so we we basically have a and b and that's going to be like xor uh xor C so going through there and so we've got that and then that's going to be on one side and then we have B which is going off to a knot so then and that not B is going to go through this or gate so we can say or not b and that's basically our entire expression and if we go right here you can kind of see that this is what it looks like like but how can we represent this uh using our new notation so we could do um so again we don't really have any notation for xor but we could just do a uh X or C that can be in parenthesis uh plus b so that's kind of how we represent that using our new notation again we don't need to worry about xor because that's not going to come up in our subsequent problems so enough dithering let's get into some form I just want to start with a really simple formula to show you how these work now if you look at these charts everything is written in terms of a or b and in this chart A and B don't necessar don't necessarily well actually they they do kind of represent inputs in a circuit so basically A or B could be true or false right these are really all just Boolean variables so let's just look at one just to get a feel for how this works so here we have a formula a do a equals a now looking at our notation earlier a. a is basically a and a so we're seeing a and a equals a so to break this down this means that for example if a equals true right that means that true and true is going to give as true which makes complete sense actually right so if you just didn't even think about the outcome right here and we just did What Would true and true be that's just going to give us true on the other hand if we had for something like true and false so if you had like a equals true and uh and b equals false and we were trying to see what a and b equals so if you're trying to see what a and b equals that would just be we'd have that would just be um false because when we have um um like for for basically A and B to be equal to True both of these both A and B would have to be equal to True right so right here we have true on one side and we have true on the other side so true and true is just going to give us true and that's going to be true whether a is false as well so if a equals false then we would just have false and false and if one side of the end is false the other side is false that's going to give us false as well so the point is any any Boolean variable that doesn't end with itself is going to give as uh itself so if we look at a circuit um things would actually get kind of weird but basically it's like if we had a um and we had a these are both going into an end and then that would just give us a now I'm not necessarily saying this formula is going to be useful but I just wanted to use this as a way to introduce how these formulas work so that being said let's look at something that's actually going to come in handy later on when we go ahead and we um try to simplify some more complex Expressions so the first one that I want to start with is going to be um probably this one right here well I'm going to look at okay I want to look at at this one but then first more something a bit more complex so this one this one and this one so let's start with let's start with a uh plus a equals a so okay now the plus means or and the fact that there's no space between A and B just means and so what this really is is a or A and B is always going to be equal to a and let's just kind of think about let's go through some scenarios and think about how this might work so if you have a equals true and we have b equals let's say b equals false for example this means we would have true or uh true and false equals a um so if we have true in one side of and and falls in the other side that means that we're going to have that's going to evaluate to false so means we're going to have true or false and with it with an or operator the Boolean operator if one if at least one side is true that means the result is going to be true so that means means that it would be equal to true and in this scenario a is true so we do actually the formula does actually work um so that's another example right there and I think the next one I want to look at is going to be a + a equal a plus b so one thing I do want to point out is some of these you can kind of Reason through so right here we know that if we have whatever we have on this side so for example if we have true on that side then of course no matter what is on this side we're going to end up with we're going to end up with true right or if a is false that means that this is going to be false right here so we're going to end up with false for our um for our result so you can kind of Reason through some of these formulas but let's just take a look at another one I'm actually not going to solve this one out but I just kind of want to talk about it a little bit so right here we're going to have we basically have a or not a and b equals a plus b so okay um a plus b is actually just going to be or so I'm going to go ahead and just kind of simplify that and okay so let's think about this for a second so we have a or Not A and B so basically we already have a or so we have this section right here and what this formula is telling us that this is always going to be equal to to what B is so if we think about a scenario where we have like um where we have a equals true and b equals false that means we're going to have true or the opposite of a which is going to be false and false and that would just be false so we end up having true or false which actually follows the uh this particular um well the particular value values we gave now again these are probably better off just memorizing these like again if you kind of look at it logically you can figure it out but the the formulas that I selected are probably ones you just want to memorize now the last one I want to look at besides dorgan's Theory which is going to be super important is a + not a equals 1 and in this case one is true so it's being it's basically saying a or not a equals true and let's think about why that might be so if we have a or the opposite of a that means one of these is always going to be true and false and we have an or operator in the middle so that means the answer is always going to be true right because if one of these is true and one of these is false we do have one true Boolean variable in the statement which is going to result in a true now the last formula that I want to talk about and I think you should know is going to be demorgan theorem this is like an absolute fundamental of Boolean algebra so I'm going to erase everything that we've gone over so far to make rule for that okay so with demorgan's theorem we're basically saying that we have a b with a bar over it equals a with a bar over it plus b with a bar over it so let's just start with that one what this is basically saying is that not A and B is equal to not a or not B now the best way to remember the Morgan's law is actually not in Boolean terms at all so let's say that A and B are not even like Boolean variables but rather they're just people going to them all so let's say a means that uh James is going to the mall and b means I don't know Ali is going to the mall now if we have not A and B that means not A and B so James is not going so not James is going to the mall and Ali is going to the mall so that means that both James and Ali are not going to the mall both of them together are not going to the mall that doesn't mean that that uh James couldn't go to the mall but uh olly could stay home James could go to the mall and olly could stay home or olly could could go to the mall and James could stay home right but A and B if we have not A and B that means that both of them are not going to the mall so that means that either like for this to be well what this basically means is that at least one of them should not be going to the mall in other words either this this means that either Ali or James is not going to the mall hence we can say not a or not B so if we say Not A and B that means that a both A and B are not true but one might be so we're saying either it's not a or it's not b and hence we can kind of use this logic to remember this part of De Morgan's theorem not a and b equals not a or not B now let's look at the other side of demorgan's the on the other hand we have a plus b with a negative bar over it equals A and B both of bars over them so in more basic terms what this means is that we have not a or b equals not a and not B sorry for writing in like a kind of Shifty way but if we go back to our Ali and James examples example this means that we have not so A and B means um Ali is going to the mall or James is going to the mall so A or B is Ali is going to the mall or James is going to the mall but if we have not that means that both Ali is not is not going to the mall and James is not going to the mall right because if a or b is Ali is going to the mall or James is going to the mall if that statement is untrue that means it no one is going to the mall so that's how we get not a and not B I hope that makes sense but that's an example of De Morgan's law and regardless of whether you understood my perhaps Mis not misguided my weird example you just need to memorize de Morgan's theorem um or demorgan's law as it's called so that you can use it later on now one thing I do want to point out before we move on is that both of these These are both demorgan's theorem and they're kind of two sides of the same rule so on the other hand we have not a or b equals not a and not b and on the other hand we have not uh we have not a and b equals not a so even if they're not necessarily the same rules they do show the same relationship just using different operators and this is going to be useful in our next slide so now that we've covered some of the basics of Boolean algebra and how to interpret these these basic rules of Boolean algebra we're going to look at these in a slightly more advanced way which we're going to need moving on so this is a slightly more complicated chart and we have a list of rules that are written both with an emphasis on the and form and the and operator and the or operator so an example of the and form right here we have we have this which is circled and we have de Morgan's law again in the or form and these correspond directly to what we saw right here these were just the and and or form of demorgan's theorem now we have a couple of other laws that we do need to know in addition to the ones that we already went over and that I asked you to memorize basically so the other two you want to the other three we want to look at are going to be so I think the item poent laws we've kind of already looked at it and they're worth knowing but also the commutative laws associative law and distributive law and these in a way are kind of easy because they they they look a little bit like algebra right so let's start with the communitive law like I'm not going to fully explain these I'm just going to review them really quickly um just so you have an understanding of what you're dealing with so the communitive law we have a and b uh equals B and A and this seems like it would be common sense but it's something that you should know um on the other hand in terms of or you have a or b is equal to b or a that's the commutative law next we have the associative law associative law and that one's saying that A and B uh and C is equal to A and B and C again the way it sitten makes it look kind of algebraic but that's just the way it is and we basically have the same thing for the or operator which I'm not going to go through writing again but that is the associative law associative law and finally we have the distributive law which kind of looks a bit like factoring um so we have a or so for the an form we have a or uh B and C is equal to a or b and a or C so we're essentially Distributing uh A to B and C so that's the distri that's distributive law and so I guess like the uh the or version looks kind of similar so for the or version We Have A and B or C equals a and b or or a and uh a and b or a and C so just another version of distribution now again we need to know de Morgan's law um but the communative law associative law and distributive law are all forms to know as well as actually the absorptive the absorption law I'm not going to go through that that uh too deeply cuz we already kind of looked at that but again all of these are worth knowing now I know I've spent a lot of topic on Boolean algebra but honestly like there are entire units that classes spend on this in University and even some High School classes um this is covered in a topic called discrete mathematics that almost every computer science student takes anyways with this tools these tools we can finally move on to a practice question okay so let's start by solving our first example so right here we need to simp simplify the following expression using buan algebra including demorgan's laws show your workings this looks complicated but actually I think the best way to approach this is to start from the top and work our way down so right here we have not and basically it's not and then not of inside Expressions but this is kind of a lot to deal with so basically if we kind of think about the way this works this knot on top right here supersedes anything down here and and that supersedes anything underneath it it's kind of a weird way of thinking about it but basically we need to deal with the top knot and then work our way down so whatever is underneath that is kind of irr irrelevant at the moment so instead what I'm going to do is I'm going to actually say that this is going to be not and then we're going to have three knots and then I'm going to say x y and z now X will be equal to uh uh a knot do B KN uh y will be equal to a not. C and Z will be equal to uh um B do d right and all of these are in each other so effectively we have not uh not X I'll go ahead and erase this we have not X and not Y and uh not not Z so now just looking at this this looks a lot like demorgan's law so if we go back right here to our basic laws of Boolean algebra we have this is one of the Morgan's laws not a and b equals not a or not B we have an extra end but that doesn't really make a difference in how things work so if we go back right here then we can say we can say not X actually we're going to lose the KN even right because right here we have not A and B becomes not a or not B so the a gets reversed the not is gone and we have an and that's turning into or so that means where everything is going to be the opposite then means the not's going to disappear everything's going to become the opposite so we're going to have X and all the ends are going to become ores so we have X or Y or Z so now basically all of this became this right here so we can say that we have x + y + z and if you if we really break that down that means that we really have um AB plus uh AC plus BD now we can further simplify this so here we have in in these two expressions right here so in these two expressions right here we have uh we have the not a right and if you look back at our chart right here that matches the um that actually matches the the absor absorption law or um it looks like it matches the distributive law right here right because this looks a hell of a lot like what this looks like right here we have in this expression right here we have a in both of these expressions in our expression our question we just have not a so using the distributor rule what we can do is we can do a and then we can do uh which again is actually a lot like algebra plus uh b d now we can try to look at our additional rules and see if there's anything we can do but we really can't so this Remains the answer our answer is going to look like this now that was probably the most complicated Boolean algebra question you'll actually see on the exam the other questions we see are a lot easier but you still need to know how to simplify these Expressions that being said let's move on to some more questions related to Boolean algebra now let's take a look at another question involving truth tables that makes use of the concepts that we just went over now here our task is to write the Boolean expression that corresponds to the given truth table as a sum of products now we haven't really seen what a sum of products is yet so this will be a demonstration so the first thing we need to do is we need to identify all of the outputs that are one so that's going to be this output this one uh this one right here right here right here and right here so we have a total of six rows where we have an output of one where one equals true now these variables a b and c these are all inputs to a circuit so they do represent Boolean variables but overall we're looking at these in the context of circuits so in order to find the sum of products we need to write an expression that represents which values are true and which values are false for each one of these particular rows so all six of these that we've circled so first if you look at the first row our expression is going to be a so we have a is true and B and D is true right here so we're going to write a b with a bar over it C with a bar over it and D with a bar over it because we have zero for b and c and then we can add that to for our next row right here we're going to have the only one that's going to be negative is going to be B so we're going to have uh a a sorry not negative but rather I guess false or zero so we're going have a b with the bar over the top and then CD uh next we'll have a uh B and then c d uh plus uh next we have so for this one this one is actually pretty much the same as the well no it's not the same um so we have we've got a B uh C with a bar over it and then D and next we've got two more rist to go so right here the only one that's negative is going to be D so or rather than negative again I mean false so we're going to have a b c d with a bar over it and then our last one is going to be okay everything is going to be one so it's just going to be ABC D and this is going to represent our sum of products so if you go to our Mark scheme over here we you can see that this is the answer which pretty much Ma matches up exactly with what we did um so this is worth three points and each of these two counts for one point out of the six Expressions now to further solidify our understanding of these types of problems which appear frequently on the a level exam in paper 3 let's look at another similar question so right here this truth represents a logic circuit we need to write the Boolean logic expression that corresponds to the given truth Pap as the sum of products so again sum of products is going to mean exactly what we did in the last question so technically while this is logic circuit um we're going to think of each expression that we're adding together as a product it's in my opinion it's kind of a weird way of approaching it but that's what it is so anyways the first thing we need to do is we need to circle the rows with an output that is one so we're going have this row this row this row this row and this one and this one so again we've got six outputs that are one and in the first one we have uh we have zeros for everything so we're going to have uh a b c d uh next we have got uh zeros for everything except for D so we're going to have a b c d um next we have the only um variable we have a one for is going to be C so we're going to have a uh B C D um next we have a one for for the C and D it's these right here and so we're going to have uh plus uh a b c d uh next we've got our uh next two variables down here so you've got for B and C we have a one so we're going to have uh a the bar over it b c and then D and then finally we've got a one for b c and d so we're going to have uh a with a bar over it and then BCD that's going to be our answer again we'll look at the Mark scheme and that's pretty much what we got anyways now that we've seen this type of question which is kind of an introduction to working with Boolean expressions in the context of circuits let's move on to Cara Maps which will take this to another level now this is what a caram appap looks like ultimately it's used to simplify Boolean expressions and these are some rules for dealing with caram maps but these don't make very much sense at the moment so once we actually go to solving some problems some A- level problems with Cara maps in the next slide I will refer back to these rules and as a whole this concept will make more sense so without further Ado let's look at an example of a Cara map so right here our task is to complete the carau map for the Boolean expression using this particular expression right here now this comes directly from a truth table so each of the Expressions that are being added in this in this expression are going to be those that give us an output of one in the given circuit and truth table so what we're going to do is we're going to take these values and put these into the grid format that represents our kmap now we're going to start by um by taking each expression and then converting it to zeros and ones for what they would represent in the truth table so start with the first one right here so this is going to be zero because a is being nodded so 0 1 uh 0 Z so if you look at our kmap right here we have AB values on this side so on our X axxis and then we have cd values on this side basically on our y- AIS so if we have the expression um negative a b ctive d so basically a is Zer B is 1 C C is 0 and D is Z first we're going to look at the top at the at the uh X axxis for 01 for ab and so we've got 01 and that's going to be right here and then we're going to look at where CD is CD is 0 0 and that's right here so we're going to put a one right here because 0 1 0 0 is going to give us this output at this particular position so next we've got uh we got not a b not c d this is going to be 0 1 0 1 so that's going to go right here 01 for ab and then 01 for CD Now next we've got a we've got AB not c not D so this going to be 1 1 0 0 so that means we're going to have a one right here next we have 1 1 0 1 so so that's going to be right here next we have 1 0 0 0 which is going to be right here and then finally we have uh 1 0 0 1 which is just going to be right here now these are the expressions or the combination of inputs that give us ones so everything else is just going to be a zero and that's how we actually fill in a caram map now if you look at the next part of this question we need to draw loops around appropriate groups in the kmap to produce an optimal sum of products and then based on the sum of products or based on the loops that we draw we're going to have to write a Boolean expression as a simplified sum of products so basically what this question is asking us to do is we're going to draw Loops in our carau map which I'll show you how to do in a second and based on the loops that we draw we can then take this expression right here and we can simplify it down so when we have complex Boolean expressions like this we can utilize caram apps to make them simpler so to draw our to draw our Loops we're going to look at some rules so we make groups of only ones so we're only going to be focusing on the uh the areas of the grid here that have one we make groups only of two n in size so our groups can only consist of two values four values eight values Etc groups can be a column row or rectangle only groups can overlap but should as little as possible and the fewer groups the better groups should be as big as possible so let's take a look at our grid right here so we can't have any rows of um of three values so we're not going to have any horizontal rows so we can't have any like any groups of three it needs to be either two or four but we can either have um we can either have two so one option is to have uh three groups of two one like that but this isn't really giving us the least number of groups possible which is one of the is which is one of the rules so instead what we're going to do is we can see that we can actually split this into groups of four but not groups of eight so the way we're going to split this into groups of four is we can have one group right here and we can have one group right here and that's going to give us the correct Loops for a carau map now actually think what I'm going to do is I'm going to put both Loops in different colors uh just to make things easier for us to understand later on so one Loop will be green and the other one will be purple so now that we have our Loops according to this question we want to write a simplified sum of products so what we're going to do is we're going to look at what is in common among all the values in each of these groups and let's start with the purple Loop actually we'll go ahead and uh erase the green Loop for now just to focus on the purple Loop so if we look at this purple Loop um first we're going to look at C and D like what do these have in common in terms of c and d and we can see that all these values have zero for C so one way we can simplify everything this group is going to be to write c um and then we can look at what so I mean that's what it has in common uh in terms of CD and then we can also see if there's anything in common in AB so with a we can actually see that we have one in common for a for everything in the group so we can write a because we have one for a and then C but we're writing not C because we have zero for C so that actually covers uh this particular group let's go back to our green group right here and so right here for our green group um we have Let's see we again have so we also know here that c is going to be zero so we can actually do uh we're going to do plus C but then in the second group we see that a is changing but B is always going to be one so we're really going to have b c and that basically takes this whole expression right here and simplifies it down let's go ahead and look at the Mark scheme just to make sure we got things right so this is our caram map which we got right and this is is the simplified form which we also got right now so our simplified sum of products is basically going to be AC and BC a not C plus b not C so we're going to have a not C plus b KN C now what we need to do is actually take this and simplify it even further and to do that we can use our chart with our Boolean expressions or our Boolean rules rather so right here we've got our Boolean laws and right here we have a not C plus b not C and both of these values share not C in common so if we just kind of look around here this is probably this right here is probably the most similar expression right here we have a plus a c and here we have a not C you have a not C plus b not C so we can kind of reformat this um putting the common elements first so basically we have uh not C A Plus not c b and that's just going to give us our common element on the outside so that just give us not C uh a plus b so you can go here we'll just write our answer let's go ahead to our Mark scheme and it does seem like we got the correct answer so that was our first caram map problem well we're going to solve a bunch more because it does take a little bit of time for you to wrap your head around how these work now let's take a look at our next kmap question here we need to complete the kmap for the given truth table now this given truth table isn't shown here but this this truth table is the same one that we looked at in a previous question when we were going over Boolean Expressions so I've simply copied the expression that we came up with and pasted it here so according to this expression right here which we solved from our true table earlier let's go ahead and fill in the kmap so first we have a not b not C D I guess it's going to be 1 0 01 so 1 0 1 is going to be right here uh next we're going to have a not b CD so that's going to be 1 1 1 so that's going to be right here uh next we've got uh a b not c not d it's going to be 1 1 0 0 it's going to be right here next you got a B not c d so it's going to be 1 1 0 1 next we've got AB b c not D so it's going to be one one uh 1 Z and then we have uh ABCD so just going to be one one one one okay so let's go ahead and fill in the ones we have yet so 1101 is going to correspond to this right here then we have 11 1 0 which is going to correspond to this one right here and then we have 1111 which will be this one right here so that's our caral map um what we can go ahead and do is actually just fill in all the other zeros just to complete it and that actually fulfills the first part of the question and if we just look at the Mark scheme we can see that we got it correct now the next part of the question wants us to do what we did before which was to produce a sum of products a simplified sum of products and then simplified even further using our Boolean rules so we need to First Circle actually they did ask us to put a loop around uh yeah actually we need to draw loops around as well so forgot about that but we would have need to we would have need to have done that anyways so I'm going to go ahead and draw Some Loops um so I think the first one is just going to be the this one right here remember we want our Loops to be as big as possible they can only have a 2 N number of values and we want to have the lowest number of Loops possible so I think this one makes sense right here it's going to give us four and then we still need to get those other two elements and the only way to do it is to draw another loop in between these maybe I'll put that in purple just to make things clear so got that right there so first of all so yeah this has Loops the greatest number of elements possible covers all the elements fewest number of groups 2 N number of values so let's go ahead and see uh what green is going to give us in terms of an expression so in green we can see that uh we've got D being uh D being one and we have a being one as well so I think we can say da for one of them plus da um or if we're to put it in alphabetical order we could do plus uh a d and for the purple one like for all of these we don't really have anything in common so all the values change because it's a column but for all of these we do have both A and B being one so we can say a plus a d okay cool all right so that's going to be our simplified expression let's go ahead and check and make sure we got that part right before we simplify it down and it does look like we did so now when we want to simplify it down we can also see similar to our previous question that we have a common term in between both and when we have a common term it's we can almost approach it like algebraically um we can use the same rule that we did before which is this one right here our distributive law and we can say a B+ D and that should be our answer so if you go right here to this question our answer is going to be AB plus a d and the simplified expression would just be a B+ D which the mark scheme says is correct so really the key is choosing the correct loops and then following the rules that we went over which are these right here let's let's move on to our next question so here we need to complete the the kmap for the following expression okay so again what we're going to do we're going to kind of translate this into ones and zeros so right here we're going to have uh 0 0 0 0 uh 0 0 0 1 0 1 0 0 uh 0 1 0 1 1 1 0 0 and 1 1 0 1 let's put these into our c M so this is going to be the first one right here um next we're going to have 0 0 01 is going to be right here next we're going to have 0 1 0 0 which is going to be right here uh 0 1 01 which is right here uh one one 0 0 which is right here and then 1 01 which is going to be right here so we can fill everything else up in a zero and that gives us our kmap let's see what else we need to do for this question presumably it's like the previous questions so yeah draw Loops uh write a simplified logic expression expression and simplify it down further uh using our Boolean rules so okay so right here um we're going to draw Some Loops so we can't have rows of three and we don't want uh three columns of two because we want to maximize the size of our Loops um but we can't I mean this looks this looks almost exactly like the first problem we looked at and we can have two groups of four four is 2 ^ of two um these give us the fewest number of groups so now that we've done this let's go ahead and find a simplified expression so if you look at the first Loop um so zero is being going to be C for both of them so we're going to have C and then for both of them a is going to be zero so we're going to have we'll just say AC Plus for the next group we're still going to have um C being zero and in this one B is going to be one so we're going to have so B is going to be one so we're going to have uh let's see B okay so that this is going to be our initial expression and then if you want to simplify down we can do the exact same thing we did before by Distributing and we can have uh not C being on the outside and not a plus b so yeah right here we're going to have a c plus b is it what is it it was uh B not C and then that's just going to give us C and then a plus b and if you look at our Mark scheme we did get the mark Or we did get the K map correct uh we got our Loops correct and it looks like we got the correct Expressions as well so let's move on to our last practice problem involving kmaps okay now for our final question uh complete the caram map with the given truth table so this truth table is again one that we looked at before um so we we solved or we found the logic expression for this when we were talking about Boolean expressions and I simply copied the expression here so we're going to go through our process again um we're going to have uh not a not b not c not D so 0 0 0 plus not a not b not C and then D so 0 0 0 1 plus not a not b c and not D so plus 0 0 1 0 plus not a not b c d 0 01 1 plus not a b c not D so it's going to be 0 1 1 0 uh Plus plus not a BCD so 0 1 1 1 so we're going to have a one right here um let's see 0 0 0 1 so another one right here uh 0o uh 0 0 1 0 one right here 0 011 one right here uh 0 1 1 0 so it's going to be one right here and then 0 11 one one so one right here and then zero is everywhere else now this Pro this problem we're also going to have to come up with a simp with a simplified expression and then a further simplified in uh expression which we um which we looked at before and in order to do that we're going to have to draw Loops now here um I think we it's pretty obvious that we have one column so that's going to be right here and we want the largest groups possible so we're not just going to have uh a column of two right here that's not how it's going to work uh we're going to have a block of four right here so part of the reason why we want to have the largest groups possible is that allows us to see the most common Trends so it allows us to see the variable whether that's a being one or B being zero or C being zero across the largest area so the larger our groups are overall the more simplified our resultant expression is so anyways if you look at what's in common in the first column um basically we have uh not a and not b and if we see what's what's common in our uh in our Square then we have uh C being one so we can have plus C and then we have um let's see we have a being zero so zero here and zero here so we can just really quickly erase this and put not a and C and if we simplify this using our distributive law we're just going to have a not a and then not B plus C so you can actually see that nearly all of our examples have involved the distributive law and they involved very similar shapes so just having done a few of these problems you'll probably be able to solve any of the Kat problems that come up on your exam let's take a look at the Mark scheme uh we're good to go right here um okay we're good to go right here and we are are also good to go in terms of our simplified expression looks good now we've covered K Maps let's move on to our next section which is going to be on logic circuits okay the first circuits we're going to talk about are going to be a half adder and a full adder now as the name indicates both of these are used to add up numbers specifically the half adder is used to add two one bit binary numbers the full adder is used to add three one bit binary numbers or even more than that so for the a-level exam we need to be able to generate truth tables for these circuits and really identify them from truth tables so if you first look at the half adder the half adder is going to consist of an X or gate and an end gate we're going to have two inputs each input is going to represent a single binary digit and then we're going to have a sum and carry and together these sum and carry are going to represent the sum of A and B so this is the truth table in our truth table we're always going to have two inputs A and B and then a sum and carry output for the half adder circuit so let's kind of analyze this truth table and see how it works so let's say let's start with one and zero let's say that we have one we're adding up one and zero so we just have one in binary form form plus 0 if we add those up our result is going to be 0 and 1 if we had a larger sum so if we adding up more numbers then this zero would actually carry to the next side and one would stay here hence the carry is going to be zero and the one is going to be the sum so whenever we add up A and B like the this number is like the number that represents 2 the^ of 0 is going to be in the sum column and this number right here the number that represents 2 the^ of one is going to be in the carry column so this one will be like this so really we're representing the numbers in Reverse in our truth table let's take a look at another example so let's see right here let's say that we're adding up one and one so if we're adding up one and one in binary so really 1 + 1 is like 2^ of 0 + 2 ^ of 0 which is really going to give us which equals one and one and that gives us two in binary two is going to be 1 Z because 2 the^ 1 2 the^ 0 so really the answer here we when we add up these two binary digits is going to be one and zero so this right here is going to be our our uh carry and this is going to be our sum and you can see what these look like in our truth table right here our sum is zero so we're Su is zero and I'll actually just use colors to represent this and our carry is going to be purple so this represents 2 the^ of 1 and this represents 2 the^ of Z and to actually even clarify our previous example I'll just write this in red right here uh so yeah this is our sum and our carry was in purple now we're basically going to do this for all the possible inputs of A and B which are shown right here in these two columns now to summarize with a half adder we can can add up two one bit binary numbers the result is going to be in the column sum and carry sum is effect is effectively going to be the last digit in our binary result and carry is going to be the first digit so this right here is going to be our uh our carry actually maybe I can write that a bit bigger so this right here will be our carry and this right here will be our sum and that's the truth table and when we see this pattern in any truth table that's given to us on an exam we can immediately identify that this is going to be a half adder circuit or this is going to represent a half adder now if you look at a full adder in this example right here a full adder is used to add three 1 bit binary numbers in reality there are ways we can add up more binary numbers a full adder is generally used to add up uh any number of any number of binary numbers that are greater than two um but again this is the most common structure we're going to be working with we we're adding up three 1 bit binary numbers now here we have a similar setup with sum and carry so let just take a look at a few examples let's take a look at this one right here right so if we add up one plus 1+ 0 now if we're adding these up in terms of binary that's going to be like 2 0 plus 2 2 the^ of 0 which would really just give us two and if you want to represent 2 in binary it'd be 1 Z so right here our answer be one Z and our carry this is going to be our carry and this is going to be our sum so accordingly we have our carry right here and our sum right here it set up the same way even though we have uh we have two we have three digits let's look take a look at a slightly more complex example so right here we have one one and one for all three of our inputs now again one thing that I didn't mention is that because we're adding up three digit digits we do need to have three inputs so we're going to have a b and c and so let's say for each of those we have one so we can do 1 + 1 + 1 and if we're really doing bying mathematics then it's going to be 2 0 + 2 0 plus two 0 which those are all one so our answer is going to be three and we can we can represent uh three in binary as 1 one because 2 the^ 1 and 2^ 0 so that means that our sum is going to be this right here and our carry is going to be this right here so we got our sum right here and our carry right here and in a nutshell that's how full adder and uh and half adder work okay so now let's take a look at what a practice question looks like involving full adders and half adders so right here this diagram shows a logic circuit that most probably contains a truth table with the full adder and half adder now I'm actually not going to solve this whole truth table because it would take a while and it's not really like it's something you should have done in a previous unit but if we go ahead and we take a look at the truth table this is what it looks like so once we've completed this truth table our next question will be to State the name of the logic circuit and then write the Boolean expressions for the two outputs Y and Z in the true table as the sum of products then we need to State the output the purpose of each output so first of all we have two possible purposes we have a sum and we have a carry um but first of all let's focus on what circuit this is going to be so we have three inputs which I think it's pretty obvious it's going to be a full Carry but if we look at some of these like so for example if you look at 1 one one the sum is or sorry the the answer we get is one and one which is one + one + one so that ends up giving us 1 one in binary and that's pretty much what we get uh if you look at this example right here we have 1 1 0 we have uh one uh one and zero and so if we add up 1 one and zero that's like two 0 plus two 0 and that's going to give us two so our answer is basically going to be 1 Z in binary and we do have one and zero right here and it looks like it's like a pretty standard format so we have our carry right here and we have our sum right here so it looks looks like actually Y is going to be our um okay let's just make sure so yeah Y is going to be our sum and Z is going to be our carry that's the purpose of both of these outputs now let's go ahead and so I mean basically what we can say is that this is going to represent a full adder circuit space looking at the truth table so the answer to our first question State the name logic circuit is just going to be full adder now next write the Boolean expressions for the two outputs Y and Z in the truth table as summer products and state the purpose of each output so in order to State the purpose of each output we can just look over here looks like Y is going to be our sum and our carry is going to be uh Z and maybe we'll just write this in specific colors just to be um a little bit more clear so the carry is going to be purple and this is what this looks like right here so we have our sum and we have our carry so Y is going to be our sum y will be our sum and Z will be our carry so now that we've done that let's go ahead and actually write the uh sum of products so remember to do this we need to look at we're going to start with just um Y and we're going to look at all of the uh instances in which Y is equal to 1 and we're going to match those up with ABC so first off we here for this one we have a a and b are zero and C is one so we're going to have a b and C uh here we have a is zero B is 1 and C is zero so we're going to have a b and c um here we have let's see um we have okay a b and c and here finally we have um a or sorry it's not going to be uh a not a that's going to be a b and c so we can go ahead and write these in the next page let's check our answers looks about right let's move on to Z so for Z I'm actually going to just use different color just to make it a lot clearer so Z right here we have a one for this uh Row one for this Row one for this row and a one for this row so for Z we're going to have first of all this one is going to be ABC uh we're going to have a b and not c um we're going to have let's see a not b and c then we're going to have not a b and c so let's go ahead and transcribe this to our uh next page and that looks about right let's check the mark scheme and we are good to go now one thing I want to point out is that under our purpose right here we just wrote summon carry which should probably be okay but it's better to write some bit and carry output those are the more exact terms for what we're looking at in terms of the circuit anyways let's move on to our next set of circuits the next the next type of circuits we're going to talk about are called flip-flop circuits now these are usually used to store a single binary digit and therefore are generally used in data storage what flip-flop circuits do is store data and then allow us to also modify this data these are the basic building blocks of registers and are also used for tasks like timing synchronization operations and making decisions in larger circuits for the a-level exam we need to know the role which you just gone over how to draw them and how to interpret their truth tables now the first flip-flop circuit we're going to talk about is going to be an Sr flipflop now an Sr flip-flop consists of two nand gates so this is our first nand gate and this is our second Nan gate and as you can see they're kind of wired in a weird way the output of one Nan gate is the input to the other Nan gate now we don't need to go completely into how this works we do need to understand the truth table that goes along with this circuit and part of that is understanding the inputs so we have two inputs which are R and S now one of them is going to be is going to be a reset input and the other one is going to be a set input set is setting the value and reset is resetting the value that is stored in the circuit so we have our outputs are q and not q but generally if you look at our truth table we're going to have the current value of Q so this is the current state of our output of Q and based on the state and reset signals qn +1 is going to be the next state what's going to occur next based on the r and s so let's take a quick look at how the state and reset uh signals affect the next state based on the current state we're going to start right here here set is zero and reset is zero and set is zero and reset is zero now we have the same we have the same set and reset inputs but we have different values of our current state which can be either zero or one now because both these are zero that means these set and reset operations are not being executed so our next state is the same as the previous state we'll just circle this in red there has been no impact because set and reset are doing nothing now if we go to our next group where both are where we have set is always going to be zero and reset is always going to be one basically reset is the only operation that's being executed because reset is being executed it's basically resetting the value of um of the circuit so whatever the current St is which is just 0 and one those are all going to become zero because think about it as refreshing the circuit next we have set or next we have 1 Z and 1 0 now this is interesting because when we run the set signal what we're doing is we're setting the value of the circuit to one so whatever the value of the circuit was before whether it was 0o or one the next value of the circuit is going to be one and one now finally we have both our set and reset signals or inputs at the same time this kind of confuses the circuit and as a result we're going to get an invalid output now before we move on I just want to make it clear that you need to be able to draw this circuit you don't necessarily need to be able to understand the circuit but you do need to be able to understand the truth table and reproduce It Anyways the next circuit we're going to look at is going to be called a JK flip-flop now A J flipflop differs from the SR flip-flop in a few ways so first of all we have um we have four nand Gates we still have a J and K input even though these are called J and K these stand these really mean set and reset so regardless what the letters are we're going to have set and reset inputs as before we're also going to have a clock and we the clock has a specific role now we're not going to see the clock input in the truth table but the reason the clock there gets the heart of why we have JK flip-flops so in our previous uh circuit in our Sr flipflop basically when we have one as both the set and reset we get an invalid input the JK flipflop is essentially meant to improve the SR flip-flop to eliminate invalid results so the truth table for the JK flip flop is the same as the SR flip flop except for the last two inputs which is where set is one and reset is one which gave us a um an invalid value before so in the JK flip-flop instead of one instead of set and reset uh being one both producing an invalid value it just switches whatever the current state is so right here a current state is zero so I'll just let's go ahead and erase this so it's clear what we're focusing on but right here our current state is zero a one for the set and the one for the reset um switch zero to one so basically they switch it to the opposite value similarly right here we have one and one again but our input is actually just one our current state rather is one so we're going to we're going to flip it to the opposite value which is zero so now in our JK flip-flop instead of getting an invalid value um for the last two rows of our truth table we're simply going to switch around our current state and that is the primary difference between a JK flip-flop and an Sr flip-flop now the clock is there to Aid in this process the role of the clock is to allow us to accomplish what's in these two rows right here so those are Sr and JK flipflops again you need to understand the truth tables and know how to draw them you also need to understand the roles with the general roles of of flip flops being to store a single binary digit and the role of the JK flip flop to eliminate invalid results that being said let's go ahead and let's take a look at a practice question so right here we need to draw a logic circuit for an Sr flip-flop and label the inputs so if we go back to right here we remember that uh and that we remember that in our Sr flip-flop we have two actually these are nor Gates I I mentioned these as being nand Gates it's my mistake these are actually going to be nor Gates versus in our uh in our JK flip-flops we actually have uh NAD Gates anyways what we need to do is we basically need to redraw this as an answer to that question so what we're going to do right here is we're basically going to draw the same circuit so we're going to have we can have S and we can have r as our input doesn't really matter what that is uh we're going to have one going into uh one Norgate and another going into another Norgate and actually you want to well I guess we'll make these a little bit bigger because we do have some space so we're going to have we're going to have that we'll just draw that right there and that right there and so this is going to be one Norgate and this is going to be another Norgate okay so we're going to draw these like this and then the output from this one is the output from this one is going to be the input to this one right here and the output from this one is going to be the input for this one right here and this is a god- awul drawing but let's go ahead and see whether it's correct and yeah I did draw it correctly as ugly as it looks anyways that's the that's actually the only practice question I've seen related to this on all the a-level exams that have been given so far and yeah I mean this is basically it this is the mark scheme um we need to have so interestingly this has nand Gates right here so it says one correct nand or Norgate with two separate inputs and one output second correct logic gate of the same type as the first so actually I guess that diagram wasn't wrong but you need to have either two nor Gates or two nand gates so two nor or to nand it's an important clarification that actually I wasn't really aware of anyways correct connections between logic gates correctly labeled inputs and I think we're good to go again we could have even drawn Nan Gates and we would have been good to go this is another version in that has nor Gates rather than Nang Gates and this brings us to the end of this tutorial now to close out this video I just wanted to make a few comments first of all this was a highly complex video there were a lot of very very specific Concepts here that I never covered in any of my computer science undergrad classes to tackle these you need a strong foundation in booleans and binary mathematics however it's not as scary as it seems there's a variety of Highly specific Concepts but the a-level curriculum doesn't delve into them with a ton of depth so you kind of need a surface level knowledge of a bunch of different concepts but there's nothing that you can't handle anyways that being said for more tutorials like this please subscribe to the channel and smash the like button and stay tuned for topic 14 see you next [Music] time