L2acm501

Lecture 2: Digital Logic ACM 501

Computers • A computer is a device which can – – – –

input and store data input and store instructions for how to process the data process the data according to the instructions output the results of the data processing

• Modern computers have basic commonalities – store all data in terms of binary digits – use simple semiconductor circuits which can basically • add or subtract numbers • compare two numbers

Digital versus Analog Systems •

There are two types of mathematical quantities – based on physical measurements • can take on any value – actual height of a room can be 2.045623423523... m. – more accurate measurement may lead to more digits – are represented by real numbers

• can change continuously with time – temperature at some location in a physical object – voltage at some point in a circuit

– based on counting • can take on only certain discrete values – number of people in the room can be 0, 1, 2, 3, ... – more accurate counting will not give 1.235 ... people

• are represented by integers • can change only in discrete steps – number of people cannot change in steps of less than 1

• digital comes from digits, meaning fingers

Analog Systems • Directly handle the data – representation is analogous to the quantity being represented

Analog Systems • Seem to be very accurate – actually very difficult and expensive to design and build – signals are distorted as they travel through the system • dispersion on the line, reflections at ends – different paths can introduce different errors

• cross-talk – errors depend on which other circuits are being used

• external noise – errors depend on the environment

• power supply – errors depend on other circuits – even general load on power supply

• temperature changes • physical degradation of circuit elements

– real life measurements are not infinitely precise anyway

Digital Systems • Based on digital representation of data – data can only take on certain specific values – changes in data values are in steps

• Real data may be analog – if we are only interested in limited accuracy • a variable can be given only to one place after the decimal – – – –

0.00 to 0.05 can be approximated as 0.0 0.05 to 0.15 can be approximated as 0.1 0.15 to 0.25 can then be treated as 0.2 ...

• Such a system would be a digital system – more tolerant of errors due to noise or distortions • unless error is large enough to change steps, data value is constant – change from 0.06 to 0.12 keeps value at 0.1

Digital Systems • Even this scheme can be problematic – assume • we need to represent lengths 0 to 100 m, in steps of 0.01 m • maximum hole size on punched card is around 10 cm – each step would correspond to 0.001 cm. – we must differentiate between 6.688 cm and 6.689 cm long slots

• we want to keep the voltage low to reduce power consumption • voltage range of system is 0 - 5 volts, – 10 divisions would need 0.5 volt intervals. – 1000 divisions would make the interval 0.005 volts.

• For a general purpose computer – the accuracy we need can vary widely – simply dividing the data into steps is not enough

Digital Systems with Binary State Elements •

To get around the problem – fundamental elements of the system have only two states • • • •

•

there is a hole at a location on the punched card, or no hole a relay circuit is open or closed a vacuum tube is on or off a voltage is high or low

This separates the levels to the maximum extent feasible – each state can have a still have range • all holes may not be identical • voltage 0 – 0.4 V can be low and 2.4 – 5 V can be high.

•

An element has two states, so can represent only two data items – data is represented using a combination of elements – many representation schemes are possible

Examples of Data Representation • Using 10 elements to represent a decimal digit, 0 - 9 – 0 - 99 can be represented using 2 sets of 10 elements – 0 - 999 can be represented using 3 sets of 10 elements • remember zero requires an explicit representation

Examples of Data Representation • How would we represent text characters? – we do not want to add an extra element for each character – use more than one element of the set at a time • punched card including characters

Number of Elements Needed • Each element has two states – on or off, hole or no hole, voltage high or low – let us call one state 0 and the other 1 for convenience • positive logic uses high voltage as 1 • negative logic uses low voltage as 1

– Each element can be called a binary digit, or BIT

• One element can represent two characters 0 0 or 1  two possible data items 1

Number of Elements Needed • A two element group will have four distinct states

0

0

0

1

1

0

1

1

00, 01, 10, 11  four possible data items 0

1

2

3

A

b

$

d

Number of Elements Needed • n elements will have 2n different states

}

– each state can represent one character

n bits total

0 2

1 x

2

1 x 2

…

1

0

2

x 2

= 2n

ASCII Character Set •

The ASCII code uses 7 bits to represent data – can represent 128 characters – includes some control characters which are not printed • instruct the device to add a tab space, or begin a new line

– represents digits 0 – 9, A – Z, a – z, and special characters like !, $, @

•

An eighth bit is added for parity checking 1

0

0

1

1

0

1

1

Parity Bit here set to 1 to ensure sum is odd

•

Extended codes exist for other symbols, languages

Data Types •

Computers handle different types of data – – – – – –

numbers 1, 2, -153, 2.54 symbols +, -, (, ), / alphanumeric strings DfgF9_$5 sounds such as beeps and music files pictures and video physical data such as temperature, radiation levels

•

The ASCII scheme can represent alphanumeric strings

•

Representing numbers in the ASCII code is inefficient – each digit uses 8 elements

•

We will soon see how to represent numbers

•

Can other analog data be digitized and represented as numbers?

Digitization of Data •

Variables can vary continuously over space and time – temperature distribution in a body at one instant of time – temperature at a point in the body versus time

• •

We take samples at certain intervals of time and space How often do we need to sample the data? – depends on the accuracy we need

Digitization of Data • Fourier Theorem – a function can be treated as a superposition of simple waves • the waves have different frequencies • it is possible an infinite number of waves may be needed • using fewer waves leads to inaccuracy in recreating the function

Digitization of Data • Nyquist-Shannon Theorem – to fully recreate the data up to some frequency f, • you need to sample the function at 2f

Digitization of Data •

A picture can be divided into small regions – each region represented, say, by the intensity of primary colors – the smaller the divisions, the better the digitized image – pixilation works because human eyes have finite resolution • bitmaps are based on such an approach • compression techniques give other file types

•

We can sample the amplitude of sound waves at discrete intervals – we are sensitive to a limited frequency range of sound waves • 20 – 20,000 Hz, phone companies can use smaller range, up to 3000 Hz

•

We can create a video from pictures at discrete time intervals – persistence of vision creates a video from stationary pictures

•

Characters can be stored as numbers using the ASCII table

•

All types of data can be stored as numbers – the binary system provides the most efficient way to store numbers

Number Systems • The number system we use is the decimal system – based on 10 digits, 0 – 9

• It is a positional system – the value of a digit depends on its position – when we write the number 4256 • • • •

the digit 4 denotes 4000 the 2 denotes 200 the 5 is 50 the digit 6 is 6 itself.

The Roman System •

The positional system is in contrast to the Roman system – certain numbers are assigned letter symbols • I denotes 1, V = 5, X = 10, L = 50, C = 100, D = 500. M = 1000

– numbers without symbols are created by combining the symbols • II = 2, XV = 15, XVI = 16

– a smaller number to the left can be subtracted from that on the right • IV = V – I = 4, IX = X – I = 9, XC = 90 • this is done to shorten the representation

– very large numbers, greater than 4000 • can be written with a bar above the symbol to denote 1000 times

V = 5000 – there is no easy way to add, subtract, multiply or divide • What is MDIX – XVII • What is MCMD times XVIII

Advantages of Positional System •

The positional system allows for ease of operations Carry First no. Second no. Sum

1

1 5 3 2 9 9 6 5 4 --------------14 9 8 3

– similar techniques are used for other operations – note that • if we use a finite number of digits, say 4 and do not use negative integers – the maximum number we can represent is 9999 – adding two numbers may lead to overflow – multiplying numbers can also lead to overflow

• subtraction can still lead to negative numbers • division can lead to fractional numbers – the number may not terminate after the decimal point – 1/3 = 0.333333 ....

•

It also necessitates a symbol for zero – so as to write 205 or 250 • in Roman system these would be CCV and CCL

Positional Values and Digits •

For the decimal system – each position has a value ten times the one to its right • 4256 = 4 x 1000 + 2 x 100 + 5 x 10 +6 x 1

– using the exponentiation notation • 4256 = 4 x 103 + 2 x 102 + 5 x 101 + 6 x 100

– we only need digits 0 to 9 • 10 = 1 x 10 + 0 = 10

Numbers with Fractional Parts •

The general form of a decimal number

The Binary Number System •

The number system suited to computers is the binary system

•

The interpretation of positional value is based on powers of 2 – unlike base 10 in the decimal system

•

The system uses only 2 digits, 0 and 1 – the number 2 is written as 1 shifted one position to the left, i.e. 10 – in the decimal system, • digits are 0 – 9 • 10 is written as 1 shifted one position left

•

A binary number can be interpreted as, for example 1011001 = 1 x 26 + 0 x 25 + 1 x 24 + 1 x 23 +0 x 22 +0 x 21 +1 x 20 = 64 + 0 + 16 + 8 + 0 + 0 + 1 = 89

•

The kth position after the binary point corresponds to 2-k

Converting Decimal Integers to Binary

Converting Decimal Fractions to Binary •

To convert a decimal fraction, say 0.625 to binary

•

Multiply the fraction by 2 – the whole number part is the first binary digit after the point 0.625 x 2 = 1.25,

•

binary is 0.1 ...

Disregard the whole number part and multiply the new fraction by 2 – the new whole number part is the second binary digit after the point .25 x 2 = 0.50,

•

binary is 0.10 ...

Continue the process till fraction is zero or repeating pattern results 0.5 x 2 = 1.0 0.625 (decimal) = 0.101 (binary)

Converting Decimal Fractions to Binary •

Sometimes a fraction may not terminate – this may also happen after conversion to binary • the decimal fraction 0.1 0.1 x 2 = 0.2;

first binary digit after the binary point is 0

0.2 x 2 = 0.4; 0.4 x 2 = 0.8; 0.8 x 2 = 1.6; 0.6 x 2 = 1.2; 0.2 x 2 = 0.4

second binary digit after point is 0 third binary digit after point is 0 fourth binary digit after point is 1 fifth binary digit after pint is 1 ... the pattern will repeat from the second step on

0.1 (decimal) = 0.00011001100110011 ...

•

We will have a truncation error due to finite digit arithmetic

Binary Addition •

The binary system is also a positional system – binary addition can be carried out similar to decimal addition – for any position, there are four possibilities for the two digits

– the issue of carry over still exists

Binary Multiplication • Binary multiplication is simpler than decimal

1011 x 1101 ------1011 0000 1011 1011 -----------10001111 • Need double length result

Multiplicand (11 dec) Multiplier

(13 dec)

Partial products

Product (143 dec)

Binary Division

00001101 Divisor 1011 10010011 1011 001110 Partial 1011 Remainders 001111 1011 100

Quotient Dividend

Remainder

Computer Representation •

Computers use binary format to store numbers – based on 0 and 1, like the binary states of elements – each element represents one binary digit, called BIT – earlier representations included binary coded decimals

•

Non-negative integers can be represented directly

•

Special formats are used for – negative integers – numbers with fractional parts

Negative Integers •

More than one method can be used to represent negative integers

•

Sign Magnitude – the leftmost bit can be treated as the sign bit • 0 for positive, 1 for negative

– if we are using 1 byte to represent an integer • +18 = 00010010 • -18 = 10010010

•

If we used 8 bits for non-negative integers – we could express 28 = 256 numbers, i.e. integers 0 to 255

•

Using sign and magnitude notation, half the numbers have negative sign – we can represent +0 to +127 positive, and -0 to -127 negative integers

•

Problems with sign magnitude – need to consider both sign and magnitude in arithmetic – subtraction needs a separate circuit – two representations of zero, +0 = 00000000 and -0 = 10000000

Negative Integers •

Two's complement – take the binary form of the positive number – invert the digits so that 0's become 1's and 1's become 0's – add 1 to the resulting number

•

To write -28 28 = 00011100 if we use 1 byte to represent integers inverting the digits gives 11100011 adding 1 gives 11100100 -28 = 11100100

•

Note that applying the procedure to 0 to get -0 gives 00000000  11111111  100000000 – the carry bit is discarded since we are using only 1 byte so -0 = 00000000 = +0

Negative Integers •

Another advantage of the two's complement method is – take two numbers, say 8 and 4 8 – 4 = 8 + (-4) – Using 2's complement notation +8 = 00001000 -4 = -(00000100) = (11111011 + 1) = 11111100 8 + (-4) = 100000100 but we only use 1 byte, or 8 bits so 8 + (-4) = 00000100 = 4

•

To subtract a number from another – – – –

convert the number to its two's complement form add easy to design a circuit for complementation no need for a separate circuit for subtraction

Negative Integers •

Examples of two's complement for 8 bits +3 = 00000011 +2 = 00000010 +1 = 00000001 +0 = 00000000 -1 = 11111111 -2 = 11111110 -3 = 11111101

Negative Integers •

Unlike sign-magnitude, we have only one value of zero – it leaves one number free, beyond 0 ... 127 and -1 ... -127

•

-128 is 10000000

•

If we try to negate it, -(-128), we get 10000000  01111111 + 1  10000000

•

The system is asymmetric as it represents -128 to +127

Negative Integers •

To convert between different word sizes – Positive number pack with leading zeros • •

+18 = 00010010 +18 = 00000000 00010010

– Negative numbers pack with leading ones • •

-18 = 10010010 -18 = 11111111 10010010

– i.e. pack with MSB (sign bit)

Negative Integers •

Another format to store negative numbers is excess 2m-1

•

In this method, for 8 bits, numbers -128 to +127 are shifted by 28-1 = 27 = 128

•

-128 maps to 0

•

127 maps to 255

•

So numbers are stored as 0 – 255, as for 8 bit positive integers

•

Same as two's complement with leftmost or sign bit reversed

Negative Integers •

Negative numbers in four formats

Negative Integers •

Negative numbers in four formats

Numbers with Fractional Parts •

Numbers can be in a variety of ranges 0.000000000000015, or 150000000000000

•

Cannot represent using a fixed number of places after decimal

•

Use scientific notation – –

•

f is the significant or mantissa e is the exponent (a positive or negative integer)

Examples – – – –

•

n = f × 10e

300.1 = 3.001 x 102 0.0011 = 1.1 x 10-3 1.5 x 10-23 1.5 x 1035

This is called floating point representation –

The decimal point is floated so that the number can be expressed in this format

Numbers with Fractional Parts •

We can do the same thing for binary numbers

•

The power has to be powers of two

•

n = f × 2e – f is the significand or mantissa – e is the exponent (a positive or negative integer) in biased format •

•

easier to compare exponents during operations

Since the only digits are 0 and 1, the first digit of f is always 1 – The first digit is implicit – Allows bits to be used for more places after the decimal – Format cannot be used to represent 0 directly

32-bit Floating Point Representation

• +/- .significand x 2exponent • Special patterns for 0, infinity, NaN • Double precision uses 64 bits.

32-bit Floating Point Representation

Floating Point Ranges •

For a 32 bit number – 8 bit exponent – 2256 ≈ 1.15 x 1077 different exponent values

•

Accuracy – The effect of changing least significant bit of mantissa – 23 bit mantissa 2-23 ≈ 1.2 x 10-7 – About 6 decimal places

•

Note that if we were to use all 32 bits to express integers, we would express 2256 different integers.

•

Using 32 bits for floating point still represents the same number of unique numbers, but the numbers are spread out over a different range than the integers.

Floating Point Ranges

Floating Point Arithmetic •

Significand can have underflow or overflow – –

overflow occurs when you exceed the maximum positive or minimum negative limit Underflow occurs when the magnitude is less than the smallest possible magnitude

•

Exponent can also have overflow

•

Addition and subtraction are complicated –

decimal or rather binary point needs to be aligned •

–

significands can then be added or subtracted •

–

•

exponents need to be made equal in case of overflow, exponent needs to be adjusted

result is normalized and rounded off

Multiplication and division are somewhat easier –

exponents are dealt with separately • •

– –

multiplication involves summation of exponents division involves subtraction of exponents

significands are treated as integers result is normalized and rounded off as needed

Double Precision

Digital Circuits •

A computer consists of circuits made up of digital gates

•

A gate is a device that – has some inputs – produces an output depending on the inputs

•

Some basic types of gates are – NOT – AND – OR

•

Gates such as NAND and NOR can be derived from these

•

All circuits can be designed using NAND or NOR gates

•

These gates can be constructed simply using transistors

Gates •

A NOT gate is one that inverts its input, A, to output X = A

Gates •

An AND gate takes two inputs, A and B, and outputs AB – output is 1 only if both inputs are 1, zero otherwise

Gates •

An OR gate takes two inputs, A and B and outputs A+B – output is 0 only if both inputs are 0, 1 otherwise

Gates •

A NAND gate is a NOT gate following an AND gate

Gates •

A NOR gate is a NOT gate following an OR gate

Construction of Gates

(a) A transistor inverter. (b) A NAND gate. (c) A NOR gate.

Construction of NOT Gate

Construction of AND Gate

Construction of OR Gate

Example: Majority Function

Example: Multiplexer

Eight-input multiplexer • parallel to serial conversion

Example: Decoder

Three to eight decoder • address memory chips

Example: EOR Gate

Example: EOR Comparator

A 4-bit comparator

Example: One BIT Half Adder

Example: One BIT Full Adder

Example: One BIT ALU

Example: 8-BIT ALU

Equivalence of Circuits

Boolean Logic •

Need formal tools for design and analysis of circuits – to minimize the number of gates – to minimize the layers so as to get the fastest circuit • each gate introduces some delay

•

The logic followed by circuits is called Boolean logic

•

Each variable can have two values, 0 or 1

•

Basic functions include AND, OR, NOT

•

Expressions can be of the form X = AB + AC + B(A+C) + C

•

There is no subtraction or division

Boolean Logic

Some identities of Boolean algebra.

Principle of Duality • Any expression that is true is also true if – AND is replaced by OR, or vice-versa – and 1 is replaced by 0, or vice-versa – X=X+X – 1=X+1 – X = X(X+Y)

X = X.X 0 = X.0 X = X +X.Y

De Morgan's Law

Alternative symbols for some gates: (a) NAND, (b) NOR, (c) AND, (d) OR

Creating Expressions from Truth Tables • Write down the inputs for any case where output is 1 – – – –

X = 0, Y = 1, Z = 0 X = 0, Y = 1, Z = 1 X = 1, Y = 0, Z = 1 X = 1, Y = 1, Z = 1

• Write the product of inputs, inverting those that are zero – using ~X for NOT X instead of the overbar, for convenience • • • •

(~X)Y(~Z) (~X)YZ X(~Y)Z XYZ

• Function is sum of the product terms • (~X)Y(~Z)+(~X)YZ + X(~Y)Z + XYZ