IKIBLOGKU

This article has been taken from www.codeguru.com,  it’s working great.

Andy McGovern (view profile)
May 26, 2004

Environment: VC++ 6, Win32

Introduction

Many exciting applications, such as data encryption and genetic algorithm programs, use randomly generated numbers to make choices. In some (rare) cases, only truly random numbers will do; that makes things complex because programs are based on logic, and the logic they use can generally be reversed. In other words, it is difficult to program a series of logical steps that produces numbers that don’t follow some kind of pattern. One approach for generating truly random numbers is to measure some kind of continuous natural phenomena; for instance, the noise power level in a radio-frequency receiver. The noise power level appears to be random because the power level at any instant in time depends on so many variables, such as cosmic radiation, solar energy, Earth thermal energy, and so forth. For most applications, pseudo-random numbers are sufficient. Pseudo-random numbers follow predictable patterns, but they do so over very long periods. The idea is that you would have to look at a very long (maybe in the billions) string of numbers before you would see a repeat of the pattern.

A conceptually simple way to generate long sequences of pseudo-random numbers is with a linear feedback shift register (lfsr). The tapped elements (the memory slots connected to the circle with the plus inside) are XOR’ed (0 xor 1 = 1; 0 xor 0 = 0; 1 xor 1 = 0) and then placed in the right-most bit slot, pushing all the previous bits one slot to the left. The sequence of 1s and 0s that pop off the left side of the register are the pseudo-random number sequence. The catch is that some tap positions cause the register to short cycle; in other words, some tap positions do not use the register to its greatest capability. A register’s maximum-length sequence will be (2^n - 1) bits long; n is the number of slots in the register. A short cycle in the register has occurred if the register ends up with the same fill that it started with before (2^n - 1) cycles elapse. Any book on spread spectrum communications or error correcting codes is bound to have a table listing tap positions corresponding to maximal length sequences for given LFSR lengths.

Figure 1: LFSR with an initial fill (0,0,1,1,0,1,0) and taps on elements (0,3) Continue reading ‘A Random Number Generation Technique with Encryption and Genetic Algorithm Applications’