20260430_4

20260423_4

---

不完全定義関数

いくつかのシステムでは、入力がすべての値の組み合わせにならない場合があるため、ドントケア項として出力を決めない不完全定義関数がある

この場合

$$f=m_0+m_1+\cdots d_1+d_2$$

とする

---

半加算器

A	B	Sum
0	0	00
0	1	01
1	0	01
1	1	10

$S$を下の桁、$Co$をキャリー(桁上がり)として、

$$\begin{array}{r}S=A\oplus B\\ Co=AB\end{array}$$

全加算器

半加算器にCarry inを追加した形

$S$を$Sum$、$C_{out}$をキャリーとして

$$\begin{array}{rl}Sum& =X\oplus Y\oplus C_{in}\\ C_{out}& =Y{C}_{in}+X{C}_{in}+XY\end{array}$$

全加算器は半加算器2つとORひとつで表現できるらしい

---

多くの桁の計算をする場合は全加算器をたくさんつなげる

1の補数の加算の時は最上位のキャリーを最下位のキャリーとして入力する→桁数が多いと上の桁までキャリーするのに時間がかかる

減算機の時は引く数にNOTを付けて1を足すことで全加算器をそのまま使える$(A-B=A+(-B)=A+\bar{B}+1)$

---

全減算機

x	y	bi	bi+1	di
0	0	0	0	0
0	0	1	1	1
0	1	0	1	1
0	1	1	1	0
1	0	0	0	1
1	0	1	0	0
1	1	0	0	0
1	1	1	1	1

bは桁借りの必要の有無を表す

---

桁上げ先見加算器

キャリーの伝播が遅い問題を解決したい

→下位の桁上がりを確認すると自身の桁が上がるかをAND-ORで計算できる(ビット数が増えると回路は大きくなる)

→計算待ちをしなくてよくなる

16bitの計算は4bitごとに分けて桁上げを予測するなどの工夫ができる

さらに大きくするときはcarry-lookaheadを重ねることで遅延を減らすらしい

---

回路を小さくするためには論理式を簡単化するが、計算時間を短くするためには回路を大きくすることをすることもある

---

5章 カルノー図

ブール代数で頑張ることもできるが、扱いにくいt

→分かりやすくて扱いやすいカルノー図を使おう

---

最小の式とは？

積和形なら

• 項数が最小
• リテラル数が最小
  和積形でも
• 項数が最小
• リテラルが最小

これまではブール代数で論理式を簡単化してきたが、冗長な項を追加してから項を消去したりしていた←難しい

カルノー図を用いて簡単に操作したい

---

2~3変数カルノー図

隣り合っているマスは1変数だけ値が違う

	A=0	A=1
B=0	1	0
B=1	1	0

1になっていて隣になっているところは併合の定理が使えることがわかる

	A=0	A=1
BC=00	000	100
BC=01	001	101
BC=11	011	111
BC=10	010	110

$F(a,b,c)=m_1+m_3+m_5$のときは以下のようになる

	A=0	A=1
BC=00	0	0
BC=01	1	1
BC=11	1	0
BC=10	0	0

このように並べると表の上下も隣接しているものとして考えられる

$2^n$個の塊で併合することが可能

書き込むときはそれに従って書けばいい

カルノー図から論理式を出すときはできる限り大きい塊を書き出せばいい(1の最小項は同一則より複数回使用できる)

コンセンサス項はカルノー図上でも冗長な項として出てくる

---

4変数カルノー図

→二つずつまとめる

	AB=00	AB=01	AB=11	AB=10
CD=00	0	4	12	8
CD=01	1	5	13	9
CD=11	3	7	15	11
CD=10	2	6	14	10

トーラスとしてとらえられる(カドは集まる)

ドントケア項については都合よく0とも1ともとらえて囲んでいい

和積形を作りたいときは0を囲んで$f^{\prime }$の積和形を作ってからドモルガンすればいい

---

主項

• ほかの項の内項にならない項が主項

graph LR
A[まだ包含されていないXを選択]
B[選択したXについて隣接するすべての1とXを探す]
C{単一の項が選択した最小項と隣接するすべての1とXを包含するか？}
D[その項を必須項として選んでループで囲む]
E{包含されていない1を全て調べたか？}
F[カルノー図上に残る1を包含する最小の主項の集合を見つける]

A-->B
B-->C
C--YES-->D
C--NO-->E
D-->E
E--YES-->F
E--NO-->A