Arduino 硬件随机序列生成器（带 Java 接口）

• 下载 ArduinoHRNG.zip - 465 KB

md5sum: 3c70aab5248e9beddf2142a4b366fb2f

引言

该电路/应用程序的目标是生成 0 到 n 之间的整数值，其中

• n 是 [(2 的偶数次幂) -1]，例如 255、511、1023 等。
• 该序列（可能）只能通过单独枚举值来通信（最大算法熵）。没有模式、简写表达式或有效的压缩方法。
• 每个值发生的可能性都相等，但它们不（一定）以相等的频率发生。
• 创建该集合的过程本身不太可能重复，并且没有匹配的初始条件会导致重复序列（非确定性）。
• 这些值与先前的值不相关。

随着序列长度接近无穷大，其中一些要求将失效。其中一些是绝对无法测量的（并且，在随机序列中，如果不存在模式，它们应该是这样的）。我们还希望能够缩放集合中的值而不引入与我们的要求相冲突的问题。

该应用程序将在 Linux 或 Windows 上运行。尚未在其他平台上进行测试。

必备组件

• 请按照您平台上的 Arduino 设置说明进行操作（http://arduino.cc/en/Guide/HomePage）。
• 请务必理解模拟读取过程。最好的方法是实现http://arduino.cc/en/Tutorial/AnalogReadSerial 处的项目。
• 该电路需要入门套件中不包含的组件。您应该拥有包括本文档原理图中所示组件在内的组件集合。
• 您需要测试设备，至少包括万用表。
• 您需要一个无纹波的电源，可提供 +/- 12 VDC
• 您应该熟悉基本的电子知识和电子安全。

电路详情

《Arduino 入门套件》包含几个BC547 晶体管。BC547 的发射极-基极击穿电压约为 6V，反向偏置时可用作齐纳二极管。下面的原理图，其中上方的 BC546 配置为反向偏置的齐纳二极管，可生成白噪声信号。

该噪声是雪崩噪声、散粒噪声和热噪声的组合，但雪崩噪声可能是占主导地位的。以下示波图显示了信号，其中主要时间刻度为 2 µs。

必须对信号进行调理，然后我们才能有效地用 Arduino 串行输入对其进行采集。下面是一个执行此操作的电路。首先，来自噪声源的信号使用OP77 运算放大器分两级放大，以更好地利用 Arduino 的 ADC 输入范围。然后，通过将放大器的输出与分压器（标记为offset）产生的可调 -2.5 VDC 信号相加，将其中心设置在 2.50 VDC，然后输入到增益可调（标记为gain）的反相LM741 运算放大器。最后，信号连接到一个 5V 齐纳电压限幅器，以提供对 Arduino 模拟输入引脚的额外保护。

以下示波图显示了调理后的信号，同样以 2 µs/div 的时间轴。请注意，它已丢失了一些高频分量，这是使用简单、低成本电路设计进行放大造成的。对于此应用，这种损失并不重要。

在连接到 Arduino 之前，请验证调理后的信号在 0 到 5 伏之间。信号的波峰因数很高，典型的万用表无法可靠测量信号强度。LM741 运算放大器的直流输出应为 +2.5 VDC。齐纳电压限幅器将限制正信号的波动，但负偏移可能会超过 Arduino 模拟输入规格。示波器是验证电压合规性的最佳方法。在确信调理后的信号在 0 V 和 5 V 之间变化后，将电路和 Arduino 连接到公共地，并将调理后的信号源连接到 Arduino A0 模拟输入。

Arduino 草图

A0 串行输入引脚连接到一个模数转换器，它会将 0-5 V 的模拟输入转换为 10 位数字值（0 到 1023）。该值通过 USB 端口以字符串形式通信。波特率为 115200。循环读取该值并将其打印到 USB 端口，后跟一个换行符。

/*Analog Pin writer for transistor noise experiment */
void setup()
{
  Serial.begin(115200);
}
void loop()  {
  int v = analogRead(0);
  Serial.print(v);
  Serial.print("\n");
}

为了测试，您可以使用 Arduino 串行监视器来收集数据。请确保正确设置端口和波特率。

在使用 Linux 时，在从 USB 端口读取数字化信号之前，必须将操作系统配置为以所需的波特率读取输入。以下命令执行此操作：

Linux，仅当前启动
stty -F /dev/ttyACM0 115200

同样使用 Linux，您可以通过以下方式完全绕过串行监视器：
cat /dev/ttyACM0
您可以读取端口 30 秒，并将输出保存到名为 test 的文件中：
timeout 30s cat /dev/ttyACM0 > test

如果将数据输入到电子表格中，您可能会看到一些损坏的值或在序列早期出现 1023 以上的值，您应该删除这些值。如果绘制数据图，您应该会看到类似下图的内容。

信号特性

原始信号是高斯噪声，而不是随机序列。如果您将 0 到 1023 的每个值的出现次数制成表格，并绘制出现频率与值的关系图，您将看到信号的概率密度函数（PDF）。在下面的示例中，洋红色线表示使用样本的均值和标准差合成的缩放的理想高斯分布。

分布尾部的值应为零，峰值应在 ~512 处。如果不是，请调整增益和偏移量。

创建随机序列

如果原始信号的概率密度函数近似于高斯分布，那么通过从原始信号创建新信号，该信号可用于生成均匀分布：新值在给定索引处为 1 当相应原始值大于均值时，为零当它小于均值时，并且当它等于均值时不使用。这会产生一个可用于组合随机数的均匀分布。

请注意，此信号比原始信号短，因为已丢弃均值处的值。它也可能不太有用，因为它只有一位熵，但我们可以将相邻值按块组合起来计算具有更高熵的均匀分布信号。例如，假设我们有以下二进制序列：{0,0,0,0,1,1,1,1,1,0,0,1}。我们可以从中创建一个具有 4 位熵的序列：{0, 15, 9}。使用此策略处理单比特均匀分布以获得 8 位均匀分布，我们得到：

请注意，它不是均匀模糊（这是一个好迹象）。下面是概率密度函数，它看起来是均匀的，如红色水平拟合线所示。另请注意，当我们将相邻位组合时，我们将信号的长度减小了 8 倍。您的拟合线不一定会具有零斜率，但它应该在重复运行中从正数波动到负数。

在电路中，我们对白噪声信号进行了调理，使其与 Arduino 兼容。Arduino 将电路产生的调理信号转换为数字信号。我们检查了数字信号，确认它是高斯噪声。在满意之后，我们用它来创建一个均匀比特序列，最后创建一个均匀的 8 位序列。我们检查了 8 位序列及其概率密度函数，并推测它是均匀的，并且可能是随机的。

我们做了一个假设，这会降低从均匀序列中提取的随机数的质量。我们推测，看似高斯信号没有偏斜……均值以上的值的数量约等于均值以下的值的数量，并且 0 和 1 在我们的单比特均匀序列的任何给定点发生的可能性均等。给定电路可能会—可重现地—朝同一方向偏斜（加权抛硬币）。为了解决这个问题，必须调整电路以最小化偏斜。在我的电路中，我通过反复试验优化来调整运算放大器增益和电容器值。

Java 接口

我们需要从 Java 应用程序中读取 USB 端口的串行数据，并且我们倾向于使用平台无关的方法。此处使用了 JSSC 库。您可以按照https://code.google.com/p/java-simple-serial-connector/ 上的链接获取库和 javadoc。

硬件随机数应用程序，ArduinoHRNG

源代码有 12 个类

1. Main.java，应用程序入口点，它测试端口然后创建一个 Acquire 类的实例。
2. Acquire.java，一个类，在构造时，它收集数据，创建均匀分布，并运行一组随机数序列测试。提供了绘图和/或保存数据的选项。
3. AnalogPinReader.java，该类使用 jssc 从串行端口读取整数数组。
4. Signal.java，整数信号数组和统计量的容器，包括绘图方法。
5. Utils.java，杂项静态方法
6. Statistics.java，统计计算的静态方法（不包括卡方统计）
7. ChiSquare.java，卡方统计的静态方法
8. RegressionModel.java，用于绘图拟合模型的枚举
9. CpuMatrixOps.java，用于线性回归
10. FileOps.java
11. PlotForm.java，一个显示图形的类
12. Stopwatch.java，一个计时器

该应用程序是作为一个演示编写的，最好从 IDE 运行。（如果您不使用 IDE，您可以修改 Main() 方法，使其从控制台输入所需的参数。）要使用该应用程序，请根据需要修改 Main.java 类中的全局变量。在 Main 类中需要修改到参数是：

• portName：用于 Arduino 接口的串行端口的特定于操作系统的名称（例如，Linux =“/dev/ttyACM0”，或 Windows com3）
• isPlot：一开始设置为 true。
• isSave；一开始设置为 false
• rawSize：一个整数，用于计算要获取的原始信号的长度。收集的长度是 rawSize*1024。开始时，选择 32 的值，这应该允许在不到一分钟内完成测试。
• repeat：允许您将整个测试重复 n 次。从 1 开始。
• baudRate：一个允许在 Arduino 草图、操作系统设置和 jssc 中使用的整数波特率。在所有三个地方设置此值。在我的实验中，115200 的值效果很好。
• maxValue：您想要的随机数序列的上限，例如 255 将给出 0 到 255 之间的值集合。使用 255 或更大的值。从 255 开始，根据需要递增值，但要使其比 2 的幂小一，例如 255、511、1023 等。原始大小参数应足够高，以便为序列中的每个可能整数值提供至少 10 个数据点的预期值。例如，如果我收集 32*1024 个原始数据点，对于 8 位示例运行，我会得到以下序列长度（值因运行而异）：
  • 原始数据长度 = 40959（大于预期的 32768，因为将字符串转换为整数在应用程序中是不可预测的）
  • 有用比特数 = 40786（低于原始信号长度，因为丢弃了均值处的值）
  • 均匀数组长度 = 5098（floor(40786/8)，因为我们将 8 个单比特熵值组合起来以获得最大可能值为 255
  • 为每个唯一整数创建的点数（预期 bin 计数）的预期值为 = 5098/256 = ~ 20。
  • 规则是：如果您想在序列中获得更高的比特熵，您需要收集更多数据。

输出，图

如果 isPlot  = true，应用程序将绘制某些数量。下面是创建的图表的示例。

原始数据的概率密度函数（洋红 = 理想高斯估计）

提取的随机序列

随机序列的概率密度函数（红色 = 回归线）

输出，统计

我开始实验，收集并保存字节数组，然后使用 ENT 随机序列测试套件（http://www.fourmilab.ch/random/）测试结果。在 Java 中，我宁愿避免将 10 位无符号字节转换为 8 位有符号字节。在应用程序中，我收集整数数组，所以我创建了用于 int[] 类型的、执行类似于 ENT 套件的测试的方法。下面是一个针对最大随机值为 1023 的 rawSize = 256（256 个块，每个块 1024 个点）数据集的控制台输出。

正在检查串行连接... 
/dev/ttyACM0
好的

测试 # 1... 正在进行中

*****************************
试用    1
        原始数据统计
计数 =        262144
均值 =        508.73
标准差 =        89.68
最小值 =        107
最大值 =        937
高于均值的值数 =    130795
低于均值的值数 =    130045
高于/低于比率 =    1.006

均匀分布统计
目标值在 0 和 1023 之间

有用比特数 =    260840
数组长度 =        26084
均值 =            512.53
标准差 =    296.58
最小值 =            0
最大值 =            1023
均值处的值数:    29
高于均值的值数:    13125
低于均值的值数:    12930
高于/低于比率:        1.015

随机序列统计

熵，比特:    9.962

已创建 1024 个 bin，预期值为 ~25
卡方统计:    1040.7
随机超过的百分比:    33.5

通过 Sedgewick 的随机性测试

Knuth（串行）相关性:    -0.00463

使用数据计算 pi 的蒙特卡洛法:    3.12958
蒙特卡洛相对误差（%）:    0.382

使用 java.util.zip.Deflater
压缩/原始大小比率是:    1

------------完成-------------

统计解释

在测试开始之前，会进行一个检查，列出可用端口并尝试从用户指定的端口收集数据。列出端口后，如果端口不正确，它将抛出不友好的错误。

原始数据统计

• 计数应约等于 ( rawSize )(1024)。
• 均值应约等于 512（通过电路偏移量微调器调整）。
• 标准差可通过增益微调器进行调整。
• 最小值应大于 0（通过增益微调器调整）。
• 最大值应小于 1023（通过增益微调器调整）。
• 高于和低于均值的值数应大致相等。

均匀分布统计

• 均值应接近所需范围的中点。
• 最小值应为零，最大值应为您的目标最大值（maxValue）。
• 标准差应约等于 sqrt((n^2-1)/12)，其中 n = [最大值 - 最小值 +1]
• 均值以上的值和均值以下的值应大致相等。

随机序列统计

比特熵应接近 log₂(最大值)。

卡方计算将数据分为 bin，每个 bin 包含最小值和最大值之间每个值的出现次数。预期值是如果数据是完全均匀的，则给定值的出现次数。您希望预期值大于 10（一些来源引用了较低的要求）。计算出卡方统计量后，会计算一个百分比，该百分比表示真正随机序列超过卡方统计量的频率。以下是来自 ENT 网站（http://www.fourmilab.ch/random/）关于此百分比的指南：

如果百分比大于 99% 或小于 1%，则序列几乎肯定不是随机的。如果百分比在 99% 到 95% 之间或在 1% 到 5% 之间，则序列可疑。90% 到 95% 和 5% 到 10% 之间的百分比表示序列“几乎可疑”。

百分比标准应定期失效（约 5% 的时间）。

Sedgewick 随机性测试是另一种卡方实现。它包含在内以供参考。同样，它应该偶尔失效。

Knuth 串行相关性测量序列中的每个值对前一个值的依赖程度。该统计量范围从 -1 到 1。对于随机序列，0 是理想值。

蒙特卡洛值应接近 pi。随着序列长度的增加，该值会提高。

压缩比应接近一。小于一的值表示可以在不传输整个序列的情况下通信该序列。

如果您想查看失败测试的示例，请在断开 Arduino 串行引脚的情况下运行测试。考虑一个修改，它在其他随机整数序列（例如可以从http://www.random.org/integers/ 下载的序列）上运行统计测试。

多重运行数据

在 Main.java 类中，您可以将 repeat 值设置为大于 1 的数字。这样，您就可以评估一组序列。

以下是 20 次运行的统计数据，每次运行收集 512X1024 个值的原始信号，并生成介于 0 和 1023 之间的随机值序列。
序列数 = 20（每个约 65K 个整数长）

	平均	标准差	最小值	最大值
均值	512.82	1.40	510.38	515.36
标准差	295.85	0.50	294.61	296.88
最小值	0	0	0	0
最大值	1023	0	1023	1023
平衡比	1.0004	0.0054	0.9925	1.0125
比特熵	9.978	0.002	9.974	9.980
串行相关性	0.00074	0.00369	-0.00749	0.00549
蒙特卡洛 pi	3.13725	0.00478	3.12646	3.14431

真正随机序列超过卡方统计量的频率

	出现次数
大于 99% 或小于 1%	0
在 99% 和 95% 之间或在 1% 和 5% 之间	1
在 90% 和 95% 之间或 5% 和 10% 之间	2

项目下载

md5sum: 3c70aab5248e9beddf2142a4b366fb2f

用户会发现，他们可以通过在 IDE 中调试应用程序来轻松测试和优化 RNG。我在 Arch Linux 和 Windows 中的 Eclipse（Helios 和 Luna）中测试了该应用程序。请使用 7 版本 JDK。

可运行的 jar 文件对实验者来说作用不大，但可以在将 Arduino USB 分配给 /dev/ttyACM0 的 Linux 机器上运行，方法是切换到可运行目录并执行：
java -jar ArduinoHRNG.jar

对于 Eclipse 用户，将整个解压的 ArduinoHRNG 文件夹复制到您喜欢的项目文件夹，并创建一个完全名为：ArduinoHRNG 的新 Java 项目。

本应用程序使用 JSSC 库（https://code.google.com/p/java-simple-serial-connector/）。要将库添加到 Eclipse 项目中，请在包资源管理器中右键单击项目，然后选择属性。选择 Java Build Path 导航窗格，转到 Libraries 选项卡，然后选择 Add External JARs。然后，导航到 JSSC 文件夹中的 jssc.jar 文件（在我的例子中是 jssc-2.8.0.jar）。选择 OK 并关闭属性。根据您的配置，该库可能已链接到您的项目中。我不使用任何其他 IDE 进行 Java 开发，因此无法建议如果您不使用 Eclipse，如何链接到该库。

我使用 Arch Linux，并通过在终端中运行 stty -F /dev/ttyACM0 115200 来开始我的会话。

遵循正确的电子安全规则。保护您的 Arduino 免受超出规格的输入。进行实验，玩得开心。寻找其他自然随机噪声源（我见过一个使用盖革计数器的）。

参考文献

• 基于雪崩噪声的随机序列生成器，http://holdenc.altervista.org/avalanche/
• 熵和随机数，https://calomel.org/entropy_random_number_generators.html
• 测试随机数生成器 http://www.cse.wustl.edu/~jain/cse567-08/k_27trg.htm
• ENT 随机序列测试，http://www.fourmilab.ch/random/
• 如何在 Java 中计算 PValue 来自 ChiSquare， http://www.vvlasov.com/2013/06/how-to-calculate-pvalue-from-chisquare.html
• 计算机程序艺术，第二卷：半数值算法（第三版），Knuth，Addison-Wesley Professional；第 3 版（1997 年 11 月 14 日），第 3.3.2 章，http://www.amazon.com/Art-Computer-Programming-Volume-Seminumerical/dp/0201896842
• 高斯噪声源的特性，Stephens，等人。Robert Muro，NoiseCom, Inc.，2008
• 白噪声发生器，电路与分析，Sanchez，德克萨斯大学圣安东尼奥分校，2008。
• www.phy.ilstu.edu/slh/chi-square.pdf
• 使用简单的晶体管结噪声源生成随机数，（第 1 版修订版 2. 2004 年 6 月 22 日），David Eather，2003
• 为什么不直接使用浮动引脚？Arduino 作为硬件随机数生成器，Kristenson，等人，2012。 http://arxiv.org/abs/1212.3777
• www.physics.unlv.edu/~bill/PHYS483/op-amps.pdf

对于雄心勃勃的人来说，一生都可以用来评估随机数序列。https://code.google.com/p/randomnumbertestsuite-nist/source/checkout

 

历史

在此处保持您所做的任何更改或改进的实时更新。