Користење на генератор на случаен број на Arduino: Функциите случајни и случајни семе. Курс Arduino - тајминг и случајно генерирање на секвенца со случаен бит Arduino

При програмирање на Arduino, има моменти кога треба да добиете број кој однапред нема да биде познат ниту од програмерот што ја пишува скицата, ниту од корисникот кој ќе го користи Arduino со таква програма. Во овој случај, генератор на случаен (или поточно псевдо-случаен) број доаѓа на помош.

За да го активирате овој генератор, доволно е да ги користите функциите random() или randomSeed(). Оваа статија ќе покаже како да работите со овие функции, како и како да се ослободите од псевдо-случајноста при генерирање броеви.

Во принцип, генератор на псевдо-случајни броеви ја имитира случајноста или случајноста на појавата на броеви, но всушност, ако анализирате одреден број од овие броеви за доволно долг период, можете да забележите одредена шема.

Значи, случајната функција за генерирање на псевдо-случајни броеви може да има до два параметра и да се запише како случаен(max) или random(min, max). Овде, максималниот параметар, кој е задолжителен, ја поставува горната граница на опсегот за генерирање на псевдо-случајни броеви. Со користење на дополнителен параметар min може да се користи за поставување на долната граница на опсегот. Како резултат на тоа, функцијата ќе врати некој псевдо-случаен број помеѓу min и max-1.

Важно е да се разбере дека кога се користи функцијата random(), секој пат ќе се генерира точно истата листа на псевдо-случајни броеви. На пример, ако направите слот машина и првиот пат кога ќе ја притиснете рачката, ќе се појави добитна комбинација, тогаш можете да бидете сигурни дека ако го ресетирате Arduino и повторно притиснете ја рачката, овој автомат ќе ја покаже истата добивка. комбинација. Навистина, на Arduino не е лесно да се имплементира машина за игри со целосно случајно генерирање броеви, како што е, на пример, имплементирано во машините за игри www.igrovye-apparati-vulcan.com/, но делумно можете да го решите проблемот со користење на randomSeed() функција.

Оваа функција зема вредност (на пример, цел број) и користи број за да ја измени листата на случајни генерирани од функцијата random(). јамка. Но, во овој случај, ќе има фаќање, а тоа е дека иако низата на случајни броеви ќе биде различна кога се користи функцијата randomSeed(), таа сепак ќе биде иста секогаш кога ќе се изврши скицата.

Единственото решение во овој случај може да биде опција со користење на аналогни периферни уреди (ADC) и соодветната функција analogRead (). Ако не го поврзете аналогниот влез со ништо, односно оставете го да „виси“ во воздухот, тогаш благодарение на бучавата на оваа линија, можете да добиете навистина случајни броеви. Потоа во поставките за поставување, можете да пишувате вака randomSeed(analogRead(A0)). Под услов аналогната порта A0 да не е поврзана никаде.

Многу е напишано за генераторите на случаен број, но скоро секогаш, кога станува збор за имплементација, се подразбира (или експлицитно наведено) дека ние зборувамеза x86/x64 и други архитектури за „возрасни“. Во исто време, форумите посветени на развојот на уреди на микроконтролери се полни со прашања „како да генерирам случаен број на %controllername%?“. Покрај тоа, опсегот на одговори се протега од „види Google / Wikipedia“ до „користете ја стандардната функција“. Оваа „стандардна функција“ е далеку од секогаш присутна и одговара на развивачот во сите погледи, почесто е обратно: или бројките се далеку од случајни, или брзината на работа е премногу мала, или добиениот код не е воопшто се вклопуваат во слободната меморија.
Ајде да се обидеме да откриеме кои се алгоритмите за генерирање на случајни броеви, како да го избереме вистинскиот и што е најважно, кои се карактеристиките на имплементацијата на овие алгоритми на контролорите.

Резултат на случајност

Апликациите за RNG можат да бидат многу различни, од играчки до сериозна криптографија. Соодветно на тоа, барањата за генераторот исто така варираат во голема мера. За да се процени квалитетот (нивото на „случајност“) на генераторот, постојат специјални тестови. Еве ги најосновните:

• фреквентен тест. Се состои од броење на бројот на нули и единици во низа од битови. Едниците и нулите треба да бидат приближно еднакви.
• Тестирајте за низа од идентични битови. Се пребаруваат редови со идентични битови, како 000...0 или 111...1. Распределбата на фреквенциите со кои се среќава серијата, во зависност од нивната должина, треба да одговара на таквата распределба за вистински случаен сигнал.
• Спектрален тест. Дискретната Фуриеова трансформација се применува на оригиналната низа. Резултирачкиот спектар не треба да има значителни врвови што би укажале на присуство на периодични својства на низата.
• Тест за автокорелација. Се пресметува корелационата вредност помеѓу копии од низата поместени релативно едни на други. Тестот ви овозможува да најдете повторливи делови во низа.

Постојат специјални комплети кои вклучуваат десетици слични тестови:
NIST - се користи во натпреварот AES за евалуација на алгоритми за шифрирање.
DIEHARD е еден од најригорозните комплети што постојат.

PRNG алгоритми

Секоја низа генерирана според тврдокодираниот алгоритам не може да се смета за навистина случајна, затоа, кога се зборува за алгоритамски генератори, тие го користат терминот псевдо-случајнопоследователна секвенца. Секој генератор на псевдо-случајни броеви (PRNG) се врти порано или подоцна, друга работа е што ова „доцна“ може да дојде за неколку милисекунди, или можеби за неколку години. Должината на циклусот зависи од големината на внатрешната состојба на генераторот N (всушност, ова е количината на меморија потребна на генераторот) и се движи од 2 (N / 2) до 2 N бита.
Измислен е огромен број PRNG алгоритми, но не сите од нив се погодни за имплементација на микроконтролери. Ние сме многу ограничени во брзината и достапната меморија, многу контролери не поддржуваат вистински аритметички, па дури и команди за множење. Имајќи ги предвид овие ограничувања, ајде да погледнеме некои добро познати алгоритми.

Линеарен конгруентен метод

Следниот член на низата се пресметува со формулата
X i+1 = (aX i + c) mod m
Број мго одредува максималниот период на низата, цели броеви аИ в- „магични“ коефициенти. Број мразумно е да се избере еднаква на моќноста на два, во кој случај операцијата за намалување на модулите се сведува на отфрлање на високите битови. За да се добие максималниот период, мора да се исполнат следниве услови:
- ви m мора да биде компактен,
- а-1треба да биде повеќекратен стрза сите прости делители стрброеви м,
- Ако ме множител на 4 (а во нашиот случај ќе биде множител), тогаш а-1мора да биде повеќекратно од 4.
Има уште една суптилност: како резултат треба да се земат само високите битови од променливата на состојбата X, бидејќи статистичките параметри на случајноста се многу полоши за ниските битови. Линеарниот конгруентен алгоритам обично се имплементира како стандарден rand() во многу библиотеки.

Добрите страни:

• максималниот можен период за дадена состојба променлива големина;
• доволно брзо;
• често веќе имплементирани во библиотеката на компајлерот.

Минуси:

• потребна е операција за множење;
• не се сите битови подеднакво случајни.

Резиме:брз и едноставен алгоритам за не многу одговорни апликации.

Фибоначи метод со одложувања

Овој алгоритам ја користи релацијата
X i \u003d X i-a - X i-b,
каде е променливата состојба Xе неозначен цел број. Вредности за одложување аИ бсе земаат не било какви, туку строго дефинирани, се препорачуваат парови (17,5), (55,24) или (97,33) за да се постигне максимален квалитет. Колку е поголемо доцнењето, толку е подолг периодот и подобри се спектралните својства на низата. Од друга страна, за да работи генераторот, потребно е да се складира max(a,b) од претходните броеви, што не е секогаш прифатливо. Исто така, за да го стартувате генераторот, потребни ви се макс(а,б) броеви, кои обично се добиваат со помош на поедноставен PRNG.

Добрите страни:

• не бара операции за множење;
• сите битови од случаен број се статистички еквивалентни.

Минуси:

• бара голема количина на меморија;
• бара голема низа на броеви за да се изврши.

Резиме:многу квалитетен, но интензивен алгоритам со ресурси.

Регистар за поместување на линеарна повратна информација

Променливата состојба е зачувана во регистар со должина N. Генерирањето на следната состојба вклучува два чекори:

1. Се пресметува вредноста на битот C = X i1 xor X i2 xor… X ik, каде i1, i2…ik- повикани броеви на битови за регистрирање се наведнува.
2. Регистарот е поместен за 1 бит надесно, најлевиот бит ја зема вредноста СО.

Излезот на генераторот е најдесниот (или најлевиот, или кој и да е) бит од регистарот, што значи дека псевдо-случајната низа се генерира еден бит по повторување. Со правилно избрани броеви на чешми, периодот на генераторот ќе биде 2 N - 1. „Минус еден“, бидејќи има забранета нулта состојба на регистарот. Броеви на филијали за Нод 3 до 168 може да се погледнат во овој документ.
Покрај погоре опишаната конфигурација, која, патем, се нарекува конфигурација на Фибоначи (да не се меша со истоимениот метод PRNG!), Постои т.н. Галоа конфигурација.


Наместо да го користите збирот на битови во секвенцата на допири за да генерирате нов најлев бит, XOR секој бит од секвенцата на допири со најдесниот бит, а потоа ротирајте го целиот регистар надесно. Оваа шема е потешка за разбирање, но полесна за имплементација, бидејќи сите операции на XOR можат да се извршат во исто време. Шемите Фибоначи и Галоа се еквивалентни во однос на должината на периодот и квалитетот на псевдослучајните броеви.

Добрите страни:

• многу едноставна имплементација, дури и аритметика не е потребна, само битови операции и поместувања;
• многу брз алгоритам (особено шемата Галоа);
• добри статистички својства.

Минуси:

• треба да ја проверите почетната вредност за нееднаквост нула.

Резиме:многу брз и прилично висококвалитетен алгоритам.

Криптоотпорни алгоритми

За примена во криптографијата, PRNG има уште еден суштински услов: неповратност. Сите алгоритми наведени погоре го немаат ова својство: знаејќи неколку излезни вредности на PRNG, можно е, со решавање на едноставен систем на равенки, да се најдат параметрите на алгоритмот (истите „магични“ константи а, б, витн). И знаејќи ги параметрите, можете да ја репродуцирате целата псевдо-случајна низа.
Секоја доволно силна блок-шифра може да се користи како криптографски силен PRNG алгоритам. Со избирање на таен клуч, блокови од псевдо-случајни броеви може да се добијат со примена на алгоритмот на последователни природни броеви. За N-битна блок шифра, периодот ќе биде најмногу 2 N. Безбедноста на таквата шема целосно зависи од тајноста на клучот.
Сите модерни криптографски алгоритми се тестираат за употреба како PRNG, односно, со користење на сертифициран алгоритам, нема потреба да се води посебна грижа за статистичките и спектралните својства на излезниот тек. Треба само да се грижите за пресметковната „замор“ на крипто алгоритмите. Ако треба да извршите голем број операции за шифрирање, има смисла да изберете контролер со хардверски криптографски блокови. Често во такви контролери има и многу добар криптоотпорен хардвер PRNG.

Извори на ентропија

Како што веќе споменавме, користејќи само детерминистички алгоритми, невозможно е да се генерира вистински случаен број. Затоа, обично се користи еден куп PRNG + надворешни извор на ентропија. Изворот на ентропија се користи за поставување на почетната вредност за PRNG, а задачата на вториот е да обезбеди спектрална и статистичка чистота на низата. Што може да се користи како извор на ентропија? Да, практично сè.

Корисничка активност

Ако уредот има интеракција со корисникот на кој било начин, прилично е добра идеја да се користи самиот корисник како извор на ентропија. На пример, времето на притискање на копче, мерено до најблиската микросекунда (или подобро, неговите најмалку значајни цифри), е целосно непредвидливо. Меѓутоа, често уредот мора да работи автономно, што значи дека го губиме овој прекрасен канал на информации.

Конвертор од аналоген во дигитален

Многу контролери имаат вградени ADC. И во многу контролери тие се со многу просечен квалитет, направени само „да се биде“. Ниските битови од резултатот ADC речиси секогаш содржат значителен шум, дури и ако се мери DC напонот. Ова може да се користи: поврзете го влезот на ADC со напонот за напојување преку делител, изведете неколку десетици мерења, земете ги најмалку значајните битови - еве одличен случаен број за вас. Ако ADC содржи вграден предзасилувач, вклучете го, исто така прави бучава.

Асинхрони генератори

Можете да ја користите разликата во периодите од два несинхронизирани часовници. Повеќето контролери содржат, на пример, тајмер за набљудување. За да се подобри доверливоста, тој се тактира од посебен осцилатор кој не е поврзан на кој било начин со главниот сигнал на часовникот. Доволно е да се брои бројот на циклуси на главниот сигнал на часовникот во еден период на тајмерот на чуварот. Ако ги изберете периодите така што бројачот се прелева многу пати за време на мерењето, можете да добиете прилично случаен број. Недостаток на овој метод е тоа што трае долго време, до неколку секунди.

Часовник во реално време

Доколку шемата има часовник во реално време, можете да ги користите нивните тековни читања за да го иницијализирате PRNG. На пример, со конвертирање на тековниот датум/време во формат на време Unix, веднаш добиваме 32 бита, што никогашнема да се случи повторно, освен ако не земате читања повеќе од еднаш во секунда. Користењето реално време дава уникатност на вредностите, но не дава никаква непредвидливост, па затоа е подобро да се комбинираат овој методсо другите.

RC коло

Доколку контролорот нема ниту еден периферни уреди, освен приклучоците за влез / излез, можете да го направите следново: едната нога е поврзана преку кондензатор со земјата, а преку отпорник - на напонот за напојување. Ако влезовите на контролорот имаат внатрешни отпорници за повлекување, не е потребен надворешен отпорник.

Издаваме сигнал „0“ на оваа порта - кондензаторот е испразнет. Ја префрламе портата во режим на влез - кондензаторот почнува да се полни. Кога напонот на него ќе го достигне прагот, влезот ќе се префрли од состојбата „0“ во „1“. Времето на полнење е многу зависно од многу фактори: напон на напојување, повлекување на параметарот на колото RC, нестабилност на прагот, температура, истекување, пречки. Мерејќи го со доволна точност и земајќи ги најмалку значајните битови, можете да добиете добра случајност.

Хардверски генератор на бучава

За многу сериозни апликации (првенствено криптографија), потребен е посигурен извор на ентропија од оние наведени погоре. Во такви случаи, сигналот се дигитализира од генератор на бучава врз основа на термички, ударни или дури и квантни ефекти. Бучниот елемент обично е специјална диода или зенер диода, сигналот од кој се засилува и се напојува до компаратор кој формира бинарен бит-стрим.

За да може прагот на одговор на компараторот да не влијае на статистичките својства на примениот сигнал, се користат два генератори на шум кои работат на еден компаратор:

Заклучок

Конечно, ќе ви раскажам една приказна од мојот живот. Започна со друго прашање поставено на форумот „како да генерирам случаен број на контролорот?“. Авторот на прашањето објасни што прави уредот што имитира фрлање коцка како проект за курсеви. По неколку неуспешни обиди да ги дознае алгоритмите, топ-стартерот го сподели своето решение: тој едноставно стркала вистинска матрица 1000 пати и ја постигна целата бесплатна меморија на контролорот со добиените броеви. Генераторот ги помина сите тестови за „случајност“ со летечки бои, со оглед на тоа што потроши помалку од една третина од својата „резерва“ за време на демонстрациите.
Затоа, ваквото решение има и право на живот, особено ако се наметнуваат многу строги барања за случајноста на броевите, но тие не се бараат многу често. Со драстично опаѓање на цените на меморијата, можеби е паметно да се складира уред со флеш-драјв „хаос за глава“ што ќе трае цел живот на уредот.
Ти благодарам за вниманието!

UPD1:Како што со право беше забележано во коментарите, ако се претпоставува напад на RNG, а напаѓачот ќе има хардверски пристап до уредот, надворешните извори на ентропија треба да се користат со големо внимание, бидејќи не е многу тешко да се замени сигналот од надворешен извор. Треба да се користат внатрешни извори, можеби покрај надворешните извори.
Исто така, добра идеја е да се акумулира ентропијата на сè слободно време, и користете го кога треба да генерирате друг случаен број. Обично во такви случаи, т.н. Ентропија базен- низа преку која периодично се извршува една од функциите PRNG и каде податоците од изворите на ентропија постојано се мешаат.

UPD2:Во многу случаи, корисно е да се зачува содржината на базенот Ентропија (извинете, не го знам нормалниот руски превод) во EEPROM за да не се акумулира повторно откако ќе го исклучите и вклучите уредот. Ова се однесува, пред сè, за добивање ентропија со методот на асинхрони генератори: при доволно стабилни услови, по секое вклучување, може да се генерира истата низа.
Доколку се очекува напад, преземете мерки на претпазливост да не ја мешате содржината на EEPROM. Ако контролорот дозволува, блокирајте го читањето / бришењето / пишувањето со помош на битови за заклучување, кога е вклучено, контролирајте го интегритетот на EEPROM, барем користејќи ги наједноставните контролни суми.

Тагови:

• rfc
• gpsch
• микроконтролери
• алгоритми

Додадете ознаки

случајно семе (семе)

Поставува вредност, или семе, како почетна точка на функцијата random().

randomSeed(вредност); // поставува „вредност“ како почетна случајна вредност

Бидејќи Arduino не може да генерира вистински случајни броеви, randomSeed ви овозможува да ставите променлива, константа или друга функција во случајната функција, што помага да се генерираат повеќе случајни броеви.

„случајни“ броеви. Постојат многу различни семиња, или функции, кои можат да се користат во оваа функција, вклучително и millis(), па дури и analogRead() за читање на електричен шум преку аналоген пин.

случаен (макс)

случаен избор (мин, макс)

Случајната функција ви овозможува да вратите псевдо-случаен број во опсегот даден со минималните и максималните вредности.

вредност = случаен (100, 200); // ја поставува „вредноста“ на случаен избор

// број помеѓу 100 и 200

Забелешка:Користете го ова откако ќе ја користите функцијата randomSeed(). Следниот пример генерира случаен број помеѓу 0 и 255 и излегува PWM

сигнал до излезот PWM еднаков на случајна вредност:

int randNumber; // променлива за складирање на случајна вредност

int led = 10; // LED со отпорник на пин 10

void setup() () // поставувањето не е потребно

randomSeed(millis()); // поставува millis() како семе

randNumber = случаен (255); // случаен број од 0 - 255 analogWrite(led, randNumber); // излез PWM сигнал

доцнење (500); // пауза половина секунда

Извор: Гололобов В. - Каде започнуваат роботите. За проектот Arduino за ученици (и не само) - 2011 година

Поврзани Мислења

Serial.begin (стапка) Ја отвора сериската порта и ја поставува стапката за сериски пренос на податоци. Типичната брзина на бауд за компјутерска комуникација е 9600, иако се поддржани други стапки на бауд. void setup()( Serial.begin…….

Сите променливи мора да се декларираат пред да се користат. Декларирањето на променлива значи дефинирање на типот на нејзината вредност: int, long, float итн., поставување единствено име на променлива и дополнително…….

Во ред, ја инсталиравме оваа програма. Го дебагиравме „механизмот“ на работа со модулот. И погледнете неколку примери. Но, јас би сакал сам да создадам нешто корисно. Да пробаме. Прво да го затвориме претходниот проект. За ова…….

Внимание! Кога работите со Arduino модулот во други развојни средини, треба да внимавате на конфигурацијата на микроконтролерот (Осигурувачи). Сè додека не знаете до што точно може да доведе промената…….

Време и случајно. Реакција

Овој пат ќе научиме што се „Случајни“ вредности, а исто така ќе научиме како да работиме со времето.

Ќе ни требаат:

• Копче за часовник
• крцкач
• Поврзувачки жици „ПАПА-ПАПА“

Реакција

Нашата задача за денес е да составиме коло што ни овозможува да ја дознаеме брзината на нашата реакција.

Кога ќе го притиснете левото копче, се слуша сигнал по „случајно“ време. И кога ќе го притиснете десното копче, се забележува колку време поминало од чкрипењето до притискање на десното копче.

Кој е вешт - сам пробува, а ние ја гледаме шемата.

#define BUZ 8 #define START 9 #define STOP 7 int time; // Променлива за синхронизација void setup() ( Serial. start (9600); pinMode (START, INPUT_PULLUP); pinMode (STOP, INPUT_PULLUP); pinMode (BUZ, OUTPUT); ) void loop() ( if(digitalRead (START) == 0) // Кога го притискате копчето СТАРТ.. ( int start_time = millis();// Запомнете го времето на притискање = start_time; // Напишете го во глобална променлива. int Rand = random(0, 4000) ; // Генерирајте „случајно“ време на одложување = време + Ранд; //Додадете го одложувањето на времето на одложување (Ранд); // Тон на чекање (BUZ, 3000, 500); //Бип! ) ако(дигиталноЧитај(СТОП) = = 0 && digitalRead( START) == 1)// При притискање на копчето STOP... ( int stop_time = millis(); //Запомни го времето на запирање. време = stop_time - време; // Пресметај ја временската разлика. Сериски .println("Време:"); // Печатете го времето во Сериски. Сериски. println(време); доцнење(1000); ) ) // Пред вториот обид, повторно притиснете го копчето СТАРТ.

Објаснувања

инт време; На променливите (не сите), кога се назначени, не мора да им се додели никаква вредност. Ја користевме оваа променлива за поврзување на две if искази.

Во C++, променливите декларирани во јамката нема да бидат достапни во другите циклуси, бидејќи тие се валидни само во тој циклус. Ова е направено со цел да се спречат програмски грешки. Кога ќе порасне програмскиот код, ќе разберете за што зборувам.

За да направите променлива достапна за повеќе изјави, треба да ја направите глобална. Оние. декларирајте променлива надвор од функциите.

millis ();Го враќа бројот на милисекунди што поминале од започнувањето на програмата.

Ни треба за да го измериме времето поминато од сигнализација до притискање на копчето.

случајно(мин,макс);Тоа е „случаен“ генератор на броеви. Зема две вредности. Тоа генерира број помеѓу min и max.

„Случајни“ броеви бидејќи тоа е одредена низа на вредности. Многу долго, но исто. За да добиете различни секвенци, треба да користите СлучајноСемка();

Таа, функцијата, го иницијализира генераторот. И ако го поставите параметарот на случаен избор, тогаш ќе ги добиеме секвенците што ни се потребни. Истата низа ќе биде ако параметарот е фиксиран.

Заклучок

Сега можете да ја тренирате вашата реакција со помош на вашиот сопствен уред. И можеш да продолжиш.

Список на радио елементи

Означување	Тип	Деноминација	Квантитет	Забелешка	Купувајте	Мојот бележник
	Ардуино плоча	Arduino Uno	1			Во бележник
	Даска за леб	Даска за леб-пола	1			Во бележник
	Пиезо звучник	Пасивно	1			Во бележник
	Копче за часовник	Без држач	2			Во бележник
	Поврзување на жици	„Тато тато“	1