VLSI回路モデルにおける面積複雑度

概要

論文の詳細を見る
Thompson，Brent，Kungは，現実のVLSI回路特有の性質を考慮して，回路面積と計算時間を尺度としたVLSI回路モデルを提案しており，離散フーリエ変換，乗算などに対し，面積時間の上下界を議論している．本論文では，Thompson，Brent，Kungと同様のモデルを用いて，回路面積に着目し，n入力m出力論理関数を実現する回路の面積複雑度を議論する．すなわち，計算時間を考慮しない場合，回路の面積を最小限どの位小さくできるかを議論する．本論文では，一般のn入力m出力関数を実現する回路とその面積の関係を与え，その結果を用いて，デコーダ，エンコーダなどの回路の面積下界を示す．例えば，n入力2n出力デコーダ，n入力log n出力エンコーダに対しては，それぞれ，A＝Ω（n），A＝Ω（log n）となる．又，デコーダ，エンコーダなどは，ここで求めた下界のオーダで実現できることを示す．
Institute of Electronics, Information and Communication Engineersの論文
1982-04-20