（转载）Pseudo-Random Number Generation Routine for the MAX765x Microprocessor

Abstract: This application note gives a function for random number generation using the MAX7651/52 microcontroller with 12-bit analog-to-digital converter (ADC).

Applications such as spread-spectrum communications, security, encryption and modems require the generation of random numbers. The most common way to implement a random number generator is a Linear Feedback Shift Register (LFSR). Codes generated by a LFSR are actually "pseudo" random, because after some time the numbers repeat. The trick is to use a shift register of sufficient length so that the pattern repeats after some extremely long time.

A basic LFSR of length five is shown in Figure 1. The shift register is a series-connected group of flip-flops, with XOR feedback. An XOR gate is use to scramble the input bit.

Figure 1. 5-stage linear feedback shift register.
Figure 1. 5-stage linear feedback shift register.

There are tables that give the proper feedback tap position for generating sequences that take the maximum number of clocks to repeat. Such a table is shown below:

Table 1. Taps for Maximal-Length LFSRs with 2 to 32 Bits
No. of bits Length of Loop Taps
2 3* [0,1]
3 7* [0,2]
4 15 [0,3]
5 31* [1,4]
6 63 [0,5]
7 127* [0,6]
8 255 [1,2,3,7]
9 511 [3,8]
10 1023 [2,9]
11 2047 [1,10]
12 4095 [0,3,5,11]
13 8191* [0,2,3,12]
14 16,383 [0,2,4,13]
15 32,767 [0,14]
16 65,535 [1,2,4,15]
17 131,071* [2,16]
18 262,143 [6,17]
19 524,287* [0,1,4,18]
20 1,048,575 [2,19]
21 2,097,151 [1,20]
22 4,194,303 [0,21]
23 8,388,607 [4,22]
24 16,777,215 [0,2,3,23]
25 33,554,431 [7,24]
26 67,108,863 [0,1,5,25]
27 134,217,727 [0,1,4,26]
28 268,435,455 [2,27]
29 536,870,911 [1,28]
30 1,073,741,823 [0,3,5,29]
31 2,147,483,647* [2,30]
32 4,294,967,295 [1,5,6,31]

* Sequences whose length is a prime number

Be aware that there are multiple solutions for tap positions to generate maximum length sequences.

There is one major issue with using LFSRs: if all stages happen to be '0', the shift register gets "stuck". This is because the XOR of all '0's is still '0'. The XOR feedback does not produce a '1' to get the sequence started again. To prevent this condition, the routine must be first loaded with a non-zero seed value. This value can be any number at all, as long as it is not zero. The numbers generated by the LFSR are based on the seed value. You will get the same sequence of numbers, over and over, unless at some point the LSFR is reloaded with a different seed.

Where does this seed value come from? It will depend on what is available in your particular application. For example, if your system has access to a RTC (real-time clock), then a good seed is based off the time. You can read the current time and/or date, mask off portions and use that as a seed. Another example is temperature. If your system can read temperature (assuming it's not constant) then that can make a good seed. The ADC of the MAX765x can be set to read all sorts of things: scales AC power line voltage, some sensor position or even amplified Johnson noise from a Zener diode (a common practice in cryptography).

However, in some cases you will just have to use 01H or some other number, and accept the fact that the sequence will repeat eventually and in a predetermined pattern.

The routine presented uses a 25-bit sequence, which repeats after being called 33 million times. Even if you cannot produce a unique seed each time, the length is such that in most applications, the "randomness" is more than sufficient.

The MAX765x listing is shown below. The routine uses four 8-bit memory locations labeled RN1-RN4. The lower 3 bytes RN1-RN3 are used for 24 bits, and the MSB of RN4 is the 25th bit. The algorithm uses XOR feedback (using the processor's XRL instruction) from "stages" 25 (the Carry bit) and stage 7 (the MSB of RN1). Since all of the resisters are simply RAM locations, you can form up to 32-bit wide random numbers. For this example, an 8-bit number RANNUM is stored in RAM at the end of the routine.

To get a true Gaussian distribution function of the random numbers, you can do further processing. Adding some arbitrary number of consecutive samples and taking the average (say 4) will create a Gaussian distribution.

One programming 'trick' which is used in the algorithm are "byte swaps" to simulate a "shifting by 8 clocks". This is to save CPU clock cycles. For example, if the original byte order was ABCD, after the byte-swaps the order is BCDA. This prevents the code from having to do "housekeeping" from shifting a byte's MSB into the next byte's LSB. It doesn't matter if the random numbers are calculated every clock or every 8 clocks: they are still random. Since the total length of the LFSR is a product of 3 prime numbers (31, 601 and 1801) the sequence is still 33,554,431 subroutine calls until the sequence repeats! Of course, since we are looking at 8 of the bits for our example, the values are restricted to 00H to 0FFH, and so the same value will be returned multiple times.

Another cycle-saving 'trick' used is when the XOR of the 2 bits of interest is executed, the entire contents of RN1 is altered (see the comment below).

;
; SUBROUTINE RANDOM
;
; GENERATES RANDOM NUMBERS USING 25 BIT SHIFT REGISTER
; WITH XOR FEEDBACK ON STAGES 7 AND 25 (MAX CYCLE LENGTH)
;
; IN ORDER FOR THIS ROUTINE TO WORK, THERE ARE 2 THINGS TO CONSIDER:
; A) SOME TYPE OF NON-ZERO VALUE ‘SEED’ MUST FIRST BE LOADED INTO RN1
: B) THE SEQUENCE WILL REPEAT AFTER APPROX 33 MILLION CALLS TO THE ROUTINE
;
; CPU RESOURCES REQUIRED:
;
; 6 RAM LOCATIONS AS FOLLOWS
;
; RANNUM: THE CALCULATED RANDOM NUMBER
; RN1-RN1: FORMS THE SHIFT REGISTER
; TEMP1: A TEMPORARY SCRATCH-PAD REGISTER
;
; THE ROUTINE DESTROYS THE A REGISTER AND THE CARRY BIT
;
;
RANDOM: MOV     A,RN4           ; BIT 25 TO CARRY
        RRC     A
        MOV     RN4,RN3
        MOV     RN3,RN2
        MOV     RN2,RN1         ; SHIFT ALL BYTES LEFT
        MOV     A,RN4           ; WAS RN3
        RRC     A               ; GET BIT 25 (IN CARRY) INTO OLD RN3
        MOV     TEMP1,A         ; SAVE IT FOR LATER
        MOV     A,RN1
        RLC     A               ; BIT 1 TO 7 IN POSITION
        MOV     RN1,A           ; PUT BACK
        MOV     A,TEMP1         ; RESTORE A
        XRL     A,RN1           ; MOD 2 SUM OF ALL BITS IN RN1 AND THE CARRY BIT
        MOV     TEMP1,A         ; SAVE IT
        MOV     A,RN4
        RRC     A
        MOV     RN4,A           ; ROTATE RN4
        MOV     A,RN3
        RRC     A
        MOV     RN3,A           ; ROTATE RN3
        MOV     A,RN2
        RRC     A
        MOV     RN2,A           ; ROTATE RN2
        MOV     A,TEMP1         ; RESTORE A
        RLC     A
        MOV     RN1,A ; xor OVER-WRITES ALL 8 BITS, BUT DOESN’T MATTER
MOV     RANNUM,A        ; RANDOM NUMBER!!
        RET

Related Parts   APP 1743: Sep 25, 2002
MAX7651 Flash Programmable 12-Bit Integrated Data-Acquisition Systems Full Data Sheet
(PDF, 488kB)
MAX7652 Flash Programmable 12-Bit Integrated Data-Acquisition Systems Full Data Sheet
(PDF, 488kB)
Automatic Updates
Would you like to be automatically notified when new application notes are published in your areas of interest? Sign up for EE-Mail™.

Your Comments
Login or register to post a comment.