課程名稱︰數位系統與實驗
課程性質︰必修
課程教師︰廖世偉
開課學院：電機資訊學院
開課系所︰資訊工程學系
考試日期（年月日）︰104/5/11
考試時限（分鐘）：180分鐘
試題 :
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. (21%) For the three functions of four variables shown on the maps below
a. (7%) 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).
b. (7%) Implement it with the ROM
c. (7%) Implement it with the PLA with eight product terms available (You
may use fewer.)
http://imgur.com/SaeboLZ
3. the identity of each of the following Boolean equations, using algebraic
manipulatoin.
a. (3%) (x+y)(x'+y) = y
b. (3%) x+y(x+z)+xz = x+yz
c. (3%) (xy+z'(s+t'))' = (x'+y)(z+s't)
4. (6%) Simplify the logic diagram below.
http://imgur.com/jJsVchZ
5. (12%) In crptography, 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 ANDand 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:
http://imgur.com/lwaSsyA
i) (ABC)'
ii) (A NAND B) NOR C
iii) F(A, B, C) = Σm(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 (= l) 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 = l.
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), orby 3
(Z). We regard inputs as A1A0 and B1B0 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, l, l, 0,
0)
since 1 is less than 2 by l. Answer the following questions:
http://imgur.com/6iqlgwi
i) Under 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 (G2, L2, ..., Z1) only. (4%)
http://imgur.com/8DypaKS
9. (Optional A, choose either A or B only) (10%) What is the function of the
following circuit diagram? Explain your answer.
http://imgur.com/xwwOD6C
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%) Does "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, opl, op2) │
│ │
│input clk, rst; │
│ │
│input [15:0] op1, op2; │
│ │
│output [39:0] out; │
│ │
│reg [31:0] product; op1 * op2; │
│ │
│assign product │
│ │
│//40-bit accumulator after 16x16 multiplier │
│ │
│always @(posedge clk || negedge rst) │
│ │
│ if(rst) out 0; │
│ │
│ else out = out + product; │
│ │
│endmodules │
└───────────────────────────────┘