EPP: Generator liczb losowych by Dondu

Autor: Dondu

Niniejszy artykuł jest częścią cyklu Efektywne Planowanie Projektu i przedstawia jedno z możliwych rozwiązań generatora liczb losowych, bez wykorzystania standardowej i pamięciożernej funkcji rand() z biblioteki stdlib. Więcej rozwiązań znajdziesz tutaj: EPP: Generator liczb losowych

Przygotowałem dla Was rozwiązanie wykorzystujące szumy powstające przy pomiarze przetwornikiem analogowo-cyfrowym (ADC).



Szum ADC - co to jest?
Przetwornik ADC pozwala na zmierzenie poziomu sygnału analogowego np. sinusoidy. Pomiar ten trwa pewien czas na przykład 20μs. W tym czasie:

Rys. Sukcesywna
aproksymacja

• napięcie zasilające ADC oraz napięcie referencyjne (odniesienia) mogą nie być stabilne (minimalne zmiany)
• mogą powstawać zakłócenia na wejściu pomiarowym ADC,
• technika pomiaru (sukcesywna aproksymacja) także nie jest idealna.

Te zjawiska zwykle są niepożądane i eliminowane za pomocą odpowiednich technik projektowania i budowy urządzeń elektronicznych. Niedokładności pomiarów nazywa się szumem ADC który ujawnia się w szczególności na najmłodszych bitach wyniku pomiaru, poprzez przyjmowanie przez nie przypadkowych stanów logicznych.

Rys. Przykład szumu ADC

Jak wykorzystać szum?
Skoro szum jest przypadkowy, to można by go wykorzystać do budowy generatora liczb losowych.

Niestety nie wystarczy odczytać pomiar ADC, ponieważ losowy stan mają najczęściej tylko bity najmłodsze (patrz animacja powyżej).

Dlatego też bezpiecznie przyjmiemy, że naszą liczbę losową tworzyć będziemy używając tylko najmłodszego bitu ADC (gdyż jest to najbardziej losowy bit). Liczbę tę będziemy składać za każdym nowym pomiarem wykonanym przez ADC w następujący sposób :

Rys. Algorytm tworzenia liczby losowej za pomocą ADC

Schemat 

Wykorzystamy jeden kanał ADC. Aby układ był najbardziej niestabilny pin wejściowy ADC pozostawimy niepodłączony, by zbierał zakłócenia.

Schemat 1

Schemat zawiera niezbędne elementy do prawidłowej pracy mikrokontrolera, które opisałem tutaj:
Minimalne podłączanie pinów



Program
Program może być rozwiązany na wiele różnych sposobów. Ja przyjąłem wersję najprostszą:

• ADC używany jest tylko do generowania liczby losowej,
• liczba ma być generowana w tle (w przerwaniu) i zapisywana do globalnej zmiennej liczba_RND,
• ADC pracować będzie w trybie FREE RUNNING (pomiar za pomiarem),
• przerwanie z ADC może być używane także do innych celów.

Niezbędne definicje początkowe:

#include <avr/io.h>
#include <util/delay.h> 
#include <avr/interrupt.h> 

volatile char liczba_RND; //liczba losowa dostępna zawsze i wszędzie

1. Inicjalizacja ADC

1.1 Wybieramy źródło napięcia odniesienia, z pinu AREF:

1.2 Wybieramy kanał na pinie ADC0:

1.3 Wybieramy wyrównanie wyniku pomiaru ADC do prawej (domyślny):

1.4 Ustawiamy preskaler ADC

Ponieważ w naszym przypadku mikrokontroler taktowany jest zegarem 8MHz, a ADC mikrokontrolera ATmega8 nie może być taktowany szybciej niż 1MHz, stąd musimy zmniejszyć częstotliwość, którą taktowany będzie ADC. Do tego celu wykorzystamy preskaler ADC ustawiając go na 8:

Rys. Preskaler ADC dla Atmega8

Ponieważ jeden pomiar ADC trwa 13 cykli zegara ADC, to policzmy ile czasu będzie trwał jeden pomiar:

Czyli co 13µs będziemy mieli nową pseudolosową liczbę. Jednakże ze względu, że:

• za każdym pomiarem liczba_RND jest przesuwana o 1 bit w lewo, a najmłodszy jej bit jest ustawiony losowo, 
• oraz liczba_RND zawiera 8 bitów, 

stąd liczba ta będzie w pełni losowa dopiero po 8 pomiarach ADC, czyli co:

UWAGA!!!
Dla 8 bitowej liczba_RND:
- odczytując ją rzadziej niż co 104µs masz pewność, że jest liczbą losową.
- odczytując ją częściej niż 140µs, ale rzadziej niż 13µs otrzymujesz liczbę pseudolosową.
- odczytując ją częściej niż co 13µs nie masz pewności, że liczba będzie się różnić od ostatnio odczytanej.

To są istotne ograniczenia tak zbudowanego generatora liczb losowych. Oczywiście gdy potrzebujesz na przykład tylko 4 bitową liczbę losową, czasy te będą odpowiednio krótsze.

Jeżeli te czasy są dla Ciebie zbyt długie, możesz zmienić poniższy program tak, by wykorzystać możliwość przekroczenia dopuszczalnych parametrów ADC, podobnie jak to zrobił Drzasiek testując przetwornik ADC w ATmega8: ADC - Ile da się wycisnąć? - czyli eksperymenty z ADC.


Tworzymy funkcję inicjującą ADC:

void ADC_inicjuj(void)
{

 //funkcja inicjuje ADC w tryb Free Running, 
 //wywołując jednocześnie pierwszy pomiar

 //ustawiamy rejestr ADMUX
 //wybierz kanał pomiarowy nr 0 czyli pin PC0, MUX3:0=0
 //wyrównaj wynik pomiaru do prawej, ADLAR=0
 //napięcie odniesienia AVcc z kondensatorem na AREF
 //jeżeli nie wykorzystujesz ADC do innych celów, to możesz 
 //nie dodawać kondensatora
 ADMUX  = (1<<REFS0);   

 //ustawiamy rejestr ADCSRA
 ADCSRA  |=  (1<<ADPS1)|(1<<ADPS0); //ustaw preskaler ADC na 8
 ADCSRA  |=  (1<<ADEN); //włącz ADC
 ADCSRA  |=  (1<<ADFR); //włącz tryb FREE RUNNING
 ADCSRA  |=  (1<<ADIE); //włącz przerwania z ADC
 ADCSRA  |= (1<<ADSC);  //rozpocznij pierwszy pomiar ADC
}

Po dokonaniu pomiaru przez ADC, wywoływane jest przerwanie w celu odczytu wyniku i wygenerowania nowej liczba_RND:

ISR(ADC_vect)      
{
 //--- Obsługa przerwania po dokonaniu pomiaru przez ADC

 liczba_RND =  (liczba_RND<<1); //przesuń liczba_RND o 1 bit w lewo

 //odczytaj ADC, pozostaw tylko najmłodszy bit
 //i skopiuj ten bit na najmłodszy bit zmiennej liczba_RND
 liczba_RND |= ADC & 0x01;   

 //tutaj możesz dodać kod wykorzystujący przerwanie z ADC 
 //także do innych celów

}

I wreszcie główna część programu:

//--- Program główny -------------
int main(void)
{

 sei();    //włącz globalne przerwania 

 ADC_inicjuj(); //inicjuj ADC  
 
 while(1)
 {
  //tutaj nie ma nic, ponieważ generator jest w funkcji przerwania z ADC
  //czyli działa w tle, a liczba losowa jest dostępna 
  //z dowolnego miejsca programu i w dowolnym momencie 
  //w zmiennej globalnej: liczba_RND

  //oczywiście możesz tutaj zamieścić swój program :-)
 }
}

Pobierz kompletny program: main11.c

Taki kod zajmuje:

• Program: 508 bytes
• Data: 1 bytes

Oooo! Jaka kolosalna różnica w porównaniu do 930 bajtów, które funduje nam funkcja rand()

Poniżej projekt pokazujący na wyświetlaczu losowane liczby uzyskane za pomocą przedstawionego wyżej rozwiązania:





Aby jeszcze zwiększyć niestabilność generatora liczb losowych, możesz zrobić prosty zewnętrzny generator szumu i podłączyć pod wejście ADC mikrokontrolera:

Schemat 2 - Generator szumu.

źródło: Hardware Random Number Generator

Powyższy generator zaprojektowany jest do napięcia 12V, będziesz musiał więc pokombinować, by dostosować go do swoich wymagań. Ale jest on na tyle prosty, że bez problemu nawet drogą eksperymentalną to osiągniesz.

Możesz zauważyć, że kolektor trazystora Q1 także jest niepodłączony (NC - not connected) i podobnie jak ADC0 ze schematu 1, zbiera zakłócenia, które są podstawą generowania losowego szumu.

Taki generator (dostosowany do napięcia zasilania Twojego mikrokontrolera) możesz podłączyć bezpośrednio pod dowolny pin mikrokontrolera (ponieważ mają one na wejściach przerzutniki Schmitta) i sprawdzać jego stan (0 lub 1) składając liczbę z bitów, w sposób opisany wyżej.

Inne przykłady generatorów szumu

Przykłady prostych układów generatorów szumu możesz znaleźć w tym opracowaniu: Random Number Generation with a Simple Transistor Junction Noise Source (kopia)



Podsumowanie
Jeżeli masz wolny przetwornik ADC, to problem masz z głowy.
Jeżeli wykorzystujesz ADC do innych celów, to możesz kombinować ze zmianami kanałów.
Jeżeli losowe liczby są Ci potrzebne bardzo rzadko, możesz maksymalnie zwolnić ADC preskalerem lub wywoływać nowe pomiary programowo, zamiast w trybie Free Running.
Generalnie ... rusz głową i dostosuj do swoich potrzeb! :-)

Zalety:

• oszczędność: 930 - 508 = 422 bajtów
• pełna losowość zależna jedynie od łapanych przez układ zakłóceń,
• bardzo krótki kod wynikowy (małe zużycie pamięci programu),
• możliwość wykorzystania przerwania z ADC do innych celów (eliminacja drgań styków przycisków, multipleksowanie wyświetlaczy, zegar czasu rzeczywistego RTC, itp.).

Wady:

• liczby losowe są uzyskiwane w odstępach czasowych
• zajęty ADC (co najmniej jeden kanał).

Powyższe podejście jest tylko przykładem i może być dowolnie zmieniane tak, aby pozbyć się niektórych z wyżej wymienionych wad, w zależności od Twoich potrzeb.
Możesz także zwiększyć ilość bitów w liczbie losowej.