Walsh transform (WT)  and Fourier transform (FT) generating normal/Gaussian distribution sequences

• Walsh変換、フーリエ変換を用いて正規分布疑似乱数を生成出来ることが分かったので、その手法をご紹介します．（偶然の発見です）　一様分布乱数を正規分布乱数へ簡単に変換出来ます．
• 厳密な解析・特性評価等はまだおこなっていません．
• 特許出願等はおこなっていませんので、どなたでもご自由にご利用いただけます．　学会発表の予定もありません．　学生さんの卒論・修論のネタなどにもご利用ください．
  
  
  • PDF資料 『Walsh変換、フーリエ変換を用いた正規分布疑似乱数の生成手法』　make_gaussian.pdf

• 長い名前を繰り返して書くのは面倒なので、以下 Walsh変換を用いた手法をWT法（Walsh Transform Method, WTM）、フーリエ変換を用いた手法をFT法（Fourier Transform Method, FTM）と略して表記することにします．　両者を一つにまとめて呼ぶなら直交変換法（Orthogonal Transform Method, OTM）とでもいうところでしょうか．
• このwebページの最初の作成・公開日（2025.3.26）がWT法・FT法・直交変換法の発表日となります．

• Nヶの平均 0 の一様分布乱数列をWalsh変換すると、Nヶの正規分布疑似乱数列が得られます．　高速Walsh変換を用いるためにデータ長Nは2の冪（N=2^M）とします．
  
  
  
  
  
  

• Nヶの平均 0 の一様分布乱数列２セットから複素数列を生成してフーリエ変換します．　変換結果の実部と虚部をそれぞれ取り出すと、Nヶの正規分布疑似乱数列が２セット得られます．　高速フーリエ変換を用いるためにデータ長Nは2の冪（N=2^M）とします．
  
  
  
  
  
  

• WT法・FT法で一様分布乱数列を正規分布に変換する基本原理は中心極限定理（CLT, Central Limit Theorem）を用いた手法と同様です．　違いは単純な加算ではなく、重み付け係数付き加算をしていることです．
  
  
  
  
  
  
• Nヶの一様分布乱数の線形結合によりNヶの正規分布乱数 g[n] を作り出しているので、出力 g[n] 間には相関が生じているのではないか？（乱数としての特性が劣化しているのではないか？）という疑義が生じますが、詳細は未確認です．　データ長Nが十分に大きければ実用上の問題が生じるほどではない～と期待したいところですが. . . . .
• 擬似乱数の検定方法として離散フーリエ変換検定というのがあるそうですが、それとWT法・FT法の技術的関連性はよく分かりません．（2025/3/28追記）
• 一様分布乱数の代わりに、-1/1の２値の擬似乱数またはオフセットを除去した２値の擬似乱数列（平均0）を用いても正規分布乱数（シミュレーション結果）を生成できます．（2025/3/29追記）
  
  
• 見方を変えると直交変換法（WT法、FT法）は以下のような問題であると考えられます．（2025.3.31追記）
  問題の記述は非常に単純ですが、厳密な数学的証明も簡単に出来るでしょうか？
  
  
  1. NヶのN次元直交ベクトル c_n があるとき
     
     c_n={ c_n0, c_n1, c_n2, ... , c_n(N-1) }　（n=0, 1, 2, ... , N-1）
     
     c_n*c_k=0　（n≠k）
     
     
  2. 平均0の乱数u_nを要素に持つN次元ベクトル u と c_n との内積を考える
     
     u={ u₀, u₁, u₂, ... , u_N-1 }
     
     u₀+u₁+u₂+ ... +u_N-1=0
     
     
  3. Nケの内積 g_n はどのような特性を持つだろうか？（特に相関特性は？）
     
     g_n=u *c_n　（n=0, 1, 2, ... , N-1）
     
     
  4. シミュレーションから g_n は正規分布乱数となることが確認されていて、これは中心極限定理からも納得出来る結果ではあるが、数学的に厳密な証明や直感的に分かりやすい証明は出来るだろうか？
     
     

• WT法のサンプル・プログラム（データ長N=2²⁰=1048576）　c_wt_gaussian.c
• c_wt_gaussian.c の出力ファイル wt_out.txt を読み込んでグラフ表示するScilabのプログラム　c_wt_graph.sce
  

• FT法のサンプル・プログラム（データ長N=2²⁰=1048576）　c_ft_gauss.c
• c_ft_gauss.c と組み合わせて用いるFFTルーチン　fft.inc
• c_ft_gauss.c の出力ファイル ft_out.txt を読み込んでグラフ表示するScilabのプログラム　c_ft_graph.sce

• 動作確認は Scilab Ver.6 でおこなっています．
• グラフはいずれも一様分布乱数のseedを変えて４回実行したシミュレーション結果を重ね書きしたものです．
• データ長はすべてN=2²⁰=1048576です．

• WT法のサンプル・プログラム　walsh_transform_method.sce
  インタープリタのScialbでWalsh変換を実行しているので非常に遅いです

上のグラフの形がかなり歪（左右非対称）に見えるので、一様分布乱数のseedを変えてもう一度プロットしてみました（2025.3.28追加）
（SEED='f0a50fa5', 'a5a53c3c', '0000ffff', 'ffff0000'）

一様乱数の代わりに-1/1の２値の擬似乱数を用いても正規分布乱数を生成できます．（2025/3/29追記）
左右のグラフは使用した２値の擬似乱数のseedが異なります．（Scilabプログラム pn_walsh_transform_method.sce）

• FT法のサンプル・プログラム　fourier_transform_method.sce

• Box-Muller法のサンプル・プログラム　boxmuller.sce

• 中心極限定理を用いた正規分布乱数生成手法のサンプル・プログラム　central_limit.sce

.

• 今まで誰も気が付かなかったのが不思議なほど単純なWT法・FT法・直交変換法を発見するにいたった経緯は次のとおりです．
  • 離散時間信号処理（デジタル信号処理）の分野のある特別な試験信号を生成する手法として、周波数領域で信号の振幅周波数特性・位相特性を定義して、その逆フーリエ変換により時間信号を得る～というものがあります．
  • ならば同様に周波数領域でランダムな位相特性を定義して、それを逆フーリエ変換すれば特性の良いランダム・ノイズ／擬似乱数が得られるのではないか？と考えて試してみました．　試行錯誤を繰り返しているうちに、適当な擬似乱数をフーリエ変換すれば正規分布特性が得られることに気づき、さらにフーリエ変換の代わりにWalsh変換を使っても良いではないかということになり、最終的に中心極限定理に基づく正規分布乱数生成手法と同じことをやっているのだと理解出来ました．
• このような形で一様分布乱数、正規分布とWalsh変換・フーリエ変換が一つに結びつくとは興味深いことです．（ガウス関数のフーリエ変換がガウス関数になるという既知の性質はあるそうですが）

• c_wt_gaussian.c, walsh_transform_method.sce で用いているWalsh変換関数は下記の本のFORTRANのソースを移植したものです．（波数順序の高速Walsh変換になっています）　単純にC、Scilabに書き換えただけで、最適化のための修正は加えていません．　そのためC, Scilabのプログラムとしては良いものではありません．
  

FFTの使い方（電子科学シリーズ91）、安居院猛、中嶋正之、産報出版、1981（ISBNコードが日本で使われるようになる以前の本です）

FORTRANの算術型GOTO文／計算型GOTO文を目にしたのは何十年ぶりでしょうか. . . .

• 高速フーリエ変換はFFTWを使うのが定番です．　ScilabもFFTWを利用しています．
  

| ← back | ↑top |

| home |