面積時間積最適な論理関数の構成について

概要

論文の詳細を見る
VLSI回路においては，回路面積と計算時間が重要な評価尺度であり，Thompson，Brent- Kungらは回路を面積と計算時間で評価するVLSIモデルを提案した．本論文では，Brent-Kungによって，提案されたVLSIモデルと類似のモデルのもとで，基本的な論理関数に対して，面積時間積が最適になる回路構成について議論する．ここでは，一般のn入力m出力論理関数のクラスに対して，面積時間積（ATα:α1）の下界を与え，復号化関数，符号化関数，優先順位付符号化関数，対称関数族のある部分クラスに対しては，いずれもその下界のオーダで実現できることを示す．また，同一セルの繰り返しで実現される一次元一方向繰り返し回路により計算できるいくつかの関数に対して，面積時間積が最適となるような構成法を示す．さらに，本論文の構成を用いると，復号化関数，符号化関数などに対しては，計算時間を変化させた場合にも，面積時間積の評価基準のもとで最適になることを示す．
Institute of Electronics, Information and Communication Engineersの論文
1984-04-20