東京工業大学 工学院 情報通信系 2016年8月実施 S4 逐次除算器と状態遷移

标签：

• TITech
• Finite-State-Machine-Minimization
• Boolean-Function-Minimization

Author

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

Description

非負整数を最上位ビットから入力し，定数 $N\ge2$ で割った商を最上位ビットから出力する。現状態を余り $A=R_k$，入力を $x$ とすると

$$B=2A+x,\qquad z=\lfloor B/N\rfloor,\qquad D=R_{k+1}=B\bmod N.$$

初期状態は $R_0=0$。論理式は最少の積項からなる NOT–AND–OR 形式で答える。

1. $N=5$，入力 $1011001$ の各時刻の $A,B,z,D$ と最終的な商 $Z_6$，余り $R_7$ を求めよ。
2. $N=3$ で $A=(a_1a_0)_2$, $B=(b_2b_1b_0)_2$ とする。$B$ の各ビットを求めよ。
3. $0\le B\le5$ に対し $C=B-3$ を3ビットの2の補数で表す。$B=6,7$ を don't care として $C$ の各ビットを簡単化せよ。$z=[C\ge0]$ と，$D=C'$（$C\ge0$）または $B'$（$C<0$）の選択式も示せ。ただし $C'=(c_1c_0)_2$, $B'=(b_1b_0)_2$。
4. $N=5$ の状態遷移表を作り，状態符号を $Q_0=000,Q_1=001,Q_2=011,Q_3=010,Q_4=100$ として次状態 $(d_2d_1d_0)$ と出力 $z$ を求めよ。

题目描述

分析从高位到低位进行常数除法的时序电路，填写运行表、化简组合逻辑，并按指定状态编码设计除以5的有限状态机。

Kai

1)

$k$	0	1	2	3	4	5	6
$x$	1	0	1	1	0	0	1
$A$	0	1	2	0	1	2	4
$B$	1	2	5	1	2	4	9
$z$	0	0	1	0	0	0	1
$D$	1	2	0	1	2	4	4

$89=5\cdot17+4$ なので $\boxed{Z_6=(0010001)_2=17,\ R_7=4}$。

2)

$B=2A+x$ は左シフトして $x$ を付ける操作なので

$$\boxed{b_2=a_1,\quad b_1=a_0,\quad b_0=x}.$$

3)a)

$B=0,1,2,3,4,5$ に対して $C$ は順に $101,110,111,000,001,010$。未使用入力を用いて簡単化すると

$$\boxed{\begin{aligned} c_2&=\bar b_2\bar b_0\vee\bar b_2\bar b_1,\\ c_1&=b_0\bar b_1\vee\bar b_0b_1,\\ c_0&=\bar b_0. \end{aligned}}$$

3)b)

符号ビットが $c_2$ だから

$$\boxed{z=\bar c_2,\quad d_1=b_1c_2\vee c_1\bar c_2,\quad d_0=b_0c_2\vee c_0\bar c_2}.$$

空欄（ア）～（オ）は $\bar c_2,c_2,\bar c_2,c_2,\bar c_2$。

4)a)

現状態	$x=0$ の次状態	$x=1$ の次状態	$x=0$ の出力	$x=1$ の出力
$Q_0$	$Q_0$	$Q_1$	0	0
$Q_1$	$Q_2$	$Q_3$	0	0
$Q_2$	$Q_4$	$Q_0$	0	1
$Q_3$	$Q_1$	$Q_2$	1	1
$Q_4$	$Q_3$	$Q_4$	1	1

4)b)

未使用符号 $101,110,111$ を don't care とすると

$$\boxed{\begin{aligned} d_2&=a_2x\vee a_0a_1\bar x,\\ d_1&=a_0\bar a_1\vee a_2\bar x\vee\bar a_0a_1x,\\ d_0&=\bar a_0a_1\vee a_0\bar a_1\bar x\vee\bar a_0\bar a_2x,\\ z&=a_2\vee a_1x\vee\bar a_0a_1. \end{aligned}}$$