研究室紹介

Last Modified:2011/03/28

九州工業大学 電子情報工学科
笹尾 勤 研究室(コンピュータLSIグループ)


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


主な研究テーマ
  1. インターネット用のパターンマッチング回路.
  2. FPGA(書換え可能なLSI)の設計理論.
  3. 新しいタイプのプログラマブル論理素子.
  4. 論理関数表現のためのデータ構造(BDDとその拡張).
  5. EXORを用いた論理設計.
  6. 多段論理回路の設計.
  7. 論理回路の複雑度解析.
  8. 多値論理の応用.
  9. スペクトル変換を用いた論理設計.
研究室には外国人学生や外国人客員教授がいるので,自然に英語がうまくなる.

インターネット用パターンマッチング回路.

 以下のようなパターンマッチングを行う論理回路を研究中である.  いずれも, 企業と共同研究中であり, 特許出願中でもある.
完全マッチング
 ビットパターンが, 完全に一致したものを見つける. インターネットのアクセス制御回路に使用する. 入力数は48から128で, パターン数は数万程度までである.

LPMマッチング
 Longest Prefix Matching (接頭語が, なるべく長く一致するようなパターンを見つける). これは, 英単語帳で, 検索している英単語を見つける作業に似ている. インターネットのルータで利用する. 入力数は, 32から128で, パターン数は, 数万程度までである.

正規表現マッチング
パターンを正規表現で記述する. ウイルスや, 迷惑メイルの検出に使う. パターン数は, 50万以上である.


FPGA(Field Programmable Gate Array)の設計理論.

FPGAでは基本モジュールとしてPLA(Programmable Logic Array),ROM(read only memory),および MPX(multiplexer)を考え,与えらた論理関数をモジュールを用いて能率よく実現する方法について研究する.

新しいタイプのプログラマブル論理回路

本回路は, LUT カスケードと呼ばれ, 以下の特徴を有する. 1. 論理関数をRAM/ROM のカスケードで表現する. 2.設計は, 従来の論理回路とは根本的に異なる手法(BDD を用いた関数分解) を用いる. 3.書き換えが容易である. 4.配線も容易である. 5.回路規模や遅延時間は、BDDから簡単に推測可能である.

論理関数表現のためのデータ構造(BDDとその拡張).

 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)を開発した.


EXORを用いた論理設計.

 従来の論理設計法は,AND,OR,及びNOTを基本としている. しかし,算術演算回路,誤り訂正回路,通信用回路等では,EXORを活用するとゲート数の少ない回路が設計できる. 本研究室で開発した高性能AND−EXOR形論理式の簡単化プログラムEXMIN2は世界的に有名である. 1995年の8月に幕張で,Reed-Muller国際ワークショップを開催した. 2009年の5月には、那覇で、Reed-Muller国際ワークショップを開催する予定である。

多段論理回路の設計.

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

論理回路の複雑度解析.

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

多値論理の応用.

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

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

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


Back