京都大学 情報学研究科 通信情報システム専攻 2024年8月実施 専門基礎A [A-2]
Author
SUN, 祭音Myyura (assisted by ChatGPT 5.4 Thinking)
Description
Answer all the following questions. Note that operators
(1)
Answer the following questions on the logic function
(a) Give all minimum sum-of-products expressions of
(b) Derive a logic circuit that realizes
(c) Give all minimum product-of-sums expressions of
(d) Assume logic functions
Among all the logic functions
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 sum-of-products form. If there is no logic function
(2)
We design a Moore-type synchronous sequential circuit that has a 1-bit input
Table 1
| clock cycle | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| input | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| output | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 |
(a) Derive a state transition diagram of this sequential circuit.
(b) Regarding the state transition diagram derived in Question (a), minimize the number of states and show the state transition table and the output table after state assignment. Explain how you verified that the number of states is minimal. Use the minimum number of D flip-flop(s) for state assignment and show the state assignment result.
(c) We implement a sequential circuit corresponding to the state transition table and the output table derived in Question (b). Derive the excitation function(s) of the D flip-flop(s) and the output function of
Kai
(1)
(a)
By simplifying
- a group of 4 cells with
and , giving the implicant , - a group of 4 cells with
and , giving the implicant , - a group of 2 cells with
, , and , giving the implicant .
Therefore, the minimum sum-of-products expression of
This minimum SOP expression is unique.
(b)
Using
a minimum 3-input-NAND realization is:
and
So the minimum number of 3-input NAND gates is 4.
(c)
To obtain the minimum product-of-sums form, group the 0-cells of the Karnaugh map:
- a group of 4 zeros with
and , giving the maxterm , - a group of 4 zeros with
and , giving the maxterm , - a group of 2 zeros with
, , and , giving the maxterm .
Hence, the minimum product-of-sums expression of
This minimum POS expression is unique.
(d)
We are given
and we need a logic function
First, consider the cases where
In those cases,
For the cases where
the value of
Thus, those cells can be treated as don't-care conditions in the Karnaugh map for
Using the determined values together with the don't-care cells, the minimum sum-of-products expression is
This expression has the minimum number of product terms, and among them, the minimum number of literals.
(2)
(a)
(b)
The minimized Moore machine has the following four states:
: : : :
The state transition table is:
| Current State ( | Next State for | Next State for | Output |
|---|---|---|---|
| 0 | |||
| 1 | |||
| 0 | |||
| 1 |
The number of states is minimal because no two states are equivalent:
and have the same output, but with input , they go to states with different outputs. and have the same output, but with input , they go to states with different outputs. - Any pair of states with different outputs are immediately distinguishable.
Therefore, all four states are necessary.
Since 4 states are required, the minimum number of D flip-flops is 2.
(c)
Two D flip-flops are required. Let their present-state outputs be
Using the state assignment
the excitation functions are
and
The output function is