C18 - Fragen zu Pseudo Random Generator

[martinidry]

Hallo,
ich programmiere einen 18F2420 mit C18. Ich versuche, 8 an PORTA angeschlossene LED so anzusteuern, dass für den Betrachter die Auswahl willkürlich bzw. zufällig erscheinen soll. Es soll immer nur eine LED leuchten. Dazu habe ich mich der Funktionen srand() und srand() aus der MPLAB C18 Compiler Library bedient (stdlib.h). Leider sieht mein Ergebnis nicht besonders zufällig aus sondern folgt irgendeiner Regelmäßigeit. Hat jemand eine Idee was ich falsch mache bzw. ob rand() für die gewünschte Aufage ungeeignet ist?

Code:

#include <p18f2420.h>                                                       
#include <delays.h> 
#include <stdlib.h>
#include <timers.h> 
#include <math.h>                                                     
                                             
void INIT(void);
void Random(void);
                                           
unsigned int seed;
                                                                                                                 
void main (void)               
{                                                                                                                         
INIT();
PORTB= 0b11110111;
while(1)
{
Random();
}               
}


/*********************************************************************************/
void Random(void)
{
unsigned int i, help,help1;

for (i=0;i<500;i++)
{   
srand(i); // Set the starting seed for rand()
help = rand()/4096; // 0...7
help1= ldexp(1,help);         // 1*2^help
PORTA= help1; // Ausgabe PortA
Delay10KTCYx(20); // bei 8Mhz = 100msec
}
}

                                                                                                                 
/*********************************************************************************/                                                                                                                           
void INIT(void)
{   TRISA = 0; // Port A Ausgang
PORTA = 0; // Alle LED aus
TRISB = 0; // Port B Ausgang
PORTB = 0;                      // Eingang B.0 auf Minus                                                                         
OSCCON = 0x72; // 0x72 "01110010" = 8 MHz, 0x62 "01100010" = 4 MHz                                 
while(!OSCCONbits.IOFS); // Wait for OSC to become stable                         
seed=0;
}

Danke
Martin

[Lux]

Ich kann es nur aus der stdio.h aus Windows ableiten und kann dir daher sagen, der "Fehler" ist, dass die Funktion rand nur pseudo Zufallszahlen liefert, was aber anhängig davon ist welchen Startwert du ihr gibst. Man löst das Problem z.B. auf dem PC, indem man beim Programmstart der Funktion die Uhrzeit übergibt (diese ist immer unterschiedlich) und somit bekommt man halbwegs Zufallszahlen).

Bei dir ist das aber immer gleich (i), daher die Regelmäßigkeit. Einen Zufall generieren könntest du z.B. indem du zum Programmstart eine Endlos for-Schleife laufen lässt, welche nur verlassen wird wenn der User eine Taste drückt z.B., der aktuelle Laufwert der for Schleife ist dann der Startwert für die srand, dann würde dein Problem auch gelöst sein. Aber beachten musst du trotzdem, dass dies keine wirklichen Zufallszahlen sind, denn dahinter steckt auch nur ein Algorithmus! Oftmals ist es auch so, dass die ersten 10-20 generierten Zahlen "Schrott" sind - man lässt sie erstmal unter den Tisch fallen und nimmt spätere Werte.

Ich hoffe ich konnte ein wenig helfen =)

Gruß Nico

[Rising]

Hallo,

nur so ne Idee, wie wäre es wenn Du den ADC startest und ein wert abließt, ich meine der ist ja ziemlich hochohmig und wird irgendwas wirres bringen.

Wenn das nicht klappt vllt ein OP als impedanzwandler mit offenem Eingang am ADC, der wird garantiert schwingen

wie gesagt nur eine Idee


Gruß
rising

[martinidry]

Hallo Nico und rising,

danke für eure Antworten.
Nach wie vor ist mir das Verhalten nicht klar. Microchip beschreibt, man möge srand(seed)vor rand() aufrufen und zwar mit unterschiedlichem seed um nicht die gleichen random Werte zu erhalten. Mit meiner Schleife füttere ich srand (i) jeweils mit unterschiedlicehn Werten, da i sich bei jedem Schleifendurchlauf erhöht. Also erwarte ich eigentlich die pseudo random zahlen. Erst nach 500 Durchläufen hatte ich ein gleiches Muster erwartet. Tatsächlich erfolgt das aber schon nach ca. 12-14 LED Anzeigen. Das sich wiederholende Muster sieht ca. so aus:
00000001
00010000
00000001
00100000
00000010
00100000
00000100
01000000
00001000
10000000
00010000
10000000
dann gehts wieder von vorne los.
Eure Vorschläge, seed mit möglichst willkürlichen Werten zu füttern habe ich aufgegriffen und mir eine Variable kreiert, die via Timer0 Interrupt alle 1 msec erhöht wird. Wenn ich mit dieser variablen srand() füttere, scheint das Muster willkürlicher, leider geht dann irgendwas mit den Zeiten in die Hose: die LED leuchten nicht mehr konstant 100 msec, sondern unterschiedlich lange und zum Teil deutlich länger als die programmierten 100 msec. Aber letztlich auch verständlich, schließlich wird innerhalb der 100msec Zeitschleife der Interrupt 100x aufgerufen und verlängert diese...
Die Idee, den unbeschalteten ADC als random Quelle zu nutzen mag zwar erfolgversprechend sein, ich hätte aber trotzdem gern gewusst, ab der Pseudo ranndom generator von Microchip für meinen Anwendungsfall nicht geeignet ist und wenn ja warum nicht, oder ob ein Programmierfehler vorliegt.

[Stampede]

Hi,

das ist aus der Helper.c des TCPIP Stacks:

Code:

// Default Random Number Generator seed. 0x41FE9F9E corresponds to calling LFSRSeedRand(1)
static DWORD dwLFSRRandSeed = 0x41FE9F9E;

/*****************************************************************************
  Function:
DWORD LFSRSeedRand(DWORD dwSeed)

  Summary:
Seeds the LFSR random number generator invoked by the LFSRRand() function. 
The prior seed is returned.

  Description:
Seeds the LFSR random number generator invoked by the LFSRRand() function. 
The prior seed is returned.

  Precondition:
None

  Parameters:
wSeed - The new 32-bit seed value to assign to the LFSR.

  Returns:
  The last seed in use.  This can be saved and restored by a subsequent call
to LFSRSeedRand() if you wish to use LFSRRand() in multiple contexts
without disrupting the random number sequence from the alternative
context.  For example, if App 1 needs a given sequence of random numbers
to perform a test, if you save and restore the seed in App 2, it is
possible for App 2 to not disrupt the random number sequence provided to
App 1, even if the number of times App 2 calls LFSRRand() varies.
 
  Side Effects:
None

  Remarks:
Upon initial power up, the internal seed is initialized to 0x1.  Using a
dwSeed value of 0x0 will return the same sequence of random numbers as
using the seed of 0x1.
  ***************************************************************************/
DWORD LFSRSeedRand(DWORD dwSeed)
{
DWORD dwOldSeed;
BYTE i;

// Save original seed to be returned later
dwOldSeed = dwLFSRRandSeed;

// Ensure zero isn't selected as a seed value, this would result in all
// 0x0000 output values from the LFSR
if(dwSeed == 0u)
dwSeed = 1;

// Set the new seed
dwLFSRRandSeed = dwSeed;

// Run the LFSR a few times to get rid of obvious start up artifacts for
// seed values that don't have many set bits.
for(i = 0; i < 16; i++)
LFSRRand();

// Return saved old seed
return dwOldSeed;
}

/*****************************************************************************
  Function:
WORD LFSRRand(void)

  Summary:
Returns a pseudo-random 16-bit unsigned integer in the range from 0
to 65535 (0x0000 to 0xFFFF).

  Description:
Returns a pseudo-random 16-bit unsigned integer in the range from 0
to 65535 (0x0000 to 0xFFFF).  The random number is generated using a
Linear Feedback Shift Register (LFSR) type pseudo-random number generator
algorithm.  The LFSR can be seeded by calling the LFSRSeedRand() function
to generate the same sequence of random numbers as a prior string of calls.

The internal LFSR will repeat after 2^32-1 iterations.

  Precondition:
None

  Parameters:
None

  Returns:
  Random 16-bit unsigned integer.
 
  Side Effects:
The internal LFSR seed is updated so that the next call to LFSRRand()
will return a different random number.

  Remarks:
None
  ***************************************************************************/
WORD LFSRRand(void)
{
BYTE i;

// Taps: 32 31 29 1
// Characteristic polynomial: x^32 + x^31 + x^29 + x + 1
// Repeat 15 times to make the shift pattern less obvious
for(i = 0; i < 15; i++)
dwLFSRRandSeed = (dwLFSRRandSeed >> 1) ^ ((0ul - (dwLFSRRandSeed & 1ul)) & 0xD0000001ul);

// Return 16-bits as pseudo-random number
return (WORD)dwLFSRRandSeed;
}


/*****************************************************************************
  Function:
DWORD GenerateRandomDWORD(void)

  Summary:
Generates a random DWORD.

  Description:
This function generates a random 32-bit integer.  It collects
randomness by comparing the A/D converter's internal R/C oscillator
clock with our main system clock.  By passing collected entropy to the
LFSRSeedRand()/LFSRRand() functions, the output is normalized (deskewed)
in the hopes of meeting statistical randomness tests.

  Precondition:
None

  Parameters:
None

  Returns:
  Random 32-bit number.
 
  Side Effects:
This function uses the A/D converter (and so you must disable
interrupts if you use the A/D converted in your ISR).  The LFSRRand()
function will be reseeded, and Timer0 (PIC18) and Timer1 (PIC24,
dsPIC, and PIC32) will be used.  TMR#H:TMR#L will have a new value.
Note that this is the same timer used by the Tick module.

  Remarks:
This function times out after 1 second of attempting to generate the
random DWORD.  In such a case, the output may not be truly random. 
Typically, this function executes in around 500,000 instruction cycles.

The intent of this function is to produce statistically random and
cryptographically secure random number.  Whether or not this is true on
all (or any) devices/voltages/temperatures is not tested.
  ***************************************************************************/
DWORD GenerateRandomDWORD(void)
{
BYTE vBitCount;
WORD w, wTime, wLastValue;
DWORD dwTotalTime;
union
{
DWORD dw;
WORD w[2];
} randomResult;

#if defined __18CXX
{
BYTE ADCON0Save, ADCON2Save;
BYTE T0CONSave, TMR0HSave, TMR0LSave;

// Save hardware SFRs
ADCON0Save = ADCON0;
ADCON2Save = ADCON2;
T0CONSave = T0CON;
TMR0LSave = TMR0L;
TMR0HSave = TMR0H;

// Set up Timer and A/D converter module
ADCON0 = 0x01; // Turn on the A/D module
ADCON2 = 0x3F; // 20 Tad acquisition, Frc A/D clock used for conversion
T0CON = 0x88; // TMR0ON = 1, no prescalar
vBitCount = 0;
dwTotalTime = 0;
wLastValue = 0;
randomResult.dw = LFSRRand();
while(1)
{
// Time the duration of an A/D acquisition and conversion
TMR0H = 0x00;
TMR0L = 0x00;
ADCON0bits.GO = 1;
ClrWdt();
while(ADCON0bits.GO);
((BYTE*)&wTime)[0] = TMR0L;
((BYTE*)&wTime)[1] = TMR0H;
w = LFSRRand();

// Wait no longer than 1 second obtaining entropy
dwTotalTime += wTime;
if(dwTotalTime >= GetInstructionClock())
{
randomResult.w[0] ^= LFSRRand();
randomResult.w[1] ^= LFSRRand();
break;
}

// Keep sampling if minimal entropy was likely obtained this round
if(wLastValue == wTime)
continue;

// Add this entropy into the pseudo random number generator by reseeding
LFSRSeedRand(w + (wLastValue - wTime));
wLastValue = wTime;

// Accumulate at least 32 bits of randomness over time
randomResult.dw <<= 1;
if(LFSRRand() & 0x0080)
randomResult.w[0] |= 0x1;

// See if we've collected a fair amount of entropy and can quit early
if(++vBitCount == 0u)
break;
}

// Restore hardware SFRs
ADCON0 = ADCON0Save;
ADCON2 = ADCON2Save;
TMR0H = TMR0HSave;
TMR0L = TMR0LSave;
T0CON = T0CONSave;
}
#else
{
WORD AD1CON1Save, AD1CON2Save, AD1CON3Save;
WORD T1CONSave, PR1Save;

// Save hardware SFRs
AD1CON1Save = AD1CON1;
AD1CON2Save = AD1CON2;
AD1CON3Save = AD1CON3;
T1CONSave = T1CON;
PR1Save = PR1;

// Set up Timer and A/D converter module
AD1CON1 = 0x0000; // Turn off the ADC so we can write to it
AD1CON3 = 0x9F00; // Frc A/D clock, 31 Tad acquisition
AD1CON2 = 0x003F; // Interrupt after every 16th sample/convert
AD1CON1 = 0x80E4; // Turn on the A/D module, auto-convert
T1CON = 0x8000; // TON = 1, no prescalar
PR1 = 0xFFFF; // Don't clear timer early
vBitCount = 0;
dwTotalTime = 0;
wLastValue = 0;
randomResult.dw = LFSRRand();
while(1)
{
ClrWdt();
#if defined(__C30__)
while(!IFS0bits.AD1IF);
#else
while(!IFS1bits.AD1IF);
#endif
wTime = TMR1;
TMR1 = 0x0000;

#if defined(__C30__)
IFS0bits.AD1IF = 0;
#else
IFS1CLR = _IFS1_AD1IF_MASK;
#endif
w = LFSRRand();

// Wait no longer than 1 second obtaining entropy
dwTotalTime += wTime;
if(dwTotalTime >= GetInstructionClock())
{
randomResult.w[0] ^= LFSRRand();
randomResult.w[1] ^= LFSRRand();
break;
}

// Keep sampling if minimal entropy was likely obtained this round
if(wLastValue == wTime)
continue;

// Add this entropy into the pseudo random number generator by reseeding
LFSRSeedRand(w + (wLastValue - wTime));
wLastValue = wTime;

// Accumulate at least 32 bits of randomness over time
randomResult.dw <<= 1;
if(LFSRRand() & 0x0080)
randomResult.w[0] |= 0x1;

// See if we've collected a fair amount of entropy and can quit early
if(++vBitCount == 0u)
break;
}


// Restore hardware SFRs
AD1CON1 = 0x0000; // Turn off the ADC so we can write to it
AD1CON3 = AD1CON3Save;
AD1CON2 = AD1CON2Save;
AD1CON1 = AD1CON1Save;
T1CON = T1CONSave;
PR1 = PR1Save;
}
#endif

return randomResult.dw;
}

Sollte recht zufällig sein. Jedoch auch incht der kürzeste Code.

Gruß
Stefan