Homework 2

22C:122/55:132, Spring 2001

Due Friday Jan 26, 2001, in class

1. Background: Skim Chapter 4 of the classic text, by Bell and Newell Computer Structures. This chapter is a reprint of the 1946 paper by Berks, Goldstein and Von Neumann that launched the computer age. This paper is in many ways very quaint, but in other ways, very little has changed.

   Problems? None this week! Be prepared to answer some next week!

2. Background: Consider the problem of adding two 2-bit binary numbers, producing a 3-bit sum.

   Part A: Give the complete truth table for this function, without optimization.

   Part B: Indicate the number of input not gates, row nand gates and output nand gates required to implement this function, without optimization.

   Part C: To what extent will the combinational optimization rules given in lecture 2 reduce the gate count?

3. 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.

   Part B: Give a state table (Moore) for the wall following control unit.

   Part C: Give a state table (Mealy) for the wall following control unit.