研究室紹介

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

1. インターネット用のパターンマッチング回路．
2. ＦＰＧＡ（書換え可能なＬＳＩ）の設計理論．
3. 新しいタイプのプログラマブル論理素子．
4. 論理関数表現のためのデータ構造（ＢＤＤとその拡張）．
5. ＥＸＯＲを用いた論理設計．
6. 多段論理回路の設計．
7. 論理回路の複雑度解析．
8. 多値論理の応用．
9. スペクトル変換を用いた論理設計．

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

　以下のようなパターンマッチングを行う論理回路を研究中である. 　いずれも, 企業と共同研究中であり, 特許出願中でもある.

完全マッチング

　ビットパターンが, 完全に一致したものを見つける. インターネットのアクセス制御回路に使用する. 入力数は48から128で, パターン数は数万程度までである.

LPMマッチング

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

正規表現マッチング

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

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

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

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

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

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

　ｎ変数論理関数を計算機上で表現する方法は多数ある．

真理値表

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

論理和形（ＳＯＰ）

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

ＢＤＤ（二分決定グラフ）

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

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

　従来の論理設計法は，ＡＮＤ，ＯＲ，及びＮＯＴを基本としている． しかし，算術演算回路，誤り訂正回路，通信用回路等では，ＥＸＯＲを活用するとゲート数の少ない回路が設計できる． 本研究室で開発した高性能ＡＮＤ−ＥＸＯＲ形論理式の簡単化プログラムＥＸＭＩＮ２は世界的に有名である． １９９５年の８月に幕張で，Reed-Muller国際ワークショップを開催した． ２００９年の５月には、那覇で、Reed-Muller国際ワークショップを開催する予定である。

多段論理回路の設計．

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

論理回路の複雑度解析．

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

多値論理の応用．

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

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

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