# 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

• 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

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

• Left Rotate and Right Rotate are identical to the corresponding "Shift" operations except that the input bit which is lost in the Shift result is "rotated" to the other end of the output pattern and used instead of the automatic 0.

For example, RightRotate of (00110101) would be (10011010).

## 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

• ### 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)

## 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

• 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
1. the result is wrong (as an unsigned binary value)
2. 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.