15110 Fall 2011 [Cortina/von Ronne]

Written Homework 7 - due Friday, October 28 in class

Reading Assignment

Read sections 8.1-8.6 in chapter 8 of the textbook Explorations in Computing.

Instructions

Type or neatly write the answers to the following problems.
Please STAPLE your homework before you hand it in.
On the first page of your homework, include your name, andrew ID, lab section (A-N), and the assignment number.
You must hand in your homework at the start of class on the given due date.

Exercises

(2 pts) For the following Boolean formulas, write a truth table that shows the value of the function for each possible combination of assignments to the boolean variables X, Y and Z. Use 1 for true and 0 for false. (NOTE: The NOT (¬) operator has a higher precedence than the AND (∧) and OR (∨) operators.)
1. (X ∧ Y) ∨ (¬Y ∧ Z)
2. ¬(X ∧ Y) ∧ Z
3. X ∨ (Y ∧ Z)
4. (X ∧ Z) ∨ (¬X ∧ ¬Y ∧ Z) ∨ (X ∧ Y ∧ ¬Z)
(1 pt)
1. The boolean expressions in problem 1 can be realized as an electric circuit. Such circuits can be represented abstractly using logic gates (instead of transistors). Draw how the first formula in problem 1 would be realized as a computational circuit at the gate level of abstraction.
2. Are any of the Boolean expression in problem 1 computationally equivalent? If so, which ones are equivalent? If not, how do you know?
(1 pt) Let ABCD represent a 4-bit binary-coded decimal number as described in Homework 6. For example, the decimal digit 7 is represented in binary-coded decimal as 0111, so in this case, A = 0, B = 1, C = 1, and D = 1.
A seven-degment display can be used to display each of the ten decimal digits as shown below.

We can define a circuit abstractly below that requires four Boolean inputs A, B, C, and D, and seven Boolean outputs s₁, s₂, ..., s₇ to control each segment of the display:
1. Derive a Boolean formula for s₄ that is true (1) if and only if the middle segment is lit.
  Your answer should be of the following form:
  s₄ = (________) ∨ (________) ∨ (________) ∨ ...
  where each missing section is a boolean expression with all 4 input variables that is true when ABCD represents a decimal digit that results in the middle segment of the display being lit. To help you get started, the digit 2 (binary 0010) will light the middle segment, so the first expression in the formula above would be
  (¬A ∧ ¬B ∧ C ∧ ¬D)
  since this formula would be true (1) if A = 0, B = 0, C = 1, and D = 0. You will need to find all of the other missing expressions.
2. (HARDER) Simply the Boolean expression from part (a) using Boolean logic laws into a formula with 4 terms that are combined using the OR (∨) operator, each term containing only 3 Boolean variables each. (HINT: You'll probably need to use the distributive law discussed in class.)
(1 pt) In Ruby, there is another loop called an until loop that runs until a particular condition is true. For example, Consider the following code using a while loop:
```
i = 0
sum = 0
while i != 10 do
    sum = sum + i
    i = i + 1
end
```
We can also write this code equivalently using an until loop:
```
i = 0
sum = 0
until i == 10 do
    sum = sum + i
    i = i + 1
end
```
Use DeMorgan's Law to convert the following while loops to equivalent until loops.
1. ```
while (x > 15) && (y <= 110) do
   ...
end
```
2. ```
while (a != 20) || (b == 11 && c < 42) do
   ...
end
```
(1 pt) A simpler adder is called a half adder which only adds 2 bits (X and Y) to produce a sum bit (S) and a carry_out (C) bit, as shown in the following truth table:
```
 X  Y  |  C  S
---------------
 0  0  |  0  0
 0  1  |  0  1
 1  0  |  0  1
 1  1  |  1  0
```
This adder can be represented abstractly using the following diagram:
1. Give Boolean formulas for C and S as functions of X and Y.
2. (HARDER) Using two half-adders and one OR gate, show how to build a full-adder as defined in class. Your picture should have three inputs, X, Y, and Carry_In and two outputs, S and Carry_Out.
(1 pt) When a programmer writes a program in a high-level language (e.g. Ruby), the program must be translated to binary machine language for the CPU to execute it. There are two kinds of programs that can be used to do this translation: an interpreter or a compiler. Which do you think is faster to run by a CPU: a program that is translated one instruction at a time by an interpreter or a program that is translated in its entirety first by a compiler? Why?
(2 pts) Write a MARS program that computes 2 raised to a positive integer power. For this specific program, you will write it so it computes 2⁵. You will need two words to hold data in "memory": a data word for the exponent (5) and a data word to hold the result (start this value with 1). To compute 2⁵, just add the result to itself 5 times. Your program should work for any positive integer exponent, so don't just write 5 ADD instructions. You will need to create a "loop" using MARS instructions. Write this program by hand (or type it) in your homework using the standard MARS assembler syntax as shown in class.
Then test your program in irb using the MARSLab from RubyLabs. First, make a test machine with your program using the make_test_machine function. Then use the dump function to show how your program is represented in "memory". Then repeat the following until the program halts: execute the step function followed by the dump instruction. Once you are done, copy all of the results from irb into a text file and include this with your homework to show that you have tested your solution.
(1 pt) Consider the following MARS program imp.txt:
```
start   MOV 0, 1
        end start
```
This is loaded into MARS as follows:
m = make_test_machine("imp.txt", 100)
What does this program do? Explain clearly. (HINT: Look at your textbook!)