Wolframのルール90/150に基づく履歴参照型アナログセルオートマトンとそのハードウェア化
河端 和義
2008 年度 卒 ／修士（工学）
修士論文の概要
標準セルオートマトンでは、時刻tにおけるセル状態は時刻t-1の近傍セル状態から求められる。近年、この考え方が見直され、過去のセル状態（〜t）の履歴を現セル状態に反映させるような、履歴参照型セルオートマトンが提案されている。履歴参照型セルオートマトンでは、時刻tにおけるセル状態は、例えば時刻t-1, t-2, t-3, …における近傍セルの状態により決められる。過去の履歴を参照することで、統計的に良い性質を持った乱数発生や、囚人のジレンマと呼ばれる最適化問題の計算，さらに複数のフラクタル構造の出現など、標準セルオートマトンでは発生しないようなパターン生成や情報処理が可能になる。本研究では、履歴参照型セルオートマトンの乱数発生への応用を念頭におき、モデルのアナログ化，CMOS回路化を行った。
本研究ではハードウェア実装が容易な1次元のデジタル型セルオートマトン（ルール90と150）に着目する。ルール90と150の違いは状態更新のための遷移関数の違いである。本研究では、状態更新方程式とルールを決める関数のアナログ化を行った。まず、リークのある積分モデルを考える。このモデルを時間で離散化したものが、本研究の対象となるアナログセルオートマトンである。積分モデルは過去の変数状態を積分する（＝過去の状態の履歴を持つ）ものであり、またリークは過去の状態の忘却を意味する。従って、リークあり積分モデルの差分ダイナミクスは、必然的に履歴参照型となる。
過去の履歴の保持の度合いを表すために、パラメータαを新たに導入した。α = 1の場合、提案モデルは標準のデジタルモデルと等しくなり、履歴機能を持たない。一方、α < 1の場合は、過去の変数の状態が次状態に反映される（過去のセル状態はリークあり積分モデルにアナログ値として保持される）。したがって、αをパラメータとすることで、履歴機能の効果を調べた。
上記のアナログ拡張により、セルの更新関数も連続アナログ関数に拡張する必要がある。本研究では、二種類の連続関数を導入する。重要なことは、デジタルモデルの遷移関数をなるべく自然に連続化することである。本研究では、一つのパラメータでステップ関数から連続関数へ変更可能なシグモイド関数を用いて遷移関数をアナログ化した。
次いで、提案したアナログ履歴参照セルオートマトンの乱数発生への応用可能性を調べた。100セルを用いて、モデルの数値計算を行った。シミュレーション結果より、1) 提案モデルが履歴を参照しない場合（α = 1）、1次元セルオートマトンによく見られる自己相似パターンが現れ、2) 履歴を参照する場合（α < 1）は、自己相似パターンが現れつつも、密な空間パターンが発生する，ということがわかった。つまり、履歴を参照しない場合は、空間的に疎なパターンが発生することがあるため、任意のセル出力を乱数として考えた場合には、時系列的に疎なランダムパターンが得られる。一方、履歴を参照する場合は、時系列的に密なランダムパターンが得られることになるため、乱数として利用可能である。
生成された乱数列の統計的性質を評価するため、本研究では二つの評価変数を考案した。履歴なし（α = 1）の場合と比較して、履歴あり（α = 0.9）の場合は評価変数平面が満遍なく点で埋め尽くされることから、履歴ありのほうが統計的に良質な乱数を生成することがわかった。
最後に、乱数発生への応用を目指して、提案したアナログ履歴参照セルオートマトンのCMOS回路化を行った。SPICEシミュレーションにより、数値シミュレーションと同様の性質（履歴のありなしで、乱数の疎密が決まる）を確認した。