Uniform random number generation

In typical stochastic simulations, randomness is produced by generating a sequence of independent uniform variates (usually real-valued between 0 and 1, or integer-valued in some interval) and transforming them in an appropriate way. In this paper, we examine practical ways of generating (deterministic approximations to) such uniform variates on a computer. We compare them in terms of ease of implementation, efficiency, theoretical support, and statistical robustness. We look in particular at several classes of generators, such as linear congruential, multiple recursive, digital multistep, Tausworthe, lagged-Fibonacci, generalized feedback shift register, matrix, linear congruential over fields of formal series, and combined generators, and show how all of them can be analyzed in terms of their lattice structure. We also mention other classes of generators, like non-linear generators, discuss other kinds of theoretical and empirical statistical tests, and give a bibliographic survey of recent papers on the subject.     

Gowers norms and pseudorandom measures of subsets

Let $A \subset {{\Bbb Z}_N}$, and ${f_A}(s) = \left\{ {\begin{array}{*{20}{l}}{1 - \frac{{|A|}}{N},}&{{\rm{for}}\;s \in A,}\\{ - \frac{{|A|}}{N},}&{{\rm{for}}\;s \notin A.}\end{array}} \right.$ We define the pseudorandom measure of order k of the subset A as follows, P_k(A, N) = $\begin{array}{*{20}{c}}{\max }\\D\end{array}$|$\mathop \Sigma \limits_{n \in {\mathbb{Z}_N}}$f_A(n + c₁)f_A(n + c₂) … f_A(n + c_k)|, where the maximum is taken over all D = (c₁, c₂, . . . , c_k) ∈ ${\mathbb{Z}^k}$ with 0 ≤ c₁ < c₂ < … < c_k ≤ N - 1. The subset A ⊂ ${{\mathbb{Z}_N}}$ is considered as a pseudorandom subset of degree k if P_k(A, N) is “small” in terms of N. We establish a link between the Gowers norm and our pseudorandom measure, and show that “good” pseudorandom subsets must have “small” Gowers norm. We give an example to suggest that subsets with “small” Gowers norm may have large pseudorandom measure. Finally, we prove that the pseudorandom subset of degree L(k) contains an arithmetic progression of length k, where L(k) = 2·lcm(2, 4, . . . , 2|$\frac{k}{2}$|), for k ≥ 4, and lcm(a₁, a₂, . . . , a_l) denotes the least common multiple of a₁, a₂, . . . , a_l.     

All-optical pseudorandom binary sequence generator with TOAD-based D flip-flops

An all-optical pseudo random binary sequence (PRBS) generator is designed using serially interconnected discrete Terahertz Optical Asymmetric Demultiplexer (TOAD)-based D flip-flops in a configuration exactly like the standard electronic setup. The performance of the circuit is evaluated through numerical simulation, which confirms its feasibility in terms of the choice of the critical parameters. The proposed scheme has been theoretically demonstrated for a 3-bit and 7-bit degree PRBS but can be extended to higher order by means of additional TOAD-based D flip-flops. Thus it can constitute an efficient solution for implementing all-optically a PRBS in an affordable, controllable and realistic manner.     

Unconventional Coding Technique Applied to Multi-Level Polarization Modulation

A new technique is proposed to improve information confidentiality in optical-fiber communications without bandwidth consumption. A pseudorandom vectorial sequence was generated by a dynamic system algorithm and used to codify a multi-level polarization modulation based on the Stokes vector. Optical-fiber birefringence, usually considered as a disturbance, was exploited to obfuscate the signal transmission. At the receiver end, the same pseudorandom sequence was generated and used to decode the multi-level polarization modulated signal. The proposed scheme, working at the physical layer, provides strong information security without introducing complex processing and thus latency.     

大族长度为pq的伪随机k元序列

Mauduit与Sárkzy在一系列论文中研究了κ元序列的伪随机性.本文通过对模pq剩余类环Z_(pq)进行分割,进而结合离散对数的方法,构造了一大族长度为pq的伪随机κ元序列,并证明其具有很好的伪随机性.     

Ultra-high speed all-optical shift registers and their applications in OTDM networks

All-optical shift registers are basic building modules for the development of ultra-high speed optical time division multiplexing networks. In this paper, we review the progress that has been made in this cutting-edge technology, focusing on implementations that exploit the attractive features of semiconductor optical amplifier (SOA)-based interferometric configurations. We present regenerative storage performed with an all-optical recirculating shift register with an inverter at 10 Gb/s using a SOA-assisted Sagnac switch and a second SOA to provide feedback. We demonstrate also an all-optical memory based on the SOA-assisted Ultrafast Nonlinear Interferometer capable of reading/writing 20 Gb/s packets of variable length without data inversion. These registers can find application in the development of two nontrivial complex all-optical circuits of enhanced functionality. The first is an all-optical pseudorandom binary sequence generator for which we describe an efficient design algorithm and propose ways for monitoring and verification. The second is an all-optical error counter for which we address the error detection and evaluation issues using a novel sampling technique. These circuits are key elements for the implementation of a high-speed, all-optical bit error rate tester (BERT), which has the potential to outperform its electronic equivalent and constitute a possible new product for the telecommunications industry.     

A complexity measure for families of binary sequences

In earlier papers finite pseudorandom binary sequences were studied, quantitative measures of pseudorandomness of them were introduced and studied, and large families of “good” pseudorandom sequences were constructed. In certain applications (cryptography) it is not enough to know that a family of “good” pseudorandom binary sequences is large, it is a more important property if it has a “rich”, “complex” structure. Correspondingly, the notion of “f-complexity” of a family of binary sequences is introduced. It is shown that the family of “good” pseudorandom binary sequences constructed earlier is also of high f-complexity. Finally, the cardinality of the smallest family achieving a prescibed f-complexity and multiplicity is estimated. This revised version was published online in August 2006 with corrections to the Cover Date.     

O-RPR网络中622 Mbps光上路源的研制

基于全光缓存器的光弹性分组交换环(O-RPR)是一种全光分组交换网络,能够克服目前RPR存在的电子瓶颈。为了模拟这种网络解决竞争的能力和解决网络的帧同步不丢失的问题,设计了一种基于FPGA的光上路源。它由数据包(帧)生成、并串变换和电光转换三部分组成,其包长、包内伪随机序列长度、及通信速率均可变,具有结构简单、成本低廉和操作方便的优点,已成功应用于O-RPR实验网络中。     

On the Linear Complexity and Multidimensional Distribution of Congruential Generators over Elliptic Curves

We show that the elliptic curve analogue of the linear congruential generator produces sequences with high linear complexity and good multidimensional distribution.communicated by: A. MenezesAMS Classification: 11T23, 14H52, 65C10     

1‐Factorizations of pseudorandom graphs

A 1‐factorization of a graph G is a collection of edge‐disjoint perfect matchings whose union is E(G). In this paper, we prove that for any ?>0, an (n,d,λ)‐graph G admits a 1‐factorization provided that n is even, C₀ ≤ d ≤ n?1 (where C₀=C₀(?) is a constant depending only on ?), and λ ≤ d^1??. In particular, since (as is well known) a typical random d‐regular graph G_n,d is such a graph, we obtain the existence of a 1‐factorization in a typical G_n,d for all C₀ ≤ d ≤ n?1, thereby extending to all possible values of d results obtained by Janson, and independently by Molloy, Robalewska, Robinson, and Wormald for fixed d. Moreover, we also obtain a lower bound for the number of distinct 1‐factorizations of such graphs G, which is better by a factor of 2^nd/2 than the previously best known lower bounds, even in the simplest case where G is the complete graph.