A1 A0 B1 B0 | S2 S1 S0 --------------+---------- 0 0 0 0 | 0 0 0 0 0 0 1 | 0 0 1 0 0 1 0 | 0 1 0 0 0 1 1 | 0 1 1 0 1 0 0 | 0 0 1 0 1 0 1 | 0 1 0 0 1 1 0 | 0 1 1 0 1 1 1 | 1 0 0 1 0 0 0 | 0 1 0 1 0 0 1 | 0 1 1 1 0 1 0 | 1 0 0 1 0 1 1 | 1 0 1 1 1 0 0 | 0 1 1 1 1 0 1 | 1 0 0 1 1 1 0 | 1 0 1 1 1 1 1 | 1 1 0
Part B: Indicate the number of gates required to implement this function, without optimization.
input not gates: 4
row nand gates: 16
output nand gates 3
Part C: To what extent will the combinational optimization rules given in lecture 2 reduce the gate count?
One row of the table has no ones on the output, so only 15 rows need to be decoded. None of the truth table rows that have the same outputs differ from each other in just one input, so none of the rows can be combined.
- Background: Consider the problem of building a robot that follows the walls of a rectilinear maze. In any time unit, this robot may either move forward (0) or rotate right (1), and it may elect to continue moving (0) or stop (1) (outputs). The robot can sense the absence (0) or presence (1) of a wall directly in front of it (inputs), and it may detect the absence (0) or presence (1) of a coin in the square of the maze it currently occupies.
The goal is to create a finite state control unit that directs the robot to move forward until it finds a wall, and then to follow that wall until it finds a coin.
Part A: Describe, using some notation at a higher level than state tables and finite state machines, the algorithm your robot will follow.
while no wall sensed and no coin found move forward -- initial endloop while no coin sensed if wall sensed -- rotate right in 3 steps. rotate left -- wall rotate left -- wall1 rotate left -- wall2 else move forward -- air rotate left -- air1 endif endloop done -- haltPart B: Give a state table (Moore) for the wall following control unit.state wall coin | next state state | move/turn stop -------------------+------------ -------+---------------- initial 0 0 | initial initial| 0 0 initial 0 1 | halt halt | 1 1 initial 1 0 | wall wall | 1 0 initial 1 1 | halt wall1 | 1 0 | wall2 | 1 0 halt x x | halt air | 0 0 | air1 | 1 0 wall x x | wall1 wall1 x x | wall2 wall2 0 x | air wall2 1 x | wall | air x 0 | air1 air x 1 | halt | air1 0 x | air air1 1 x | wallPart C: Give a state table (Mealy) for the wall following control unit.
state wall coin | next state move/turn stop -------------------+---------------------------- initial 0 0 | initial 0 0 initial 0 1 | halt 1 1 initial 1 0 | wall 1 0 initial 1 1 | halt 1 0 | halt x x | halt 1 1 | wall x x | wall1 1 0 wall1 x x | wall2 1 0 wall2 0 x | air 0 0 wall2 1 x | wall 1 0 | air 0 0 | air1 1 0 air 0 1 | halt 1 1 | air1 0 x | air 0 0 air1 1 x | wall 1 0