Traffic Light Behavior
IF A=1
AND B=0
A
B
Car
Sensors
Traffic Light Behavior
Otherwise
IF A=1
AND B=0
A
B
Car
Sensors
Traffic Light Behavior
Otherwise
IF A=1
AND B=0
Always
A
B
Car
Sensors
Traffic Light Behavior
Otherwise
IF A=1
AND B=0
Always
IF A=0
B
Car
Sensors
AND B=1
Otherwise
Traffic Light Behavior
Otherwise
IF A=1
AND B=0
Always
Always
IF A=0
B
Car
Sensors
AND B=1
Otherwise
Traffic Light Behavior
Otherwise
IF A=1
AND B=0
Always
Always
IF A=0
B
Car
Sensors
Note:
Clock beats
every 4 sec.
So Light is
Yellow for
4 sec.
AND B=1
Otherwise
Traffic Light State Machine
Otherwise
IF A=1
AND B=0
Always
Always
IF A=0
B
Car
Sensors
Note:
Clock beats
every 4 sec.
So Light is
Yellow for
4 sec.
AND B=1
Otherwise
Traffic Light Design
Weve figured out the logical behavior of
the Traffic Light in terms of a
State Machine:
We know what the states are.
For each state, given any input,
we know which state to go to next.
How do we build it?
Traffic Light Design
Thinking this through:
Our machine needs to:
Traffic Light Design
Thinking this through:
Our machine needs to:
Remember which state it is in (Memory)
Traffic Light Design
Thinking this through:
Our machine needs to:
Remember which state it is in (Memory)
Given the state it is in and input values,
it must determine which state to go to
next (Logic)
Traffic Light Design
Thinking this through:
Our machine needs to:
Remember which state it is in (Memory)
Given the state it is in and input values,
it must determine which state to go to
next (Logic)
And thats all !
Traffic Light Design
Problem 1:
Remember which state it is in (Memory)
How do represent the states?
We could keep one bit of memory for
whether Light A is Green or not,
whether it is Yellow or not,
This would take 6 bits of memory.
There is a much simpler way!
Traffic Light Design
Problem 1:
Remember which state it is in (Memory)
How do represent the states?
Answer:
Just number them (using binary numbers).
We have 4 states.
Call them 00, 01, 10, 11.
We (human designers) will keep track of
what these names mean.
Traffic Light States
Otherwise
IF A=1
Light A
AND B=0
Always
Always
IF A=0
AND B=1
Light B
Otherwise
Traffic Light States
Otherwise
Light A
00
IF A=1
AND B=0
Always
Always
11
01
IF A=0
AND B=1
Light B
10
Otherwise
Traffic Light Design
Problem 2:
Given the state it is in and input values,
it must determine which state to go to
next (Logic)
Answer:
Traffic Light Design
Problem 2:
Given the state it is in and input values,
it must determine which state to go to
next (Logic)
Answer:
Build a Truth Table
Use Universal Method!
Traffic Light Behavior
Build A Truth Table
for next state / Output
M1 M2 A B
D1 D2 Light A Red
Light B Red
Traffic Light Behavior
Otherwise
Light A
00
IF A=1
AND B=0
Always
Always
11
01
IF A=0
AND B=1
Light B
10
Otherwise
Traffic Light Behavior
Build A Truth Table
for next state / Output
M1 M2 A B
D1 D2 Light A Red
Light B Red
0 1
Traffic Light Behavior
Otherwise
Light A
00
IF A=1
AND B=0
Always
Always
11
01
IF A=0
AND B=1
Light B
10
Otherwise
Traffic Light Behavior
Build A Truth Table
for next state / Output
M1 M2 A B
D1 D2 Light A Red
Light B Red
0 1
* *
Traffic Light Behavior
Otherwise
Light A
00
IF A=1
AND B=0
Always
Always
11
01
IF A=0
AND B=1
Light B
10
Otherwise
Traffic Light Behavior
Build A Truth Table
for next state / Output
M1 M2 A B
D1 D2 Light A Red
Light B Red
0 1
* *
0 1
Traffic Light Behavior
Otherwise
Light A
00
IF A=1
AND B=0
Always
Always
11
01
IF A=0
AND B=1
Light B
10
Otherwise
Traffic Light Behavior
Build A Truth Table
for next state / Output
M1 M2 A B
D1 D2 Light A Red
Light B Red
0 1
* *
0 1
* *
0 0
Traffic Light Behavior
Otherwise
Light A
00
IF A=1
AND B=0
Always
Always
11
01
IF A=0
AND B=1
Light B
10
Otherwise
Traffic Light Behavior
Build A Truth Table
for next state / Output
M1 M2 A B
D1 D2 Light A Red
Light B Red
0 1
* *
0 1
* *
0 0
0 0
0 0
Traffic Light Design
We understand how to represent which
state the system is in (so we can store it in
Memory)
We understand how the system can
determine which state to go to next (Logic)
Lets put it together
Traffic Light Design
Input: Sensor A
Input: Sensor B
Traffic Light Design
D1
Current State
D2
Write
Sensor A
Sensor B
2-bit
Memory
Register
M1
M2
Traffic Light Design
Current State
Write
Sensor A
Sensor B
2-bit
Memory
Register
Logic
For
Next
State
&
Output
Next
State
6 Outputs:
for each
Light
Traffic Light Design
Current State
Write
Sensor A
Sensor B
2-bit
Memory
Register
Logic
For
Next
State
&
Output
6 Outputs:
for each
Light
Traffic Light Design
Current State
Clock
Sensor A
Sensor B
2-bit
Memory
Register
Logic
For
Next
State
&
Output
6 Outputs:
for each
Light
Design for Any State Machine
Many
bits
Current State
Clock
Inputs
Memory
Register
Logic
For
Next
State
&
Output
Outputs
State Machines
in Real Life
Elevator control systems
Car control systems
VCRs
Alarm Clocks
Personal Computers
Just about everything!
More Sophisticated Designs
Just add more states, more inputs, more
outputs, more rules
Example: Add a longer delay before Traffic
Light changes from Yellow to Red.
(Say 8 seconds instead of 4.)
Traffic Light Behavior
Otherwise
IF A=1
Light A
AND B=0
Always
Always
Always
Always
IF A=0
AND B=1
Light B
Otherwise
More Sophisticated Designs
Note that the new delay states we added
correspond to the SAME combinations of
lights as other states (Red/Yellow).
The purpose of the new states is only
to add delays.
Logical states need not correspond to
different observable states of the machine!
More Sophisticated Designs
Can also add other State Machines!
More Sophisticated Designs
Example (Fairness):
We might want a separate Timer machine
for the Traffic Light:
If cars keep coming, Light should decide
after 3 minutes to switch lights.
A Timer is just a state machine that keeps
counting beats of the Clock
More Sophisticated Designs
Inputs
Main State
Machine
Outputs
Timer
State
Machine
Computers!
State Machines that you can program
Review
In designing state machines, we used:
Binary Representation (to represent states)
Memory (to store the current state)
Logic Circuits & Universal Method
(to determine the next state)
In this way, we learned how to build
special-purpose digital systems
(e.g. traffic lights)
General Purpose Computers
What makes a PC different?
Today your PC cant play Final Fantasy X.
Tonight, you buy the Final Fantasy X CD-ROM
Tomorrow your PC can play the game!
PCs are general-purpose computers.
Realize state machines for traffic lights, digital
cameras, VCRs,
You can write a program (software) to control the
circuitry (hardware) of a general purpose computer
The Stored Program
Idea is simple:
Build a machine that can execute certain
instructions.
Then, write down different lists of
instructions (programs) to accomplish
different things.
One program plays an adventure game
Another program lets you write papers
Another lets you surf the Web
Programming
Using software to control hardware
Hardware is fixed circuitry
Software is instructions to the processor to
control the inputs to the fixed circuitry
Inputs to the hardware are of 2 types
Data
Program
We dont differentiate
Both are stored in computers memory
History of Programmable
Machines
First programmable
system was the early
printing process developed
in China circa 800 C.E.
First program was
perhaps Chinese
translation of
Buddhist Canon
(the Tipitaka)
History (cont.)
Gutenbergs Printing Press
(circa 1450)
Main Contribution:
Just a few basic
instructions (smaller
alphabet size) suffice.
History (cont.)
Huygens Pendulum
Clock
(circa 1650)
Main Contribution:
Timing, clock ticks
increase accuracy
History (cont.)
Musical Machines:
Barrel Organs (1500!)
Music boxes (between)
Player Pianos (c. 1700)
Main Contributions:
Drive cylinder or disk with
pins (bits!!) which play
notes at the right time
Change disk -> change song!!
History (cont.)
Jacquards Loom
(circa 1810)
Punched Cards
stored program
for weaving patterns.
History (cont.)
Charles Babbage (1822-64):
Input -- Punched Cards
Hardware -- general-purpose
mechanical mathematical
system
(Analytical Engine) -- never
built
Could be programmed
punched card could say:
Go back 5 punched cards
Instructions could be
Executed repeatedly, or in
different order.
The Modern Computer
von Neumann (1945)
Princeton, NJ
Basic Idea still the same:
A machine that can execute certain
instructions.
Machine instructions represented by
sequences of 0s and 1s
(Machine Language)
Instructions, and data, stored in Memory
Memory
Weve seen that memory can be used to build
State Machines.
In modern computers, memory is also used
in a different way:
Big arrays of Memory called
RAM : Random Access Memory
RAM is a place to store information while the
computer is running
The information includes the data that the
program reads and writes, as well as the
program itself (I.e. its instructions)
Programs are Just Like Data
One of the important features of the von
Neumann model is the fact that:
The instructions themselves
And
The data the instructions manipulate
are all stored in the same RAM.
This was one of the revolutionary features of
the modern computer, totally unlike Punch-Card
computers proposed in the past.
Programs are Just Like Data
This innovation is crucial to modern computing.
It even allows for the possibility of programs
that change themselves as they are executed.
With great power comes great risk
Computer Viruses!
How Memory (RAM) Works
Take a single bit of memory
D
M
Write
RAM (cont.)
Group 8 of them together.
D
8 bits (b)
is called a
byte (B).
Most RAM
is arranged
in bytes.
W
D
W
D
W
D
W
D
W
D
W
D
W
D
W
RAM (cont.)
A byte of memory (a.k.a. an 8-bit register)
8 bits input
Write
8 bits Output
8 bits
(1 byte)
of Memory
RAM (cont.)
We want a HUGE number of such 1 byte
memory cells.
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
RAM (cont.)
We want a HUGE number of such 1 byte
memory cells.
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
1B
Problem: How do we indicate which byte of
memory we want to use at any given time?
RAM (cont.)
Solution: Assign each byte an address.
We can number all the bytes in binary.
Each bytes assigned number is called
the bytes address in memory.
Then, we can ask the RAM:
What is byte number 011010101010?
Or tell the RAM:
Write 01101100 into memory at address
011010101010
RAM (cont.)
Address
Data input
Write
20
bytes of
RAM
(1 Mega-byte)
Data Output
RAM (cont.)
20 bits of
address
Address
Data input
Write
20
bytes of
RAM
(1 Mega-byte)
Data Output
RAM (cont.)
20 bits of
address
Address
Data input
Write
20
bytes of
RAM
(1 Mega-byte)
8 bits (1 byte)
of data
Data Output
