課程名稱︰交換電路與邏輯設計
課程性質︰大二必修
課程教師︰簡韶逸
開課學院：電資學院
開課系所︰電機工程學系
考試日期（年月日）︰2015/1/16
考試時限（分鐘）：110 分鐘
試題 :
===============================================================================
Switching Circuits & Logic Design, Fall 2014
Final Exam( 3:30 pm ~ 5:20 pm, 2015/1/16 )
Problem 1:( 25 points )
摩斯密碼(Morse code)是在加密傳送資料時一種被廣泛應用的編碼方式，可藉由連續
的閃光、敲擊或聲音來傳送。因應外太空通訊需求，吳教授發明了一種簡單版的摩斯密
碼，稱為Simplified Morse Code(簡稱 S-Morse code)。S-Morse code在傳送時可以用
兩種聲音(或字元)來表示，分別是"Di"(。)跟"Da"(─)。另外，當code不足四個字元時
，會以空訊號"X"做填補，等待下個訊息。在譯電員解碼時，會以0來表示"Di"(。)，1
來表示"Da"(─)及don't care X表示空訊號(X)(Table 1)。在解碼時會因為符合的字元
數不同而有不同的優先順序，完全符合的字元數越多具有較高的順位；舉例來說，"。
───"在解碼時與"。───"有4個字元完全符合、與"。─XX"有2個字元完全符合，
此時便會被解碼成"0"而非"1"。接下來，本題將提供一S-Morse code的解碼器系統架構
，並在解碼後已7-segment display來表示解碼的結果。
附註：7-segment display為常用顯示數字的電子元件。藉由七個發光二極體以不同組
合來顯示數字，其中包含四個直向、三個橫向另外加上右下角一點的發光二極體，由以
上發光體便可組合出不同的數字。其對外有10個pin角分別代表a, b, c, d, e, f, g及
h，另外兩個pin腳供Vss與Gnd使用(see Fig. 1 and 2)。
Simplified Morse Code
Number Q3 Q2 Q1 Q0
1 。 ─ X X
2 ─ 。 。 。
3 ─ 。 ─ 。
4 ─ 。 。 X
5 。 ─ 。 。
6 。 。 ─ 。
7 ─ ─ 。 X
8 。 。 。 。
9 。 。 X X
0 。 ─ ─ ─
下圖(Fig.3)為一S-Morse code解碼器架構圖，其中包含shift register, counter及
7-segment display。其中counter的輸入為(T5T4)，輸出為(Q5Q4)，combinational
logic的輸入為(Q3Q2Q1Q0)。請依照以下各小題要求完成此架構設計。
(a)(5%) Please help to build the 2-stage counter using T flip flop and the
enable logic. Note that you should derive the input logic of T5, T4 and
the enable logic as the function of Q5, Q4.
The count sequence is 00 01 11 10 00 ... and 7-segment display will show
the number only when the counter's output is 10.
(b)(15%) Please derive the combinational logic of a, b and c as the
function of Q3, Q2, Q1, Q0 for the input of 7-segment display( needn't
consider the enable signal )
(c)(5%) Please try to decode the following sequence. Answer the question
with decoded numbers.
"。───。。─。。─。。─。─。──。。─。。。。。。。"
Problem 2:(25 points)
A Mealy sequential circuit has one input X, one output Z, and two D
flip-flop Q1Q2. A timing diagram of this circuit is shown as follows.
(a)(15%) Please construct a state transition table and state graph for
this circuit.
(b)(10%) Implement this circuit with only 4-word x 3-bit ROMs( it only has
2 address bits and stores 3-bit words), multiplexers, and D flip-flops.
Please draw the circuit as well as the contents of the ROMs.( Hint: you
can use more than one ROM )
Problem 3:(25 points)
The function of the decoding machine, S*, is to detect groups of three
consecutive inputs and produce an output Z = 1 if one of the input sequences
UAA, UAG, UGA occurs. Please note that there are four different symbols, A,
C, G and U in the input sequence.
A typical sequecne of inputs(X) and outputs(Z) is:
X = AUG│CCA│UAA│AUG│ACU│GGA│UAG│AUG│CCU│CAC│UUU│AAU│UGA
Z = 000│000│001│000│000│000│001│000│000│000│000│000│001
(a)(12%) Please find the Mealy state graph for the machine above.
(b)(2%) How many D Flip-Flops should be used to design the sequential
circuit in (a)?
(c)(3%) How many variable are there in the Karnaugh map to design the
sequential circuit in (a)?
(d)(8%) Please find the Moore state graph for the machine above.
Problem 4:(13 points)
Consider the conversion between BCD(8, 4, 2, 1) and BCD(8, 4, -2, -1) codes.
(a)(3%) Given a table showing the mapping between the two coding systems
for digits 0, 1, ..., 9.
(b)(6%) Draw a minimum-state Mealy state transition graph that converts
(8, 4, 2, 1) code to (8, 4, -2, -1) code. Assume the input and output
are serial with the least significant bit first, the circuit resets
every four inputs, and only valid codes are given to the input.
(c)(4%) To reverse the conversion (i.e. from (8, 4, -2, -1) code to
(8, 4, 2, 1)), how can we obtain a minimum-state Mealy state transition
graph by modifying that of (b) without starting over the entire design
process? Please state the rule of your modification.
Problem 5:(12 points)
Given a sequential machine M with one (binary) input and one (binary)
output that resets for every k inputs, consider using row matching to
minimize its number of states.
(a)(4%) What is the minimum possible number of states that M can have
after row matching if M is implemented as a Mealy machine?
(b)(4%) What is the maximum possible number of states that M can have
after row mathcing for k = 10 if M is implemented as a Mealy machine?
(c)(4%) Is row matching a complete method for state minimization of a
sequential machine in general (without reset)? Please explain why if the
answer is yes, or give a counterexample if the answer is no.
=============================== 試題完 ====================================
備註：
1. 題目有不懂的可以直接舉手問助教。
2. Problem 1, Problem 2 有圖待補。