Använda en slumptalsgenerator i Arduino: Random och RandomSeed funktioner. Arduino Course - Tid och slumpmässigt Arduino genererar en slumpmässig bitsekvens

När du programmerar Arduino, finns det tillfällen då du behöver få ett nummer som inte kommer att vara känt i förväg, varken för programmeraren som skriver skissen eller för användaren som ska använda Arduino med ett sådant program. I det här fallet kommer en slumpmässig (eller snarare pseudo-slumpmässig) nummergenerator till undsättning.

För att aktivera denna generator, använd bara funktionerna random() eller randomSeed(). Det här materialet kommer att visa dig hur du arbetar med dessa funktioner, samt hur du blir av med pseudo-slumpmässighet när du genererar siffror.

I allmänhet simulerar en pseudoslumptalsgenerator det kaotiska eller slumpmässiga utseendet av siffror, men i själva verket, om du analyserar en serie av dessa siffror under en tillräckligt lång period, kan du märka ett visst mönster.

Så slumpfunktionen för att generera pseudoslumptal kan ha upp till två parametrar och skrivs som slumpmässig(max) eller slumpmässig(min, max). Här max parameter, som är obligatoriskt, anger den övre gränsen för intervallet för generering av pseudoslumptal. Genom att använda ytterligare parameter min kan du ställa in den nedre gränsen för intervallet. Som ett resultat kommer funktionen att returnera något pseudoslumptal i intervallet från min till max-1.

Det är viktigt att förstå att när du använder funktionen random() kommer exakt samma lista med pseudoslumptal att genereras varje gång. Till exempel, om du gör en spelautomat och första gången du trycker på handtaget visar den en vinnande kombination, då kan du vara säker på att om du återställer Arduino och trycker på handtaget igen, kommer den spelautomaten att visa samma vinnande kombination . Det är faktiskt inte lätt att implementera en spelmaskin med helt slumpmässig siffergenerering på Arduino, som till exempel är implementerad i spelmaskiner www.igrovye-apparati-vulcan.com/, men du kan delvis lösa problemet med randomSeed () funktion.

Den här funktionen tar ett värde (som ett heltal) och använder talet för att modifiera den slumpmässiga listan som genereras av funktionen random(). Du kan sätta randomSeed() i setup-funktionen och använda funktionen random() i en oändlig slinga. Men även då är haken att även om slumptalssekvensen kommer att vara annorlunda när du använder funktionen randomSeed() kommer den fortfarande att vara densamma varje gång skissen körs.

Den enda lösningen i det här fallet kan vara att använda analog kringutrustning (ADC) och motsvarande analogRead()-funktion. Om den analoga ingången inte är ansluten till någonting, det vill säga lämnas "hängande" i luften, kan du tack vare bruset på denna linje få verkligt slumpmässiga siffror. Sedan i inställningsinställningarna kan du skriva randomSeed(analogRead(A0)). Förutsatt att analog port A0 inte är ansluten någonstans.

Det har skrivits mycket om slumptalsgeneratorer, men nästan alltid när det kommer till implementering antyds (eller uttryckligen) att vi pratar om om x86/x64 och andra "vuxna" arkitekturer. Samtidigt är forum dedikerade till utvecklingen av enheter på mikrokontroller fulla av frågor "hur kan jag generera ett slumpmässigt nummer på %controllername%?" Dessutom sträcker sig utbudet av svar från "titta på Google/Wikipedia" till "använd standardfunktionen." Denna "standardfunktion" finns inte alltid och passar utvecklaren i alla avseenden; oftare är det tvärtom: ibland är siffrorna långt ifrån slumpmässiga, ibland är operationshastigheten för låg, eller ibland är den resulterande koden inte passa in i ledigt minne överhuvudtaget.
Låt oss försöka ta reda på vilka slumptalsgenereringsalgoritmer är, hur man väljer den rätta, och viktigast av allt, vad är funktionerna för att implementera dessa algoritmer på styrenheter.

Att bedöma "slumpmässighet"

Applikationerna för RNG kan vara väldigt olika, från leksaker till seriös kryptografi. Följaktligen varierar också kraven på generatorn mycket. Det finns speciella tester för att bedöma kvaliteten (nivån av "slumpmässighet") hos generatorn. Här är de mest grundläggande av dem:

• Frekvenstest. Består av att räkna antalet nollor och ettor i en sekvens av bitar. Det ska vara ungefär lika många ettor och nollor.
• Testa för en sekvens av identiska bitar. Rader med identiska bitar genomsöks, som 000...0 eller 111...1. Fördelningen av frekvenser med vilka serierna uppträder, beroende på deras längd, bör motsvara denna fördelning för en verkligt slumpmässig signal.
• Spektraltest. En diskret Fouriertransform appliceras på den ursprungliga sekvensen. Det resulterande spektrumet bör inte ha signifikanta toppar som skulle indikera närvaron av periodiska egenskaper hos sekvensen.
• Autokorrelationstest. Korrelationsvärdet mellan sekvenskopior skiftade i förhållande till varandra beräknas. Testet låter dig hitta återkommande regioner i en sekvens.

Det finns speciella kit som innehåller dussintals liknande tester:
NIST - används i AES-tävlingen för att utvärdera krypteringsalgoritmer.
DIEHARD är en av de mest rigorösa uppsättningarna som finns.

PRNG-algoritmer

Varje sekvens som genereras enligt en strikt definierad algoritm kan inte betraktas som verkligt slumpmässig, därför använder de termen när man talar om algoritmiska generatorer pseudoslump efterföljande. Alla pseudo-slumptalsgeneratorer (PRNG) kommer att gå i loop förr eller senare, den andra saken är att detta "sena" kan komma om några millisekunder, eller kanske om några år. Längden på cykeln beror på storleken på det interna tillståndet hos generatorn N (i själva verket är detta mängden minne som behövs av generatorn), och sträcker sig från 2 (N/2) till 2 N bitar.
En stor mängd PRNG-algoritmer har uppfunnits, men alla är inte lämpliga för implementering på mikrokontroller. Vi är kraftigt begränsade i hastighet och tillgängligt minne; många kontroller stöder inte riktiga aritmetiska eller ens multiplikationsinstruktioner. Med dessa begränsningar i åtanke, låt oss titta på några välkända algoritmer.

Linjär kongruent metod

Nästa medlem i sekvensen beräknas med formeln
X i+1 = (aX i + c) mod m
siffra m definierar den maximala perioden för sekvensen, heltal a Och c- "magiska" koefficienter. siffra m Det är rimligt att välja lika med en potens av två, i detta fall reduceras modulomvandlingsoperationen till att förkasta de mest signifikanta bitarna. För att erhålla den maximala perioden måste följande villkor vara uppfyllda:
- c och m måste vara relativt prime,
- a-1 måste vara en multipel sid för alla primära faktorer sid tal m,
- Om mär en multipel av 4 (och i vårt fall kommer det att vara en multipel), då a-1 måste vara en multipel av 4.
Det finns ytterligare en subtilitet: endast de mest signifikanta bitarna av tillståndsvariabeln X bör tas som resultat, eftersom de statistiska parametrarna för slumpmässighet är mycket sämre för de lägsta bitarna. Den linjära kongruenta algoritmen implementeras vanligtvis som standard rand() i många bibliotek.

Fördelar:

• den maximala möjliga perioden för en given storlek av tillståndsvariabeln;
• snabb nog;
• ofta redan implementerad i kompilatorbiblioteket.

Minus:

• en multiplikationsoperation krävs;
• inte alla bitar är lika slumpmässiga.

Sammanfattning: en snabb och enkel algoritm för inte särskilt krävande applikationer.

Fibonacci-metoden med lags

Denna algoritm använder relationen
Xi = Xi-a - Xi-b,
var är tillståndsvariabeln X- heltal utan tecken. Fördröjningsvärden a Och b inte vilka som helst utan strikt definierade tas, för att uppnå maximal kvalitet rekommenderas par (17,5), (55,24) eller (97,33). Ju större fördröjning, desto längre period och desto bättre spektrala egenskaper för sekvensen. Å andra sidan, för att generatorn ska fungera är det nödvändigt att lagra max(a,b) av tidigare nummer, vilket inte alltid är acceptabelt. För att köra generatorn behöver du också max(a,b)-tal, som vanligtvis erhålls med en enklare PRNG.

Fördelar:

• kräver inte multiplikationsoperationer;
• alla bitar av ett slumptal är ekvivalenta i statistiska egenskaper.

Minus:

• kräver en stor mängd minne;
• kräver ett stort antal nummer för att köras.

Sammanfattning: en mycket högkvalitativ men resurskrävande algoritm.

Linjär feedback skiftregister

Tillståndsvariabeln lagras i ett register med längden N. Att generera nästa tillstånd innebär två steg:

1. Bitens värde beräknas C = X i1 xor X i2 xor… X ik, där i1, i2…ik- registrera bitnummer, anropade böjer sig.
2. Registret förskjuts 1 bit åt höger, biten längst till vänster tar på sig värdet MED.

Utsignalen från generatorn är biten längst till höger (eller längst till vänster, eller vad som helst) i registret, det vill säga den pseudoslumpmässiga sekvensen genereras en bit per iteration. Med korrekt valda tappnummer kommer generatorns period att vara 2 N - 1. "Minus ett", eftersom det finns ett förbjudet nolltillstånd i registret. Filialnummer för N från 3 till 168 finns i detta dokument.
Utöver konfigurationen som beskrivs ovan, som för övrigt kallas Fibonacci-konfigurationen (inte att förväxla med PRNG-metoden med samma namn!), finns den så kallade. Galois-konfiguration.


Istället för att använda summan av bitarna i tappsekvensen för att generera en ny bit längst till vänster, XELLER den varje bit i tappsekvensen med biten längst till höger och roterar sedan hela registret åt höger. Detta schema är svårare att förstå, men lättare att implementera, eftersom alla XOR-operationer kan utföras samtidigt. När det gäller periodlängd och kvalitet på pseudoslumptal är Fibonacci- och Galois-scheman likvärdiga.

Fördelar:

• mycket enkel implementering, kräver inte ens aritmetik, bara bitoperationer och skiftningar;
• mycket snabb algoritm (särskilt Galois-schemat);
• goda statistiska egenskaper.

Minus:

• du måste kontrollera initialvärdet för olikhet till noll.

Sammanfattning: mycket snabb och ganska högkvalitativ algoritm.

Kryptosäkra algoritmer

För användning i kryptografi har PRNG:er ytterligare ett väsentligt krav: irreversibilitet. Alla algoritmer som listas ovan har inte denna egenskap: genom att känna till flera utdatavärden för PRNG kan du, genom att lösa ett enkelt ekvationssystem, hitta parametrarna för algoritmen (samma "magiska" konstanter a, b, c etc). Och genom att känna till parametrarna kan du reproducera hela pseudo-slumpmässiga sekvensen.
Varje tillräckligt starkt blockchiffer kan användas som en kryptografiskt stark PRNG-algoritm. Genom att välja en hemlig nyckel kan du få block med pseudoslumptal genom att tillämpa algoritmen på naturliga sekventiella tal. För ett N-bitars blockchiffer kommer perioden inte att vara mer än 2 N. Säkerheten för ett sådant system beror helt på nyckelns hemlighet.
Alla moderna kryptografiska algoritmer testas för användning som PRNG, det vill säga med en certifierad algoritm, det finns inget behov av att särskilt bry sig om de statistiska och spektrala egenskaperna hos utströmmen. Du behöver bara oroa dig för den beräkningsmässiga "frossigheten" hos kryptoalgoritmer. Om du behöver utföra ett stort antal krypteringsoperationer är det vettigt att välja en styrenhet med hårdvarukrypteringsblock. Ofta har sådana kontroller också en mycket bra kryptoresistent hårdvara PRNG.

Källor till entropi

Som redan nämnts, med endast deterministiska algoritmer, är det omöjligt att generera ett verkligt slumptal. Därför används vanligtvis en kombination av PRNG + extern källa till entropi. Entropikällan används för att ställa in det initiala värdet för PRNG, och den senares uppgift är att säkerställa sekvensens spektrala och statistiska renhet. Vad kan användas som en källa till entropi? Ja, nästan vad som helst.

Användaraktivitet

Om enheten interagerar med användaren på något sätt, helt enkelt bra beslut kommer att använda användaren själv som en källa till entropi. Till exempel är tiden för att trycka på en knapp, mätt med en noggrannhet på en mikrosekund (eller snarare, dess minst signifikanta siffror), helt oförutsägbar. Men ofta måste enheten fungera autonomt, vilket innebär att vi är berövade denna underbara informationskanal.

Analog-till-digital-omvandlare

Många kontroller har inbyggda ADC:er. Och i många kontroller är de av mycket medelmåttig kvalitet, gjorda bara för att vara. De låga ordningens bitar av ADC-resultatet innehåller nästan alltid betydande brus, även vid mätning av DC-spänning. Detta kan användas: anslut ADC-ingången till matningsspänningen genom en delare, ta några dussin mätningar, ta de minst signifikanta bitarna - här har du ett stort slumptal. Om ADC:n innehåller en inbyggd förförstärkare, slå på den, den är också bullrig.

Asynkrona generatorer

Du kan använda skillnaden i perioder för två osynkroniserade klockgeneratorer. De flesta kontroller innehåller till exempel en watchdog-timer. För att öka tillförlitligheten klockas den från en separat generator, som inte på något sätt är kopplad till huvudklocksignalen. Det räcker med att räkna antalet cykler av huvudklocksignalen under en period av watchdog-timern. Väljer man perioder så att räknaren svämmar över många gånger under mätningen kan man få ett ganska slumpmässigt tal. Nackdelen med denna metod är att den tar mycket tid, upp till flera sekunder.

Riktig tids klocka

Om diagrammet har riktig tids klocka, kan du använda deras nuvarande avläsningar för att initiera PRNG. Till exempel, genom att konvertera aktuellt datum/tid till Unix-tidsformatet får vi omedelbart 32 bitar, vilket aldrig kommer inte att hända igen om du inte gör avläsningar mer än en gång per sekund. Att använda realtid ger unika värden, men ger ingen oförutsägbarhet, så det är bättre att kombinera den här metoden med andra.

RC-krets

Om styrenheten har nr kringutrustning, förutom I/O-portarna kan du göra följande: ett av benen är anslutet via en kondensator till jord och genom ett motstånd till matningsspänningen. Om regulatorns ingångar har interna pull-up-motstånd behövs inget externt motstånd.

Vi matar ut en "0"-signal till denna port - kondensatorn är urladdad. Vi byter porten till ingångsläge - kondensatorn börjar laddas. När spänningen över den når tröskeln kommer ingången att växla från tillstånd "0" till "1". Laddningstiden beror starkt på många faktorer: matningsspänning, drift av RC-kretsparametrar, tröskelinstabilitet, temperatur, läckor, störningar. Genom att mäta det med tillräcklig noggrannhet och ta de minst signifikanta bitarna kan du få bra slumpmässighet.

Hårdvara brusgenerator

För många seriösa tillämpningar (främst kryptografi) krävs en mer tillförlitlig entropikälla än de som anges ovan. I sådana fall använder de digitalisering av signalen från en brusgenerator baserat på termiska, skott- eller till och med kvanteffekter. Bruselementet är vanligtvis en speciell diod eller zenerdiod, vars signal förstärks och matas till en komparator som genererar en binär bitström.

För att säkerställa att komparatorns svarströskel inte påverkar den mottagna signalens statistiska egenskaper, används två brusgeneratorer som arbetar på en komparator:

Slutsats

Till sist ska jag berätta en historia från mitt liv. Det började med en annan fråga som ställdes på forumet: "hur kan jag generera ett slumpmässigt nummer på styrenheten?" Frågans författare förklarade att han som ett kursprojekt gör en apparat som emulerar att kasta tärningar. Efter flera misslyckade försök att förstå algoritmerna, delade ämnesstartaren sin lösning: han slog helt enkelt en riktig tärning 1000 gånger och fyllde hela det lediga minnet hos kontrollern med de resulterande siffrorna. Generatorn klarade briljant alla "slumpmässighet"-test, med tanke på att den under demonstrationen använde mindre än en tredjedel av sin "reserv".
Därför har en sådan lösning också rätt till liv, särskilt om det ställs mycket stränga krav på slumpmässighet i siffror, men de krävs inte för ofta. Med minnespriserna rasande kan det vara klokt att utrusta en enhet med en "kaosreserv" som kommer att hålla hela enhetens livstid.
Tack för uppmärksamheten!

UPD1: Som det med rätta noterades i kommentarerna, om en attack på RNG förväntas, och angriparen har hårdvaruåtkomst till enheten, måste externa entropikällor användas med stor försiktighet, eftersom det inte är särskilt svårt att ersätta signalen från extern källa. Interna källor bör användas, förutom externa.
Det är också en bra idé att samla entropi allt fritid, och använd den när du behöver generera ett annat slumptal. Vanligtvis i sådana fall den sk Entropi pool- en array över vilken en av PRNG-funktionerna utförs periodiskt och i vilken data från entropikällor ständigt blandas in.

UPD2: I många fall är det användbart att spara innehållet i Entropy-poolen (tyvärr, jag kan inte den normala ryska översättningen) i EEPROM så att den inte ackumuleras igen efter att ha stängt av och på enheten. Detta hänför sig först och främst till att erhålla entropi genom att använda metoden för asynkrona generatorer: under tillräckligt stabila förhållanden kan samma sekvens genereras efter varje påslagning.
Om en attack förväntas, vidta försiktighetsåtgärder mot EEPROM-manipulation. Om styrenheten tillåter det, blockera läsning/radering/skrivning med låsbitar, och när du slår på den, övervaka integriteten hos EEPROM, åtminstone med enkla kontrollsummor.

Taggar:

• RNG
• gpsch
• mikrokontroller
• algoritmer

Lägg till taggar

randomSeed (frö)

Ställer in värdet, eller seed, som startpunkt för funktionen random().

randomSeed(värde); // ställer in 'värde' som det initiala slumpmässiga värdet

Eftersom Arduino inte kan generera riktigt slumpmässiga tal, låter randomSeed dig lägga in en variabel, konstant eller annan funktion i slumpfunktionen, vilket hjälper till att generera fler slumpmässiga tal.

"slumpmässiga" siffror. Det finns många olika frön, eller funktioner, som kan användas i den här funktionen, inklusive millis(), eller till och med analogRead() för att läsa elektriskt brus genom ett analogt stift.

slumpmässigt (max)

slumpmässigt (min, max)

Slumpfunktionen låter dig returnera ett pseudoslumptal inom det intervall som anges av min- och maxvärdena.

värde = slumpmässigt(100, 200); // sätter 'värde' till slumpmässigt

// ett tal mellan 100 och 200

Notera: Använd detta efter att ha använt funktionen randomSeed(). Följande exempel skapar ett slumptal mellan 0 och 255 och matar ut PWM

signal till PWM-utgången lika med ett slumpmässigt värde:

int randNumber; // variabel för att lagra ett slumpmässigt värde

int led = 10; // LED med motstånd på stift 10

void setup() () // setup behövs inte

randomSeed(millis()); // sätter millis() med det initiala numret

randomNumber = random(255); // slumptal från 0 – 255 analogWrite (led, randNumber); // ut PWM-signal

fördröjning(500); // pausa i en halv sekund

Källa: Gololobov V. – Var börjar robotar. Om Arduino-projektet för skolbarn (och inte bara) – 2011

relaterade inlägg

Serial.begin (hastighet) Öppnar serieporten och ställer in hastigheten för seriell dataöverföring. Den typiska baudhastigheten för datorkommunikation är 9600, även om andra hastigheter stöds. void setup() (Serial.begin…….

Alla variabler måste deklareras innan de kan användas. Att deklarera en variabel innebär att definiera typen av dess värde: int, long, float, etc., att tilldela variabeln ett unikt namn och dessutom…….

Okej, vi har installerat det här programmet. Vi har felsökt "mekanismen" för att arbeta med modulen. Och vi tittade på flera exempel. Men jag skulle vilja skapa något användbart själv. Låt oss försöka. Låt oss först avsluta det föregående projektet. För detta…….

Uppmärksamhet! När du arbetar med Arduino-modulen i andra utvecklingsmiljöer bör du vara försiktig med mikrokontrollerns konfiguration (säkringar). Tills du vet exakt vad förändringen kan leda till…….

Tid och slumpmässighet. Reaktion

Den här gången ska vi lära oss vad "Slumpmässiga" värden är och även lära oss hur man arbetar med tid.

Vi kommer att behöva:

• Taktknapp
• Squeaker
• Anslutningsledningar "MALE-MALE"

Reaktion

Vår uppgift för idag är att sammanställa ett diagram som låter oss ta reda på hastigheten på vår reaktion.

När du klickar på vänster knapp, ljuder en signal efter en "slumpmässig" tid. Och när man trycker på höger knapp noteras det hur lång tid som har gått från gnisslet till att man tryckt på höger knapp.

De som är skickliga provar själva, och vi tittar på diagrammet.

#define BUZ 8 #define START 9 #define STOP 7 int time; //Variabel för synkronisering void setup() ( Serial. begin(9600); pinMode(START, INPUT_PULLUP); pinMode(STOP, INPUT_PULLUP); pinMode(BUZ, OUTPUT); ) void loop() ( if(digitalRead(START) == 0) // När du trycker på START-knappen.. ( int start_time = millis(); // Kom ihåg tiden för tryckning time = start_time; // Skriv det till en global variabel. int Rand = random(0, 4000) ); // Låt oss generera en "slumpmässig" fördröjningstid = tid + Rand; //Lägg till fördröjningstidsfördröjningen(Rand); //Vänta på ton(BUZ, 3000, 500); //Beep! ) if(digitalRead( STOP) == 0 && digitalRead( START) == 1) // När du trycker på STOP-knappen... ( int stop_time = millis(); // Kom ihåg stopptiden. time = stop_time - time; // Beräkna tidsskillnad. Serial.println("Tid: "); // Mata ut tiden till Serial. Serial.println(tid); delay(1000); ) ) // Innan det andra försöket, tryck på START-knappen igen.

Förklaringar

int tid; Variabler (inte alla), när de betecknas, behöver inte ges något värde. Vi använde denna variabel för att länka två if-satser.

I C++ kommer variabler som deklareras inuti en loop inte att vara tillgängliga i andra loopar, eftersom de bara har effekt inom den loopen. Detta görs för att förhindra programmeringsfel. När programkoden växer kommer du att förstå vad jag pratar om.

För att göra en variabel tillgänglig för flera påståenden måste du göra den global. De där. deklarera en variabel utanför funktioner.

millis(); Returnerar antalet millisekunder som har gått sedan programmet startades.

Vi behöver det för att kunna mäta hur lång tid som har gått från signalen gavs tills knappen trycktes ned.

slumpmässig(min,max); Detta är en slumptalsgenerator. Tar två värden. Den genererar ett tal i intervallet från min till max.

"Slumpmässiga" tal eftersom de är en specifik sekvens av värden. Väldigt lång, men likadan. För att få olika sekvenser bör du använda SlumpmässigUtsäde();

Denna funktion initierar generatorn. Och om vi ställer in parametern till slumpmässigt kommer vi att få de sekvenser vi behöver. Sekvensen blir densamma om parametern är fixerad.

Slutsats

Nu kan du träna din reaktion med hjälp av en enhet du själv har gjort. Eller så kan du fortsätta studera vidare.

Lista över radioelement

Beteckning	Typ	Valör	Kvantitet	Notera	affär	Mitt anteckningsblock
	Arduino-bräda	Arduino Uno	1			Till anteckningsblock
	Brödbräda	Brödbräda-halva	1			Till anteckningsblock
	Piezo emitter	Passiv	1			Till anteckningsblock
	Taktknapp	Utan lås	2			Till anteckningsblock
	Anslutningsledningar	"pappa-pappa"	1