Jak skutecznie generować liczby losowe w mikrokontrolerze?

Question

Jak skutecznie generować liczby losowe w mikrokontrolerze? Czy są jakieś ogólne wytyczne lub konkretna szybka metoda?

Answer 1

Można wygenerować pseudolosowych numerów poprzez manipulowanie bitami poprzez symulowanie rejestr przesuwający z liniowym sprzężeniem zwrotnym

Kwestia staje się 'ile bitów chcesz symulować?

Wikipedia zawiera informacje.

Answer 2

Jeśli masz dostęp do ADC, możesz odczytać z niego najmniej znaczący bit i użyć go jako nasienia dla generatora liczb pseudolosowych, tak jak napisali inni. Oczywiście będziesz musiał przeczytać więcej niż jeden bit z ADC, więc potrzeba wielu odczytów, co może trochę potrwać. Ale wystarczy to zrobić tylko raz, na przykład przy starcie, a następnie użyć szybszego PRNG do generowania nowych liczb losowych.

Wiele wbudowanych urządzeń ma wbudowane ADC, na przykład rodzina Atmel z rodziny ATMega.

Answer 3

Zwykle generowane są liczby pseudolosowe, a nie rzeczywiste liczby losowe, chociaż obie są możliwe w różnym tempie.

Istnieją dwie ogólne kategorie, w zależności od tego, czy sekwencja będzie używana do celów kryptograficznych. Podstawowym rozróżnieniem jest to, czy znajomość jednej liczby w sekwencji umożliwia przewidywanie następnej. Ogólnego przeznaczenia RNG nie martwią się o to, czy znajomość algorytmu pozwoli obserwatorowi na skopiowanie sekwencji i przebiegają one trochę szybciej.

Typowym uniwersalnym algorytmem RNG jest Mersenne Twister. Istnieje wiele publicznych implementacji różnych algorytmów. See here dla jednego.

Jeśli MT wymaga zbyt dużo pamięci, w pół drogi przyzwoity awaryjny jest linear congruential generator. (MT nie został wymyślony do 1997 r.) Ten generator ma pewne problemy, ale prawie nie wymaga pamięci, prawie żadnego kodu i jest niezwykle szybki. Wdrożenia są wszędzie i szczegółowo omówiono je w algorytmach seminumerycznych Knuta:.

Aby zaszczepić dowolny RNG, będziesz potrzebował źródła entropii, zobacz http://en.wikipedia.org/wiki/Entropy_(computing) (Uwaga: SO denerwuje się() w tym łączu.) Jest to zazwyczaj pochodne od zdarzeń czasowych, które procesor może obserwować, takie jak jako naciśnięcia klawiszy (myślę, że to nie zadziała) przerwań i przylotów pakietów. Zegar czasu rzeczywistego jest często dopuszczalnym źródłem, jeśli zachowuje swój własny stan, ponieważ restarty rzadko mają określony czas w dowolnej kolejności.

Answer 4

Generatory liczb pseudolosowych, które są najszybszymi i najmniej wymagającymi w.r.t. zestaw instrukcji (tylko shift i xor, bez mnożenia lub dzielenia) są mniejszymi wariantami pomysłu twister Mersenne (zwanego Generalized Linear Feedback Shift register). Mersenne Twister sam potrzebuje zbyt dużo pamięci dla mikrokontrolerów.

Problem z tymi generatorami polega na tym, że mogą generować długie sekwencje w pobliżu zera, jeśli nie masz szczęścia. Przy rozsądnym rozmiarze przestrzeni stanów i inicjalizacji z innego PNRG jest to jednak mało prawdopodobne.

Nie są również bezpieczne do kryptografii lub hazardu, inteligentny przeciwnik może przewidzieć przyszłe stany po zaobserwowaniu wyniku. Jest tak, ponieważ są one liniowe.

Kiedyś zaprojektowałem taki generator dla małego niestandardowego procesora z przestrzenią stanu około 50 24-bitowych słów. Testowałem warianty z zestawem testowym Diehard, dopóki nie znalazłem dobrego. Aplikacja generowała losowe odmiany w teście sprzętowym.

Answer 5

Jeśli sprzęt ma przycisk dla użytkownika, prosta sztuczka polega na zliczaniu czasu naciśnięcia przycisku. Dzięki wystarczająco krótkiemu licznikowi otrzymujesz liczbę "losową".

Answer 6

Odczytywanie timera i xoring/nanding/etc z serią bitów da pół losowe dla użytkownika, ponieważ czas pomiędzy zdarzeniami jest prawdopodobnie wystarczająco duży, niezależnie od tego, że użytkownik nie będzie w stanie powiedzieć korelacja z zegarem.

Answer 7

można przechowywać materiał siewny do pamięci EEPROM, a po uruchomieniu urządzenia można zwiększyć materiał siewny i zapisać go ponownie. Tak więc przy każdym ponownym uruchomieniu będziesz miał inną losową liczbę.

Answer 8

Jeśli możesz pozostawić sworzeń unoszący się, może to pomóc w generowaniu liczb losowych z liniowym rejestrem przesuwu liniowego. Nie jestem pewien, że to jest do zrobienia, ale proszę spojrzeć na mój kodu:

// This code was written for 8051 (AT89S52) 
unsigned char lfsr = 231; //8 bit shift register, with the seed of 231 or '11100111b' 
unsigned char input_bit, i; 

void main (void) 
{ 
    //Setup 
    P0_0 = 0; // Leave Pin 0 Port 0 floating 
    uart_init(); //Initializing uart/serial communication with pc 


    while (1) 
    { 
     for (i = 0; i < 255; i++) 
     { 
      if (P0_0 == 1) // If Pin 0.0 is HIGH 
      { 
       input_bit = ((lfsr >> 0)^(lfsr >> 2)^(lfsr >> 3)^(lfsr >> 4)) & 1; 
       lfsr = (lfsr >> 1) | (input_bit << 7); 
      } 
     } 
     printf_tiny("%u\n", lfsr); //Send the random number to PC 
     soft_delay(65535); //Simple delay function 
    } //end while (1) loop 

} 

EDIT: I okazało się, moja odpowiedź może być zły. Więcej szczegółów na temat, dlaczego nie należy używać pływającego cyfrowego pin: https://electronics.stackexchange.com/questions/50476/random-number-generators-using-a-gpio-pin