Zufallsgenerator

[Ozzy]

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

[Madgyver]

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.

[Ozzy]

Hi,

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

MfG, Ozzy

[Madgyver]

Im moment nicht, könnte etwas dauern, da ich gerade Vordiplom habe.

[robocat]

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:

  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

[Madgyver]

Will nicht nörgeln, aber ich dachte er wollte einen Assembler code?

[robocat]

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

[Ozzy]

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

[JanB]

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

[SprinterSB]

@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

#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).

	.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])*.