2025-11-15T08:07:11.841523

A Pseudo-random Number Generator for Multi-Sequence Generation with Programmable Statistics

Wu, Salim, Elmitwalli et al.
Pseudo-random number generators (PRNGs) are essential in a wide range of applications, from cryptography to statistical simulations and optimization algorithms. While uniform randomness is crucial for security-critical areas like cryptography, many domains, such as simulated annealing and CMOS-based Ising Machines, benefit from controlled or non-uniform randomness to enhance solution exploration and optimize performance. This paper presents a hardware PRNG that can simultaneously generate multiple uncorrelated sequences with programmable statistics tailored to specific application needs. Designed in 65nm process, the PRNG occupies an area of approximately 0.0013mm^2 and has an energy consumption of 0.57pJ/bit. Simulations confirm the PRNG's effectiveness in modulating the statistical distribution while demonstrating high-quality randomness properties.
academic

A Pseudo-random Number Generator for Multi-Sequence Generation with Programmable Statistics

基本信息

  • 论文ID: 2501.00193
  • 标题: A Pseudo-random Number Generator for Multi-Sequence Generation with Programmable Statistics
  • 作者: Jianan Wu, Ahmet Yusuf Salim, Eslam Elmitwalli, Selçuk Köse, Zeljko Ignjatovic (University of Rochester)
  • 分类: cs.CR cs.IT math.IT
  • 工艺节点: 65nm CMOS工艺
  • 论文链接: https://arxiv.org/abs/2501.00193

摘要

伪随机数生成器(PRNGs)在从密码学到统计仿真和优化算法的广泛应用中至关重要。虽然均匀随机性对于密码学等安全关键领域至关重要，但许多领域（如模拟退火和基于CMOS的伊辛机）受益于受控或非均匀随机性来增强解决方案探索和优化性能。本文提出了一种硬件PRNG，能够同时生成多个不相关的序列，具有针对特定应用需求定制的可编程统计特性。采用65nm工艺设计，PRNG占用面积约0.0013mm²，能耗为0.57pJ/bit。仿真确认了PRNG在调制统计分布方面的有效性，同时展现了高质量的随机性特性。

研究背景与动机

问题定义

传统的PRNG主要关注生成均匀分布的随机序列，但在许多实际应用中需要具有特定统计特性的非均匀随机序列：

  1. 应用需求多样化: 模拟退火、CMOS基伊辛机等应用需要可控的非均匀随机性来优化性能
  2. 多序列需求: 许多应用需要同时生成多个不相关的随机序列
  3. 硬件实现挑战: 现有PRNG难以在硬件层面实现统计特性的灵活调控

研究重要性

  • 性能优化: 受控随机性可以增强解决方案空间探索，提高算法性能
  • 应用适配: 不同应用对随机性的统计要求不同，需要可编程的解决方案
  • 硬件效率: 硬件实现的PRNG在功耗和面积方面具有优势

现有方法局限性

  1. 统计分布固定: 传统PRNG主要生成均匀分布，缺乏灵活性
  2. 多序列开销: 生成多个序列需要多套独立硬件，增加成本
  3. 实时调控困难: 现有方案难以实现运行时统计特性调整

核心贡献

  1. 提出了可编程统计特性的硬件PRNG架构，能够实时调控输出序列的统计分布
  2. 设计了多序列生成方案，通过共享LFSR和阈值控制器实现高效的多序列输出
  3. 实现了紧凑的硬件设计，在65nm工艺下面积仅0.0013mm²，功耗0.57pJ/bit
  4. 提供了动态阈值控制机制，支持时变统计特性，适用于模拟退火等应用
  5. 验证了序列质量，通过自相关和互相关分析确认了良好的随机性

方法详解

任务定义

设计一个硬件PRNG系统，能够：

  • 输入: 时钟信号、阈值控制参数
  • 输出: 多个具有可编程统计特性的1比特伪随机序列
  • 约束: 低功耗、小面积、高质量随机性、序列间低相关性

模型架构

整体架构

系统由三个核心模块组成：

  1. 线性反馈移位寄存器(LFSR)
    • 32位LFSR确保足够长的周期(2³²-1)
    • 特征多项式定义反馈结构：P(x)=xn+an−1xn−1+...+a1x+1P(x) = x^n + a_{n-1}x^{n-1} + ... + a_1x + 1
    • 通过选择不同的抽头组合生成多个m位均匀分布序列
  2. 阈值控制器
    • 输出m位阈值信号，控制最终序列的统计特性
    • 支持静态和动态阈值调整
    • 动态控制器基于计数器实现时变阈值
  3. 数字比较器
    • m位比较器将LFSR输出与阈值进行比较
    • 输出概率理论表达式：P(1)=2m−1−Threshold2mP(1) = \frac{2^m - 1 - Threshold}{2^m}

多序列生成机制

  • 通过选择不同间隔的LFSR抽头确保序列不相关
  • 每增加一个序列只需添加一个比较器和对应的XOR门
  • 共享LFSR和阈值控制器提高硬件效率
  • 可生成的不相关m位序列数量：C(n−1,k−1)/mC(n-1, k-1)/m，其中k为每个XOR操作的抽头数

技术创新点

1. 可编程统计控制

  • 创新点: 通过阈值调制实现统计分布的精确控制
  • 实现原理: 均匀分布的m位序列与可调阈值比较，输出概率可控
  • 优势: 实时调整，无需重新设计硬件

2. 动态阈值控制

动态阈值控制器实现：
- 计数器提供递增阈值
- 逻辑电路控制计数器启停
- 支持模拟退火等需要时变随机性的应用

3. 高效多序列架构

  • 资源共享: 多个序列共享同一LFSR和阈值控制器
  • 抽头选择策略: 确保不同序列间低相关性
  • 可扩展性: 线性增加硬件开销即可支持更多序列

实验设置

硬件实现

  • 工艺: 65nm CMOS工艺
  • 设计工具: Cadence Virtuoso ADE
  • LFSR配置: 32位，确保长周期
  • 比较器: 8位，平衡精度和功耗
  • 时钟频率: 2GHz

评价指标

  1. 统计特性控制精度: 理论值与实测值对比
  2. 随机性质量:
    • 自相关分析(非零滞后)
    • 互相关分析(不同序列间)
  3. 硬件性能:
    • 面积效率
    • 功耗特性
    • 能耗效率

测试场景

  1. 固定阈值测试: 验证不同阈值下的统计分布
  2. 动态阈值测试: 验证时变统计特性
  3. 多序列相关性测试: 验证序列间独立性

实验结果

主要结果

硬件性能指标

  • 面积: 261.5μm × 21.2μm = 0.0013mm²
  • 功耗: 1.14mW @ 2GHz
  • 能效: 0.57pJ/bit

统计控制精度

实验验证了阈值与输出概率的关系：

  • 阈值27: 高概率输出'1'
  • 阈值127: 中等概率输出'1'
  • 阈值227: 低概率输出'1'
  • 实测结果与理论公式P(1)=2m−1−Threshold2mP(1) = \frac{2^m - 1 - Threshold}{2^m}高度吻合

动态阈值性能

动态阈值控制下的累积计数表现出二次趋势： NCC(t)=−1.5396+2.4658tN+0.00551tN2NCC(t) = -1.5396 + 2.4658t_N + 0.00551t_N^2

增长率呈线性递减： dNCCdtN=−3.0792tN+2.4658\frac{dNCC}{dt_N} = -3.0792t_N + 2.4658

随机性质量评估

互相关分析

  • 不同序列间最大互相关值接近零
  • 表明序列间具有良好的独立性
  • 验证了抽头选择策略的有效性

自相关分析

  • 非零滞后下的最大自相关值接近零
  • 表明序列具有强随机性
  • 无明显周期性或重复模式

案例分析

动态阈值控制展现了两阶段行为：

  1. 阈值增长阶段: 输出'1'的概率逐渐降低，累积计数呈二次增长
  2. 阈值饱和阶段: 达到最大阈值后不再输出'1'，累积计数稳定

相关工作

传统PRNG方法

  1. 线性同余生成器(LCG): 简单但周期相对较短
  2. 线性反馈移位寄存器(LFSR): 硬件友好，周期长
  3. 细胞自动机(CA): 并行性好但复杂度高
  4. 混沌PRNG: 非线性特性好但实现复杂

本文优势对比

  • 统计可编程性: 相比传统方法，本文实现了运行时统计调控
  • 多序列效率: 通过资源共享显著降低硬件开销
  • 应用适配性: 特别适合需要非均匀随机性的应用

结论与讨论

主要结论

  1. 成功实现了可编程统计特性的硬件PRNG，能够精确控制输出分布
  2. 验证了多序列生成的有效性，序列间保持良好的独立性
  3. 达到了优异的硬件性能，面积和功耗均处于先进水平
  4. 确认了随机性质量，满足高质量PRNG的要求

局限性

  1. 阈值分辨率限制: 8位阈值控制器限制了统计调节的精细度
  2. 序列数量约束: 可生成的不相关序列数量受LFSR位数和抽头选择限制
  3. 应用领域特定: 主要针对需要非均匀随机性的特定应用

未来方向

  1. 提高阈值分辨率: 增加阈值控制器位数以实现更精细的统计控制
  2. 扩展序列容量: 优化抽头选择算法以支持更多不相关序列
  3. 集成更多分布: 支持高斯分布等其他常用概率分布
  4. 应用验证: 在实际的伊辛机和模拟退火系统中验证性能

深度评价

优点

  1. 技术创新性强: 首次在硬件层面实现了统计可编程的PRNG
  2. 实用价值高: 直接针对新兴应用需求，如量子计算模拟
  3. 设计优雅: 通过简单的阈值比较实现复杂的统计控制
  4. 验证充分: 从理论分析到硬件实现都有完整验证
  5. 性能优异: 面积和功耗指标达到先进水平

不足

  1. 理论分析深度: 对于抽头选择的理论分析可以更深入
  2. 应用验证: 缺乏在实际应用系统中的性能验证
  3. 比较范围: 与其他可编程PRNG方案的对比不够充分
  4. 可扩展性分析: 对大规模多序列场景的分析不够详细

影响力

  1. 学术贡献: 为可编程随机数生成领域提供了新的硬件解决方案
  2. 产业价值: 在量子计算模拟、优化算法等新兴领域有重要应用前景
  3. 技术推广: 设计方法可推广到其他需要可控随机性的系统

适用场景

  1. CMOS伊辛机: 需要时变随机性的量子计算模拟
  2. 模拟退火算法: 需要动态调整随机性的优化算法
  3. Monte Carlo仿真: 需要特定分布的统计仿真
  4. 神经网络训练: 需要可控噪声的随机化训练

参考文献

本文引用了6篇关键参考文献，涵盖了PRNG理论基础、硬件实现方法以及目标应用领域，为研究提供了坚实的理论和应用基础。

总体评价: 这是一篇高质量的硬件设计论文，提出了创新的可编程统计PRNG架构，在理论设计、硬件实现和性能验证方面都较为完整。该工作针对新兴应用需求，具有重要的学术价值和实用意义，为相关领域的发展做出了有益贡献。