Jakie jest najmniejsze i najprostsze ziarno generatora liczb losowych?

Mały mikrokontroler (8-bitowy Atmel) steruje wieloma światłami, aby zaprezentować pokaz świetlny z wieloma fantazyjnymi losowymi sekwencjami światła.

Odpowiedni pseudo-RNG dobrze sobie radzi, ale szukam dla niego dobrego ziarna. Ziarno będzie konieczne, ponieważ jeśli ktoś włączy jednocześnie wiele takich urządzeń, nie będzie dobrze wyglądać, jeśli wszystkie wygenerują te same sekwencje efektów, dopóki nie zaczną się powoli rozsuwać z powodu niewielkich różnic w poszczególnych źródłach zegara.

Bardzo dobra metoda wysiewu pseudo-RNG, której często używałem, jest możliwa w przypadku urządzenia, które należy uruchomić przez naciśnięcie przycisku lub naciśnięcie przełącznika. Zaraz po włączeniu µc można uruchomić bardzo szybki timer, a wartość tego timera uruchamia RNG, gdy tylko przycisk zostanie naciśnięty po raz pierwszy.

Problem polega na tym, że w tym scenariuszu nie ma przycisków. Program musi zostać uruchomiony natychmiast po włączeniu urządzenia.

Miejsce na płytce drukowanej jest bardzo ograniczone (może się zmieścić tylko kilka bardzo małych części SMD), więc szukam możliwie najmniejszego i najprostszego rozwiązania. Dlatego wykluczę wymyślne rozwiązania, takie jak prawdziwy sprzęt RNG, odbiorniki radiowe itp.

Wszystko, co mam, to 16-bitowy licznik timera w procesorze i nieużywany portpin, który ma dostęp do ADC.

Moje obecne rozwiązanie polega na użyciu rezystora (tak niedokładnego, jak to możliwe), aby dostarczyć około połowy napięcia zasilania na pin ADC i zaszczepić RNG pierwszą wartością konwersji AD. Jednak obecnie większość 10% rezystorów ma niedokładność znacznie poniżej 1% (fajnie byłoby wyobrazić sobie twarz dostawcy, gdy mówię im, że chcemy najgorszej jakości rezystorów SMD, jakie mogą znaleźć), więc istnieje bardzo duża szansa na wiele jednostek zaczynających się od tego samego ziarna.

Lepszą alternatywą byłoby wykonanie wielu konwersji i zbudowanie wartości z najmniej znaczących bitów tych pomiarów. Jednak wcześniej użyłem ADC tego typu µc i wiem, że jest bardzo dokładny. Pomocne może być uruchomienie ADC z najszybszą możliwą prędkością.

Czy ktoś ma lepszą sugestię? Nasiona nie muszą być idealnie równomiernie rozmieszczone, ale im bardziej równomierny jest rozkład, tym lepiej. 16-bitowe ziarno z idealnie jednolitym rozkładem byłoby snem zbyt pięknym, aby mogło być prawdziwe, ale myślę, że wystarczający może być w połowie przyzwoity rozkład na 5 lub 6 bitów.

Umieść rezystor równoległy i kondensator między stykiem A / D a masą. Ustaw rezystor na dość wysokim poziomie, najlepiej znacznie powyżej wymaganej impedancji sygnału wejściowego dla A / D. Ustaw czas RC na stały, może około 10 µs. Na przykład 100 kΩ i 100 pF brzmi jak dobra kombinacja.

Aby uzyskać wartość z pewną przypadkowością, podnieś pin przez chwilę, a następnie ustaw na wysoką impedancję i zrób odczyt A / D kilka µs później. W szczególności, jeśli właściwie wykorzystasz czas akwizycji A / D, napięcie, które zobaczy, będzie zależeć od wartości R i C, prądu upływu pinów, innych pobliskich szumów i temperatury.

Chwyć niski bit lub dwa niskie bity i powtórz w razie potrzeby, aby uzyskać dowolną liczbę losowych bitów.

Aby uzyskać bardziej losowy wzorzec, należy od czasu do czasu wykonać tę procedurę i wstrzyknąć niski bit wyniku A / D do generatora liczb losowych, którego już używasz.

Niektóre możliwe opcje:

1. Zaprogramuj unikalny adres seryjny dla każdego urządzenia. Jeśli masz wystarczająco dobry algorytm RNG, to nawet sekwencyjna lista adresów szeregowych da zupełnie odmienne wyniki.

2. W zależności od MCU / konfiguracji mogą być dostępne dwa różne źródła zegara dla zegara systemowego i wejścia watchdog licznik / licznik timera. Jeśli jedno / oba mają znaczną wariancję, możesz użyć tego do wygenerowania odpowiednio innego ziarna. Oto przykład, który napisałem, który wykorzystuje wewnętrzny zegar kontrolny Arduino i zewnętrzny zegar systemowy XTAL .

3. Użyj tranzystora BJT i ​​zbuduj wzmacniacz wysoce zależny od wersji beta. Można to odczytać z ADC dla nasion.

4. Kondensatory / cewki indukcyjne mają zwykle znacznie gorszą tolerancję niż rezystory. Za ich pomocą można zbudować jakiś obwód filtra (RC, RL, LC) i zmierzyć moc wyjściową za pomocą ADC.

Niezainicjowana pamięć

Możesz spróbować użyć niezainicjowanej pamięci w mikrokontrolerze. Sztuką jest znalezienie bitów, które mają najbardziej „zbalansowane” przerzutniki i są w rzeczywistości losowe. Procedura polega na odczytaniu całej pamięci, zresetowaniu i powtórzeniu kilka razy, aby zmierzyć, które bity są naprawdę losowe. Następnie używasz tej mapy, aby odczytać wystarczającą liczbę losowych bitów, aby zasiać PRNG lub LFSR!

Ta metoda powinna dać ci losowe nasiona, nawet z identycznym sprzętem, więcej szczegółów (i linki) są dostępne w tym artykule o hack-dziennie

Podoba mi się ta metoda, ponieważ nie wymaga żadnych dodatkowych obwodów ani styków; twój AVR ma już ram, po prostu musisz znaleźć niestabilne (losowe) bity. Można również zautomatyzować procedurę mapowania; możesz zastosować ten sam kod i procedurę do każdego urządzenia i uzyskać naprawdę losowe wyniki!

To, co zrobiłem dla odtwarzacza MP3 z funkcją losowego, to po prostu użycie innego sekwencyjnego materiału siewnego przy każdym włączeniu zasilania. Zacząłem od 1 i zapisałem to w EEPROM, więc przy następnym cyklu zasilania użyłem 2 itd. To było na ATMEGA168. Jak zauważył helloworld922, nawet proste sekwencyjne ziarno wygeneruje zupełnie inne pseudolosowe sekwencje.

Użyłem jednego z liniowych przystających generatorów losowych sekwencji, co daje równomierny rozkład.

int i;
seed = seed * 2053 + 13849;
i = (seed % max) + 1;  // max is the maximum value I want out of the function

Oczywiście, jeśli chcesz, aby wiele jednostek miało różne sekwencje, mimo że mogły mieć taką samą liczbę cykli zasilania, potrzebujesz czegoś, aby zacząć losowo.

Można tego dokonać dowolną z metod zaproponowanych przez inne plakaty - Jedna z metod, o której myślę, mogłaby użyć przejścia przez zero prądu przemiennego do procesora, jeśli go masz (na przykład do kontroli fazy lampy)? Można to wykorzystać do próbkowania licznika czasu na pierwszym przejeździe po włączeniu zasilania, a następnie wykorzystać jako ziarno.

Czy na urządzeniu są jakieś przyciski do wyboru trybu itp.? Jeśli tak, możesz próbkować licznik przy pierwszym naciśnięciu przycisku po zaprogramowaniu MCU, możesz początkowo wygenerować losowe ziarno i zapisać je w EEPROM. Każde wzmocnienie po tym punkcie użyłoby przechowywanego ziarna.

ADC jest bardzo dobrym źródłem losowości.

Nie musisz polegać na tolerancjach rezystorów. Każdy rezystor generuje szum termiczny , a ten sam efekt fizyczny wprowadzi szum do ADC podczas wykonywania wszystkich kroków próbkowania i konwersji. (Arkusz danych powie ci o ilości hałasu i jakie ustawienia konfiguracji są najgorsze / najlepsze.)

Nie należy pozostawiać pływającego styku ADC; może to pozwolić, aby napięcie unosiło się zbyt daleko i grozi nasyceniem wejścia.
(Wiele MCU pozwala na użycie czegoś takiego jak połowa napięcia zasilania jako wejścia ADC, do kalibracji. To oszczędza zewnętrzny rezystor i wciąż powoduje hałas. Ponownie, patrz arkusz danych dla najgorszej / najlepszej konfiguracji.)

Nie musisz polegać na pojedynczym pomiarze ADC; możesz łączyć wiele pomiarów za pomocą prostej funkcji skrótu lub sumy kontrolnej (wystarczy CRC). Jeśli musisz natychmiast zacząć korzystać z RNG, możesz później połączyć wynik ADC z bieżącym ziarnem RNG.

Czy możesz zapisać ziarno między sesjami? Jeśli tak, to czy możliwe jest włączenie każdej jednostki na jakiś losowy okres czasu po utworzeniu? W ten sposób wszystkie jednostki zostaną wysłane ze wstępnie ustawionymi nasionami, które prawdopodobnie nie będą takie same.

Kolejna myśl: jak połączyć ze sobą wiele jednostek, aby włączały się jednocześnie? Jeśli są połączone szeregowo, dodaj jakiś kondensator, aby (n + 1) urządzenie zaczęło kilka cykli zegara po n-tym urządzeniu. Idealnie kondensatory rozładowałyby się bardzo szybko przy wyłączaniu urządzenia, więc przy każdym uruchomieniu / ponownym uruchomieniu występuje większa przerwa między sekwencjami.

Jeśli są one równoległe, nadal możesz trochę losowo ustalić czas uruchamiania. Zakładam, że jest jakaś filtracja mocy za pomocą kondensatorów. Jeśli tak, wytworzenie urządzeń z nieco innymi obwodami filtracyjnymi spowodowałoby, że każde urządzenie uruchomiłoby się w nieco innym czasie, powodując rozbieżność po kilku ponownych uruchomieniach.

Odmianą tego jest dodanie wariancji do sygnałów zegara, jeśli to możliwe. Różnica prędkości zegara o 0,1% może mieć niewielki wpływ na pokaz świetlny, a jednocześnie dość szybko zmieniasz tempo przechodzenia przez tabelę PRNG.

Jeśli korzystasz z wewnętrznego „skalibrowanego” źródła zegara. Czy po pewnym czasie nie możesz zapisać ziarna, najlepiej w pamięci EEPROM? Zegar będzie dryfował i będzie się różnił w zależności od jednostki. Aby zapisać nową wartość po jakimś czasie (może co 10 minut lub po czasie, który jest wystarczająco krótki, aby nastąpił w normalnym czasie włączenia urządzenia. Im dłużej urządzenie jest włączone, tym bardziej prawdopodobne jest, że zapisze „inna” wartość w EEPROM.

Od czasu do czasu również wykonuj skok (nie za często) i resetuj, gdy urządzenie jest włączone (zapisz tę nową wartość w EEPROM).

Co powiesz na rozszerzenie oryginalnego pomysłu konwersji AD w oparciu o zmienny rezystor poprzez dodanie LDR lub termistora? (Pierwszy musiałby być w stanie „spojrzeć” na zewnątrz, nie wiem, czy to wykonalne; ale zmiana światła może być wyższa niż zmiana temperatury między urządzeniami uruchomiona mniej więcej w tym samym czasie i w tym samym miejscu. ..)

2 potencjalne rozwiązania, przy założeniu, że potrzebujesz unikalnego materiału siewnego na jednostkę.

1. Jeśli flashujesz swoje jednostki jeden po drugim w fabryce, plik hex może być programowo modyfikowany przez jakiś skrypt pośredni w programerze. Jeśli jest sterowany komputerowo, możesz nadpisać inicjalizację zmiennej datą i godziną. Gwarantujemy, że będzie unikalny dla każdej jednostki!

2. Urządzenia drutowe Dallas 1 wykorzystują tylko jeden pin, a każdy z nich ma unikalny 64-bitowy numer seryjny. Możesz użyć tego jako ziarna.

Możesz zostawić pływający pin ADC, aby zasilić generator liczb losowych (RNG) przechwyconym hałasem. Wystarczy wygenerować ziarno, a nawet użyć go jako generatora RNG.

Nie zapomnij użyć minimalnego możliwego czasu konwersji.

Innym rozwiązaniem może być generator szumów zastosowany w pinie ADC.