第16回 回路とシステム(軽井沢)ワークショップ
プログラム

プログラム

このページのプログラムは，各論文に アブストラクトを付 けています．
アブストラクト無しの短いプログラムはこちらです．

会場受付時間


2003年4月26日(土)18:00〜20:00
2003年4月27日(日)8:00〜
2003年4月28日(月)8:00〜

セッション表

各セッションの論文データ一覧にリンクしています．

2003年4月27日(日)

ABaBdCD

カオス1
9:20-10:10

高速伝送
9:00-10:15

実現技術I
9:00-10:15

システム設計
9:15-10:15

カオス2
10:40-11:55

サンプリングシステム
10:45-12:00

実現技術II
10:30-12:10

リコンフィグラブル・コンピューティング
11:00-12:00

ユビキタス
10:45-11:45

非線形回路の数値解析
13:30-14:15

ユビキタス社会を支える高速アナログ回路とアンテナ技術
13:30-14:30

マスストレージ技術
13:30-14:30

ハードウェア設計
13:30-15:00

ハイブリッドダイナミカルシステム(1)
13:00-14:45

非線形回路の数値解析
14:15-15:15

ユビキタス社会を支える高速アナログ回路とアンテナ技術
15:00-17:00

マスストレージ技術
14:45-15:45

レイアウト設計手法
15:30-17:00

ハイブリッドダイナミカルシステム(2)
15:00-17:00

シグナルインデグリティ
15:30-17:00

マスストレージ技術
16:00-17:00

特別招待講演
懇親会


2003年4月28日(月)

ABaBdCD

地球シミュレータ
9:00-10:15

MOS回路
9:00-10:15

信号処理応用
9:00-10:40

プロセッサ合成
9:00-10:30

離散事象システム
9:15-10:15

非線形ディジタル信号処理
10:40-12:10

電源回路
10:45-12:00

招待講演
11:00-12:00

グリッド・コンピューティング
10:45-11:45

非線形振動
13:30-14:45

画像・映像処理技術I
13:20-15:00

システムレベル検証評価見積り
13:30-15:00

グラフ・アルゴリズム
13:00-15:00

非線形ネットワーク
15:15-16:30

画像・映像処理技術II
15:15-16:30

ペトリネット
15:30-16:30
フェアウエル企画


論文一覧(「○」印は発表予定者を表す)



2003年4月27日(日)

セッション SA1-1 カオス1 (9:20-10:10)
座長: 長谷川 晃朗 (通信総研)

題名理想ダイオードを含む区分線形強制ダフィング-ファンデルポール発振器に見られるトーラスとカオス
著者 関川 宗久, 三好 徹哉, 塚本 和孝, 稲葉 直彦(宇都宮大学工学部情報工学科)
keywords トーラス, カオス
abstract 本論文では，ダイオードを含む区分線形強制ダフィング-ファンデルポール発振 器の解析を行なっている．ダイオードを理想的なスイッチとみなす，ある種の特 異摂動法を用いることにより拘束方程式を導出できる．この場合，ポアンカレ写 像を一次元写像として厳密に導出できる．この写像を解析することにより，トー ラスとカオスの発生領域の境界を数式として陽に得ることができた．また，2パ ラメータ分岐図を作成した．Arnold's tongue，intermittency\cite{gucken}， カオスなどの興味深い現象が発生しており，周期解からトーラスへの転移と周期 解からカオスへの転移とが明確に識別可能となることを明らかにする．


題名フローティングゲートMOSFETを用いた非線形抵抗回路による一次元写像回路
著者 矢ヶ崎 知海, 大久保 政幸, 堀尾 喜彦(東京電機大学 工学部電子 工学科), 合原 一幸(東京大学 工学部 計数工学科)
keywords 一次元写像回路, 離散時間力学系, 非線形抵抗回路, フローティングゲートMOSFET
abstract フローティングゲートMOSFETを用いた非線形抵抗回路の電圧-電流(V-I)特性を一次元離散時間力学系の非線形写像関数として用いた一次元写像回路を提案する．フローティングゲートMOSFETを用いた非線形抵抗回路によれば，多様なΛ字型およびV字型さらにはN 字型のV-I特性が実現でき，かつ，それらの特性が外部電圧により調整可能である．提案方法ではこの非線形抵抗回路を写像回路として用いるため，同一の回路でさまざまな一次元離散時間力学系が構築できる．そのため，カオスを含む多様なダイナミクスを容易に得ることが可能である．さらに，提案回路は標準的なCMOS半導体プロセスで集積化できるため，応用回路の小型化，高速化が可能となる．本論文では上に凸な単峰写像，下に凸な逆単峰写像，さらにN 字型の写像回路の具体例を示し，個別部品を用いた実験を通して，提案手法の有効性を確認する．
セッション SA1-2 カオス2 (10:40-11:55)
座長: 長谷川 幹雄 (通信総研)

題名インターミッテンシー・カオスのマルコフ・チェインによるモデリング
著者 上手洋子(徳島大学工学部電気電子工学科 牛田研究室), 西尾芳文, 牛田明夫(徳島大学工学部電気電子工学科)
keywords インターミッテンシー, カオス, マルコフ・チェイン, ニューラルネットワーク, 組み合わせ最適化問題
abstract 本研究では，ロジスティックマップにより得られるインターミッテンシー・カオスのマルコフ・チェインによるモデリング方法を提案する．特に，インターミッテンシー・カオスの特徴であるラミナー部の持続時間長の分布に注目する．提案したモデルが，インターミッテンシー・カオスのよい性能を持つことを確認するためにインターミッテンシー・カ オスとマルコフ・チェインをTSP より解くのが非常に難しいといわれている二次割り当て問題(QAP)を解くホップフィールド・ニューラル・ネットワークに適用したときの性能について評価する．コンピュータシミュレーションの結果，提案したモデルがインターミッテンシー・カオスの性能とよく似た良い結果を示すことが分かった．


題名Chaos Neurons and Invariant Measures
著者 Masahiro Nakagawa(Nagaoka University of Technology)
keywords Chaos Neuron, Invariant Measure, Frobenius-Perron Equation
abstract 　In this paper, the Frobenius-Perron equations for a few chaos neurons are solved by means of the Fourier expansion scheme in order to derive the invariant measure. To explore the importance of the symmetry of the invariant measure, i.e. chaos neuron dynamics previously proposed, the simultaneous linear characteristic equation for the expansion coefficients will be numerically evaluated. It is also concluded that the symmetry of the invariant measure, which is found to be different for each chaos neurons, may be closely related to the ability of the chaos neurons applied to the practical applications with the neural networks, e.g. associative memory and learning model etc.　　

題名動的閾値法によってドライブされたベルヌーイ写像の一考察
著者 矢野 健治, 山田 洋己, 田中 清(信州大学工学部)
keywords カオス力学系, ベルヌーイ写像, 動的閾値法
abstract 本稿では，カオス軌道を生成する1次元写像のひとつとして知られるベルヌーイ写像の不連続点を写像反復毎に 動的に変化させる，動的閾値法(Dynamic Thresholding)によってドライブされたベルヌーイ写像を提案し， その統計的性質について検討している． 不連続点の動的なドライブ方法として(i)ランダムドライブ法および(ii)カオス的ドライブ法について検討し， それぞれの場合における軌道のエルゴード性，混合性，リアプノフ数などのカオスを特徴付ける性質について実験的に考察する．
セッション SA1-3 非線形回路の数値解析 (13:30-14:15)
座長: 山村 清隆 (中央大)

題名(招待)SPICEシミュレータの理工学分野への応用
著者 牛田 明夫(徳島大学)
keywords
abstract

セッション SA1-3 非線形回路の数値解析 (14:15-15:15)
座長: 丹野 真哉 (三洋電機)

題名An Interval Algorithm for Finding All Solutions of Nonlinear Resistive Circuits
著者 Naoya Igarashi, Kiyotaka Yamamura(Chuo University)
keywords 非線形回路, 数値解析法, 区間解析, 直流解析, 全解探索
abstract 非線形回路（あるいは区分的線形回路）のすべての直流動作点を求 める効率的なアルゴリズムを提案する。本手法は区間解析、双対単 体法、縮小法に基づくものである。提案手法により、非線形回路に 対しては、700変数の回路方程式の全解探索を初めて（数学的保証 付きで）行うことに成功した（ちなみにこれまでの最高記録は200 変数）。また区分的線形回路に対しては、線形領域数1000^1000の 超大規模問題の全解探索を初めて実用時間内で行うことに成功した （ちなみにこれまでの最高記録は線形領域数10^500）。


題名An Initial Solution Approach for Globally Convergent Homotopy Methods Solving Transistor Circuits
著者 Yasuaki Inoue(Waseda University), Saeko Kusanobu(University of East Asia), Makoto Ando(Chuo University)
keywords nonlinear circuit, circuit analysis, homotopy method, initial solution, unique solution
abstract To find DC operating points of transistor circuits, homotopy methods have been studied from various viewpoint. For efficiency of globally convergent homotopy methods, it is important to give an appropriate initial solution as a starting point. However, there are few studies concerning such initial solution algorithms. In this paper, initial solution problems in homotopy methods are discussed, and an effective initial solution algorithm is proposed for globally convergent homotopy methods, which finds DC operating points of transistor circuits efficiently. A new criterion on the initial solution necessary for guaranteeing the global convergence of homotopy methods is presented for a practical class of transistor circuits. Numerical examples show the effectiveness of the proposed algorithm.
セッション SA1-4 シグナルインデグリティ (15:30-17:00)
座長: 遠矢 弘和 (NEC)

題名瞬時IRドロップの解析手法
著者 林 左千夫, 南 文裕, 山田 正昭(東芝 セミコンダクター社)
keywords 瞬時IRドロップ, ダイナミック解析, 電源系ネットワーク
abstract 平均IRドロップの解析ツールは実用化されてきているが、瞬時IRドロップの解析ツールはまだ実用的なレベルには達しておらず、また、実測結果もほとんど存在しない。そのため、瞬時IRドロップの定量的な数値評価は、いまだ不十分な状況である。そこで、瞬時IRドロップの実用的な解析手法を構築し、いくつかのチップについて解析実験をして、分析・評価・考察を行った。その結果、瞬時IRドロップと平均IRドロップとでは1.5倍以上の違いがあり、遅延への影響としては 10%以上の差が生じることがわかった。


題名電源・グランド間容量が同時切替ノイズに与える影響の解析
著者 坂田 和之, 佐藤 高史, 横溝 剛一(（株）日立製作所半導体グループ/設計技術開発部)
keywords 同時切替ノイズ, 回路シミュレーション, 電源ノイズ, 伝送線路
abstract 同時切替ノイズの発生原理を，LSI, 基板の試作・測定結果とシミュレーションとの比較により解析した。従来のモデルでは十分な精度が得られなかった駆動信号線から離れた位置の電源・グランド電圧の変動を，シミュレーションにより再現した。電流経路を分析することで，立ち上がり時の同時切替ノイズはオンチップ容量を介した高周波電流の回り込みであることがわかった。この結果から，同時切替えノイズのシミュレーションではチップ内 I/O 回路の電源・グランド間容量のモデル化が重要であることを明らかとし，ノイズ低減に効果があるオンチップ容量の大きさを定量的に示した。

題名配線R(f)L(f)C抽出のための代表周波数決定手法
著者 土谷 亮, 橋本 昌宜, 小野寺 秀俊(京都大学 情報学研究科 通信情報システム専攻)
keywords 配線, 抽出, 周波数依存性
abstract 本稿では，配線の RLC 抽出に用いる周波数について議論する． 従来，回路設計には周波数に依存しない回路モデルが利用されてきた． しかし，周波数が高くなると表皮効果などの影響により，配線特性は周波数依存性を持つ． 周波数依存性のある配線特性を単一周波数でモデル化するためには，信号の伝搬特性に大きな影響を与える代表的な抽出周波数を適切に選ばなければならない． 本稿では，配線長から抽出周波数を決定する手法を提案する． 提案代表周波数を用いて配線をモデル化することで，様々な配線構造と入力パルスに対して精度の高い波形の解析が可能であることを実験的に確認した．
セッション SBa1-1 高速伝送 (9:00-10:15)
座長: 小林 春夫 (群馬大)

題名2.5V CMOS Fully Differential Low Power High Linearity Analog Line-Driver
著者 Khayrollah Hadidi(Electrical Enginnering Department, Urmia University, Iran), 大島 宗之, 佐々木 昌浩, 松本 隆(早稲田大学 理工学部 電気電子情報工学科／早稲田大学 大学院 理工学研究科)
keywords Line-driver, CMOS, Op-amp, Analog integrated circuit, Low voltage
abstract xDSLやfast-ethernet等で採用されているfull-duplex systemにおいて，重要な構成要素の一つにAnalog Line-driver(ALD)がある．ALDは低インピーダンスのメタリック・ケーブルを駆動し，アナログ信号を整流・伝送するための回路である． ALDに対する要求としては，伝送信号の線形性の維持，低消費電力化，高速化，小面積が挙げられる．しかし，近年のCMOSプロセスでは，微細化に伴う電源電圧の低下により，必要な出力電圧振幅を生み出すことが困難になってきており，その上で線形性を維持し，高速化を行うことは回路設計者にとって重要な課題となってきている． 本論文では，従来のプッシュ・プル インバータ バッファを改良することによって，電源電圧2.5V，抵抗負荷75Ωに対して10MHz，2Vp-pのアナログ信号を，高線形性を維持しつつ駆動可能な回路を提案する．また，シミュレーション結果より，消費電力124mW，全高調波歪THD -47.6dBを達成した．


題名10Gbps高周波信号伝送向けプリント基板回路構造
著者 豊田 英弘, 西村 信治(日立製作所 中央研究所), 金井 久亮(日立製作所 生産技術研究所)
keywords ブラインドVia, オープンスタブ
abstract 従来、10Gbps帯の電気伝送において、基板内層の信号線を使用し、かつ高密度に実装することは非常に困難と言われてきた。本研究ではプリント基板の材料と構造を検討することによって、上記信号を基板上に実装することを目指した。 電磁界シミュレーションから求めた基板構造に基づき，伝搬損失、クロストーク、Via部オープンスタブによる反射影響評価のための試作基板を作成した。本試作基板は基板材料として低誘電率・低誘電正接材料を用い、通常の積層基板（プリント基板）とマルチワイヤ基板にて製造した。 各線路の特性評価の結果、低誘電率・低誘電正接材料を用いることと、ブラインドViaとVia下層の信号層を使用することで、伝送距離を100mm（伝搬損失-3dB、10GHz時）まで使用可能となることが判った。以上により、10Gbpsの信号の電気伝送を基板内層を使用して実現できる事を示した。

題名ラティラル・バイポーラ・トランジスタの駆動力を使った高速で低エネルギーなCMOSインバータ回路
著者 秋濃 俊郎(近畿大学 生物理工学部 電子システム情報工学科)
keywords ラティラル・バイポーラ・トランジスタ, SOI, CMOSインバータ回路, 電流増幅率
abstract ４端子のnチャンネルとpチャンネルのMOSトランジスタは、各々３端子のnpnとpnpのラティラル・バイポーラ・トランジスタを構造的に内存する。それらトランジスタをSOI上に集積したCMOSインバータ回路を混成モードで動作させる。その入力電圧が立ち上る（下る）時にのみ同期して、一方のn（p）チャンネルMOSトランジスタのサブストレート、即ちベース端子へ順方向電流を流すプルアップ（プルダウン）MOSトランジスタの電流源を設け、その電流を電流増幅率hFE倍したドレイン、即ちコレクタ電流を引き出して駆動力を大幅に増やし、高速に放電（充電）する。同じタイミングで、他方のp（n）チャンネルMOSトランジスタのベース電流を零にして、そのトランジスタをオフ状態に保つ。更に入力が変化しない場合には、両方のベース電流を零にすると、通常のCMOS動作となり、電力を消費しない。例えば0.35μmCMOSプロセスの回路シミュレーション結果では、Vdd=1.0Ｖとして、またhFE=100のラティラル・バイポーラ動作を仮定して、混成モードのCMOSインバータ回路は、通常のCMOSと比べて、100×5.534fF＜この5.534fFは最小インバータ回路のゲート容量値＞という大きな容量負荷に対して、20倍も高速で、1/16という低いエネルギーとなる。
セッション SBa1-2 サンプリングシステム (10:45-12:00)
座長: 劉 洋 (アナログデバイセズ)

題名バンドパスΔΣAD変調器用マルチビットDAC非線形性のノイズ・シェープ・アルゴリズム
著者 傘 昊, 小林 春夫, 川上 慎也, 黒岩 伸幸(群馬大学 工学部 電気電子工学科)
keywords ∆ΣAD変調器, ノイズ・シェーピング, バンドパス・フィルタ, DA 変換器, エレメント・ローテーション
abstract 携帯電話や無線LAN 等の通信システムのRF受信回路に用いられるバンドパス∆ΣADCを高精度化するための一手法を提案する。∆ΣAD変調器はオーバーサンプリングとノイズ・シェープ手法で高分解能を実現するが、マルチビット∆ΣAD変調器を用いる場合、変調器内のDACの非線形性は ノイズ・シェープされずADC全体の精度を劣化させてしまう。そこで高精度バンドパス∆ΣADCを実現するために、わずかなデジタル回路を付加する事でマルチビットDACの非線形性をノイズ・シェープする新しいアルゴリズムを提案する。またその効果をMatlabによるシミュレーションで確認した。


題名ΔΣA/D変換器用コンパレータに関する考察
著者 井上 直樹, 島 健(神奈川大学大学院工学研究科)
keywords ΔΣA/D変換器, コンパレータ, 有限利得
abstract 近年ΔΣA/D変換器が限られたアナログ・コンポーネントを用いるだけで、低域のアナログ信号に対して高精度なA/D変換が可能であることから、オーディオ機器などを中心に使われるようになった。ただしオーバーサンプリング・コンバータであるがゆえに信号帯域の数十倍のサンプリング周波数が必要となり、このことは各コンポーネントに対し性能に対する要求が厳しくなる。とりわけA/D変換の要となるコンパレータが要求する性能について議論することは重要である。今回の報告書では、コンパレータのもつ利得が低くとも、高精度な変換が行なえる可能性について述べる。

題名Input-Dependent Sampling-Time Error Effects in MOS Sampling Circuits
著者 早坂 直人, 小林 春夫(群馬大学工学部電気電子工学科)
keywords Sampling, Jitter, Track/Hold, ADC, MOS Switch
abstract This paper analyses the input-dependent sample-time error in MOS sampling circuits caused by the finite slope of the sampling clock, and clarifies the following: (i) Input-dependent sampling jitter causes phase modulation in the sampled data. (ii) The formulas for SNR due to such sampling errors are explicitly derived. (iii) NMOS sampling circuits generate even-order harmonics, which are greatly reduced by using a differential topology. (iv) CMOS sampling circuits without clock skew between V_{clk} and V_{clkb} generate odd-order harmonics which a differential topology cannot help cancel, whereas circuits with clock skew generate even-order as well as odd-order harmonics. (v) For single-ended sampling circuits, the SNR of CMOS circuits without clock skew is better than that of NMOS circuits. (vi) NMOS differential sampling circuits are relatively insensitive to input-dependent sampling jitter effects, which would be the best regarding to the input-dependent sampling jitter effects.
セッション SBa1-3 ユビキタス社会を支える高速アナログ回路とアンテナ技術 (13:30-14:30)
座長: 兵庫 明 (東京理科大)

題名(招待)ユビキタス社会を支える低電圧高周波アナログ回路 ---電流モードアナログ回路と高周波集積化フィルタ---
著者 藤井 信生(東京工業大学)
keywords
abstract

セッション SBa1-4 ユビキタス社会を支える高速アナログ回路とアンテナ技術 (15:00-17:00)
座長: 兵庫 明 (東京理科大)

題名(招待)快適な無線通信環境を実現するためのスマートアンテナ
著者 庄木 裕樹(東芝)
keywords
abstract


題名(招待)無線通信回路技術動向
著者 小久保 優(日立)
keywords
abstract


セッション SBd1-1 実現技術I (9:00-10:15)
座長: 西川 清史 (都立大)

題名ΔΣ変調による1ビットディジタル信号の乗算手法
著者 折野 裕一郎, 黒澤 実(東京工業大学大学院 総合理工学研究科), 片桐 崇((有)プライムモーション)
keywords ΔΣ変調, 1ビットディジタル信号処理, 乗算器
abstract 高速かつ高精度なディジタル制御システムの低コスト実現を目指し、 1ビットディジタル信号処理による制御システムを実現するための乗算器要素の、 新しい手法を提案する。 等価値である2通りの実現方法を示し、 従来手法によるマルチビット演算より小規模で実現できる可能性を指摘する。 また、回路規模および演算精度を決定する設計パラメータ$N_Z$に対し、 実際にどの程度の精度が得られるのかをシミュレーションで評価する。 また周波数特性や位相遅れ、過渡応答特性といった演算器の特性を評価し、 1ビット乗算器の設計指針を明らかにする。


題名遺伝的アルゴリズムによる複数の定数乗算回路の最適合成手法
著者 天川 昌充, 佐々木 孝雄, 豊嶋 久道(神奈川大学 工学部 電気電子情報工学科 豊嶋研究室)
keywords 複数の定数乗算回路, 遺伝的アルゴリズム, 加算器数, 加算段数, 最適化
abstract 複数の定数乗算回路は，フィルタ，線形変換などディジタル信号処理においてしばしば現われる回路であり，回路規模，消費電力の点から演算量を最小とする合成手法が望まれる．著者らは既にスタック型オペレータを遺伝子とした遺伝的アルゴリズムによる合成方法を提案しているが，合成する回路によっては探索範囲が膨大となり最適化が困難になるという問題点があった．そこで本研究では，加算される枝の組合せに順位付けをし，各加算における順位を並べたものを遺伝子とし，加算器数と加算段数を評価する方法を採用する．これにより遺伝子集団中の適応度が上がるため，最適化の効率を上げることができる．

題名タブーサーチによるFIRディジタルフィルタの係数乗算ブロック最適化
著者 松本 有弘, 佐々木 孝雄, 豊嶋 久道(神奈川大学 工学部 電気電子情報工学科 豊嶋研究室)
keywords タブーサーチ, FIRディジタルフィルタ, 乗算ブロック, グラフ表現
abstract FIRディジタルフィルタの設計では，フィルタ係数を演算回路のビット長に合わせて 量子化する事により特性が劣化してしまう． 一方で，FIRフィルタは回路中の複数の乗算部を乗算ブロックとして演算器を 共有化させることにより回路の計算量の削減が可能である． FIRフィルタの設計では，この特性と回路規模の両面を考慮した設計が必要となる． 本研究では，グラフ表現された係数乗算ブロックに対してタブーサーチ (Tabu Search,TS)を用いることで，回路の計算量を変化させずに係数を 変化させ，量子化により劣化したフィルタ特性を向上させる方法を提案する．
セッション SBd1-2 実現技術II (10:30-12:10)
座長: 村松 正吾 (新潟大)

題名リフティング構成されたウェーブレットにおける乗算器係数感度の解析と応用
著者 外村 喜秀, 倉重 宏之, 岩橋 政宏(長岡技術科学大学 電気系)
keywords ウェーブレット
abstract リフティング構成によるウェーブレット変換は、フィルタ処理後にラウンディング処理を行うことにより帯域信号を整数値で表せる。そのため、可逆・非可逆統合符号化の一手法として注目されている。このリフティング構成されたウェーブレットの乗算器係数値は一般に実数値で与えられ、この係数を近似することで演算負荷の軽減が可能となりリアルタイム・ソフトウェア・デコーダや機能メモリにおいて有効であると考えられる。そこで本報告では、近似誤差すなわち乗算器係数の有限語長化誤差がウェーブレット内部をどのように伝播するかを9/7フィルタを例に調べ、いくつかの仮定のもとで再生信号の劣化量を理論的に解析する。そして、帯域信号の自己相関、相互相関、誤差変動の微小性が有限語長化誤差の分散値にどのように影響するかを定量的に評価する。また、得られた結果を乗算器係数の語長配分などに応用する。


題名整数DCTにおける乗算器係数感度の理論解析とその応用
著者 中川 光太郎, 杉森 新, 岩橋 政宏(長岡技術科学大学)
keywords 整数DCT, 有限語長化
abstract 可逆／非可逆・統合符号化の一手法として整数DCTが近年注目されており、これまでにいくつかの回路構成法は提案されているが、演算負荷の軽減を目的とした乗算器係数の短語長化についてはあまり報告されていない。西田らは短語長化の画質劣化への影響として画質係数感度を定義し、その値を実験的に求めて係数値の語長配分に応用した。しかし、係数感度の理論的な導出はなく、誤差発生のメカニズムは解明されていない。 そこで本報告では、整数DCT内部における短語長化誤差の伝播経路を調べることで、いくつかの仮定の下で画質係数感度を理論的に導出し、感度の入力依存性、最大有効語長、最適語長配分について定量的に解析・評価する。

題名ゼロ値予測に基づくDCT演算数削減手法の提案とその評価
著者 西田 敬宏(福岡大学大学院 工学研究科 電子工学専攻), 井上 弘士(福岡大学 工学部 電子情報工学科), モシニャガ ワシリー(福岡大学 工学部 電子情報工学科)
keywords 低消費エネルギー, DCT, 量子化, 値予測
abstract ゼロ値予測を用いたDCTの演算数削減手法を提案する。通常、ブロックを構成する8×8画素の全てはDCT処理により周波数成分に変換され、その後、量子化される。そのため、1ブロック当り、64回のDCT演算と64回の量子化演算が必要となる。これに対し、提案手法ではゼロ値予測を行うことで演算量を削減する。DCT処理において、複数の連続した演算結果がゼロ値であった場合、それ以降、当該ブロック内の全てのDCT演算結果をゼロ値と予測する。ゼロ値予測されたDCT結果に関しては量子化処理も不必要となる。

題名2-D Variable IIR Digital Filters with Improved Tuning Accuracy Using the Quasi-Newton Method
著者 ジャン ヒョクゼ, 川又 政征(東北大学)
keywords variable digital filter, 2-D IIR filter, reduced-dimensional decomposition form, quasi-Newton method
abstract This paper proposes a realization method of 2-D variable IIR digital filters with improved tuning accuracy using the quasi-Newton method. In our approach, the reduced-dimensional decomposition form is used as the prototype filter of the 2-D variable digital filters to suppress the degradation of frequency tuning accuracy. Furthermore, the compensation coefficients are added to the variable circuit in order to minimize the frequency tuning error due to the linear approximation. The optimal compensation coefficients are estimated by using the quasi-Newton method. A numerical example is presented to demonstrate the effectiveness of the proposed design method.
セッション SBd1-3 マスストレージ技術 (13:30-14:30)
座長: 木村 誠聡 (日本IBM)

題名(招待)塗布型高密度磁気記録媒体の最近の技術
著者 荒木 宏明(富士写真フィルム)
keywords
abstract

セッション SBd1-3 マスストレージ技術 (14:45-15:45)
座長: 尾保手 茂樹 (茨城大)

題名(招待)垂直磁気記録のための信号処理方式
著者 大沢 寿, 岡本 好弘(愛媛大学)
keywords
abstract

セッション SBd1-3 マスストレージ技術 (16:00-17:00)
座長: 木村 誠聡 (日本IBM)

題名(招待)超高速大容量のハードディスクを支える最新サーボ技術
著者 仙波 哲夫(日立グローバルストレジテクノロジーズ)
keywords
abstract


セッション SC1-2 リコンフィグラブル・コンピューティング (11:00-12:00)
座長: 木村 晋二 (早稲田大)

題名自己再構成可能論理デバイスにおける適応的負荷分散モデル
著者 多田 一仁(京都大学工学部電気電子工学科), 湯浅 隆史, 泉 知論, 尾上 孝雄, 中村 行宏(京都大学大学院情報学研究科通信情報システム専攻)
keywords 再構成可能論理デバイス, 動的再構成, 負荷分散
abstract PCA (Plastic Cell Architecture)は、デバイスの動作中にその一部を自ら書き換えることができる機能を有している。この機能の応用として、ある処理の負荷が増大した場合にそれを実行する回路を増やし、全体の性能向上をはかる適応的負荷分散処理が挙げられる。本稿では、PCA上で適応的負荷分散処理を実現するモデルについて検討を行う。本モデルでは、2つの処理が限られた資源（再構成領域）を共有し、負荷状況に応じてそれぞれの回路を増減させる。目的の処理を実行する回路ひとつと制御回路をひとつの単位とし、同じ構造を持つ単位が相互に局所的な連携を行なうことにより、全体として所望の機能を実現する。


題名PCAにおけるマスタ・スレーブ型適応的負荷分散モデルの提案と実装
著者 伊藤 俊之, 高橋 宏章, 北道 淳司, 黒田 研一(会津大学大学院コンピュータ理工学研究科)
keywords 動的再構成, PCA, 負荷分散, 自律再構成, FPGA
abstract 本稿では動的再構成可能なデバイスであるPlastic Cell Architecture(PCA)の自律再構成の特徴を活用した負荷分散モデルを提案する。提案するモデルは、過負荷を検出して分散させるための管理ユニットをマスタとし、複数の処理ユニットをスレーブとするマスタ・スレーブ型のモデルを採用している。提案するモデルでは管理ユニットの構成を変更することなく負荷の状況に適応して処理ユニットの数を増減させることを可能としている特長がある。再構成可能デバイス上で処理ユニットの数を負荷に適応して可変とするために必要となる管理ユニットおよび処理ユニットの構成条件について述べるとともに、本稿で提案したモデルを動的再構成可能デバイスであるPCA-1チップ上に実装し、実装サイズや処理オーバヘッドについて評価している。
セッション SC1-3 ハードウェア設計 (13:30-15:00)
座長: 橋本 昌宜 (京都大)

題名液晶パネル向け疑似濃淡画像生成回路の設計
著者 古家 眞, 陸 峰(大阪大学大学院情報科学研究科), 李 副烈(シャープ株式会社), 藤田 玄, 尾上孝雄(大阪大学大学院情報科学研究科), 築山修治(中央大学理工学部), 西 修司, 久保田靖(シャープ株式会社), 白川 功(大阪大学大学院情報科学研究科), 今井繁規(シャープ株式会社)
keywords 疑似濃淡化, TFT, システムオンパネル
abstract 液晶ディスプレイは，情報家電などの分野を中心として広く普及しており，現在，さらなる高性能化，多機能化に向けた技術革新に向け，画面（ディスプレイ）と周辺回路を同じ基板上に形成する一体化技術（システムオンパネル）の開発が進められている．本文ではシステムオンパネル技術を用いたTFT液晶パネル駆動回路向け擬似階調生成回路の設計について述べる．設計においてはTFTプロセスを考慮し，4並列のデータ処理ユニットを用いることで実時間処理を可能とする．3umTFTプロセスを用いて設計を行った結果，面積42mm×5mmで実時間処理可能な320×240液晶パネル駆動回路向け擬似階調生成回路を実現した．


題名遺伝的アルゴリズムによる定数乗算回路のハードウェア設計
著者 込宮 英幸, 佐々木 孝雄, 豊嶋 久道(神奈川大学 工学部 電気電子情報工学科 豊嶋研究室)
keywords 定数乗算回路, 遺伝的アルゴリズム, 桁上げ保存加算器, 半加算器
abstract 　定数乗算はシフトと加算で実現されるが，ハードウェア設計 としては加算に桁上げ保存加算器(CSA)を用いることが多い． 本研究では，機能評価の簡略化のため遺伝子を桁上げ伝搬加算器 (CPA)として表現し，機能を満たす遺伝子をCSAに変換し，その 回路規模，遅延時間を最小とするような回路を遺伝的アルゴリズム を用いて設計する方法を提案する。

題名Post-Floorplan Control Schedule under Max/Min Logic/Interconnect Delays
著者 Mineo Kaneko, Koji Ohashi(Japan Advanced Institute of Science and Technology)
keywords scheduling, RTL architecture, interconnect delay
abstract In this paper, we will focus our attention on post-floorplan scheduling problem and propose a novel model for control signal schedule under max/min logic/interconnect delay. Once binding and floorplan have been fixed, we will extract delay information of each signal transmission path. Using those delay information, we will formulate the problem to schedule control signals (not operations themselves). Peculiar features of our approach are; (1) our model can treat uncertainty/fluctuation of signal delay in the form of max/min delay. (2) our model not only consider interconnect delay in data-path part but also can handle interconnect delay from a controller to a component in data-path part.
セッション SC1-4 レイアウト設計手法 (15:30-17:00)
座長: 泉 知論 (京都大)

題名Network-Flow Based Delay-Aware Circuit Partitioning Algorithm
著者 Masato Inagi, Atsushi Takahashi(東工大集積システム専攻)
keywords partitioning, FPGA, I/O, delay, slack
abstract We propose a delay-aware circuit partitioning algorithm under I/O pins and size constraints. These two constraints are essential in multi-device implementation. The partitioning in multi-device implementation affects the delay much, since the propagation delay of inter-device connection is considerably larger than that of intra-device connection. Many approaches without considering delay fail to obtain a reasonable solution. Our partitioning algorithm is an enhancement of a partitioning algorithm based on flow network without considering delay, called PART. The idea of our enhancement is the reflection of timing slack into the flow network in order to avoid cutting tighter slack net. Our algorithm is implemented and applied to benchmark circuits. In experiments, we observed that the maximum propagation delay between registers is shorter and the number of sub-circuits is smaller compared with PART.


題名ソフトモジュールを含むフロアプラン探索の一手法
著者 糸賀 裕明(東京農工大学 大学院 工学研究科 電気電子工学専攻), 藤吉 邦洋(東京農工大学 工学部 電気電子工学科)
keywords フロアプラン, ソフトモジュール, 制約グラフ
abstract VLSI のレイアウト設計において，配置問題を解く前にしばしばフロアプランを求める．フロアプラン設計では，最適なフロアプランの探索を行うが，その探索の際にソフトモジュール（与えられた面積の下で縦横比を変更できるモジュール）の縦横比の決定も含めた最適化が望まれる．本稿では，チップの高さができるだけ増加しない様にチップの幅を 1 次元圧縮するための，縦横比を変更するソフトモジュール集合を効率的に選択する手法を提案する．この手法では，制約グラフの平面性に着目し，パスを求めることによってその集合が得られるグラフを作成して用いる．さらに，選択したソフトモジュール集合の各要素に対して縦横比を変更する発見的な手法を提案する．そして，本手法をフロアプラン探索へ組み込んで実験を行い，良好な結果を得た．

題名An ILP-Based Algorithm for Crosspoint Assignment under Crosstalk Constraints with Shielding Effects
著者 高島 康裕(北陸先端科学技術大学院大学), 中武 繁寿, 梶谷 洋司(北九州市立大学)
keywords crosspoint assignment, global routing cell, crosstalk, shielding effects
abstract This paper presents a crosspoint assignment (CPA) algorithm that takes into consideration crosstalk noise and shielding effects in deep sub-micron design. We provide the formulation for a single boundary based on an integer linear programming. In the formulation, we introduce d-pitch and {d,1}-pitch constraints to separate adjacent nets not closely to each other but considering shielding effects. Furthermore, we give discussion about an algorithm for multi-boundary. Experiments for industrial instances demonstrated that our algorithm attained compact assignments to avoid crosstalk violations in practical time.

セッション SD1-1 システム設計 (9:15-10:15)
座長: 酒井 良哲 (東芝)

題名オンデマンド輸送計画システムに対する運行計画手法
著者 中丁 和也, 宮本 俊幸, 熊谷 貞俊(大阪大学 大学院工学研究科 電気工学専攻)
keywords デマンドバスシステム, 運行計画, リアルタイム処理, 自律分散システム
abstract オンデマンド輸送計画システムの一つであるデマンドバスシステムを取り上げ，その運行計画手法を提案する．このデマンドバスシステムは利用客のバスへの割り当て問題，およびバスのルート作成問題をリアルタイムで高速に処理する必要がある．提案手法では，各バスに対応したバスエージェント群からなるマルチエージェントシステムにより問題の高速処理が可能であり，利用客の乗降車に対する遅延時間およびバスの運行コストを減らすことが目的である．また，計算機実験によって提案手法の検討を行った．


題名万葉集検索システムにおける異訓情報の生成法について
著者 中田 充, 大鶴 仁美, 葛 崎偉, 吉村 誠(山口大学教育学部)
keywords データベース, テキスト処理
abstract 万葉集には多くの写本や注釈書が存在し、和歌本文以外にも和歌の題詞、左注、異訓、異同などの様々な情報がある。万葉集研究では、これらの情報を含めて和歌を検索可能なシステムが必要とされている。このような背景のもと、筆者らは万葉集の和歌を異訓、異同などを意識することなく検索可能な検索システムを構築している。しかし、従来のシステムは、「ある読みの漢字が、万葉集において他にどのように読まれているか」という異訓情報をもたないため、漢字の読みによる柔軟な和歌検索ができないという問題がある。そこで、本研究では、異訓情報の生成について検討し、検索システム中の和歌データと幾つかの関連情報を元にした生成法を提案する。
セッション SD1-2 ユビキタス (10:45-11:45)
座長: 巳波 弘佳 (関西学院大)

題名(招待)ユビキタスサービスの技術動向と今後の展望
著者 大和 淳司, 阪本 秀樹, 久保田 稔(日本電信電話)
keywords
abstract

セッション SD1-3 ハイブリッドダイナミカルシステム(1) (13:00-14:45)
座長: 西尾 芳文 (徳島大)

題名(招待)非線形科学と計算機科学からみたハイブリッドシステム
著者 潮 俊光(大阪大学 大学院基礎工学研究科)
keywords 招待講演
abstract 招待講演


題名(招待)ハイブリッドシステムの形式的検証手法の動向
著者 山根 智(金沢大学 工学部情報システム工学科)
keywords
abstract

セッション SD1-4 ハイブリッドダイナミカルシステム(2) (15:00-17:00)
座長: 潮 俊光 (大阪大)

題名サンプル値区分的アファインシステムの最適制御とCPUの高速・省電力化制御への応用
著者 東 俊一, 井村 順一(東京工業大学)
keywords hybrid systems, sampled-data, piecewise affine systems, optimal control, controllability
abstract This paper discusses the optimal continuous-time control problem of a class of continuous-time piecewise affine (PWA) systems with the sampled-data autonomous switching, which we call here the sampled-data PWA systems. First, the optimal continuous-time controller is derived for the finite-time optimal control problem, and the feasibility for this problem is discussed in terms of the controllability notion. Next, this controller is applied to the high-speed and energy-saving control problem of CPU.


題名Synthesis of Hybrid Systems with Limit Cycles Using Piecewise Quadratic Lyapunov Functions
著者 Masakazu Adachi, Toshimitsu Ushio, Shigeru Yamamoto(Graduate School of Engineering Science, Osaka Univ)
keywords hybrid systems, limit cycles, Lyapunov functions
abstract This paper proposes a synthesis method for hybrid systems with nonsmooth limit cycles. In the proposed method, a given periodic orbit is splitted into some ellipsoidal curves, we calculate a piecewise quadratic Lyapunov function V(x) such that V(x) is constant on the curve, and we obtain a desired hybrid system with a stable limit cycle.


題名連続系の挙動を考慮に入れたPLCの動作検証
著者 小中 英嗣, 鈴木 達也, 大熊 繁(名古屋大学大学院工学研究科)
keywords PLC, 動作検証, ハイブリッドシステム
abstract シーケンス制御を実行する代表的な制御器にPLC(Programmable Logic Controller)があり，PLCを用いた制御系はこれまで離散事象系として扱われてきた。 PLCのプログラム言語としてラダー図やSFCなどがあるが，これらで記述されたプログラムの動作検証を行う場合，何らかの形で制御対象のモデルが必要となる。 従来手法では，制御対象を制御則同様，離散事象系としてモデル化し，閉ループを離散事象系として扱うことで制御則の検証を行っている。しかし，これらの手法では本来連続系として扱われるべき制御対象の挙動に関する情報が失われてしまう。 そこで本論文では制御対象を連続系としてモデル化し，制御対象のより細かな挙動を考慮した動作検証，とくに安全性検証に焦点を当てた検証アルゴリズムを提案する。

題名アポトーシスシグナル伝達経路の Genomic Object Net によるモデル化とシミュレーション
著者 土井 淳(山口大学大学院理工学研究科), 田中 由紀子(山口大学理学部自然情報科学科), 長崎 正朗(東京大学医科学研究所ヒトゲノム解析センター), 青島 均, 松野 浩嗣(山口大学理学部自然情報科学科), 宮野 悟(東京大学医科学研究所ヒトゲノム解析センター)
keywords シミュレーション, ペトリネット, バイオパスウェイ, バイオインフォマティクス, モデリング
abstract 我々は、ハイブリッド関数ペトリネットによって、生物システムのモデル化とシ ミュレーションを行うことを提案してきた。今回、ハイブリッド関数ペトリネッ トを記述するツールとして開発したGONを用いて、アポトーシスシグナルが伝達 され、細胞が核の断片化を引き起こすまでのパスウェイを記述し、シミュレーシ ョンを行った。その結果、Fasリガンドによって、カスパーゼが連鎖的に活性化 し、最終的にDNAの断片化を誘導する様子を再現できた。さらにツールのインタ ーフェイスの向上により、より生物学のモデルに近い表現になったことを紹介す る。これによって、GONで記述された生物モデルの理解と作成が容易になると考 えられる。

特別招待講演

題名(招待)産学連携は今後どうあるべきか
著者 白川 功(大阪大学 大学院情報科学研究科)
keywords 全体企画, 特別招待講演
abstract 全体企画「特別招待講演」


2003年4月28日(月)

セッション SA2-1 地球シミュレータ (9:00-10:15)
座長: 横溝 剛一 (日立)

題名(招待)地球シミュレータ
著者 平野 哲(地球シミュレータセンター)
keywords
abstract

セッション SA2-2 非線形ディジタル信号処理 (10:40-12:10)
座長: 棟安 実治 (関西大)

題名指紋復元のためのディジタル反応拡散システムの設計
著者 伊藤 康一, 青木 孝文, 樋口 龍雄(東北大学大学院情報科学研究科)
keywords 反応拡散システム, 非線形フィルタ, 画像復元
abstract 本論文では，ディジタル反応拡散システム(Digital Reaction-Diffusion System: DRDS)を用いたかすれた指紋画像を復元するアルゴリズムを提案する．ディジタル反応拡散システムは，反応拡散システムを時間・空間で離散化したモデルであり，生物系のテクスチャやパターンの生成に有用である．本論文では，かすれた指紋画像が与えられたときに，元の指紋パターンを復元することができるDRDSを設計する．また，本論文で提案する指紋復元アルゴリズムの処理を高速化するために並列Octaveを用いた並列化についても述べる．


題名分割型フィルタを用いたガウス性雑音と高発生確率のインパルス雑音の混合雑音除去手法
著者 山下 哲孝, 呂 建明, 関屋 大雄, 谷萩 隆嗣(千葉大学大学院自然科学研究科)
keywords 分割型フィルタ, 画像処理, ニューラルネットワーク, 雑音除去, 混合雑音
abstract 本研究では，ガウス性雑音と高発生確率のインパルス雑音の混合雑音を除去するフィルタとして,信号の削減とニューラルネットワーク(NN)を利用した，新しい分割型フィルタを提案する.提案したフィルタでは，入力信号から画素値の最大値側と最小値側の信号を削除する．削減処理によって，入力信号からインパルス雑音を除去することができ，残った信号列にはほとんどインパルス雑音が存在しない. フィルタの出力は，削減処理後の信号列と処理点の画素値を用いて推定する．出力値の推定はNNによって行う．NNが持つ非線形の入出力特性により，欠落した情報が補完され，良好な推定が可能となる．計算機シミュレーションを行い，PSNRと復元画像から提案するフィルタの有効性を確認する．

題名(招待)ディジタル信号処理の発展と今後の動向
著者 谷萩 隆嗣(千葉大学 工学部)
keywords
abstract

セッション SA2-3 非線形振動 (13:30-14:45)
座長: 和田 昌浩 (甲南大)

題名パラメータ励振されたLCR回路の漸近安定化と同期化
著者 井上 馨(同志社大学 工学部), 山本 茂, 潮 俊光(大阪大学大学院 基礎工学研究科), 加藤 利次(同志社大学 工学部)
keywords パラメータ励振, LCR回路, 時変システム, 漸近安定化, 同期化
abstract In this paper, firstly we analyze stability of time-varying systems represented by second-order vector differential equations based on the characteristics of its coefficient matrices. New sufficient conditions for asymptotic stability of the equilibrium points are derived. Then, an asymptotic stabilizing control method of parametric LCR circuit is discussed based on the obtained sufficient conditions. A method synchronizing two parametric systems is also given. The effectiveness of the results are discussed by some numerical examples.


題名平衡点のない区分線形系に発生する振動現象について
著者 芹澤 昌邦(湘南工科大学 工学専攻科 大学院生), 岡崎 秀晃, 中野 秀夫(湘南工科大学 システムコミュニケーション工学科)
keywords 非線形振動, 合成力学系, エネルギ関数
abstract スイッチング要素により切り換わる区分線形ベクトル場について解析する。対象とする区分線形ベクトル場の固有値の実部は負であり、また、区分線形ベクトル場の結合部は不連続である。さらに、この区分線形ベクトル場には平衡点が存在しないことが特徴である。電磁機械式発振機を具体例に、単純に２つの線形ベクトル場を接合した系には振動現象が発生しないことを、エネルギ関数を用いて証明する。また、電磁石の駆動回路を１次遅れ系でモデル化し、その１次遅れ系で２つの線形ベクトル場を結合すると、発振現象が起きることを数値シミュレーションにより確認する。さらに、実機による測定結果を示し、提案モデルの妥当性を確認する。

題名パルスで結合された積分発火モデルの同期現象について
著者 島崎 正直, 鳥飼 弘幸, 斉藤 利通(法政大学工学部情報電気電子工学科)
keywords 積分発火モデル, パルス結合系, 不応性, 同期現象
abstract 積分発火型ニューロンのパルス結合系は様々な同期現象を呈することができる。パルス結合系の同期現象の応用例として連想メモリや画像のエッジ検出などがある。また、生態の情報処理においてニューロンのスパイク列の同期が重要な役割を果たしているという指摘もある。この様にパルス結合系の同期現象の考察はニューラル情報処理を考える基礎となる。本稿では、積分発火ニューロン回路の新しいパルス結合系を提案し、各ニューロン回路の不応性が結合系の現象とパルス符号化能力に与える影響を解明する。
セッション SA2-4 非線形ネットワーク (15:15-16:30)
座長: 田中 衛 (上智大)

題名連想記憶モデルにおけるカオスと有限温度効果
著者 川村 正樹(山口大学 理学部), 徳永 隆治(筑波大学 電子・情報工学系), 岡田 真人(理化学研究所 脳科学総合研究センター)
keywords 連想記憶, ダイナミックス, カオス, 分岐, フラストレーション
abstract 連想記憶モデルでは記憶したパターンを想起できることが重要であり、そのダイ ナミックスを解析することが必要である。また、非単調ニューロンを用いた連想 記憶モデルにおいて、その想起過程でカオス的な振舞いが見られることが知られ ている。しかしながら、厳密な想起過程の解析がなされておらず、分岐構造など は明らかにされてこなかった。本研究では、フラストレーション誘因カオスが温 度によってどのように変化するかを議論する。有限温度(T>0)の場合、微視的 な状態は確率的に遷移する。しかしながら、この場合においても、巨視的状態方 程式は決定論的になり、系のダイナミックスを厳密に解析することができる。


題名経路探索のための興奮性ディジタル反応拡散システムの設計
著者 伊藤 康一, 永田 識, 青木 孝文, 樋口 龍雄(東北大学大学院情報科学研究科)
keywords 経路探索, 興奮性ダイナミクス, 反応拡散システム
abstract 本論文では，離散時間・離散空間で定義された抽象的な反応拡散システムのモデルであるディジタル反応拡散システム (Digital Reaction-Diffusion System: DRDS) を利用した最短経路探索アルゴリズムを提案する．DRDSは，能動的に信号や画像を生成する多次元のディジタルフィルタであり，用いる非線形反応関数を変えることで，さまざまなパターン・テクスチャ・構造を発生することが可能である．本論文では，神経インパルス伝導のモデル式であるFitzHugh-南雲システムの反応関数を用いたDRDSを提案し，これを用いて興奮性反応拡散ダイナミクスをシミュレートした結果を示す．そして，この興奮性を有するDRDSが発生する興奮波の性質を利用した最短経路探索アルゴリズムを提案し，迷路や障害物が配置された平面から最短経路を探索した実験結果を示す．

題名テンプレートライブラリを持つ連想記憶セルラーニューラルネットワーク
著者 神尾 武司, 森末 道忠(広島市立大学/情報科学部)
keywords 連想記憶, セルラーニューラルネットワーク
abstract セルラーニューラルネットワーク(CNN)はハードウェア化に適した ニューラルネットワークである。特に、空間的に一様なテンプレート を持つCNNは空間的に非一様なテンプレートを持つCNNと比較して、非 常に低いコストでハードウェア化が可能である。しかし、連想記憶CNN に関する研究では、性能の低さから前者のCNNはほとんど利用されてい ない。そこで我々は、『たった1つのテンプレートによってネットワー ク全体の結合が定義されるため、荷重値の保存と変更が容易に実行で きる』という前者のCNNが持つ利点に着目し、テンプレートをライブラ リ化することにより、前者のCNNを有効に利用した連想記憶システムを 提案する。

セッション SBa2-1 MOS回路 (9:00-10:15)
座長: 和保 孝夫 (上智大)

題名等価MOSFETを用いた低電圧動作可能なOTAの構成法
著者 河合 慶悟, 高頭 和博, 熊沢 利昭, 高井 伸和(東京工芸大学)
keywords 等価MOSFET, 低電源電圧, OTA
abstract Equivalent MOSFETs without cutoff region are proposed for rail-to-rail operation. Conventional equivalents MOSFETs are not suitable for low power-supply voltage because level shift voltage $V_{tune}$ is greater than threshold voltage. In this paper, an equivalent MOSFET which operates under low power-supply voltage is proposed. In order to realize a low power operation, level shift circuit whose shift voltage $V_{tune}$ can be set less than Vtn, is employed. As an application example, a rail-to-rail OTA is shown. SPICE simulations of the proposed equivalent MOSFETs indicate good performances.


題名可塑シナプスのためのΛ字形負性抵抗素子を用いた多値メモリセル
著者 佐伯 勝敏(日本大学理工学部電子情報工学科), 中島 平裕(日本大学大学院理工学研究科博士前期課程電子工学専攻), 関根 好文(日本大学理工学部電子情報工学科)
keywords アナログ回路, 多安定回路, 多値メモリセル, L字形負性抵抗素子, 可塑シナプス
abstract 本稿は，可塑シナプスのためのL字形負性抵抗素子を用いた多値メモリセルを構成することを目的に，まず，エンハンスメント型MOSFETでΛ字形負性抵抗素子を構成し，これを単位回路として並列に接続することにより，多安定回路が構成できることを明らかにしている。更に，構成した多安定回路を用いて多値メモリセルを構成する検討を行い，CMOSプロセスに適用可能なエンハンスメント形MOSFETでΛ字形負性抵抗素子を単位回路として並列に接続することで，外部電源により各安定点及び同期範囲が可変できる多安定回路が構成できることを明らかにしている。また，可塑シナプスへの応用を考え，一例として，10値メモリセルを構成し，書き込み及びデータの保持が可能であることを明らかにしている。

題名ニューロンMOSを用いた冗長2進数から2進数への復号器
著者 森本 康文(広島市立大学情報科学研究科), 坂本 政祐, 森末 道忠(広島市立大学情報科学部情報機械システム工学科)
keywords 冗長2進数, 復号器, ニューロンMOSFET, 桁上げスキップ加算器
abstract 冗長2進数から2進数への復号器について、桁上げスキップ加算器の 手法とニューロンMOSFETを用いた高速化を提案する。 復号器は本質的に減算回路であり桁上げ伝搬は避けられないので、 各種の加算器の高速化手法が有効である。 その内、桁上げスキップ加算器は入力を複数桁にブロック化して 各ブロックの処理を並列に行い、桁上げは各ブロックの伝搬条件を 検出し、スキップすることで高速化する手法である。 その際、桁上げスキップ経路が1レベル・マルチレベルのいずれに おいてもブロックの数に依存した遅延が生じるが、これをニューロン MOSFETを用いることで高速化する。 Hspiceシミュレーションによりその高速性を確認する。
セッション SBa2-2 電源回路 (10:45-12:00)
座長: 渡邉 健蔵 (静岡大)

題名スイッチング電源のEMI低減化回路と測定による検証
著者 定村 宏(群馬大学工学部電気電子工学科), 行方 真実(群馬県工業試験場), 光野 正志, 小林 春夫, 石川 信宣(群馬大学工学部電気電子工学科)
keywords スイッチング電源, スイッチングノイズ, EMI, EMC, スペクトラム拡散クロック
abstract This paper presents Electro-Magnetic Interference (EMI) reduction and measurement techniques　of DC-DC converters (switching regulators). We have already proposed a simple, inexpensive technique for intentionally broadening and flattening the spectrum of a switching regulator to reduce EMI. This noise spectrum broadening technique involves intentionally introducing pseudo-random dithering of control clock timing, which can be achieved by adding simple digital circuitry. In this paper we will report the measured results of switching regulators　that this technique can significantly reduce EMI to the DC-DC converter input voltage source, with regards to　peak detection, quasi-peak detection and average detection.　The measurements were performed using　a standard EMI measurement system in an electro-magnetic　shield room　(anechoic chamber).


題名Design of Class DE Amplifier with Any Output Q, Any Duty Ratio and Switch on Resistance
著者 Satoki Oshikawa, Hiroo Sekiya, Jianming Lu, Takashi Yahagi(Graduate School of Science and Technology, Chiba University)
keywords Class DE amplifier, Design procedure, Output Q, Duty ratio, Switch on resistance
abstract This paper presents a new design procedure for class DE amplifier. And a design of class DE amplifier with any output Q, any duty ratio, and switch on resistor is carried out. The feature of the proposed design procedure is that the waveform equations never be needed. The design procedure requires only circuit equations and the design specifications. When circuit equations are got, the other procedures for computation of design values are carried out with aid of computer. Therefore, we can design class DE amplifier with any conditions, namely, with any output Q, any duty ratio, switch on resistance and so on. We can denote the design values and output capability of class DE amplifiers with any output Q, any duty ratio, and switch on resistor by using proposed design procedure. By carrying out the circuit experiments, we find that the experimental results agree with the calculation results quantitatively, and show the validity of the proposed design procedure.

題名チャージポンプ電源回路の突入電流とその対策
著者 名野 隆夫, 女屋 佳隆(三洋電機 セミコンダクターカンンパニー), 柏瀬 賢二, 小林春夫(群馬大学 工学部 電気電子工学科), 小林 一行, 鈴木 達也, 逸見 和夫(三洋電機 セミコンダクターカンンパニー)
keywords チャージポンプ回路, 突入電流, ＤＣ−ＤＣ変換器, 高電圧発生回路, 電源回路
abstract 先に我々は携帯機器応用のための高効率・大電流出力可能なチャージポンプ電源回路を開発した。しかし電源投入時に大きな突入電流が流れる問題点があった。そこでこの論文では突入電流の問題を解析し、またその対策回路を考案しシミュレーションで有効性を確認した。考案した対策回路は実際のチャージポンプ電源回路に組み込む予定である。



セッション SBd2-1 信号処理応用 (9:00-10:40)
座長: 比嘉 良人 (日本TI)

題名ダブルトーク問題を考慮したVolterra適応フィルタで用いるエコーキャンセラアルゴリズム
著者 竹市 嘉一郎, 古川 利博(東京理科大学), 三村 昌義(慶應義塾大学), 金子 聡(東京理科大学)
keywords エコーキャンセラ, ダブルトーク問題, Volterra適応フィルタ, OECLMSアルゴリズム, Gram-Schmidtの直交化法
abstract エコーキャンセラにおいて，従来よりもエコーを減衰させるには，エコー経路の非線形性成分を考慮する必要があり，Volterra適応フィルタを用いた様々な手法が提案されている．それらの手法の多くは，シングルトーク問題にしか対応できず，非線形エコーキャンセラにおけるダブルトーク状態に関しての決定的な解決策には至っていない．本論文では，ダブルトーク問題を考慮したOECLMSアルゴリズムの考えを利用し，2次Volterra適応フィルタにおけるエコーキャンセラアルゴリズムを提案する．本手法は，Gram-Schmidtの直交化法を用いることで収束速度の改善を図っている．


題名連立方程式法に基づく分散型マルチチャネル能動騒音制御システム
著者 棟安実治(関西大学工学部電子工学科), 若杉友美, 香川健一(広島大学工学部), 藤井健作(姫路工業大学工学部), 雛元孝夫(広島大学工学部)
keywords 能動騒音制御, 分散型制御器, マルチチャネル, 適応フィルタ, 連立方程式法
abstract これまで提案されているマルチチャネル能動騒音制御システムは，全体を集中的に制御しようとするものが多い．しかし，マイクロホンやスピーカの数が増加するにつれて，プロセッサへの負荷が高くなり，実現が困難になる． 本稿では，複数の能動騒音制御器を用いる分散型マルチチャネル能動騒音制御システムを提案する．ここでは，若干の制御器間の通信を許容することで負荷の分散を図っている．さらに本手法では，連立方程式を利用しているので，事前に誤差経路系を推定することなしに，騒音制御フィルタの係数を推定でき，動作中の経路の変動にも追従できる．結果として良好な消音効果が期待できる．

題名QoS制御を可能とするマルチレートOFDMに関する研究
著者 横田 智也, 西川 清史(東京都立大学大学院工学研究科電気工学専攻)
keywords OFDM, QoS, マルチレート
abstract 本稿では，QoS制御の実現を目的としたマルチレートOFDMを提案する． 提案法は，OFDM信号を得る前に送信データを任意の拡散率で拡散することで，伝送品質の異なる通信路を実現するものである． また，簡単なシミュレーションモデルを用いて，提案法がガウス雑音に起因する伝送誤りを制御できることを確認する．

題名ガソリンエンジンの空燃比制御システムにおける無駄時間解析
著者 渡辺 貴英, 水谷 直喜, 菊池 久和, 村松 正吾(新潟大学工学部), 大隈 重男, 渡邉 悟(日立ユニシアオートモティブ)
keywords 信号処理, ウェーブレット, 無駄時間, ガソリンエンジン
abstract 　ガソリンエンジンの空燃比制御システムにおける無駄時間をウェ ーブレット変換を用いて逐次算出する手法を提案する。空燃比とは 吸入空気量と燃料噴射量との比であり、無駄時間とは燃料噴射装置 へ送られる制御信号と、空燃比センサ出力の間の遅れである。空燃 比センサ出力をウェーブレット変換し、無駄時間がもたらす不連続 性を検出することで無駄時間を算出する。本手法を実測データに応 用し、実際のエンジンの無駄時間をさまざまな運転条件の下で測定 した結果を示す。

セッション SBd2-3 画像・映像処理技術I (13:20-15:00)
座長: 阿部 淑人 (大日本印刷)

題名Frequency Weight Adjustment of Motion-JPEG2000 for Invertible Deinterlacer
著者 石田 拓麿, 村松 正吾, 周 杰, 佐々木 重信, 菊池 久和(新潟大学電気電子工学科)
keywords Motion-JPEG2000, Invertible deinterlacer, frequency weight
abstract In this work, frequency weight adjustment of Motion-JPEG2000(MJP2) for invertible deinterlacer is proposed. As previous works, we have developed invertible deinterlacer that suppresses comb-tooth artifacts caused by field interleaving for interlaced scanning video, which affect the quality of scalable intraframe-based codec such as MJP2. Our technique has two features that the sampling density is preserved and the image quality can be recovered by the inverse process on demand. When no codec is applied in between the deinterlacer and inverse process, the original video is perfectly reconstructed. Otherwise, it is approximately recovered. The purpose of this work is to improve the quality of recovered images when MJP2 codec is inserted. It is shown that our invertible deinterlacer can be embedded into the DWT. As a result, frequency weighting for rate-distortion control can be moderately compensated. Simulation results show that the quality recovery is improved more than 1.5 dB in PSNR by applying the proposed compensation compared with the original weighting at 2.0bpp of decoding rate for 8-bit grayscale pictures.


題名コードブロックに基づくMotionJPEG2000画像の効果的なクロスフェード法
著者 渡邊 修, 貴家 仁志(東京都立大学工学研究科)
keywords JPEG2000, MotionJPEG2000, クロスフェード
abstract 本論文ではMotionJPEG2000符号化された動画像のクロスフェード処理に伴う従来のクロスフェード法の問題点を議論し、問題点を改善するためにコードブロックに基づく効果的なクロスフェード法を提案する。提案法は、符号化された画像のコードブロックごとにクロスフェード処理を行うため、従来法のようにクロスフェード処理のために画像を空間領域に復号するという操作が不要である。したがって、提案法を用いることにより、処理負担の低減や必要となるメモリ量削減が期待できる。以上の特徴を、計算機シュミレーションによって確認する。

題名誤り率を考慮したJPEG2000符号化画像の生成とその評価
著者 黒崎 正行, 貴家 仁志(東京都立大学大学院工学研究科電気工学専攻)
keywords JPEG2000, 誤り耐性, 電子透かし
abstract 本報告では，無線通信網などの高い誤り率から再送要求可能な低い誤り率の通信まで，すべてに適用可能なJPEG2000符号化画像の生成法を提案する．提案法は，電子透かし技術と誤り訂正符号を組み合わせたものである．したがって，提案法を用いて符号化された画像はJPEG2000標準のデータ構造を保持しており，汎用のデコーダでの復号をも可能とする．また，提案法はへッダ，レイヤーなど保護するデータ量を自由に変化させることが可能であるため，誤り率と保護すべきデータ量についても考察する．

題名JPEG画像のための画質保証型電子透かしに関する検討
著者 藤吉 正明, 河西 元彦, 貴家 仁志(東京都立大学大学院工学研究科電気工学専攻)
keywords JPEG, 画質保証, 量子化行列, 圧縮領域
abstract 本稿はJPEG画像のための画質保証型電子透かしについて検討している．検討対象は，JPEG符号化手順において，圧縮領域，すなわち，量子化後のDCT係数へ透かしを埋め，かつ，生成される透かし入りJPEG画像の画質が自動的に指定画質となる画像電子透かしである．JPEG符号化手順で用いる量子化行列を考慮し，指定画質を維持することが可能となるDCT係数を選択し，透かしを埋めることで画質を保証している．シミュレーションにより，画質保証性能が示されている．
セッション SBd2-4 画像・映像処理技術II (15:15-16:30)
座長: 菊池 久和 (新潟大)

題名疑似濃淡化のための輪郭適応誤差拡散法
著者 阿部淑人(大日本印刷株式会社 生産総合研究所)
keywords halftoning, error diffusion, adaptive processing
abstract 疑似濃淡化において多用される誤差拡散法は低階調のデバイスに疑似的に階調を表現できる優れた方法であるが，階調再現性と輪郭再現性にはトレードオフがあり固定法では両立が困難である． 本研究では輪郭強度を測定しながら拡散係数を制御することによって その両立を図った．


題名High Quality Image Interpolation by Generalized Piecewise-Linear Multiple Generators
著者 Koichi Ichige(Yokohama National University), Thierry Blu, Michael Unser(Swiss Federal Institute of Technology Lausanne)
keywords interpolation, image processing, filterbank, wavelet
abstract This paper presents an interpolation method based on shifted versions of two piecewise linear generators, which provides approximation order 2 like usual piecewise-linear interpolation; i.e., this method is able to represent the constant and the ramp exactly. Our interpolation is characterized by two real parameters: tau, the location of the generators, and alpha, related to their dissymmetry. By varying these parameters, we show that it is possible to optimize the quality of the approximation, independently of the function to interpolate. We recover the optimal value of shifted-linear interpolation (tau=0.21 and alpha=1) which requires IIR prefiltering, but we also find a new configuration (tau=0.21 and alpha=0.58) which reaches almost the same quality, while requiring FIR filtering only. This new solution is able to greatly reduce the amount of Gibbs oscillations generated in the shifted-linear interpolation scheme.

題名色覚バリアフリーを目的とするWeb色補正に関する一検討
著者 市川 学, 田中 清 (信州大学工学部), 近藤 昭治((株)関東電子応用開発), 廣島 康二, 市川 一夫(社会保険中京病院), 田辺 詔子, 深見 嘉一郎(視覚研究所)
keywords 色覚バリアフリー, Web色補正, インターネット, 色覚異常, 遺伝的アルゴリズム(GA)
abstract 本稿ではインターネット上での色覚バリアフリーを実現することを目的に，HTMLで記述されたWebページの色補正を行う一手法を検討する．まず，カラー画像を色情報によって領域分割した結果を記述する画像抽象化モデルを確立し，色の相互関係について定義する． 次に，色覚異常モデルによる色の見え方に基づき，色補正を効果的に行うための評価関数の設計を行う．そして複数の相互関係を持つ色の最適化を遺伝的アルゴリズム(GA)を用いて解法する．色覚異常のシミュレーションによる結果を通して，色覚異常者にとって識別しやすい配色へと補正できることが確かめられる．

セッション SC2-1 プロセッサ合成 (9:00-10:30)
座長: 冨山 宏之 (ISIT)

題名ASIP Meisterにおけるゼロ・オーバヘッド・ループ制御方式の提案
著者 三田健太朗, 小林真輔, 武内良典, 坂主圭史, 今井正治(大阪大学)
keywords ASIP, コンフィギュラブル・プロセッサ, ゼロ・オーバヘッド・ループ, コンパイラ・ジェネレータ
abstract 本研究では，コンフィギュラブル・プロセッサ開発環境ASIP Meisterにおけるゼロ・オーバヘッド・ループ制御方式を提案する． ZOL制御用モジュールのパラメタ化を行い，さらに ZOLに対応したコンパイラのコード生成手法を提案する． 評価実験では，ループのネスト・レベルおよびループカウンタ・サイズを変更した様々な構成のプロセッサを設計し，生成したコンパイラを 用いてアプリケーションの性能比較を行った． 評価実験の結果，アプリケーションに最適なZOL構成を選択できる ことがわかった．


題名ATM処理を対象としたCAMプロセッサ自動合成システム
著者 田中 英夫(早稲田大学理工学部電子・情報通信学科), 戸川 望(北九州市立大学国際環境工学部情報メディア工学科), 柳澤 政生, 大附 辰夫(早稲田大学理工学部電子・情報通信学科)
keywords CAM, プロセッサ, 自動合成, ATM
abstract 本稿では,ATM処理を対象とするCAM(一致検索機能を有する機能メモリ)プロセッサ自動合成システムを提案する.本システムはC言語で記述されたCAM機能を使用したアプリケーションプログラムおよび面積/時間制約を入力とし,制約を満足するメモリユニットとマイクロプロセッサユニットで構成されるCAMプロセッサの論理合成可能なハードウェア記述およびCAMプロセッサ上で動作するバイナリコードを出力する.本システムは合成対象のメモリユニットにCAMとRAMを併用することで,ネットワークにおけるATMスイッチング諸利を1クロックサイクルで実現可能となった.計算機上に実装した本システムにアプリケーションを入力した結果,実行時間はCAMのみを使用した場合と比較して約0.78倍に短縮された.

題名不規則なデータパスを持つプロセッサのハードウェア/ソフトウェア協調合成手法
著者 宮岡 祐一郎(早稲田大学理工学部), 戸川 望(北九州市立大学国際環境工学部), 柳澤 政生, 大附 辰夫(早稲田大学理工学部)
keywords 不規則なデータパス, ハードウェア/ソフトウェア協調合成, DSP
abstract 不規則なデータパスを持つプロセッサのハードウェア/ソフトウェア協調合成手法を提案する．アプリケーションプログラムを表すコントロールフローグラフおよびデータフローグラフと時間制約を入力とし，時間制約を満たす中で面積を最小化したプロセッサの構成情報と，そのプロセッサ上で動作するアセンブリコードを出力する．まず，実行サイクル数を最小にするデータパス構成を実現して演算ユニットの最大数と，暫定解となる面積を得る．その後演算ユニットの数で分枝し，プロセッサ面積を最小化する特殊レジスタの個数やその接続を決定する部分問題を解く分枝限定法によりプロセッサ構成を得る．部分問題は，十分な数の特殊レジスタを徐々に削減することで解く．提案手法を計算機上に実装し評価した．
セッション SC2-2 招待講演 (11:00-12:00)
座長: 小林 和淑 (東大)

題名(招待)システムLSIの社会情報基盤への利用 -Digital Naming社会を目指して-
著者 安浦 寛人(九州大学)
keywords
abstract

セッション SC2-3 システムレベル検証評価見積り (13:30-15:00)
座長: 山田 晃久 (シャープ)

題名命令レベルにおけるレジスタの変化ビット幅を考慮した組み込みプロセッサ向 け消費電力見積り手法
著者 樋口 昭彦(京都大学大学院情報学研究科通信情報システム専攻), 小林 和淑(東京大学大規模集積システム設計教育研究センター), 小野寺 秀俊(京都大学大学院情報学研究科通信情報システム専攻)
keywords 組み込みプロセッサ, 消費電力解析, レジスタの変化ビット幅
abstract 本稿では, 命令レベルにおけるレジスタの変化ビット幅を考慮した組 み込みプロセッサ向け消費電力見積り手法を提案する. 本手法ではア センブラコードを実行させて, その結果を各命令のレジスタの変化 ビット幅に応じたエネルギーテーブルを参照することによって消費電 力を見積もる. これにより高速な見積り, 効率的な低消費電力のアルゴリズムの研究などが可能になる.


題名データ流量解析に基づく組込みシステム性能見積り手法
著者 上田 恭子, 坂主 圭史, 武内 良典, 今井 正治(大阪大学)
keywords データ流量, 性能見積り, SystemC, 組み込みシステム
abstract 本論文では，データ流量解析に基づく，組み込みシステムの性能見積り手法を提案する．提案手法では，システムにおけるデータ転送の依存関係からデータ転送依存グラフを作成し，データ転送依存グラフを解析することでシステムの処理時間を見積る．バス・アーキテクチャを変更するとデータ転送時間は変化するが，データ転送量は一定であることに着目し，グラフの解析時にあらかじめ測定したデータ転送量からデータ転送時間を算出することで，異なるバス構成におけるシステム性能を見積ることができる．評価実験により，提案手法を用いることで，アーキテクチャごとにシミュレーションして性能を見積る場合に比べ，短時間での見積りが可能であることを確認した．

題名ソフトウェア設計手法による高品質システムＬＳＩ設計手法の提案
著者 内場 誠, 河原畑 光一, 芦原 秀一, 藤内 俊一(富士通西日本コミュニケーション･システムズ(株)/システム機器開発部)
keywords 設計手法, システムLSI, 品質, Webツール
abstract 近年のC言語記述によるシステムLSI設計の広がりにより、ハードウェア 設計においてもソフトウェア設計に近い設計手法が求められている。 さらに、今後はＣ言語設計の普及、設計ツールの自動化が進み、言語 記述が設計のアウトプットとなる事が予想され、言語記述の前段に位置 する仕様をいかに表現するかが重要となる。 今回我々は、上位仕様レベルと評価試験に重点を置き、ソフトウェア 開発の手法を導入した。各設計と作業内容を細かく定義した設計手法と e-mailとDataBaseを融合した設計情報管理Webツールの開発/適用で ある。その結果、高い設計品質を実現する事が出来たので報告する。


セッション SD2-1 離散事象システム (9:15-10:15)
座長: 鈴木 達也 (名古屋大)

題名Supervisory Control of a Class of Concurrent Discrete Event Systems
著者 Shigemasa Takai(Wakayama University), Toshimitsu Ushio(Osaka University)
keywords discrete event system, supervisory control, concurrency, controllability, concurrently well-posedness
abstract In this paper, we study supervisory control of a class of discrete event systems with simultaneous event occurrences, which we call concurrent discrete event systems. The behavior of the system is described by a language over the simultaneous event set. We introduce a notion of concurrent well-posedness of languages. We then prove that Lm(G)-closure, controllability, and concurrent well-posedness of a specification language are necessary and sufficient conditions for the existence of a nonblocking supervisor. We address the computational complexity for verifying the existence conditions.


題名State Equation of Program Nets and Its Application to Verifying Token Self-Cleanness of Acyclic SWITCH-less Nets
著者 Shingo Yamaguchi, Kousuke Yamada(Faculty of Engineering, Yamaguchi University), Qi-Wei Ge(Faculty of Education, Yamaguchi University), Minoru Tanaka(Faculty of Engineering, Yamaguchi University)
keywords dataflow program, program net, state equation, token self-cleanness, verification
abstract This paper proposes a state equation of program nets and its application to analysis of program nets. We first define a matrix representation of program nets. We then propose a state equation of the program nets using the matrix representation. Finally, for acyclic program nets with no SWITCH-node, we show an application to verifying token self-cleanness which is an important property of program nets.
セッション SD2-2 グリッド・コンピューティング (10:45-11:45)
座長: 佐々木 淳 (NTT)

題名(招待)グリッド・コンピューティングの現状と将来
著者 伊藤 智(産業技術総合研究所)
keywords
abstract

セッション SD2-3 グラフ・アルゴリズム (13:00-15:00)
座長: 中山 慎一 (徳島大)

題名L字型描画の列挙
著者 高木 正博, 中野 眞一(群馬大学)
keywords グラフ, アルゴリズム, 列挙
abstract グラフを, 各面がL字形(退化したL字形として長方形を含む)であるように, かつ, 辺が交差することなく, 平面に描画したものを, グラフのL字形描画と呼ぶ. 本文は, すべての底辺つきL字形描画を, 重複も抜けもなく列挙する高速なアルゴリズムを与える. 本文のアルゴリズムは, 内面の個数がちょうどn個である底辺つきL字形描画のすべてを, 重複も抜けもなく, 描画1つあたりO(1)時間で生成する. このアルゴリズムが使用する作業用記憶領域はアルゴリズム全体でO(n)である.


題名Caterpillarの列挙アルゴリズム
著者 菊地 洋右, 田中 博行, 中野 眞一, 柴田 幸夫(群馬大学工学部情報工学科)
keywords caterpillar, 列挙アルゴリズム, spider, scorpion
abstract グラフの個数の数え上げには様々な研究があ る.数え上げの研究は,主に組み合わせ論の手 法による.一方,それらのグラフの全てを計 算機等で出力することは,グラフの個数が一般に 膨大であるため困難であった.しかし,近年 の計算機の性能の向上に伴い,計算機による 列挙が可能になり,様々なアルゴリズムも提 案されてきた.本文は,木の部分クラスであ るcaterpillarの列挙に関するものであ る.これまでに,様々な,木の列挙に関する 研究がある.例えば,根付き木の列挙アルゴ リズムや,平面植木の列挙アルゴリズムなど である.また,頂点の個数が$n+4$である caterpillarの個数は, $2^n + 2^{\lfloor n/2 \rfloor}$であると知られている.

題名広域クラスタにおけるブロードキャストスケジューリングについて
著者 田崎 太(新潟工科大学 大学院工学研究科), 田村 裕(新潟工科大学), 仙石 正和(新潟大学工学部), 篠田 庄司(中央大学理工学部)
keywords 並列分散処理, クラスタシステム, ブロードキャスト, 最小ブロードキャスト時間問題, スケジューリングアルゴリズム
abstract クラスタシステムのブロードキャストスケジューリングについて検討する．ブロードキャストスケジューリング問題は一般にNP完全であることが知られている．そして，ネットワークトポロジと問題の複雑さの関係や，効率の良いスケジュールを出力するアルゴリズムについて多くの研究がなされてきた．本稿では，ネットワークトポロジが，あるSplit Graphで表されるクラスタのブロードキャストスケジューリングを検討する．同種クラスタの場合には，ブロードキャストスケジューリング問題が多項式時間で解けることを示す．また，異種クラスタに対しては，高確率で最適解を得ることができるヒューリスティックなアルゴリズムも提案する．

題名最小重み点被覆問題に対する近似解法の実験的性能評価
著者 高藤 大介, 田岡 智志, 渡邉 敏正(広島大学大学院 工学研究科 情報工学専攻)
keywords 最小重み点被覆問題, 近似解法, 計算機実験比較
abstract 本稿では，自然数の点重みを持つグラフにおける最小重み点被覆問題を扱う．グ ラフの点被覆とは，頂点集合であって，任意の辺の両端点のうち少なくとも一方 を含むものである．点被覆の重みは，点被覆に含まれる各頂点の重み総和である． グラフの最小重み点被覆問題は，自然数の点重みを持つ無向グラフが与えられた とき，重み最小となる点被覆を求める問題である．今までのところ最小重み点被 覆問題の発見的または近似解法に関し，実データに対する計算機実験による性能 比較は行われていないようである． 本稿では，最小重み点被覆問題に対する既存近似解法に関して，計算機実験によ る性能比較結果を報告する．
セッション SD2-4 ペトリネット (15:30-16:30)
座長: 名嘉村 盛和 (琉球大)

題名各トランジションの発火が2回以下である辺重み付きカクタスにおける発火系列探索
著者 高原 伸水, 田岡 智志, 渡邉 敏正(広島大学大学院 工学研究科 情報工学専攻)
keywords ペトリネット, 辺重み付きカクタス, 発火系列問題, 多項式時間アルゴリズム
abstract ペトリネットの発火系列問題（LFS）とは，『ペトリネットN，初期マーキング M，発火回数ベクトルXが与えられたとき，Mから順次発火可能で各トランジショ ンtが丁度X(t)回出現する発火系列sigmaが存在するか否かを判定し，存在する ならばそのような発火系列を求めよ．』と定義される．LFSを解くことは容易 ではなく，単純な構造を持つペトリネットに対してもNP-困難であることが知 られている．しかしながら，ペトリネットが辺重み付きカクタス構造で，かつ X =1の場合は O(|P|log |P|) 時間で解けることが既に示されている．本稿で は，その解法を拡張して，ペトリネットが辺重み付きカクタス構造で，かつ各 トランジションtの発火回数X(t)が1または2の場合に，O(|P|log |P|) 時間解 法を提案する．


題名ペトリネットのマーキング構成問題とその発見的解法MCGHk
著者 田岡 智志(広島大学大学院 工学研究科 情報工学専攻), 吉竹 一将(広島大学工学部第2類情報工学課程アルゴリズム論研究室), 渡邉 敏正(広島大学大学院 工学研究科 情報工学専攻)
keywords ペトリネット, マーキング構成問題, 可達問題, 発見的解法
abstract 本論文はペトリネットのマーキング構成問題(MCP: Marking Construction Problem)に対する発見的解法を提案し、既存手法と計算機実験により性能比較 をする．MCP は，``ペトリネット N，初期マーキング M，目標マーキング M' が与えられた時，M からトランジションの発火により遷移可能なマー キングのうちで M' に最も近いマーキング M'' を求めよ''という問題で ある．ここで M' と M'' に対し，差分の絶対値総和を考え，これが最小 であることを M'' は M' に最も近いと言うことにする． MCPは一般的にはNP-困難であるので、発見的解法が提案されている。