公開日：2025/05/24

34th Season

#34-9　真性乱数と擬似乱数の協調

　Cmod A7ボード(FPGA)を使って、オリジナル16ビットCPUコアMoscoviumの開発を進めています。
　こちらの記事「#34-7　真性乱数発生器(SSCG方式)」で設計した真性乱数発生器TRNG32ユニットを強化してみたいと思います。名付けて「疑似真性乱数発生器」……、って？強化してるんだか、弱体化してるんだか、ムムム……な感じですね、ネーミングは……。最後の結論まで読み進めてもらったら、真意は伝わるはずです。

擬似乱数の問題点

　まず、擬似乱数のお話から始めたいと思います。

M系列(LFSR；Linear Feedback Shift Register)

　M系列はLFSRによって発生することができる数列です。LFSRが発生する数値データだけを眺めると乱数を発生しているように見えるのですが、論理シミュレーションを実行して時系列で見ると、規則的な波形が観測されます(下図)。



　LFSRを乱数として使う場合、使い方によっては、規則的なデータが出力される恐れがあります。

線形合同法(LCG；Linear Congruential Generators)

　線形合同法は、昔から使われてきた擬似乱数を発生する方式で、今でもC言語の標準関数などで採用されています。
　LFSRの時と同様に、シミュレーションして時系列で見てみましょう(下図)。



　実は線形合同法の場合、下位桁が規則的に変化することが知られています。上図でも、はっきりと見えています。

• ビット0(最下位桁)：
• 0と1が交互に出現しています。
• 乱数としてみると、必ず、偶数と奇数が交互に出現します。
• 例）コイントス
• コイントスの結果として、
• 最下位ビットが0の場合を裏面、
• 1の場合を表面等に割り当ててしまうと、
• 必ず裏面と表面が交互に発生します。
• こんなことでは乱数でも何でもありません。
• ビット1：
• 0，0，1，1，……と、0と1が2回毎に入れ替わっています。
• ビット2：
• 同様に、0と1が4回毎に入れ替わっています。
• ビット3：
• 実は上図だと判りませんが、もう少し広い範囲で見ると、規則的波形の繰り返しになっています。

　線形合同法で生成した擬似乱数を使う場合、下位桁は使わずに上位桁を使う事が求められます。

線形合同法の正しい使い方

　線形合同法の下位桁は規則的なので、以下の使い方は誤った例です。

　　例）TFTディスプレイなどへ、ランダムドットを描画

• TFTディスプレイのサイズ：　128×160[ドット]
• 線形合同法による32ビット疑似乱数を返す関数をLCG()関数と仮定する。
• x＝LCG ()%128
• y＝LCG ()%160
• draw_dot (x，y)
• 必要な数値範囲(上例では128や160)の剰余(%)を取ることで、
• 発生した擬似乱数LCG()関数の下位桁を取り出して使っている。
• 線形合同法の出力は下位桁が規則的なので、
• 場合によってはランダムな座標にならず、
• 規則的な位置にドットが描画される。

　正しい使い方は、例えば以下の様になります。

• x＝(LCG ()>>16)%128
• y＝(LCG ()>>16)%160
• draw_dot (x，y)

　右シフト演算(>>)によって規則的な下位桁を捨て、上位桁だけを使用しました。これは一例ですが、何らかの方法で、上位桁の情報から優先的に使う事が正しい使用方法です。

組み合わせる

　LFSRも線形合同法も、単体では短所が目立ってしまいます。そこで、

• 原始多項式(やパラメータ)が異なる2つのLFSR(や線形合同法)同士を組み合わせたり、
• 各々異なる特性を持ったLFSRと線形合同法とを組み合わせることで、

各々の短所を互いにカバー🩹し合うことができるのではないか？と言う考えが浮かびます。
　本ページでは、後者を選択したいと思います。同じ性格を持ったLFSR(や線形合同法)同士を組み合わせるより、性格の異なる者同士を組み合わせた方が、より良い結果が得られるだろうという推測に基づいた考えです。

　組み合わせの方法としては、加算や減算なども考えられますが、より回路規模が小さく伝搬遅延時間も短い、EOR(排他的論理和)を採用したいと思います。

　LFSRと線形合同法をEORで組み合わせ、シミュレーションした波形図が以下図となります。



　LFSRの短所だった時系列の規則的変化や、線形合同法の短所だった下位桁の規則的変化は、見られなくなりました。

周期

　前節で示した様にLFSRと線形合同法を組み合わせたところで、各々が規則的に変化する擬似乱数であることに変わりありません。組み合わせた乱数列もまた、擬似乱数だという事です。
　ただ、

• LFSRの周期：　2³²−1＝3×5×17×257×65537(素因数分解)
• 線形合同法の周期：　2³²

と言う事で、組み合わせた擬似乱数の周期は各周期の最小公倍数(素因数の和集合)ですので、組み合わせた新しい乱数列の周期は(2³²−1)×(2³²)≒2⁶⁴という長周期です。

　例えば擬似乱数を数値シミュレーションなどに使用する場合、32ビット線形合同法では周期2³²毎に、まったく同じ乱数列が発生し続けてしまいます。もし、乱数を2³²個以上使う場合、ビット幅を48ビットや64ビット幅に拡張しないと、乱数性が低下するのです。
　擬似乱数の周期が長い事もまた、特長と言って良いと思われます。

TRNG32ユニットの強化

　TRNG32ユニットは、物理的雑音を利用した真の乱数を生成するためのハードウェアとして設計しました。
　TRNG32ユニットでは、物理的雑音が数クロックサイクル毎に1ビットの割合で発生します。発生した雑音はLFSRを使って織り込み、複数ビット(32ビット)の真性乱数としてtrngrandレジスタから読み出すことができます。

　前節では規則的に変化する擬似乱数である、LFSRと線形合同法を組み合わせた事により、互いの短所を補い合うことができました。ならば、LFSRを使った真性乱数と、線形合同法を組み合わせることも理にかなっているのではないか？この考えに基づいて拡張したTRNG32ユニットのブロック図が以下図です。



※薄黄色の箱はCPUからアクセス可能なI/Oレジスタ、薄緑色の箱はハードマクロ、青破線はRTLとハードマクロの境界線です。

• ここで、trngtlcgレジスタ＝trngrandレジスタ＾LCG[i]である。
• 演算子(＾)は、排他的論理和(EOR；Exclusive OR)。
• trngrandレジスタは、生成した真性乱数を読み出し可能なレジスタ。
• LCG[i]は、線形合同法による擬似乱数。
• LCG[i]＝LCG[i−1]×A＋B
• 定数A，Bは、ユーザが自由に設定できる様、TRNG32ユニットの外部にRTLとして記述。
• 参考までに、C言語(GCC)標準関数の実装では、A＝1,103,515,245、B＝12,345。
• trngrandレジスタ値は、システムクロック(@24MHz)サイクル毎に更新されている。
• 一方、擬似乱数LCG[i]は、trngtlcgレジスタを読み出した時だけ更新される。

　LFSRと線形合同法を組み合わせる事によって、LFSRの短所であった時系列の規則的変化が観測されなくなる事は検証済みです。
　一方、真性乱数と線形合同法を組み合わせても、雑音を織り込み続けて真の乱数を発生する機構は阻害されていません。つまり、真性乱数は真性乱数のまま、短所だけが修正されたのです。
　追加したtrngtlcgレジスタ(上図参照)が、真性乱数(LFSR)と擬似乱数(線形合同法)とを組み合わせた、いわば「疑似真性乱数」レジスタです。こちらのI/Oレジスタ仕様を更新しておきましたのでご確認ください。

疑似真性乱数レジスタの使い方

　TRNG32ユニット設計時の実験にて、32ビットの真性乱数を生成するのに必要な時間は約160サイクルだと判っています。160サイクルで32ビットなので、1ビットの雑音が発生する平均時間は、約160サイクル÷32ビット＝約5[サイクル/ビット]です。

　　使い方：

• 毎回32ビットの真性乱数が必要なら、
• 約160サイクル待ってから、
• trngtlcgレジスタを読み出せば良い
• 最低1ビットの雑音が発生すれば充足するなら、
• 約5サイクル待ってから、
• trngtlcgレジスタを読み出せば良い
• ※必要な雑音数が得られるまで、5サイクル×雑音数の時間を待てば良い。
• 擬似乱数と同じかもしれないが、雑音が入っていたらなお良いと言う程度なら、
• 何時でもtrngtlcgレジスタを読み出して良い
• ※何れの待ち時間も、前回使用時からの経過時間で良い。

　trndtlcgレジスタの読み出し間隔を調整するだけで、真性乱数としても、中間の疑似真性乱数としても使用可能です。これが当方が到達した最終結論であり、最終提案です。いかがでしょうか？

デザイン

　Cmod A7ボード等、XilinxのFPGAに書き込むのに必要な、Moscoviumマイコンの設計データ(Vivadoのプロジェクトファイル一式を含む)はGitHubで提供しています。以下バナーよりアクセスしてください。



　TRNG32ユニットの設計データを更新しておきました。TRNG32ユニットを搭載したマイコンNHOC113DB9808等でご確認ください。コンパイル(論理合成・配置配線)結果も更新してあります。
　デザイン(回路)をCmod A7ボードに書き込む手順については、こちらをご確認ください。


　真性乱数が必要なケースでも、普段使いの擬似真性乱数が必要なケースでも、使用可能なユニットに改定することができました。ただし、再現性が必要な場合には従前の線形合同法などを使う事を推奨します。