課程名稱︰數位系統與實驗
課程性質︰資工系大二必帶
課程教師︰歐陽明
開課學院：電機資訊學院
開課系所︰資訊工程學系
考試日期（年月日）︰2018/06/28
試題 :
1. (10%) Design a circuit which functions as Larry's code below.
module LarryModule(input clk, output reg [3:0] out);
always@(posedge clk) begin
if(out == 4'd9)
out = 0;
else
out <= out+1;
end
endmodule
Design your circuit using AND gates, OR gates, NOT gates, and four JK flip-
flops.
2. (20%) Design a sequential circuit which investigates an input sequence X and
will produce an output of Z = 1 for any input sequence ending in 1101 or 011.
Example:
X 0 0 1 1 0 1 1 0 1 0 1 1 0 1 0
Z 0 0 0 1 0 1 1 0 1 0 0 1 0 1 0
Notice that the circuit does not reset to the start state when an output of
Z = 1 occurs. However, your circuit should have a start state and should be
provided with a method for manually resetting the flip-flops to the start
state.
(a) Create a minimized "state diagram" for this 4-bit sequence detector. A
minimum solution requires six states. (10%)
(b) Design your circuit using three D flip-flops. (Assign 000 to the start
state.) (10%)
3. (20%) Consider the circuit below.
https://i.imgur.com/umb0qps.png
\begin{circuitikz}
\tikzset{
flipflop JK1/.style={flipflop, flipflop def={
t1=$J_1$, t2=Ck, c2=1, n2=1, t3=$K_1$, t4=$Q_1'$, t6=$Q_1$
}},
flipflop JK2/.style={flipflop, flipflop def={
t1=$J_2$, t2=Ck, c2=1, n2=1, t3=$K_2$, t4=$Q_2'$, t6=$Q_2$
}}
}
\ctikzset{logic ports=ieee}
\draw (9, 0) node[flipflop JK1](jk1){};
\draw (jk1.bpin 5) node[left]{FF};
\draw (9, -3) node[flipflop JK2](jk2){};
\draw (jk2.bpin 5) node[left]{FF};
\draw (0, 0) node[anchor=east]{Clk} to (jk1.pin 2);
\draw (7.5, 0) node[circ]{} |- (jk2.pin 2);
\draw (4, 3) node[nand port](nand1){};
\draw let \p1=(nand1.in 1) in (0, \y1) node[anchor=east]{$X$} to (\p1);
\draw let \p2=(nand1.in 2) in (0, \y2) node[anchor=east]{$Q_2'$} to (\p2);
\draw (4, 1) node[nand port](nand2){};
\draw let \p1=(nand2.in 1) in (0, \y1) node[anchor=east]{$Q_2$} to (\p1);
\draw let \p2=(nand2.in 2) in (1.5, \y2) node[not port](not1){};
\draw let \p1=(nand1.in 1) in (.5, \y1) node[circ]{} |- (not1.in);
\draw (not1.out) to (nand2.in 2);
\draw let \p1=(jk2.pin 1) in (4, \y1) node[nor port](nor1){};
\draw let \p2=(nand2.in 2) in (2.75, \y2) node[circ]{} |- (nor1.in 1);
\draw let \p2=(nor1.in 2) in (0, \y2) node[anchor=east]{$Q_1$} to (\p2);
\draw (nor1.out) to (jk2.pin 1);
\draw (6.5, 2) node[nand port](nand3){};
\draw (nand1.out) |- (nand3.in 1);
\draw (nand2.out) |- (nand3.in 2);
\draw (nand3.out) |- (jk1.pin 1);
\draw let \p3=(jk1.pin 3) in (6.5, \y3) node[not port](not2){};
\draw let \p2=(nand2.out) in (\p2) node[circ]{} |- (not2.in);
\draw (not2.out) to (jk1.pin 3);
\draw let \p1=(jk2.pin 1) in (7, \y1) node[circ]{} |- (jk2.pin 3);
\draw (12, -1.5) node[nor port](nor2){};
\draw (jk1.pin 4) -| (nor2.in 1);
\draw (jk2.pin 4) -| (nor2.in 2);
\draw (nor2.out) node[anchor=west]{$Z$};
\end{circuitikz}
(a) Construct a state table and graph for the circuit. Assume 00 is the ini-
tial state. (7%)
(b) Is the circuit a Mealy or Moore circuit? (3%)
(c) Draw a timing diagram for the input sequence X = 01100. (6%)
(d) What is the output sequence for the input sequence? (4%)
4. (10%) For the following state table, please determine a minimal state table.
Next State Output
────── ──────
Present State x = 0 x = 1 x = 0 x = 1
────────────────────────
a f b 0 0
b d c 0 0
c f e 0 0
d g a 1 0
e d c 0 0
f f b 1 1
g g h 0 1
h g a 1 0
────────────────────────
5. (10%) One day, Larry found an interesting problem which looked roughly like
this:
There are one door and four guys (X, Y, Z, and W).
The door has several door locks on it, and each guy has keys to some of the
locks.
We find that the door can't be opened unless more than two guys bring all
their keys.
How can this be done? What's the minimum number of door locks and keys re-
quired?
To formulate this problem and make it clear, all we have to do here is find a
function DOOR = f(W, X, Y, Z) which satisfies the following conditions:
ⅰ. Each input value is either 0 or 1.
ⅱ. DOOR = 1 when more than two inputs are equal to 1, otherwise DOOR = 0.
ⅲ. It must be written in the form of product-of-sums.
ⅳ. Any usage of negation is prohibited.
ⅴ. The number of sum terms is minimal.
ⅵ. The number of appearance of variables is minimal.
Please write down the truth table of this function, construct the K-map
(please focus on all 0s instead of 1s), and derive the simplified product-of-
sums expression.
6. (15%) Design a sequential circuit. It has two inputs A and B, and one output
Y. When the circuit sees a "101" on input A, Y will output the complement of
B for the next 16 cycles; otherwise, Y will be 0. The circuit should ignore
what A is receiving during these 16 cycles. Use positive-edge-triggered T
flip-flops and a 4-bit binary counter as your building block, and below is an
example patterns:
Input A: 0011 0010 0110 1001 0010 1010 1110 0111
Input B: 1011 0011 1000 1111 0000 1111 1000 0011
Output Y: 0000 0000 0000 0000 1111 0000 0111 0000
7. (15%) There is an MN flip-flop, which
(ⅰ) if MN = 00, this flip-flop's next state is 0,
(ⅱ) if MN = 01, this flip-flop won't change its state,
(ⅲ) if MN = 10, this flip-flop's next state is the complement of present
state,
(ⅳ) if MN = 11, this flip-flop's next state is 1.
(a) Use present state (Q), next state (Q') and input (M, N) to construct a
table. (Notice: use don't-care term as possible as you can.)
(b) Use derived table and K-maps to design a counter which consists of three
MN flip-flops, and its output sequence is as below:
ABC = 000, 010, 001, 100, 110, 000, 010, ...
For your reference:
Excitation Table
\begin{tabular}{cc|cc|cc|c|c}
$Q$ & $Q^+$ & $R$ & $S$ & $J$ & $K$ & $T$ & $D$\\
\hline
0 & 0 & X & 0 & 0 & X & 0 & 0\\
0 & 1 & 0 & 1 & 1 & X & 1 & 1\\
1 & 0 & 1 & 0 & X & 1 & 1 & 0\\
1 & 1 & 0 & X & X & 0 & 0 & 1
\end{tabular}
Characteristic Equations
R-S: $Q^+ = S + \bar RQ$
D: $Q^+ = D$
J-K: $Q^+ = J\bar Q + \bar KQ$
T: $Q^+ = T\bar Q + \bar TQ$