Basic Unsigned Numeric Encoding
In order to represent and manipulate numeric values within the circuits of a computer system it is
necessary to use some coding scheme whereby each number can be represented or "encoded" by
the pattern of electrically on/off states in a collection of circuits. For a computer, the simplest and
fastest scheme for encoding numeric values is the Unsigned Binary Encoding scheme.
Encoding
- replacement or representation of some discrete data object (number, character, etc.) by an
on/off circuit pattern
- an "encoding system" is a one-to-one function for encoding a set of related data object (e.g. all
integer values between 0 and 100 inclusive, or all the letters of the alphabet)
Number of Circuits Required for Encoding
- each circuit will be in either one of two states : "on" or "off" (for convenience we will write
these using 1 for "on" and 0 for "off")
- only two possible patterns are possible for a single circuit: 0 and 1
- with two circuits, four patterns become possible: 00, 01, 10, and 11
- each time another circuit is added, the number of patterns doubles; half of the new patterns will
have this additional circuit turned on and the other half will have it turned off.
| Number of Circuits |
Number of Patterns |
| 1 |
2 |
| 2 |
4 |
| 3 |
8 |
| 4 |
16 |
| .... |
.... |
| 8 |
256 |
| 10 |
1024 (1K) |
| 16 |
65536 (64K) |
| 20 |
1048576 (1M) |
| n |
2n |
- in order to encode a collection of data objects, the encoding scheme must have at least as many
patterns available as there are objects to be encoded
- for example, if we wished to encode the integer values from 0 to 9, a minimum of 4 circuits
(providing 16 patterns) would be required
The Decimal Odometer Analogy
- most cars have an odometer which records the total distance traveled (in either kilometres or
miles)
- a typical odometer might have 6 digit "wheels" with the right most wheel rotating most rapidly
from 0 up to 9 and back to 0 again every 10 kilometers (or miles); the next wheel to the left
would only make this change every 100 kilometers; etc.
- a 6 digit odometer only has 1,000,000 different values (0 to 999999 inclusive); a car driven
6,372,945 kilometers and one driven 7,372,945 kilometers would have the same odometer
reading
- notice that the 6 digit wheels are built-into the car, and do not automatically expand to 7 digit
wheels once the car passes 999,999 kilometers
- because the decimal positional notation is so familiar to use, we recognize without much
thought that an odometer reading of 372945 means
- 3 x 100000
- +7 x 10000
- +2 x 1000
- +9 x 100
- +4 x 10
- +5 x 1
- each digit wheel of an odometer is analogous to a single circuit
- where each digit has 10 different values (0 to 9), a single circuit only has 2 ( 0 and 1)
- the odometer within a car is analogous to a "word" in a computer system (i.e. a word in a
computer system is the basic unit for representation of a simple numeric value)
- different makes of cars may have a different number of wheels in their odometers; different
makes of computers may have a different number of circuits (bits) in their words
- the number of circuits (bits) in a specific computer's word unit is "fixed" and can not be
modified just because all the patterns have been used up
- a 6-bit word with a pattern of 100101, if viewed as a positional system analogous to the 6-digit
odometer, would mean
- 1 x 32 (2 x 2 x 2 x 2 x 2)
- +0 x 16(2 x 2 x 2 x 2)
- +0 x 8(2 x 2 x 2)
- +1 x 4(2 x 2)
- +0 x 2
- +1 x 1
Unsigned Binary Encoding
- notice that to this point we have not been concerned with representing negative values; we
have been dealing with "unsigned" (i.e. assumed to be 0 or positive) numbers
- the "bits" or circuits of a computer "word" are imagined to be lined up in a horizontal row
regardless of their actual physical positioning
- each bit has its own "weight" with the right-most bit having a weight of 1 and every other bit
having a weight which is double that of the bit to its immediate right
- notice that the sum of the weights of all bits to the right of any specific bit is always one less
that the weight of that bit
- in the (unsigned) binary encoding scheme, the numeric value being encoded is the sum of the
weights of the bits which are turned on
- for example using an 8-bit "word"
| pattern in word: |
off
(0) |
on
(1) |
off
(0) |
off
(0) |
on
(1) |
on
(1) |
off
(0) |
off
(0) |
| weight |
128 |
64 |
32 |
16 |
8 |
4 |
2 |
1 |
the value of this encoded word (01001100) would be 64 + 8 + 4 = 76
- conversely to encode a particular value, for example 137, in an 8-bit word using the (unsigned)
binary encoding scheme
- the bit with weight 128 must be on (since the sum of all the remaining bits only adds up to 127)
- if the bit with weight 128 is on, then the remaining bits must contain a pattern that adds up to
137 - 128 = 9
- the bits with weights 64, 32, and 16 must be off, since if any of them were on the total would
add up to too much
- the bit with weight 8 must be on, leaving 9 - 8 = 1 to be represented by the remaining bits
- the bits with weights 4 and 2 must be off
- the bit with weight 1 must be on
- therefore, the 8-bit (unsigned) binary encoded pattern for 137 is 10001001
| weight |
128 |
64 |
32 |
16 |
8 |
4 |
2 |
1 |
| pattern |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
Multi-Column Addition
- addition of multi-bit binary numbers is done one binary column at
a time, starting with the right-most binary column
- just as when adding two decimal numbers, the addition of a column of
two digits results in two values: the
"column result" and a "carry" value which must be carried left and
included when adding the next column to the left.
- when adding two binary numbers, each column except for the
right-most requires the addition of three binary digits: two from the
numbers and a (possibly zero) carry from the column to its right
- therefore, the addition of two binary values requires
the (repeated) ability to add three single bits at a time to create a
"result" and a "carry" for every column
Each binary column therefore requires us to consider three bits: two
bits from the actual numbers being added, and a third bit coming from the
"carry" out of the column to the right. With three bits, there are only
eight possible combinations:
Three bit addition, showing "result" and "carry":
0 + 0 + 0 --> result: 0 carry: 0
0 + 0 + 1 --> result: 1 carry: 0
0 + 1 + 0 --> result: 1 carry: 0
0 + 1 + 1 --> result: 0 carry: 1
1 + 0 + 0 --> result: 1 carry: 0
1 + 0 + 1 --> result: 0 carry: 1
1 + 1 + 0 --> result: 0 carry: 1
1 + 1 + 1 --> result: 1 carry: 1
We can express the above list In tabular form:
| Adding Two Binary Numbers:
The 8 Possible Input Combinations and Their Outputs |
| bit values being added
carry in from previous column |
0
0
0 |
0
0
1 |
0
1
0 |
0
1
1 |
1
0
0 |
1
0
1 |
1
1
0 |
1
1
1 |
| column result |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
| carry to next column |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
Multi-Column Subtraction
- although not always taught in primary school in this fashion, subtraction can be done in a
similar manner, one column at a time (primary school subtraction often teaches children to skip
over several (zero valued) columns when "borrowing" enough to perform a "proper
subtraction
| 3-Bit Subtraction: The 8 Possible Input
Combinations and Their Outputs |
"Subtrahend"
minus "minuend"
minus borrow from previous |
0
0
0 |
0
0
1 |
0
1
0 |
0
1
1 |
1
0
0 |
1
0
1 |
1
1
0 |
1
1
1 |
| column result |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
| borrow from next column |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
Application of Logic Gates to Basic Binary Encoding
Simple binary logic gates operate on one pair of single bits at a time, but most basic computer
operations work on pairs of multiple bits. In general this increases the speed at which the
computer operates. For example, comparing two patterns of 16 bits each in parallel should be 16
times faster than performing 16 separate comparisons on pairs of single bits.
Each logic gate takes a certain (small) amount of time to respond to a change in its inputs; this is
called the gate switching time. The time required to perform any basic computer instruction
depends upon the maximum number of logic gates signals must pass through to complete the
instructional operation (plus some other "overhead" factors.
The fastest instructions should therefore be those which involve no operational logic gates: the
shifts and rotates, followed by those which involve only one level of operational logic gates: the
bit level logical operators, and so on.
In actual practice, computer instructions are organized so as to start on regular internal clock
pulses (a 200MHz clock, for example, providing 200 million pulses per second). Even at today's
high clock speeds, modern gate switching times in VLSI is fast enough that multiple logic gates
can be managed within a single clock pulse "frame"; however, when the instruction becomes
complex enough that the number of logic gates on the longest path reaches a certain level, the
instruction will require multiple clock pulse "frames" to complete.
Fast Operations That Require No Operational Logic
Gates
Shift
- Left Shift - each input bit is reproduced as an output bit one position further to the left
except for the left-most input bit which is ignored (or copied to a status flag); the
right-most output bit is set to 0.
For example, LeftShift of (00110101) would be (01101010)
Note, as a result of this "shift" each bit gets moved to a position with double the weight
of its original position, and (provided no 1-valued bit is lost off the left-end) the result
for an unsigned binary encoded number is twice the original value.
- Right Shift (Logical) - same as the Left Shift except for the direction of the shift;
RightShift of (00110101) would be (00011010), with the right-most 1 being lost (or
copied to a status flag).
For an unsigned binary encoded number, the RightShift is a fast method for
dividing by 2.
- Right Shift (Arithmetic) - many computers also include another version of the
RightShift in which the left-most output bit is a copy of the left-most input bit (instead
of being automatically 0).
This is sometimes called the "Arithmetic" Right Shift because of its use with a signed
binary encoding scheme, called 2's Complement.
Rotate
Bit Manipulation with a Single Layer of Operational
Gates
Note that while these computer operations have the same names as the logic gates on which they
are based, they operate on two words in parallel and not on a pair of bits.
- OR - Turning Selected Bits of a Word "On"
- If we wish to force the right-most two bits of a 6-bit word to be "on" (we want the
result to look like xxxx11, where the x's represent the original bit values),OR the
original pattern with 000011
- AND - Turning Selected Bits of a Word "Off"
- If we wish to force the middle two bits of a 6-bit word to be "off" (we want the result
to look like xx00xx)AND the original pattern with 110011
- XOR - "Toggling" Selected Bits of a Word
- If we wish to reverse the left-most bits of a 6-bit wordXOR the original pattern with
110000
- NOT - Reversing All Bits of a Word
- NOT the original pattern (which is the same as XOR'ing with 111...1)
Unsigned Binary Addition - Multiple Layers of Gates
Addition of 2 Bits
- note that although there are two logic gates there is only one layer of gates required
Addition of 2 Multi-Bit Words
- note that because of the carry requirement from each column to the next, the number of layers
of gates increases with the number of bits in a word; effectively, from a gate switching point of
view, addition of 32-bit words should take 4 times longer than addition of 8-bit words.
More Complex Instructions and CISC Computers
CISC - Complex Instruction Set Computer
Factors Which Reduce Instruction Execution Speed
- larger number of logic gate layers in the instruction circuit
- requirements to access data value in external memory (with sub-factors:
the number of accesses required, and the type/speed of the external memory)
Alternative: RISC - Reduced Instruction Set Computer
Binary Operation Flags
Performing arithmetic operations produce results which require more space
(more circuits/bits) than were provided by individual input data values.
For simple operations, such as addition and subtraction, this "extra" space is only one bit and can
be handled by the use of a "Carry/Borrow" (single-bit) flag. Other operations, such a
multiplication and division, require different methods for handling this problem; these methods are
much less standard and vary considerably from computer to computer.
The "Carry" Flag
Addition
- as we have already seen, every column in a (binary) addition produces a "carry" signal
for the next column
- for the left-most column, there is no subsequent column for this signal to go to
- if there is a carry (i.e. the carry signal is 1 / the Carry flag is on) out of the left-most
column for an addition of two (unsigned) binary encoded values, it means that the actual
result is two large to fit into the number of bits/circuits available (for this computer)
- the Carry flag should be checked following any addition of (unsigned) binary values, to
ensure that the results are correct; the "checking" requires execution of a separate
instruction following the addition. For some mythical processor this sequence might
look like:
- LOAD A FROM @3054 'copy value from memory at address 3054 to ALU
working "register" A
- LOAD B FROM @4190 'copy value from memory at address 4190 to ALU
working "register" B
- ADD_TO A FROM B 'replace value in "register" A with sum of original values
- IF_CARRY_GOTO ERROR_ROUTINE 'go somewhere else to handle error if it
occurred
- ...value in "register" A is OK
Subtraction
- Subtraction works the same way as Addition except that we use a "borrow from next
column" signal instead of a "carry to next column"
- rather than implement a separate "Borrow" flag, most systems re-use the "Carry" flag to
record the final column "need to borrow" indicator
- following an (unsigned) binary subtraction, if the Carry flag is on, then
- the result is wrong (as an unsigned binary value)
- an attempt was made to subtract a larger number from a smaller number
- Subtracting and then checking the Carry flag can therefore be used as a method for
determining the relative size of two numbers
The "Zero" Flag
- in addition to a "Carry" flag, all computer processors have a "Zero" flag (or some functional
equivalent).
- the "Zero" flag is turned on, when all "result" output bits are turned "off" i.e. when the result is
zero; the "Zero" flag will be turned off if any of the result bits are "on"
- this flag is set/reset by the bit manipulation operations (OR, AND, XOR, NOT) and by the
basic ADD and SUBTRACT operations; other instructions may set/reset the Zero flag, but
these vary among different processors.
- to test to determine if two values are equal, subtract one from the other and then check the
zero flag; if it is on, the values are equal
Multiplication - Double Word Result
- binary multiplication is performed as a series of left shifts and additions
- notice that when multiplying two 3-digit (decimal) numbers, the result may require as many a 6
digits
- similarly when multiplying two 16-bit (unsigned binary encoded) words, the computer's ALU
must allow for as many as 32 bits in the result
- a simple single-bit flag is not sufficient to handle this problem
Division - 2 Results
- unlike addition, subtraction, and multiplication, Division produces two results: a Quotient and
a Remainder when dealing with integers values (such as unsigned binary encoded values)
- a computer's execution unit must make some provision for handling this double result;
however, the specific method for handling this varies from computer to computer, and otten
within a single computer, different instructions may handle this problem in different ways.
