| 2010年4月18日(日) | 17:30〜19:00 |
| 2010年4月19日(月) | 8:00〜 |
| 2010年4月20日(火) | 8:00〜 |
| 2010年4月19日(月) [会場: 軽井沢プリンスホテル ウエスト・国際会議場 浅間] |
| A | Ba | Bd | C | D |
|---|---|---|---|---|
PLL |
信号処理基礎 |
スケジューリング |
||
[特別セッション] 学習と最適化 |
アンプ・フィルタ |
信号処理応用 |
[特別セッション] 動作合成・高位合成(1) |
アルゴリズム論 |
回路解析 |
[チュートリアル講演] CMOSアナログ集積回路チュートリアル |
[特別セッション] 学生セッション(ディジタル信号処理) |
[特別セッション] 動作合成・高位合成(2) |
[招待講演] フォーマルメソッド |
[特別セッション] ニューロダイナミクスの基礎と応用 |
[招待講演] |
高信頼設計 |
[招待講演] 超並列計算のためのアルゴリズミックス |
|
| 奨励賞表彰式 17:30-17:40 [会場: 長野] | ||||
| 特別招待講演: 「複雑系数理モデリングとその応用」 合原 一幸(東京大学) 17:40-18:40 [会場: 長野] | ||||
| 懇親会 18:40-20:40 [会場: 長野] | ||||
| 2010年4月20日(火) [会場: 軽井沢プリンスホテル ウエスト・国際会議場 浅間] |
| A | Ba | Bd | C | D |
|---|---|---|---|---|
配線モデリングと抽出 |
ADC |
システム実現技術 |
低消費電力設計手法 |
並行システム |
カオスと同期現象 |
電源 |
画像処理 |
[特別セッション] メニーコア時代の並列シミュレーション |
グラフ・ネットワーク理論 |
| 2010年4月19日(月) |
| 題名 | (招待) PSOのダイナミクス解析 |
| 著者 | ○神野 健哉, 進藤 卓也 (日本工業大学) |
| Page | pp. 1 - 6 |
| Keyword | PSO, 固有値, 減衰係数, 最適化問題, 正準形 |
| Abstract | 最適化問題をより迅速に近似的に解くための手法として粒子群最適化法(PSO)が注目を集めている。このようなPSOでは慣性係数ならびに加速度係数等のパラメータが最適解の探索能力に非常に重要な影響を与えるが、パラメータのうち加速度係数には一様乱数が乗じられるため、PSO は確率論的な動作をするシステムとみなせる。PSOの動作の厳密な解析を行うため、確率論的要素を取り除いた決定論的PSO(D-PSO)が提案、解析が行われている。本稿ではD-PSOの固有値に着目し、最適解探索能力と固有値の関係について考える。更に、より固有値の設定が容易に設定が可能となる正準形決定論的PSO(CD-PSOを提案し、CD-PSOの最適解の探索能力をいくつかのベンチマーク関数を用いて数値実験による解析を行う。その結果、慣性係数と加速度係数によって決定されるシステムの固有値により、CD-PSOの探索能力が変化することを明らかにし、CD-PSOとD-PSOとの違いに関して議論する。 |
| 題名 | N-Nバイナリーニューラルネットワークの進化的学習アルゴリズム |
| 著者 | ◎伊藤 良, 壁谷 秀太郎, 斎藤 利通 (法政大学 理工学部 電気電子工学科) |
| Page | pp. 7 - 10 |
| Keyword | ニューラルネット, 学習, 遺伝的アルゴリズム |
| Abstract | N入力N出力バイナリーニューラルネットの学習法を提案する。 同学習法は、遺伝的アルゴリズムを用い、あいまいさを許容し、 各出力に対応する中間層ニューロンを有効に共有させるものである。 基本的な数値実験によって、中間層ニューロン数や探索回数を抑制等の、 有効性を確認する。 |
| 題名 | 動径基底関数ネットワークによる音声合成 |
| 著者 | ◎神山 恭平 (明治大学大学院理工学研究科), 鎌田 弘之 (明治大学理工学部) |
| Page | pp. 11 - 16 |
| Keyword | 音声合成, RBF, ニューラルネットワーク |
| Abstract | 人間の音声を人工合成する方法は、記録媒体が大容量化、低価格化してから、実用的な手法の検討が注目されにくくなっている。しかし、現在実用化されている手法は、完全な録音音声か、人口音声の範疇を越えていない自然性に欠けたものである。 しかも、声帯の振動数変化にはカオス性があることは知られているが、カオス性を考慮した声帯波合成に関する研究は皆無である。 本研究では、音声が含む非線形性に基づく周期のカオス的な揺らぎや、粘膜特性等線型理論では表現しにくい要素をも考慮して音声合成を行うことを目的とし、人間の自然な任意の音声を人工合成することを最終的な目標する。そのために、カオスなどの非線形写像の再現も可能なRBFN（動径基底関数ネットワーク）の応用を音声合成に試用する。 検討するステージは、以下の２つに分類される。一つは、時系列信号を直接RBFNによって学習・合成する方法について検討した。 もう一つは、揺らぎのある声帯波周期に同期したインパルス列をRBFNにより学習・合成し、インパルス応答を重畳し合成する方法について検討した。 結果としてはどちらの方法も共に、初期的には忠実に系列を忠実に再現可能であるが、長期的には定常的な周期パターンの繰り返しになってしまうことがわかった。 これは、声帯振動数の変化を再現するためのダイナミクスを学習するには、3層のニューラルネットワークでは難しいことを暗示しているものと考える。 |
| 題名 | 整数計画法を用いた区分的線形回路の全解探索法 |
| 著者 | ◎上田 恭大, 田村 直也, 山村 清隆 (中央大学理工学部電気電子情報通信工学科) |
| Page | pp. 17 - 22 |
| Keyword | 非線形回路, 回路シミュレーション, 直流動作点解析, 全解探索, 整数計画法 |
| Abstract | 非線形回路のすべての直流解を求める実用的なアルゴリズムを確立することは，集積回路設計における重要な課題の一つである．この問題に対しては多くの効率的なアルゴリズムが提案されているが，それらはインプリメンテーションの際に高度な専門的知識と複雑なプログラミングを必要とするため，初心者や非専門家には敷居の高い方法となっていた．本論文では，近年の整数計画法の驚異的発展を背景に，整数計画法のソフトウェアを利用した区分的線形回路の実現容易な全解探索法を提案する．本手法は，区分的線形回路を記述する区分的線形方程式を混合整数計画問題に定式化し，それにGLPK, CPLEXといった無償／商用の優れた整数計画法のソフトウェアを適用するものである．このようなアプローチは近年の整数計画法の飛躍的発展により初めて可能となったもので，初心者でも複雑なプログラムを作ることなく，簡単に全解探索を行うことができる． |
| 題名 | Conservation Operator in Micro-electromagnetic Field, and Its Macro-expression by the Optimum Approximation Aimed at Iterative Design of Nonlinear Composite Materials |
| 著者 | Yuichi Kida (The School of Pharmaceutical Sciences, Ohu University), ○Takuro Kida (Prof. Emeritus of Tokyo Institute of Technology) |
| Page | pp. 23 - 28 |
| Keyword | Generalized conservation relation, Sensitivities based on the micro-expression of the Maxwell relations in an electromagnetic field, Nonlinear optics, CAD design, Nonlinear signal processing |
| Abstract | Generalized conservation relation of a lumped-constant network is proved by B.D.H.Tellegen and, T.Kida establishes a necessary and sufficient condition of conservation operator of multi-port networks. As an application of this operator, it is shown that sensitivity for an LC element with respect to amplitude and phase characteristic of a resistively terminated LC 2-port can be expressed by the stored energy of the element under the stationary sinusoidal excitation. This treatment of sensitivity has been extended to many types of conservation relations and analysis of parasitic effect by element deviation in systems. On the other hand, we present the optimum running approximation of a signal in a certain set of approximately band-limited signals and extend this approximation to the optimum interpolation approximation for multidimensional vector signals that all elements of the corresponding vector are separable-variable functions and, by putting variables of the vector signals to be identical with each other, we derive the optimum interpolation approximation of a system having non-linear characteristics. In appearance, it is considered that these two fields of research are not related each other. However, recently, composite linear and nonlinear materials have attracted much attention in many fields of optics, physics and engineering. Some of these realize up-conversion of razer waves by nonlinear optical characteristics of the materials and others achieve unprecedented physical properties such as negative refraction and functionality unattainable with natural materials. In the theoretical treatment of sensitivity and iterative CAD design of these new materials, it is necessary to establish the theory of conservation operators and sensitivities based on the micro-expression of the Maxwell relations in an electromagnetic field, as well as its extension to the macro-expression by means of the optimum approximation by interpolation using the observed sample values of the actual nonlinear physical quantities such as nonlinear polarization. We combine the above two concepts and present conservation operator in micro-electromagnetic field and its macro-expression by the optimum nonlinear approximation which are aimed at iterative design of linear and nonlinear materials. |
| 題名 | Circuit Analysis Technique Using Random Walk Method |
| 著者 | 三輪 仁, ○鈴木 五郎 (北九州市立大学情報メディア工学科) |
| Page | pp. 29 - 34 |
| Keyword | Monte Carlo, Markov chain, power grid, noise analysis, random walk |
| Abstract | Random walk method for power grid noise analysis, that treats lots of large valued decoupling capacitors and calculates voltage drops from VCC, has been existing. The computational complexity of this method is O(L2M), where L is the number of interconnects and M is the transient analysis elapsed time. Therefore, when we apply the existing technique to actual circuit, it becomes very time consuming. This paper proposes a novel technique which improve the computational complexity from O(L2M) to O(L). Basic idea is inversing the transient analysis timestep order from successor to predecessor that is backward direction. The CPU time using proposed technique can be 6 (%) and 12 (%) compared with existing technique and SPICE, respectively for one interconnect analysis. |
| 題名 | (招待) マルチ時間スケール系のダイナミクス：分岐・カオス・特異摂動 |
| 著者 | ○土居 伸二 (京都大学) |
| Page | pp. 35 - 40 |
| Keyword | Hopf分岐, カオス, 緩和振動, ニューロンモデル |
| Abstract | 自然界には時間スケールの異なった様々な現象が存在する．速く変化する変数とゆっくり変化する変数が同時に存在するような，複数の時間スケールを内包するダイナミカルシステムは特異摂動系と呼ばれ，古くから，数多くの研究がなされている．これらの解析学的特異摂動論だけでなく幾何学的特異摂動論は，ニューロダイナミクスの研究とも相俟って，近年大きな進展を見せている．本稿では，カナール解など，特異摂動論に関する簡単な概説の後，最近の我々の研究を紹介する．特に，特異摂動系ではホップ分岐の近傍に極めて周期の長い振動解やカオス的振動現象が生じることを示す． |
| 題名 | スモールワールドネットワークを用いたFPGA配線構造の改善 |
| 著者 | ◎小澄 匡俊, 茂呂 征一郎 (福井大学) |
| Page | pp. 41 - 45 |
| Keyword | スモールワールドネットワーク, FPGA, 配線構造, 平均経路長 |
| Abstract | スモールワールドネットワークを用いたFPGA配線構造の改善法を提案している．これまでに，FPGAの規則的な配線構造のうちある種類のラインのみををランダムに再配線しスモールワールド化することで，ブロック間の平均パス長を短くできることが報告されている．本研究では，再配線するラインの種類を拡大し，様々な組み合わせを考えることで，さらにパス長を短くできるほか，ネットワークの大きさによって適した組み合わせが異なることを確認している． |
| 題名 | デジタルスパイク位相写像とスパイク列の学習 |
| 著者 | ◎小川 貴史, 斎藤 利通 (法政大学 理工学部 電気電子工学科) |
| Page | pp. 46 - 49 |
| Keyword | スパイキングニューロン, 学習 |
| Abstract | スパイキングニューロンを参考としたデジタルスパイク位相写像を提案し、 スパイク列入力を教師信号とする学習について考察する。 同写像は、デジタルスパイクニューロンの簡略化システムとみなすこともできる。 学習アルゴリズムは、入力とその近傍の部分の写像が逐次決定される簡素なものであり、その有効性は、基本的な例題に対する数値解析で確認される。 |
| 題名 | ディジタル余弦波発生器を用いた分数分周PLL回路 |
| 著者 | ◎丸地 俊也 (青山学院大学大学院 理工学研究科), 松谷 康之 (青山学院大学 理工学部) |
| Page | pp. 50 - 55 |
| Keyword | PLL, 分数分周器, デジタル余弦波発生器 |
| Abstract | 従来の分数分周PLL回路ではPLL内の分周器の周辺にスプリアス雑音が生じ、これが隣接チャネルへの妨害やクロックジッタの原因となっていたため、スプリアスを除去・低減する手法が研究されている。この問題を解決する一手法としてデジタル回路による余弦波派生回路、D/A変換器、LPF、電圧比較器を用いた新しい分数分周器を用いた分数分周PLL回路を提案する。シミュレーションにおいてスプリアスが生じないことを明らかにし、また試作回路において要素原理であるLPFによるゼロクロス点の抽出により、スプリアスが発生せず、ノイズフロアが-75dB程度に抑圧されていることを実測により明らかにした。 |
| 題名 | 位相比較回路用非線形TDC回路の検討 |
| 著者 | ◎渡辺 菜津美 (青山学院大学理工学部), 稲垣 雄志 (青山学院大学大学院理工学研究科), 松谷 康之 (青山学院大学理工学部) |
| Page | pp. 56 - 61 |
| Keyword | TDC, PLL, バブルコード |
| Abstract | 従来の遅延バッファのストリング回路により基準遅延を発生させてDFFにより時間比較をするTDC（Time to Digital Converter）は配線遅延やトランジスタ特性バラツキにより，出力コードが単調に増加しないバブルコードを発生するおそれがある．そこで，DFFの遅延を用いたTDC回路を提案し，単調性を保障する際に問題となるバブルコードが発生しないことを回路シミュレーションによって明らかにした．また提案TDC回路のデータ入力に遅延バッファを挿入することで位相分可能を向上できることを示した．さらに提案TDCを応用して高速引き込みと低位相雑音特性を実現する非線形TDCを提案しPLLへ応用可能であることを示した． |
| 題名 | TDCを用いない全デジタルPLLの検討 |
| 著者 | ◎稲垣 雄志, 松谷 康之 (青山学院大学大学院 理工学研究科) |
| Page | pp. 62 - 66 |
| Keyword | 全デジタルPLL, 周波数シンセサイザ, 固定小数点カウンタ |
| Abstract | LSIプロセスの0.1μm以下への微細化と電源電圧の1V以下への低減の傾向から，TDCやループフィルタ等のアナログ的要素を全く含まない全デジタルPLLの実現が望まれている．本報告では，回路の全デジタル化および小型化のためTDCや除算器を用いない全デジタルPLLを提案し，MATLAB/Simulinkによるシミュレーションおよびブレッドボード回路の評価結果より，フラクショナルスプリアスが抑制され，基準クロック100周期以下で周波数引き込みが完了することを確認した． |
| 題名 | MOSFETのゲート-ドレイン間の寄生容量を考慮したE級増幅器の設計 |
| 著者 | ◎魏 秀欽, 関屋 大雄, 黒岩 眞吾 (千葉大学大学院融合科学研究科), 末次 正 (福岡大学工学部電子情報工学科), Marian K. Kazimierczuk (Department of Electrical Engineering, Wright State University) |
| Page | pp. 67 - 72 |
| Keyword | E級増幅器, ゲート–ドレイン, 寄生容量, 解析 |
| Abstract | 本論文ではMOSFETのゲート-ドレイン間の寄生容量を考慮したE級増幅器の波形式と設計方程式を示す. 設計例を示し, 回路のシミュレーションおよび実験を行う. 電圧波形がE級動作条件を満足することを確認し, 本論文における解析の妥当性を示す. 回路実験において, E級増幅器は出力電力Po=4.04 Wおよび動作周波数f=7 MHzにおいて92.8 %の電力変換効率を達成した. 本論文の結果は, 高周波数環境でのE級増幅器の設計において, MOSFETのゲート-ドレイン間の寄生容量を考慮することの重要性を示している. |
| 題名 | 2乗電流源と差動対で構成される新しい適応バイアス型線形MOSトランスコンダクタ |
| 著者 | ◎プラウィット トンプーン, 松元 藤彦, 竹内 均, 野口 泰明 (防衛大学校 応用物理学科) |
| Page | pp. 73 - 78 |
| Keyword | CMOS, アナログ集積回路, トランスコンダクタ, 線形回路 |
| Abstract | 線形トランスコンダクタは、アナログ信号処理回路の基本的な構成単位である。バイアスオフセット型トランスコンダクタは線形性の優れた回路として知られいる。しかし、この回路を動作させるには、2つの非接地バイアス電圧源が必要になり、回路面積が大きくなる。また、バイアス電圧を大きくすると、動作範囲が狭くなる。一方、従来の適応バイアス型線形トランスコンダクタには、これらのような問題が生じない。しかし、CMRRとPSRRが低いという問題がある。そこで本研究では、高いCMRRとPSRRをもつ、新しい適応バイアス型線形トランスコンダクタを提案する。更に、提案回路は、シングルエンド変換なしで線形な入出力特性を実現できる。 |
| 題名 | 0.5V以下の電圧駆動を実現したサブスレショルド動作アナログ回路 |
| 著者 | ○原田 知親, 高橋 良輔, 佐山 裕紀, 奥山 澄雄, 松下 浩一 (山形大学大学院 理工学研究科) |
| Page | pp. 79 - 84 |
| Keyword | サブスレショルド動作, アナログ回路, オンチップ電源 |
| Abstract | 本研究では、バッテリー等の限られた電力で数年動作可能な極低電圧駆動アナログ回路を含めたLSI の実現に向け、弱反転領域を用いた微小電流により、0.5V 以下の極低電源電圧で入出力Rail-to-Rail 動作が可能な、差動増幅回路を設計・評価を行った。そして、サブスレショルド領域で回路を安定に動作させるためのオンチップ電源回路について設計し評価を行なった。 |
| 題名 | 位相および振幅特性の逐次最適化に基づいたマイクロ波フィルタの自動調整手法 |
| 著者 | ◎武内 陽介 (横浜国立大学工学府), 市毛 弘一 (横浜国立大学工学研究院), 宮本 幸一, 恵比根 佳雄 (日本電業工作株式会社) |
| Page | pp. 85 - 90 |
| Keyword | 自動調整, マイクロ波フィルタ |
| Abstract | 近年，無線通信技術の発達により移動体通信が急速に普及し，通信スペクトルの過密化が問題となっている．そこで，隣接帯域信号による電波干渉を低減することができる多段BPFの需要が高まっている.多段BPFはスカート特性が急峻であり，過密化したスペクトルから所望帯域を分離するのに適している．しかしながら，BPFを作成した最初の段階では素子のばらつきや組立誤差などによって所望特性を満たしておらず，その為最後に特性を満足するよう調整する必要がある．この調整作業だが，非常に煩雑で現在熟練職人の手作業によって微調整が行われている為にコストや時間がかかるといった問題がある．そこで，機械による調整でも所望特性を満たすことができるような調整アルゴリズムを提案・実装し，調整精度を検討している． |
| 題名 | (招待) CMOSアナログ集積回路設計を目指す学生・若手技術者が習得しておくべき コア技術 |
| 著者 | ○谷口 研二 (大阪大学) |
| Page | pp. 91 - 94 |
| Keyword | CMOS, アナログ, 回路設計, コア技術, 教育 |
| Abstract | CMOSアナログ集積回路設計者を目指す学生・若手技術者育成について述べる。 アナログ回路は信号処理の手段であり、入出力信号の因果関係を表す伝達関数が最も重要である。PLLやAD変換器なども広義の伝達関数で表される。能動素子の特性を相互コンダクタンスgm、出力抵抗ro、寄生容量Cで表現すればアナログ回路はこれらの物理パラメータを含む伝達関数で表される。逆に、伝達関数から仕様に合うgm,roが導かれると、素子のバイアス電流や電圧が決まる。実際の回路設計の現場ではこれに加え、様々な回路トポロジー、アーキテクチャを選択してアナログ回路の消費電力、信号雑音比、歩留まり、歪などを考慮しながら仕様を満たす最適な解を求める。もちろん出力信号の一部を入力側にフィードバックすることで様々な伝達関数が実現できる。講演の中ではこれらの基礎知識を基に、CMOSアナログ集積回路の動作を理解するため、アナログ回路技術の分野横断的なコア技術を分かりやすく紹介する。 |
| 題名 | The Optimum Discrete Signal Estimation of a Slightly Non-linear Filter Bank Including Running-type Approximation |
| 著者 | Yuichi Kida (The School of Pharmaceutical Sciences, Ohu University), ○Takuro Kida (Prof. Emeritus of Tokyo Institute of Technology) |
| Page | pp. 95 - 100 |
| Keyword | Nonlinear signal processing, Filter bank, The optimum approximation |
| Abstract | Theory of interpolation approximation of a signal in a given set of signals has been focused as a powerful technique in the digital signal processing. In our previous papers, we present many theories of the optimum interpolation approximation for various types of signals including deterministic signals or statistical signals. In these theories, the interpolation approximations are modeled as a certain generalized filter bank. In these theories, the generalized analysis filters are linear operators. However, in many physical effects in biomedical field and sensors in material engineering, it is often the case that some small non-linear characteristics are contained. In our previous paper, we treat approximation of non-linear filter bank. However, running approximation is not treated. In this paper, a theory of a favorable interpolation approximation of running-type filter banks with non-linear analysis filters is presented based on the one-to-one correspondence between errors in a wide interval in the variable domain and its small segment. |
| 題名 | 分枝限定法によるCSD係数FIRフィルタ設計の高速化 |
| 著者 | ◎高橋 伸夫, 陶山 健仁 (東京電機大学 工学部 電気電子工学科) |
| Page | pp. 101 - 106 |
| Keyword | FIRフィルタ, 混合整数計画法, 分枝限定法, タブーサーチ |
| Abstract | 本研究では分枝限定法によるCSD係数FIRフィルタ設計の高速化について検討する．これまで，CSD表現を線形制約としてもつ離散係数FIRフィルタの設計問題を混合整数計画問題として定式化し，分枝限定法により最適設計を行ってきた．しかし，分枝限定法は多くの部分問題を生成し，膨大な計算時間を要するため部分問題数の削減が重要な課題である．従来法では，分枝限定法の暫定値に初期値を与えることで部分問題数の削減を確認してきたが，さらに，分枝限定法の初期解が最適解に近ければ部分問題数の削減が期待できる．本研究では分枝限定法の初期解にタブーサーチで得られた近似解を用いて部分問題数削減を図る．設計例より提案法の有効性を示す． |
| 題名 | ヴォルテラフィルタを用いたカオス変復調システムに関する研究 |
| 著者 | ◎太田 征宏 (明治大学大学院理工学研究科), 鎌田 弘之 (明治大学理工学部) |
| Page | pp. 107 - 110 |
| Keyword | ヴォルテラフィルタ |
| 題名 | 無駄時間を含む伝達関数同定のための微分フィルタ |
| 著者 | ○立花 康夫 (神奈川工科大学 情報メディア学科) |
| Page | pp. 111 - 114 |
| Keyword | Identification, Dead time, Transfer function, Differential filter, FIR |
| Abstract | この論文は、微分フィルタを用いた無駄時間を含む伝達関数の同定法と必要となる微分フィルタの設計法を与える。無駄時間を1次遅れで近似し、伝達関数の分母に繰り込んで元の系を無駄時間の無い伝達関数で近似する。これを対象系の入出力サンプル値の微分フィルタ信号を用いて推定する。提案微分フィルタはFIR型で線形位相である。1次微分フィルタと1次低域フィルタと高次の低域フィルタのカスケード接続で所定の特性を満たす。提案同定手法には狭い幅の低域特性が必要となり、400次程度の高次フィルタを用いる。フィルタ設計は最小二乗法により、解法にはGauss-Seidel法を用いる。元の系の伝達関数係数と無駄時間は推定伝達関数係数の非線形方程式を満たす。これはNewton- Raphson法による逐次近似で解く。フィルタ設計例と同定例を示す。 |
| 題名 | Improving Performance of Hybrid Active Noise Control Systems for Narrowband Periodic Disturbances |
| 著者 | ◎Muhammad Tahir Akhtar, Wataru Mitsuhashi (The University of Electro-Communications) |
| Page | pp. 115 - 120 |
| Keyword | Active Noise Control, FxLMS algorithm, Hybrid ANC, Periodic Disturbances |
| Abstract | In filtered-x LMS (FxLMS) algorithm-based single-channel feedforward active noise control (ANC) system, a reference signal is available that is correlated with the primary disturbance at the error microphone. In some practical situations, there may be an uncorrelated disturbance appearing at the error microphone, for which correlated reference signal is not available. This disturbance, degrades the performance of the ANC system. In this paper we propose an improved performance hybrid ANC system which can simultaneously control both the correlated and uncorrelated noise signals. The proposed method comprises three adaptive filters; 1) the FxLMS algorithm-based ANC filter to cancel the primary noise, 2) a separate FxLMS algorithm-based ANC filter to cancel the uncorrelated disturbance, and 3) the LMS algorithm based supporting adaptive filter to generate appropriate signals for the two ANC filters. Computer simulations are carried out which demonstrate that the proposed method can effectively mitigate the correlated and uncorrelated primary disturbances, and gives significantly improved noise reduction performance. This improved performance is achieved at an increased computational complexity. |
| 題名 | パラレル構成型適応ノッチフィルタの演算量削減 |
| 著者 | ○川村 新, 柳 允雄, 飯國 洋二 (大阪大学基礎工学研究科) |
| Page | pp. 121 - 126 |
| Keyword | ノッチフィルタ, パラレル構成, 収束速度, 推定精度, 演算量削減 |
| Abstract | 広帯域信号に混在する不要な狭帯域信号を除去するための手段として，適応ノッチフィルタを用いる方法が研究されている．適応ノッチフィルタは，除去周波数が自動的に未知正弦波周波数に収束することが確認されている．しかしながら，このような適応ノッチフィルタには，推定精度と収束速度のトレードオフという根本的な問題がある．この問題を解決するため，我々はパラレル構成型適応ノッチフィルタ(PNF: Parallel Notch Filter)について検討してきた．PNFは，推定精度優先のノッチフィルタ1と収束速度優先のノッチフィルタ2から構成される．そして各時刻において，それぞれのフィルタの出力分散を比較し，分散が小さい方のフィルタ係数を選択して利用するものである．したがって，推定初期では収束速度優先のノッチフィルタ2の係数が利用され，収束値近傍では推定精度優先のノッチフィルタ1の係数が利用される．結果として，PNFは収束速度と推定精度のトレードオフを解決できる．本稿では，このPNFの演算量削減について検討している． |
| 題名 | 混合雑音重畳画像からのエッジの抽出法 |
| 著者 | ◎石井 聡, 馬場 賢浩, 木村 誠聡 (神奈川工科大学情報学部情報工学科), 田口 亮 (東京都市大学工学部) |
| Page | pp. 127 - 130 |
| Keyword | 混合雑音除去, ファジー推論, エッジ抽出 |
| Abstract | 画像処理の重要な処理の一つとしてエッジ抽出処理がある.しかしながら,画像にガウス性やインパルス性雑音が重畳していた場合,そのエッジ抽出処理はエッジだけでなく雑音成分も一緒に抽出し良好な結果は期待できない.本稿では処理点と局所領域の情報を用い,各種情報をファジー推論で関連付け,雑音除去を行いつつエッジ抽出を行う方法を提案する.提案法は従来法に比べ処理が簡潔になったにも関わらず,ほぼ同等の性能を示すことを明らかにした. |
| 題名 | 勾配強度近似および二乗ヒストグラムによる高速HOG |
| 著者 | ◎渡辺 秀典, 村松 正吾, 菊池 久和 (新潟大学工学部電気電子工学科) |
| Page | pp. 131 - 136 |
| Keyword | HOG, 二乗ヒストグラム, 勾配強度近似 |
| Abstract | 本研究ではHOGに含まれる平方根の計算コストを削減する方法を提案する．HOGは一般物体検出において注目を集めており，組み込み実装の研究が行われている．組み込み実装においては省電力性能が求められるため，プロセッサ等の性能が制限される．したがって計算コストが少ないアルゴリズムが求められる．そこで，HOGの輝度勾配の強度の計算およびヒストグラムの正規化における平方根の演算コストを削減するための手法を提案，性能評価を行う． |
| 題名 | 音声のスパース性に基づく複数音源定位の性能改善 |
| 著者 | ◎梅津 浩史, 関 幸夫, 染谷 貴徳, 陶山 健仁 (東京電機大学工学部電気電子工学科) |
| Page | pp. 137 - 142 |
| Keyword | マイクロホンアレー, 音源定位, スパース性 |
| Abstract | 本研究では，音声のスパース性に基づく2マイクロホンによる複数音源定位について検討する．これまで，「時間−周波数」平面上の推定結果の信頼性を複数の指標を用いて評価し，その信頼性分布からマイクロホン数以上の音源を定位する手法について検討してきた．本稿では，マイクロホン間隔を広げ，マイクロホンアレーの空間解像度を向上することによって推定精度の向上を図る．また，その際高周波帯域において発生する空間エイリアシング問題を解決するための指標について検討する．実環境実験により，使用した音源定位法に依らず空間エイリアシング指標が有効であることを示す． |
| 題名 | 高次の可変ディジタルフィルタを用いた狭帯域雑音除去システムの改良 |
| 著者 | ◎熊本 裕樹, 越田 俊介, 阿部 正英, 川又 政征 (東北大学大学院工学研究科電子工学専攻) |
| Page | pp. 143 - 148 |
| Keyword | 狭帯域雑音除去, 適応信号処理, 可変帯域阻止フィルタ, 周波数変換, 差分方程式 |
| Abstract | 本稿では，高次の可変帯域阻止フィルタ(Variable Band-Stop Filter: VBSF)を用いた狭帯域雑音除去システムを改良する．一般的な高次のVBSFの実現法に基づく狭帯域雑音除去システムでは，VBSFのフィルタ係数をプロトタイプフィルタのフィルタ係数と可変パラメータで記述する必要がある．このため適応アルゴリズムの導出は困難である．本稿では，VBSFの内部状態を差分方程式で再帰的に記述し，任意の次数のVBSFを容易に実現する手法を提案する．そして，上記の提案法を用いて適応アルゴリズムを簡潔な形で導出する．最後に，計算例によって提案法が狭帯域雑音を除去できていることと高次のVBSFを用いる有効性を示す． |
| 題名 | グラミアン保存周波数変換を用いた高精度可変帯域通過・阻止フィルタの実現 |
| 著者 | ◎三好 啓太, 越田 俊介, 阿部 正英, 川又 政征 (東北大学大学院 工学研究科 電子工学専攻) |
| Page | pp. 149 - 154 |
| Keyword | 可変帯域通過フィルタ, 可変帯域阻止フィルタ, 状態空間表現, 周波数変換, 量子化誤差 |
| Abstract | 本論文では，グラミアン保存周波数変換を用いた高精度可変帯域通過・阻止フィルタの実現法を提案する．提案法では，帯域通過・阻止フィルタの中心周波数が可変となる．まず，プロトタイプ低域通過フィルタを平衡形などの高精度の構造で実現し，次に低域-帯域または低域-帯域阻止のグラミアン保存周波数変換をプロトタイプフィルタに適用する．これにより，プロトタイプフィルタの高精度を維持した可変帯域通過・阻止フィルタを実現できる．実現された可変帯域通過・阻止フィルタは状態空間表現により記述され，可変パラメータの値によらずフィルタの精度は一定である． |
| 題名 | Particle Swarm OptimizationによるCSD係数FIRフィルタの設計 |
| 著者 | ◎小中原 孝, 高橋 伸夫, 陶山 健仁 (東京電機大学工学部電気電子工学科) |
| Page | pp. 155 - 160 |
| Keyword | FIRフィルタ, Paticle Swarm Optimization, 混合整数計画 |
| Abstract | 本研究では，Particle Swarm Optimization(PSO)を用いたCSD係数FIRフィルタの設計について提案する．CSD係数はフィルタ係数に含まれる非零桁数を削減できる有効な表現方法であるが，その設計問題は混合整数計画問題となり，設計に膨大な時間を要する．そこで本研究では，近年，非線形計画問題に対するヒューリスティック解法として注目されているPSOを用いた設計法を提案する．設計例によって，提案法が分枝限定法を用いて算出した最適解に近い解を高速に算出可能であることを示す． |
| 題名 | (招待) オンデマンドバイオメトリックス認証 |
| 著者 | ○中西 功 (鳥取大学大学院) |
| Page | pp. 161 - 166 |
| Keyword | バイオメトリックス, オンデマンド認証, 脳波, 人体伝搬信号 |
| Abstract | 利用者管理を考えると一度きりの認証ではセキュリティ性は非常に低いため，必要な際に（オンデマンド）認証を行う必要がある．それには二つのアプローチが考えられ，一つは，生体情報を無意識に提示できるバイオメトリックスを選ぶこと，もう一つは．握るや触るといった継続した動作を利用するバイオメトリックスを用いることである．本論文では，前者の例として脳波，後者の例として人体伝搬信号を取り上げ筆者らのグループのこれまでの研究の成果を紹介する． |
| 題名 | (招待) 携帯端末による読み取りを考慮した印刷画像へのデータ埋め込み技術 |
| 著者 | ○棟安 実治 (関西大学) |
| Page | pp. 167 - 172 |
| Keyword | 2次元バーコード, 電子透かし, 携帯端末, 情報埋め込み, 印刷画像 |
| Abstract | 印刷物からインターネット上のデータへアクセスする手段として，2次元バーコードの利用が一般的になっている．これを代替するために，電子透かしの技術を応用して，自然画像にデータを埋め込み印刷し，携帯電話のカメラなどの入力デバイスを用いて画像を読み込み，埋め込まれたデータを抽出する手法が検討されている．本稿では，このような情報伝達のための電子透かし技術，特に携帯端末の利用を意識した印刷画像への情報埋め込み技術について，その概要といくつかの手法について解説を行う．概要ではシステムのモデルと留意点，アルゴリズム上の考慮すべき点について述べ，手法の紹介では画素領域と周波数領域を利用する方法をそれぞれ説明する． |
| 題名 | メモリアクセス高速化のための回路自動生成の一手法 |
| 著者 | ◎岸田 和也 (近畿大学大学院 総合理工学研究科), 神戸 尚志 (近畿大学 理工学部 電気電子工学科) |
| Page | pp. 173 - 178 |
| Keyword | メモリアクセス, オンチップメモリ, アーキテクチャ設計, システムLSI |
| Abstract | システムLSIは各種電子機器に広く利用され、年々複雑化・高度化が進み、設計の危機と言われている。特に、急激に複雑・高度化する各種アプリケーションは大規模なメモリやデータを高速にアクセスすることが多く、メモリアクセス部のアーキテクチャ設計が重要課題となっている。 本文では、この点に注目し、ハードウエアにおけるメモリアクセス方法に即した3種類のアーキテクチャ自動最適化手法(単変数に対するレジスタ化、オンチップへのデータ格納のパイプライン化、ループ構造を持つメモリアクセスに対するオンチップ配列化)を提案し、これらを統合したメモリアクセスアーキテクチャを実際に回路に適用し、その有効性を確認する。 |
| 題名 | (招待) LSI開発における高位合成の実用化の課題と適用事例 |
| 著者 | ○山下 公彰, 水田 剛, 森木 創作 (富士通九州ネットワークテクノロジーズ株式会社) |
| Page | pp. 179 - 184 |
| Keyword | 高位合成, 動作合成, ESL, システムLSI, SoC |
| Abstract | 半導体プロセス微細化の進化に伴い、LSIの設計生産性の危機が指摘されて久しい。生産性を向上する手段として高位合成技術が提案されており、その登場から10年ちかく経過しているが、当初の期待ほど普及しているとは言い難い。本稿では、LSI開発エンジニアの視点から、高位合成技術が製品の開発現場で適用が進みにくい理由について、リスクや適用効果の観点から分析を行う。また、リスクを回避して製品適用に成功した事例について紹介する。 |
| 題名 | 整数計画法による高位合成基本タスクの記述 |
| 著者 | ◎井上 恵介, 金子 峰雄 (北陸先端科学技術大学院大学) |
| Page | pp. 185 - 190 |
| Keyword | 高位合成, 整数計画法 |
| Abstract | LSI設計における高位合成では，入力として計算アルゴリズムを受け取り，制御スケジューリング，演算器割り当て，レジスタ割り当ての三つのタスクを行う．これまで，これらのタスクを段階的に行う手法や二つのタスクを同時に行う手法が提案されているが，こうした順次最適化では，解の最適性を保証できず，また，発見的手法としての妥当性も曖昧である．本稿では，整数計画問題として定式化することにより，高位合成における三つのタスクを同時に最適化する手法を提案する．こうして得られる整数計画問題に対して，計算量の観点から厳密解を求めることは難しいと予想されるが，従来の枠組みにとらわれない新しい発見的手法への足がかりを提供でき ると期待される． |
| 題名 | (招待) 高位合成における種々の最適化手法について |
| 著者 | ○松永 裕介 (九州大学) |
| Page | pp. 191 - 196 |
| Keyword | 高位合成, 最適化, スケジューリング, アロケーション, パイプライン |
| Abstract | 高位合成とは，動作記述からレジスタ転送レベルの回路を自動生成する処理であり，演算をいつ実行するのか(スケジューリング)， どのような演算器を使用するのか(アロケーション)， どの演算器やレジスタに演算や変数を割り当てるのか(バインディング)， といった子問題を同時にあるいは逐次的に解く必要がある． 一般にこれらの問題を厳密に解くことは難しく， 多くの場合はヒューリスティックを用いた近似手法が用いられる． 本稿では，古典的ではない高位合成の最適化手法として，2つの手法を紹介する。 |
| 題名 | RSA暗号に対するスキャンベース攻撃 |
| 著者 | ◎奈良 竜太, 佐藤 圭, 戸川 望 (早稲田大学基幹理工学部情報理工学科), 柳澤 政生 (早稲田大学基幹理工学部電子光システム学科), 大附 辰夫 (早稲田大学基幹理工学部情報理工学科) |
| Page | pp. 197 - 202 |
| Keyword | RSA暗号, スキャンベース攻撃, スキャンパス |
| Abstract | 本稿ではRSA暗号に対するスキャンベース攻撃について研究した． 提案手法によりRSA暗号を処理している間のスキャンデータを取得・解析することで 鍵長1,024ビット時たかだか30個，鍵長2,048ビット時たかだか35個の入力で 秘密鍵を解読することに成功した． |
| 題名 | アプリケーション固有の情報を利用したモデル生成法とSRAM歩留計算への応用 |
| 著者 | ○松岡 英俊, 池田 弘, 樋口 博之, 富田 憲範 (�衂抻猟霧Φ羹�) |
| Page | pp. 203 - 208 |
| Keyword | SRAM, 歩留, バラツキ, 応答局面, 多項式 |
| Abstract | 我々はアプリケーション固有の物理情報を用いてモデル化を行う手法[1]を提案した。提案手法では実行済の条件の異なる多数のシミュレーション結果からアプリ固有情報を抽出し、モデル生成時に、その情報を用いて精度向上、高速化を実現している。SRAMの歩留計算への応用では、モデルを用いない従来法と比べ700倍、モデルを用いた従来法と比べても10倍の高速化を達成している。本論分では新たに提案手法の精度向上の効果をより詳しく分析した結果を示す。提案法では、精度向上効果の高い領域に絞って発生した少ないサンプルで高次成分を持ったモデルを安定的に生成できており、それが一部のモデル化しにくいサンプルの精度向上に寄与していることを示す。 |
| 題名 | 有向閉路型走行経路を用いたAGVシステムにおける総移動距離を最小化する乱択オンラインアルゴリズムの競合比解析 |
| 著者 | ◎小泉 賢司 (豊橋技術科学大学 電子・情報工学専攻), 増山 繁 (豊橋技術科学大学 知識情報工学系) |
| Page | pp. 209 - 214 |
| Keyword | AGVシステム, オンラインアルゴリズム, 競合比解析, マルコフ過程, 乱択アルゴリズム |
| Abstract | 本研究は，AGVの動作を中央処理装置が管理するAGVシステムにおいて，オンラインモデルにおける，全AGVの移動距離の総和(総移動距離)の最小化を目的とした搬送スケジューリングを行うオンラインアルゴリズムを提案する．AGVシステムで用いる走行経路形状を有向閉路型に限定し，搬送を行うか否かを確率を用いて決定する乱択オンラインアルゴリズムを提案する．また，提案する乱択オンラインアルゴリズムの理論的な性能評価を競合比解析により行う．競合比解析においては，まず，一部の解析過程を，AGV システム内のAGV数を一般のkとした場合について記述し，具体的に競合比を導出する際はAGV 数を2台に固定して解析を行った． |
| 題名 | カンファレンスプログラムの自動編成について |
| 著者 | 畑 守之, ○田岡 智志, 渡邉 敏正 (広島大学大学院) |
| Page | pp. 215 - 220 |
| Abstract | カンファレンスとは学術的な研究発表会や国際会議などの総称であり，実施まで に多くのプロセスを経る．その際，数十件から数千件の投稿論文を扱うため，セッ ションスケジューリングにも多くの労力と時間がかかる．セッションスケジュー リングは，組合せ的な制約条件（同じ時間帯での著者/座長の重複の禁止等）を 満たしつつ評価値を最適化する組合せ最適化問題の一種であり，NP-困難である． セッションスケジューリングにおける制約条件は数多く存在し，これらの制約を なるべく多く満たすプログラム (発表時間割表) を求める必要がある．本研究で は，組合せ最適化問題に対する発見的解法として知られている近傍探索法，山登 り法を利用した発見的解法を提案し，計算機実験によりその有用性を示す．加え てセッションスケジューリングに関するさまざまな問題解決を支援するための実 装機能も紹介する． |
| 題名 | 逆探索に基づく p6 タイリングの生成 |
| 著者 | ◎山根 祥悟, 堀山 貴史 (埼玉大学 理工学研究科) |
| Page | pp. 221 - 226 |
| Keyword | 逆探索法, タイリング, polyiamond, 回転対称, 列挙アルゴリズム |
| Abstract | Polyiamondは単位正三角形を辺同士が接続するように 組み合わせてできる図形である。本稿では、2つの回転 中心により、60度回転と120度回転を繰り返すことで 平面を隙間もなく、重なりもなく、平面に敷き詰め られる p6 タイリング可能な polyiamond の生成法に ついて述べる。従来法では試行錯誤により図形を生成 するが、本稿で提案するアルゴリズムは逆探索を利用し、 ルールに従い図形の生成を行う。9個の単位正三角形に よる 29種類の図形までを生成した従来法に対し、提案 手法では 21個の単位正三角形による 27,436種類と 有意に多種の図形を生成することに成功した。 |
| 題名 | 8面，20面ダイスを用いたRolling Dice PuzzleのNP完全性 |
| 著者 | ◎上嶋 章宏 (大阪電気通信大学大学院 工学研究科 情報工学専攻), 岡田 貴裕 (日新システムズ) |
| Page | pp. 227 - 232 |
| Keyword | 計算量理論, NP完全, Rolling Cube Puzzle, 正多面体 |
| Abstract | 本研究では，既存のRolling Cube Puzzleを一般化したRolling Dice Puzzleを提案し，8面，20面ダイスを用いたRolling Dice Puzzleの計算複雑さを議論する．本問題は，盤面上に記載された移動規則に従いダイスを回転させ，中継点ごとに指定される状態に遷移しながら，全ての中継点を通過する経路を探索する問題である．正多面体ダイスに限定した場合，通常の6面ダイスを用いる問題のNP完全性はすでに証明されており，本研究で扱う2問題のみが未解決であった．本稿では，ハミルトンパス・閉路問題からの多項式時間還元を示すことで，両問題のNP完全性を示す． |
| 題名 | (招待) 車載システムを対象とした形式手法の応用研究と課題 |
| 著者 | ○佐野 範佳 (豊田中央研究所) |
| Page | pp. 233 - 233 |
| Keyword | 形式手法, 車載システム, 組込みシステム, 課題 |
| Abstract | 車載組込みシステムの高信頼化･開発効率化をねらいとして，形式手法が活用されつつある．モデル検査に関しては，モデル検査器を組み込んだ制御系設計ツールなどにより活用の目処が立っているが，広い意味で形式手法を活用した開発プロセス・開発方法論に関しては，まだ試行錯誤を積み重ねている段階であると思われる．そのような状況のもと，車載システムを対象とした形式手法の応用研究と研究課題について紹介する． |
| 題名 | (招待) 宇宙機ソフトウェアに対するIV&Vにおけるモデル検査の適用事例 |
| 著者 | ○松本 勉 (宇宙航空研究開発機構), 氏原 頌悟 (三栄ハイテックス) |
| Page | pp. 234 - 239 |
| Keyword | IV&V, 独立検証, モデル検査 |
| Abstract | 宇宙航空研究開発機構（JAXA）では、宇宙機に関するソフトウエアの信頼性を向上させ、安全性を確保するために、形式手法を用いた検証技術の研究・実用を図っている。本稿では、多数の実プロジェクトにおいて実施されている独立検証及び有効性確認（IV&V：Independent Verification and Validation）の活動概要と、その活動の中で評価手法の一つとして使用しているモデル検査について、これまで中核として実施している、ソフトウェア要求仕様に関する状態遷移モデルを用いた評価手法や、最新の導入事例として、異常時運用手順に関する評価手法について紹介する。 |
| 題名 | (招待) 大規模並列計算のためのアルゴリズミックス |
| 著者 | ○渡辺 治 (東京工業大学) |
| Page | pp. 240 - 243 |
| Keyword | 大規模並列計算, 分散計算, GPU 計算 |
| Abstract | 計算世界観による科学の手法を実現していくには，スパコンなど 最近の大規模並列コンピュータをうまく使いこなす技術の開発が 必要である．大規模並列計算を設計するアルゴリズム論について ２つのテーマの背景と研究方針そして基本的な計算モデルについ て述べる． |
| 題名 | (招待) CUDA Implementation of Iterative Updating: the Radix-2 Algorithm and Discrete Fourier Transforms |
| 著者 | ○Mikael Onsjö, Kenta Kasai, Osamu Watanabe (Tokyo Institute of Technology) |
| Page | pp. 244 - 248 |
| Keyword | GPU, DFT, bank-conflict |
| Abstract | We consider the problem of computing f_m(f_{m-1}(...f_1(x)...)). This generalizes "butterfly" algorithms, such as Radix-2 for computing Fourier transforms. We demonstrate how to use a graphics Processing Unit (GPU) to perform a large number of executions of these algorithms efficiently in parallel. In particular, we discuss an algorithmic way for reducing the bank conflicts in the GPU implementation. |
| 題名 | (招待) 双曲型方程式のマルチGPUによる大規模高精度計算 |
| 著者 | ○杉原 健太 (東京工業大学大学院 理工学研究科), 青木尊之 (東京工業大学 学術国際情報センター) |
| Page | pp. 249 - 254 |
| Keyword | GPU, CUDA, Tesla, TSUBAME, Overlap |
| Abstract | 3次元移流方程式に対して、NVIDIA の Tesla S1070 を搭載したスパコン TSUBAME を用いて CUDA プログラミングを行った。単一 GPU での 1 次~6 次精度差分法や 5 次精度 WENO 法の計算に 対し演算性能の測定および評価を行い WENO では 289 GFlops を達成した。さらに、複数の GPU を用 いて3次元領域分割に基づく並列化を行い、60 GPU で 6.1 TFlops の実行性能を達成した。また、各計算 領域をさらに 7 つの Kernel に分け非同期実行するこ とによる「計算 Kernel, Device-Host 間通信, MPI 通 信」3つのオーバーラップテクニックを提案し、そ れにより 60 GPU で 7.8 TFlops の実行性能を達成し た。また、このオーバーラップテクニックは直交格 子のステンシル計算全般で適用可能である。GPU 計 算は従来の CPU による計算と比べて非常に高速で あり、有効性が高い。 |
| 題名 | (招待) On the Scalability of Parallel Best First Search |
| 著者 | Akihiro Kishimoto, ○Alex Fukunaga (Tokyo Institute of Technology), Adi Botea (NICTA / Australian National University) |
| Page | pp. 255 - 256 |
| Keyword | 探索, 並列計算, 人工知能 |
| Abstract | We investigate the scaling of HDA*, a simple, parallel best-first search algorithm. Experimental results using up to 1024 cores for the domain-independent planning problem will be presented. |
| 題名 | (招待) 複雑系数理モデリングとその応用 |
| 著者 | 合原 一幸 (東京大学) |
| 2010年4月20日(火) |
| 題名 | Explicit Effective Capacitance Model for CMOS Gate with Interconnect Load |
| 著者 | ◎Minglu Jiang (Graduate School of Information, Production and Systems, Waseda University), Zhangcai Huang (Fukuoka Industry, Science and Technology Foundation), Atsushi Kurokawa (SANYO Electric Co., Ltd), Yasuaki Inoue (Graduate School of Information, Production and Systems, Waseda University) |
| Page | pp. 257 - 262 |
| Keyword | effective capacitance, gate delay, non-iterative |
| Abstract | Delay evaluation is always a vital concern for the highperformance digital VLSI design. The conventional methods usually use an iterative method to ensure the accuracy of the effective capacitance Ceff, which is usually used to compute the delay of gate with interconnect load and to capture the output signal shape of the real gate response. In this paper, a polynomial approximation method is used to make the nonlinear Ceff equation be solved without iterative method. Compared to the conventional methods, the proposed method has the merit of improving the efficiency for Ceff calculation. Meanwhile, experimental results show that the proposed method is in agreement with the Spice simulation. |
| 題名 | GPGPUによる統計的寄生容量抽出アルゴリズムの並列実装 |
| 著者 | ○渡邉 貴之, 槙 雄亮 (静岡県立大学経営情報学部) |
| Page | pp. 263 - 268 |
| Keyword | GPGPU, 容量抽出, モンテカルロ法, ランダムウォーク |
| Abstract | 本論文では、GPUを用いた寄生容量抽出アルゴリズムの並列実装例について示す。並列化の対象とした抽出アルゴリズムは、よく知られているフローティング・ランダムウォークによるモンテカルロ積分を用いた統計的手法である。モンテカルロ法は並列化が容易であり、本論文で対象とした抽出アルゴリズムについても、すでにPCクラスタやマルチコアCPUでの実装が報告されている。本研究では、コア数が多いながらもコアあたりの性能がCPUに比較して低く、実装における制約もあるGPUを用いて上記アルゴリズムを実装し、その性能について評価する。 |
| 題名 | A Chaos Associative Memory with Tchebycheff Activation Function |
| 著者 | ○Masahiro Nakagawa (Faculty of Engineering, Nagaoka University of Technology) |
| Page | pp. 269 - 274 |
| Keyword | chaos neuron, periodic mapping, associative memory |
| Abstract | In this paper we shall put forward a novel chaos neuron model and investigate the dynamic properties of memory retrievals. The present artificial neuron model is defined by such periodic input-output mapping as the Tchebycheff function of the second kind. It is apparently shown that the present neural network with a periodic activation function has an ability of the retrievals of the embedded patterns superior than the conventional neural network with such a monotonous mapping. This advantage is considered to be as a result of the nonmonotonous property of the periodic mapping which involves a chaotic behaviour of the neurons. It is also found that the present chaos neuron model has a remarkably larger memory capacity than the conventional association system with the monotonous dynamics. These findings are considered to result from the chaotic dynamics to avoid at an unfavourable spurious states. |
| 題名 | 低次Volterra FIlterベースのカオス変調システムの暗号強度検証に関する研究 |
| 著者 | 佐藤 元樹, ◎川西 義明, 鎌田 弘之 (明治大学) |
| Page | pp. 275 - 278 |
| Keyword | カオス, 暗号, 解析 |
| Abstract | カオス理論を用いた変復調システムはディジタル通信網におけるセキュリティ確保の手段のうちの１つである。 筆者らは、Chaotic Neuron Type Nonlinearityをベースに非線形要素を組み込んだ変調システムを提案してきた。 また、カオス変調システムではブルートフォースアタック以外に解析法が確立されていなかったが、[軽井沢2009]にて 固定小数点演算における非オーバーフロー点を用いた解析法が提案された。さらに、[FIT2009]では、その解析法を 想定したカオス変調システムの提案を行った。 本論文では、[FIT2009]で提案された変調システムに対して解析を行うことでどのような環境下で解析が可能であるかを 明らかにする。 |
| 題名 | 一方向結合と相互結合の両者を含む神力型カオス発生回路の結合系 |
| 著者 | ◎海老澤 謙一, 三堀 邦彦 (拓殖大学大学院 工学研究科 電子情報工学専攻) |
| Page | pp. 279 - 284 |
| Keyword | カオスの同期, 一方向結合, 相互結合, 一般化同期, 神力回路 |
| Abstract | カオスは決定論的な系に発生する、複雑かつ不規則な振動である。カオス発生回路の抵抗結合系では、カオスの同期が発生する。カオスの同期とは、各回路で発生するカオスの間で位相が揃う現象である。主な構成として一方向結合系と相互結合系がある。回路同士の間で信号が一方向に伝わる結合を一方向結合、信号がお互いを行き来する結合を相互結合と呼ぶ。各々の結合系においてカオスの同期の発生が報告されている。これに対し、本研究では、両方の結合方式を含む系に注目する。Zhen等はこれに発生する現象を数式モデルで調べたが、電子回路実験での報告例はない。我々はこの問題にアプローチした。 |
| 題名 | 結合三角形型発振器ネットワークで観測される同期現象 |
| 著者 | ○上手 洋子 (University/ETH Zurich), 西尾 芳文 (徳島大学), Ruedi Stoop (University/ETH Zurich) |
| Page | pp. 285 - 288 |
| Keyword | 結合発振器, 同期現象, ネットワークトポロジー, 理論解析 |
| Abstract | 結合発振器は，実物理システムで観測される高次の非線形現象を説明する優れたモデルである． 結合発振器は，位相伝搬波やクラスタリングなどといった興味深い位相同期パターンを生み出すことも知られており， この位相同期パターンを連想記憶や学習過程といった脳の情報処理モデリングに応用できるのではないかと期待されている． また，自然界には蜂の巣構造で有名なハニカム構造や結晶構造など様々なタイプのネットワーク構造が存在する． しかし，発振器の大規模結合系の研究としては，環状や二次元格子状のモデルが多く， 多角形が結合されたネットワークトポロジーについての研究はこれまであまり報告されていない． 我々は，発振器をより複雑なネットワーク構造に応用することで，それぞれのネットワーク構造が持つ 新しい特徴を見出すことができるのではないかと考える． 本研究では，多角形が結合された大規模ネットワーク研究の第一段階として， 二つの三角形型 van der Pol 発振器ネットワークの一辺を介して結合したシステムで観測される同期現象について コンピュータシミュレーションおよび理論解析によって調査を行う． さらに，結合抵抗部分の消費電力を求め，同期現象とエネルギーの関係を明らかにする． |
| 題名 | 冗長アルゴリズムSAR ADCのテスト容易化技術 |
| 著者 | 小川 智彦, 小林 春夫 (群馬大学大学院/工学研究科), ◎伊藤 聡志, 上森 聡史, 丹 陽平 (群馬大学/工学部), 高井 伸和, 山口 隆弘 (群馬大学大学院/工学研究科) |
| Page | pp. 289 - 294 |
| Keyword | 逐次比較近似ADC, デジタル誤差補正, 冗長性, テスト容易化, ADCテスト |
| Abstract | この論文では冗長アルゴリムを用いたSAR ADCのテスト容易化技術を考察する．冗長アルゴリズムSARADCではコンパレータの誤判定を許容するため，内部DAC出力の整定を待つ必要がなく高速サンプリングが実現できる．この冗長SAR ADCの最終出力と各ステップのコンパレータの判定値から各ステップでのDAC出力の整定値を推定し，スピード余裕を知る方式を提案する．このことにより温度・電源電圧を変化させてテストを行う工数を削減できテストコストが減少できる．さらに出荷時のATEによるスピード余裕推定をもとにチップ毎のプロセス変動に応じて最適な冗長アルゴリズムを選択する再構成可能なSAR ADCを提案する． |
| 題名 | インターリーブＡＤＣでのタイミングスキュー影響のデジタルフィルタによる補正技術 |
| 著者 | 浅見 幸司 (（株）アドバンテスト), ◎黒沢 烈士, 立岩 武徳, 宮島 広行, 小林 春夫 (群馬大学) |
| Page | pp. 295 - 300 |
| Keyword | インターリーブADC, タイミングスキュー, デジタルフィルタ |
| Abstract | この論文ではインターリーブADCのチャネル・サンプリング・クロック間のタイミングスキューの影響をデジタルフィルタで補正する新手法を記述する．インターリーブADCではチャネル間のミスマッチによる影響が問題となっている．インターリーブADCのタイミングスキューの影響を解析し，タイミングスキュー校正を行うデジタルフィルタを設計する．さらにそのフィルタのインターリーブADCのタイミングスキュー校正への適用とその有効性をシミュレーションで示す． |
| 題名 | Large Input-Scale Delta-Sigma AD Modulator with Error-Feedforward Architecture |
| 著者 | ◎Takumi Shimizu, Hao San, Masao Hotta (東京都市大学集積化システム研究室) |
| Page | pp. 301 - 305 |
| Keyword | Delta-sigma modulator, Error-Feedforward, MASH |
| Abstract | This paper proposes a two-step architechture of delta-sigma AD modulator for large scale input signal. By adding an error-feedforward structure in the front end of the delta-sigma AD modulator, only the quantization noise is processed at the following stage, and allowable input-scale of the modulator is greatly improved. The proposed modulator can be simply reconfigured from conventional full-feedforward delta-sigma AD modulators which is suitable for reuse the modulators circuit with minimum re-design. The proposed modulator is similar to a cascade of two-stage MASH architechture. However, the first stage of the modulator is just a multibit quantizer without any analog/digital loop filters working as an error-feedforward structure. Moreover, the second stage of modulator does not use any digital filters to cancel out the quantization noise of the first stage, therefore the noise leakage propolem of MASH modulator can be relaxed systematically. MATLAB simulation results prove the effectiveness of the proposed modulator structure. |
| 題名 | 単一インダクタ2出力DC-DCコンバータの検討 |
| 著者 | 津志田 健吾, ◎美和 俊介, 高橋 健司, 横尾 甫, 今井 亮輔, 村上 和貴, 岩瀬 浩之, Santhos A. Wibowo, 小林 春夫, 高井 伸和 (群馬大学大学院工学研究科電気電子工学専攻), 小田口 貴宏, 高山 茂樹, 深井 功, 松田 順一 (旭化成東光パワーデバイス株式会社) |
| Page | pp. 306 - 311 |
| Keyword | 単一インダクタ, チャージポンプ方式, 疑似連続モード |
| Abstract | 本論文では、単一インダクタを用いた2出力DC-DCコンバータを検討する。チップサイズ縮小、低コスト化を図り、疑似連続モードを用いたクロスレギュレーションの改善、さらにチャージポンプ方式を用いた負電圧可変手法の提案と解析、そのシミュレーション結果を示す。 |
| 題名 | A Low Voltage CMOS Rectifier for Low Power Battery-less Devices |
| 著者 | ○Qiang Li (Graduate School of Information, Production and Systems Waseda University), Zhangcai Huang (Fukuoka Industry, Science and Technology Foundation), Minglv Jiang, Renyuan Zhang, Yasuaki Inoue (Graduate School of Information, Production and Systems Waseda University) |
| Page | pp. 312 - 315 |
| Keyword | 1, 9, 8, 6 |
| Abstract | This paper presents a low voltage CMOS full-wave rectifier for transcutaneous power transmission in low power battery-less devices such as biomedical implants. By using a simple comparator-controlled switch which needs a small supply voltage, the lowest input voltage amplitude can be reduced to 0.7V With only one comparator, the proposed design dramatically reduces the power loss and the production cost. The proposed rectifier can achieve a maximum peak voltage conversion efficiency of more than 93% and a power efficiency of approximately 87%. |
| 題名 | An Efficient Charge Pump Based on Cockcroft-Walton Structure |
| 著者 | ◎Renyuan Zhang, Qiang Li (Graduate School of Information, Production and Systems Waseda University), Zhangcai Huang (Fukuoka Industry, Science and Technology Foundation), Minglv Jiang, Yasuaki Inoue (Graduate School of Information, Production and Systems Waseda University) |
| Page | pp. 316 - 321 |
| Keyword | Cockcroft-Walton type, transistor gate capacitance, level shift, voltage boosting efficiency, power efficiency |
| Abstract | This work proposes a Cockcroft-Walton type charge pump circuit, in which each device including transistor and capacitor just stands against the voltage no more than the supply voltage Vdd. Therefore a low breakdown voltage fabrication of pumpingcapacitors can be applied in the proposed circuit. Furthermore, the level shift technique can be also realized in the proposed circuit to enhance the power efficiency. With a 0.18um standard CMOS process the proposed circuit can obtain the power efficiency more than 85%, and the voltage boosting efficiency of 96% which is 12% more than the recent improved Dickson type charge pump. |
| 題名 | 高スループット固定小数点FFT回路実装における量子化および計算誤差とハードウエア量に関する検討 |
| 著者 | ○高野 光司, 大庭 信之, 片山 泰尚 (日本アイ・ビー・エム株式会社/東京基礎研究所) |
| Page | pp. 322 - 327 |
| Keyword | 固定小数点FFT, 高スループット, 802.15.3c |
| Abstract | 近年、通信分野では直交波周波数分割多重(OFDM)のような周波数領域での情報処理を行うためにFFTが用いられている。通信の広帯域化に伴い、FFTには高スループット化と高次数化が求められるがハードウエア量の増加は避けられない。一方で、扱う情報の広帯域化によりAD/DA変換器のEffective Number of Bits(ENoB)が低下しており、FFTが必要以上の精度をもつことは、FFTのハードウエア量の観点から非効率である。本論文では、入出力データのENoBとFFTの特性を考慮し、FFTを少ないハードウエア量で十分な演算精度を得る方式について述べる |
| 題名 | アンダーサンプリング方式パルスレーザ測距装置のラグランジュの定理に基づく高速化 |
| 著者 | ○大石 政裕 (�螢肇廛灰� 技術開発グループ 研究開発センター), 大友 文夫 (�螢肇廛灰� 技術開発グループ), 矢部 雅明, 鹿子木 満, 齋藤 貴昭, 鈴木 康顕, 小野田 岳志 (�螢肇廛灰� ポジショニングビジネスユニット), 徳田 義克 (�螢肇廛灰� 技術開発グループ 研究開発センター), 長澤 親生 (首都大学東京 大学院システムデザイン研究科) |
| Page | pp. 328 - 333 |
| Keyword | undersampling, rangefinder, pulse, laser |
| Abstract | A new Speedup technique based on Lagrange's Theorem of a rangefinder with a pulsed laser using an undersampling method has been developed. In the undersampling method, frequency conversion and digitizing are conducted by sampling reference frequency signals at timing of reception of pulsed light from a target. In the present work, by employing change of a period of an emitting pulsed light without changing a synthesizer frequency which generates the period, the rangefinder generates the different sampling interval of the reference frequency signal. The technique allows us to control the minimum number of sampling for the calculation of distance measurement, so that high-speed data acquisition time for coarse measurement and normal data acquisition time for fine measurement are selectable. |
| 題名 | 複数の移動型ロボットによる天井マップ共有システムにおける伝送データ量の削減 |
| 著者 | 福谷 泰明, 高橋 知将, ◎松本 拓也, 岩橋 政宏 (長岡技術科学大学電気系), 木村 哲也 (長岡技術科学大学システム安全系) |
| Page | pp. 334 - 339 |
| Keyword | ロボットビジョン, JPEG2000 |
| Abstract | 本システムでは、屋内を移動するロボットに設置された、天井方向のカメラから得られる動画像から、一枚の天井マップ静止画像が生成される。次に、この先行機に追従して移動するロボットの自己位置が、その天井マップ上に表示される。この際、膨大な量の動画像データが通信される。従って、追従機数の増加に伴い、ネットワーク容量の不足が生じる。我々は既に、追従機の自己位置推定にとって必要最小な情報のみを伝送することで、ロボット通信に要するデータ伝送量を削減できる機能的階層符号化を報告した。また、前面方向のカメラから得られる動き情報を用いることで、不整地走行時の自己位置推定の精度を向上させた。本報告では、先行機にデータ伝送量の負荷を集中させることで、追従機の伝送量を大幅に削減させる。これにより、ネットワークの限られた伝送容量のもとで、より多くの追従機の参加が可能となる。 |
| 題名 | ドライビングフィーリング分析のためのドライバ挙動計測システムの検討 |
| 著者 | ○福間 慎治, 花井 雅典, 佐藤 亮介, 森 眞一郎 (福井大学大学院工学研究科), 林 憲孝 (富士重工業) |
| Page | pp. 340 - 345 |
| Keyword | 自動車, 運転者, 光学式モーションキャプチャ, フィーリング |
| Abstract | 本報告では自動車を運転中のドライバ挙動計測システムの検討と評価を行う．ドライバの頭部姿勢と操縦動作を，ステアリング角，加速度，位置等の車両挙動と同時に測定し，「運転のしやすさ」−ドライビングフィーリングと結びつける．ドライバ挙動は画像計測とし，頭部姿勢はステレオカメラ，操縦動作はモーションキャプチャで測定する．コースで実車走行実験を行い，ドライバ挙動とドライビングフィーリングの間の関係を考察する． |
| 題名 | ロバスト電子透かしを目的とした反復埋込法の提案 |
| 著者 | ◎中本 昌由, 左山 紘平 (広島大学), 棟安 実治 (関西大学), 大野 修一 (広島大学) |
| Page | pp. 346 - 351 |
| Keyword | 電子透かし, 反復埋込み, 離散ウェーブレット |
| Abstract | 近年，インターネットの普及によって世界中のユーザが手軽に画像・動画等のさまざまなディジタルコンテンツにアクセスすることが可能になりつつある．その利便性の一方で，ディジタルコンテンツの不正なコピーや配布が問題となっている．電子透かしは，ディジタルコンテンツに透かし信号を埋め込むことによって著作権を保護する手法として注目を集めている．本論文では，電子透かし法のロバスト性向上を目的として新しい埋込み方法と検出方法を提案する．本論文では，1つの秘密鍵（疑似乱数の初期値）から生成される疑似乱数列から K セットの透かし信号を作成し，それを繰返し埋込んだ場合（これを反復埋込みと呼ぶ．）の相関値と画質劣化について解析を行う．また，反復埋込み法のこの性質を利用した新しい検出法を提案する．これは，K 回の反復で埋込んだ透かしについてそれぞれ相関値を計算し，それらが正となる相関値の個数によって透かしの有無を判定するものである．計算機シミュレーションでは， 標準画像Lennaに対して埋込み実験を行い，各種画像処理への耐性を示す． |
| 題名 | H.264/AVCにおけるフレーム間およびフレーム内予測を考慮したマクロブロック高速選択法 |
| 著者 | ◎藤井 健一, 市毛 弘一 (横浜国立大学 大学院 工学府 /工学研究院) |
| Page | pp. 352 - 357 |
| Keyword | H.264/AVC, マクロブロック選択法, 高速化手法, 動き予測 |
| Abstract | 本論文では動画像圧縮符号化技術の国際標準であるH.264/AVCにおけるマクロブロックの高速化手法について述べる． マクロブロックを選択するために行うコスト計算を伴なう処理は複雑で時間がかかることで知られている． そのためマクロブロックをいかにして効率よく選択するか，ということは圧縮速度を高めるための手段として非常に効果的であるといえる． 本研究では，事前に用いたサブマクロブロックの情報を保持し，空間的，時間的に相関の高いマクロブロックのみを候補とする手法と フレーム内予測でマクロブロック内の画素値からどのマクロブロックを適用するのが適切かを判定する手法を組み合わせることで， さらなる高速化が実現可能であることを確認する． |
| 題名 | 位相情報に基づく歯科X線画像認証アルゴリズムと大規模データベースを用いた性能評価 |
| 著者 | ○伊藤 康一, 半澤 雄希, 青木 孝文 (東北大学), 小菅 栄子 (神奈川歯科大学) |
| Page | pp. 358 - 363 |
| Keyword | 個人識別, 歯科X線画像, バイオメトリクス, 位相限定相関法, 身元確認 |
| Abstract | 歯科X線画像は，歯科診療における資料として，また大規模災害における犠牲者の身元確認の手段として広く利用されている．身元確認作業の大部分は，専門家の手画像で行われているため，膨大な時間を要する．そこで，歯科X線画像を用いて自動的に素子確認を行うシステムの要求が高まっている．これに対し，本論文では，位相限定相関法を用いた歯科X線画像の認証アルゴリズムを提案する．また，大規模なデータベースを用いて，大規模災害を想定した性能評価実験を行い，提案アルゴリズムの有効性を評価する． |
| 題名 | ＳＯＭを導入した形状認識ユニットによる形状認識・抽出手法の開発 |
| 著者 | ◎小山 将人, 鷲見 育亮 (鳥取環境大学), 植田 拓也 (（株）ギャラクシー), 薮木 登 (津山工業高等専門学校), 築谷 隆雄 (松江工業高等専門学校) |
| Page | pp. 364 - 369 |
| Keyword | 形状認識, 形状抽出, SOM, 輪郭, 道路標識 |
| Abstract | 本論文では、画素の欠損に影響を受けにくい形状認識・抽出手法の検討を行い、自己組織化マップ（Self Organizing Map：SOM）[1]を導入した形状認識ユニットを開発し、それを用いた新しい形状認識法を開発したことを報告する。開発した形状認識法で、形状認識・抽出 実験を行い、実験結果から、クラスタリング特性を持つSOＭを形状認識ユニットに導入し、そのユニットを本手法に組み込むことで、輪郭 線の欠損に影響されにくい、本手法の有効性を確認した。 |
| 題名 | RTOSのハードウエア化によるソフトウエアベースTCP/IP処理の高速化と低消費電力化 |
| 著者 | ○丸山 修孝 (ネットクリアスシステムズ（株）), 石原 亨, 安浦 寛人 (九州大学) |
| Page | pp. 370 - 375 |
| Keyword | TCP/IP, RTOS, ASIC, Network Processor |
| Abstract | 近年のネットワーク技術における高速化ニーズの高まりに対応し、MAC、PHY部のみならずTCP/IPの高速化も求められている。組み込みシステムにおいて数100Mbps以上のTCP/IPスループットを達成することは、組み込み型CPUの性能から言って大変困難であり、また消費電力的にも問題がある。我々はTCP/IPのソフトウエアを解析し、プロトコル処理以外の大部分の処理をハードウエア化することによりTCP/IPの処理の高速化を実現した。特に重要なのはRTOSをハードウエア化したことであり、これにより従来にない性能を達成しつつ、プロトコルソフトウエアの柔軟性を維持することができた。実験結果では従来のプロセッサに比較し約10倍のスループットをが達成しつつ、消費電力は1/7であった。 |
| 題名 | メモリ混載型メディアン・フィルタの設計 |
| 著者 | ◎山本 竜也, モシニャガ ワシリー, 橋本 浩二 (福岡大学大学院 工学研究科 電子情報工学専攻 / 計算機システム研究室) |
| Page | pp. 376 - 381 |
| Keyword | メモリ混載型, メディアン・フィルタ, 低消費エネルギー, 演算量削減, ビットシリアル型 |
| Abstract | 本発表では、メモリ混載型メディアン・フィルタのアーキテクチャを提案している。このアーキテクチャでは、メモリ・バスおよび内蔵メモリ等で構成されるSoCに適した、専用に設計されたSRAMとビット・シリアル型メディアン・フィルタ回路で構成される高性能・小規模画像メディアン・フィルタを構成することができ、またプロセッサ-メモリ間データ・アクセス量を削減できるため、低消費エネルギーかつ高速な画像フィルタリング処理SoCを実現できる。 |
| 題名 | (招待) 波動問題に対する GPU を用いた大規模格子系シミュレーション |
| 著者 | ○青木 尊之 (東京工業大学/学術国際情報センター) |
| Page | pp. 382 - 387 |
| Keyword | GPU, 波動問題, 格子ボルツマン法, リアルタイム津波シミュレーション, 圧縮性流体計算 |
| Abstract | GPGPU (General-Purpose Graphics Processing Unit) can be easily applied to the computation of such wave phenomena as electromagnetic wave propagation, since explicit numerical methods are available for them. We demonstrate a compressible flow solving Euler equation with a higher-order numerical scheme IDO-CF and the performance of 54 GFlops on NVIDIA GeForce GTX 285 was achieved. The multi-GPU computing for Lattice Boltzmann method is carried out on the Tesla GPU of TSUBAME grid cluster of Tokyo Tech with 100 GPUs. The shallow water equation for the real-time tsunami simulation is also solved on the multi-GPU and the overlapping technique between the communication and computation to hide the GPU-to-GPU communication time. The Tesla 10 GPUs achieved the performance comparable with 1000 TBUBAME Opteron CPUs |
| 題名 | (招待) 高速電子設計のための多並列SI/PI/EMIシミュレーション技術 |
| 著者 | ○浅井 秀樹 (静岡大学) |
| Page | pp. 388 - 391 |
| Keyword | 高速電子設計, 多並列シミュレーション, シグナル/パワー・インテグリティ, EMI, 回路/電磁界シミュレーション |
| Abstract | 昨今、半導体や高密度基板など電子回路の高集積化や高周波化に伴い、大規模電気シミュレーション技術に対する要求は高まる一方である。折から、マルチコアやGPU等のハードウエア・アクセラレータの出現により、並列計算技術を利用したシミュレーションの劇的な高速化が実現されつつある。本稿では、高速伝送設計において不可欠となっているシグナル／パワー・インテグリティや電磁妨害の振る舞いを見積もるためのSI/PI/EMIシミュレーションの現状と並列シミュレーションへの展開について述べる。 |
| 題名 | On Parallel Degree of Well-Structured Workflow Nets |
| 著者 | 山口 真悟, ◎曲 南 (山口大学大学院理工学研究科) |
| Page | pp. 392 - 397 |
| Keyword | Petri net, workflow, WF-nets, parallel degree, PARAdeg |
| Abstract | Workflows can be modeled as a subclass of Petri nets, called workflow nets (WF-nets for short). In this paper, we discuss how to measure the parallelism of WF-nets. We first give the definition of parallel degree, PARAdeg, for WF-nets. We focus the discussion on a subclass of WF-nets, called well-structured WF-nets, because they are useful to model actual workflows. We show it is intractable to compute the value of PARAdeg for acyclic well-structured WF-nets. Then we propose a heuristic algorithm to compute the value. Finally, we show the effectiveness of our algorithm through an experiment. |
| 題名 | 並行計算モデルによる組込みシステムの仕様記述 |
| 著者 | ○河辺 義信, 伊藤 暢浩, 石井 直宏 (愛知工業大学 情報科学部) |
| Page | pp. 398 - 403 |
| Keyword | 形式手法, 組込みソフトウェア, 仕様記述, 検証, TOPPERS |
| Abstract | 近年，組込みシステムは，生活のあらゆる場面で使われている． 多くの組込みシステムは複数のプロセッサを持ち，OSもマルチタスク化がすすんでいる． そのため，ひとつの組込みシステム内で，数多くのソフトウェアが並行動作する状況が生まれている． これらのソフトウェアは，同期をとるために互いに通信する必要があるが，その通信の複雑さが増すにつれ，デバッグが困難になっている． そこで本稿では，組込みソフトウェアの検証に向けた，形式手法の適用を試みる． 並行計算モデルに基づく形式言語を導入することで，組込みソフトウェアの並行性は自然に扱われる． また，簡単な例に対する，システム記述と検証の例を示す． |
| 題名 | σ辺連結2部グラフの(σ + 1)辺連結化のための高速アルゴリズム |
| 著者 | ◎沖 忠親, 田岡 智志 (広島大学 大学院 工学研究科), 間島 利也 (広島国際大学 工学部), 渡邉 敏正 (広島大学 大学院 工学研究科) |
| Page | pp. 404 - 409 |
| Keyword | 2部グラフ, 辺連結度, アルゴリズム |
| Abstract | 2部グラフのλ辺連結化問題（以下，UW-Bipartite-λECA(*, MA)と略記）は以下のように定義される．:「単純無向2部グラフG=(V+, V-; E)が与えられたとき，辺付加後のグラフG'=(V+, V-; E∪E')がλ辺連結2部グラフであるような最小の付加辺集合E'を求めよ．」 本稿では，Gがk辺連結のときにUW-Bipartite-(k + 1)ECAに対する最適解を算出する高速アルゴリズムを提案し，k ∈ {1, 2}については線形時間で解けることを示す． |
| 題名 | Cayleyグラフの逐次診断可能次数の下界 |
| 著者 | ○山田 敏規 (埼玉大学 大学院理工学研究科 数理電子情報部門) |
| Page | pp. 410 - 414 |
| Keyword | Cayleyグラフ, 逐次診断可能次数, 下界, スターグラフ, Wrapped Butterfly |
| Abstract | 小文では，すでに知られているCCCの逐次診断可能次数の下界を求める手法を一般化して，任意のN点Cayleyグラフの逐次診断可能次数がOmega(N/D)であることを示す．ここで，DはCayleyグラフの直径である．また，本結果をN点スターグラフとWrapped Butterflyへ適用することによって，逐次診断可能次数がそれぞれOmega(N log log N/log N)とOmega(N/log N)であることを示す． |
| 題名 | Heuristic Extraction of a Maximum Induced Tree from a Graph |
| 著者 | ◎吉田 浩之, 高藤 大介, 田岡 智志, 渡邉 敏正 (広島大学大学院工学研究科) |
| Page | pp. 415 - 420 |
| Keyword | Extraction of induced subgraphs, Maximum induced trees, Vertex deletion of graphs, Heuristic algorithms, Evalution of algorithms |
| Abstract | The problem of extracting a maximum induced tree of a graph (MAXIT), which is NP-hard, asks for a vertex set of largest cardinality among those ones each of which induces a tree of a given graph. It is known that heuristic algorithms are useful tools for solving the constrained via minimization problems for layout design of printed wiring boards. The subjects of the paper are the following (1) and (2). (1) Several heuristic algorithms for MAXIT are proposed, and (2) their capability is compared by computing experiment. |
| 題名 | 通信経路に制約のある通信ネットワークの信頼性評価 |
| 著者 | ○林 正博 (NTTサービスインテグレーション研究所), 阿部 威郎 (東京医療保健大学医療情報学科) |
| Page | pp. 421 - 426 |
| Keyword | 信頼性, 通信ネットワーク, 通信経路, アルゴリズム |
| Abstract | 通信ネットワークの信頼性評価モデルとして、確率グラフが研究されているが、このモデルは、現実の通信ネットワークにおける諸条件（通信経路の制約、同時故障、通信容量）を反映してない。筆者等は、このような現実の諸条件を反映したモデルを既に提案しているが、そのモデルを対象とした信頼性評価アルゴリズムは、計算時間が膨大となることが問題となっていた。そこで、本稿では、計算アルゴリズムの改良を行い、より簡便で高速な方法を提案する。 |