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

标签：

• Kyoto-University
• Boolean-Function-Minimization
• Not-AND-and-Not-OR-Universal-Gates
• D-Flip-Flop
• Counter-Circuit
• Shift-Register

Author

SUN, 祭音Myyura (co-authored with ChatGPT 5.4 Thinking)

Description

大学公表の原題 Answer all the following questions. An overbar, ·, and + denote logical negation, logical and, and logical or, respectively.

(1)

Answer the following questions on the logic function $f$ defined below.

$$f = (a + b + c + d)\cdot(\bar{a} + b + \bar{c} + d)\cdot(\bar{a} + b + c)\cdot(a + \bar{b} + \bar{c})\cdot(a + \bar{c} + d)$$

(a) Give all minimum sum-of-products expressions of $f$.

(b) Give all minimum product-of-sums expressions of $f$.

(c) Derive a logic circuit that realizes $f$ with the minimum number of 3-input NOR gates only. Assume $a, b, c, d$ and their complements $\bar{a}, \bar{b}, \bar{c}, \bar{d}$ are available as inputs.

(d) Assume logic functions $g = b + d$ and $r = \bar{a}\cdot\bar{c}\cdot d$. Among all the logic functions of $h$ that satisfy

$$f = (g \cdot h) + r,$$

derive a minimum sum-of-products expression of a logic function that has the minimum number of product terms with the minimum number of literals in its minimum sum-of-products form.

(2)

We design a sequential circuit with a 1-bit input $u$ and a 3-bit output $(q_2, q_1, q_0)$ using three D flip-flops. The outputs of the D flip-flops are $q_2, q_1,$ and $q_0$, and they are the outputs of the sequential circuit as they are. When $u = 1$, this circuit operates as a binary down counter whose cycle is 8. Namely, $(q_2, q_1, q_0)$ change like

$$(1,1,1) \rightarrow (1,1,0) \rightarrow (1,0,1) \rightarrow \cdots \rightarrow (0,0,1) \rightarrow (0,0,0) \rightarrow (1,1,1).$$

When $u = 0$, the circuit operates as a shift register, where $q_0$ moves to $q_2$, $q_2$ to $q_1$, and $q_1$ to $q_0$. For example, $(q_2, q_1, q_0)$ change like

$$(1,0,0) \rightarrow (0,1,0) \rightarrow (0,0,1) \rightarrow (1,0,0).$$

Answer the following questions.

(a) Derive a state transition table.

(b) Let $d_2, d_1,$ and $d_0$ be the D input of the D flip-flops that output $q_2, q_1,$ and $q_0$, respectively. We derive $d_2, d_1,$ and $d_0$ as logic functions of $q_2, q_1, q_0,$ and $u$. Show the minimum sum-of-products expressions of $d_2, d_1,$ and $d_0$.

题目描述

回答全部问题。上划线、$\cdot$、$+$ 分别表示逻辑非、与、或。

1. 对逻辑函数

   $$f=(a+b+c+d)(\bar a+b+\bar c+d)(\bar a+b+c) (a+\bar b+\bar c)(a+\bar c+d)$$

   回答：

   1. 给出 $f$ 的所有最简与或式。
   2. 给出 $f$ 的所有最简或与式。
   3. 仅用三输入 NOR 门实现 $f$，使门数最少；可直接使用 $a,b,c,d$ 及其反变量。
   4. 设 $g=b+d$、$r=\bar a\bar c d$。在所有满足 $f=(g\cdot h)+r$ 的 $h$ 中，求一种最简与或式，使其乘积项数最少，并在此基础上文字数最少。

2. 用三个 D 触发器设计输入 $u$、输出 $(q_2,q_1,q_0)$ 的时序电路，三个 Q 输出即为电路输出。

   • 当 $u=1$ 时，电路为周期 8 的二进制减计数器：

     $$111\to110\to101\to\cdots\to001\to000\to111.$$

   • 当 $u=0$ 时，电路为循环移位寄存器，$q_0\to q_2$、$q_2\to q_1$、$q_1\to q_0$；例如 $100\to010\to001\to100$。

   回答：

   1. 写出状态转移表。
   2. 令 $d_2,d_1,d_0$ 分别为输出 $q_2,q_1,q_0$ 的 D 触发器输入。求它们作为 $q_2,q_1,q_0,u$ 的逻辑函数的最简与或式。

Kai

(1)

(a)

Derive the K-map of $\bar{f}$ and $f$:

$\bar{f} = \bar{b}\bar{d} + \bar{a}bc + a\bar{b}\bar{c}$	$f = b\bar{c} + ab + \bar{a}\bar{b}d + \bar{b}cd$

All minimum SOP expressions are

$$\begin{aligned} f&=b\bar c+ab+\bar a\bar b d+\bar bcd,\\ f&=b\bar c+ab+\bar a\bar b d+acd,\\ f&=b\bar c+ab+\bar a\bar c d+\bar bcd. \end{aligned}$$

(b)

Simplified POS expression for f:

$$f = (b + d)(a + \bar{b} + \bar{c})(\bar{a} + b + c)$$

(c)

From part (b), the minimum POS form is

$$f=(b+d)(a+\bar{b}+\bar{c})(\bar{a}+b+c)$$

Using a two-level NOR–NOR implementation, let

$$x_1=\overline{b+d}=\operatorname{NOR}(b,d,d)$$

$$x_2=\overline{a+\bar{b}+\bar{c}}=\operatorname{NOR}(a,\bar{b},\bar{c})$$

$$x_3=\overline{\bar{a}+b+c}=\operatorname{NOR}(\bar{a},b,c)$$

Then the output is

$$f=\overline{x_1+x_2+x_3}=\operatorname{NOR}(x_1,x_2,x_3)$$

Therefore, the logic circuit is realized by four 3-input NOR gates only.

For the lower bound, apply De Morgan duality: $F(a,b,c,d)=\overline{f(\bar a,\bar b,\bar c,\bar d)}$ turns every NOR into a NAND with the same gate count. Its 1-inputs $1111,1001,0110$ cannot be covered pairwise by one implicant, so $F$ requires at least three product terms. To justify minimality, note that no literal is true on every 1-input and no entire literal half-space has output 1. The last NAND for $F$ therefore cannot receive a primary literal. With at most three gates, its inputs must come from the preceding one or two gates. Parallel preceding gates give at most two product terms. If the first gate is $\overline T$ and the second is $\overline{\overline T P}$, feeding both into the last gate gives $T+P$, again at most two terms. Feeding only the second gives $\overline T P$: nonconstant $P$ forces a common literal on all 1-inputs, while constant $P$ gives the complement of one product, contrary to the half-space property. Thus three gates cannot suffice.

(d)

Derive the corresponding K-map:

Expression for h:

$$h = \bar{a}\bar{b} + b\bar{c} + ac$$

(2)

Since D flip-flops are used, the D inputs are exactly the next-state bits:

$$d_2=q_2^{+},\qquad d_1=q_1^{+},\qquad d_0=q_0^{+}$$

The state behavior is:

• When (u=1): 3-bit binary down counter
• When (u=0): circular shift register

$$(q_2,q_1,q_0)\to(q_0,q_2,q_1)$$

(a) State transition table

Present state $(q_2q_1q_0)$	$u=0$ next state	$u=1$ next state
000	000	111
001	100	000
010	001	001
011	101	010
100	010	011
101	110	100
110	011	101
111	111	110

So we obtain the truth table for $(d_2,d_1,d_0)$.

(b)

K-map for $d_2$

1-cells:

$$d_2=\Sigma m(1,2,6,10,11,13,14,15)$$

Rows: $q_2q_1=00,01,11,10$ Columns: $q_0u=00,01,11,10$

$q_2q_1 \backslash q_0u$	00	01	11	10
00	0	1	0	1
01	0	0	0	1
11	0	1	1	1
10	0	0	1	1

Grouping results:

• column $10$ $\rightarrow q_0\bar u$
• block $(11,10)\times (11,10) \rightarrow q_2q_0$
• pair on row $11$, columns $01,11$ $\rightarrow q_2q_1u$
• single cell $(00,01) \rightarrow \bar q_2\bar q_1\bar q_0u$

$$\boxed{d_2=q_0\bar u+q_2q_0+q_2q_1u+\bar q_2\bar q_1\bar q_0u}$$

K-map for $d_1$

1-cells:

$$d_1=\Sigma m(1,7,8,9,10,12,14,15)$$

Rows: $q_2q_1=00,01,11,10$ Columns: $q_0u=00,01,11,10$

$q_2q_1 \backslash q_0u$	00	01	11	10
00	0	1	0	0
01	0	0	1	0
11	1	0	1	1
10	1	1	0	1

Grouping results:

• block $(11,10)\times (00,10) \rightarrow q_2\bar u$
• pair in column $01$, rows $00,10 \rightarrow \bar q_1\bar q_0u$
• pair in column $11$, rows $01,11 \rightarrow q_1q_0u$

$$\boxed{d_1=q_2\bar u+\bar q_1\bar q_0u+q_1q_0u}$$

K-map for $d_0$

1-cells:

$$d_0=\Sigma m(1,4,5,6,9,12,13,14)$$

Rows: $q_2q_1=00,01,11,10$ Columns: $q_0u=00,01,11,10$

$q_2q_1 \backslash q_0u$	00	01	11	10
00	0	1	0	0
01	1	1	0	1
11	1	1	0	1
10	0	1	0	0

Grouping results:

• column $01 \rightarrow \bar q_0u$
• block $(01,11)\times (00,10) \rightarrow q_1\bar u$

$$\boxed{d_0=\bar q_0u+q_1\bar u}$$