論理設計学 問題と解答解説集

テキスト：Morris Mano “Digital Design”
対応ノート：第15回 順序回路の設計手順 | 順序回路 総復習

使い方

まず自分で解いてから、解答コールアウトを開いて答え合わせ。解説コールアウトで理解を深めよう。必要な回路図はMermaidで描いてある。

---

1章 — 2進数・基数変換

1.11 基数変換

以下の2進数を8進数と16進数に変換せよ。次に、8進数と16進数をそれぞれ10進数に変換し、等しいことを確認せよ。

$(a)101111010100.101_2(b)100001101111.010_2$

解答

(a) $101111010100.101_2$

8進数：3桁ずつ区切る（小数点を中心に）
$101111010100.101$
$=5724.5$
→ $5724.5_8$

16進数：4桁ずつ区切る
$101111010100.1010$
$=BD4.A$
→ $BD4.A_{16}$

10進数確認：

• $5724.5_8=5\times 8^3+7\times 8^2+2\times 8^1+4\times 8^0+5\times 8^{-1}=2560+448+16+4+0.625=3028.625_{10}$
• $BD4.A_{16}=11\times 16^2+13\times 16^1+4\times 16^0+10\times 16^{-1}=2816+208+4+0.625=3028.625_{10}$
• 一致！✓

(b) $100001101111.010_2$

8進数：$100001101111.010$
$=4157.2$
→ $4157.2_8$

16進数：$100001101111.0100$
$=86F.4$
→ $86F.4_{16}$

10進数確認：

• $4157.2_8=4\times 8^3+1\times 8^2+5\times 8^1+7\times 8^0+2\times 8^{-1}=2048+64+40+7+0.25=2159.25_{10}$
• $86F.4_{16}=8\times 16^2+6\times 16^1+15\times 16^0+4\times 16^{-1}=2048+96+15+0.25=2159.25_{10}$
• 一致！✓

解説

2進数→8進数：小数点を中心に3桁ずつ区切り、各グループを8進数1桁に変換。
2進数→16進数：同様に4桁ずつ区切り、各グループを16進数1桁に変換（10〜15はA〜F）。

覚え方：$8=2^3$, $16=2^4$ だから、3桁と4桁のグループ分けになる。

---

1.17 2進数の加算・減算・乗算

以下の2進数について加算、減算、乗算を行え。

$(a)1111と1001(b)1101001と110110(c)110010と11101$

解答

(a) $1111_2=15_{10},1001_2=9_{10}$

加算：

  1111
+ 1001
------
 11000  (= 24)

減算：

  1111
- 1001
------
  0110  (= 6)

乗算：

    1111
  × 1001
  -------
    1111
   0000
  0000
 1111
--------
10000111  (= 135)

(b) $1101001_2=105_{10},110110_2=54_{10}$

加算：

 1101001
+ 0110110
---------
10011111  (= 159)

減算：

 1101001
- 0110110
---------
 0110011  (= 51)

乗算：
$105\times 54=5670_{10}=1011000100110_2$（過程省略）

(c) $110010_2=50_{10},11101_2=29_{10}$

加算： $110010_2+11101_2=1001111_2$（$=79_{10}$）
減算： $110010_2-11101_2=10101_2$（$=21_{10}$）
乗算： $50\times 29=1450_{10}=10110101010_2$

解説

2進数の加算は桁上がりに注意。

• $1+1=0$ で桁上がり $1$
• $1+1+1=1$ で桁上がり $1$

減算は2の補数を使うと楽。乗算は筆算と同じく、掛ける数の各ビットが1のときだけ被乗数をシフトして加算。

---

1.21 基数の特定

以下は3桁の正の数の加算を示す。この結果が正しいとき、3桁の正の数の基数を答えよ。また、それぞれオーバフローが生じるか否かを答えよ。

$(a)654+013=000(b)024+043+013+033=223(c)024+043+013+033=201$

解答

(a) 基数 $r=8$。オーバフローあり。
$654_r+013_r=(6r^2+5r+4)+(0r^2+1r+3)=6r^2+6r+7$
結果 $000_r=0$ なので $6r^2+6r+7=0$ → 負の解は不適。
実際には $654_8+013_8=667_8$、結果が000なのでオーバフロー（3桁で表現できない）。

基数を求める：$654_r+013_r=667_r$ だが結果は $000_r$。これは $667_r$ が $r^3$ で割り切れる（オーバフローで下3桁が000）ことを意味する。
$6r^2+6r+7=r^3$ を解くと $r^3-6r^2-6r-7=0$。$r=7$: $343-294-42-7=0$ ✓ → 基数は7？でも7進数では digit 7は使えない（654の「6」はOK、でも7はdigitとして使えない）。
ちょっと違う。もう一度。

$654_r+013_r$ の和は $r^3$ 以上になっており、下3桁が000になっている。
つまり $6r^2+5r+4+r+3=6r^2+6r+7=k\cdot r^3$（$k$ は整数、オーバフローにより下3桁のみ表示→000）
$k=1$ とすると $6r^2+6r+7=r^3$ → $r^3-6r^2-6r-7=0$
$r=7$: $343-294-42-7=0$ ✓ → 基数は7、オーバフローあり。

確認：$654_7+013_7=(6\cdot 49+5\cdot 7+4)+(0+1\cdot 7+3)=(294+35+4)+(7+3)=343=7^3$ → 下3桁 $000_7$ ✓

(b) 基数 $r=5$。オーバフローなし。
$024_r+043_r+013_r+033_r=(2r+4)+(4r+3)+(r+3)+(3r+3)=10r+13$
結果 $223_r=2r^2+2r+3$
$10r+13=2r^2+2r+3$ → $2r^2-8r-10=0$ → $r^2-4r-5=0$ → $(r-5)(r+1)=0$ → $r=5$

確認：$024_5+043_5+013_5+033_5=(2\cdot 5+4)+(4\cdot 5+3)+(1\cdot 5+3)+(3\cdot 5+3)=14+23+8+18=63_{10}$
一方 $223_5=2\cdot 25+2\cdot 5+3=50+10+3=63_{10}$ ✓ オーバフローなし。

(c) 基数 $r=6$。オーバフローあり。
同じ式：$10r+13$
結果 $201_r=2r^2+1$
$10r+13=2r^2+1$ → $2r^2-10r-12=0$ → $r^2-5r-6=0$ → $(r-6)(r+1)=0$ → $r=6$

確認：$024_6+043_6+013_6+033_6=(2\cdot 6+4)+(4\cdot 6+3)+(1\cdot 6+3)+(3\cdot 6+3)=16+27+9+21=73_{10}$
一方 $201_6=2\cdot 36+1=73_{10}$ ✓ … あれ、オーバフローは？
いや、$201_6$ は3桁に収まっている。基数6で 73 は 201_6 だからオーバフローなし。
でも問題には「オーバフローが生じるか否か」とあるから、オーバフローなし。

あれ、(c) の計算：$2\cdot 6^2+1=72+1=73$ で合ってる。(b) の $223_5=2\cdot 25+2\cdot 5+3=50+10+3=63$ も合ってる。
どちらもオーバフローなし。

問題文に「オーバフローが生じるか否かを答えよ」とあるので、どちらも「生じない」。

解説

基数未知の加算問題は、次の手順で解く：

1. 左辺・右辺をそれぞれ基数$r$の多項式で表す
2. 等式を立てて$r$について解く
3. 桁あふれ（オーバフロー）は、結果の桁数が元の数の桁数を超えているかで判定

オーバフローの有無は、「本来の和の桁数が3桁を超えているか」で判定する。結果が3桁に収まっていればオーバフローなし。

---

2章 — 論理式の簡単化（定理の適用）

2.12 定理を1つ適用した簡単化

以下の論理式に定理を1つ適用して簡単化せよ。また、使用した定理を述べよ。

$(a)(X+Y^{\prime }Z)+(X+Y^{\prime }Z{)}^{\prime }$
$(b)[W+X^{\prime }(Y+Z)][W^{\prime }+X^{\prime }(Y+Z)]$
$(c)(V^{\prime }W+UX{)}^{\prime }(UX+Y+Z+V^{\prime }W)$
$(d)(U{V}^{\prime }+W^{\prime }X)(U{V}^{\prime }+W^{\prime }X+Y^{\prime }Z)$
$(e)(W^{\prime }+X)(Y+Z^{\prime })+(W^{\prime }+X{)}^{\prime }(Y+Z^{\prime })$
$(f)(V^{\prime }+U+W)[(W+X)+Y+U{Z}^{\prime }]+[(W+X)+U{Z}^{\prime }+Y]$

解答

(a) $1$ — 使用定理：T5 (A + A’ = 1)
$A=X+Y^{\prime }Z$ とおくと $A+A^{\prime }=1$

(b) $X^{\prime }(Y+Z)$ — 使用定理：T12’ $\{(A+B)(A^{\prime }+B)=B\}$
$A=W,B=X^{\prime }(Y+Z)$ とおくと $(W+B)(W^{\prime }+B)=B$

(c) $(V^{\prime }W+UX{)}^{\prime }(Y+Z)$ — 使用定理：T8 (分配則) + T5
$(V^{\prime }W+UX{)}^{\prime }[(V^{\prime }W+UX)+Y+Z]$
$=(V^{\prime }W+UX{)}^{\prime }(V^{\prime }W+UX)+(V^{\prime }W+UX{)}^{\prime }(Y+Z)$
$=0+(V^{\prime }W+UX{)}^{\prime }(Y+Z)$

(d) $U{V}^{\prime }+W^{\prime }X$ — 使用定理：T10 (吸収則 $A(A+B)=A$)
$A=U{V}^{\prime }+W^{\prime }X$ とおくと $A(A+Y^{\prime }Z)=A$

(e) $Y+Z^{\prime }$ — 使用定理：T5 (A + A’ = 1)
$(Y+Z^{\prime })[(W^{\prime }+X)+(W^{\prime }+X{)}^{\prime }]=(Y+Z^{\prime })\cdot 1=Y+Z^{\prime }$

(f) $W+X+Y+U{Z}^{\prime }$ — 使用定理：T2 (A + 1 = 1)
$A=W+X+Y+U{Z}^{\prime }$ とおくと $(V^{\prime }+U+W)A+A=A(V^{\prime }+U+W+1)=A\cdot 1=A$

解説

定理を1つだけ使って簡単化する問題。ポイントはパターン認識：

• $A+A^{\prime }$ → T5（補元則）で $1$
• $(A+B)(A^{\prime }+B)$ → T12’ で $B$
• $A\cdot A^{\prime }$ → T5 で $0$
• $A(A+B)$ → T10（吸収則）で $A$
• $A+AB$ → T10 で $A$
• $A\cdot 1$ → T1 で $A$

各定理の番号と内容を結びつけて覚えておくと、テストで「何を使ったか」聞かれたときに困らない。

---

3章 — 展開・排他的論理和

3.15 展開

下記の式を展開せよ（ヒント：式(3.3) $(X+Y)(X+Z)=X+YZ$ を活用する）。

$(a)(K^{\prime }+M^{\prime }+N)(K^{\prime }+M)(L+M^{\prime }+N^{\prime })(K^{\prime }+L+M)(M+N)$
$(b)(K^{\prime }+L^{\prime }+M^{\prime })(K+M+N^{\prime })(K+L)(K^{\prime }+N)(K^{\prime }+M+N)$

解答

(a) 展開結果：$K^{\prime }M+K^{\prime }L+M^{\prime }{N}^{\prime }+MN$

段階的に展開する：

1. $(K^{\prime }+M^{\prime }+N)(K^{\prime }+M)=K^{\prime }+(M^{\prime }+N)M=K^{\prime }+M^{\prime }N$（式3.3、$X=K^{\prime },Y=M^{\prime }+N,Z=M$）
2. $(K^{\prime }+M^{\prime }N)(L+M^{\prime }+N^{\prime })$ → 展開を続ける
   $=(K^{\prime }+M^{\prime }N)(L+M^{\prime }+N^{\prime })=K^{\prime }L+K^{\prime }{M}^{\prime }+K^{\prime }{N}^{\prime }+M^{\prime }NL+M^{\prime }N{M}^{\prime }+M^{\prime }N{N}^{\prime }$
   $=K^{\prime }L+K^{\prime }{M}^{\prime }+K^{\prime }{N}^{\prime }+L{M}^{\prime }N+0+0$
   $=K^{\prime }L+K^{\prime }(M^{\prime }+N^{\prime })+L{M}^{\prime }N$
3. さらに $(K^{\prime }+L+M)$ と $(M+N)$ を掛けると最終的に $K^{\prime }M+K^{\prime }L+M^{\prime }{N}^{\prime }+MN$ となる。

(b) 展開結果：$K^{\prime }{L}^{\prime }+LM+KN+M^{\prime }{N}^{\prime }$

解説

式(3.3) $(X+Y)(X+Z)=X+YZ$ は分配則の双対形。通常の分配則 $X(Y+Z)=XY+XZ$ と対になっている。

展開のコツ：

• まず隣接する2項に式(3.3)を適用して簡単化
• 繰り返し適用して項を減らしながら展開
• 相補性 $X\cdot X^{\prime }=0$ や $X+X^{\prime }=1$ で消える項に注目

---

3.16 排他的論理和の変形

式(3.6) $A\oplus B=A{B}^{\prime }+A^{\prime }B$ を用いて排他的論理和を積和形に変形した後、全体の論理式を和積形に変形せよ。

$(a)(KL\oplus M)+M^{\prime }{N}^{\prime }(b)M^{\prime }(K\oplus N^{\prime })+MN+K^{\prime }N$

解答

(a) $KL\oplus M$ を積和形に：
$KL\oplus M=(KL)M^{\prime }+(KL{)}^{\prime }M=KL{M}^{\prime }+(K^{\prime }+L^{\prime })M=KL{M}^{\prime }+K^{\prime }M+L^{\prime }M$

よって全体 = $KL{M}^{\prime }+K^{\prime }M+L^{\prime }M+M^{\prime }{N}^{\prime }$
これをK-mapで簡単化すると → $M^{\prime }+K^{\prime }M$

和積形：$(M^{\prime }+K^{\prime })(M^{\prime }+M)=M^{\prime }+K^{\prime }$ …ではなく、もう一度整理。

積和形簡単化：$KL{M}^{\prime }+K^{\prime }M+L^{\prime }M+M^{\prime }{N}^{\prime }$
K-map上でまとめると：$M^{\prime }+K^{\prime }M$
さらに変形：$M^{\prime }+K^{\prime }M=M^{\prime }+K^{\prime }$（T11: $A+A^{\prime }B=A+B$）
よって積和形 = $K^{\prime }+M^{\prime }$

和積形：$(K^{\prime }+M^{\prime })$ はすでに和積形（ORの形）。

(b) $M^{\prime }(K\oplus N^{\prime })=M^{\prime }(KN+K^{\prime }{N}^{\prime })=M^{\prime }KN+M^{\prime }{K}^{\prime }{N}^{\prime }$

全体：$M^{\prime }KN+M^{\prime }{K}^{\prime }{N}^{\prime }+MN+K^{\prime }N$
簡単化：K-mapを使うと… → $N+M^{\prime }{K}^{\prime }$

積和形：$N+M^{\prime }{K}^{\prime }$
和積形：$(M^{\prime }+N)(K^{\prime }+N)$

解説

排他的論理和（XOR）は「2入力が異なるとき1」：
$A\oplus B=A{B}^{\prime }+A^{\prime }B$

積和形（SOP）から和積形（POS）への変換は、ド・モルガンかK-mapを使う：

• SOPの最小項の補集合をとるとPOSになる
• K-map上で0をまとめてPOSを直接得ることもできる

---

4章 — 加算器・減算器

4.11 全減算器（Full Subtractor）

全減算器について以下の問いに答えよ。

(a) 表4.6から、$b_{i+1}$ と $d_i$ の論理式を求め、論理ゲートを用いた回路図を描きなさい。
(b) $d_i$ と全加算器の出力Sumの論理式(4.20)を比較して、それらの関係を述べよ。また、$b_{i+1}$ と全加算器の出力 $c_{out}$ の論理式(4.21)を比較して、それらの関係を述べよ。

解答

(a) 全減算器の真理表（表4.6）：

$x_i$	$y_i$	$b_i$（下位からの借り）	$d_i$（差）	$b_{i+1}$（上位への借り）
0	0	0	0	0
0	0	1	1	1
0	1	0	1	1
0	1	1	0	1
1	0	0	1	0
1	0	1	0	0
1	1	0	0	0
1	1	1	1	1

K-mapから論理式を導出：
$d_i=x_i\oplus y_i\oplus b_i$
$b_{i+1}=x_i^{\prime }{y}_i+x_i^{\prime }{b}_i+y_i{b}_i$

回路図：

(b) 全加算器との関係：

• $d_i$（減算の差）と $Sum$（加算の和）は全く同じ論理式：
  $d_i=x_i\oplus y_i\oplus b_i=Sum$
• $b_{i+1}$（減算の借り）と $c_{out}$（加算の桁上げ）は双対関係：
  $b_{i+1}=x_i^{\prime }{y}_i+x_i^{\prime }{b}_i+y_i{b}_i$
  $c_{out}=x_i{y}_i+x_i{c}_i+y_i{c}_i$
  → $b_{i+1}$ は $c_{out}$ の $x_i$ を $x_i^{\prime }$ に置き換えた形！

解説

全減算器は全加算器と非常に似ている。

• 差 $d_i$ は XOR 3つの連接で、全加算器の Sum と同じ
• 借り $b_{i+1}$ は $x_i$ を反転した全加算器の桁上げ $c_{out}$

つまり全加算器の入力 $x_i$ だけ反転させれば全減算器になる。これは $X-Y=X+(Yの2の補数)$ という性質とも対応している。

---

4.12 4ビット加算回路

下記の4ビットの2進数の計算を行う回路を、1ビットの全加算器モジュールとインバータを用いて図示せよ。ただし、4ビットの2進数は2の補数とする。

$(X_3{X}_2{X}_1{X}_0+Y_3{Y}_2{Y}_1{Y}_0)-Z_3{Z}_2{Z}_1{Z}_0=S_3{S}_2{S}_1{S}_0$

解答

方針： $A-B=A+(Bの2の補数)$ を利用する。
$(X+Y)-Z=(X+Y)+(Zの2の補数)$
Zの2の補数 = $Z^{\prime }+1$（全ビット反転して＋1）

構成：

1. Zの各ビットをNOTで反転 → $Z^{\prime }$
2. X+Y+Z’ を4個の全加算器で計算
3. 最下位FA0の桁上げ入力 $c_0=1$（これで $Z^{\prime }+1$ の+1を実現）
4. 結果 $S=X+Y+Z^{\prime }+1=X+Y-Z$

解説

2の補数表現では $A-B=A+(\text{2の補数}B)=A+B^{\prime }+1$。
この問題では $X+Y-Z$ なので、X+Yの結果と-Zを同時に処理する。

回路のポイント：

• Zの各ビットにインバータ（NOT）を接続
• 最下位FAの $c_0$（桁上げ入力）を1に固定 → $+1$ を実現
• $c_0=1$ が $Z^{\prime }+1$ の「+1」部分になる

この回路は加算器1個＋NOTアレイで減算もできる便利な構成。

---

5章 — カルノー図

5.14 K-map → 最小積和形（SOP）

下記の関数について、カルノー図を用いて最小の積和形の論理式を求めよ。

$(a)f_1(A,B,C)=m_1+m_2+m_5+m_7$
$(b)f_2(d,e,f)=\sum m(1,5,6,7)$
$(c)f_3(r,s,t)=r{s}^{\prime }+r^{\prime }{s}^{\prime }+s{t}^{\prime }$
$(d)f_4(a,b,c)=m_0+m_2+m_3+m_7$
$(e)f_5(n,p,q)=\sum m(1,3,4,5)$
$(f)f_6(x,y,z)=M_1\cdot M_7$

解答

(a) $f_1(A,B,C)=m_1+m_2+m_5+m_7$
K-map（3変数、AがMSB）：
$f_1=A^{\prime }{B}^{\prime }C+A^{\prime }B{C}^{\prime }+A{B}^{\prime }C+ABC=A^{\prime }{B}^{\prime }C+A{B}^{\prime }C+A^{\prime }B{C}^{\prime }+ABC$
まとめると：

• $A^{\prime }{B}^{\prime }C+A{B}^{\prime }C=B^{\prime }C$
• $A^{\prime }B{C}^{\prime }$ と $ABC$ は独立した最小項
  → $f_1=B^{\prime }C+A^{\prime }B{C}^{\prime }+ABC$（これ以上簡単化できず）
  さらに $A^{\prime }B{C}^{\prime }+ABC=A{C}^{\prime }$？いや $A^{\prime }B{C}^{\prime }+ABC=B{C}^{\prime }$？
  確認：$A^{\prime }B{C}^{\prime }+ABC=B(A^{\prime }{C}^{\prime }+AC)=B(A\oplus C{)}^{\prime }=B(A^{\prime }{C}^{\prime }+AC)$ → 簡単化できない。
  もっと整理：$f_1=B^{\prime }C+A^{\prime }B{C}^{\prime }+ABC$

(b) $f_2(d,e,f)=\sum m(1,5,6,7)$
最小項：$m_1=d^{\prime }{e}^{\prime }f,m_5=d{e}^{\prime }f,m_6=de{f}^{\prime },m_7=def$
K-mapでまとめる：

• $m_1+m_5=e^{\prime }f$（dが変化）
• $m_6+m_7=de$（fが変化）
  → $f_2=e^{\prime }f+de$

(c) $f_3(r,s,t)=r{s}^{\prime }+r^{\prime }{s}^{\prime }+s{t}^{\prime }$
K-map展開：
$r{s}^{\prime }=r{s}^{\prime }(t+t^{\prime })=r{s}^{\prime }t+r{s}^{\prime }{t}^{\prime }$
$r^{\prime }{s}^{\prime }=r^{\prime }{s}^{\prime }(t+t^{\prime })=r^{\prime }{s}^{\prime }t+r^{\prime }{s}^{\prime }{t}^{\prime }$
$s{t}^{\prime }=s{t}^{\prime }(r+r^{\prime })=rs{t}^{\prime }+r^{\prime }s{t}^{\prime }$

最小項：$r^{\prime }{s}^{\prime }{t}^{\prime }(0),r^{\prime }{s}^{\prime }t(1),r{s}^{\prime }{t}^{\prime }(4),r{s}^{\prime }t(5),r^{\prime }s{t}^{\prime }(2),rs{t}^{\prime }(6)$
→ $f_3=\sum m(0,1,2,4,5,6)$
K-mapでまとめると：$m_0+m_1+m_4+m_5=s^{\prime }$、$m_2+m_6=t^{\prime }$（ただし $s^{\prime }{t}^{\prime }$ は既にカバー済み）
→ $f_3=s^{\prime }+t^{\prime }$

(d) $f_4(a,b,c)=m_0+m_2+m_3+m_7$
$m_0=a^{\prime }{b}^{\prime }{c}^{\prime },m_2=a^{\prime }b{c}^{\prime },m_3=a^{\prime }bc,m_7=abc$
K-mapでまとめる：

• $m_0+m_2=a^{\prime }{c}^{\prime }$
• $m_3$ は単独
• $m_7$ は単独
  → $f_4=a^{\prime }{c}^{\prime }+a^{\prime }bc+abc$
  → さらに $a^{\prime }bc+abc=bc$ なので $f_4=a^{\prime }{c}^{\prime }+bc$

(e) $f_5(n,p,q)=\sum m(1,3,4,5)$
$m_1=n^{\prime }{p}^{\prime }q,m_3=n^{\prime }pq,m_4=n{p}^{\prime }{q}^{\prime },m_5=n{p}^{\prime }q$
K-mapでまとめる：

• $m_1+m_3=n^{\prime }q$
• $m_4+m_5=n{p}^{\prime }$
  → $f_5=n^{\prime }q+n{p}^{\prime }$

(f) $f_6(x,y,z)=M_1\cdot M_7$
$M_1$ は $m_1$ の補集合。つまり $M_1=(x^{\prime }{y}^{\prime }z{)}^{\prime }=x+y+z^{\prime }$
$M_7$ は $m_7$ の補集合。$M_7=(xyz{)}^{\prime }=x^{\prime }+y^{\prime }+z^{\prime }$
$f_6=(x+y+z^{\prime })(x^{\prime }+y^{\prime }+z^{\prime })$
これは和積形（POS）。積和形に変換：
$=(x+y+z^{\prime })(x^{\prime }+y^{\prime }+z^{\prime })=(x+y+z^{\prime })(x^{\prime }+y^{\prime }+z^{\prime })$
展開すると：$=(x+y)(x^{\prime }+y^{\prime })+z^{\prime }$
さらに：$=x{y}^{\prime }+x^{\prime }y+z^{\prime }$
→ $f_6=x\oplus y+z^{\prime }$

解説

K-mapのコツ：

• 隣接する1を長方形で囲む（サイズは $2^k$ 個）
• 大きな長方形ほど簡単な式になる
• 同じ1を複数の長方形で囲んでOK（冗長項は後で削除）

$f_3$ の $r{s}^{\prime }+r^{\prime }{s}^{\prime }+s{t}^{\prime }$ のように見た目が複雑でも、K-mapに書くと大半が1だとわかる。
$f_6$ の $M_1\cdot M_7$ は「最大項（Maxterm）」の積で与えられている。補集合を取れば最小項なので、
$f_6=\sum m(0,2,3,4,5,6)$ としてからK-mapを書くのが簡単。

---

5.15 K-map → 最小和積形（POS）

上記(a)〜(f)の関数について、カルノー図を用いて最小の和積形の論理式を求めよ。

解答

(a) $f_1=B^{\prime }C+A^{\prime }B{C}^{\prime }+ABC$
和積形：K-map上の0をまとめる
0のマス（$m_0,m_3,m_4,m_6$）をグループ化

• $m_0+m_4=A^{\prime }{B}^{\prime }{C}^{\prime }+A{B}^{\prime }{C}^{\prime }=B^{\prime }{C}^{\prime }$
• $m_3+m_{?}$ → 3変数K-mapで0の位置を確認

0のマス：$m_0(000),m_3(011),m_4(100),m_6(110)$
グループ：$m_0+m_4=B^{\prime }{C}^{\prime }$、$m_3+m_6=BC$？
検証：$m_3(011)+m_6(110)$ は隣接していない（2ビット異なる）→まとめられない
個別に取るしかない。

$f_1^{\prime }=A^{\prime }{B}^{\prime }{C}^{\prime }+A^{\prime }BC+A{B}^{\prime }{C}^{\prime }+AB{C}^{\prime }$
これを簡単化：$A^{\prime }{B}^{\prime }{C}^{\prime }+A{B}^{\prime }{C}^{\prime }=B^{\prime }{C}^{\prime }$
$A^{\prime }BC+AB{C}^{\prime }$ → これ以上簡単化できない
$f_1^{\prime }=B^{\prime }{C}^{\prime }+A^{\prime }BC+AB{C}^{\prime }$
→ ド・モルガン：$f_1=(B^{\prime }{C}^{\prime }+A^{\prime }BC+AB{C}^{\prime }{)}^{\prime }=(B+C)(A+B^{\prime }+C^{\prime })(A^{\prime }+B^{\prime }+C)$

(b) $f_2=e^{\prime }f+de$
和積形：$f_2$の補集合を求める
$f_2^{\prime }=\sum m(0,2,3,4)$ → K-mapでまとめる
$f_2^{\prime }=d^{\prime }{f}^{\prime }+e^{\prime }{f}^{\prime }$ ?
実際：$m_0(000)=d^{\prime }{e}^{\prime }{f}^{\prime },m_2(010)=d^{\prime }e{f}^{\prime },m_3(011)=d^{\prime }ef,m_4(100)=d{e}^{\prime }{f}^{\prime }$
K-map：$m_0+m_4=e^{\prime }{f}^{\prime }$、$m_2+m_3=d^{\prime }e$
$f_2^{\prime }=e^{\prime }{f}^{\prime }+d^{\prime }e$
∴ $f_2=(e+f)(d+e^{\prime })$

(c) $f_3=s^{\prime }+t^{\prime }$
もともとORの形 → そのまま和積形として成立
→ $f_3=s^{\prime }+t^{\prime }$（積和形と和積形が同じ）

(d) $f_4=a^{\prime }{c}^{\prime }+bc$
$f_4^{\prime }=\sum m(1,4,5,6)$？
$m_1(001)=a^{\prime }{b}^{\prime }c,m_4(100)=a{b}^{\prime }{c}^{\prime },m_5(101)=a{b}^{\prime }c,m_6(110)=ab{c}^{\prime }$
K-map：$m_1+m_5=b^{\prime }c$、$m_4$は単独、$m_6$は単独
→ $f_4^{\prime }=b^{\prime }c+a{b}^{\prime }{c}^{\prime }+ab{c}^{\prime }$

(e) $f_5=n^{\prime }q+n{p}^{\prime }$
$f_5^{\prime }=\sum m(0,2,6,7)$
$m_0(000)=n^{\prime }{p}^{\prime }{q}^{\prime },m_2(010)=n^{\prime }p{q}^{\prime },m_6(110)=np{q}^{\prime },m_7(111)=npq$
K-mapでまとめる：$m_0+m_2=n^{\prime }{q}^{\prime }$、$m_6+m_7=np$
→ $f_5^{\prime }=n^{\prime }{q}^{\prime }+np$
∴ $f_5=(n+q)(n^{\prime }+p^{\prime })$

(f) $f_6=x\oplus y+z^{\prime }=x{y}^{\prime }+x^{\prime }y+z^{\prime }$
これは積和形でも和積形でもこの形のまま。

解説

和積形（POS）を求めるには3つの方法がある：

1. K-mapで0をまとめる（0のグループ = $f^{\prime }$ の積和形、そこからド・モルガン）
2. $f$ の積和形から補集合を求める
3. 分配則で積和形→和積形に変形

AND-OR（SOP）はNAND-NANDに、OR-AND（POS）はNOR-NORに変換しやすい。

---

6章 — クワイン・マクラスキー法

6.9 Q-M法

クワイン・マクラスキー法を用いて、次の関数の最小の積和形を求めよ。

$f(a,b,c,d)=\sum m(2,3,4,7,9,11,12,13,14)+\sum d(1,10,15)$

解答

Step 1：最小項を1の数でグループ分け

グループ	最小項	2進数
1（1個の1）	2	0010
	4	0100
2（2個の1）	3	0011
	9	1001
	12	1100
3（3個の1）	7	0111
	11	1011
	13	1101
	14	1110
4（4個の1）	15(dc)	1111
1（1個の1）	1(dc)	0001
2（2個の1）	10(dc)	1010

Step 2：ペアリング（1回目）
隣接グループ間で1ビット異なるペアを結合：

結合	元の項	結果	備考
2,3	0010, 0011	001- (a’b’c) ✓
2,10	0010, 1010	-010 (b’cd’) ✓
3,7	0011, 0111	0-11 (a’bd) ✓
3,11	0011, 1011	-011 (b’cd) ✓
4,12	0100, 1100	-100 (ac’d’) ✓
9,11	1001, 1011	10-1 (ab’d) ✓
9,13	1001, 1101	1-01 (ac’d) ✓
12,13	1100, 1101	110- (abc’) ✓
12,14	1100, 1110	11-0 (abd’) ✓
7,15	0111, 1111	-111 (bcd) ✓
11,10	1011, 1010	101- (ab’c) ✓
13,15	1101, 1111	11-1 (abd) ✓
14,15	1110, 1111	111- (abc) ✓
1,3	0001, 0011	00-1 (a’b’c) ✓
1,9	0001, 1001	-001 (b’c’d) ✓

Step 3：ペアリング（2回目）
上記の結果からさらに1ビット異なるペアを結合：

• 001- + 101- → -01- (b’c) ✓
• 0-11 + 1-11 → —11 (cd) ✓
• -010 + -110 → -01- ？いや -0-0 (b’d’)？ 検証…
• -100 + -110 → —10 → 異なる
• 110- + 111- → 11— (ab) ✓
• 10-1 + 11-1 → 1—1 (ad) ✓

など。最終的に以下の主項が得られる：

• P1: $b^{\prime }c$（-01-：項2,3,10,11をカバー）
• P2: $cd$（—11：項3,7,11,15をカバー）
• P3: $ab$（11—：項12,13,14,15をカバー）
• P4: $ad$（1—1：項9,11,13,15をカバー）
• P5: $b^{\prime }{d}^{\prime }$（-0-0：項2,4,10をカバー）
• P6: $a{c}^{\prime }{d}^{\prime }$（-100：項4,12をカバー）
• P7: $a^{\prime }{b}^{\prime }c$（00-1：項1,3をカバー）

Step 4：最小被覆を選ぶ

主項	2	3	4	7	9	11	12	13	14
P1: $b^{\prime }c$	✓	✓				✓
P2: $cd$		✓		✓		✓
P3: $ab$							✓	✓	✓
P4: $ad$					✓	✓		✓
P5: $b^{\prime }{d}^{\prime }$	✓		✓
P6: $a{c}^{\prime }{d}^{\prime }$			✓				✓
P7: $a^{\prime }{b}^{\prime }c$		✓

必須主項：P3（12,13,14を唯一カバー）、P5（2を唯一カバー）

残った3,4,7,9,11をカバーする最小の組合せ：

• P1($b^{\prime }c$) は 3,11 をカバー
• P4($ad$) は 9,11 をカバー
• P2($cd$) は 3,7,11 をカバー
• P6($a{c}^{\prime }{d}^{\prime }$) は 4 をカバー

P2($cd$) で 3,7,11 をカバーし、P6($a{c}^{\prime }{d}^{\prime }$) で4をカバー。P5で2をカバー、P3で12,13,14をカバー。

よって $f={\mathbf{b}}^{\prime }\mathbf{c}+\mathbf{cd}+\mathbf{ab}+{\mathbf{b}}^{\prime }{\mathbf{d}}^{\prime }$ または $f={\mathbf{b}}^{\prime }\mathbf{c}+\mathbf{cd}+\mathbf{ab}+\mathbf{a}{\mathbf{c}}^{\prime }{\mathbf{d}}^{\prime }$
→ 最小形は $f=b^{\prime }c+cd+ab+b^{\prime }{d}^{\prime }$

解説

Q-M法の流れ：

1. 最小項を1の個数でグループ分け
2. 隣接グループ間で1ビットだけ異なるものを統合（ダッシュで表現）
3. 統合できなかった項が主項
4. 被覆表で必須主項を特定、残りを最小被覆

dc（Don’t Care）項はペアリングのときは使えるが、被覆表ではカバーしなくてよい（点で表現）。

K-mapが3変数・4変数までしか実用的でないのに対し、Q-M法はアルゴリズムとして機械的に実行でき、多変数でも使えるのが強み。

---

7章 — 多段ゲート回路

7.1 2段・3段ゲート回路

下記の式について(a)と(b)に答えよ。

$f(a,b,c,d)=m_4+m_6+m_7+m_8+m_9+m_{10}$

(a) 最小の2段OR-ANDゲート回路の論理式を求めよ。
(b) 最小の3段OR-AND-ORゲート回路の論理式を求めよ。

解答

最小項を確認：$m_4=0100,m_6=0110,m_7=0111,m_8=1000,m_9=1001,m_{10}=1010$

K-mapで1をプロット：

       cd
       00  01  11  10
ab 00   0   0   0   0
   01   1   0   1   1  ← m4,m6,m7
   11   0   0   0   0
   10   1   1   0   1  ← m8,m9,m10

(a) 2段OR-AND回路（積和形SOP）
K-mapで1をまとめる：

• $m_4+m_6=a^{\prime }b{c}^{\prime }{d}^{\prime }+a^{\prime }bc{d}^{\prime }=a^{\prime }b{d}^{\prime }$
• $m_6+m_7=a^{\prime }bc{d}^{\prime }+a^{\prime }bcd=a^{\prime }bc$
• $m_8+m_9=a{b}^{\prime }{c}^{\prime }{d}^{\prime }+a{b}^{\prime }{c}^{\prime }d=a{b}^{\prime }{c}^{\prime }$
• $m_8+m_{10}=a{b}^{\prime }{c}^{\prime }{d}^{\prime }+a{b}^{\prime }c{d}^{\prime }=a{b}^{\prime }{d}^{\prime }$
• $m_9+m_{10}$？$m_9(1001),m_{10}(1010)$ は隣接していない

まとめ方によって複数の解がある。最小のもの：
$f=a^{\prime }b{d}^{\prime }+a^{\prime }bc+a{b}^{\prime }{c}^{\prime }+a{b}^{\prime }{d}^{\prime }$
または $f=a^{\prime }b{d}^{\prime }+a^{\prime }bc+a{b}^{\prime }{c}^{\prime }+a{b}^{\prime }{d}^{\prime }$

さらに簡単化できないか？
$a^{\prime }b{d}^{\prime }+a^{\prime }bc=a^{\prime }b(d^{\prime }+c)=a^{\prime }b(c+d^{\prime })$
$a{b}^{\prime }{c}^{\prime }+a{b}^{\prime }{d}^{\prime }=a{b}^{\prime }(c^{\prime }+d^{\prime })=a{b}^{\prime }(cd{)}^{\prime }$
→ SOPとしてはこれ以上簡単化できない。

(b) 3段OR-AND-OR回路
OR-AND-OR回路は、SOPを因数分解してAND-ORの前にORの段を追加する。
$f$ はもともと6個の最小項だが、次のように因数分解できる：

$f=a^{\prime }b{d}^{\prime }+a^{\prime }bc+a{b}^{\prime }{c}^{\prime }+a{b}^{\prime }{d}^{\prime }$
$=a^{\prime }b(d^{\prime }+c)+a{b}^{\prime }(c^{\prime }+d^{\prime })$
$=a^{\prime }b(c+d^{\prime }{)}^{\prime }+a{b}^{\prime }(cd{)}^{\prime }$ … ここからさらに…

実際には $f$ の補集合をOR-ANDで表す：
$f$ の0のマス（$m_0,m_1,m_2,m_3,m_5,m_{11},m_{12},m_{13},m_{14},m_{15}$）をK-mapでまとめて、ド・モルガンで全体を反転する。

でも問題は「最小の3段OR-AND-OR」が欲しいので、因数分解された形を示す：
$f=a^{\prime }b(c+d^{\prime })+a{b}^{\prime }(c^{\prime }+d^{\prime })$

3段OR-AND-OR：

段1（OR）：c + d'      と  c' + d'
段2（AND）：a'b(c+d')  と  ab'(c'+d')
段3（OR）：上記2つのOR

解説

2段回路（SOP）：AND-OR形態 → K-mapで1をまとめるだけ
3段回路（OR-AND-OR または AND-OR-AND）：因数分解して中間段を作る

3段回路にするメリット：同じゲート型でも配線のファンインを減らせることがある。
2段AND-OR：ANDゲートの入力数が多いと、ゲート遅延が増大する
3段：中間でORを取ることでANDゲートの入力を減らせる（ただし段数が増えるトレードオフ）

---

8章 — ハザード

8.7 静的0ハザード

下記の関数が静的0ハザードをもつか答えよ。静的0ハザードが発生する場合の入力 $(a,b,c,d)$ の変化をすべて列挙せよ。

$f(a,b,c,d)=(a+d^{\prime })(b^{\prime }+c+d)(a^{\prime }+c^{\prime }+d^{\prime })(b^{\prime }+c^{\prime }+d)$

ヒント：図8.10(b)のようなカルノー図を描き、隣接する2つの0で同一ループに含まれない組合せをすべて探す。

解答

静的0ハザードは、入力変化時に出力が0→1→0と一瞬1に変動する現象。

手順：

1. 関数をK-mapにプロット（和積形POSなので、0に注目）
2. 各項で0になる領域を確認
3. 隣接する0のペアで、同一の積項でカバーされていないものを探す

$f=(a+d^{\prime })(b^{\prime }+c+d)(a^{\prime }+c^{\prime }+d^{\prime })(b^{\prime }+c^{\prime }+d)$

項	0になる条件
$a+d^{\prime }$	$a=0$ かつ $d=1$
$b^{\prime }+c+d$	$b=1$ かつ $c=0$ かつ $d=0$
$a^{\prime }+c^{\prime }+d^{\prime }$	$a=1$ かつ $c=1$ かつ $d=1$
$b^{\prime }+c^{\prime }+d$	$b=1$ かつ $c=1$ かつ $d=0$

K-map上で0の領域：

• $a=0,d=1$ のエリア（cd=01,11列 × ab=00,01,10,11行のうちa=0の行=00,01）
  • ab=00, cd=01（$m_1$）と cd=11（$m_3$）
  • ab=01, cd=01（$m_5$）と cd=11（$m_7$）
• $b=1,c=0,d=0$ → abc=010 または 110、d=0
  • ab=01, cd=00（$m_4$）と ab=11, cd=00（$m_{12}$）
• $a=1,c=1,d=1$ → ab=10または11、cd=11
  • ab=10, cd=11（$m_{11}$）と ab=11, cd=11（$m_{15}$）
• $b=1,c=1,d=0$ → ab=01または11、cd=10
  • ab=01, cd=10（$m_6$）と ab=11, cd=10（$m_{14}$）

静的0ハザードが発生する隣接0ペア：

• $m_1(0001)$ と $m_3(0011)$：$a$の変化 → 両方とも第1項$a+d^{\prime }$でカバー → ハザードなし
• $m_4(0100)$ と $m_{12}(1100)$：$a$の変化 → $b^{\prime }+c+d$でカバー（$b=1,c=0,d=0$）？$m_4$は$b=1$だが$m_{12}$も$b=1$ → 両方とも第2項でカバー → ハザードなし
• $m_5(0101)$ と $m_7(0111)$：$c$の変化 → $m_5$は第1項($a+d^{\prime }$)でカバー（a=0,d=1）、$m_7$も第1項でカバー → ハザードなし
• $m_6(0110)$ と $m_{14}(1110)$：$a$の変化 → $m_6$は第4項($b^{\prime }+c^{\prime }+d$: b=1,c=1,d=0)でカバー、$m_{14}$も第4項でカバー → ハザードなし
• $m_{11}(1011)$ と $m_{15}(1111)$：$a$の変化 → $m_{11}$は第3項($a^{\prime }+c^{\prime }+d^{\prime }$: a=1,c=1,d=1)でカバー、$m_{15}$も第3項 → ハザードなし

すべての隣接0ペアが同一の項でカバーされている。よって 静的0ハザードは発生しない。

解説

静的ハザードの判定手順：

1. SOP（積和形）の回路 → 静的1ハザードをチェック（隣接する1のペアで同一積項に含まれないもの）
2. POS（和積形）の回路 → 静的0ハザードをチェック（隣接する0のペアで同一和項に含まれないもの）

ハザードを防ぐには：

• 冗長項（SOPなら $X+X^{\prime }$ に相当する項）を追加する
• または出力にFFを入れて、ハザードが収まった後の値を読む

---

9章 — マルチプレクサ（MUX）

9.17 MUXの実装

アクティブハイ出力／アクティブハイ・イネーブルの2:1 MUX 2個とインバータ、ORゲートを用いて、下記の回路を実装したい。

(a) アクティブハイ出力／イネーブルなしの 4:1 MUX を図示せよ。
(b) アクティブロー出力／イネーブルなしの 4:1 MUX を図示せよ。

解答

(a) アクティブハイ出力／イネーブルなし 4:1 MUX

2:1 MUX 2個で4:1 MUXを作る。2:1 MUXは選択線Sで入力を切り替える：$Y=S\cdot D_1+S^{\prime }\cdot D_0$

構成：

• MUX0 が D₀, D₁ を S₀ で選択
• MUX1 が D₂, D₃ を S₀ で選択
• S₁ をインバータで反転 → MUX0 のイネーブル（EN）に
• S₁ をそのまま MUX1 のイネーブルに
• OR ゲートで両 MUX の出力を合体 → Y

これで $Y=S_1^{\prime }\cdot (S_0^{\prime }{D}_0+S_0{D}_1)+S_1\cdot (S_0^{\prime }{D}_2+S_0{D}_3)$ が実現できる。
2:1 MUXにイネーブル機能があれば、第3のMUXは不要。

2:1 MUXにイネーブル機能がある場合：

• MUX0のイネーブル = S1’（インバータで反転）
• MUX1のイネーブル = S1
• ORゲートで両MUXの出力を合体

(b) アクティブロー出力／イネーブルなし 4:1 MUX
アクティブロー出力は $Y^{\prime }$（出力の否定）を出す。つまり出力段にインバータが付く。

構成は(a)と同じだが、最終出力にインバータを追加するか、MUXの出力段がもともとアクティブローであればそのまま使う。

• MUX0, MUX1の出力をアクティブローで取得
• ORゲートはNANDに置き換え（アクティブロー同士のOR=NAND）
• または単純に(a)の出力YをNOTで反転

解説

MUXの拡張の基本：

• $2^n:1$ MUXは $2^{n-1}:1$ MUX 2個 + 最終選択段 で構成
• 選択線が増えるごとに2倍のMUXが必要

アクティブハイ vs アクティブロー：

• アクティブハイ：制御信号=1で有効、出力は正論理
• アクティブロー：制御信号=0で有効、出力は負論理

2:1 MUXの真理表：

S	出力（アクティブハイ）	出力（アクティブロー）
0	D0	D0’
1	D1	D1’

---

10章 — リセット優先フリップフロップ

10章の問題

リセット優先フリップフロップは入力 $S=R=1$ が許可され、このときにフリップフロップがリセットされることを除いてS-Rフリップフロップと同様に動作する。

(a) リセット優先フリップフロップの真理値表（遷移表）を示せ。
(b) カルノー図を用いてリセット優先フリップフロップの特性方程式を求めよ。
(c) S-Rフリップフロップに何らかの回路を追加することで、リセット優先フリップフロップ回路を図示せよ。（ヒント：教科書p.90の式(10.5)と(b)で求めた式を比較して考えると良い）

解答

(a) 真理値表（遷移表）

S-R FFの特性（通常）：$S=R=1$ は禁止入力
リセット優先FF：$S=R=1$ のとき $Q^{+}=0$（リセット優先）

S	R	Q	Q⁺	動作
0	0	0	0	保持
0	0	1	1	保持
0	1	0	0	リセット
0	1	1	0	リセット
1	0	0	1	セット
1	0	1	1	セット
1	1	0	0	リセット（S-R FFでは禁止）
1	1	1	0	リセット（S=R=1でもリセット優先）

(b) 特性方程式

K-map（ $Q^{+}$ を S, R, Q の関数として）：

       RQ
      00  01  11  10
S 0    0   1   0   0
  1    1   1   0   0

$Q^{+}=S+R^{\prime }Q$

通常のS-R FFの特性式 $Q^{+}=S+R^{\prime }Q$（$S\cdot R=0$ が条件）と全く同じ式！
違いは $S=R=1$ のとき、この式は $Q^{+}=1+0\cdot Q=1$ となって矛盾する…？

いや、$S=R=1$ を代入すると：$Q^{+}=1+0\cdot Q=1$ → セットになる。
でもリセット優先は $Q^{+}=0$ のはず。おかしい。

K-mapを書き直し：

       RQ
      00  01  11  10
S 0    0   1   0   0
  1    1   1   0   ? ← S=1,R=1,Q=1 → Q⁺=0, S=1,R=1,Q=0 → Q⁺=0

正しくは：

       RQ
      00  01  11  10
S 0    0   1   0   0
  1    1   1   0   0

S=1,R=1の列（RQ=11,10）はどちらも Q⁺=0。

K-mapでまとめる：

• $S=1,R=0$ の列 = 1
• $S=0,R=0$ の列 = Q
• $S=0,R=1$ の列 = 0
• $S=1,R=1$ の列 = 0

→ $Q^{+}=S\cdot R^{\prime }+R^{\prime }\cdot Q=R^{\prime }(S+Q)$
または $Q^{+}=S+R^{\prime }Q$ は間違いで、正しくは $Q^{+}=S\cdot R^{\prime }+R^{\prime }\cdot Q=R^{\prime }(S+Q)$

確認：$S=1,R=1$ → $Q^{+}=1^{\prime }\cdot (1+Q)=0\cdot (1+Q)=0$ ✓（リセット優先！）

(c) S-R FF + 追加回路

ヒント「式(10.5)と比較」：
S-R FFの式(10.5)：$Q^{+}=S+R^{\prime }Q$（ただし $S\cdot R=0$ の条件付き）
リセット優先の式：$Q^{+}=R^{\prime }(S+Q)$

両者の関係：リセット優先FFは、S-R FFのS入力を $S\cdot R^{\prime }$（SとR’のAND）に置き換えたもの。

構成：

1. RをNOTで反転 → R’
2. SとR’をAND → 新しいセット入力 $S^{\ast }=S\cdot R^{\prime }$
3. $S^{\ast }$ と R を S-R FF に入力

これで $S=R=1$ のとき $S^{\ast }=1\cdot 1^{\prime }=0$、$R=1$ → リセット優先が実現する。

解説

S-R FFとリセット優先FFの違い：

入力 (S,R)	S-R FF	リセット優先FF
00	保持	保持
01	リセット	リセット
10	セット	セット
11	禁止	リセット

リセット優先の特性式 $Q^{+}=R^{\prime }(S+Q)$ は「R=1なら強制リセット、R=0ならSでセットか保持」の意味。
実装はS-R FFのS入力の前に $S\cdot R^{\prime }$ のANDを追加するだけでOK。

---

カウンタ設計（J-K FF）

下記の次状態表を持つカウンタをJ-Kフリップフロップ3個で設計する。各J-Kフリップフロップの入力 $J_C,K_C,J_B,K_B,J_A,K_A$ の論理式を求めよ。また、初期値 $CBA=000$ のとき、次状態のカウンタ値を答えよ。

C B A	C⁺ B⁺ A⁺
0 0 0	0 0 1
0 0 1	0 1 0
0 1 0	0 1 1
0 1 1	1 0 0
1 0 0	1 0 1
1 0 1	1 1 0
1 1 0	1 1 1
1 1 1	0 0 0

解答

この表は**3ビット2進カウンタ（0→1→2→…→7→0）**の動作そのもの。

遷移表から各FFの $Q^{+}$ を抽出：

C B A	C⁺	B⁺	A⁺
0 0 0	0	0	1
0 0 1	0	1	0
0 1 0	0	1	1
0 1 1	1	0	0
1 0 0	1	0	1
1 0 1	1	1	0
1 1 0	1	1	1
1 1 1	0	0	0

J-K FFの入力方程式を求める：

J-K FFの特性：$Q^{+}=J{Q}^{\prime }+K^{\prime }Q$
つまり：

• $Q^{+}=1$ のとき：$J=1$（$K$は任意）
• $Q^{+}=0$ のとき：$K=1$（$J$は任意）
• $Q^{+}=Q$ のとき：$J=K=0$（保持）
• $Q^{+}=Q^{\prime }$ のとき：$J=K=1$（トグル）

A ($J_A,K_A$) のK-map：

C B	A=0→A⁺	A=1→A⁺	$J_A$	$K_A$
0 0	1	0	1	1
0 1	1	0	1	1
1 0	1	0	1	1
1 1	0	1	1	1

$J_A=K_A=1$（常にトグル）

B ($J_B,K_B$) のK-map：

C A	B=0→B⁺	B=1→B⁺	$J_B$	$K_B$
0 0	0	1	0	0
0 1	1	0	1	1
1 0	0	1	0	0
1 1	1	0	1	1

$J_B=K_B=A$（A=1のときトグル）

C ($J_C,K_C$) のK-map：

B A	C=0→C⁺	C=1→C⁺	$J_C$	$K_C$
0 0	0	1	0	0
0 1	0	1	0	0
1 0	1	0	1	1
1 1	1	0	1	1

$J_C=K_C=B\cdot A$（B=A=1のときトグル）

論理式まとめ：
$J_A=K_A=1$
$J_B=K_B=A$
$J_C=K_C=B\cdot A$

初期値 $CBA=000$ からのカウント：
$000\to 001\to 010\to 011\to 100\to 101\to 110\to 111\to 000\to \cdots$

解説

J-K FFの設計では「$Q^{+}$ を $Q$ と比較してJとKを決める」が基本：

Q → Q⁺	J	K	動作
0 → 0	0	d	保持またはリセット
0 → 1	1	d	セット
1 → 0	d	1	リセット
1 → 1	d	0	保持またはセット

d（don’t care）はK-mapのマージに活用できる。

このカウンタのパターン：

• A（LSB）→ 毎クロック反転（$J_A=K_A=1$=トグルモード）
• B → A=1のときだけ反転
• C（MSB）→ A=B=1のときだけ反転

これはリップルカウンタではなく同期式カウンタ（全ビットが同時に変化）。

---

13章 — 順序回路の解析

13.4 順序回路（遷移表・状態図・タイミング図）

教科書の図12.17の回路（CLKの立下りエッジ駆動）で、入力が X のみ、Dフリップフロップが3個の回路を考える。また、組合せ回路の論理式が以下の通りとする。

$D_1=Q_2{Q}_3^{\prime },D_2=Q_3,D_3=Q_2^{\prime }+X,Z=X{Q}_2^{\prime }+X^{\prime }{Q}_2$

(a) この回路の遷移表と状態図を示せ。
(b) 入力 $X=01011$ に対する X, CLK, Q1, Q2, Q3, Z のタイミング図を図示せよ。ただし、X は CLK の立下りエッジと立上りエッジの中間で変化するものとする。
(c) このタイミング図で誤った出力が出る場合、誤った出力が出ないようにするにはクロックに対して入力がどこで変化すればよいか？ただし、フリップフロップのホールド時間はゼロとする。

解答

(a) 遷移表

D-FFなので $Q^{+}=D$

Q1 Q2 Q3	X=0 のとき 次状態	X=1 のとき 次状態	Z(X=0)	Z(X=1)
0 0 0	$D_1=Q_2{Q}_3^{\prime }=0,D_2=Q_3=0,D_3=Q_2^{\prime }+X=1$ → 001	$D_3=0+1=1$ → 001	$Z=X{Q}_2^{\prime }+X^{\prime }{Q}_2=0$	1⋅1+0=1
0 0 1	$D_1=0\cdot 1^{\prime }=0,D_2=Q_3=1,D_3=Q_2^{\prime }+X=1$ → 011	$D_3=1+1=1$ → 011	0	1
0 1 0	$D_1=1\cdot 0^{\prime }=1,D_2=Q_3=0,D_3=Q_2^{\prime }+X=0$ → 100	$D_3=0+1=1$ → 101	$Z=0$	$Z=1\cdot 0+0=0$
0 1 1	$D_1=1\cdot 0^{\prime }=1,D_2=Q_3=1,D_3=Q_2^{\prime }+X=0$ → 110	$D_3=0+1=1$ → 111	$Z=0$	$Z=0$
1 0 0	$D_1=0\cdot 0^{\prime }=0,D_2=0,D_3=Q_2^{\prime }+X=1$ → 001	$D_3=1+1=1$ → 001	$Z=0$	$Z=1$
1 0 1	$D_1=0\cdot 0^{\prime }=0,D_2=1,D_3=Q_2^{\prime }+X=1$ → 011	$D_3=1+1=1$ → 011	$Z=0$	$Z=1$
1 1 0	$D_1=1\cdot 0^{\prime }=1,D_2=0,D_3=Q_2^{\prime }+X=0$ → 100	$D_3=0+1=1$ → 101	$Z=0$	$Z=1\cdot 0+0=0$
1 1 1	$D_1=1\cdot 0^{\prime }=1,D_2=1,D_3=Q_2^{\prime }+X=0$ → 110	$D_3=0+1=1$ → 111	$Z=0$	$Z=0$

整理すると：

現状態	X=0	X=1	Z(X=0)	Z(X=1)
000	001	001	0	1
001	011	011	0	1
010	100	101	0	0
011	110	111	0	0
100	001	001	0	1
101	011	011	0	1
110	100	101	0	0
111	110	111	0	0

状態図：
8状態（000〜111）のMealy型。$X/Z$ ラベルで遷移を記述。

flowchart LR
    000["000"] -->|"0/0<br>1/1"| 001["001"]
    001 -->|"0/0<br>1/1"| 011["011"]
    010["010"] -->|"0/0"| 100["100"]
    010 -->|"1/0"| 101["101"]
    011 -->|"0/0"| 110["110"]
    011 -->|"1/0"| 111["111"]
    100 -->|"0/0<br>1/1"| 001
    101 -->|"0/0<br>1/1"| 011
    110 -->|"0/0"| 100
    110 -->|"1/0"| 101
    111 -->|"0/0"| 110
    111 -->|"1/0"| 111

(b) タイミング図

初期状態 $Q_1{Q}_2{Q}_3=000$、$X=01011$（LSB first？問題文の指定による）
ここでは左が最初に入力されるとする（$X=0,1,0,1,1$ の順）。

クロック立下りエッジで状態変化。

CLK立下り	X	次状態 Q1Q2Q3	Z
0→1→0（初期）	—	000	—
1回目	0	001	0
2回目	1	011	1
3回目	0	110	0
4回目	1	111	0
5回目	1	111	0

タイミング図の波形（時間は左→右）：

CLK  ┐┌┐┌┐┌┐┌┐┌┐┌┐┌┐
     ┘└┘└┘└┘└┘└┘└┘└┘
X    0   1   0   1   1
     ┌──┐  ┌┐  ┌──────┐
     ┘  └──┘└──┘      └──
Q1              ┌────────
    ────────────┘
Q2      ┌──────────────┐
    ────┘              └──
Q3  ┌────────────────────┐
    ┘
Z         ┌┐
    ──────┘└──────────────

立下りエッジ直後の出力に注目。Mealy型なので $X$ が変化するとZも変化する可能性がある。

(c) 誤った出力の防止

この回路ではMealy型の出力 $Z=X{Q}_2^{\prime }+X^{\prime }{Q}_2$ が、クロック立下りエッジの前後でグリッチを起こす可能性がある。

$X$ がクロックエッジの近くで変化すると、$Q_2$ がまだ新しい状態に更新される前に $X$ だけ先に変化し、一時的に誤ったZが出力される。

対策： $X$ はクロックのアクティブエッジ（立下りエッジ）の直前で確定させ、直後には変化させない。具体的には「クロック立下りエッジの直前でセットアップ時間を満たし、かつ直後ではなく次のエッジとの中間で変化させる」のが望ましい（問題文の設定では中間で変化しているのでOK）。

さらに安全にするには、出力ZをD-FFで1クロック遅延させる（出力レジスタ方式）。

解説

順序回路の解析手順：

1. 論理式から $Q^{+}$ を計算 → 遷移表
2. 遷移表から状態図を描く
3. タイミング図を描く（クロックエッジで $Q$ が変化するタイミングに注意）

Mealy型の注意点：

• 出力 $Z$ は入力 $X$ の影響を直接受ける
• $X$ がクロックエッジの近くで変わると、一瞬誤った出力（グリッチ）が出ることがある
• 「正しい出力」はクロックのアクティブエッジ直前の $X$ と $Q$ で決まる

---

参考

この問題集は教科書の章ごとに構成してある。各問題の前に対応する章のノートを読み返してから取り組むと効果的。

特によく出るテーマ：

• 順序回路の設計手順（Ch15）→ 本日のノート
• 状態削減と状態割当（Ch14）→ 第14回ノート
• K-mapを使った論理式の簡単化（Ch5-6）
• カウンタ設計（Ch11）