n変数論理関数の面積時間複雑度

スポンサーリンク

概要

• 論文の詳細を見る

• 半導体技術，VLSI技術の進歩に伴い，VLSI回路に特有な費用の尺度が用いられるようになってきた．VLSI回路においては，回路に含まれるゲート数よりも，回路の占める面積がより適当な尺度と考えられる．Brent，Kungらは，VLSI回路に適したモデルを提案し，回路の面積Aと計算時間Tとの積（ATα：α0）を尺度として，乗算器，加算器などの複雑さを議論している．本論文では，Brent，Kungのモデルに基づき，一般のn変数論理関数を計算する回路において，面積時間複雑度が，ATα＝Ω（n（logn）α－1）（α1）であることを示す．又，n変数論理関数のうちで，回路がATα＝O（n（logn）α－1）で実現できる関数が存在することを，実例をあげて示す．

• Institute of Electronics, Information and Communication Engineersの論文
• 1981-08-20

著者

• 和田 幸一

  名古屋工業大学電気情報工学科

関連論文

• 境界配置条件を課したVLSIモデルにおける面積時間複雑度
• 3. ハードウェアアルゴリズムの設計法 3.2 ハードウェアアルゴリズムの記述と検証 (VLSI向きハードウェアアルゴリズム)
• 2. ハードウェアアルゴリズムの基礎理論 2.3 VLSIモデルと面積複雑度 (VLSI向きハードウェアアルゴリズム)
• VLSIモデルにおけるd次シャフルグラフの埋込み面積について
• 面積時間積最適な論理関数の構成について
• VLSI回路モデルにおける面積複雑度
• n変数論理関数の面積時間複雑度
• 面積時間積最適な論理関数の構成について
• n変数論理関数の面積時間複雑度
• VLSI回路モデルにおける面積複雑度
• VLSIモデルにおけるd次シャフルグラフの埋込み面積について
• 境界配置条件を課したVLSIモデルにおける面積時間複雑度

もっと見る 閉じる

スポンサーリンク