random - 为什么 16 位 LFSR 能通过所有 Diehard 测试？

Question

我在硬件中实现了 LFSR。它基于维基百科页面中的 LFSR。它具有相同的输出。

它通过了顽固分子的所有测试，但是，如果我绘制这些对，我会在 2D 中得到这不是很随机的线

LFSR 的 2D 图

那么，我怎样才能有一个强大的统计测试来证明这个 PRNG 并不理想呢？

解决了：

我必须使用命令

dieharder -a -f exemple_LSRF_BS_1_DH.txt -g 202

并在输出文件中添加一个标题，我有我的号码。

Answer 1

从你的情节来看，我猜你的随机比特流在每个周期后发出整个寄存器，而不是每个周期只发出一个位。这意味着当被视为 16 位字时，x_(n+1)是X_n / 2或X_n / 2 + 32768。这表现为两条梯度为 0.5（或 2.0，取决于顺序和/或移位方向）的对角线。

LFSR 的正常使用将在每个周期发射一个比特，或者每个周期发射所有n比特n。这确实会产生一些负面属性，但它们并不像您所展示的那样明显。

至于为什么你的测试失败得更加顽固；我认为你的测试设置一定有缺陷。我修改了Wikipedia中的代码，以便在 stdout 的每个周期中发出 16 位状态，并将其通过管道传输到dieharder -a -g200.，但它在前五个测试中立即失败。这就是人们所期望的；甚至hexdump -C显示出明显的可见图案。

修改代码以每 16 个周期发出 16 位状态，hexdump -C看起来更加随机，但顽固分子仍然失败。

也许您没有将生成器源指定为更顽固，因此它使用了默认的内部生成器。您可以在输出的第五行确认这一点：

   rng_name    |rands/second|   Seed   |
        mt19937|  1.42e+08  |1473327481|

即便如此，如果您想对您的生成器进行更彻底的测试，请查看TestU01。