順序回路の論理段数最小・最適状態割当て法

概要

論文の詳細を見る
安浦は、集積回路の集積度技術の進歩で素子数に関する制限は緩和されつつあり、それよりも計算時間の短縮、すなわち回路の論理段数の削減によって高速化をはかるような順序回路の設計評価基準を提案している。順序回路の動作速度は、クロックの周期によって決まる。クロックの周期は順序回路の次状態を計算する組合せ回路の論理段数に比例して決まる。従って、順序回路の高速化のためには次状態を計算する組合せ回路の段数が小さくなるように状態割当てをする設計をしなければならないというのが、安浦の議論である。論理段数を小さくするには、局所的な情報のみに依存する部分を見つけ出せばよいことから、安浦は局所計算可能性の概念も提出している。論理の局所化による段数最小化は、論理ゲートの活性化率を低減するので、低消費電力化にもつながる。我々は、順序回路の状態集合について、多ブロック分割の概念を導入して分割対の遷移グラフ表現を作った。そして、多ブロック分割を適当に2ブロック分割化することで状態遷移関数の論理段数最小の中で最小符号長をもつ状態割当てを得るアルゴリズムを考案した。
一般社団法人情報処理学会の論文
1990-03-14