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

Basic Information

• Paper ID: 2501.00193
• Title: A Pseudo-random Number Generator for Multi-Sequence Generation with Programmable Statistics
• Authors: Jianan Wu, Ahmet Yusuf Salim, Eslam Elmitwalli, Selçuk Köse, Zeljko Ignjatovic (University of Rochester)
• Classification: cs.CR cs.IT math.IT
• Technology Node: 65nm CMOS
• Paper Link: https://arxiv.org/abs/2501.00193

Abstract

Pseudo-random number generators (PRNGs) are crucial for a wide range of applications spanning from cryptography to statistical simulation and optimization algorithms. While uniform randomness is essential for security-critical domains such as cryptography, many fields—including simulated annealing and CMOS-based Ising machines—benefit from controlled or non-uniform randomness to enhance solution space exploration and optimization performance. This paper proposes a hardware PRNG capable of simultaneously generating multiple uncorrelated sequences with programmable statistical properties tailored to specific application requirements. Designed in 65nm technology, the PRNG occupies an area of approximately 0.0013mm² with power consumption of 0.57pJ/bit. Simulations confirm the PRNG's effectiveness in modulating statistical distributions while demonstrating high-quality randomness characteristics.

Research Background and Motivation

Problem Definition

Traditional PRNGs primarily focus on generating uniformly distributed random sequences, yet many practical applications require non-uniform random sequences with specific statistical properties:

1. Diverse Application Requirements: Applications such as simulated annealing and CMOS-based Ising machines require controllable non-uniform randomness to optimize performance
2. Multi-Sequence Demands: Many applications require simultaneous generation of multiple uncorrelated random sequences
3. Hardware Implementation Challenges: Existing PRNGs struggle to achieve flexible control of statistical properties at the hardware level

Research Significance

• Performance Optimization: Controlled randomness can enhance solution space exploration and improve algorithm performance
• Application Adaptation: Different applications have varying statistical requirements for randomness, necessitating programmable solutions
• Hardware Efficiency: Hardware-implemented PRNGs offer advantages in power consumption and area efficiency

Limitations of Existing Methods

1. Fixed Statistical Distribution: Traditional PRNGs primarily generate uniform distributions, lacking flexibility
2. Multi-Sequence Overhead: Generating multiple sequences requires independent hardware sets, increasing costs
3. Difficult Runtime Control: Existing approaches struggle to achieve runtime adjustment of statistical properties

Core Contributions

1. Proposed a programmable hardware PRNG architecture capable of real-time modulation of output sequence statistical distributions
2. Designed a multi-sequence generation scheme achieving efficient multi-sequence output through shared LFSR and threshold controllers
3. Implemented a compact hardware design with area of only 0.0013mm² and power consumption of 0.57pJ/bit in 65nm technology
4. Provided dynamic threshold control mechanisms supporting time-varying statistical properties suitable for applications like simulated annealing
5. Verified sequence quality through autocorrelation and cross-correlation analysis confirming excellent randomness

Methodology Details

Task Definition

Design a hardware PRNG system capable of:

• Input: Clock signal, threshold control parameters
• Output: Multiple 1-bit pseudo-random sequences with programmable statistical properties
• Constraints: Low power consumption, small area, high-quality randomness, low inter-sequence correlation

Model Architecture

Overall Architecture

The system comprises three core modules:

1. Linear Feedback Shift Register (LFSR)
   • 32-bit LFSR ensures sufficiently long period (2³²-1)
   • Characteristic polynomial defines feedback structure: $P(x) = x^n + a_{n-1}x^{n-1} + ... + a_1x + 1$
   • Multiple m-bit uniformly distributed sequences generated through different tap combinations
2. Threshold Controller
   • Outputs m-bit threshold signal controlling final sequence statistical properties
   • Supports both static and dynamic threshold adjustment
   • Dynamic controller implements time-varying thresholds based on counters
3. Digital Comparator
   • m-bit comparator compares LFSR output with threshold
   • Output probability theoretical expression: $P(1) = \frac{2^m - 1 - \text{Threshold}}{2^m}$

Multi-Sequence Generation Mechanism

• Ensures sequence decorrelation through LFSR taps at different intervals
• Each additional sequence requires only one comparator and corresponding XOR gate
• Shared LFSR and threshold controller improve hardware efficiency
• Number of uncorrelated m-bit sequences: $C(n-1, k-1)/m$, where k is the number of taps per XOR operation

Technical Innovations

1. Programmable Statistical Control

• Innovation: Achieves precise statistical distribution control through threshold modulation
• Implementation Principle: Uniformly distributed m-bit sequences compared with adjustable threshold, output probability becomes controllable
• Advantage: Real-time adjustment without hardware redesign

2. Dynamic Threshold Control

Dynamic Threshold Controller Implementation:
- Counter provides incrementing threshold
- Logic circuits control counter start/stop
- Supports applications requiring time-varying randomness such as simulated annealing

3. Efficient Multi-Sequence Architecture

• Resource Sharing: Multiple sequences share single LFSR and threshold controller
• Tap Selection Strategy: Ensures low correlation between different sequences
• Scalability: Linear hardware overhead increase supports additional sequences

Experimental Setup

Hardware Implementation

• Technology: 65nm CMOS
• Design Tools: Cadence Virtuoso ADE
• LFSR Configuration: 32-bit, ensuring long period
• Comparator: 8-bit, balancing precision and power consumption
• Clock Frequency: 2GHz

Evaluation Metrics

1. Statistical Property Control Precision: Comparison of theoretical and measured values
2. Randomness Quality:
   • Autocorrelation analysis (non-zero lag)
   • Cross-correlation analysis (between different sequences)
3. Hardware Performance:
   • Area efficiency
   • Power characteristics
   • Energy efficiency

Test Scenarios

1. Fixed Threshold Testing: Verifies statistical distribution under different thresholds
2. Dynamic Threshold Testing: Verifies time-varying statistical properties
3. Multi-Sequence Correlation Testing: Verifies inter-sequence independence

Experimental Results

Main Results

Hardware Performance Metrics

• Area: 261.5μm × 21.2μm = 0.0013mm²
• Power: 1.14mW @ 2GHz
• Energy Efficiency: 0.57pJ/bit

Statistical Control Precision

Experiments verified the relationship between threshold and output probability:

• Threshold 27: High probability of outputting '1'
• Threshold 127: Medium probability of outputting '1'
• Threshold 227: Low probability of outputting '1'
• Measured results align closely with theoretical formula $P(1) = \frac{2^m - 1 - \text{Threshold}}{2^m}$

Dynamic Threshold Performance

Cumulative count under dynamic threshold control exhibits quadratic trend: $\text{NCC}(t) = -1.5396 + 2.4658t_N + 0.00551t_N^2$

Growth rate shows linear decrease: $\frac{d\text{NCC}}{dt_N} = -3.0792t_N + 2.4658$

Randomness Quality Assessment

Cross-Correlation Analysis

• Maximum cross-correlation between different sequences approaches zero
• Indicates excellent independence between sequences
• Validates effectiveness of tap selection strategy

Autocorrelation Analysis

• Maximum autocorrelation at non-zero lags approaches zero
• Indicates strong randomness in sequences
• No apparent periodicity or repetitive patterns

Case Study

Dynamic threshold control exhibits two-stage behavior:

1. Threshold Growth Stage: Probability of outputting '1' gradually decreases, cumulative count exhibits quadratic growth
2. Threshold Saturation Stage: After reaching maximum threshold, no longer outputs '1', cumulative count stabilizes

Related Work

Traditional PRNG Methods

1. Linear Congruential Generator (LCG): Simple but relatively short period
2. Linear Feedback Shift Register (LFSR): Hardware-friendly, long period
3. Cellular Automata (CA): Good parallelism but high complexity
4. Chaotic PRNG: Good nonlinear properties but complex implementation

Advantages Compared to This Work

• Statistical Programmability: Achieves runtime statistical control compared to traditional methods
• Multi-Sequence Efficiency: Significantly reduces hardware overhead through resource sharing
• Application Adaptability: Particularly suitable for applications requiring non-uniform randomness

Conclusions and Discussion

Main Conclusions

1. Successfully implemented programmable hardware PRNG capable of precise distribution control
2. Verified effectiveness of multi-sequence generation with excellent inter-sequence independence
3. Achieved excellent hardware performance with area and power consumption at advanced levels
4. Confirmed randomness quality meeting high-quality PRNG requirements

Limitations

1. Threshold Resolution Constraints: 8-bit threshold controller limits fineness of statistical adjustment
2. Sequence Number Constraints: Number of uncorrelated sequences limited by LFSR bit width and tap selection
3. Application-Specific: Primarily targets specific applications requiring non-uniform randomness

Future Directions

1. Increase Threshold Resolution: Expand threshold controller bit width for finer statistical control
2. Extend Sequence Capacity: Optimize tap selection algorithms to support more uncorrelated sequences
3. Integrate Additional Distributions: Support other common probability distributions such as Gaussian
4. Application Validation: Verify performance in actual Ising machines and simulated annealing systems

In-Depth Evaluation

Strengths

1. Strong Technical Innovation: First hardware-level implementation of statistically programmable PRNG
2. High Practical Value: Directly addresses emerging application requirements such as quantum computing simulation
3. Elegant Design: Achieves complex statistical control through simple threshold comparison
4. Comprehensive Verification: Complete verification from theoretical analysis to hardware implementation
5. Excellent Performance: Area and power consumption metrics reach advanced levels

Weaknesses

1. Limited Theoretical Depth: Theoretical analysis of tap selection could be more thorough
2. Insufficient Application Validation: Lacks performance verification in actual application systems
3. Limited Comparison Scope: Insufficient comparison with other programmable PRNG schemes
4. Incomplete Scalability Analysis: Insufficient analysis for large-scale multi-sequence scenarios

Impact

1. Academic Contribution: Provides novel hardware solution for programmable random number generation field
2. Industrial Value: Important application prospects in quantum computing simulation, optimization algorithms
3. Technology Promotion: Design methodology applicable to other systems requiring controllable randomness

Applicable Scenarios

1. CMOS Ising Machines: Quantum computing simulation requiring time-varying randomness
2. Simulated Annealing Algorithms: Optimization algorithms requiring dynamic randomness adjustment
3. Monte Carlo Simulation: Statistical simulation requiring specific distributions
4. Neural Network Training: Randomized training requiring controllable noise

References

This paper cites six key references covering PRNG theoretical foundations, hardware implementation methods, and target application domains, providing solid theoretical and application basis for the research.

Overall Assessment: This is a high-quality hardware design paper proposing an innovative programmable statistical PRNG architecture with relatively complete theoretical design, hardware implementation, and performance verification. This work addresses emerging application requirements with significant academic value and practical significance, making beneficial contributions to related field development.