_________________ /_ /\ \/ _______ / \ / / / / / / /______/ / / / __/ / / _______ \ __/ / / / / \ / /______/ / / _/ / / /______________/ / BLACK SUN RESEARCH FACILITY \ \ / http://blacksun.box.sk/ \______________\/ BOOLEAN LOGIC GATES ================================================= WRITTEN BY [ cos125@hotmail.com :E-MAIL ] BINARY RAPE [ 114603188 :ICQ# ] [ http://blacksun.box.sk/ :TURORIALS ] CONTENTS ======================================= 1. Introduction. 2. A Quick Look At Binary. 2.1 A Little Conversion 3. The Logic Gates. 3.1 The Not Gate 3.2 The And Gate 3.3 The Or Gate 4. Negated Gates. 4.1 The Nand Gate 4.2 The Nor Gate 5. The Exclusive Gates. 5.1 The Xor Gate 5.2 The Xnor Gate 6. Binary Addition. 7. Last Words. ____________________________________________________________________________________________ 1.0 INTRODUCTION ======================================= Before reading this tutorial i suggest you read the bsrf tutorial on different number base's and the first few sections of the bsrf assembly tutorial unless you are confident that you understand binary and and a bit of boolean algebra would help, never the less continue on and I hope that things become clear to you. 2.0 A QUICK LOOK AT BINARY ======================================= Basically binary is very simple, we as people are used to counting in decimal, 1,2,3, etc..., this is known as base 10 as their are 10 numbers in decimal 0,1,2,3,4,5,6,7,8,9 and no 10 is not one of them, to get ten we put 1 and 0 together when we move past 9, we do this in order to count higher, obviously, and once we get passed 9 we go back to 0 move over one space and put on a 1. 0 1 2 3 4 5 6 7 8 9 <- Reached the maximum of our numbers in decimal 10 <- So we move over one place and put on a 1 and start again 11 12 13 14 15 16 17 18 19 <- Again we reach the maximum so we move over one place and add a 1 20 21 .. .. 90 <- And so on till we reach 90 91 92 93 94 95 96 97 98 99 <- Weve now reached the maximum on both numbers so we have to move 2 places over and add a 1 100 <- And the cycle starts again What we have to remember is that decimal has 10 numbers and is therefore known as base10, binary only has 2 numbers, 1 and 0 and is therefore known as base 2, but what happens when we try and lay out the binary numbers like we did above with the decimal ones? 0 1 <- Already weve reached the maximum of binary numbers! 10 <- Like decimal we move over and start again 11 <- So quickly weve already run out on both sides 111 <- like the decimal number 1 hundred we move over 2 and start again As you can see there isnt much to binary, lets count to ten in binary to get a little more used to it. Decimal Binary ------- ------ 0 00 1 01 2 10 3 11 4 100 5 101 6 110 7 111 8 1000 9 1001 10 1010 See binary is easy enough and if you leave out the first column you will notice that 4 - 7 look like 0 - 3 and remember its just like going from 9 to 10 in decimal, move over 1 place and add on a 1. 2.1 A LITTLE CONVERSION ======================================= So how do we convert from decimal to binary numbers? Sure you could write out a table like above and check it to get the binary value you want but what if your looking for a value for a number like 1275, good look writing a table up to 10011111011 or we could just use the good old repeated division of 2 method. This works by repeatedly dividing the decimal number by 2 and if its an even number record a 0, if its an odd record a 1. Say for example we wanted to convert 57 to binary: 2/57 remainder = 1 = 28 2/28 remainder = 0 = 14 2/14 remainder = 0 = 7 2/7 remainder = 1 = 3 2/3 remainder = 1 = 1 2/1 remainder = 1 = 0 Now if we put those remainders alongside eachother starting from the bottom up we get 111001, which is 57 in binary. 3.0 THE LOGIC GATES ======================================= Well binary is nice n easy n all but if thats all that a computer understands then how does it go from that to a word processor or an entire operating system. Well we build up these complicated tasks using simple logic gates and boolean algebra, boolean algebra was created by George Boole in Ireland in the 1800's, wahey. The gates provide a way to make decisions and more complex tasks are built upon them. These gates accept input of Binary numbers and their output is based on the type of gate and what input was involved. There are three simple gates. 3.1 THE NOT GATE ======================================= The simplest of all the gates is the NOT gate, it just takes a binary value of either 1 or 0 and gives back the oppossite. The NOT gate is symbolised by the operator '~'. Consider the following. A | Q ------+------- 0 | 1 1 | 0 ~0 = 1 ~1 = 0 This table shows all possible inputs and outputs of the NOT gate, this kind of a table is known as a 'truth table'. Fig 1.0 Standard NOT Gate 3.2 THE AND GATE ======================================= The AND gate unlike the NOT gate doesnt take just one input (A) it takes at least 2 (A,B), its symbol is '&'. A B | Q -------+------ 0 0 | 0 0 1 | 0 1 0 | 0 1 1 | 1 0 & 0 = 0 0 & 1 = 0 1 & 0 = 0 1 & 1 = 1 As you can see from the truth table above, the output of a AND gate is only equal to 1 when both A AND B are equal to 1, this is the following. If A = 0 and B = 0 then Q = 0 If A = 0 and B = 1 then Q = 0 If A = 1 and B = 0 then Q = 0 If A = 1 and B = 1 then Q = 1 Fig 1.1 Standard AND Gate 3.3 THE OR GATE ======================================= The OR gate also only takes in 2 parameters, A and B, its symbol is '|' A B | Q -------+------ 0 0 | 0 0 1 | 1 1 0 | 1 1 1 | 1 0 | 0 = 0 0 | 1 = 1 1 | 0 = 1 1 | 1 = 1 The OR gate outputs a value of 1 if either A OR B OR both are equal to 1 If A = 0 and B = 0 then Q = 0 If A = 0 and B = 1 then Q = 1 If A = 1 and B = 0 then Q = 1 If A = 1 and B = 1 then Q = 1 Fig 1.2 Standard OR Gate 4.0 NEGATED GATES ======================================= There are 2 Negated Gates, these are the NOR and NAND gates. Basically these gates act like an OR and AND gate only there output is the opposite. 4.1 THE NAND GATE ======================================= The truth table of a NAND gate is as follows A B | Q -------+------ 0 0 | 1 0 1 | 1 1 0 | 1 1 1 | 0 Notice that it is the opposite of an AND gate. 0 & 0 = 0, ~0 = 1 To wrap this up a bit better we use brackets () ~(0 & 0) = 1 ~(0 & 1) = 1 ~(1 & 0) = 1 ~(1 & 1) = 0 Now the result of the calcuation in the brackets is negated. Fig 1.3 Standard NAND Gate 4.2 THE NOR GATE ======================================= The truth table for the NOR gate is as follows A B | Q -------+------ 0 0 | 1 0 1 | 0 1 0 | 0 1 1 | 0 ~(0 | 0) = 1 ~(0 | 1) = 0 ~(1 | 0) = 0 ~(1 | 1) = 0 Fig 1.4 Standard NOR Gate 5.0 THE EXCLUSIVE GATES ======================================= The final 2 gates remaining are the XOR (eXclusive OR) and XNOR (eXclusive NOR) gates. Here they are. 5.1 THE XOR GATE ======================================= The logic behind this gate is that if either A or B is equal to 1 but not both then the output is equal to 1, here is its truth table. A B | Q -------+------ 0 0 | 0 0 1 | 1 1 0 | 1 1 1 | 0 The gate is constructed as follows. (A & ~B) | (~A & B) (0 & ~0) | (~0 & 0) = 0 (0 & ~1) | (~0 & 1) = 1 (1 & ~0) | (~1 & 0) = 1 (1 & ~1) | (~1 & 1) = 0 Fig 1.5 Standard XOR Gate 5.2 THE XNOR GATE ======================================= The XNOR gate is simply the opposite of the XOR gate, its truth table looks like the following. A B | Q -------+------ 0 0 | 1 0 1 | 0 1 0 | 0 1 1 | 1 Its kind of like ~((A & ~B) | (~A & B)). This is a good time to point out something about boolean algebra, remember that ~ changes the value of an input to its opposite, therefore ~(~A) = A and the 2 ~'s simply cancel eachother out. So XNOR becomes (~A & B) | (A & ~B). Fig 1.6 Standard XNOR Gate 6.0 BINARY ADDITION ======================================= So we all know how to add decimal numbers (im presuming), its easy 1 1 1 + 1 + 2 + 3 --- --- --- = 2 = 3 = 4 But how do we add in binary? Easy watch this 0 0 1 1 + 0 + 1 + 0 + 1 --- --- --- --- = 0 = 1 = 1 = 10 Thats fine but with 1+1 we get a carry over that we have to deal with. So we add an extra space to handle the carry. 0 0 1 1 + 0 + 1 + 0 + 1 --- --- --- --- = 00 = 01 = 01 = 10 Lets write a truth table to handle this data. A B | CO Q -------+-------- 0 0 | 0 0 0 1 | 0 1 1 0 | 0 1 1 1 | 1 0 Notice the new column on the truth table for the carry out (CO). We now notice that CO and Q and familiar, C0 is the same as an AND gate and Q is the same as an XOR. A & B = Q (A & ~B) | (~A & B) = CO Thats fine for adding single bit numbers but what if we want to add 2 8-bit numbers? In this case were going to need a component called a full binary adder. Once we create the full adder we can put 8 of them together to form an 8-bit or byte-wide adder and move the carry bit from one adder to the next. The main difference for us between the first adder and this full adder is that we now need a third input called a Carry-In (CI). Heres the truth table for the full adder. A B CI | CO Q -------------+-------- 0 0 0 | 0 0 0 0 1 | 0 1 0 1 0 | 0 1 0 1 1 | 1 0 1 0 0 | 0 1 1 0 1 | 1 0 1 1 0 | 1 0 1 1 1 | 1 1 If we examine the output youll realise that the top 4 numbers for C0 look like an AND gate for A and B and the bottom 4 look like an OR gate for A and B, while top 4 of Q look like an XOR and the bottom 4 like an XNOR gate. By putting those gates together we could form a form a more complicated and useful circuit such as the adder and thats how a computer builds up from a series of 1's and 0's to addition. 7.0 LAST WORDS ======================================= Well in this tutorial we looked at Logic Gates and how they perform functions on binary numbers, Gates can be used to build up much better and sophisticated functions such as loops and comparisons, used together these can easily perform multiplication and division and we can use these in everyday equipment, from washing machines and microwave ovens to motion sensitive cameras and pc's. SHOUTS ======================================= Starman_Jones - Thanks for everything over the years (especially for my own room). Vsus - I am never drinking Tsambuca with you again :P. Delusive - Nice arse luv :P. BSRF - Thanks to every-1 at BSRF for releasing this and for being a good laugh :). ALL @ IRC.BOX.SK