Transcript Slides10_20 (L3

State Machines
Used to Design Sequential Circuits
Implementing a Finite State Machine
• Combinational logic
– Determine outputs at each state.
– Determine next state.
• Storage elements
– Maintain state representation.
State Machine
Inputs
Clock
Combinational
Logic Circuit
Storage
Elements
Outputs
Storage
• Each master-slave flipflop stores one state bit.
• The number of storage elements (flipflops) needed
is 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 digit, 5 bits for minutes, 6
bits for seconds,1 bit for possession arrow, 1 bit
for half, …
Complete Example – Traffic Sign
• Design a “blinking” traffic sign which exhibits this behavior:
State 1) No lights on
State 2) 1 & 2 on
State 3) 1, 2, 3, & 4 on
State 4) 1, 2, 3, 4, & 5 on
State 1) No lights on





.
.
( - Repeat as long as operate
switch is turned on.
- The system is in state 1 when
the operate switch is off)
3
4
1
5
2
DANGER
MOVE
RIGHT
Traffic Sign State Diagram
Switch off
State bit S1
State bit S0
State Transitions occur on each clock cycle.
Switch on
Outputs
Traffic Sign Truth Tables
Outputs
(depend only on state: S1S0)
Next State: S1’ S0’
(depend on state and input)
Switch
Lights 1 and 2
Lights 3 and 4
Light 5
S1
0
0
1
S0
0
1
0
Z
0
1
1
Y
0
0
1
X
0
0
0
1
1
1
1
1
In S1 S0 S1 S0
0
1
1
1
X
0
0
1
X
0
1
0
0
0
1
1
0
1
0
1
1
1
1
0
0
Whenever In=0, next state is 00.
Traffic Sign Combinational Logic
Master-slave, or
Edge Triggered
D flipflops
Chapters 4 & 5:
LC-3 Computer
• Architecture
• Machine Instructions
• Assembly language
• Programming in Machine and Assembly Language
Overview
The LC-3 Computer
16 bit machine, word addressable, 64K or 65,536 locations
Computer Machine Instructions – Computer “native” instructions
- The basic instructions that all programs use on that computer
(The “atomic” unit of work done by a computer – see next slide)
The Architecture
- The hardware (state machine) that executes the instructions (see slide)
The Memory
- Holds the Operating System, the Program, support routines, data, etc.
The Instruction Cycle
- The steps in the execution of a machine language instruction
(Fetch, Decode, Evaluate Address(es), Fetch operand(s), Execute,
and Store results)
LC-3 Instructions (Fig 5.3 – Appendix a)
Data Paths
of the LC-3
LC-3 Data Paths:
Combinational
Logic
Storage
State Machine
LC-3 Memory Layout
x0000 – x2FFF System: Operating System programs, tables,
and data - Generally off limits to programmer
(Programs run in Supervisor mode)
x3000 – xFDFF User: User Program and Data Area
Area shared by users like you
(Nominally run in non-supervisor mode)
xFE00 – xFFFF Device: I/O Register Addresses
Pseudo memory used for input/output
R0-R7
Registers (16 bit)
LC-3 Memory Map
Computer Machine Instruction Formats
What is IN an instruction?
• Operation code – what to do
• Input Operand(s) – where to get input operands (memory, registers)
• Output Operand(s) – Where to put results (memory, registers)
What are the major instruction types?
• Data Movement (load, store, etc.)
• Operate (add, sub, mult, OR, AND, etc.)
• Control (branch, jump to subroutine, etc.)
The Instruction Cycle
Steps (or phases):
• Fetch Next Instruction from Memory
(PC)  (points to) next instruction
PC (PC) + 1
• Decode Fetched Instruction
• Evaluate Address (es) (find where the data is)
• Fetch Operand (s) (get data)
• Execute Operation
• Store Result (if specified)
The LC-3 Instruction Addressing Modes
• Register
(Operand is in one of the 8 registers)
•
PC-relative
(Operand is “offset” from the (PC) )
•
Base + Offset (Base relative)
(Operand is “offset” from the contents of a register)
•
Immediate
(Operand is in the instruction)
•
Indirect
(The “Operand” actually points to the real address
– rather than being the operand)
The LC-3 Instruction Addressing Modes
• Register
(Operand is in one of the 8 registers)
• Immediate (Operand is in the instruction)
• PC-relative (Operand is “offset” from the (PC) )
• Indirect (The “Operand” actually points to the real address
– rather than being the operand)
• Base + Offset (Base relative) (Operand is “offset” from the
contents of a register)
Note: no Direct Addressing defined in the LC-3
LC-3 Instructions (Fig 5.3 – Appendix a)