Przetwarzanie liczb losowych o rozkładzie nierównomiernym na liczby losowe o rozkładzie równomiernym

• Autorzy: Jessa M.

Warianty tytułu

EN

Converting random numbers with non-uniform distribution into uniformly distributed random numbers

• Języki publikacji: PL

Abstrakty

PL

Podstawową wadą liczb losowych otrzymywanych sprzętowo jest ich nierównomierny rozkład. W rezultacie w ciągu wyjściowym liczba otrzymanych zer może się znacząco różnić od liczby jedynek. Sposobem na eliminację tej wady jest tzw. postprocessing. W artykule zaproponowano nową metodę postprocessingu, łatwą do zaimplementowania w każdym układzie cyfrowym. Stosując przekształcenia analityczne wykazano, że na wyjściu otrzymujemy liczby o rozkładzie równomiernym, niezależnie od postaci rozkładu liczb na wejściu. Metodę zilustrowano przykładem.

EN

Uniformly distributed random numbers play a key role in many fields of science. The basic disadvantage of random number generators is that the properties of a physical implementation differ from the theoretical expectations. Most sources of noise have a non-uniform distribution function, which eliminates them as a direct source of uniformly distributed random numbers. If the distribution is symmetric, we can use a threshold function, but this reduces the output bit rate and the output sequences are biased when the design is implemented in a real circuit. In this paper, there is proposed a novel method for producing uniformly distributed random numbers from non-uniformly distributed random numbers. The method uses an algorithm for improving the statistical quality of multiplicative congruential generators described in the literature. There is analytically shown that the bitwise exclusive-or sum of independent random numbers with non-uniform distribution provides, in the limit, numbers with uniform distribution. The proposed method also eliminates bias for constructions that use a threshold function and for sources with theoretically uniform distribution but implemented in real physical systems. Consequently, the set of systems that can be considered for use as sources of uniformly distributed random numbers is increased significantly to include practically all known sources of randomness. The method can be easily implemented in contemporary digital circuits.

Słowa kluczowe

PL

generator losowy; rozkład liczb losowych; kryptografia

EN

random number generator; distribution of numbers; cryptography

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2014
• Tom: R. 60, nr 7
• Strony: 453--455
• Opis fizyczny: Bibliogr. 7 poz., tab., wykr.

Twórcy

autor

Jessa M.

• Politechnika Poznańska, Wydział Elektroniki i Telekomunikacji, ul. Polanka 3, 60-965 Poznań

Bibliografia

• [1] Jessa M.: Generatory ciągów liter alfabetu skończonego, Wyd. Politechniki Poznańskiej, 2008.
• [2] Jessa M.: Jaworski M.: High-Speed FPGA-Based Pseudorandom Generators with Extremely Long Periods, ReConFig’10, Dec. 13-15, 2010, Cancun, s. 286-291.
• [3] Gentle J. E.: Random Number Generation and Monte Carlo Methods, Springer, 2003.
• [4] Davies R.: Exclusive OR (XOR) and hardware random number generators.”http://www.robertnz.net.
• [5] Schuster H. G.: Just W.: Deterministic Chaos, Wiley-VCH, 2005.
• [6] Bernstein G., Lieberman M. A.: Secure random number generation using chaotic circuits, IEEE Trans. Circuits and Syst. vol. 37, pp. Sept. 1990, s. 1157-1164.
• [7] Kudrewicz J.: Wąsowicz S.: Equations of Phase-Locked Loops, Dynamics on Circle, Torus and Cylinder, World Scientific, 2007.