Binary Number & Digital Logic written by Conundrum | 12/15/2000 Binary Number System Number Basics The number system we use to date provides a framework for representing quantities as well as performing mathematical computations from basic addition and subtraction to a computer program with thousands of lines of code. The system we use today are the Arabic numberals: 1, 2, 3, 4, 5, 6, 7, 8, 9, and 0; which are now referred to as symbols or digits. While some systems may use more or less of these digits than all ten, we will be learning the binary system which uses just two: 1, and 0. Base, Point, and Place Value The positional numbering system you encounter daily is the base ten system which consists of a base or radix, point, and place value, same as all other systems. Base The base of a system determines the number of symbols in that system. For example, the decial system has a base of ten because it has the opportunity to consist of digits with a value as high as 9. The octal system, base eight, uses digits up to the value of 7. And the ase for the binary system is 2, which means it consists of values up to the numeral 1. Within a system, no single digit can represent a higher or equivalent quantity to the base. So in the binary system you can use the first 2 digits: 1 and 0 but not 2, 3, 4, 5, 6, 7, 8, or 9, because they are higher than the base. The base of a number is written as a subscript to that number. For example the number 101 base 2 (the "base 2" would be shown as 2 (subscript (below the number)). Point The point of a numbering system is used to divide whole numbers from fractions and takes the name of the system in which it is used in. As in the decimal system it is called a decimal point; in the binary system it is a binary point. Whole numbers are always placed to the left of the point, and fractions to the right, this doesn't change no matter what system you are using. Place Value Place value describes the location that the number holds. Just as every number has a value so does every position. Looking at the decimal system number 105.0. The first digit (looking left) tells how many ones are in that number, the second digit - how many tens, and the third - how many hundreds. The number to the right of the decimal point shows how many tenths. Notice the 0, it serves as only a place holder with no value so that 1 and 5 can hold their position. It can also be read as 10*0 for ones, 10*1 for tens, 10*2 for hundreds, and 10*3 for thousands. The pattern found to the left of the point is the same as to the right, so it would be from 10*0, 10*-1, 10*-2, 10*-3, and so on. Other Base Systems There are many more systems than just the decimal and binary.There is the ternary (base 3), the quaternary (base 4), the quinary (base 5), the senary (base 6), the septenary (base 7), the octonary (base 8), and the nonary (base 9), base 2 and base 10 you already know. Binary Mathematical Operations Binary to Decimal Conversion Learning to convert numbers from one system to another is very important because it will aid in trouble shooting a problem or in certain situations you may not be able to use one system but can use another so you must improvise. The easiest of these is from binary to decimal because all you have to do is computate the digit value by the number multiplied by the place value then add these all together to form one number. As an example I have the binary number 1101.0 which we want to make a decimal number. We will first take the place values: 2*3, 2*2, 2*1, and 2*0. Take these and multiply them by the digit in that place value. So this is done as an example: 1*(2*3)=8, 1*(2*2)=4, 0*(2*1)=0, 1*(2*0)=1, and 0*(2*-1)=0. Next take all of these totals and add them together: 8+4+0+1+0=13, and 13 is our decimal number. Decimal to Binary Conversion As you may have guessed, the determining factors in this conversion are the place value and digit value. There are actually several methods showing you the "subtraction method" which is one of the easiest do to the fact that the bases are so small. This method consists of only three steps. First, determine the largest binary place value that can be subtracted from the decimal number. Second, subtract the base two place value from the decimal number. And third, if there is a remainder left over, repeat steps one and two. For an example I will use the decimal number 13. First we determine what to subtract with, 2*4 is to large, but we can use 2*3. Next we will subtract (2*3) from 13 which ends up as 5. And lastly, we see that we have a remainder of 5 (remember, in the binary system, numbers must be 1 or 0) so what can we subtract with 5? (2*4). We subtract that with 5 and end up with 1. The only thing we can subtract from 1 is (2*0) so we are done subtracting. Once we have done these steps we see that the place value (2*3) and (2*2) were used so we place a 1 in those positions. (2*1) was skipped so a zero goes there, and we used (2*0) so a one goes there. The binary number for 13 is 1101 Binary Multiplication, Subtraction, Addition, and Division Multiplication The rules for multiplying binary numbers is the same as what you should be used to with the decimal system so we will not cover this subject. Subtraction There is a slight difference in subtracting binary numbers than you are used to. When subtracting we use these rules: 0-0=0, 1-0=1, 1-1=0, and 0-1=1 borrow 1 (which is where the differences come in). When you subtract (0-1) the only thing is that you must take a one from the next highest place value. Addition The only difference between addition and what you have seen before is similar to our subtraction rule. When you add together (1+1) it equals 0 and you carry a 1 to the next highest place value. So the equation (1+1) by itself would be 10 because (1+1)=0 and you carry a one to the next highest place value. Division In binary division the same rules apply that you are used to with the decimal system. Digital Logical Operations Previously, you were taught how to read and convert vinary numbers. This knowledge, you will use to understand logic operations and the logic gates that perform these functions The building blocks of digital circuits are logic gates which perform a specific logic function. It is the arrangement of these gates which determine the difference between a computer and a calculator. The gates themselves are relatively simple to understand, but it's the combination of these blocks that are more complex. The Basic Logic Operations There are three basic logic operations: ANDing, ORing, and Complementing. These operations, both singly and combined, form the operations performed by electronic switches, known as gates. Logic Levels Electronic switches or gates may have one or more inputs but will always have only one output. There are only two voltage levels that are usually associated with these inputs and outputs, which is 5 volts and 0 volts. These two voltage levels are represented by ones and zeros. These are called logic conditions or levels. The higher voltage is represented by a one and the lower by a zero. This term is "positive logic". The condition of a logic gate is determined by its output level, not its input. Logic gates are always either on or off, true or false, active or inactive, and high or low. Therefore, if the level of an output is high, then the condition of the gate is active, true, on, and high. The OR Function In the OR function the current flow is either through switch A or B. This function states simply that if any or all of it's inputs are true then the output is also true; if the inputs are all flase then the output is false. The OR function is represented in mathematical computation by the addition sign (+). When it is read in algebraical formulation it is read as "or" not "plus" so the equation A+B=C is read "A or B equals C" not "A plus B equals C". Looking more closely, A+B=C means: if switch A closes, the light will light. if switch B closes, the light will light. if both switches close, the light will light. if both switches remain open, the light will not light. In digital logic we let ones and zeros create the equation, not letters, so if a closed switch were true, the open switch false, and the light being lit, the desired condition being true, you can compose four equations with 1 being true and 0 being false: 1+0=1 (switch A closed, B opened) 0+1=1 (swich A open, B closed) 1+1=1 (switch A closed, and B closed) 0+0=0 (switch A opened, and B opened) These equations should look similar to you from gradeschool algebra but they are not. If you look at the third equation you will notice it may look wrong. However, it is not wrong because when studying digital logic we use Boolean algebra. From these four equations you can derive a truth table which is simply a summary of the equations with values inserted for the variables for a gate in chart form. Functions are also represented by gates which are graphical representations of the function. The AND Function In this function the path for current flow is through both switches. The function states the the output will only be true if all inputs are true or all gates are true. Along with the OR function, the AND function also has a mathematical symbol. This is the times symbol (*) which is read as "and" not "times" or "multiply". It can also be represented by an absense of any symbol at all, such as in this equation: AB=C. At a closer look: 1*0=0 (if switch A alone closes, the light will not light.) 0*1=0 (if switch B alone closes, the light will not light.) 1*1=1 (if both switches close, the light will light.) 0*0=0 (if both switches open, the light will not light.) Complementation Complementation is the inversion of a signal. Unlike the other two operations, complementation (aka: inversion or negation) is not performed by a gate. The complement of a one is zero, the complement of zero is one (it is always the opposite). Just light high is low, true is false, and 100101 is 011010. Complement is indicated by a "superior bar" which is a line placed above the variable or numeral to be complemented. In this case, the numeral 100101 would be complemented as 100101 with a straight line above the number. You would simply see it this way in algebraic formula but it would be read as "not 100101". The complement for A is A with a line above it, read as "not A". If A were one, then not A would be zero. The complement of ABC is ABC with a line above it read as "not A and B and C" it is not read as "not A and not B and not C" or "not ABC". This is because, if you recall, "and" has a meaning of it's own. You can also negate twice, this is simple known as "double negation". It is written with two lines inserted above a variable instead of just one and as read as "not not A" with A being the example variable. So if A equals 1, not A equals 0, and not not A equals 1. Whenever a complement is present, it will be shown as a inverter or bubble on the tip of the gate. Schematically, ti will be shown as a small circle directly to the right of a gate. This circle is also known as a "state indicator". Combinatorial Functions There are three combinatorial functions. These are the NOR function which consists of the OR function and an inverter on the output, the NAND function which consists of the AND function with an inverter on its output, and the Exclusive OR (XOR) function which outputs a high when its inputs are different and low when they are the same, and the Exclusive NOR (XNOR) function which is a combination of the XOR function and another complement. Inhibited Gates Inhibited gates simply involve having a compliment on one or more of its inputs instead of on the output. Equivalent Gates This term states to two or more gates that perform the same function. This is important because of the fact that gates are not sold individually. You are given chips with prepackaged gates and must stay within the refrains of your chip. So if you had to call on an AND function but no AND funtions were available then you would have to use a different gate, or a combination of gates to get the desired effect. Timing, Triggering, Clocking & Bistable Devices Most digital circuits rely on sequenced events. Digital devices with multiple inputs require that those signals are sufficiently strong, propertly shaped, and of proper duration and specific sequence. Timing Synonymous with sequencing is timing. This is no more than a way of representing a sequence fo events. Timing represents what is happening in the device from moment to moment as a signal is applied. A timing diagram is a graphical description of an event divided into equal time periods. This is just another way of showing what is going in inside the circuit. Triggering The act of changing a digital electronic device from one condition to another. There are two types of triggering, edge and level. Edge triggering is when the device may be triggered by either the beginning or the end of a signal. However, level triggering reacts on the state of the signal instead. Clocking This determines when a circuit will react to the trigger or input. Instead of reacting immediately to a change of input conditions the circuit will wait for the clock pulse before accepting an input. Just like triggering, clocking also has the two types of edge and pulse. Bistable Devices The most common digital circuits are bistable. Bistable devices have two stable states, latch and flip-flop which we will cover next. Once these circuits are set to a certain condition, the device will remain the same and constant until the circuit is reset. Latches & Flip-Flops These simple devices are at the core of all digital devices. Though numerous, they all share the same following characteristics: The ability to store and pass on information or data. At least one input for data. Two complimentary outputs which are designated as "Q" and "not Q". The device condition is determined by the state of Q. When the input condition makes Q equal to 1, the device is considered "set". When the input condition makes Q equal to 0, the device is considered "reset". They have the ability to be set by pulsing the preset input regardless of the state of the clock or data inputs. They have the ability to be reset by pulsing the clear input, regardless of the state of the clock or data inputs. Set / Reset Latch (RS) A latch is a simple bistable device. A latch is also known as a rudimentary memory or bistable multivibrator. Input/Output An RS latch has two data inputs and two outputs. The data inputs are labeled, (S) for Set and (R) for Reset. The outputs are labeled Q and not Q. Set/Reset These simple memory devices can be Set or Reset by placing a brief input on the Set and Reset lines. The device then holds or stores that information once the input is taken away. Race We must also consider what would happen when an attempt is made to change a latch to the disallowed condition. A latch's output, like a logic gate, is dependent upon the inputs. But unlike a gate, in a latch the sequence in which the inputs are applied is very important. When a latch is changed to the disallowed condition, as when both data inputs are driven low, or both data inputs are driven high, it is impossible to change both inputs at precisely the same instant. In essence, it becomes a "race" to see which input will control the output. RS Flip-Flop The difference between a latch and a flip-flop is that latches are unclocked, they can be triggered at any time and flip-flops require a clock pulse along with a trigger to change states. You can create an RS flip-flop from a RS latch by adding a clocking circuit. Clock The clock in this circuit does two things for us. First, in enables or disables both AND gates simultaneously, and it provides a window to change the flip-flop. Preset/Clear This input will allow you to Set or Reset the condition of the various devices without an input on the clock line or the data input lines. D Latch & D Flip-Flop D Latch The D stands for data or dely. Adding a D latch to a circuit makes it impossible for this latch to create a disallowed condition. The single split data input has killed the chance of any input being the same state. If there is a high on the data line then one input will be high, the other low. Consequently, if the data line is low, the opposite will happen. D Flip-Flop The D flip-flop also makes use of a single split input to eliminate the problems of race. This makes the circuit HAVE no disallowed condition. JK Flip-Flop The JK flip-flop is the most widely used flip-flop in digital equipment. Like the D flip-flop, it is not subject to race conditions iwth the attendant undefined output. The JK flop-flop, unlike any other, represents "so far" and has four possible input conbinations: no change, or toggle. The first dfference you'll notice in this flip-flop is how the outputs are fed back to the inputs. This accounts for the uniqueness of this flip-flop, as well as the elimination of race and it's ability to toggle or change. Master-Slave Flip-Flops The master-slave relationship in these flip-flops do two important things. First, they eliminate the possibility of race and allow flip- flops to be cascaded or connect together input and output. Logic Symbol Elements These logic symbols show different types of triggering on the clock as well as the preset and clear inputs. In the logic symbols, notice that this sybol (> ) indicates edge, while the symbol (o) indicates a low as the active condition. Adders, Subtractors, Counters, & Registers Adders & Subtractors Half Adder This adder has two inputs, A and B. It also has two outputs, S (sum) and C (carry). In these gates there are certain rules that the outputs must follow similar to many other types of gates we have already covered: The sum output is high when A and B are opposite logic levels. The sum output is low when A and B are the same logic level. The carry output is hgih only when A and B are both high. The outputs of these circuits flow the same rules of binary additon. Pull Adder This is simply nothing more than two half adders with their carry outputs OR'ed together. This adder not only can add the information on the A and B data inputs, but it is also able to add data on the C data input, which is a "carry in" from a preceding stage. Subtractor These circuits also follow the same rules of binary subtraction. There are two types of subtractors, full and half. The full subtractor has one more input than the half subtractor, this additional input is the "borrow in" input. This configuration is more versatile than the half subtractor because it allows the full subtractor to be used in ocnjunction with other subtractors. Digital circuits, mainly do not use these type circuits to subtract but you may occasionally come in contact with them. They will usually use addition to also subtract through the help of an inverter circuit which uses processes known as twos and ones complementation. Counters Also known as dividers or accumulators. These "counter" are circuits that count input pulses. Counters output a pulse for every one or more input pulses. Because they can be configured to output a pulse for any number of input pulses, counters can be used to divide as well as count. These devices are basically flip-flops or latches cascaded together. Counters are structured in two basic configurations, asynchronous and synchronous. Asynchronous counters are also known as serial or ripple- carry counters. Each latch in these counters uses the previous stage's output as an input. Because of this dependency the action of the latches or flip-flops is sequentialin a serial counter. Synchronous counters, also known as parallel counters, are configured so that they may be triggered simultaneously or each flip-flop or latch in the counter can change states at the same time without problems. Registers Registers are used to store information, but unlike a flip-flop, a register can store more than one bit of information at a time. Registers are also used to act as buffers, to generate sequences, to divide, and to convert information from serial to parallel format and back again. Format, as it refers to registers, refers to the method of inputting and outputting information. These formats will either be serial or parallel. Serial format describes a configuration that allows information to be transferred in one bit at a time only. Parallel format describes a configuration that allows information to be loaded or unloaded in a singel operation with more than just one bit at a time. Conclusion Thankyou for taking the time to get to the end of this document. Hopefully I didn't loose you too much, but if you have any questions regarding this tutorial please let me know. With the information gathered here you should now have no problem reading, converting, and performing algebraic formulations with binary and other number systems. You should also be able to read, convert, and create digital equipment from the ground up, starting with the most basic digital circuitry.