Fråga:
Vad är det minsta och enklaste fröet för en slumpgenerator?
vsz
2015-09-02 21:21:55 UTC
view on stackexchange narkive permalink

En liten mikrokontroller (8-bitars Atmel) styr ett antal lampor för att presentera en ljusshow med många snygga randomiserade ljussekvenser.

En lämplig pseudo-RNG gör sitt jobb snyggt, men jag letar efter ett bra frö för det. Ett frö kommer att vara nödvändigt, för om någon slår på flera sådana enheter samtidigt ser det inte bra ut om de alla genererade samma sekvenser av effekter förrän de sakta glider isär på grund av de små skillnaderna i deras individuella klockkällor. / p>

En mycket bra metod för att sådd en pseudo-RNG, som jag ofta använde, är möjlig i fall av en enhet som måste startas med ett knapptryck eller en omkopplare. Så snart µc slås på kan en mycket snabb timer startas och värdet på denna timer fröer RNG så snart knappen trycks in för första gången.

Problemet är, i i det här scenariot finns det inga knappar. Programmet måste starta så snart enheten är påslagen.

Platsen på kretskortet är extremt begränsad (inget mer än några av de allra minsta SMD-delarna kan passa ), så jag letar efter den minsta och enklaste möjliga lösningen. Därför utesluter jag snygga lösningar som äkta RNG-hårdvara, radiomottagare etc.

Allt jag har är en 16-bitars timer-räknare i CPU: n och en oanvänd portpin som har tillgång till en ADC.

Min nuvarande lösning är att bara använda ett motstånd (så felaktigt som möjligt) för att ge ungefär hälften av matningsspänningen till ADC-stiftet, och sådd RNG med det första AD-omvandlingsvärdet. Men nuförtiden har de flesta 10% motstånd en felaktighet under 1% (det skulle vara kul att föreställa sig en leverantörs ansikte när jag säger till dem att vi vill ha de värsta SMD-motstånden de kan hitta), så det finns mycket stor chans att flera enheter som börjar med samma utsäde.

Ett bättre alternativ skulle vara att göra flera omvandlingar och bygga ett värde av de minst betydande bitarna av dessa mätningar. Jag använde dock ADC av denna µc-typ tidigare och jag vet att den är mycket exakt. Att köra ADC med snabbast möjliga hastighet kan hjälpa till här.

Har någon ett bättre förslag? Fröet behöver inte fördelas perfekt enhetligt, men ju mer enhetligt fördelningen är desto bättre. Ett 16-bitars frö med en perfekt enhetlig fördelning skulle vara en dröm för bra för att vara sant, men jag tror att en halvvägs anständig fördelning över 5 eller 6 bitar kan vara tillräcklig.

"det skulle vara kul att föreställa sig en leverantörs ansikte när jag säger till dem att vi vill ha de värsta SMD-motstånden de kan hitta" - det skulle vara ännu roligare att låta värdet på detta motstånd vara odefinierat i kretsschemat och berätta förmänniskor i produktion att den här delen måste lödas manuellt efter att kretskortet kommer ut ur placeringsmaskinen, ur en soptunna där vi blandar ihop varje motståndsvärde vi har.- Eftersom det inte är en RNG jag letar efter, utan ett * frö *.Så om det genererar samma värde nästan varje gång det inte är så illa är det viktigare att vara annorlunda mellan enheter.
Biten "långsamt drivs isär" har faktiskt medvetet utforskats i konstmusik, t.ex."György Ligeti - Poème Symphonique For 100 Metronomes" eller "Piano Phase" av Steve Reich.
Kan du programmera varje UC med en något annorlunda programfil?
Finns det någon anledning till att ADC-stiftet inte kunde lämnas flytande och ett värde avlästes från det?Kanske subtrahera ett belopp och sedan multiplicera för att förstärka felet?
Varför inte skriva ett slumpmässigt värde till EEPROM-lagring under produktionsprogrammering?På det här sättet kan du använda den mest snygga RNG som du gillar, eftersom den bara kommer att finnas i produktionsprogrammeraren (s) och inte i slutenheterna.(Tack till @immibis: din "något annorlunda programfil" gav mig idén.)
"8-bitars atmel" i slags vaga: AVR-serien?8051-serien?Övrig?
@Calrion Det var vad jag tänkte på.
Du kan också koppla några snabba saker, som en klocka eller någon buss eller vad har du, till ADC, med eller utan ett externt RC-filter (ingången kommer att ha några inbyggda filter och / eller parasitiska parametrar) och extrahera bitar frånden där.
Så bara för att vara 100% klar, är problemet att de kan börja i samma sekvens, inte att de kan flyta ifrån varandra över tiden, eller hur?
Valet av din RNG är viktig: vissa behöver frön av god kvalitet, andra inte.Till exempel, för Xorshift fungerar alla andra frön än 0 och fungerar lika bra.Till och med en liten skillnad i det ursprungliga fröet kommer att resultera i en helt annan utgångsposition i RNG: s cykel.
Du kan kombinera alla ADC-svar med statistik och timing för ännu mer slumpmässighet.Mät till exempel hur många processormärken det tar tills du tar N-prover där de nedre 3 LSB: erna är 101 och M-proverna där de nedre 3 LSB: erna är 110. Utvidga detta koncept som önskat.
4. Obligatorisk xkcd-serie: [länk] https://xkcd.com/221/
[Relaterat.] (Https://electronics.stackexchange.com/questions/50476/random-number-generators-using-a-gpio-pin)
Tio svar:
helloworld922
2015-09-02 22:00:09 UTC
view on stackexchange narkive permalink

Några möjliga alternativ:

  1. Förprogrammera en unik seriell adress för varje enhet. Om du har en tillräckligt bra RNG-algoritm, kommer till och med en sekventiell lista med seriella adresser att ge väldigt olika resultat.

  2. Beroende på din MCU / inställning kan du ha två olika klockor tillgängliga källor för systemklockan och vakthundens timer / timerräknaringång. Om en / båda av dessa har betydande varians kan du använda den för att generera ett lämpligt annorlunda frö. Här är ett exempel jag skrev som använder en Arduinos interna vakthundstimer och en extern XTAL-systemklocka.

  3. Använd en BJT-transistor och bygg en mycket beta beroende förstärkare. Detta kan läsas från en ADC för utsäde.

  4. Kondensatorer / induktorer specificeras vanligtvis till en mycket sämre tolerans än motstånd. Du kan bygga någon form av filterkrets (RC, RL, LC) med dessa och mäta utdata med ADC.

Jag röstar för alternativ 1, det är en lösning för noll delantal som kommer att resultera i att sekvenserna aldrig behöver matcha.Serienumret och RND-generatorn kan säga 16 bitar vilket gör att alla enheter har en försumbar chans att efterlikna andras mönster.
Jag gillar också lösningen.Om du använder en enkel hashingalgoritm bör du ha det bra även om du har löpande serienummer.
En trevlig sak med alternativ 1 är att vissa enheter levereras med inbyggda serienummer (vanligtvis nätverks- / RF-relaterade mikro) så att du inte ens behöver ett separat steg för att bränna serienumren
Till och med ett skräp-RNG som en [LCG] (https://en.wikipedia.org/wiki/Linear_congruential_generator) kommer att "" ge väldigt olika resultat för en sekventiell lista över seriella adresser "_.Jag röstar också på 1.
Om du har en tidskälla kan det hjälpa dig att kompensera saker mellan körningar om du använder det som bas för din växling.Kombinera detta med en seriell adress / nummer eller MAC-adress om din enhet har en och du kommer att fixa matchningen mellan enheterna också.Jag har sett någon programvara som ihållande lagrar några eller varje slumpmässigt nummer som genereras för användning som utsäde, även efter en omstart.Om dina enheter har olika driftstider ska de glida isär.
+1 för att använda ett förprogrammerat serienummer som utsädet.
@BlueRaja-DannyPflughoeft rätt, till och med [RANDU] (https://en.wikipedia.org/wiki/RANDU)!
Jag gillar alternativ 2, eftersom det inte kräver någon extern hårdvara, förutom en extern oscillator.Det fungerar dock inte om jag använder den interna oscillatorn som klockkälla.
Det beror på MCU;till exempel har ATmega1280 en separat intern oscillator för vakthundtimern än den interna oscillatorn som används för systemklockan.Hur mycket de två faktiskt skiljer sig åt är dock svårt att säga, eftersom de tillverkas på samma munstycke.
Olin Lathrop
2015-09-02 22:15:23 UTC
view on stackexchange narkive permalink

Sätt ett parallellt motstånd och kondensator mellan A / D-stiftet och jord. Gör motståndet ganska högt, helst långt över insignalimpedanskravet för A / D. Gör RC-tiden konstant, kanske cirka 10 µs. Till exempel låter 100 kΩ och 100 pF som en bra kombination.

För att få ett värde med viss slumpmässighet, kör stiftet högt ett tag, ställ sedan in det på hög impedans och ta en A / D-avläsning några µs senare. Särskilt om du missbrukar A / D-insamlingstiden korrekt, kommer spänningen att se att vara beroende av R- och C-värdena, stiftläckströmmen, annat närliggande brus och temperatur.

Ta tag i den låga biten eller de två låga bitarna och upprepa vid behov för att få valfritt antal slumpmässiga bitar.

För ett mer slumpmässigt mönster, utför denna procedur ibland och injicera den låga biten av A / D-resultatet i slumptalsgeneratorn du redan använder.

Det låter bra.Var noga med att kontrollera ingångsimpedansen på ADC - Atmega8-serien har en analog ingångsimpedans på 100Meg vilket gör Olins motståndsvärde lite lågt.
@stef: Ingångsimpedans och signalimpedansen som krävs för korrekt konvertering är två olika saker.Ja, ingångsimpedansen är mycket hög på grund av att den är CMOS.Det finns emellertid en maximal impedansgräns på signalen för att göra det möjligt att ladda provet och hålla locket inom den angivna tiden och för att övervinna det läckage som stiftet kan ha.
tyvärr, från ditt svar trodde jag att du hänvisade till ingångsimpedansen i motsats till källimpedansspecifikationen.10k är Atmega8: s angivna maximala källimpedans, så ditt svar är perfekt.Som referens är S / H-kåpan inuti 14pF, om någon var intresserad.
@stef: Jag redigerade svaret för att göra detta tydligare.
Du saknade månfas och helgdagar.Handvinkar också ett användbart tillskott, särskilt om lågt C och inte är väl skyddad.
esoterik
2015-09-03 03:19:32 UTC
view on stackexchange narkive permalink

Oinitialiserat minne

Du kan försöka använda det oinitialiserade minnet i mikrocontrollern. Tricket är att hitta de bitar som har de mest "balanserade" flip-flopsna, och är faktiskt slumpmässiga. Proceduren är att läsa hela minnet, återställa och upprepa några gånger för att mäta vilka bitar som verkligen är slumpmässiga. Sedan använder du den här kartan för att läsa upp tillräckligt med slumpmässiga bitar för att sådd din PRNG eller LFSR! en dag artikel

Jag gillar den här metoden eftersom den inte kräver några ytterligare kretsar eller stift. din AVR har redan ram, du behöver bara hitta de instabila (slumpmässiga) bitarna. Kartläggningsproceduren kan också automatiseras. du kan tillämpa samma kod och procedur på varje enhet och ha riktigt slumpmässiga resultat!

Du behöver inte riktigt räkna ut vilka bitar som är slumpmässiga.XOR-ing alla byte ger dig ett slumpmässigt resultat även om bara 8 bitar är slumpmässiga.Och som bilden visar kanske de faktiska värdena inte är slumpmässiga i tidsmässig mening, de är unika nog - vilket är precis vad vi behöver här.
Om du hittar en PRNG som låter dig "blanda in" entropi, kan det vara ännu bättre än alternativet XOR-då-frö.Iterera genom det oinitialiserade minnet och blanda in bytes till PRNG.T.ex.se mitt [simplerandom C-bibliotek — mix-funktion] (https://github.com/cmcqueen/simplerandom#mix-function).
Detta ger dig inte slumpmässig kryptokvalitet.
@CamilStaps såklart kommer det inte.
Detta fungerar inte.Oinitialiserat minne är odefinierat beteende om jag har ett operativsystem och jag inte har någon kontroll över vilken del av minnet som kommer att tilldelas mitt program och vad som fanns där tidigare.På en mikrokontroller utan operativsystem är detta inte fallet.Särskilt med AVR, för där kommer allt RAM att vara noll om tillräckligt med tid har gått för att kondensatorerna ska tömmas av strömförbrukningen i brownout.
@vsz Nej, vissa bitar är slumpmässiga vid uppstart.Försök.
@vsz vissa bitar vid start är "stabila" och kommer alltid att vara desamma, andra bitar kommer att vara "instabila" och kommer att vara slumpmässiga, det är därför du måste initialisera minnet.Du kan mäta vilka bitar som är slumpmässiga och vilka som inte är, de slumpmässiga bitarna har kretsar som är mer balanserade och börjar därför slumpmässigt som en eller 0. Även AVR använder SRAM (dvs. flip-flops) inte DRAM (dvs. kondensatoreratt uppdateras).Ja, det finns några fall med återställningskant där ram inte återställs vid utbrott;motsatsen till vad du sa!
Kevin White
2015-09-03 01:04:37 UTC
view on stackexchange narkive permalink

Vad jag gjorde för en MP3-spelare med slumpmässig förmåga är att bara använda ett annat sekventiellt frö vid varje start. Jag började vid 1 och lagrade detta i EEPROM så att jag vid nästa strömcykel använde 2 etc. Detta var på en ATMEGA168. Som helloworld922 noterade till och med ett enkelt sekventiellt frö kommer att generera helt olika pseudoslumpmässiga sekvenser.

Jag använde en av de linjära kongruenta slumpmässiga sekvensgeneratorerna, detta ger en enhetlig fördelning. int i; utsäde = utsäde * 2053 + 13849; i = (utsäde% max) + 1; // max är det maximala värdet jag vill ha ur funktionen

Naturligtvis om du vill att flera enheter ska ha olika sekvenser trots att de kan ha haft samma antal effektcykler så behöver du något att börja slumpmässigt.

Detta kan göras med någon av de metoder som föreslagits av de andra affischerna - En metod jag kan tänka mig kan använda AC-nollkorsningen som går in i processorn om du har det (för lampfasreglering till exempel)? Detta kan användas för att prova timern vid första korsningen efter uppstart och sedan användas som utsäde.

Finns det några tryckknappar på enheten för att välja läge etc? Om så är fallet kan du prova räknaren första gången du trycker på knappen efter att MCU: n har programmerats. Varje uppstart efter denna punkt skulle använda det lagrade utsädet.

CL.
2015-09-02 21:59:31 UTC
view on stackexchange narkive permalink

En ADC är en mycket bra källa för slumpmässighet.

Du behöver inte lita på motståndstoleranser. Varje motstånd genererar termiskt brus, och samma fysiska effekt kommer att introducera buller i ADC när du gör alla samplings- och konverteringsstegen. (Databladet berättar om mängden brus och vilka konfigurationsinställningar som är sämst / bäst.)

Du ska inte låta ADC-stiften sväva; detta kan låta spänningen flyta för långt och riskera att mätta ingången.
(Många MCU-enheter låter dig använda ungefär hälften av matningsspänningen som en ADC-ingång för kalibrering. Detta sparar det externa motståndet och ger dig fortfarande Återigen, se databladet för den värsta / bästa konfigurationen.)

Du behöver inte förlita dig på en enda ADC-mätning. Du kan kombinera flera mätningar med en enkel hash- eller kontrollsummefunktion (CRC räcker). Om du måste börja använda RNG omedelbart kan du senare kombinera ADC-resultatet med det aktuella RNG-utsäde.

Jag är inte säker på att Johnson-buller är lämpligt i den här applikationen;Vid STP har ett 10Meg-motstånd över en 10kHz bandbredd `40uV` av Johnson-brus.Du behöver en> 14 bitars ADC eller en förstärkarkrets för att rimligt mäta detta.
STP är inte riktigt relevant.Särskilt temperaturen kan avsiktligt höjas, men ytterligare 60 grader över STP är bara 10% extra buller.
Ett liknande tillvägagångssätt skulle vara att använda skottbuller i en diod.https://en.wikipedia.org/wiki/Noise_generator#Shot_noise_generators
MichaelS
2015-09-03 10:39:31 UTC
view on stackexchange narkive permalink

Kan du spara utsäde från session till session? Om så är fallet, är det möjligt att slå på varje enhet under en slumpmässig tidsperiod efter skapelsen? På så sätt kommer alla enheter att levereras med förinställda frön som sannolikt inte är desamma.

En annan tanke: Hur länkar du flera enheter tillsammans så att de slås på samtidigt? Om de är i serie, lägg till någon form av kondensator så att (n + 1) enheten börjar några klockcykler efter den n: te enheten. Helst skulle kondensatorer urladdas mycket snabbt vid avstängning av enheten, så varje start / omstart finns ett större mellanrum mellan sekvenserna.

Om de är parallella kan du fortfarande slumpmässigt starta upp starttiden. Jag antar att det finns någon form av effektfiltrering med kondensatorer. Om så är fallet skulle tillverkning av enheter med lite olika filtreringskretsar få varje enhet att starta vid en något annan tidpunkt, vilket skulle orsaka divergens efter flera omstart.

En variation på detta är att lägga till varians till dina klocksignaler om möjligt . En skillnad på 0,1% i klockhastighet kan ha liten inverkan på ljusshowet medan du ändrar hastigheten du passerar PRNG-tabellen ganska snabbt.

anslut kanske en stor häll till den analoga i stiftet och ta några avläsningar av "nätbrum" för att utsäda RNG.
@Jasen, alla enheter som är anslutna till samma förlängningskabel kommer att se samma nätbrum.
Mats
2015-09-03 12:09:29 UTC
view on stackexchange narkive permalink

Om du kör på intern "kalibrerad" klockkälla. Kunde du inte spara ett frö efter en tid, helst i EEPROM. Klockan kommer att glida och den kommer att skilja sig från enhet till enhet. För att spara ett nytt värde efter en tid igen (kanske var 10: e minut eller så eller efter en tid som är tillräckligt kort för att uppstå inom normal tid för enheten. Ju längre enheten är på, desto mer sannolikt kommer det att spara ett "annorlunda" värde i EEPROM.

Ta också ett hopp då och då (inte för ofta) och sätt på nytt medan enheten är på (spara detta nya värde i EEPROM).

Hagen von Eitzen
2015-09-05 21:53:03 UTC
view on stackexchange narkive permalink

Vad sägs om att utvidga din ursprungliga idé om AD-konvertering baserat på ett varierande motstånd genom att lägga till en LDR eller termistor? (Det första skulle behöva kunna "titta" ute, jag vet inte om det är möjligt, men variationen i ljus kan vara högre än temperaturvariationen bland enheter som startade ungefär samma tid på ungefär samma plats. ..)

Termistorer kommer in med en annan användbar egenskap.Flera serier från de flesta tillverkare har en enorm variation och felaktighet.Detta kommer att "förbättra" resultatet ytterligare.
jnk0le
2015-09-02 21:35:21 UTC
view on stackexchange narkive permalink

Du kan lämna en flytande ADC-stift för att mata slumptalsgeneratorn (RNG) med fångat brus. Det borde vara tillräckligt att generera ett frö eller till och med använda det som RNG-generator.

Glöm inte att använda minsta möjliga omvandlingstid.

Den andra lösningen kan vara en brusgenerator applicerad i ADC-stiftet.

Jag gör några mätningar, men om jag kommer ihåg rätt läser en flytande ADC-stift '0' eller nära '0'.Jag ska kolla igen för att se om så är fallet.
Jag är intresserad, står det "0" när det flyter?
Problemet är att detta kan fungera på ett utvecklingskort och misslyckas i slutprodukten.
Loganf
2015-09-03 01:24:35 UTC
view on stackexchange narkive permalink

2 potentiella lösningar, båda förutsatt att du behöver ett unikt utsäde per enhet.

  1. Om du blinkar dina enheter en efter en i fabriken, kan hex-filen ändras programmatiskt av något mellanliggande skript i programmeraren. Om den är datorstyrd kan du skriva över en variabel initialisering med datum och tid. Garanterad att vara unik för varje enhet!

  2. Dallas 1-ledningsenheter använder bara en stift och alla har ett unikt 64-bitars serienummer. Du kan använda detta som fröet.

Jag gillar 2, men tyvärr är DS-delarna ganska dyra.
Använd inte produktionstidsstämpel för slumpmässig kryptokvalitet, det är förutsägbart.
@CamilStaps För OP: s applikation krävs inte kryptokvalitet
@HagenvonEitzen sant, men andra kan komma till den här frågan och leta efter krypto-Q slumpmässighet, så det är värt att nämna.
@CamilStaps * Suck *, det verkar som om du har gett upp mänskligheten :) Är det verkligen för krävande att förvänta sig av någon som vill använda ett svar från electronicsSE för kryptografiska ändamål att de är åtminstone noga med att läsa frågan som den skasvar?"16bit" eller "5 o5 6 bit" frön är inte krypto-Q även om de genereras av en massa Schrödinger katter :)
@HagenvonEitzen det är bara för mycket på spel för att inte klargöra det.Jag skulle alltid nämna det när jag skriver ett svar som detta.I alla fall...
Ska jag redigera svaret?Jag skulle vilja tro att människor som letar efter slumpmässighet i kryptokvalitet skulle kunna känna igen skillnaden.


Denna fråga och svar översattes automatiskt från det engelska språket.Det ursprungliga innehållet finns tillgängligt på stackexchange, vilket vi tackar för cc by-sa 3.0-licensen som det distribueras under.
Loading...