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

What Is Project

What is Project
by Rajesh Kulkarni
http://rkstechnofusion.blogspot.com
http://children-off-lesser-gods.blogspot.com

Venue BIET
Audience : IV/IV CSE and IT students
ocassion: Two-Day Workshop "Technofusion 2007"
Date: 19-01-2007

FINAL YEAR PROJECTS



§ Working in a team
§ Going thru all the phases of project life cycle from requirement to deployment
§ Developing a piece of software which serves at least as a prototype
§ The developed software should be well documented and maintainable
Final year Project Setup
§ Schedules and deadlines are to be given by Teachers
§ Team selection and problem statement is to be given by students
§ Roles Customer: Internal Guide Initially fuzzy requirement specificationInteraction and negotiation with your customer/guide will lead to SRS which may be approved by your Team Lead/ Project coordinator and Project Manager/HODSRS Document review to be done by project manager/HOD/Committee
§ Coach: Technical problem solving, discussion on new topics, technologies(ensure audience,LCD/OHP,S/W)
§ Design the architecture: Use Case Document




§No money but good marks
§No software architect, all the job will be done by students hence it is not expected that they will be designing a perfect software architecture
§As the life cycle is small(three months) maintenance issues can not be touched
§The product is meant only as a prototype and not for productive use


New technologies can be explored, like
§ CVS (concurrent versions system) or documentum for version control
§ LaTeX/ msword for documentation
§ TogetherJ / Rational Rose as UML editor for modeling and code generation
§ Java libraries like JUnit for regression testing and a setup for daily build and smoke tests
§ XML libraries like JAXP and Log4J for logging mechanism
§ Framework/platform like eclipse

Lessons to be learned from final year project
§ Communication
§ Technical Issues
§ Non-technical issues like problem domain understanding, work division, deadlines, design focus, learning new technologies
§ Process Knowledge
§ Manage problems
§ Documentation
§ Team organisation

Happy Projects !!!!

WASE BITS-WIPRO SESSION 2 DT:21-01-07

venue wipro
audience : wase 2006 batch
Chapter 4The Von Neumann Model
The Stored Program Computer
1943: ENIAC
Presper Eckert and John Mauchly -- first general electronic computer.(or was it John V. Atanasoff in 1939?)
Hard-wired program -- settings of dials and switches.
1944: Beginnings of EDVAC
among other improvements, includes program stored in memory
1945: John von Neumann
wrote a report on the stored program concept, known as the First Draft of a Report on EDVAC
The basic structure proposed in the draft became knownas the "von Neumann machine" (or model).
a memory, containing instructions and data
a processing unit, for performing arithmetic and logical operations
a control unit, for interpreting instructions
Von Neumann Model
Memory
2k x m array of stored bits
Address
unique (k-bit) identifier of location
Contents
m-bit value stored in location
Basic Operations:
LOAD
read a value from a memory location
STORE
write a value to a memory location
Interface to Memory
How does processing unit get data to/from memory?
MAR: Memory Address Register
MDR: Memory Data Register
To LOAD a location (A):
Write the address (A) into the MAR.
Send a "read" signal to the memory.
Read the data from MDR.
To STORE a value (X) to a location (A):
Write the data (X) to the MDR.
Write the address (A) into the MAR.
Send a "write" signal to the memory.
Processing Unit
Functional Units
ALU = Arithmetic and Logic Unit
could have many functional units.some of them special-purpose(multiply, square root, …)
LC-3 performs ADD, AND, NOT
Registers
Small, temporary storage
Operands and results of functional units
LC-3 has eight registers (R0, …, R7), each 16 bits wide
Word Size
number of bits normally processed by ALU in one instruction
also width of registers
LC-3 is 16 bits
Input and Output
Devices for getting data into and out of computer memory
Each device has its own interface,usually a set of registers like thememory’s MAR and MDR
LC-3 supports keyboard (input) and monitor (output)
keyboard: data register (KBDR) and status register (KBSR)
monitor: data register (DDR) and status register (DSR)
Some devices provide both input and output
disk, network
Program that controls access to a device is usually called a driver.
Control Unit
Orchestrates execution of the program



Instruction Register (IR) contains the current instruction.
Program Counter (PC) contains the addressof the next instruction to be executed.
Control unit:
reads an instruction from memory
the instruction’s address is in the PC
interprets the instruction, generating signals that tell the other components what to do
an instruction may take many machine cycles to complete
Instruction Processing
Instruction
The instruction is the fundamental unit of work.
Specifies two things:
opcode: operation to be performed
operands: data/locations to be used for operation
An instruction is encoded as a sequence of bits. (Just like data!)
Often, but not always, instructions have a fixed length,such as 16 or 32 bits.
Control unit interprets instruction:generates sequence of control signals to carry out operation.
Operation is either executed completely, or not at all.
A computer’s instructions and their formats is known as itsInstruction Set Architecture (ISA).
Example: LC-3 ADD Instruction
LC-3 has 16-bit instructions.
Each instruction has a four-bit opcode, bits [15:12].
LC-3 has eight registers (R0-R7) for temporary storage.
Sources and destination of ADD are registers.
Example: LC-3 LDR Instruction
Load instruction -- reads data from memory
Base + offset mode:
add offset to base register -- result is memory address
load from memory address into destination register
Instruction Processing: FETCH
Load next instruction (at address stored in PC) from memoryinto Instruction Register (IR).
Copy contents of PC into MAR.
Send "read" signal to memory.
Copy contents of MDR into IR.
Then increment PC, so that it points to the next instruction in sequence.
PC becomes PC+1.
Instruction Processing: DECODE
First identify the opcode.
In LC-3, this is always the first four bits of instruction.
A 4-to-16 decoder asserts a control line correspondingto the desired opcode.
Depending on opcode, identify other operands from the remaining bits.
Example:
for LDR, last six bits is offset
for ADD, last three bits is source operand #2
Instruction Processing: EVALUATE ADDRESS
For instructions that require memory access,compute address used for access.
Examples:
add offset to base register (as in LDR)
add offset to PC
add offset to zero
Instruction Processing: FETCH OPERANDS
Obtain source operands needed to perform operation.
Examples:
load data from memory (LDR)
read data from register file (ADD)
Instruction Processing: EXECUTE
Perform the operation, using the source operands.
Examples:
send operands to ALU and assert ADD signal
do nothing (e.g., for loads and stores)
Instruction Processing: STORE RESULT
Write results to destination.(register or memory)
Examples:
result of ADD is placed in destination register
result of memory load is placed in destination register
for store instruction, data is stored to memory
write address to MAR, data to MDR
assert WRITE signal to memory
Changing the Sequence of Instructions
In the FETCH phase,we increment the Program Counter by 1.
What if we don’t want to always execute the instructionthat follows this one?
examples: loop, if-then, function call
Need special instructions that change the contents of the PC.
These are called control instructions.
jumps are unconditional -- they always change the PC
branches are conditional -- they change the PC only ifsome condition is true (e.g., the result of an ADD is zero)
Example: LC-3 JMP Instruction
Set the PC to the value contained in a register. This becomes the address of the next instruction to fetch.
Instruction Processing Summary
Instructions look just like data -- it’s all interpretation.
Three basic kinds of instructions:
computational instructions (ADD, AND, …)
data movement instructions (LD, ST, …)
control instructions (JMP, BRnz, …)
Six basic phases of instruction processing:
F ® D ® EA ® OP ® EX ® S
not all phases are needed by every instruction
phases may take variable number of machine cycles
Control Unit State Diagram
The control unit is a state machine. Here is part of asimplified state diagram for the LC-3:
Stopping the Clock
Control unit will repeat instruction processing sequenceas long as clock is running.
If not processing instructions from your application,then it is processing instructions from the Operating System (OS).
The OS is a special program that manages processorand other resources.
To stop the computer:
AND the clock generator signal with ZERO
When control unit stops seeing the CLOCK signal, it stops processing.