研究室紹介

九州工業大学　電子情報工学科
笹尾　勤　研究室（電子情報基礎講座）


論理回路をコンピュータを用いて設計するための基礎理論を研究している．

主な研究テーマ
  1. 論理関数表現のためのデータ構造（ＢＤＤとその拡張）．
  2. 新しいタイプのプログラマブル論理素子．
  3. ＥＸＯＲを用いた論理設計．
  4. 多段論理回路の設計．
  5. ＦＰＧＡ（書換え可能なＬＳＩ）の設計理論．
  6. 論理回路の複雑度解析．
  7. 多値論理の応用．
  8. スペクトル変換を用いた論理設計．
研究室には外国人学生や外国人客員教授がいるので，自然に英語がうまくなる．

論理関数表現のためのデータ構造（ＢＤＤとその拡張）．

　ｎ変数論理関数を計算機上で表現する方法は多数ある．
真理値表
　関数部のみを記憶すれば，２nビットで表現できる． ｎ＝５のとき，32ビット計算機では１ワードに納まり，高速に演算が実行できる． また，表現が一意的という特長もある． n=24程度(16MB)までは実用的であが，ｎ≧30の時はメモリが大きくなりすぎる．

論理和形（ＳＯＰ）
　一つの積項は２ｎビットで表現できる．ＡＮＤ，ＯＲ，ＮＯＴ等の処理が比較的容易であり，多数のアルゴリズムが開発されている．また，ＳＯＰはＡＮＤ−ＯＲ二段回路に対応している．パリティ関数や加算器などを表現するには，ＳＯＰは２nに比例した大きさとなる．一般に，一つの関数を表現するＳＯＰは一意的に決まらない．

ＢＤＤ（二分決定グラフ）
関数とその否定を同時に表現できる．また，変数の展開順序を決めれば，ＢＤＤは 一意的に定まる．ＡＮＤ，ＯＲ，ＮＯＴ演算や等価性判定が高速に実行できる．多くの実用回路に対しては，ＢＤＤはそれほど大きくならない．展開する変数の順序によって表現の複雑度が大きく変わる．最悪Ｏ(2n/n)個の節点が必要である．多くの実用的な関数に対して，真理値表やＳＯＰよりもＢＤＤの方がメモリは少なくてよい．そのため，論理設計の種々の問題は，ＢＤＤで表現すると能率よく解決できる場合が多い． 　本研究室では，ＢＤＤの拡張として，スペクトル変換グラフや ＳＭＴＢＤＤ（shared multi-terminal binary decision diagram)を開発した．

新しいタイプのプログラマブル論理素子

本方法は, LUT カスケード法と呼ばれ, 以下の特徴を有する. 1. 論理関数をRAM/ROM のカスケードで表現する. 2. 上のカスケードをメモリとシーケンサで模擬する. 3. 配線部分は, 直接実現せず制御部で仮想的( ソフトウエア的) に行う. 4. 制御部は, 関数に応じて書き換える. これにより, 配線の問題が解決できる. 従って, 設計者は, 論理設計に集中でき, 回路の段数の削減と, ROM/RAM 容量 の削減が問題となる. LUT カスケード法は, 「ソフトウエア」と「ハードウエア」の中間の性質をもつ. つまり, 「メモリ部分を書き換える」という意味では, ソフトウエアの性 質をもつが, 「配線を記憶する制御部を書き換える」という意味では, FPGA などのハードウエアの性質をもっている. ただし, 設計は, 従来の論理回路やプログラムの設計法とは根本的に異なる手法(BDD を用いた関数分解) を用いる.

ＥＸＯＲを用いた論理設計．

　従来の論理設計法は，ＡＮＤ，ＯＲ，及びＮＯＴを基本としている． しかし，算術演算回路，誤り訂正回路，通信用回路等では，ＥＸＯＲを活用するとゲート数の少ない回路が設計できる． 本研究室で開発した高性能ＡＮＤ−ＥＸＯＲ形論理式の簡単化プログラムＥＸＭＩＮ２は世界的に有名である．

多段論理回路の設計．

　多段論理回路は二段論理回路に比べ，ゲート数や接続線数が少なくてすむことが多い． 本研究室では、多段論理回路設計の基礎となる関数分解法を研究している.

ＦＰＧＡ（Field Programmable Gate Array)の設計理論．

ＦＰＧＡでは基本モジュールとしてＰＬＡ(Programmable Logic Array)，ＲＯＭ(read only memory)，および ＭＰＸ(multiplexer)を考え，与えらた論理関数をモジュールを用いて能率よく実現する方法について研究する．

論理回路の複雑度解析．

　与えらた論理関数を論理回路として実現する際，必要なゲート数や接続線数の予測が重要である． ゲート数や接続線数は実現法や，実現すべき関数のクラスによって異なる． 任意のｎ変数関数を実現するために必要なゲート数は，ｎの指数関数となる． 論理回路の複雑度を調べることによって，回路実現に必要なゲート数や接続線数を予測できる．

多値論理の応用．

　多値論理は，二値論理を一般化したものである． 最近は，フラッシュ・メモリなどにも使用されている． １９９８年の５月に福岡で，多値論理国際シンポジウムを開催した．

スペクトル変換を用いた論理設計．

　論理関数のスペクトルを解析することにより，論理関数の大域的性質が明らかになり，それを用いて能率の良い回路を設計できる． これは，アナログシステムの設計や解析にスペクトラル解析が有効であるのに似ている． スペクトラル解析をデジタルシステムの設計や解析に利用する手法は従来から知られていた． しかし，ｎ変数論理関数のスペクトルを計算するために２nの行列を用いる計算法しか知られておらず，ｎ＝３０程度の問題でも，計算機の記憶容量を越えてしまい，実用上利用不可能であった． しかし，最近，ＭＴＢＤＤ（多端子二分決定グラフ）を用いることにより，n＝100以上の論理関数のスペクトラムを短時間内に計算する方法が開発された． この方法を用いることにより，スペクトル解析を実用回路の設計に利用できる可能性が出てきた． 本研究では，論理関数のスペクトルを解析することにより，論理関数の大域的性質を解析し，それを用いて回路を能率よく設計する方法について研究を行う．
Back