This discussion has been locked.

You can no longer post new replies to this discussion. If you have a question you can start a new discussion

how to generate random number?

Ivan Cheung over 21 years ago

Does anybody know how to generate random number using 8051?

Parents

0 Graham Cole over 21 years ago in reply to Ivan Cheung

Here is a very small 16-bit LFSR based pseudo random number generator and it is about as basic as you can get.

#include <REG52.H>

//
//  Masks for 8-bit galios LFSR maximum run length generator
//
//  8 stages, 4 taps:  (6 sets)
//
//  [8, 7, 6, 1]
//  [8, 7, 5, 3]
//  [8, 7, 3, 2]
//  [8, 6, 5, 4]
//  [8, 6, 5, 3]
//  [8, 6, 5, 2]
//
//  [8, 7, 6, 1] =
//
//    3                   2                   1                   0
//  1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
//  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1
//
//  0 0 0 0 0 0 0 0  = 0xE1
//
//  Masks for 16-bit galios LFSR maximum run length generator
//
// 16 stages, 8 taps:  (406 sets)
//
//  [16, 15, 14, 13, 12, 11, 10, 4]
//  [16, 15, 14, 13, 12, 11, 9, 8]
//  [16, 15, 14, 13, 12, 11, 9, 6]
//  [16, 15, 14, 13, 12, 11, 9, 5]
//  [16, 15, 14, 13, 12, 11, 8, 2]
//  [16, 15, 14, 13, 12, 11, 5, 2]
//  [16, 15, 14, 13, 12, 10, 9, 5]
//  [16, 15, 14, 13, 12, 10, 5, 1]
//  [16, 15, 14, 13, 12, 9, 8, 7]
//  [16, 15, 14, 13, 12, 9, 7, 1]
//  [16, 15, 14, 13, 12, 9, 6, 3]
//  [16, 15, 14, 13, 12, 9, 6, 2]
//  [16, 15, 14, 13, 12, 9, 3, 2]
//  [16, 15, 14, 13, 12, 8, 4, 1]
//  [16, 15, 14, 13, 12, 7, 6, 4]
//  [16, 15, 14, 13, 12, 6, 5, 3]
//  [16, 15, 14, 13, 12, 6, 5, 2]
//  [16, 15, 14, 13, 12, 6, 3, 2]
//  [16, 15, 14, 13, 12, 5, 4, 3]
//  [16, 15, 14, 13, 12, 5, 3, 2]
//  [16, 15, 14, 13, 11, 10, 8, 4]
//  [16, 15, 14, 13, 11, 10, 6, 1]
//  [16, 15, 14, 13, 11, 10, 5, 4]
//  [16, 15, 14, 13, 11, 10, 3, 1]
//  [16, 15, 14, 13, 11, 9, 8, 5]
//  [16, 15, 14, 13, 11, 9, 8, 2]
//  [16, 15, 14, 13, 11, 9, 7, 4]
//  [16, 15, 14, 13, 11, 9, 7, 3]
//  [16, 15, 14, 13, 11, 9, 6, 5]
//  [16, 15, 14, 13, 11, 9, 6, 4]
//  [16, 15, 14, 13, 11, 9, 6, 1]
//  etc...
//
//  [16, 15, 14, 13, 11, 9, 6, 1] =
//
//    3                   2                   1                   0
//  1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
//  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 0 1 0 0 1 0 0 0 0 1
//
//  1 1 1 1 0 1 0 1  = 0xF5
//  0 0 1 0 0 0 0 1  = 0x21
//

#pragma ASM

$REGUSE small_rand( PSW, A, R7 )

#pragma ENDASM

static data unsigned int lfsr = 0xA5A5;

unsigned char small_rand()
{

    #pragma ASM
                                    ;
        MOV     R7,#8               ;
                                    ;
?random_loop:                       ;
                                    ;
        CLR     C                   ;
        MOV     Acc,lfsr+0          ;
        RRC     A                   ;
        MOV     lfsr+0,A            ;
        MOV     Acc,lfsr+1          ;
        RRC     A                   ;
        MOV     lfsr+1,A            ;
                                    ;
        JNC     ?random_x           ;
                                    ;
        XRL     lfsr+0,#0xF5        ;
        XRL     lfsr+1,#0x21        ;
                                    ;
?random_x:                          ;
                                    ;
        DJNZ    R7,?random_loop     ;
                                    ;
    #pragma ENDASM

    return( (unsigned char) lfsr );
}

And a test harness:

extern unsigned char small_rand();

main()
{
    data  unsigned int loop;

    data  unsigned int v,target;

    xdata unsigned int a[256];

    loop = 256;

    do
    {

         a[ loop ] = 0;

    } while( --loop != 0 );

    target = small_rand();

    loop = 0;

    do
    {

        v = small_rand();

        a[ v % 256 ]++;

        if( v == target )
        {
            target = v;
        }

    } while( ++loop != 0 );
}

I have not had time to test this fully, but it seems to work OK.

It is possible to have an LFSR that is just 8-bits long, but the shorter the LFSR the less random the results are. If you let us know what the numbers are needed for, we may be able to offer more helpful advice.

The LFSR implemented above is a 16-bit Galois implementation. See here for a very helpful web-site: http://www.newwaveinstruments.com/resources/articles/m_sequence_linear_feedback_shift_register_lfsr.htm#Table%20of%20M-Sequence%20Feedback%20Taps

Reply

0 Graham Cole over 21 years ago in reply to Ivan Cheung

Here is a very small 16-bit LFSR based pseudo random number generator and it is about as basic as you can get.

#include <REG52.H>

//
//  Masks for 8-bit galios LFSR maximum run length generator
//
//  8 stages, 4 taps:  (6 sets)
//
//  [8, 7, 6, 1]
//  [8, 7, 5, 3]
//  [8, 7, 3, 2]
//  [8, 6, 5, 4]
//  [8, 6, 5, 3]
//  [8, 6, 5, 2]
//
//  [8, 7, 6, 1] =
//
//    3                   2                   1                   0
//  1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
//  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1
//
//  0 0 0 0 0 0 0 0  = 0xE1
//
//  Masks for 16-bit galios LFSR maximum run length generator
//
// 16 stages, 8 taps:  (406 sets)
//
//  [16, 15, 14, 13, 12, 11, 10, 4]
//  [16, 15, 14, 13, 12, 11, 9, 8]
//  [16, 15, 14, 13, 12, 11, 9, 6]
//  [16, 15, 14, 13, 12, 11, 9, 5]
//  [16, 15, 14, 13, 12, 11, 8, 2]
//  [16, 15, 14, 13, 12, 11, 5, 2]
//  [16, 15, 14, 13, 12, 10, 9, 5]
//  [16, 15, 14, 13, 12, 10, 5, 1]
//  [16, 15, 14, 13, 12, 9, 8, 7]
//  [16, 15, 14, 13, 12, 9, 7, 1]
//  [16, 15, 14, 13, 12, 9, 6, 3]
//  [16, 15, 14, 13, 12, 9, 6, 2]
//  [16, 15, 14, 13, 12, 9, 3, 2]
//  [16, 15, 14, 13, 12, 8, 4, 1]
//  [16, 15, 14, 13, 12, 7, 6, 4]
//  [16, 15, 14, 13, 12, 6, 5, 3]
//  [16, 15, 14, 13, 12, 6, 5, 2]
//  [16, 15, 14, 13, 12, 6, 3, 2]
//  [16, 15, 14, 13, 12, 5, 4, 3]
//  [16, 15, 14, 13, 12, 5, 3, 2]
//  [16, 15, 14, 13, 11, 10, 8, 4]
//  [16, 15, 14, 13, 11, 10, 6, 1]
//  [16, 15, 14, 13, 11, 10, 5, 4]
//  [16, 15, 14, 13, 11, 10, 3, 1]
//  [16, 15, 14, 13, 11, 9, 8, 5]
//  [16, 15, 14, 13, 11, 9, 8, 2]
//  [16, 15, 14, 13, 11, 9, 7, 4]
//  [16, 15, 14, 13, 11, 9, 7, 3]
//  [16, 15, 14, 13, 11, 9, 6, 5]
//  [16, 15, 14, 13, 11, 9, 6, 4]
//  [16, 15, 14, 13, 11, 9, 6, 1]
//  etc...
//
//  [16, 15, 14, 13, 11, 9, 6, 1] =
//
//    3                   2                   1                   0
//  1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
//  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 0 1 0 0 1 0 0 0 0 1
//
//  1 1 1 1 0 1 0 1  = 0xF5
//  0 0 1 0 0 0 0 1  = 0x21
//

#pragma ASM

$REGUSE small_rand( PSW, A, R7 )

#pragma ENDASM

static data unsigned int lfsr = 0xA5A5;

unsigned char small_rand()
{

    #pragma ASM
                                    ;
        MOV     R7,#8               ;
                                    ;
?random_loop:                       ;
                                    ;
        CLR     C                   ;
        MOV     Acc,lfsr+0          ;
        RRC     A                   ;
        MOV     lfsr+0,A            ;
        MOV     Acc,lfsr+1          ;
        RRC     A                   ;
        MOV     lfsr+1,A            ;
                                    ;
        JNC     ?random_x           ;
                                    ;
        XRL     lfsr+0,#0xF5        ;
        XRL     lfsr+1,#0x21        ;
                                    ;
?random_x:                          ;
                                    ;
        DJNZ    R7,?random_loop     ;
                                    ;
    #pragma ENDASM

    return( (unsigned char) lfsr );
}

And a test harness:

extern unsigned char small_rand();

main()
{
    data  unsigned int loop;

    data  unsigned int v,target;

    xdata unsigned int a[256];

    loop = 256;

    do
    {

         a[ loop ] = 0;

    } while( --loop != 0 );

    target = small_rand();

    loop = 0;

    do
    {

        v = small_rand();

        a[ v % 256 ]++;

        if( v == target )
        {
            target = v;
        }

    } while( ++loop != 0 );
}

Children

No data