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.