E15: Fundamentals of Digital Systems - Fall 2015 - HOMEWORK 3
1. For the function F(w, x, y, z) = Σ(0, 1, 4, 5, 7, 10, 11, 13, 14, 15)
a. Simplify the function using a K-map to form a sum of products.
b. Draw a gate diagram implementing the SOP using NAND gates (you may use inverters, but only to complement the input variables).
2. For the function F(a, b, c, d) = Σ(3, 6, 7, 9, 12, 13)
a. Simplify the function using a K-map to form a product of sums.
b. Draw a gate diagram implementing the POS using NOR gates (you may use inverters, but only to complement the input variables).
3. For the function F(A, B, C, D) = Σ(0, 1, 2, 3, 4, 6, 8, 9, 10, 11, 12, 14)
a. Simplify the function using a K-map to form either a sum of products or product of sums representation of F.
b. Based the Boolean expression you obtained, would it be more natural to implement F using NAND gates or NOR gates? Why?
4. In computer graphics programming, a bitmap is an image made of 0's and 1's. On a 5 row by 8 column grid, draw the bitmap which corresponds to the '1' bits set in the following sequence of hexadecimal numbers: D7, 94, D6, 91, D6.
The first number should correspond to the top row of the image, and the LSB should be in the rightmost column. You should find the bitmap's contents relevant to this course.
5. Here's a couple of shortcuts for converting numbers from binary to decimal.
The number 011000112 is quickly converted to decimal because it's equal to 3 = 112 plus 3 · 25 = 11000002 (since multipying by two is equivalent to shifting a number one bit to the left and adding a zero onto the right hand side).
You can also mentally group bits into four-bit nibbles and multiply by powers of 16. This is the same as converting from binary to hexadecimal, to decimal. For instance, 010110012 = 16 · 5 + 9, because the binary number 01012 = 5 is shifted four bits to the left (i.e. multiplied by 16), and added to the binary number 10012 = 9.
Finally, if an n-bit binary number has just one or two zeros in it, it can be faster to work by starting with 2n-1 - 1 and subtracting off the zero elements. For example, 111101112 = 255 - 8 = 247.
Use your newfound powers of awesomeness to convert these binary numbers to decimal. For each number, indicate which shortcut you used.
a. 11111010
b. 11100110
c. 10100001
6. Convert the following decimal numbers to binary 4-bit two's complement representations, or explain why the conversion is not possible.
a. 3
b. -5
c. 6
d. -10
e. -4
f. 14
7. Perform these 4-bit two's complement sums, following the example below. In addition to the sum, indicate the decimal representations of the addends and the 4-bit result. If the conversion of the 4-bit result from two's complement binary to decimal does not equal the correct quantity, please indicate that overflow has occurred.
Example: 0101 + 1101.
1 1 (carry bits)
0101 (5)
+ 1101 (-3)
1 0010 (2)
a. 0100 + 0011
b. 1100 + 0101
c. 0111 + 0101
d. 1101 + 1011
e. 1110 + 1001
8. Let A3, B3, and S3 represent the MSB of the 4-bit addends and sum, respectively, of a two's complement addition operation. How can we determine of overflow has occurred simply by examining these three bits alone?