-         

Ergebnis 1 bis 10 von 10

Thema: Zufallsgenerator

  1. #1
    Erfahrener Benutzer Begeisterter Techniker
    Registriert seit
    20.03.2005
    Ort
    Lübeck
    Beiträge
    315

    Zufallsgenerator

    Anzeige

    Hi,

    ich möchte einen Zufallsgenerator bauen, der in einem Register eine Zahl bekommt (1-8), und die dann auf einem Port mit LED's ausgibt. Die Pins sollen dann eben "zufällig" ausgewählt werden. Also z.B. bei einer 5: "01101011" oder "11101010". Hat da von Euch einer eine Idee zu?

    MfG, Ozzy

  2. #2
    Erfahrener Benutzer Roboter Genie
    Registriert seit
    15.07.2004
    Alter
    32
    Beiträge
    807
    Echten Zufall kriegt man wohl nicht so einfach hin (Softwaremässig sowieso nicht)

    Also hilft da nur Pseuderandom.

    Schau dir mal diesen Artikel bei Wiki an:
    http://de.wikipedia.org/wiki/Zufallszahlengenerator

    Was du willst wäre wohl der periodische Generator. Du definierst dir eine Startzahl und speicherst sie in eine Register ab (zb R16) und führst dann den Algo aus (bzw. rechnest due Formel aus) der dann die Zahl in R16 überschreibt. Wenn man dann den Algo nochmal ausführt, dann steht da eine andere Zahl und dann noch eine. Die Zufallszahl kann dann per Timer oder so immer wieder aufgerufen werden.

  3. #3
    Erfahrener Benutzer Begeisterter Techniker
    Registriert seit
    20.03.2005
    Ort
    Lübeck
    Beiträge
    315
    Hi,

    hättest Du denn auch etwas Code für mich?`

    MfG, Ozzy

  4. #4
    Erfahrener Benutzer Roboter Genie
    Registriert seit
    15.07.2004
    Alter
    32
    Beiträge
    807
    Im moment nicht, könnte etwas dauern, da ich gerade Vordiplom habe.

  5. #5
    Erfahrener Benutzer Roboter Genie Avatar von robocat
    Registriert seit
    18.07.2006
    Beiträge
    935
    jemand hat mal geschrieben, dass der nicht beschriebene speicher des controllers reichlich zufällig ist, und sogar wechselt bei jedem reset. ich habe es nicht selbst getestet, aber das wäre eine möglichkeit.
    oder du liest den status eines flatternden ports, oder einen wert an einem schnell-schwingendemn eingang eines analogport.
    code habe ich leider auch grad keinen.
    ah doch, hab da was:
    Code:
      function IntNoise(32-bit integer: x) 
    
        x = (x<<13) ^ x;
        return ( 1.0 - ( (x * (x * x * 15731 + 789221) + 1376312589) & 7fffffff) / 1073741824.0);    
    
      end IntNoise function
    musst natürlich anpassen, aber erzeugt pseudo-zufällige zahlen.

    gruesse

  6. #6
    Erfahrener Benutzer Roboter Genie
    Registriert seit
    15.07.2004
    Alter
    32
    Beiträge
    807
    Will nicht nörgeln, aber ich dachte er wollte einen Assembler code?

  7. #7
    Erfahrener Benutzer Roboter Genie Avatar von robocat
    Registriert seit
    18.07.2006
    Beiträge
    935
    ja, aber in asm habe ich nix gefunden hier. 32bit asm code würde ihm auch nix helfen, wenn er einen atmega benutzt (das weiss ich nicht). deshalb habe ich nur pseudo-op-code gepostet, und gehofft, er kann es "irgendwie" umsetzen.

    gruesse

  8. #8
    Erfahrener Benutzer Begeisterter Techniker
    Registriert seit
    20.03.2005
    Ort
    Lübeck
    Beiträge
    315
    Hi,

    ne, also das kann ich nicht "irgendwie" umsetzen... Wenn jeder Compiler die Programme in Assembler übersetzt, dann muss sich doch theoretisch was finden...

    MfG, Ozzy

  9. #9
    Erfahrener Benutzer Roboter Experte
    Registriert seit
    10.12.2004
    Ort
    LEV
    Beiträge
    505
    Hallo,
    schau doch mal in den angegebenen WIKI-Artikel.
    Dort wird das rückgekoppelte Schieberegister beschrieben.
    Das lässt sich doch wirklich leicht in ASM umsetzen.

    Gruß Jan

  10. #10
    Erfahrener Benutzer Robotik Einstein Avatar von SprinterSB
    Registriert seit
    09.06.2005
    Ort
    An der Saar
    Beiträge
    2.801
    @Ozzy: Ich antworte mal hier, vielleicht kann ja sonst noch wer was damit anfangen...

    Was meinst du mit "auf verschiedene Pins ausgeben? Sind doch immer die gleichen...

    Zunächst mal mein C-File, da ist manches besser nachzuvollziehen, auch für Assembler-Progger, die kein C können

    Code:
    #include <avr/io.h>
    #include "parit-15.h"
    
    #define POLY 0xe125 /* 1 + x^2 + x^5 + x^8 + x^13 + x^14 + x^15 */
    #define DEGREE 15
    #define ROOT 0x2200 /* x^9 + x^13 */
    
    typedef uint16_t poly;
    
    static uint16_t seed;
    static poly pprod (poly, poly);
    static poly ppow  (poly, poly);
    
    #define MASK(b) \
    	(((poly) 1) << (b))
    	
    /**
     * Berechnet a*b mod p
     */
    poly pprod (poly a, poly b)
    {
    	const poly mask = MASK (DEGREE);
    	poly c = 0;
    
    	while (b)
    	{
    		// Ist bit i in b gesetzt?
    		if (b & 1)
    			c ^= a;		// dann c = c + a * x^i
    		a <<= 1;		// a = a*x
    		
    		if (a & mask)	// a = a mod p
    			a ^= POLY;
    
    		b >>= 1;
    	}
    
    	return c;
    }
    
    
    void __attribute__ ((naked, section (".init3")))
    __init_seed()
    {
    	uint16_t s = 0;
    	uint16_t *p = (uint16_t*) (RAMEND+1);
    	extern uint16_t __noinit_start;
    	
    	while (p >= &__noinit_start + 1)
    		s ^= * (--p);
    	
    	seed = s;
    }
    
    // Liefert eine Pseudo-Zufallszahl x
    // mit 1 <= x <= 2^DEGREE-1 = 32767
    uint16_t prandom()
    {
    	return (uint16_t) (seed = pprod (seed, ROOT));
    }
    Hier das, was GCC draus macht. "Out of the Box" wirst du das nicht nutzen können, weil (i) benutzt du wohl kein GNU-Assembler und (ii) hast du bestimmt ne andere ABI (Registerverwendung etc) und wirst es in lesbareren Assembler hinschreiben wollen.

    __init_seed
    Als erstes wird __init_seed aufgerufen (Vorsicht, muss noch ein RET dazu). Sie berechnet aus dem uninitialisierten RAM-Inhalt eine seed, indem der RAM-Inhalt als 16-Bit-Werte interpretiert wird, die mit XOR "überlagert" werden. Das Ende des RAM war bei 1120 (=96+1024 = 0x60+0x400). Das RAM wird von hinten dach vorne durchpflügt.

    Evtl reicht dir schon, ne seed aus den (ebenfalls nicht initialisierten) GPRs zu besorgen: seed = R1:R0 xor R3:R2 xor ... xor R31:R30.

    Für die Anfangs-seed muss gelten 1 <= seed <= 32767

    prandom
    Besorgt eine weitere Zufallszahl x mit 1 <= x <= 32767 und aktualisiert seed. Am klarsten wird das im C-File.

    avr-gcc hat sich entschieden, pprod in prandom zu integrieren...aber egal. Magische Zahlen sind:
    8704 = ROOT
    -7899 = POLY

    Der 15-Bit-Rückgabewert wird in R25:R24 zurückgegeben.
    Zerstört werden die Inhalte von R18-R23, seed lebt im RAM und wird wie gesagt aktualisiert. __zero_reg__ ist hier R1 (es entält den Wert 0).



    pprod
    Die eigentliche, für den Pseudozufall verantwortliche Routine. Auf den mathematischen Hintergrund will ich nicht eingehen. (Entweder man raffts am Kommentar, oder versteht's auch mit Erklärung nicht tiefer).

    Code:
    	.file	"parit-15.c"
    	.arch atmega8
    __SREG__ = 0x3f
    __SP_H__ = 0x3e
    __SP_L__ = 0x3d
    __tmp_reg__ = 0
    __zero_reg__ = 1
    	.global __do_copy_data
    	.global __do_clear_bss
     ;  GNU C version 3.4.5 (avr)
    
    	.section	.init3,"ax",@progbits
    .global	__init_seed
    	.type	__init_seed, @function
    __init_seed:
    /* prologue: frame size=0 */
    /* prologue: naked */
    /* prologue end (size=0) */
    	ldi r18,lo8(0)	 ;  s,
    	ldi r19,hi8(0)	 ;  s,
    	ldi r30,lo8(1120)	 ;  p,
    	ldi r31,hi8(1120)	 ;  p,
    .L7:
    	ldi r24,hi8(__noinit_start+2)	 ; ,
    	cpi r30,lo8(__noinit_start+2)	 ;  p,
    	cpc r31,r24	 ;  p,
    	brlo .L6	 ; ,
    	ld r25,-Z	 ;  tmp43,
    	ld r24,-Z	 ;  tmp43,
    	eor r18,r24	 ;  s, tmp43
    	eor r19,r25	 ;  s, tmp43
    	rjmp .L7	 ; 
    .L6:
    	sts (seed)+1,r19	 ;  seed, s
    	sts seed,r18	 ;  seed, s
    /* epilogue: frame size=0 */
    /* epilogue: naked */
    /* epilogue end (size=0) */
    /* function __init_seed size 17 (17) */
    	.size	__init_seed, .-__init_seed
    	.text
    .global	prandom
    	.type	prandom, @function
    prandom:
    /* prologue: frame size=0 */
    /* prologue end (size=0) */
    	lds r18,seed	 ;  a, seed
    	lds r19,(seed)+1	 ;  a, seed
    	ldi r20,lo8(8704)	 ;  b,
    	ldi r21,hi8(8704)	 ;  b,
    	ldi r24,lo8(0)	 ;  c,
    	ldi r25,hi8(0)	 ;  c,
    	ldi r22,lo8(-7899)	 ;  tmp49,
    	ldi r23,hi8(-7899)	 ;  tmp49,
    .L13:
    	sbrs r20,0	 ;  b,
    	rjmp .L11	 ; 
    	eor r24,r18	 ;  c, a
    	eor r25,r19	 ;  c, a
    .L11:
    	lsl r18	 ;  a
    	rol r19	 ;  a
    	sbrs r19,7	 ;  a
    	rjmp .L12	 ; 
    	eor r18,r22	 ;  a, tmp49
    	eor r19,r23	 ;  a, tmp49
    .L12:
    	lsr r21	 ;  b
    	ror r20	 ;  b
    	cp r20,__zero_reg__	 ;  b
    	cpc r21,__zero_reg__	 ;  b
    	brne .L13	 ; ,
    	sts (seed)+1,r25	 ;  seed, c
    	sts seed,r24	 ;  seed, c
    /* epilogue: frame size=0 */
    	ret
    /* epilogue end (size=1) */
    /* function prandom size 30 (29) */
    	.size	prandom, .-prandom
    	.lcomm seed,2
    /* File "parit-15.c": code   47 = 0x002f (  46), prologues   0, epilogues   1 */
    Die Periode der Zahlen liegt bei 2^15-1 = 32767. Für gleiche seed wird auch die gleiche Folge erzeugt. Ein Zufallswert ist nur abhängig von der Anfangs-seed und der Anzahl der prandom-Aufrufe.

    Wenn du einen 8-Bit Zufallswert willst, dann schiebst du der Wert am besten um 2 Bits (oder so) nach rechts und wirfst den high-Teil weg. Der Wertebereich ist dann 0...255.

    Einen 8-Bit-Algorithmus zu implementieren ginge auch. Er wäre merklich knapper und schneller, hätte allerdings nur eine Periode von 127 (mit etwas Hirnschmalz auch 255). Du bräuchtest dann ein irreduzibles Polynom POLY vom Grad 8 über F2 sowie eine primitive Wurzel ROOT von (F2[x] mod r*F2[x])*.
    Disclaimer: none. Sue me.

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •