論理関数のスペクトラル解析とその論理合成への応用に関する研究

論理関数のスペクトラル解析とその論理合成への応用に関する研究
九州工業大学
情報工学部・教授
笹尾勤
〒 8 2 0 - 8 5 0 2 飯塚市大字川津 6 8 0 - 4
2000年
1 は
10月
17日
して,7(FPttl√:メ),η
(質RO:r),およびノ(メ
)を示す。
また,これらの値とT(FPRAr iメ),T(rk‐
Rθ :メ),及び
じめに
論理関数のスペクトルを解析することにより, 論理関数
の大域的性質を抽出でき, それを用いて能率の良い回路を
設計できる. スペクトラル解析をデジタルシステムの設
T(SOP:r)と
比較する。ここで , T ( F P R ■
ど : メ) は , 関
数 rを表現する最小 FPRMの積項数,T(rtWO:メ )は,
最小 KROの積項数,及び T(50P iザ)は ,最小 SOPの
計や解析に利用する手法は従来から知られていた 16卜し
積項数である。ノ(メ
)<7(rkコ θ :デ)のとき,多くの場
かし,n変数論理関数のスペクトルを計算するために2化×
合,メを表現するメを表現するSOPの積項数は,KROの
2 ' の行列を用いる計算法しか知られておらず , ■ = 3 0 程
度の問題でも, 計算機の記憶容量を越えてしまい , 実用上
利用不可能であった。しかし, 最近 , M T B D D ( 多端子三分
決定グラフ) を用いることにより, 碑 = 1 0 0 以上の論理関
数のスペクトラムを短時間内に計算する方法が開発され
た。この方法を用いることにより, スベクトル解析を実用
回路の設計に利用できる可能性が出てきた本研究では.
論理関数のスペクトルを解析することにより, 論理関数の
大域的性質を解析し, それを用いて回路を能率よく設計す
る方法について研究を行う.
与えられた々の関数を種々の論理式で表現した場合の
表現の大きさを求める. 次に, それらの大きさを簡単に
推測する論理関数の尺度 ( M e a s l l r e ) を
論理関数のスベク
トラムから求める. 本研究では特に「
A N D - O R 回路で実
現するのが得策か A N D ― E X O R 回路で実現するのが得策
か J を高速に判定する尺度に関して, 実験を行い統計的デー
タを収集する。このデータを用いると, スペクトラムを調
べることにより, いずれの方法で回路設計すべきかが明ら
かになる。
例えば, 関数メ = r l ● 「2 ● …・● r a を表現するに
は, 論理和形 ( S O P : A N D ― O R 二段論理回路 ) では, 2 ・ 1
個の積項が必要であるが , E X O R 論理和形 ( A N D _ E X O R
二段論理回路 ) では, わずか , 個の積項で十分である. 一
方 , 関数 r = r l J l v r 2 y 2 v … . v r w 角を表現するに
は, S O P では , 1 個の積項で十分であるが, E X O R 論理和
形では, 2 れ- 1 個の積項が必要となる. 与えられた関数メ
を表現する E X O R 論理和形が S O P よりも逢かに簡単な
場合には. E X O R に基づく論理設計法を使用すべきであ
る. 関数メを表現する最適な方法を見つけるには、一般に
時間がかかる。従って, 種々の表現法の大きさを高速に見
積もる手段が必要である [ 2 , 3 , 7 , 9 ‐
1 司.
要警
さ
￨ズ
犠誓
姦
1陥:れ4留
,お
経弓
α
F P R M や K R O の積項数よりも多くなる。ただし, 例外
も存在する. 7 ( F P t t l r : メ) ゃ切( r I W O : r ) は , 論理関数
ら計算でき,
r の拡張真理値ベクトルや, E X O R _ T D D か
また, ン( ァ
) は, メの B D D から計算できる. 後述するよう
に, 拡張真理値表 ( E X O R _ T D D ) は論理関数のスペクト
ラムと考えることができる
2 積和形の複雑度の尺度
定義 2.1論理関数ザの最小論理和形の積項数をT(SθP:
/)と表記する。他の論理式に対しても同様な記法を用い
る.
S O P の場合 , 真の最小項の個数が , 論理式の複雑度を見積
もる一つの方法となっている.
定義 2 . 2 論理関数メの真の最小項の個数をァ
ィ
(メ
)=￨メ￨
と言
己す.
補題 2 . l T ( S O P : r ) ≦
↓
チ
(メ
).
乱数関数に対しては,rr(r)は
複雑度の尺度として,かな
1の
り使える12,3,7‐
9,1司.しかし,メ
そ
(メ
)≧2・場合や,
・
ど
の
縮退関数に対して,メ
r(r)は
メ('1,r2,…
,r免
)=ぞ1な
複雑度の尺度として,ほとんど無力である
以下では, S O P の複雑度の尺度として, さらに精度の高
いものを導く.
定義 2,3論理関数メのシャノン展開 r tt れ
v rjrlを
trど
考える,ただしだ,は￨れメ
11の値が最大になるように選ぶ
このときフ(メ
11と定義するただし,メは,
)=メ￨―lrOメ
して, 与えられた論理関数 r を表現する固定極性リード・変数関数,れとす
1は (P-1)変数関数とする.
本稿では , 論理関数を実現する S O P 及び E X O R 論理
和形の複雑度を高速に見積もるために尺度を提案する。そ
マラー論理式 ( F P R M 積
項数の平均値
) の
ー
,(FPttlr iプ
) , とクロネッカ論理式 ( K R O ) の積項数
定理 2.lT(50P:メ)≦ フ(4デ
r(メ
)≦ァ
).
の平均値 ,(rlttο
:メ)を与える公式を導くまた,与えら
れた論理関数メを表現する,論理和形 (SOP)の複雑度の
ついても述べる.フ(す
尺度ン(tr)に
)は,最小論理和形の積
項数の上界になっている.種々のベンチマーク関数に対
-
1
(証明)シャノン展開メ=舟ガOVrず1を考える。次にメ=
Fj90とrjθ
る展開を考える,ここです
l v J2な
0=れ月,
1,92主れず
1である。このとき,T(50Pir)≦
す1=れす
-
T ( 5 0 P : , o ) 十 T ( S θP i J l ) 十 T ( J θP : J 2 ) であるま
P : サ 1 ) ≦ 〃1 1 。
「( S ( り
P:
た, T ( J θ P : 」 0 ) ≦ I J O I , T ( 5 θ
人' 択θ
2 ) ≦I J 2 1 , I J JO l十+ 2 1 , 2 1 = / r)げ
が成立するので, 次
」
の結果を得る
T(5θPir)≦ ノ(ず
)
= T ( 5 0 P : 」 o ) 十ケ( S て
'P:Jl)+T(SOP:J2)
=rr(4′
)一 J21
図 3 . 1 : 種々の A N D ―E X O R 論
( 証明終)
S,μ
定理 2 . 1 は
, フ( プ
)力 (メ
) よりもタイトな上界であるこ
とを示している論理関数 / の真の最小項の個数は, すが
B D D で表現されているときには. 比較的容易に計算でき
る.
3 EXOR論
3 . 2 固定極性リード・マラー論理式 ( F P R M )
各変数 r ど( ナ= 1 ‐ 2 , …. , , ) に対して, 正極性ダビオ展
開, または負極性ダビオ展開のいずれかを適用して得られ
る論理式を固定極性リード・マラー論理式 ( F P R M ) とい
う各変数 r i に対して, 正極性 ( r f ) と負極性 ( 舟j ) の二つ
の極性が存在するので, コ変数関数では, 2 ' 4 回の異った極
性の集合が存在する。与えられた関数に対して、極性の集
意的に
合が決まれば, 係数の集合 ( 々
1 , …・, ? 1 2 ■ ) は
0,“
定まる
理和形の定義と性質
本節では,EXOR論理和形の幾つかのクラスを定義し.
その性質を紹介する110,1刻
3.1 正極性リード・マラー論理式 (PPRM)
次に示す展開は, E X O R 論
理式の関係
12ト
理式の基礎となる 1 4 ‐
3.3 ク
ロネッカー論理式 (KRO)
1 任意の論理関数は. 以下の三つの方法で展開可
補題 3 。
能である。
r = メ 0 キ「げ2 ,
メ = メ 1 キ予1 め,
メ = r 1 / o″1母/ 1 ,
各変数に対して,シヤノン展開,正極性ダビオ展開,ま
たは負極性ダビオ展開のいずれかを適用して得られる論
ロッカー論理式 (KRO)という・各変数に対
( 3 . 1 ) 理式をクネ
して,三つの展開法が存在するので,抑変数関数に対して,
(32)
高々 3向個の異なった KROが存在する.
(33)
ここで
3.4 種々の論理式の間の関係
…, r . ) ,
,・
れ = ず ( 0 , r 2 ,3メ
,r"),
デ1 = メ ( 1 , r 2 , r 3…
,・
=
れ
中
れ
rl・
定義より, 次の定理を得る.
定理 3.1??紀 M,ア ?紀 vM,およびだ紀0を対応する論
MC
理式の集合とする。このとき,??兒 McF?紀
κttOが成立する.
である.
よび ( 3 . 3 ) を, それぞれ, 正極性ダビオ展
(3.1),(3.2),お
開, 負極性ダビオ展開, シヤノン展開と呼ぶ. ( 3 . 1 ) を関数
メに再帰的に適用すると, 次の補題が得られる。
図 31に種々の AND― EXOR論理式のクラスの関係を示す。
Mは ,??紀 Mを真に含み,だ紀0の部分集合になっ
ア?兒フ
ている.従って,任意の論理関数 rに対して,次に定理を
得る.
r . ) は,
補題 3 . 2 任意の n 変数関数 r ( r l , r 2 …‐
■口, だ
2βF 2 …・
Ⅲ
,
l Ⅲ
デ = αO 中で1 「
Ⅲa 1 2l「r 2 + α
1 3 lごr 3 …Ⅲ Ⅲ “, , 1 , t P ' ,+ l
理 3。2T(rl‐妃θ :メ )≦ T(FPRユ
r 定
r ル
r:r)≦
T(PPttnr i
プ) ・
寸貧12 ,3.どltr2だ3 ・・Pi rl
(3.4)
3 . 5 拡張真理値ベクトルとその表現
と表現できる
ー・
ー
( 3 . 4 ) を正極性リドマラ論理式 ( P P R ヽI ) と呼ぶ. 与
ol・
β2 Ⅲ
…・￨
えられた関4 / k メに対して, 上式の係数 ( ■
0卜
・1 2 , ) は , 一意的に決まる. 従って, P P R ヽ I は標準形で
あり, P P R ヽ I の最小化問題は存在しない論理式 ( 3 4 ) の
積項数は高々 2 ' であり, すべてのリテラルは正極性 ( 肯
定リテラル) である。
-2-
よび K R O の生成に極め
決定木は P P R M , F P R M , お
て重要である. 本節では, E X O R 三分決走木 ( E T D T ) を
紹介するもE T D T はこれら三つの論理式の簡単化に必要
な情報をすべて包含する E T D T の
形式的な定義を述ベ
る前に, 簡単な例を示そう.
例 3 . 2 図 3 2 に示す完全 E T D T を考える. 4 個の要素か
らなる二値ベクトル i プ
真
00‐
れトメ1 0 , 1` 1′1 は, メ( r l , r 2 ) の
理値ベクトルであるまた, 9 個の要素からなる二値ベク
トル [ れ
0 , oメl , 2れ, 1メ0 ,1 メ
1 ,1 メ
2 , 0め, れ
1,め
21は
,メ
(rl,r2)
の拡張真理値ベクトルである
f。
。 f01
f。2 f10 fll
f12 f20 f21
(例終り)
次に, 拡張真理値ベクトルの計算法について述べる。完全
E T D T の 3 ' 個の終端節点は, 拡張真理値ベクトル
f22
.,メ
表す。ここで,各要素は
プ(ao),メ
3'1)1を
〔
(al),…
(α
三値ベクトルα=(al,a2,…
,ar)),a,C{0,1,2}('=
1,2,…
…ヵ)で番号付けてある.
図 3 2 1 2 変数関数の E T D T
アルゴリズム 3 . 1 ( 拡張真理値ベクトル
)
例 3 . 1 2 変数関数プ( r l , r 2 ) を
考える図 3 . 2 にメ( , 1 , r 2 ) ど=1‐
2,_,れに対して,a,c(0,1}が成立するとき,
の完全 E T D T を示す。ここで.
),
れ = メ( 0 ,2ご
1メ主メ( 1 ,2だ
),
メ(a)の値は,メの真理値表から得られる。また,あるどに
対して,a;=2のとき,デ(a)の値は,次のように計算で
きる。
2プ= れ Ⅲ メ1 ,
れ0 = r ( o , o ) , 1れ
= r ( o , 1 ) , 2れ
= れo Ⅲれ1 ,
メl o = メ
( 1 , 0 ) , 1 1メ= メ
( 1 1‐) ,
. , a)7=カ
,,も
,…
…
メ
( r 1 1,,と
プ( a l ,. …
…, r 1 7 ' )
11 ′
2 = れO Ⅲメ1 1 ,
…. , 1 , _ . , a l , ) .
Ⅲデ( r t 卜
ぬo = れ o キメ1 0 , ん
1 = れ 1 守メ1 1 , 2メ2 = め0 守め1 ・
である.
( 例終り)
０
０
れ
れ
〓
れ
ぬ
１
１
１０
１
１
０
１０
０１１
０
００
０
１
０１１
１０
論理関数の間の関係は次のように定義
０
を持つ . E T D T と
される。
００
１０００
そ
ど
す
'『
ん(ど
r(Ⅲ
,ァ
{1,2,.…
オを持ち,三つの子供rο
(で
),ヵ
)
),crθ
ア
つ
∈予を持 .終端節点 ?,は
●c{o,1}
,属性として?!artと
１１
０
定義 3 . l E X O R 三分決定木 ( E T D T ) では, 頂点の集合
ヽアが非終瑞節点と終端節点の二つのタイプの節点から構
成されている. 非終端節点ぃは, 属性として , ■
だでご( J ) C
０
形式的な定義を述べ
１
以下に, , 変数関数の完全 E T D T の
る
拡張真理値ベクトルは, 要素数 3 比個のスペクトラムと
考えることができる、これは、
拘o
れ1
れ2
デ10
/11
メ12
めo
れ1
れ2
のような変換を考えたとき, 最初の 9 × 4 のマトリックス
1 . どが終瑞節点のとき:
なゴ
( a ) aげr c“( J ) = 1 ら￨
, ふ= 1 .
ar“
c(け
, メT = 0 .
(1))コ
) = 0 なら1 ゴ
2 . どが非終端節点で力l ●
どr ( Ⅲ
) = どのとき, ∴】は, 次に
定義される論理関数である.
が,変換行列を定義し,拡張真理値ベクトル〔
2ザ10,
れ0,れ1,拘
11,メ
1 2,め
0,れ1,め
21がスペクトラムに対応する。この考
す
え方は, 一般に , 変数関数に拡張できる [ 1 6 1
3.6 FPRMと
KROの
極性ベクトル
定義 3 . 3 , , 変数 F P R M の極性ベクトルとは, 二値ベクト
・ ,rァ
と) =
ん ('1,r21・
ルa = ( a l ,2紀
でる. βj = 0 は,
1…
・, α
■
),ぢ
βC { 0 , 1 ) あ
Fが !。
" , ( )ど( r l , r 2 1 … , r . )
″ぢで正極性ダビオ展開を使用することを示し, αぢ= 1 は ,
れで負極性ダビオ展開を使用することを示す。
争r ' 力所。
ん( T ) ( r l ,2・
, …。
ル
,rヶ
),
1,r2,.. ,何
れ)=
メFNοR(ど
)(″
ぃ(T)(「
卜r2,…・
抗。
,だ比)
…l r)r.と
◆/ /jと
ダ
と
( T ) ( r l 2ギ, ・
ETDTにおいて,根から終端節″
点に至るどの経路におい
ても,丁度 ′
1個の非終端節点を含むとき,ETDTは完全
であるという.
与えられた関数が完全 ETDTで表現されているとき.
ETDTの終瑞節″
くは拡張真理値ベクトルを表す.
2,変数関数の拡張真理値ベクトルとは,3・個の
定義 3。
要素からなる二値ベクトルであリー各要素は完全 ETDT
の終端節点に対応する.
-3-
,と
変数関数の F P R ヽ1 には, 2 ・個の異なる極性が存在し,
極性ベクトルがその展開法を指定する. X R O の
場合に
は, 正極性ダビオ展開, 負極性ダビオ展開, シャノン展開
の三つの異なる展開法が存在するので, 極性ベクトルは,
3 免個の異なる極性が存在する.
4,2変数 KROの
定義 3 。
極性ベクトルとは, 三値ベクト
ルa = ( a l ‐
Q2,・
…
, a ), ,ぁr l {i0∈
, 1 , 2あ
}る
で. Q ど= 0
は, r どで正極性ダビオ展開を使用することを示し, αち主 1
は, r f で負極性ダビオ展開を使用することを示し, a ど= 2
は, αj でシャノン展開を使用することを示す。
,と
変数関数の K R O は , 3 比個の異なる極性が存在し, 極性
ベクトル α がその展開法を指定する.
定理 4 . 3 , 変敬関数メのF P R M の積項数の平均値は,
`だ
,十
t/iょ
(`/)
PR■
r:す
竹),
仲)メ
7ぱ
)=2'Σ 入
oo
メ
. / 0れo
0
0√
1
`
0
1
れ1
.′
ん2
れo Ⅲれ1
lo
`1′0
メl o メ
1
.1′
/11 rll
`1だ2
/ 1 0 中メ1 1
20
lo
ず
れo やデ
ん1
れ1 やプ1 1
メ1 1 / 2 2
れO фれ1 中ザ1 0 Ⅲ
γC T ・
数であ
で与えられる , ここで人( γ) = 2 芹 ‐於は 7 の 1 の 1 固
る
で
り. T = { 0 , 1 , 2 }あ
とき,
例4 . 3 , = 2 の
R ユr i r ) =
' 7 (Pダ
2 21(r(0,0)+プ
r (( 1o ,. 01 ))(+十
1メ, 1 ) )
2
)
十̀
+ 2 ( (メ0 , 2 ) (+ 1す‐ (′2 , 0 )(+2デ, 1 ) )
+ 4 メ( 2 , 2 ) 1 .
図 4.1:拡
張真理値表の導出
EXOR論
4 AND―
j 終り)
(伊
理式の積項数の平均値
定義より,次の関係を得る
4.1 正極性リード・マラー論理式
系 4.lT(FPR■
定理 4.1関数プを表現するPPRMの積項数は,
ケ
rir)= Σ ず
(α
),
(PPtt■
4.3 ク
ac(012}'
rir)≦
ィ(ゴPRAr:てだ)
ロネッカー論理式 (KRO)
定理 4.4,変数関数ザのKROの積項数の平均値は,
で与えられるここでΣ は整数和を示す.
0:々
ザ
だ
)=(2/3)'Σ
竹),
釈戸景
TCT'
例 4.1,=2の
場合,
T(PPRlど
: メ) = r ( 0 , o ) 十
与えられるここでぃT = { 0 , 1 , 2 } で
ある.
2,2) で
r ( 0 , 2 ) 十 r ( 2 , 0 ) 十メ( を
(例終り)
である。
定義 4.1すべての ,変数関数を表現する PPRMの
記す。
数の平均値を ,(PPRAr:,)と
定理 4.2η (PPttnr iテ1)=2閉
例 4 . 4 ァ】= 2 の
場合 ,次のようになる
「
0 , 1ず
)(キ
0,2)
( t F ) = ( 2 / 3( )0 2, i0 プ
ザ
)(キ
)十
十メ( 10‐
メ( 1 , 1 ) + 24 )/ ( 1 ‐
)l.
)十
十す( 20‐
プ( 2 , 1 `)(ガ
22‐
十
積項
l,
4 . 2 固定極性リード・マラー論理式
( 例終り)
定義 4.2関数すを表現するFPRNIの積項数の平均値を
己す。
η(ゴPRl√ :ザ)と言
定義毎 r の拡醸理値ベクロレを臼< : 房
記す。
で
,ォ
)￨で
「
(メ
) の非零要素の個数を￨ ?十
(メ
義より` 次の関係を得る
定
系 4.2T(ARO:デ )≦ ,(圧景0:ず )
5 複雑度の尺度の計算法
F'
チ
ここで, T = { 0 , 1 , 2 ド F 羅
nl=Σ
1針
く
E デ竹) ・
鰈
テ
態 ( きいとき, 本手法で必 :
は, 拡張真理値ベクトルを率直に表現するよりも少なくで
きる。
TcTれ
例 4 . 2 図 4 . 1 に, ″ = 2 変数関数の真理値ベクトルから定
拡張真理値ベクトルを導く方法を示す. 真理値ベクトル関
は、2 ' ' 個の要素から構成される一方。拡張真理値ベクトの
終り) 共
ルは, 3 ' 個の構成から要素される。
(例
-4-
1 入力変数の順序が固定されていると仮定する
義 5。
の
数ず E X O R 三分決定グラフ ( E X O R ゴ D D ) とは, デ
E X O R 完全三分決定本において. 同型な部分グラフを
有して得られる有向グラフである
E X O R _ T D D l 1 0 1 は , 三分決定グラフ ( B D D ) 1 1 1 と同様な
アルゴリズムで生成できる入力変数の個数が多い時に
は, B D D は , 真理値ベクトルや, S O P のキューブ表現よ
りもコンパクトに ( 少ないメモリで) 表現できる同様に,
E X O R _ T D D も , 拡張真理値ベクトルよリコンパクトに
変数関数の完全三分決定木の節点数は, 1 +
表現できる. , ュ
. + 3 ' 1 = ( 3 ' - 1 ) / 2与
でえられる。しかし,
31+32+…
は, 一つの部分関数に対して, ただ一つの
EXOR_TDDで
フを
グラ
部分
実現すればよいので ―同じ部分関数が何度も
生じる場合には, 節点数を削減できる.
1 任意のヵ変数関数は, 節
定理 5 。
EXOR_TDDで
表現可能である.
点数 θ( 3 " / , ) の
定理 5 . 2 任意のヵ変数対称関数は節点歓 θ( " 3 ) の
EXOR_TDDで
表現可能である。
アル」リズム 5 。
1,(FPRArir)の
計算
1 関数プの E X O R T D D を構成する。
2 各枝に重み人( 1 ) を付ける。各パスの重みの和を言
十算
する
人
3り(FPRl丁
(γ
ギ)=2'Σ
い)メ
)・
々
l AND―
6。
EXOR論
理式で表現された関数
JB(,,,1)=ど 1キ ,2Ⅲ …Ⅲトデ"は ,担変数パリテイ
KROで
関数である。この関数を表現するには FPRMと
は,"積項で十分であるが ,SOPでは 2'1積項必要であ
る.
Sβ (9,4)=rl,2'3r4Ⅲ
rl「2r3打5Ⅲ ・… ￨やr6rTr8'9
は, E S O P 簡単化プログラムのベンチマーク関数である
[81 この関数ずでは,関係 T(JOP:メ )=T(FPRy:
√)=「(IPO:メ )が成立している.
Testlは関数 /=rl r2…・デ,キ r,+1,('7=8)である.
すべての ,に対して,T(FPRl√
:メ)=T(斉
抑
: メ) =
2・
T ( J θP : メ) = , 1 + 1 が成立する
2 AND―
6。
OR論
理式で表現された関数
…r虎,("=2T=
Test2は関数ず=Fl予 2… テ,V rl,2・
べ
ての
ァ
,に
8)であるす
対して,T(50P:メ
)=2,
T(ダPFir:プ )=2'+1_2,T(圧
Rθ :メ)=2が成立
する
Test3は関数メ =rlr2 V r3r4∨ …'Vr.lr.,(,=
2メ=8)である。すべてのヵに対して,T(SθPiプ )=r,
T(FPR■ r:r)=T(r.‐貫0:r)=2'-1が
成立する.
γc T れ
6 . 3 算術演算関数
2 7 ( I R ο : r ) の計算
アルゴリズム 5 。
1 . 関数メの E X O R T D D を構成する
2 . 1 枝に重み 1 , 0 枝に重み 0 を付け, l p a t h の重みの
計算を行う.
妃
θ:メ
3,(斉
プ
侍)
)=O/3)'Σ
、
vst8,
rdll18,rot8,sqr8‐
れdr4,inc8,lo38,lnlp4,nrll14‐
and syll19などは算術演算関数である。このうち,adr4,
inc8,111lp4,rdn18,sqr8,および wst8では,KROの積項
数は SOPの積項数よりも少ない。これらの場合 ,7(【兄ο :
tF)<フ (プ)となっている。
TCT'
6 . 4 乱数関数
2 多出力関数への拡張
5。
与えられた , 入力 , コ出力関数 r = ( / o , メ 1 , . …, かれ 1 )
が多端子三分決定グラフ ( M T B D D ) 1 1 列で表現されてい
るものとする。この場合 , 複雑度の尺度を次のように計算
する。すに☆
寸する MTTDDと
,c】古
(す)対する MTBDD
を構成する
7 結論
メ( す) = 非零要素に至る経路の数
= 2 ' 一 ( 零要素に至る経路の数)
本稿では,論理関数プを表現するFPRMおよびKRO
の積項数の平均値を与える公式 7(ゴPRAr iメ )および
:メ)を導いた。これらの値は,アの拡張真理値
切(rlttθ
ベクトルやEXOR_TDDから容易に計算できる.次に,
種々のベンチマーク関数に対して,7(ゴPttM : メ )と
,(IttO:メ )の値を計算し,ザの最小 FPRMの積項数
兄0:r)
「(FPRlr i r)および最小 KROの積項数 T(/1‐
と比較した。また,SOPの複雑度の尺度としてノ(ザ
)を
定義したこれは,メの最小 SOPの積項数の上界になっ
ている。メがBDDで表現されている場合,ノ(メ
)も容易
に計算できる.種々のベンチマーク関数に対して,ン(す
)
:r)のと
の値も求めた,多くの場合,ノ(r)く η(rtttθ
０
≠
ｒ
＞
ｏ
争
つ ≠
付げ
像
・
メ
‐
, ( / R・O : す ) =
柳ｐ鳩
ノ( メ
0)
(1,a)≠
)=ァで
( r ) 一( す
(o,a)=す
となるような要素a c B ' 2 1 の個数
7(ゴPRArir)=
角 = 7 , 8 , 9 に対して, 疑似乱数関数を生成した. ただ
し, どの関数も真の最小項を丁度 2 ' 1 個含むどの場
合にも, S O P の積項数は, K R O や F P R I X I よりも少なく
なったこれらの場合, ノ( プ
) < , ( r k ‐況0 : メ ) , フ( メ
)<
いる.
い
ど:
ザ
になって
う関係
)と
切( F P R ■
6 実験結果
表 6 . 1 に種々の関数に対する実験結果を示す。これらの
関数は 4 つのグループに分類できる
- 5 -
き, S O P の積項数は, K R O の積項数よりも少ない. 一方,
たはフ( r ) > η ( 斉兄0 : メ ) の
″( ザ
) > η ( F P R ‐V r i r ) ま
c ‐c 7 . 所
C
に1 M D a v i O , J ― P D c s ( 1 l a I I I I ) S A l l ( l A T l l a yDsネ
表 6.1:実験結果
入出
,:平均値
FP
力力
RヽI
I(R0
SB(8、 1)
8
1
8 5
44 9
SB(9‐ 1)
9
1
9 5
66 6
SB(9,4)
9
4
189 0
259 4
Tk)stl
9
1
27 1
26 6
1
49 3
19 9
■〔
lst3
8
1
57 6
54 2
a(1■
4
8
5
70 0
lIIc8
8
孜 ,st2
r: 塙
詫/1ヽ
直
イ
R ヽI
I(R0
9
56 2
F9 9
8
230 7
222 9
)4
IIllェ
8
205 8
204 2
1lrI114
5
226 6
211 2
r(1l118
8
78 0
121 8
rot8
5
175 6
154 8
236 8
239 2
wst8
4
154 0
202 1
SVI119
1
186 5
Rall(1()1117
1
65 7
64 4
Rnil(1()1118
1
126 5
127 0
Ra1ldOI119
1
250 4
254 7
Graw―
Hill IIIt(IIlati()1lal,
D D c l ) 1 1iをt h a l l ( l T S a s a ( )F,a s｀
t Bo()lca11 11latClllIIts
→
('1ltativ(,ギ
α
llll(1(lr VArial)1(11)(,rl【
1lltatioIェ
llsillg l(,I)r(￨｀
ムさ方
FP
SOP
″ '4サケ07パ lMぐ
1978
SOP
何ぁ材 5 o l ↓サん P ● ●, , c D ・
さj す7 , ス “ヤo , ′ぉa れ " ル σ o 7 り牝 7 C 7 , C C , A S P ‐
D ■ 0 ' θθ、1 ) 1 ) 3 5 9 - 3 6 2 、J A 1 1 1 9 9 9
256
9
2
2
2
2
15
Iilk」
、れ1 1 ( l J C ヽ I l l % i o ‐
助 CCt,0[
r /jc、
(1(工
1985
Trcわ ",?ィ̀c く方
7'I)句力ar ttθ
A (!と
、
1 11( PI css‐
S L Hllrst,D M ヽ
“ a g c 、r a l l l c s o f ( 1 1 l a i l ―
F ヽ1 1 1 ば0 ■ 1 1 ( l G P R l t % ( ) 1 1A1v,ぃ
や
all
fRlll(lti()11
11lilliIIェ
i%れti()11、
titiCS Al)1)(ralilェ
g ill B()()1(ェ
十
サ、ヽ( ) l E C - 1 3 . N ( ) 4 , A p r i l
r 』』β 7 ■. 7 パ E ′C C C r ヵr , P 比
9
2
4
1964,I)p 87-92
に
ssli(11‐
((｀) f M O D _
T Sasa()a11(lP B(ヽ
0 1 l t l l (ぐ! ( ) 1 1 1 1i)t1ド
Ⅲ
r。
″
￨
‐
s 、 r β』』 7 子r r ,、
ぁo 7 お θφ? r2ち
2 Slllll PLA｀
'イヽ 1 32,
34
loビ8
sqr8
,ヶル″ 、1/1ケ
lcん ,7う
o力
256
l)1990
N()2,pI)262-266‐ F(ヽ
｀
■A g ( 、1 1 1 1 1 1 l1l())(f｀
l)r()(1( ) 1 1 1 1 ( l s ( ) 1 l tと
、
hv((｀
T S を l s i l ( )B、
225
｀
( )0 (■1 1 1 ( 1( ド
xヽI ) r (S｀
i ( ) I I )s1景
1 1 ( t s i l l l l l ( , I111l1i1l1l1ilェS l l l 1l )1 ご
い
を
「
″
1t1｀
11(<1()1lt l)1lt flllictiOIis、
1(1￨1―
( , ( l i l l I )イ
10l-t、
1 1 1 1 1 l t i l、
)r1ヽ
I ( ) 1 4 0 、N o 5 、
ヽゆ″
" θ ゆ? ′
,P?1ヤ
r 』』』 T 7 伊ル
、｀
1)1)645-651、
r l ar、1 9 9 1
小
143
￨ん
をヽ
材 θ ! ,サ
打l l z a r l o,7 お
C S77ち
ホ a ″ル
T S a s a o ( ( 卜 ( 1 ) 、あつo ケ
サ
255
255
c a ( 1 ( , 1 1 l i c P l l l ) sl 、
i s1 i9 l9 (3 ■
I ( 1 1 l w ( ,A ど
｀
i t l l l)lrl 丘
江I N 2 : A s i I I I I ) l i f l ( a t i1(3)(1)1r■
T S a s i l o ‐ E ♪t ふ
84
、1 ) r 、
i o l l 、よ ) r
o ■1 ) r ( ) ( 1 1 l c(t￨、
(、
‐c l l、s i v (Oヽ
R Slllll―
(sヽ
l G ( l i l l I ) 1 l tv を
1t1w1(l)C―
( l o l l l l ) 1 l t f R l l、
lcti()IIs中
l l l l l l t i lv )a l1 c1 ―
226
212
r2野朋
昴 η 7'町 ●サ'o7パ
ひ″
″ θ O'アル
。,ル qだ rィル
PィιサC卜 ■ サ″●イ Dc、ケ
ヽrr,↓
rF S1/、
￨`ャ
rド, V()1 12‐ N() 5‐ 311■ド
サ̀サ'αttCr7 σ
,7Cイ
tl・
とき, S O P の積項数は, F P R M や
K R O の積項数よりも
い
よ
もある。ィ( F P R ■ r i
も
ちろん
うに例外
多
,Test3の
:
メ
に計算できるので,
比較的容易
r ) , , ( r k R θ ) , ″( メ) は
T ( ゴP F l r : r ) , T ( r t ‐
R θ : デ) , T ( 5 θP : メ ) を見積もるの
に利用できる.
本論文の基礎となっている拡張真理値ベクトルや
一
EXOR_TDDは
, 論理関数のスペクトラムの種と考え
ペ
ム
られ [ 1 6 1 , スクトラから論理式の複雑度がある程度推
測できることが分かる.
1993、 1)p 621-632
1 材方
θ7 ちθす D ホー
ド
7ル
T SASa()all(1ヽ
I Flljita(c(1)、
妃t 2 , , C・
c Plll)hsilcrs.1996
御 c l c r↓
“
7,CIあ
7 が、I ( 1 1 l w ( , r A ( , a (11l(i■
｀
1I( 卜
1 ) 1 l a t l lG、
1 1 (1 ｀
を
1 l i Z C ( l R c ( ,1(111-1ヽ
T S a s a ( ) をヽ
11(lD D(卜
(ヽ
( ' ｀1 ) r ( ヽ
ssioIIsi CO11lI)1(P、
ity alェ (l an(￨、
い
rErC2 2),7パ
■180ritll111、
act 11111liIIlizatioll
acれ07み
ヽゴ竹7ル
材■7,C7'14子
さ,
V()l E79-A、N0 12,I)I)2123-2130‐ D(( 1996
｀
1141 T Sasao,｀ Aritlllllctic tcrilary(lccisi011(liagralIIs aII(1
｀
rl子
ス
本んοP
ん r/ル
サ
c,7ル
r 7サ
を
,7ル
フ″o,ヽ
tll(lir apI)li(,ati01lsギ
Pο“,サ
)θを
7‐
ぁ
s q ルんc t t c c ‐
材
Л
″? ↓
材●7 β 】2 2 f 7 7あ7
0 7 おれ ' P ′
t C a れ。ァ
パれ″
c 地方
サD c s j v ■! r t t C c 材〃 " 材c T θ
C a l l a ( 1、
れA l l
り、V i C t O r i a 、
謝辞
gllst 20-21,1999
( ￨ (1 ヽ
T S a s a o K r 1 1 1 ( l I ( I ( 1 l r i 1 1 l oT1l0l,r“
)araIIlctcrs to nlld
本研究は, 一部 , 高柳記念電子科学技術振興財団の研究
助成および, 文部省科学研究費補助金による
f l 1 1 l c t i o l l a l d c c o I I I I ) ( ) S i t i ( ) 1 l s文
, いれ a n 7 ち冴 5 0 化サん P a c t t c
'″
D C さ句 7 わ A l ` サ o , / 阿 t どo / 1 θ o 7 げ C , C 7 , C C r ム s P ― D ■ σ
θθθり、
1)1)259-26と
参考文献
、
11
(l a13oritl111ls ft)rB()()lcと
11l R E Bryallt,｀ Gral)11-1)as(ヽ
‐
｀
↓
t,V01C―
r』EE分 ,7パ θθ?I,Pィ
fllllcti()11 11lallil)11lati()11、
、Y o k o l l a I ェ l a l J a l ) a l l ↑J a 1 1 2 6 - 2 8 ‐
2000
d T SASaO‐ ｀
SI)c(:ti al ■
IIIt(ヽ
R S Sta■ koviと
, alェ
1)rCta―
サ
l F9ヽ
ど
S
,),んフ
さん。P,7↓ S177ル
ア
ti()11 0f TDDs,い,ん
c ScⅢで
Fθ?ス
o子
ο
サ
7ル
0メ
ら
Ctt
Tccあ,ぁ
■7と
ガ Sυ さ
,c,r, r7あ
●
"Cド
ol'llο
Ml・
や
N()v 2526‐ 1997
■M玉 θり、OSaka‐ JAl)all、
rs■き
(On th(l cstiIIla―
1ll)(ヽ
rd、｀
D ヽ IarIIla aII(lE A Tra(,111(‐
o 8 ‐A l l g 1 9 8 6 ‐1 ) 1 ) 6 F T - 6 9 1
3 5 、1 ギ
)r(1(lsisll allt01natioll aI)I)li―
ti()11()f10gic coIIIPICXityよ
｀AIl clltr()1)y111(,asllrc
Ⅲ
121 1( CllCllg all(l V D Agrawal、
, 'サ
07み
α子Cθ″
lrr,c″
↓
cゼ07み
ill yppθr』EE r″ル
サ
c,7ら
cati()1ls、
ity()f11111lti_01ltl)llt B001(lali fll11(jtioilsギて
for thc(iollll)1(1、
/五Sr,7" て
,
ガ
P,Occさ
,?ァ
￨サ
7ド
'つ
?れ
ィ
,↓
C'ぶ'7↓
て
ル
Cケ
立
)c
stす
手
ブ
?ィ
″
o,ァ
ι
a 抗o 7 あ
7 C 7C↓
t , 1 ) 1 ) 3 0 2 - 3 0 5J 、
llIIc 1990
D e れす, ぁ
ス“↓
σ0 7 4 ル
ぶつ?｀
ど、1)1)368-71、0(it 1990
“
rallg, ｀
Loぶ網 nctWOrk cost
111(111_
sis A11(1 01)tiIIIizatioll
l)〔
Logi(i syllth(卜
1朝 R W Cook alxl M J Flyllll、
1181 S ヽ
｀
'Mθ
サ、V01C-22,No 9、
跡a7パ σ,7rヮ
イ
“
all(l cIItr()1)y,"r』
」どち
1 1 l a r k l i s c r 8 1 v1 (i ,( rl Sc i、( ) 1 1 3 0 、「C 、J a l l 1 9 9 1
1)I)823-826、S(lpt 1973
-6-
Publication list 1998-2000
1988
u狙 (l T Sasao,“
Time_赴宙siOn
Fi HttZ Md.Hasan Bお
IIlultiple対
ng rcattzatiOns of multiplc_olltl)ut fullctions
Decision diagrams for discrcte
[1l R.Stankovic an(l T Sasao,“
'■3ta
functiOnsi Classincation and untted hterpretationず
α"冴 Sο“せ
れ Pac"c Des竹
D■ σ'98,Fel).1998,
れム“セ
οr/2oを
す
oれ θo,ザcrc,CC,■ JP‐
based on sh_ed ml述
diagatEIIS," rJrσ
ti‐
terIIllnal multiplc_valucd dccisiOn
β コ
確れs
r,げ
1/ol.E82-D,No.5,pp.925--932,ヽ
97切
航 tOれ a"″
Sr」s↓cれじ,
仁ay 1999
Functional decompositions us_
181T,SaSao and S,Kajihara,“
A hellristic a180五thm to design
121 D.Del)nath ttd T,Sasao,“
ing an automatic test pattem generator and a logic simぃ
AND― OR‐ EXOR threぃ
れ
lcvei networks,"A3ja aれ
材 Sθ“サ
lator,"■ OM/1Eβ β 舟戒cttat,oれar ИOT魅れη 。7あ五町じ
C Syれ,
PaC"C Dcsを
,ス “す
。れa↓サ
07あσ O″
ザCr.れcc, ASP‐ D■ θttJ,
け
れ。
3お,Lake Tahoe,CA,June 1999.
Peb. 1998.
191T.Sasa。 ,“Arithmetic tcrnary decisiOn diagraIIIs alld their
131 Hanz Md.Ht■ stt Babu and T.Sasac,“ Desitt Of IIlultiplぃ
,
apI)hcatiOns," ダοttrを
あゴ乃サ
cr″aサ
す
oれα! WorZ37JOP OれムPPr↓
outpllt net、
vOrks using tiIIle doIIlお
n multiple這
‐
cattο
れ3?メを
あC ttccど
l″
“rrer E響
.角
3ど
οれ'η6'確“ど
をDcsを■,
ng aIId
shared lnulti_terminal lnultiple va11led decisiOn diagraIIIs,''
‐
IRC筋 lど“r:er 9り ,ViCtOria,Callada,AugHst 20-21,1999。
朋 βど r73サ
C r7脇
サ
jOれar SyttP。抗碗 οれ肋輌れ,rc‐7ar“c″ぁりを
c,
Exact ttinimization of FPRMs
1101 D Debnath and TtSasao,“
pp 45-51,Fuklloka,JaPan,X/1ay 27-29,1998.
for incompletely spedned logic hnctiOIIs," Fo“
″,あ rれサ
cr_
14!J.Butier aIId T sasaO,``On the properties of IIlultiple―
れoセ,οttar"/。 rんsれοP o7P7ム PP,ca↓ ぢ
ο憾 Orあ c ttcαかれ「
切材cr
valued functiOns that are syml■ etric iII both variable
Japaれ立θれ ,れ arc“ サ
をDesをれ,律 CCか〃 “!rcr θθノ,ViCtOria,
mllles and labels," IEEど
r7Lサ
erれ所tοれar StyttP。3れ初 οれ
Callβda,Allgust 20-21,1999.
〃 “れば
uc材ぅ。すtc, pp. 83-89, Fukuoka, Japan, Arlay
Pre,,名′
Representadons of
[lJ Harlz Md.Hasall Babu alld T.Sasao,“
27-29,1998
multiple―
outゎ
ut ttnctiOns using bintty decision diagraIIIs
DECOMPOS:An integrated
[51 To SaSac and M.Matsuura,“
for characteristic functiOns,'' rgrcE 助
穂 . F七れ″αttc角‐
systeln for ilnctiOnal decOIIlposition,"■ OM/1EJ』
r乃を
cr_
セ
αる,h/01 E82,A,N。 .11,pp.2398-2406,Nov. 1999.
natぢθ几″!"わ r梅れo″ oれあο
んosお,Lake Tahoe,CA,
g,c Styれを
JuIIc 1998
61 Y Iguchi,T,Sasao,and M(Matsuura,“ 0■ properties of2 0 0 0
〔
Kleenc TDDs,"rarσ』 Trans.折げo rrr3
tott
aをan″
S73'CttS,
Ineters to lhd
11l To Sttac and K.Kurimoto,“ Three part■
ヾもl E81‐ D,No.7,pp.716-723,July, 1998.
fllnctiOnal decompositions,"ム
3'00"材 J。しを
あ PccttC DC―
171 HarlZ M(1.Hasran Babu and T SasaO,``Represcntatio■s
れA“セ
οttα
セ
じ
ο
れσο
7げ
ere,CC rASP‐
z)A σ
t tθ
θ
of inultiple‐
Output logic functi01ls by binary decision dia‐ 3む
の,pp.259264,YOkOhaIIla,Japan,Jall. 26-28,2000.
r施れοP
graIIIs for ttaracteristic hnctions,"むれcどぜ乱れ巧/θ
Exact minimizatiOn of ixed
ηSyれ
ο
せ
んcsお■ηtt Syuサ
121D.Debnath and T.Sasao,“
c77t r,'qgraサ
,oれ
″
あCtt Tccん
7P20:0‐
。
メ五
通りり, p p . 1 0 1 1 0 8 , S e, nJ da お
" c s rs ■
p a l l , O c t . 1 9 -polarity Rβed_MIuller expressions for incompletely speci‐
20,1998.
Shared ml■lti‐
181 Httz Md,Hasan Babu alld To SttaO,“
terIIlillal b血
functiOIIs,"rgrσ
征 y decision diagraIIIs for IIlultiple‐
『
σ ο碗拘切れ,cat,ο れ3 a砲
ち
酔 αれ3.P“
れどaれ。れサαる
冴 σ ο碗 7“ をcr SC'Cれ
。utput
ザ
β ′ccサ門砲ぢC5,
CCS, Vol. E81‐
A,
aed ttnctions,"■3'こαれ'Sο竹セ
あPacttC De3を角Дuサ
ο砲4抗0れ θ07】
セTCnCC IASP‐Z)Дσ
ttθ
θの,pp.247-252,YOkO‐
haIIla,Japan,JaII. 26-282000.
A hard‐
[31Y.Iguchi,T,St■ sao,M.Matsuura,alld A Iseno,“
ware simulation engine based on decisiOn diagraIIIs,'' ム s,a
aれど Jο “を
あ Pac"C Desを
NO. 12,pp.2545-2553,Dec. 1998.
D■
れ ■ 況 οttα ttοれ σο7げ ereれ CC rA品
み
σ ttθθの ,pp.73-76,YOkOhalna,Japall,JaII.26-28,
2000
Mininiza―
141H述 z Md.Hassan Babu and TsutOmu Sttao,“
tion of lnultiple‐
valued decisiOn diagrams using saIIIPLng
Rcal―
method,"PTο ccc流れ。sげサ
れCS仰け
れcsts aれ材Sv3をctt rttc。陶 _
11l Y Iguchi,T SasaO,M Matsuura,and A.Iseno,“
izatiOn of regular ternttyc loび
ttnCtiOns using doubletrぶ
l
を
あれげ脇 ″冴挽 c あ
砲ο『
θθノ, K y o t o , J a p a l l ,
" e 3 r S ■ S I M ■2 θ
iogic,"■
sta α
れ冴Sο“を
あPacttC Desをれ去“tο
砲況jο
れσο
れ,
Apri1 6-7,2000.
u and T SasaOrRepresentations of
ル r e ηC C , ■S P ‐D ■ σりθ, p p . 3 3 1 - 3 3 4 , J a n . 1 9 9 9 .
いlH誼 Z Md.Hasan Bお
21 D Debnath alld T,Sasao, “ Fast BOoleaII Inttchttg
mllltiple―
output sH′
itching functiOns using lnultiple‐
valued
〔
1999
' ■Sぢ
under variable permutation using represcntativeず
α
α7あ
】SO“と
あPac"c Dcs'すれム“サ
ぢ
ο"σ ο駒汀
οttaサ
crcace,■SP‐
'θ
θ,pp.359-362,Jan. 1999,
tcんあ。助 cο即ル r五 ?すぢ
C Sy,セれ●313,Kluwer
131T.SaSa。 ,s切ガ
AcadeHlic Pubttshers,1999
DAσ
1剣T,Sasa。 , “TOtally undecomposable ttnctiOns: ap‐
valued decompositions,"
plicatiOlis to enlcient multiple‐
rβJ』ぁサ
cTれ。,tο
れar Sυ
ttPost“
砲 οれ虹、lt"!c,V化!し
eどあり tc,
pp.59-65,Freiburg,German〕
与MIay 20-23,1999.
Shared
いl HanZ Md.Hasan Babu alld Tsutomu SasaO, “
multiple―
将
ミ ued decision diagraIIIs for multiple‐output
' Jθ
サ
ο,ar
せ
んrれ
を
erれ
aを
pseudO,Kronecker decisiOn diagramsず
“施ヵrc_/aれ e芝あり ,c,POrtlaIId,Oregon,
SyfZP03れ碗 0れ肋「
U.S.A.,MIay 23-25,2000.
161T,Stta。 ,“On the number Of dependent variables fOr in―
completely sPecined multiple― valued ttinctions,"Jθ せ
ん r73‐
サ
erれαttο
ttar SyttP。5れ砲 ο■ 2γ“れ"!c‐Iれ施Cどあθ"c,POrt_
lalld,Ore30■ ,U,S.A.,Mray 23-25,2000.
“
tl Y Iguchi,T.SasaO,and M Mttsuur可 Implementation of
'Jθ
IIluitiple,o工
tput functions using PROttIDDsギ
を
あr72を
cr‐
れαを
われar SyttPosぁれ οれM“れ"re‐yarttcど
ちり,c,POrtlalld,
Oregon,U.S.A.,NIay 23-25,2000.
functiOns,力
rβ』″ r73を
Crれ
oサ
'9■
ar SvttPosど
“7720れ眼ヽれ"!e‐ 181 To SaSa。
,“A New exPaIIsiOn Of symmetric ttnctiOns and
ycr“c】と。g↓
c,pp. 166-172, Freiburg,German〕
thett apphcation to non‐
disjOint ttnctional decoIIlpOsi‐
l A/1守 2023,1999.
tiOns fOr LUT‐
type FPCAs,"r乃サ
cTれ
αを
'o砲
ar worた
Jあ
ο
n
P θ
Multiple,valued ttnimization
あ?。
,c Sryη
サ
んo3お
ornia,U.S,A.,May 31161D.Debnatll and To Sasao,“
,Dalla POint,Cal∬
to optinizc PLA with Output Puity gates,"Iβ
BB rれを
er―
Julle 2,2000,
7腕サ
われこど挽″ηosれ碗 ο砲虹、!を
c,pp.99-104,
"re_7ぁれ況ぁりを
FIrcil〕
1lrg,CermFanJ,WIay 20-23,1999
- 7 -

Download Report