WASE BITS-WIPRO SESSION 3 DT:28-01-07

VENUE : WIPRO HYDERABAD
AUDIENCE : BITS-WASE 2006 BATCH
RESOURCES : PATTPATEL PPTs AND MORRIS MANO TEXT

Chapter 3Digital LogicStructures
Transistor: Building Block of Computers
Microprocessors contain millions of transistors
• Intel Pentium 4 (2000): 48 million
• IBM PowerPC 750FX (2002): 38 million
• IBM/Apple PowerPC G5 (2003): 58 million

Logically, each transistor acts as a switch
Combined to implement logic functions
• AND, OR, NOT
Combined to build higher-level structures
• Adder, multiplexer, decoder, register, …
Combined to build processor
• LC-3
Digital circuits
Constructed with ICs
IC is a small semiconductor crystal called chip containing gates
Depending on the number of gates we call them SSI,MSI,LSI,VLSI
SSI-10 GATES
MSI-200 GATES e.g. DECODERS,ADDERS,REGISTERS
LSI-1000s OF GATES e.g. PROCESSORS,MEMORY
VLSI- MANY 1000s MEMORY ARRAYS, COMPLEX CHIPS

DIGITAL INTEGRATED CIRCUITS
THE circuit technology/ digital logic family have their own basic electronic circuit upon which more complex digital circuits and functions are developed.
The basic circuit in each technology is either a NAND, a NOR or an inverter gate.
Logic Families
TTL/DTL- SUPPLY IS 5VOLTS, TWO STATES ARE 0,3.5V
ECL-SUPER COMPUTERS, DELAY IN NANOSECS
MOS- UNIPOLAR TRANSISTOR ONLY ONE CARRIER i.e. ELECTRONS(N-CHANNEL) OR HOLES(P-CHANNEL) CALLED AS PMOS AND NMOS
CMOS-PMOS+NMOS IN COMPLEMENTARY FASHION
Decoder
Combination circuit that converts binary information from n inputs to 2n unique outputs
N x m decoder means n inputs and m outputs where m<=2n
3 x 8 decoder can be used for binary to octal conversion

Commercial decoders have enable input E . If E=1 the decoder operates in normal fashion and if E=0 then the outputs are equal to zero

Decoder Expansion:- A 6-to-64 decoder can be constructed using four 4-to-16 decoders
Multiplexer

Combinational circuit that receives binary information from one of 2n input data lines and directs it to a single output line

The selection of a particular input data line for the output is determined by a set of selection inputs.

May have enable input E


Registers
A register consists of group of flip-flops and gates that effect their transition.
Flip-flops are capable of storing one bit of information.
Gates control when and how new information is transformed in to the register.
The transfer of new information into a register is referred to as loading the register.
Memory
A memory unit is a collection of storage cells together with associated circuits needed to transfer information in and out of storage. The memory stores binary information in groups of bits called words. A word in memory is an entity that moves in and out of storage as a unit.

Conventional memory – 1M = 220=20 address lines
= 640k + 384k uma. Addresses are from A0000 to FFFFF

Memories are RAM and ROM
RAM has two operations read and write, data input output lines, address lines, control lines
Memories
The internal structure of a memory unit is specified by the
number of words it contains and the number of bits in
each word. Special input lines called address lines select
one particular word. Each word has one unique address.

A decoder accepts this address and opens the path
needed to select the bits of the specified word.
Logic Gates
The manipulation of binary information is done by logic circuits called gates.

Gates are blocks of hardware that produce signals of binary 1 or 0 when input logic requirements are satisfied.

Each gate has a distinct graphic symbol and its operation can be described by an algebraic expression.

The input-output relationship of the binary variables for each gate can be represented in tabular form by a truth table.

Combinational Circuits
It is a connected arrangement of logic gates with a set of inputs and outputs.

The binary values of the output are a function of the binary combination of the inputs.

It transforms binary information from the given input data to the required output data.

Examples of combinational circuits are Half-Adder and Full-Adder which are arithmetic circuits
Full Adder
It is a combinational circuit that forms the arithmetic sum of three input bits.
It consists of three inputs and two outputs.

When all the input bits are 0, the output is 0.

S is equal to 1 when only one input is equal to 1 or when all three inputs are equal to 1.

C output has a carry of 1 if two or three inputs are equal to 1.
Half Adder
A combination circuit that performs the arithmetic addition of two bits is called a half-adder.

The input variables of a half adder are are called the augend and addend bits. The output variables the sum and carry.

It consists of an exor gate and an and gate.
Sequential circuit
They are storage elements which require that the system be described in terms of sequential circuits.
The most common type of sequential circuit is the synchronous type.
Synchronous sequential circuits employ signals that affect the storage elements only at discrete instant of time.
Synchronization is achieved by a timing device called a clock pulse generator that produces a periodic train of clock pulses.
Storage elements employed in clock sequential circuits are Flip-Flops.

Flip-Flop
It is binary cell capable of storing one bit of information.
It has two outputs, one for the normal value and one for the complementary value of the bits stored in it.
A flip-flop maintains a binary state until directed by a clock pulse to switch states.
The difference among various types of flip-flops is in the number of inputs they possess and in the manner in which the inputs affects the binary state.
The most common types of flip-flops are SR, D, JK, T, Edge-triggered
Simple Switch Circuit
Switch open:
• No current through circuit
• Light is off
• Vout is +2.9V

Switch closed:
• Short circuit across switch
• Current flows
• Light is on
• Vout is 0V
n-type MOS Transistor
MOS = Metal Oxide Semiconductor
• two types: n-type and p-type
n-type
• when Gate has positive voltage,short circuit between #1 and #2(switch closed)
• when Gate has zero voltage,open circuit between #1 and #2(switch open)
p-type MOS Transistor
p-type is complementary to n-type
• when Gate has positive voltage,open circuit between #1 and #2(switch open)
• when Gate has zero voltage,short circuit between #1 and #2(switch closed)
Logic Gates
Use switch behavior of MOS transistorsto implement logical functions: AND, OR, NOT.

Digital symbols:
• recall that we assign a range of analog voltages to eachdigital (logic) symbol





• assignment of voltage ranges depends on electrical properties of transistors being used
Ø typical values for "1": +5V, +3.3V, +2.9V
Ø from now on we'll use +2.9V
CMOS Circuit
Complementary MOS
Uses both n-type and p-type MOS transistors
• p-type
Ø Attached to + voltage
Ø Pulls output voltage UP when input is zero
• n-type
Ø Attached to GND
Ø Pulls output voltage DOWN when input is one

For all inputs, make sure that output is either connected to GND or to +,but not both!
Inverter (NOT Gate)
NOR Gate
OR Gate
NAND Gate (AND-NOT)
AND Gate
Basic Logic Gates
DeMorgan's Law
Converting AND to OR (with some help from NOT)
Consider the following gate:
More than 2 Inputs?
AND/OR can take any number of inputs.
• AND = 1 if all inputs are 1.
• OR = 1 if any input is 1.
• Similar for NAND/NOR.

Can implement with multiple two-input gates,or with single CMOS circuit.
Summary
MOS transistors are used as switches to implementlogic functions.
• n-type: connect to GND, turn on (with 1) to pull down to 0
• p-type: connect to +2.9V, turn on (with 0) to pull up to 1

Basic gates: NOT, NOR, NAND
• Logic functions are usually expressed with AND, OR, and NOT

DeMorgan's Law
• Convert AND to OR (and vice versa) by inverting inputs and output
Building Functions from Logic Gates
Combinational Logic Circuit
• output depends only on the current inputs
• stateless
Sequential Logic Circuit
• output depends on the sequence of inputs (past and present)
• stores information (state) from past inputs

We'll first look at some useful combinational circuits,then show how to use sequential circuits to store information.
Decoder
n inputs, 2n outputs
• exactly one output is 1 for each possible input pattern
Multiplexer (MUX)
n-bit selector and 2n inputs, one output
• output equals one of the inputs, depending on selector
Full Adder
Add two bits and carry-in,produce one-bit sum and carry-out.
Four-bit Adder
Logical Completeness
Can implement ANY truth table with AND, OR, NOT.
Combinational vs. Sequential
Combinational Circuit
• always gives the same output for a given set of inputs
Ø ex: adder always generates sum and carry,regardless of previous inputs
Sequential Circuit
• stores information
• output depends on stored information (state) plus input
Ø so a given input might produce different outputs,depending on the stored information
• example: ticket counter
Ø advances when you push the button
Ø output depends on previous state
• useful for building “memory” elements and “state machines”
R-S Latch: Simple Storage Element
R is used to “reset” or “clear” the element – set it to zero.
S is used to “set” the element – set it to one.







If both R and S are one, out could be either zero or one.
• “quiescent” state -- holds its previous value
• note: if a is 1, b is 0, and vice versa
Clearing the R-S latch
Suppose we start with output = 1, then change R to zero.
Setting the R-S Latch
Suppose we start with output = 0, then change S to zero.
R-S Latch Summary
R = S = 1
• hold current value in latch
S = 0, R=1
• set value to 1
R = 0, S = 1
• set value to 0

R = S = 0
• both outputs equal one
• final state determined by electrical properties of gates
• Don’t do it!
Gated D-Latch
Two inputs: D (data) and WE (write enable)
• when WE = 1, latch is set to value of D
Ø S = NOT(D), R = D
• when WE = 0, latch holds previous value
Ø S = R = 1
Register
A register stores a multi-bit value.
• We use a collection of D-latches, all controlled by a common WE.
• When WE=1, n-bit value D is written to register.
Representing Multi-bit Values
Number bits from right (0) to left (n-1)
• just a convention -- could be left to right, but must be consistent
Use brackets to denote range:D[l:r] denotes bit l to bit r, from left to right






May also see A<14:9>, especially in hardware block diagrams.
Memory
Now that we know how to store bits,we can build a memory – a logical k × m array of stored bits.
22 x 3 Memory
More Memory Details
This is a not the way actual memory is implemented.
• fewer transistors, much more dense, relies on electrical properties
But the logical structure is very similar.
• address decoder
• word select line
• word write enable
Two basic kinds of RAM (Random Access Memory)
Static RAM (SRAM)
• fast, maintains data as long as power applied
Dynamic RAM (DRAM)
• slower but denser, bit storage decays – must be periodically refreshed
State Machine
Another type of sequential circuit
• Combines combinational logic with storage
• “Remembers” state, and changes output (and state) based on inputs and current state

Combinational vs. Sequential
Two types of “combination” locks
State
The state of a system is a snapshot ofall the relevant elements of the systemat the moment the snapshot is taken.
Examples:
• The state of a basketball game can be represented bythe scoreboard.
Ø Number of points, time remaining, possession, etc.
• The state of a tic-tac-toe game can be represented bythe placement of X’s and O’s on the board.
State of Sequential Lock
Our lock example has four different states,labelled A-D:A: The lock is not open, and no relevant operations have been performed.
B: The lock is not open, and the user has completed the R-13 operation.
C: The lock is not open, and the user has completed R-13, followed by L-22.
D: The lock is open.
State Diagram
Shows states and actions that cause a transition between states.
Finite State Machine
A description of a system with the following components:
• A finite number of states
• A finite number of external inputs
• A finite number of external outputs
• An explicit specification of all state transitions
• An explicit specification of what determines eachexternal output value

Often described by a state diagram.
• Inputs trigger state transitions.
• Outputs are associated with each state (or with each transition).
The Clock
Frequently, a clock circuit triggers transition fromone state to the next.





At the beginning of each clock cycle,state machine makes a transition,based on the current state and the external inputs.
• Not always required. In lock example, the input itself triggers a transition.
Implementing a Finite State Machine
Combinational logic
• Determine outputs and next state.
Storage elements
• Maintain state representation.
Storage: Master-Slave Flipflop
A pair of gated D-latches, to isolate next state from current state.
Storage
Each master-slave flipflop stores one state bit.

The number of storage elements (flipflops) neededis determined by the number of states(and the representation of each state).

Examples:
• Sequential lock
Ø Four states – two bits
• Basketball scoreboard
Ø 7 bits for each score, 5 bits for minutes, 6 bits for seconds,1 bit for possession arrow, 1 bit for half, …
Complete Example
A blinking traffic sign
• No lights on
• 1 & 2 on
• 1, 2, 3, & 4 on
• 1, 2, 3, 4, & 5 on
• (repeat as long as switchis turned on)
Traffic Sign State Diagram
Traffic Sign Truth Tables
Traffic Sign Logic
From Logic to Data Path
The data path of a computer is all the logic used toprocess information.
• See the data path of the LC-3 on next slide.

Combinational Logic
• Decoders -- convert instructions into control signals
• Multiplexers -- select inputs and outputs
• ALU (Arithmetic and Logic Unit) -- operations on data
Sequential Logic
• State machine -- coordinate control signals and data movement
• Registers and latches -- storage elements
LC-3 Data Path