京都大学 情報学研究科 通信情報システム専攻 2020年8月実施 専門基礎B [B-4]

标签：

• Kyoto-University
• Boolean-Function-Minimization
• Not-AND-and-Not-OR-Universal-Gates
• Mealy-Machine
• Finite-State-Machine-Minimization
• D-Flip-Flop

Author

SUN

Description

Answer all the following questions.

(1)

Suppose that we design a circuit that compares two 2-digit binary integers $A = (a_1 a_0)_2$ and $B = (b_1 b_0)_2$ represented by two 2-bit inputs $(a_1, a_0)$ and $(b_1, b_0)$. It outputs 1 in the case of $A > B$, and outputs $0$ in the case of $A \le B$. Answer the following questions.

• (a) Give a minimal sum-of-products expression of output $x$.
• (b) Give a minimal product-of-sums expression of output $x$.
• (c) Derive a logic circuit that realizes $x$ with the minimum number of 3-input NAND gates only. Assume $a_1, a_0, b_1, b_0$ and their complements $\overline{a_1}, \overline{a_0}, \overline{b_1}, \overline{b_0}$ together with logic values $0$ and $1$ are available as inputs.

(2)

Suppose that we design a Mealy-type synchronous sequential circuit that has a 1-bit input $x$ and a 1-bit output $y$. The circuit outputs $1$ when the value of the current input is different from the value at one clock earlier. It outputs $0$ when the value of the current input is the same as the value at one clock earlier. At the time the circuit starts operating, it is assumed that the value of the input at one clock earlier is $0$. For example, when 010110 is fed to the circuit, it produces 011101. Answer the following questions.

• (a) Derive a state transition diagram of the circuit.
• (b) Show the state transition table and the output table with the minimum number of states. Explain how you verified that the number of states is minimal.
• (c) We would like to implement the circuit with the minimum number of D flip-flops. Derive the excitation function(s) of D flip-flop(s) in a minimal sum-of-products form. Here, the initial value of a D flip-flop is $0$, and logic variables of the input and the output of a D flip-flop are $d$ and $q$, respectively. If multiple flip-flops are used, distinguish them by subscripts.
• (d) Derive the output $y$ in a minimal sum-of-products form.

(3)

Suppose that we design a Mealy-type synchronous sequential circuit that restores the input $x$ from the output $y$ of the sequential circuit in Question (2). Answer the following questions.

• (a) Derive a state transition diagram of the circuit.
• (b) Show the state transition table and the output table with the minimum number of states. Explain the state transition and the output sequence for the input sequence of 011101.

题目描述

回答全部问题。

1. 设计比较两个 2 位二进制整数 $A=(a_1a_0)_2$、$B=(b_1b_0)_2$ 的组合电路：当 $A>B$ 时输出 $x=1$，否则输出 $x=0$。
   1. 写出 $x$ 的最简与或式（最小乘积项之和）。
   2. 写出 $x$ 的最简或与式（最小和项之积）。
   3. 仅用最少数量的三输入 NAND 门实现 $x$。可直接使用 $a_1,a_0,b_1,b_0$ 及其反变量，以及逻辑常量 $0,1$。
2. 设计一个输入 $x$、输出 $y$ 均为 1 位的 Mealy 型同步时序电路。当当前输入与前一时钟输入不同，输出 $1$；相同则输出 $0$。启动时假定前一拍输入为 $0$。例如输入 010110 时输出 011101。
   1. 画状态转移图。
   2. 用最少状态写出状态转移表和输出表，并说明如何验证状态数最少。
   3. 用最少的 D 触发器实现，求各 D 触发器激励函数的最简与或式。D 输入与 Q 输出分别记为 $d,q$，多个触发器时用下标区分；初值为 $0$。
   4. 求输出 $y$ 的最简与或式。
3. 设计另一个 Mealy 型同步时序电路，从第 2 问电路的输出 $y$ 恢复原输入 $x$。
   1. 画状态转移图。
   2. 用最少状态写出状态转移表和输出表，并说明输入序列 011101 时的状态转移与输出序列。

Kai

(1)

(a)

Derive the corresponding K-map:

$$x = a_0\overline{b_1}\overline{b_0} + a_1\overline{b_1} + a_1 a_0\overline{b_0}$$

(b)

$$x = (a_1 + a_0)(a_1 + \overline{b_0})(a_1 + \overline{b_1})(a_0 + \overline{b_1})(\overline{b_1} + \overline{b_0})$$

(c)

(2)

(a)

State definition:

• S0: the previous input was 0
• S1: the previous input was 1

Initial state: S0

State transition diagram:

(b)

Input x	Current state	Next state	Output y
0	S0	S0	0
1	S0	S1	1
0	S1	S0	1
1	S1	S1	0

Minimum-state verification: For the same input, the outputs in S0 and S1 are different (for example, when x=0, the outputs are 0 and 1, respectively). Hence the two states are distinguishable and cannot be merged. Therefore, the number of states is minimal (2 states).

(c)

K-map for $d$:

Minimal sum-of-products:

$$d = x$$

(d)

K-map for $y$:

$$y = \overline{q}x + q\overline{x}$$

(Equivalently, $y = x \oplus q$.)

(3)

(a)

State definition:

• S0': the previous value of x was 0
• S1': the previous value of x was 1

Initial state: S0'

Input: $y$ Output: $x$

State transition diagram:

(b)

Input y	Current state	Next state	Output x
0	S0'	S0'	0
1	S0'	S1'	1
0	S1'	S1'	1
1	S1'	S0'	0

Minimum-state verification: For the same input, the outputs in S0' and S1' are different (for example, when y=0, the outputs are 0 and 1, respectively). Hence the two states are distinguishable and cannot be merged. Therefore, the number of states is minimal (2 states).

(c)

Initial state: S0'

Input y	Current state	Next state	Output x
0	S0'	S0'	0
1	S0'	S1'	1
1	S1'	S0'	0
1	S0'	S1'	1
0	S1'	S1'	1
1	S1'	S0'	0

Output sequence:

$$010110$$