Random-Number-Generator

是否可以建構一個輸出數字具有一定漢明權重分佈的 PRNG?

  • May 20, 2020

我需要一個非均勻隨機數生成器,其中每個 n 位輸出都有一個具有一定二項分佈的漢明權重。

例如,我想要一個非均勻 PRNG,它生成具有漢明權重的 32 位輸出,其二項式分佈為 n=32,p=0.1。例如,輸出 0xFF 的機率應該明顯低於 0x200,而 0x200 的機率又應該與 0x1 相同。

也許我可以修改像 xorshift 或 LFSR 這樣的 PRNG 的輸出來適應這個?我考慮過拒絕對輸出進行採樣,但統一 PRNG 的漢明權重分佈不一定包含具有可變參數 p 的給定二項式分佈,尤其是當 p << 0.5 時。

我不關心輸出的加密質量。但是,我正在開發具有 2 KB SRAM 的 8 位微控制器,因此記憶體和速度都是我最關心的問題。在最天真的情況下,我會生成一個隨機數數組,並在給定門檻值機率的情況下將每個元素轉換為 0 和 1,最後將生成的 0 和 1 數組轉換為整數。但我真的非常想避免這種 n 元素數組的記憶體成本。

顯而易見的方法是生成 N 個字,並使用邏輯運算將它們組合成一個字,這樣輸出字的每個位都是 1,機率約為 0.1(並且各個位不相關)。

在最簡單的情況下,您可以生成 3 個單詞,然後將它們組合成一個單詞。在 C 中,這將是:

    r1 = rand();
    r2 = rand();
    r3 = rand();
    return r1 & r2 & r3;

這使每個位集的機率為 0.125,接近 0.1

如果這還不夠接近,您可以通過使用更多位來獲得更接近的近似值;例如,r1 & r2 & r3 & ~(r4 & r5)以機率設置位的結果 $ 3/32 = 0.09375 $

使用這種技術,您可以使用 $ n $ 隨機詞以機率生成位集 $ k 2^{-n} $ 對於某個整數 $ k $ ; 這可以任意接近 0.1。

這顯然使用最少的記憶體;計算時間並不算太糟糕(假設您的 rand 實現很便宜),除非您堅持對目標機率有一個非常好的近似值。

而且,雖然我說的是“單詞”,但您的實現將使用它認為最方便的任何大小;對於 8 位 CPU,每個字可能是 8 位(您只需執行 4 次即可生成所需的 32 位)。

引用自:https://crypto.stackexchange.com/questions/80837