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

Author

SUN, 祭音Myyura (assisted by 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 defined below.

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

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

(c) Derive a logic circuit that realizes with the minimum number of 3-input NOR gates only. Assume and their complements are available as inputs.

(d) Assume logic functions and . Among all the logic functions of that satisfy

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 and a 3-bit output using three D flip-flops. The outputs of the D flip-flops are and , and they are the outputs of the sequential circuit as they are. When , this circuit operates as a binary down counter whose cycle is 8. Namely, change like

When , the circuit operates as a shift register, where moves to , to , and to . For example, change like

Answer the following questions.

(a) Derive a state transition table.

(b) Let and be the D input of the D flip-flops that output and , respectively. We derive and as logic functions of and . Show the minimum sum-of-products expressions of and .

Kai

(1)

(a)

Derive the K-map of and :

(b)

Simplified POS expression for f:

(c)

From part (b), the minimum POS form is

Using a two-level NOR–NOR implementation, let

Then the output is

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

(d)

Derive the corresponding K-map:

Expression for h:

(2)

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

We use the corrected state behavior:

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

(a) State transition table

Present state	next state	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 .

(b)

K-map for

1-cells:

Rows: Columns:

	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
• block
• pair on row , columns
• single cell

K-map for

1-cells:

Rows: Columns:

	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
• pair in column , rows
• pair in column , rows

K-map for

1-cells:

Rows: Columns:

	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
• block