電気通信大学 情報理工学研究科 情報・ネットワーク工学専攻 2021年8月実施 選択問題 計算機の基本原理

标签：

• University-of-Electro-Communications
• Boolean-Function-Minimization
• Combinatorial-Circuit
• Mealy-Sequence-Detector-State-Minimization
• D-Flip-Flop
• Sequential-Circuit

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

4 脚の椅子 A, B, C, D の着席を、それぞれ入力 $a,b,c,d\in\{0,1\}$ で表す。入力は各クロックで更新される。

• 回路 $M$ の出力 $u$ は、3 人以上の着席が 3 回連続したとき、かつそのときに限り 1 となる。
• 回路 $N$ の出力 $v$ は、3 人以上の着席が 3 回連続するか、4 人の着席が 2 回連続したとき、かつそのときに限り 1 となる。

問1

$M$ を組合せ回路 $M_1$ と順序回路 $M_2$ に分ける。$M_1$ は 3 人以上が同時に着席しているとき $s=1$ を出力し、$M_2$ は $s$ から $u$ を生成する。

1. $s$ の簡単な加法標準形を求めよ。
2. 状態数が最小の $M_2$ の状態遷移を示せ。
3. 状態割当てを行い、次状態と $u$ の論理式を求めよ。
4. D 型フリップフロップと AND, OR, NOT ゲートだけで $M$ を構成せよ。

問2

同様に、状態数が最小の $N$ の状態遷移を示し、状態割当て後の次状態と $v$ の加法標準形を求め、D 型フリップフロップと AND, OR, NOT ゲートだけで構成せよ。

题目描述

根据四把椅子的周期性占用信号，设计两个 Mealy 型同步时序电路：一个检测“至少三人连续三次”，另一个还要检测“四人连续两次”。要求给出最小状态机、状态编码、下一状态/输出逻辑及 D 触发器实现。

Kai

問1

(a)

3 人以上が着席する条件は

$$\boxed{s=abc+abd+acd+bcd}.$$

(b)

$S_0,S_1,S_2$ を、それぞれ「末尾の連続した $s=1$ が 0 回、1 回、2 回以上」とする。遷移表は次のとおりである。表中は「次状態 / 出力」である。

現状態	$s=0$	$s=1$
$S_0$	$S_0/0$	$S_1/0$
$S_1$	$S_0/0$	$S_2/0$
$S_2$	$S_0/0$	$S_2/1$

三つの状態は、それぞれ今後 3 回、2 回、1 回の $s=1$ で初めて出力 1 となるため互いに区別でき、状態数は最小である。

(c)

状態を $(q_1,q_0)$ で

$$S_0=00,\qquad S_1=01,\qquad S_2=11$$

と割り当てる。このとき

$$\boxed{q_0'=s,\qquad q_1'=sq_0,\qquad u=sq_1}.$$

(d)

$M_1$ で (a) の $s$ を生成し、2 個の D 型フリップフロップに

$$\boxed{D_0=s,\qquad D_1=sq_0}$$

を入力する。出力ゲートを $u=sq_1$ とすればよい。いずれも AND, OR, NOT だけで構成できる。

問2

4 人全員が着席している条件を

$$t=abcd$$

とおく。$t=1$ なら必ず $s=1$ である。次の 4 状態を用いる。

• $T_0$：末尾の $s=1$ がない。
• $T_3$：直前が 3 人着席で、連続長は 1。
• $T_4$：直前が 4 人着席で、連続長は 1。
• $T_2$：$s=1$ が 2 回以上連続している。

可能な入力 $(s,t)=00,10,11$ に対する遷移は次のとおりである。

現状態	$00$	$10$	$11$
$T_0$	$T_0/0$	$T_3/0$	$T_4/0$
$T_3$	$T_0/0$	$T_2/0$	$T_2/0$
$T_4$	$T_0/0$	$T_2/0$	$T_2/1$
$T_2$	$T_0/0$	$T_2/1$	$T_2/1$

$T_3$ と $T_4$ は次の入力 $11$ で区別でき、$T_0,T_2$ も必要な残り連続回数が異なるため、4 状態は最小である。

状態を

$$T_0=00,\qquad T_3=01,\qquad T_4=10,\qquad T_2=11$$

と割り当てると、加法標準形は

$$\boxed{ \begin{aligned} q_1'&=sq_1+sq_0+st,\\ q_0'&=sq_1+sq_0+s\bar t,\\ v&=q_1\bar q_0t+q_1q_0s. \end{aligned}}$$

したがって 2 個の D 型フリップフロップへ上式の $q_1',q_0'$ を入力し、同じく上式で $v$ を生成すれば、AND, OR, NOT ゲートだけで $N$ を構成できる。