Midterm review: numbers, logic, memory, von Neumann, LC-3

This page is a compressed version of the first eight weeks. We collected the recipe of each topic in a table, then gave the solutions of mixed questions. This is a procedure course: most of the points come from questions solved with the same steps every time. First read the table, then solve the questions against the clock, and go back to the page of the topic you got wrong.

The scope of the midterm may change from semester to semester (in some semesters weeks 1-6, in some the LC-3 is included). Decide which block to emphasize according to the announcement on the course page.

Topic → question type → recipe

Five reminders for exam day

1. Write the representation. An expression like “8-bit 2’s complement” should be at the start of your answer.
2. Do the check. In every conversion, go back to decimal and verify. Five seconds, one point.
3. For overflow, write the rule sentence: “Overflow occurs only if both operands have the same sign and the result has the opposite sign.”
4. In simplification, write the name of the rule: distributive, complement, DeMorgan…
5. In the LC-3, add the offset to the incremented PC. The most commonly lost point.

Mixed examples

Numbers: the four readings of 0x9C and sign extension

0x9C = 1001 1100
unsigned  128+16+8+4          = 156
SM        minus, 001 1100 = 28 = -28
1's       flip 0110 0011      = -99
2's       156 - 256           = -100
sign extension to 16 bits: 1111 1111 1001 1100 = 0xFF9C (still -100)

IEEE: encode 19.5

19 = 10011, 0.5 = .1 → 10011.1 = 1.00111 × 2^4
S = 0, E = 4 + 127 = 131 = 1000 0011, F = 00111 0...
0 10000011 00111000000000000000000 = 0x419C0000

Logic: Σm(2, 3, 6, 7)

m2 = A'BC'  m3 = A'BC  m6 = ABC'  m7 = ABC
A'B(C' + C) + AB(C' + C) = A'B + AB = B(A' + A) = B

Four minterms were reduced to a single letter: every row where B = 1.

Memory and FSM

$2^{14}$ locations × 32 bits = $2^{14} \times 4$ bytes = 64 KB. An FSM with 12 states: $2^3 = 8 < 12 \le 16$ → 4 flip-flops.

von Neumann

FETCH when PC = x4A3F: MAR ← x4A3F, PC ← x4A40, MDR ← M[x4A3F], IR ← MDR. The increment of the PC in hex: F + 1 = 10, the carry goes left.

LC-3: encode, decode, trace

LDR R5, R1, #-2 → 0110 101 001 111110 = x6A7E.

xA9FE at x3000 → 1010 100 111111110 → LDI R4, offset -2 → pointer address x3001 - 2 = x2FFF; R4 ← M[M[x2FFF]].

        AND  R1, R1, #0     R1 = 0
        ADD  R2, R1, #3     R2 = 3
AGAIN   ADD  R1, R1, R2     |  round R1   R2
        ADD  R1, R1, R1     |   1     6    2
        ADD  R2, R2, #-1    |   2    16    1
        BRp  AGAIN          |   3    34    0  (Z, fall through)
        HALT

Overflow: three additions, three decisions

The third row is the trap the exam likes: there is a carry-out but the result is correct. In the second row the true sum is -129, which went past the lower limit of 8 bits, -128.

Circuit: a NOR and an AND

Gate 1 NOR(A, B) = X, gate 2 AND(B, C) = Y, gate 3 OR(X, Y) = F. When you fill in the table with the intermediate columns, you get F = Σm(0, 1, 3, 7) = A’B’ + BC (week 3, the circuit reading section). In the exam, give a name to every intermediate output; partial credit comes from there.

I/O: a three-line wait loop

POLL    LDI  R1, KBSRP   ; read KBSR
        BRzp POLL        ; bit 15 = 0 → wait
        LDI  R0, KBDRP   ; the character is in R0

When ready, KBSR = x8000, that is negative. That is why BRzp. KBSRP is a .FILL xFE00; LD cannot reach that far, LDI is needed.

Instruction cycle: the phases of LDR

LDR R4, R2, #-3, R2 = x4005: FETCH (MAR ← PC, PC ← PC + 1, IR ← instruction), DECODE (opcode 0110), EVALUATE ADDRESS (x4005 - 3 = x4002), FETCH OPERANDS (MDR ← M[x4002]), no EXECUTE, STORE RESULT (R4 ← MDR, the CC is set). Memory was accessed twice.

Quick checklist

Common mistakes

        AND  R1, R1, #0
        ADD  R2, R1, #3
AGAIN   ADD  R1, R1, R2
        ADD  R1, R1, R1
        ADD  R2, R2, #-1
        BRp  AGAIN
        HALT