Submit as a PDF file via Moodle by 8:30AM Wednesday, May 1. For circuit diagrams and other pictures, you may draw by hand and scan or photograph the picture for inclusion in your PDF, but please make sure the resulting image is readable. For problem #2, you may either copy your code into the PDF or include an asm file with your submission.
This is an exam. You may consult your notes, any book, and the internet. You may not speak with any person other than Jeff Ondich, electronically or otherwise, about the content of this exam. If you obtain relevant information from any source other than yourself, cite your sources clearly.
(4 points) Consider this C program. Get yourself to a Unix terminal (say, on one of the Macs in the CMC labs or Weitz 138). Follow the instructions in the comment to compile and run the program. This program runs for kind of a long time, so just let it run until it completes. Read a book or something.
- What number does the program print out (eventually)?
- Explain clearly and precisely why it's exactly that number and not some other number.
(8 points) Write a MIPS subroutine called convert whose job is to convert a string encoded in UTF-16LE to UTF-16BE. At the time convert is invoked (via jal convert), register a0 should contain the memory address of a null-terminated UTF-16LE string. After convert returns (via jr $ra), the string (i.e. in the exact same memory addresses) should be a null-terminated UTF-16BE string with the same characters in it.
Note that this is not really as complicated as it might sound. The convert subroutine just needs to swap the first and second bytes, then swap the third and fourth bytes, etc. until it encounters two bytes containing zero.
(6 points) Consider the 32-bit number 0x80470007. What does this number represent if you interpret it as:
- a two's complement integer?
- a MIPS instruction? (You may find this chart of op codes handy.)
- two characters encoded in UTF-16LE?
- two characters encoded in UTF-16BE?
-
(8 points) Consider the MIPS instruction
li $s5, 17- The Mars assembler treats "li $s5, 17" as a pseudo-instruction, and converts it into a different MIPS instruction. What instruction is that?
- For the instruction in part (a), show a diagram of the MIPS instruction, and the values of each of its fields. (See this intro to instruction formats for examples of the kind of diagram I'm talking about. If the instruction is an R-format instruction, for example, show me the contents of all six of its fields; if it's I-format, show me the contents of all four of its fields; etc.)
- If you replace the 17 in our original instruction with 98765 (i.e. li $s5, 98765), Mars converts the pseudo-instruction into two instructions. What are they?
- Why does Mars convert li $s5, N into a single MIPS instruction for N=17, but into a pair of instructions for N=98765?
- For which values of N will li $s5, N become just one instruction, and for which values will it become two?
(8 points) Consider the following boolean function of three variables:
A B C | Out ================ 0 0 0 | 1 0 0 1 | 1 0 1 0 | 0 0 1 1 | 1 1 0 0 | 0 1 0 1 | 1 1 1 0 | 1 1 1 1 | 1- Write a boolean algebraic expression for this function, using a sum of 3-term products, as we did with a similar function in class. (That is, I want a sequence of 3-input ANDs, all OR'd together.)
- Simplify your algebraic expression as much as possible.
- Draw a circuit implementing this function using only NOT gates and 2-input AND and OR gates. Use as few gates you can.
(6 points) Consider the following story about D latches and flip-flops.
- In the beginning, Q = 0, D = 1, and C = 0
- C's value rose to 1
- D's value fell to 0
- C's value fell to 0
Assuming there was a long enough pause between each step to enable the whole circuit to stabilize, draw a timing diagram for this story for each of the following:
This D latch
This D flip-flop
- The D flip-flop, but with the NOT gate moved so it goes in front of the C line on the lefthand latch instead of the righthand latch
(2 points) I'm looking for a TV show to watch. Any suggestions? (Don't watch TV? I'm always looking for book recommendations, too.)
(8 points) I was at a lunch yesterday, talking to my friend Julie from the Psychology department, and she told me about a digital circuit she needed to build a few years ago in her research into the behavior and cognition of monkeys. I don't remember the exact circuit, but it was something like this.
You start with a button, of the kind where you can push it down, but when you take your hand off it it pops up again. This button has a line coming out of it that has value 0 when the button is in its normal state, and value 1 when you're pushing the button down. In addition to the button, this circuit has two lights (L1 and L2), each with a single input line. Each light is on if its input line has value 1, and off if its input line has value 0.
Julie wants these devices to behave like so:
- Start with both lights off
- Push and release the button, and now L1 is on and L2 is still off
- Push and release the button again, and now both lights are on
- Push and release the button a third time, and now both lights are off
Your job is to design a circuit that does this. Your circuit should have one button, two lights, and any of the digital components we have discussed in class (i.e. gates, multiplexers, decoders, adders, D latches, and D flip-flops). You definitely won't need all of those components, but you'll need some. Keep your circuit as simple as possible.