SIMS 255: Assignment 1

Practice with Logic Gates

(1-3) Do problems 1-3 from Chapter 1 of Brookshear.

(4) Use deMorgan's law to figure out how to convert the following circuit so that it does not use any AND gates, but computes the same outputs for the given inputs. Show the resulting circuit and show how you used deMorgan's law.



Practice with Binary and Binary Arithmetic

1. How many unique binary numbers can be represented by 16 bits?
2. Convert the following decimal numbers to binary:
   • 23
   • 1024
   • 2046
3. Convert the following binary numbers to decimal:
   • 010010
   • 110011
4. Add the following pairs of binary numbers (write results in binary):
   • 01010 + 10101
   • 10001 + 01111

Practice with Boolean Logic

Consider the Venn diagram below. Note that the areas of D, E, and F are all supposed to include the area of G. Note also that H is supposed to mean only the area in gray. Finally, C' (not labeled on the diagram) is the area within C that does not include any of A or B.


Part A:

Express the areas labeled by D, E, F, G, H, and C' in terms of Boolean logic, using the notation of Intersection, Union, and Not (represented as a bar over the terms). Express C' in two different ways, but using Boolean logic in both cases. (Keep in mind that C' (not labeled on the diagram) is the area within C that does not include any of A or B.)

Part B:

Show each of these Boolean expressions using logic gates.

Part C:

If you ever watched the old TV game show "Let's Make a Deal" (ok, I'm showing my age), then you know that contestants have a chance to win a grand prize at the end of the show. Three doors are shown; behind one is a great prize like a vacation to Rome or a new Mercedes; behind another is a mildly good prize like a side-by-side refrigerator, and behind another door is a joke prize like a donkey.

Monty Hall, the host of the show would ask contestants: "Do you choose Door Number 1, Door Number 2, OR Door Number 3?"

How, in a general sense, do the results of this game show choice differ from the search results returned by a web search engine for this query: "bicycle" OR "car" OR "truck"?

(You don't need to have ever seen the TV show to determine the answer.)

The Painting Machine

Goals

The goal of this question is to give you a very deep understanding of the relationship between assembly language, machine instructions, and how they can be used to control a machine. You will also get more insight about the notion of code and data having the same representation, and some practice with designing a small circuit using logic gates.

The ideas needed here are similar to, but not identical to, what we've seen in class about how gates work, how instruction sets work, how a CPU-like machine works, and how to code things in binary.

I'm asking you to do this problem on your own. If you talk to other people, they might tell you too much and prevent you from getting all the insights you will get if you make the discoveries yourself. If you need a hint, send email to the TAs or to me.

This is supposed to be FUN, by the way.

Problem Statement

Imagine that some of the other MIMS students developed a great new machine that can produce computer-controlled paintings. The paint is mixed from the three primary colors (red, blue, and yellow), poured through a funnel, and placed, pixel by pixel, onto paper that is positioned underneath the funnel by moving along rollers. (See the figure.)



These students didn't take IS255, so they need your help in making the hardware and instruction set for controlling their painting machine.

They've set things up so there are wires that control the valves on the three paint dispensers (called A, B, and C). When a valve recieves a value of 1, it snaps open enough for one blob of paint to flow out of the dispenser and into the funnel, and then snaps shut, all within one clock cycle.

There is another wire (called D) that controls the opening on the funnel. When it receives a 1 it snaps open long enough to paint the spot just underneath it with a perfect pixel of color, and then snaps shut. When the funnel valve opens, it uses up all of the paint in the funnel, leaving the insides of the funnel clean. (This is a special kind of paint that slips off of metal but sticks to paper.)

The hardware is set up so the rollers can either go forwards-backwards or left-right; they can't move in both directions simultaneously.

The wire called E controls the forwards-backwards movement of the paper on the appropriate rollers. When it receives a 1 it moves the paper forwards or backwards one pixel. The wire called F controls the left-right movement of the paper. When it receives a 1 it moves the paper one pixel left or right.

Finally, the wire called G is used to indicate the direction for the roller. When set to 1, if E is also set to 1, it tells the roller to go forwards. If G is set to 0 when E is set to 1, the it tells the roller to go one unit backwards. Similarly, when G is set to 1 and F is set to 1, it means go one unit left, otherwise one unit right.

The assembly language consists of the following 14 operations:

mix red
mix yellow
mix blue
mix purple
mix green
mix orange
mix black
mix white
paint
move left
move right
move forwards
move backwards
halt


Mix means dispense paint into the funnel, where it will mix itself.

Paint means snap open the valve on the bottom of the funnel, so it will paint the pixel on the piece of paper that is currently under the funnel.

Move means move the paper one pixel either left-right or forward-backward.

Part A: Write a Program for the Machine

To get a feeling for the assembly language, first write a program that paints the three center rows of the painting shown below, using the assembly language instructions shown above. Assume the program starts with the funnel over the center pixel in the center row.


Part B: Design the Instruction Set

To enable the students to be able to run their machine, you need to design an instruction set that can implement the assembly language shown above. To save money, the students need you to restrict your instruction set to consist of instructions of length 5 bits. You also have to design some circuitry that will convert the machine code instructions into actions that run the machine. You have to have one machine code instruction for each and every one of the assembly language instructions shown above.

The system works as follows. (See the expanded figure below.)



The major components are connected to the clock, as shown in the figure.

The instructions get loaded into RAM, starting at memory address 0. The RAM is quite large, so you don't need to worry about running out of space.

The program counter starts at memory address 0. Each instruction takes four clock cycles to execute. In the first cycle, the contents of the memory location that is pointed to by the Program Counter are read into the Instruction Register. In the second cycle, the contents of the Instruction Register go through the circuit (denoted as ? in the figure) whose output is connected to wires A - G. In the third cycle, all the mechanical parts of the machine are activated and have time to do their work, thus responding to the values on A - G (they are deactivated at the end of the cycle). In the fourth cycle, the Program Counter is incremented.

So first design the binary representation of the instruction set shown above. Remember, instructions can only be 5 bits long. You should make a table that shows each instruction next to its assembly language representation.

Part C: Design the Circuit

Now design a circuit that connects the outputs of the instruction register to the wires labeled A - G. Use Boolean logic and whatever gates you need.

Hint 1: build a truth table to help you with this.

Hint 2: consider some of the larger circuits we looked at in class.

Hint 3: Try to use good, modular design when creating this circuit. There should not be a spaghetti of wires all over the place. Using the first two hints will help with this.

Hint 4: The circuit design will be pretty straightforward if you use the previous three hints. If you can't see how to do this, then rethink your instruction set design. You can't just make an arbitrary instruction set or your circuit design will be a mess. Figuring out how to do this is the most important part of this assignment.

OPTIONAL: Optionally, design your circuit so that if an illegal instruction is received (meaning if some combination of inputs is received that does not correspond to a valid instruction), the paint machine does not do anything in response to that invalid instruction (it just sits and does not change state).

Part D: Write the Program in Machine Code

Repeat the program you designed above, this time showing the machine instructions next to the assembly language lines. You only need to do this for the first 15 instructions, if you don't want to do the entire thing.

Bonus Questions

You don't have to answer these to complete the assignment, but give them a try.

1: Which of the assembly language instructions is unnecessary?

2: What problems can happen with the machine if the user doesn't write their assembly language program correctly?

3: What changes are needed to make it so the roller can move more than one pixel at a time?

4: What would be a simple way to reduce from 4 to 3 the number of clock cycles needed to execute an instruction?