京都大学 情報学研究科 通信情報システム専攻 2021年8月実施 専門基礎B [B-4] Author SUN , 祭音Myyura
Description 下記のすべての問に答えよ。x ‾ \overline{\phantom{x}} x ⋅ \cdot ⋅ + + + ⊕ \oplus ⊕
(1)
以下に示す論理関数 f f f
f = ( a + b ˉ + d ) ⋅ ( a + c ˉ + d ˉ ) ⋅ ( b ˉ + c ˉ + d ) ⋅ ( a ˉ + c ˉ + d ˉ ) ⋅ ( a ˉ + b + d ˉ ) f
=
(a+\bar{b}+d)\cdot(a+\bar{c}+\bar{d})\cdot(\bar{b}+\bar{c}+d)\cdot(\bar{a}+\bar{c}+\bar{d})\cdot(\bar{a}+b+\bar{d}) f = ( a + b ˉ + d ) ⋅ ( a + c ˉ + d ˉ ) ⋅ ( b ˉ + c ˉ + d ) ⋅ ( a ˉ + c ˉ + d ˉ ) ⋅ ( a ˉ + b + d ˉ ) (a) 論理関数 f f f
(b) 論理関数 f f f
(c) 3入力 NAND ゲートのみを用いて、論理関数 f f f a , b , c , d a,\ b,\ c,\ d a , b , c , d a ˉ , b ˉ , c ˉ , d ˉ \bar{a},\ \bar{b},\ \bar{c},\ \bar{d} a ˉ , b ˉ , c ˉ , d ˉ
(d) 論理関数
g = b ⋅ c ˉ + a ⋅ b ˉ , r = b ⋅ c ˉ ⋅ d g=b\cdot\bar{c}+a\cdot\bar{b},\qquad r=b\cdot\bar{c}\cdot d g = b ⋅ c ˉ + a ⋅ b ˉ , r = b ⋅ c ˉ ⋅ d を考える。
f = ( g ⊕ h ) + r f=(g\oplus h)+r f = ( g ⊕ h ) + r を満足するすべての論理関数 h h h
(2)
図(a)に示す入力 x x x y y y
(a) 状態遷移出力表を示せ。リセットされた状態を初期状態とし、初期状態から回路を動作させても到達できない状態は記載しないこと。
(b) 問(a)で求めた状態遷移出力表について、状態数が最小であるか答えよ。最小でない場合には、等価な状態の組を示せ。
题目描述
回答全部问题。x ‾ \overline{\phantom{x}} x ⋅ \cdot ⋅ + + + ⊕ \oplus ⊕
对逻辑函数
f = ( a + b ˉ + d ) ( a + c ˉ + d ˉ ) ( b ˉ + c ˉ + d ) ⋅ ( a ˉ + c ˉ + d ˉ ) ( a ˉ + b + d ˉ ) \begin{aligned}
f={}&(a+\bar b+d)(a+\bar c+\bar d)
(\bar b+\bar c+d)\\
&\cdot(\bar a+\bar c+\bar d)(\bar a+b+\bar d)
\end{aligned} f = ( a + b ˉ + d ) ( a + c ˉ + d ˉ ) ( b ˉ + c ˉ + d ) ⋅ ( a ˉ + c ˉ + d ˉ ) ( a ˉ + b + d ˉ ) 回答：
求 f f f
求 f f f
仅用三输入 NAND 门设计门数最少、输出为 f f f a , b , c , d a,b,c,d a , b , c , d
令
g = b c ˉ + a b ˉ g=b\bar c+a\bar b g = b c ˉ + a b ˉ r = b c ˉ d r=b\bar c d r = b c ˉ d f = ( g ⊕ h ) + r f=(g\oplus h)+r f = ( g ⊕ h ) + r h h h
对下图所示、输入为 x x x y y y
写出状态转移—输出表，以复位状态为初态，不列从初态不可达的状态。
判断所得状态数是否最少；若不是，指出等价状态对。
Kai (1)
(a)
Derive the corresponding K-map of f ˉ \bar{f} f ˉ f f f
f ˉ = c d + b c + a ˉ b d ˉ + a b ˉ d \bar{f} = cd + bc + \bar{a}b\bar{d} + a\bar{b}d f ˉ = c d + b c + a ˉ b d ˉ + a b ˉ d f = b ˉ d ˉ + a b c ˉ + a ˉ c ˉ d f = \bar{b}\bar d + ab\bar{c} + \bar{a}\bar{c}d f = b ˉ d ˉ + ab c ˉ + a ˉ c ˉ d
(b)
Simplified Boolean Expression for f f f
f = ( c ˉ + d ˉ ) ( b ˉ + c ˉ ) ( a + b ˉ + d ) ( a ˉ + b + d ˉ ) f=(\bar c+\bar d)(\bar b+\bar c)(a+\bar b+d)(\bar a+b+\bar d) f = ( c ˉ + d ˉ ) ( b ˉ + c ˉ ) ( a + b ˉ + d ) ( a ˉ + b + d ˉ ) (c)
NAND/Logic Expression for f f f
f = b ˉ d ˉ ‾ ⋅ a b c ˉ ‾ ⋅ a ˉ c ˉ d ‾ ‾ f=\overline{
\overline{\bar b\bar d}\cdot
\overline{ab\bar c}\cdot
\overline{\bar a\bar c d}} f = b ˉ d ˉ ⋅ ab c ˉ ⋅ a ˉ c ˉ d The three product terms are formed by three 3-input NAND gates (duplicate one input for b ˉ d ˉ \bar b\bar d b ˉ d ˉ
(d)
Derive the K-map of g , r , h g, r, h g , r , h
Equation for h h h
h = a ˉ c ˉ + a b ˉ d + a ˉ b ˉ d ˉ h = \bar{a}\bar{c} + a\bar{b}d + \bar{a}\bar{b}\bar{d} h = a ˉ c ˉ + a b ˉ d + a ˉ b ˉ d ˉ (2)
(a)
D 2 = a 1 a 0 + a ˉ 2 a 0 x + a 2 a 0 x ˉ D_2 = a_1 a_0 + \bar{a}_2 a_0 x + a_2 a_0 \bar{x} D 2 = a 1 a 0 + a ˉ 2 a 0 x + a 2 a 0 x ˉ D 1 = a 2 a ˉ 0 + a 1 a ˉ 0 x ˉ + a ˉ 2 a ˉ 1 a 0 x ˉ D_1 = a_2 \bar{a}_0 + a_1 \bar{a}_0 \bar{x} + \bar{a}_2 \bar{a}_1 a_0 \bar{x} D 1 = a 2 a ˉ 0 + a 1 a ˉ 0 x ˉ + a ˉ 2 a ˉ 1 a 0 x ˉ D 0 = a ˉ 0 x + a ˉ 2 x + a ˉ 2 a ˉ 1 a 0 D_0 = \bar{a}_0 x + \bar{a}_2 x + \bar{a}_2 \bar{a}_1 a_0 D 0 = a ˉ 0 x + a ˉ 2 x + a ˉ 2 a ˉ 1 a 0 y = x ˉ a ˉ 1 a ˉ 0 + a 2 a ˉ 0 y = \bar{x} \bar{a}_1 \bar{a}_0 + a_2 \bar{a}_0 y = x ˉ a ˉ 1 a ˉ 0 + a 2 a ˉ 0 State Transition Table
Current State (a 2 a 1 a 0 a_2a_1a_0 a 2 a 1 a 0 x = 0 x=0 x = 0 x = 1 x=1 x = 1 000 000 / 1 001 / 0 001 011 / 0 101 / 0 010 010 / 0 001 / 0 011 100 / 0 101 / 0 100 010 / 1 011 / 1 101 100 / 0 000 / 0
(b)
The six reachable states are pairwise distinguishable by successive partition refinement. Therefore, the state table is already minimal; there is no equivalent pair among the reachable states.
