CSCI 162: Spring 2019 Midterm Sample Solutions

Question Mark
1. Data representation
[16 marks] 		 
2. Boolean logic and digital circuits
[16 marks] 		 
3. Architecture and assembly language
[16 marks] 		 
Exam Total

[48 marks]

 

Question 1: Data representation [16]

  1. [8] Using a 12-bit two's complement representation, fill in the table below to show the binary, octal, and hexadecimal representations corresponding to the decimal value shown.
    (Advice: make use of the powers-of-2 table in the reference sheet.)
    decimal binary octal hexadecimal
    -2048
          		1000 0000 000 4000 800
    1537
          		0110 0000 0001 3001 601
    -5
          		1111 1111 1011 7773 FFB
    74
          		0000 0100 1010 0112 04A

  2. [4] Using an 8-bit two's complement representation, first show the result (in binary) of taking the binary value 00100110 and multiplying that by 4, then show the result (also in binary) of taking that value and applying an arithmetic shift right by 3 bits. 

    Sample solution
0010 0110 x 4 is like shifting left by 2 bits,
   i.e. 1001 1000
if we then do an arithmetic shift right by 3 it will shift in 1's
   i.e. 1111 0011

  3. [4] Suppose we chose to represent floating point numbers using a sign bit, 8 bits for an exponent, and 23 bits for a mantissa. When we want to multiply integers by powers of 2 we can do this quickly using bit shifts. Does the same idea apply with our floating point representation? Justify your answer. 

    Sample solution
Doing a simple bit shift wouldn't work, we would be shifting some of
   the mantissa bits into the exponent, and the exponent bit(s) could
   be shifted into the sign bit or lost entirely

But, since the exponent already represents the power of 2 we are
   multiplying the mantissa by, if we wanted to take the existing
   number and multiply it by 2x then we could get the
   same effect by adding x to the exponent

Question 2: Boolean logic and digital circuits [16]

  1. [6] For the truth table given below, draw the corresponding Karnaugh map and use it to find a minimal sum-of-products expression for function f.
    wxyz f 
    0000 1 
    0001 1 
    0010 1 
    0011 1 
    0100 1 
    0101 0 
    0110 1 
    0111 1 
    1000 1 
    1001 1 
    1010 1 
    1011 1 
    1100 0 
    1101 1 
    1110 1 
    1111 1 
    Our Karnaugh map would look something like
   yz 00 01 11 10
wx
00     1  1  1  1
01     1  0  1  1
11     0  1  1  1
10     1  1  1  1

The minimal expression would then be
    x' + y + wz + w'z'
(remember the table "wraps around" both top-bottom and left-right)

  2. [5] Clearly show how to apply DeMorgan's rule to the circuit below to give a sum-of-products structure, and give the sum-of-products expression matching the new circuit.

    current circuit formula: ((wx'y)'(x'z')'(xy)')' 

    Sample solution
If we apply DeMorgan to the final NAND gate (right before the output)
   it becomes a NOR gate with inverted inputs and inverted outputs
We then note that there are two negations on the final output,
   which cancel each other out,
and that there are two negations on each input to the or gate,
   again cancelling each other out,
and we are left with three AND gates feeding into an OR gate,
   i.e. a sum-of-products on the exact same inputs:
f = wx' + x'z' + xy

  3. [5] The circut below matches the truth table from part 1 of this question.
    circuit formula: ((xy+x')'((w^z)+x'))'

    Suppose the XOR gate is malfunctioning as follows:
        the value output by the XOR gate is always 1, regardless of its input values.

    Fill in the truth table below to match the resulting output for the broken circuit.

    wxyz fbroken
    0000 1
    0001 1
    0010 1
    0011 1
    0100 0
    0101 0
    0110 1
    0111 1
    1000 1
    1001 1
    1010 1
    1011 1
    1100 0
    1101 0
    1110 1
    1111 1 
    
Notes:
 - since the broken xor gate always outputs a 1,
   the or gate following it will always output a 1
 - this means the effect of the final NAND gate is
   to negate whatever comes out of the NOR gate
 - the formula for the output of the NOR gate in
   this circuit is (xy + x')' so if we negate that
   we can see the final circuit output will be
      (xy + x') or (xy')'

Question 3: Architecture and assembly language [16]

The Marie program below obtains a value, N, from the user and displays 2N. 
        input                / get value of N
        store       N
While,  load        N        / compute N-I
        subt        I
        skipcond    800      / if N-I is positive we're not done
        jump        Done     / otherwise we are done
        load        Result   / simulate Result << 1 by doubling Result
        add         Result
        store       Result
        load        I        / increment I
        add         Incr
        store       I
        jump        While    / go back to loop test
Done,   load        Result   / we're done, print Result
        output
        halt
Result, dec         1        / result so far (2^I)
N,      dec         0        / exp  (for 2^N), i.e. num of bits to shift
I,      dec         0        / loop counter
Incr,   dec         1        / used for ++

  1. [2] What is the address (in hex) of the line "Result, dec 1"? Explain how you computed the address. 

    Sample solution
The addresses are numbered sequentially by instruction, starting from 0
  so the "Result," line would be #16 in decimal or #10 in hex

  2. [4] Which instruction in the program would have machine code 3010 (hex)? Explain how you got your answer. 

    Sample solution
3xxx is the add instruction,
and 010 is the address of Result (as we saw in part 1 above)
so 3010 is the "add Result" instruction

  3. [4] What does the program currently do if the user enters a negative integer for N. 

    Sample solution
The result of the first N-I is negative,
so the skipcond does NOT skip,
so we immediately jump to DONE,
where we load and display RESULT (which is 1)
i.e. the program just displays 1 then ends

  4. [6] Modify the program so that if the user enters a negative integer for N then the program outputs -1 and halts. 

    Sample solution
There are many possible approaches, one would be
   to add a section before the While to see if the
   value is negative, and if so put a -1 in Result
e.g.
   input
   store N
   skipcond 000  / first line of new code section
   jump While
   load Neg1
   store Result  / last line of new code section
...
   rest of program goes here
...
Neg1, dec -1    / declare the new variable we used