Как да генерирам ефективно случайни числа в микроконтролер?

Можете да генерирате псевдослучайни числа чрез манипулиране на битове чрез симулиране на ЛИНЕЕН РЕГИСТЪР ЗА ИЗМЕСТВАНЕ С ОБРАТНА СВЪРЗКА

Тогава въпросът става "колко бита искате да симулирате?"

Уикипедия има известна информация.

Обикновено се генерират псевдослучайни числа, а не действителни произволни числа, въпреки че и двете са възможни с различни скорости.

Има две общи категории в зависимост от това дали последователността ще се използва за криптографски цели. Основното разграничение е дали познаването на едно число в последователността позволява предсказване на следващото. RNG с общо предназначение не се притесняват дали познаването на алгоритъма би позволило на наблюдател да дублира последователността и те работят доста по-бързо.

Типичен RNG алгоритъм с общо предназначение е Mersenne Twister. Има много публични реализации на различни алгоритми. Вижте тук за един .

Ако MT изисква твърде много памет, полуприличен резервен вариант е линейният съгласуван генератор. (MT е изобретен едва през 1997 г.) Този генератор има определени проблеми, но не изисква почти никаква памет, почти никакъв код и е изключително бърз. Реализациите са навсякъде и това беше разгледано подробно в Получисловите алгоритми на Knuth.

За да заредите всеки RNG, ще ви трябва източник на ентропия, вижте http://en.wikipedia.org/wiki/Entropy_(computing) (Забележка: SO се обърква относно () в тази връзка.) Това обикновено се извлича от времеви събития, които процесорът може да наблюдава, като натискане на клавиши (предполагам, че няма да работи за вас) прекъсвания и пристигащи пакети. Часовникът за реално време често е приемлив източник, ако поддържа собственото си състояние, тъй като рестартирането рядко се синхронизира в някаква последователност.

можете да съхранявате семе в EEPROM и когато устройството се стартира, можете да увеличите семе и да го съхраните отново. Така че при всяко рестартиране ще имате различно произволно число.

Ако имате достъп до ADC, тогава можете да прочетете най-малко значимия бит от него и да го използвате като семе за генератор на псевдослучайни числа, както други са публикували. Очевидно ще трябва да прочетете повече от един бит от ADC, така че са необходими многократни четения, което може да отнеме известно време. Но трябва да направите това само веднъж, например при стартиране, и след това да използвате по-бърз PRNG, за да генерирате нови произволни числа.

Много вградени устройства имат вграден ADC, например фамилията ATMega от Atmel.

Ако хардуерът има бутон за потребителя, прост трик е да преброите колко дълго е натиснат бутонът. С достатъчно бърз къс брояч получавате "случайно" число.

Генератори на псевдослучайни числа, които са най-бързите и най-малко взискателни с.р.т. наборът от инструкции (само shift и xor, без умножение или деление) са по-малки варианти на идеята на Mersenne twister (наречена генерализиран линеен регистър на преместване с обратна връзка). Самият Mersenne twister се нуждае от твърде много памет за микроконтролери.

Проблемът с тези генератори е, че те могат да генерират дълги последователности близо до нула, ако нямате късмет. При разумен размер на пространството на състоянието и инициализация от друг PNRG това обаче е малко вероятно.

Те също така не са сигурни за криптография или хазарт, интелигентен противник може да предвиди бъдещи състояния, след като наблюдава изхода. Това е така, защото те са линейни.

Веднъж проектирах такъв генератор за малък нестандартен процесор с пространство на състоянието от около 50 24-битови думи. Тествах варианти с пакета от тестове на Diehard, докато не намеря добър. Приложението генерираше случайни вариации за хардуерен тест.

Четенето на таймера и неговото xoring/nanding/и т.н. с поредица от битове ще даде полуслучайно на потребителя, тъй като времето между събитията вероятно ще бъде достатъчно раздалечено, така че потребителят наистина няма да може да каже корелацията с таймер.

Ако можете да оставите щифт плаващ, това може да помогне за генериране на произволни числа с сместващ регистър с линейна обратна връзка. Не съм сигурен, че това е правилният начин, но моля, погледнете моя код:

// 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

}

РЕДАКТИРАНЕ: Разбрах, че отговорът ми може да е лош. Повече подробности защо не трябва да използвате плаващ цифров щифт: https://electronics.stackexchange.com/questions/50476/random-number-generators-using-a-gpio-pin