課程名稱︰數位系統與實驗
課程性質︰必修
課程教師：歐陽明
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰2015.05.11
考試時限（分鐘）：
試題 :
NTU CSIE Digital System and Labs 2015 MIDTERM May 11, 2015
1. (14%) Plot the following functions on a Karnaugh map and convert them into
minimum sum of products.
a. (4%) f(a,b,c) = Σm(0,1,3,6)?
b. (4%) g(w,x,y,z) = Σm(3,4,7,10,11,14) + Σd(2,13,15)
c. (6%) Find all minimum sum of products expressions
F(a,b,c,d) = Σm(0,2,3,7,8,9,13,15) + Σd(1,12)
2. (20%) For the three functions of four variables shown on the maps below
(5%) Implement it with the ROM
(5%) Find a minimum cost two-level NAND circuit (where minimum cost is
minimum number of gates, and among those with the same number of
gates, minimum number of gates inputs). Assume all inputs are
available both complemented and uncomplemented (minimum is 10 gates).
(5%) Implement it with a PAL similar to the one in the textbook.
(5%) Implement it with the PLA with eight product terms available (You may
use fewer.)
╔═══╤═╤═╤═╤═╦═══╤═╤═╤═╤═╦═══╤═╤═╤═╤═╗
║ CD\AB│00│01│11│10║ CD\AB│00│01│11│10║CD\AB │00│01│11│10║
╟───┼─┼─┼─┼─╫───┼─┼─┼─┼─╫───┼─┼─┼─┼─╢
║ 00 │ │ │ │ 1║ 00 │ 1│ 1│ 1│ 1║ 00 │ │ │ 1│ ║
╟───┼─┼─┼─┼─╫───┼─┼─┼─┼─╫───┼─┼─┼─┼─╢
║ 01 │ 1│ 1│ │ 1║ 01 │ │ 1│ │ ║ 01 │ 1│ 1│ 1│ ║
╟───┼─┼─┼─┼─╫───┼─┼─┼─┼─╫───┼─┼─┼─┼─╢
║ 11 │ 1│ 1│ │ 1║ 11 │ │ 1│ │ ║ 11 │ 1│ 1│ 1│ ║
╟───┼─┼─┼─┼─╫───┼─┼─┼─┼─╫───┼─┼─┼─┼─╢
║ 10 │ │ │ │ ║ 10 │ 1│ │ │ 1║ 10 │ 1│ │ 1│ 1║
╚═══╧═╧═╧═╧═╩═══╧═╧═╧═╧═╩═══╧═╧═╧═╧═╝
X Y Z
3. (10%) Prove the identity of each of the following Boolean equations, using
algebraic manipulation.
a. (3%) (x + y)(x' + y) = y
b. (3%) x + y(x + z) + xz = x + yz
c. (4%) (xy + z'(s + t'))' = (x' + y')(z + s't)
4. (6%) Simplify the logic diagram below.
logic diagram: http://i.imgur.com/2y1IkWO.png
5. (12%) In cryptography, the term "plaintext" is information a sender
wishes to pass to receivers, while the term "ciphertext" is the result of
encrypted plaintext. Here we introduce the "XOR cipher" where the ciphertext
is generated by plaintext XOR the key:
plaintext: 1011 1110 1110 1111
the key: 0110 0110 0110 0110
─────────────────
ciphertext: 1101 1000 1000 1001
Now we define that the 4-bit codes indicate the hexadecimal numbers,
from 0000 = 0 to 1111 = F. So the example above encrypts the
"BEEF" to "D889" with the key "0110". And if the key were "1101 0011", the
ciphertext would be "6D3C". Answer the questions:
i) What is the ciphertext if the plaintext is "BABEFACE" with the key
"3D"?
ii) We have just intercepted the enemy's ciphertext "3310AE86", and we
have known that they encrypt the text "C" as "6". Please decrypt the
intercepted message.
iii) The intelligence agency just indicates that our enemy just changed
their encryption method. They AND and OR plaintext with key,
respectively, then XOR these 2 results to generate the ciphertext.
According to this rule, what is the plaintext for the question (ii)?
6. (12%) Given the Venn's Diagram as below, each number represents a set, use
sum of sets to answer the following questions. For examples:
A · B = 4 + 7, A + B = 1 + 2 + 4 + 5 + 6 + 7:
Venn's Diagram: http://i.imgur.com/LkLXN5R.png
i) (ABC)'
ii) (A NAND B) NOR C
iii) F(A, B, C) = Σ(2, 3, 5, 7)
iv) Minterm m_3 of F(A, B, C)
v) A ⊕ B ⊕ C
vi) A NXOR B NXOR C
7. (10%) Consider a 6-bit division checker D as the following: the first 4-bit
indicates dividend, and the rest represents divisor. D returns True (= 1)
if the dividend is divisible by the divisor; otherwise it returns False
(= 0). By the way, D returns X (don't care) if the divisor is zero. For
example: 101010 means "Is 10 divisible by 2?" the answer is true, so D = 1.
011000 means "Is 6 divisible by 0?" in this example, D = X due to zero
divisor.
i) Draw the K-map for D (6%)
ii) Write the Boolean expression for D, your answer should include a
1-literal term and a 2-literal term at least (4%)
8. (16%) The following left figure shows 4 to 5 magnitude comparator, which
takes 2 binary numbers as input and determine whether the first number is
greater than (G), less than (L) the other number by 1 (X), by 2 (Y), or by
3 (Z). We regard inputs as A_1 A_0 and B_1 B_0 in unsigned integers, and
assume that 1 means true in output, while 0 means false.
For example, if the input is 0110, this comparator should output
(0, 1, 1, 0, 0) since 1 is less than 2 by 1. Answer the following questions:
┌───┐ A3 A2 B3 B2 A1 A0 B1 B0
│ G├─○ ○ ○ ○ ○ ○ ○ ○ ○
A1 ○─┤ │ │ │ │ │ │ │ │ │
│ L├─○ ┌─┴─┴─┴─┴─┐┌─┴─┴─┴─┴─┐
A0 ○─┤ │ │ ││ │
│ X├─○ │ ├┤ │
B1 ○─┤ │ │G2 L2 X2 Y2 Z2││G1 L1 X1 Y1 Z1│
│ Y├─○ └┬─┬─┬─┬─┬┘└┬─┬─┬─┬─┬┘
B0 ○─┤ │ │ │ │ │ │ │ │ │ │ │
│ Z├─○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○
└───┘
i) Under what condition the output would be (0, 0, 0, 0, 0), and how many
possibilities are there. (2%)
ii) Draw the K-maps for G and X (2%)
iii) Draw the PLA implementation of this magnitude comparator (4%)
iv) Now we combine two magnitude comparators to implement a bigger
comparator as the right figure above. Let the function F means
A - B = 5. Write the Boolean expression for F using ten outputs above
(G_2, L_2, …, Z_1) only. (4%)
9. (Optional, A, choose either A or B only) (10%) What is the function of the
following circuit diagram? Explain your answer.
circuit diagram: http://i.imgur.com/QrXzeZs.png
9. (Optional B, choose either A or B only) (10%) (Verilog HDL) Take a look at
the following Verilog program.
a. (3%) Can a Verilog module name start with a number?
b. (4%) Do "clk" below need to be declared in the parameter list?
c. (3%) Should the module end with "endmodule" or "endmodules"?
┌───────────────────────────────────┐
│module 16x16-MAC (out, rst, op1, op2) │
│input clk, rst; │
│input [15:0] op1, op2; │
│output [39:0] out; │
│reg [31:0] product; │
│assign product = op1 * op2; │
│//40-bit accumulator after 16x16 multiplier │
│always @(posedge clk || negedge rst) │
│ if(rst) out = 0; │
│ else out = out + product; │
│endmodules │
└───────────────────────────────────┘