随机数生成器的最小和最简单的种子是什么?

电器工程 随机数
2022-01-20 06:12:14

一个小型微控制器(8 位 Atmel)控制多个灯光,以呈现具有许多花哨的随机灯光序列的灯光秀。

一个合适的伪 RNG 可以很好地完成它的工作,但我正在为它寻找一个好的种子。种子是必要的,因为如果有人同时打开多个这样的设备,如果它们都产生相同的效果序列,直到它们由于各自时钟源的微小差异而慢慢分散开来,看起来就不好看。

在必须通过按下按钮或翻转开关启动设备的情况下,可以使用一种非常好的方法来播种我经常使用的伪 RNG。一旦µc 通电,就可以启动一个非常快的计时器,并且一旦第一次按下按钮,该计时器的值就会为 RNG 播种。

问题是,在这种情况下,没有按钮。该程序必须在设备通电后立即启动。

PCB 上的位置非常有限(可能只适合一些非常小的 SMD 部件),所以我正在寻找最小和最简单的解决方案。因此,我将排除像真正的 RNG 硬件、无线电接收器等花哨的解决方案。

我所拥有的只是 CPU 中的一个 16 位定时器计数器,以及一个可以访问 ADC 的未使用端口引脚。

我目前的解决方案是仅使用一个电阻器(尽可能不准确)为 ADC 引脚提供大约一半的电源电压,并使用第一个 AD 转换值为 RNG 播种。然而,现在大多数 10% 的电阻器的误差都远低于 1%(当我告诉供应商我们想要他们能找到的最差质量的 SMD 电阻器时,想象一下供应商的表情会很有趣),所以很有可能从同一个种子开始的多个单元。

一个更好的选择是进行多次转换并从这些测量的最低有效位中建立一个值。但是,我之前使用过这种 µc 类型的 ADC,我知道它非常准确。以尽可能快的速度运行 ADC 可能会有所帮助。

有人有更好的建议吗?种子不需要完全均匀分布,但分布越均匀越好。具有完全均匀分布的 16 位种子将是一个好得令人难以置信的梦想,但我认为 5 或 6 位的一半体面分布可能就足够了。

4个回答

在 A/D 引脚和地之间放置一个并联电阻和电容。使电阻器相当高,最好远高于 A/D 的输入信号阻抗要求。使 RC 时间常数大约为 10 µs。例如,100 kΩ 和 100 pF 听起来是一个很好的组合。

要获得具有一定随机性的值,请将引脚驱动一段时间,然后将其设置为高阻抗,并在几微秒后读取 A/D 读数。特别是如果你适当地滥用 A/D 采集时间,它所看到的电压将取决于 R 和 C 值、引脚泄漏电流、其他附近的噪声和温度。

抓取低位或低两位并根据需要重复以获得任意数量的随机位。

对于更随机的模式,偶尔执行此过程并将 A/D 结果的低位注入您已经使用的随机数生成器。

一些可能的选择:

  1. 为每个设备预编程一个唯一的串行地址。如果你有一个足够好的 RNG 算法,那么即使是序列地址的顺序列表也会产生截然不同的结果。

  2. 根据您的 MCU/设置,您可能有两个不同的时钟源可用于系统时钟和看门狗定时器/定时器计数器输入。如果其中一个/两个具有显着差异,您可以使用它来生成适当不同的种子。这是我编写的一个示例,它使用 Arduino 的内部看门狗定时器和外部 XTAL 系统时钟

  3. 使用 BJT 晶体管并构建高度依赖于 beta 的放大器。这可以从种子的 ADC 中读取。

  4. 电容器/电感器的公差通常比电阻器差得多。您可以使用这些构建某种滤波器电路(RC、RL、LC)并使用 ADC 测量输出。

未初始化的内存

您可以尝试使用微控制器中未初始化的内存。诀窍是找到具有最“平衡”触发器的位,并且实际上是随机的。该过程是读取所有内存,重置并重复几次以测量哪些位是真正随机的。然后您使用此映射读取足够的随机位来为您的 PRNG 或 LFSR 播种!

此方法应为您提供随机种子,即使使用相同的硬件,此 hack-a-day文章中提供了更多详细信息(和链接)

我喜欢这种方法,因为它不需要任何额外的电路或引脚;您的 AVR 已经有 ram,您只需要找到不稳定(随机)位。映射过程也可以自动化;您可以将相同的代码和程序应用于每个设备,并获得真正随机的结果!

我为具有随机功能的 MP3 播放器所做的只是在每次开机时使用不同的顺序种子。我从 1 开始并将其存储在 EEPROM 中,以便在下一次电源循环时使用 2 等。这是在 ATMEGA168 上。正如 helloworld922 所指出的,即使是一个简单的顺序种子也会生成完全不同的伪随机序列。

我使用了一种线性全等随机序列生成器,这给出了均匀分布。

int i;
seed = seed * 2053 + 13849;
i = (seed % max) + 1;  // max is the maximum value I want out of the function

当然,如果您希望多个单元具有不同的序列,即使它们可能具有相同数量的电源循环,那么您需要一些东西来随机启动。

这可以通过其他海报提出的任何方法来完成 - 我能想到的一种方法可以使用进入处理器的交流过零(如果有的话)(例如用于灯相位控制)?这可用于在上电后的第一个交叉点上对定时器进行采样,然后用作种子。

设备上是否有用于选择模式等的按钮?如果是这样,您可以在 MCU 编程后第一次按下按钮时对计数器进行采样,您可以最初生成一个随机种子并将其存储在 EEPROM 中。此后的每次上电都将使用存储的种子。