CPSC 120, Spring 2002
First Test, February 13


This is the first test from CPSC 120: Principles of Computer Science, Spring 2002.

Question 1: Define each of the following terms, as they relate to this course:
           a) machine language
           b) address of a location in RAM
           c) CPU (Central Processing Unit)
           d) fetch-and-execute cycle

Answer: (Stuff in parentheses is not required for a correct answer.)
           a) Machine language is a programming language that consists of simple instructions, encoded as binary numbers, that can be executed directly by a computer. (Each type of computer has its own machine language. Programs written in other languages must be translated into machine language before the computer can execute them.)
           b) RAM, or "main memory", consists a numbered sequence of locations. The address of a location is its number in this sequence. (Each location can hold a binary number. The address of the location must be specified in order to read that number or to change the number that is stored.)
           c) The CPU is the part of the computer that does all the computations. It executes programs and controls the entire computer. It can be considered to be the "brain" of the computer.
           d) The fetch and execute cycle is the process by which the CPU executes machine language programs that are stored in the computer's memory. The CPU "fetches" one instruction from memory, "executes" that instruction, and repeats this cycle over and over for as long as it is operating.

Question 2: Draw a logic circuit that computes the Boolean expression 

           ( (NOT (A OR B)) AND ( B OR C) )  OR  ( A AND B AND (NOT C) )

Answer:


Question 3: Why do memory circuits need feedback loops?

Answer: If a circuit has no feedback loops, then the outputs of the circuit depend only on the current values of the inputs. A memory circuit must "remember" something. Its state must depend not just on its current inputs, but on what its input were in the past. Without feedback, this is impossible.

Question 4: Write a program for the xComputer that will compute the value of the expression:   42-17+103. The answer should be put into memory location number 7, and the computer should halt after computing and storing the answer.

Answer: 

               LOD-C  42   ;  Put the number 42 into the AC
               SUB-C  17   ;  Subtract the number 17 from the AC
               ADD-C  103  ;  Add the number 103 to the AC
               STO    7    ;  Store the number in the AC in location 7
               HLT         ;  Stop the computer

Question 5:
           (a) What is the meaning of the xComputer instruction JMP 42 ?
           (b) Explain why executing a JMP instruction requires the LOAD-PC-FROM-IR control wire.

Answer:
           (a) This tells the CPU to jump to location 42. That is, instead of executing the instruction in the next memory location, the CPU will get its next instruction from location 42 and then continue on from that point in the program.
           (b) The PC holds the address of the next instruction that the CPU should execute. In order for the CPU to jump to a new location in the program, the address of the new location must be put into the PC. When a JMP instruction is executed, the instruction is stored in the IR, so the address that has to be copied to the PC must come from the IR. Turing on the LOAD-PC-FROM-IR accomplishes the desired transfer of information. (Only the last ten bits of the instruction are copied. The first six bits in the IR encode the instruction, JMP, and the last ten bits encode the address, such as 42.)

Question 6: Convert the binary number 1011012 into an ordinary base-10 number.

Answer: 

      1011012  =  1 X 25  +  0 X 24  +  1 X 23  +  1 X 22  +  0 X 21  +  1 X 20

                          =  32 + 8 + 4 + 1

                          =  45

Question 7: Add the two binary numbers:

                     1 0 0 1 1 1 0 1 0 1
                   + 1 1 1 1 1 0 0 1 1 1
                  -----------------------

Answer:    11001011100

Question 8: Fred needs a logic circuit with the following properties: It has three inputs and it has one output. If exactly one of the inputs is on, then the output will be on. If zero, two, or three of the inputs are on, then the output will be off. Fred thinks that the following Boolean algebra expression describes a circuit with these properties: 

                 ( A OR B OR C )  AND  ( NOT ((A AND B) OR (A AND C) OR (B AND C)) )

Is this formula correct? If so, explain why it works. If not, explain what is wrong with it.

Answer: The formula is correct. One way to test this is to make a table that shows all possible combinations of values for the inputs (A, B, and C) and the value of the expression for each combination of inputs. Then, you can simply verify that the output is as desired. You can also answer the question by reasoning about the expression.

Briefly: The first part of the expression tests whether at least one of the inputs is true. The second part tests that it is NOT the case that two or more inputs are on. For the whole expression to be true, both of these conditions must hold.

In more detail:

Question 9: Explain the purpose of the PC (or Program Counter) register, and explain why it has an INCREMENT-PC control wire.

Answer: The program counter holds the address (in memory) of the next machine language instruction that the CPU is supposed to execute. After executing one instruction, the CPU generally goes on to the instruction in the next memory location. For this to happen, the value in the PC must be increased by one. That's exactly what the INCREMENT-PC does. This wire is used once during each fetch-and-execute cycle to set up the program counter for the next cycle. (But in the case of a jump instruction, of course, the value in the PC will be changed by other means when the instruction is executed.)

Question 10: The Clock is the component that actually makes the computer run. Explain how it does this, and explain how this is related to the COUNT register in the xComputer.

Answer: The clock simply turns its output wire on and off in a continuous cycle. Each time the output wire turns on, other control wires are activated, and one step of the fetch-and-execute cycle takes place. The output wire of the clock is actually connected to the INCREMENT-COUNT wire, which adds one to the number in the COUNT register. The COUNT register counts off the steps in the fetch-and-execute cycle. (The value in the COUNT register goes to the Control Circuit, which uses it to help decide which control wires to turn on.)

Question 11: A major theme of this course is structured complexity. Explain what this means, and then, as a detailed example, describe the steps that lead from transistors to a circuit capable of adding two eight-bit binary numbers. Illustrate your answer with some pictures. (This is an essay question. Your answer should demonstrate the depth of your knowledge.)

Answer: Complex things can be made from simple parts, but for people to deal with complexity, it should be structured. Complex systems can be built in a series of levels, where the step from one level to the next is relatively easy. On each level, components from the previous level are combined to make components that are only a little more complex. These components are then used as building blocks for the next level. By building level upon level in this way, great complexity can be achieved.

We have seen this principle applied to computer hardware. At the bottom level, computers are made from transistors, which are very simple switches. Transistors are combined to make gates, which can carry out simple logical function such as AND, OR, and NOT. Gates can be combined into simple logic circuits, such as a circuit that can take two bits as input and compute their sum. A circuit that does this is called a half-adder. Two half-adders can be used to make a full-adder, which is a circuit that takes three bits as inputs and computes their sum. A full-adder can be used to do the computation for one column in the sum of two 8-bit binary numbers. The inputs to a full-adder represent one bit from each of the numbers and the carry from the column to the right. By combining 8 full-adders, we get a circuit that can add binary numbers. If we continue building up circuits in this step-by-step fashion, we can eventually get something as complex as a computer.

(The two pictures that seem most useful are a diagram of a full adder showing inputs and output and a picture that shows how to put together several full-adder circuits to make a multi-bit adder. An 8-bit adder contain eight full adders. It would have at least 16 inputs (in two groups of 8 to represent the two numbers to be added) and 8 outputs (to represent the sum).)

David Eck, eck@hws.edu