VLSI設計支援工学 2

積和形論理式と多段論理式
• 積和形論理式 = AND-ORの2段
• 多段論理式 = 3段以上の任意の形
• 一般的には、多段論理式の方がコンパクトな表
現になる
– ace + ade + bce + bde + cf + df = (c + d)(e(a + b) + f)
• 回路面積の目安 = リテラル数
– 16 → 6
• 回路遅延の目安 = 2入力基本ゲートで表現し
た時の段数
– 5段 → 4段
論理式の割り算
• f = gh + r
– fをgで割った商がhで、あまりがr
– 一般的には、hとrはユニークには決まらない
• hとrに制限をつけない=論理的割り算
– 無限通りの割り方がある
– 1回の割り算に積和形論理式の簡単化と同じ手間が
かかる
• ghを代数的積に制限する=代数的割り算
– 結果がユニークにできる
– O(n log n)の手間で計算できる
– そんなに悪くないことが多い
論理式の代数的処理
• 代数的論理式とは、論理関数の積和形論理式
表現で、他の1つのキューブに含まれるキューブ
(single cube containmentと呼ぶ)のないもの
– ab + abc + cdは代数的論理式ではない
– ab + cdは代数的論理式
• 代数式fとgの代数的積fgとは、fgを展開し、
single cube containmentについて冗長性を取った
もの
– fとgに共通な変数がないとfgは必ず代数的積
– (a + b)(c + d) = ac + ad + bc + bdは代数的積
– (a + b)(a + c) = aa + ac + ab + bc = a + bcは代数的積
ではない
論理式の割り算の例
f= ad + ae + bcd + j
g1 = a + bc
g2 = a + b
• fをg1で代数的に割ると、商はd、あまりは
ae + j
• fをg2で代数的に割ると、商は(a + b)d、あ
まりはae + j (代数的には割れない)
Weak division(代数的割り算であまりの
キューブ数最小のもの)のアルゴリズム
Weak_div(F,G):
U = {uj}/* Fの全てのキューブだが、Gに現れるリテ
ラルだけに制限したもの*/
V = {vj}/* Fの全てのキューブだが、Gに現れるリテ
ラル以外のリテラルに制限したもの */
/* uj vjがFのj番目のキューブとなっている */
Vi = {vj ∈ V| uj = Gi}
H = ∩ Vi
R = F – GH
return (H, R)
• 上のアルゴリズムはO(n log n)です。どこがそうでしょう
か?
• O(n)にできますか?
Weak divisionのアルゴリズム:例題
F = ace + ade + bc + bd + be + a’b + ab
G = ae + b
U = ae + ae + b + b + b + b + ab
V = c + d + c + d + 1 + a’ + 1
Vae = c + d
Vb = c + d + 1 + a’
H=c+d
R = be + a’b + ab
F = (ae + b)(c + d) +be +a’b + ab
Gをどうやって選ぶか?
カーネル、コカーネル
• 効果的に割れるGを探す必要
– Gは無限にある
• 問題: 論理式の集合{Fi}が与えられた時、できるだけ多く
共通に割れる代数的項を探す
• 探索対象=カーネルに制限
• 定義
– 積和形論理式がキューブフリーとは、すべての積項に共通なリテ
ラルがないことを言う
– 積和形論理式のカーネルとは、その論理式に含まれる複数の積
項からリテラルをとってキューブフリーにしたもの
– 積和形論理式のコカーネルとは、カーネルを作るときにとったリテ
ラルの積
カーネル、コカーネルの例
x = adf + aef + bdf + bef + cdf + cef + g
= (a + b + c)(d + e)f + g
カーネル
a+b+c
d+e
(a + b + c)(d + e)f + g
コカーネル
df, ef
af, bf, cf
1
カーネルに関する基本定理
• 論理式F、Gについて、Fの任意のカーネル
kFとGの任意のカーネルkGが共通に持つ
積項がたかだか1の場合、FとGは積項数
2以上の積和形論理式で代数的には割れ
ない
• つまり、論理式をカーネルで割ったしまえ
ば、複数の論理式を共通に割れるのは、
キューブに限定される
カーネルの計算アルゴリズム
R ← Kernel(j, G)
R←0
If (Gがキューブフリー)R ← {G}
For i = j+1, …, n {
If (liが1つの積項のみで現れる) then continue
c ← G/liを割り切る最大キューブ
If (あるk<i に対し、lk ∈ c) then continue
else R ← R ∪ Kernel(I, G/(li・c))
}
Return R
• Kernel(0, F)がすべのカーネルを計算
• lk ∈ cが高速化のポイント(同じカーネルを求めな
い)
abcd+abce+adfg+aefg+adbe+acdef+beg
b
a
b
c
d e
c d e
d+e c+d b+ef b+df
e
d
f
c
d
e
(a) (a) ac+d+g
c
(a)
e f f gd+e
b+cfce+gcd+g
c+e
co-kernel
1
a
ab
abc
abd
abe
ac
acd
注意:
kernel
f g)( d + e) + de( b + cf ))) + beg
+
( bc+ f g)( d + e) +de( b + cf )
c( d + e) + de
d +e
c +e
c +d
b( d + e) + def
b + ef
f =bc= ad +ae = a( d + e).
a(( bc
多段化の例
f1 = ab(c(d + e) + f + g) + h
f2 = ai(c(d+e) + f + j) + k
カーネルd + eで割ると
l=d+e
f1 = ab(cl + f + g) + h
f2 = ai(cl + f + j) + k
さらにカーネルcl + fで割ると
m = cl + f
f1 = ab(m + g) + h
f2 = ai(m + j) + k
共通に割れるカーネルはないので、キューブで割る
n = am
f1 = b(n + ag) + h
f2 = I(n + aj) + k