课程名称︰交换电路与逻辑设计
课程性质︰大二必修
课程教师︰简韶逸
开课学院：电资学院
开课系所︰电机工程学系
考试日期（年月日）︰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 有图待补。