研究室紹介
九州工業大学 電子情報工学科
笹尾 勤 研究室(電子情報基礎講座)
論理回路をコンピュータを用いて設計するための基礎理論を研究している.
主な研究テーマ
- 論理関数表現のためのデータ構造(BDDとその拡張).
- 新しいタイプのプログラマブル論理素子.
- EXORを用いた論理設計.
- 多段論理回路の設計.
- FPGA(書換え可能なLSI)の設計理論.
- 論理回路の複雑度解析.
- 多値論理の応用.
- スペクトル変換を用いた論理設計.
研究室には外国人学生や外国人客員教授がいるので,自然に英語がうまくなる.
n変数論理関数を計算機上で表現する方法は多数ある.
- 真理値表
- 関数部のみを記憶すれば,2nビットで表現できる.
n=5のとき,32ビット計算機では1ワードに納まり,高速に演算が実行できる.
また,表現が一意的という特長もある.
n=24程度(16MB)までは実用的であが,n≧30の時はメモリが大きくなりすぎる.
- 論理和形(SOP)
- 一つの積項は2nビットで表現できる.AND,OR,NOT等の処理が比較的容易であり,多数のアルゴリズムが開発されている.また,SOPはAND−OR二段回路に対応している.パリティ関数や加算器などを表現するには,SOPは2nに比例した大きさとなる.一般に,一つの関数を表現するSOPは一意的に決まらない.
- BDD(二分決定グラフ)
- 関数とその否定を同時に表現できる.また,変数の展開順序を決めれば,BDDは
一意的に定まる.AND,OR,NOT演算や等価性判定が高速に実行できる.多くの実用回路に対しては,BDDはそれほど大きくならない.展開する変数の順序によって表現の複雑度が大きく変わる.最悪O(2n/n)個の節点が必要である.多くの実用的な関数に対して,真理値表やSOPよりもBDDの方がメモリは少なくてよい.そのため,論理設計の種々の問題は,BDDで表現すると能率よく解決できる場合が多い.
本研究室では,BDDの拡張として,スペクトル変換グラフや
SMTBDD(shared multi-terminal binary decision diagram)を開発した.
本方法は, LUT カスケード法と呼ばれ, 以下の特徴を有する.
1. 論理関数をRAM/ROM のカスケードで表現する.
2. 上のカスケードをメモリとシーケンサで模擬する.
3. 配線部分は, 直接実現せず制御部で仮想的( ソフトウエア的) に行う.
4. 制御部は, 関数に応じて書き換える.
これにより, 配線の問題が解決できる. 従って, 設計者は, 論理設計に集中でき, 回路の段数の削減と, ROM/RAM 容量
の削減が問題となる. LUT カスケード法は, 「ソフトウエア」と「ハードウエア」の中間の性質をもつ. つまり, 「メモリ部分を書き換える」という意味では, ソフトウエアの性
質をもつが, 「配線を記憶する制御部を書き換える」という意味では, FPGA などのハードウエアの性質をもっている.
ただし, 設計は, 従来の論理回路やプログラムの設計法とは根本的に異なる手法(BDD を用いた関数分解) を用いる.
従来の論理設計法は,AND,OR,及びNOTを基本としている.
しかし,算術演算回路,誤り訂正回路,通信用回路等では,EXORを活用するとゲート数の少ない回路が設計できる.
本研究室で開発した高性能AND−EXOR形論理式の簡単化プログラムEXMIN2は世界的に有名である.
多段論理回路は二段論理回路に比べ,ゲート数や接続線数が少なくてすむことが多い.
本研究室では、多段論理回路設計の基礎となる関数分解法を研究している.
FPGAでは基本モジュールとしてPLA(Programmable Logic Array),ROM(read only memory),および MPX(multiplexer)を考え,与えらた論理関数をモジュールを用いて能率よく実現する方法について研究する.
与えらた論理関数を論理回路として実現する際,必要なゲート数や接続線数の予測が重要である.
ゲート数や接続線数は実現法や,実現すべき関数のクラスによって異なる.
任意のn変数関数を実現するために必要なゲート数は,nの指数関数となる.
論理回路の複雑度を調べることによって,回路実現に必要なゲート数や接続線数を予測できる.
多値論理は,二値論理を一般化したものである.
最近は,フラッシュ・メモリなどにも使用されている.
1998年の5月に福岡で,多値論理国際シンポジウムを開催した.
論理関数のスペクトルを解析することにより,論理関数の大域的性質が明らかになり,それを用いて能率の良い回路を設計できる.
これは,アナログシステムの設計や解析にスペクトラル解析が有効であるのに似ている.
スペクトラル解析をデジタルシステムの設計や解析に利用する手法は従来から知られていた.
しかし,n変数論理関数のスペクトルを計算するために2nの行列を用いる計算法しか知られておらず,n=30程度の問題でも,計算機の記憶容量を越えてしまい,実用上利用不可能であった.
しかし,最近,MTBDD(多端子二分決定グラフ)を用いることにより,n=100以上の論理関数のスペクトラムを短時間内に計算する方法が開発された.
この方法を用いることにより,スペクトル解析を実用回路の設計に利用できる可能性が出てきた.
本研究では,論理関数のスペクトルを解析することにより,論理関数の大域的性質を解析し,それを用いて回路を能率よく設計する方法について研究を行う.
Back