logo elektroda
logo elektroda
X
logo elektroda
REKLAMA
REKLAMA
Adblock/uBlockOrigin/AdGuard mogą powodować znikanie niektórych postów z powodu nowej reguły.

[atmega8][c] Losowanie zadanej części populacji liczb - pomysł

jarekz_2 25 Cze 2011 09:28 2352 12
REKLAMA
  • #1 9647753
    jarekz_2
    Poziom 16  
    k_kudra napisał: (...) stanąłem przed problemem skonstruowania urządzenia, które będzie w sposób losowy załączało wyjście, w dodatku zrobi to dla zadanego procentu losowań (...) chodzi o to aby np na 100 losowań tylko 20 zakończyło się załączeniem wyjścia, ale to 20 występowało losowo wśród wszystkich 100 losowań (...)
    Z tego co piszesz wynika, że dopuszczalne - a wręcz zalecane - będzie użycie liczb pseudolosowych. Ciąg liczb pseudolosowych można generować np. w rejestrze ze sprzężeniem zwrotnym (Linear Feedback Shift Register, LFSR). Rejestr N-bitowy wytwarza ciąg liczb pseudolosowych, powtarzający się, o okresie (2^N)-1. W ramach jednego okresu każda liczba z zakresu od 1 do (2^N)-1 pojawia się dokładnie raz.
    Użycie takich liczb miałoby tę zaletę, że ich ilość leżąca poniżej jakiejś wartości granicznej jest ściśle określona. Przykład: rejestr jest 16-bitowy, wytwarza liczby z zakresu 1...65535, wśród których 20% jest mniejszych niż 13108, 10% - mniejszych niż 6554 itp. A zatem dałoby się zagwarantować, że załączenie wyjścia spowoduje określony, zadany procent (np. 20).
    Zaletą jest też fakt, że używanie takich pseudolosowych liczb nie wymaga "sztuczek" w rodzaju odczytu kanału ADC itp. Wystarczy zrealizować rejestr LFSR i np. co 0,1 sekundy generować w nim kolejną liczbę.
  • REKLAMA
  • #2 9647807
    tmf
    VIP Zasłużony dla elektroda
    Kolego, fajnie, że piszesz post w oderwaniu od tematu. Fajnie, że przeczytałeś parę stron na temat generatorów pseudolosowych. Tylko jeszcze koniecznie przeczytaj co to takiego ziarno i skąd go wziąć.
  • REKLAMA
  • #3 9648168
    jarekz_2
    Poziom 16  
    Kolego, fajnie, że piszesz post w oderwaniu od tematu.
    Nie jest to wcale fajne. Temat został z nieznanych przyczyn zablokowany (o czym informuje symbol kłódeczki z prawej strony; fakt że jest to symbol malutki i może jak widać łatwo ulec przeoczeniu). Dlatego nie było innego wyjścia niż utworzyć temat nowy.
    Tylko jeszcze koniecznie przeczytaj co to takiego ziarno i skąd go wziąć.
    He, he... Czekałem na to pytanie, co prawda spodziewałem się, że pierwszy zgłosi się twórca tematu... Otóż w tym wypadku wystarczyłoby po "resecie" wpisać do rejestru LFSR dowolną (zawsze tę samą) liczbę z wyjątkiem zera. Jeżeli układ ma pracować na "bramce", a generator będzie wytwarzać kolejne liczby w każdej sekundzie kilka razy (a mógłby to bez problemu robić dziesiątki tysięcy razy), to stan generatora w danej chwili byłby dla człowieka praktycznie niemożliwy do przewidzenia.
  • #4 9649572
    tmf
    VIP Zasłużony dla elektroda
    Temat został zablokowany przez twórcę, bo widać uznał informacje za wystarczające.
    Co do drugiej części to całkowicie się mylisz - inicjowanie takich generatorów stałą wartością prowadzi do otrzymania stałego ciągu wyjściowego, nie ma to nic wspólnego nawet z pseud-pseudolosowością. I właśnie problem polega na tym, że nie można wpisać wartości dowolnej, znasz jakąś instrukcję asemblera, któa chociaż w ogólnych zarysach może być opisana jako - wpisz dowolną wartość do rejestru?
  • #5 9649889
    jarekz_2
    Poziom 16  
    tmf napisał:
    Co do drugiej części to całkowicie się mylisz - inicjowanie takich generatorów stałą wartością prowadzi do otrzymania stałego ciągu wyjściowego, nie ma to nic wspólnego nawet z pseud-pseudolosowością.


    Rozwijam temat; moim zdaniem warto:
    Układ generatora, który mam na myśli, to tzw. „rejestr przesuwny z liniowym sprzężeniem zwrotnym”: tu oraz tu.
    Nietrudno znaleźć tam informację, którą podawałem wcześniej, że LFSR o długości N bitów generuje okresowo powtarzający się ciąg, złożony z 2^N-1 różnych stanów (warunkiem jest zainicjowanie takiego generatora wartością różną od zera).
    Najkrótszy ciąg, wytwarzany w rejestrze 2-bitowym, miałby tylko 3 różne stany. Ale już rejestr 32-bitowy, który bez problemu daje się zaimplementować w C, generuje „w kółko” 4294967295 stanów. Natomiast „stały ciąg wyjściowy”, rozumiany jako ciąg tych samych wartości, możliwy byłby tylko po zainicjowaniu generatora zerem!
    W opisywanym projekcie, stan rejestru (zainicjowanego po „resecie” wartością jak najbardziej nieprzypadkową i zawsze tą samą) jest w danej chwili, z punktu widzenia człowieka, praktycznie przypadkowy, przy spełnieniu jednego warunku: kolejne stany rejestru są generowane na tyle szybko by nie mógł za nimi w jakiś sposób nadążyć ewentualny „hacker” - np. co 1ms. Na współczesnym mikrokontrolerze to żaden problem.
    O jednej rzeczy zapomniałem – aby spełnić wymaganie odnośnie ilości procentowej liczb załączających wyjście, od chwili przejścia przez bramkę pierwszej osoby rejestr powinien generować kolejne stany tylko w momentach przejść kolejnych osób.
    tmf napisał:
    I właśnie problem polega na tym, że nie można wpisać wartości dowolnej, znasz jakąś instrukcję asemblera, któa chociaż w ogólnych zarysach może być opisana jako - wpisz dowolną wartość do rejestru?

    Programista wybiera sobie jakąś wartość między 1 a 2^N-1 i inicjuje nią rejestr. Jest to wartość dowolna w tym sensie, że żadna wartość z tego zakresu nie jest uprzywilejowana. Przykład: unsigned long LFSR = 0x12345678;
    Natomiast mikrokontroler, ze “swojego punktu widzenia”, wpisuje do odpowiednich komórek pamięci wartości jak najbardziej zdeterminowane.
    No - gdyby wpisywał tu i ówdzie wartości „dowolne”, to ładnie byśmy wyglądali… A i owszem, widziałem kiedyś kalkulator, który dawał wyniki „trochę dobre, a trochę przypadkowe”, np. 5 x 7 bywało raz równe 38, a za drugim razem np. 29…

    A poważnie - mam nadzieję że teraz wszystko się wyjaśniło.
  • REKLAMA
  • #6 9650022
    tmf
    VIP Zasłużony dla elektroda
    Wszyscy tu wiedzą jak działa taki generator, jednak wymaga on losowego ziarna. Inaczej masz za każdym razem taki sam ciąg liczb i nic więcej. Czyli w praktyce, w omawianym układzie, po każdym resecie kolejne numery wybierane do kontroli byłyby takie same, czyli np. po każdym włączeniu urządzenia osoby 1, 20, 22, 33 itd. byłyby losowane. Co z tego, że miałbyś 2^32 takich liczb? Już pomijam oczywistą rzecz, że takie generatory są wyjątkowo kiepskie. Łatwo się o tym przekonać rysując punkty w "losowo" wygenerowanych miejscach. Pouczające doświadczenie. W C, w tym w AVR-gcc takie generatory są zaimplementowane, ale w praktyce się do niczego nie nadają, zresztą nie podejrzewam, że pytający nie zna funkcji języka C rand. Skoro więc zadał o to pytanie to pewnie stwierdził, że to rozwiązanie jest OKDR.
  • #7 9650266
    jarekz_2
    Poziom 16  
    tmf napisał:
    Wszyscy tu wiedzą jak działa taki generator, jednak wymaga on losowego ziarna. Inaczej masz za każdym razem taki sam ciąg liczb i nic więcej.

    A czy to w tym wypadku przeszkadza?
    tmf napisał:
    (...)po każdym resecie kolejne numery wybierane do kontroli byłyby takie same, czyli np. po każdym włączeniu urządzenia osoby 1, 20, 22, 33 itd. byłyby losowane.

    No to teraz już wiem, że robisz sobie jaja.
    „Kloss, udając że zapina but, zaobserwował że zasilanie sterownika bramki włączono o 6:58.21,018. Wiedział, że LFSR zaczął „tykać” 719ms później. Odczekał cztery minuty i ruszył raźnym krokiem w stronę bramki. Szedł z prędkością 1,357732m/s, a bramkę przeszedł dokładnie o 7:03.01,549. Tak jak oczekiwał - nie skierowano go do rewizji. Stan generatora wynosił bowiem wtedy 0xB610C43D i leżał znacznie powyżej granicy 20%. Kloss uśmiechnął się pod nosem: co za prymitywny system…”
    Kończąc:
    Temat odświeżyłem, by uzmysłowić koledze k_kudra fakt, iż nie musi on wcale w swojej aplikacji inicjować generatora wartością losową (co jest na pewno bardziej kłopotliwe niż inicjowanie go przez stałą). Cała ta historia potwierdza pewne moje spostrzeżenie: dla średnio zaawansowanych elektroników typowe jest stosowanie sposobów podręcznikowych, „kanonicznych”, choć często przypomina to przysłowiowe strzelanie z armaty do wróbla. A zaletą forum dyskusyjnego jest to, że może znaleźć się ktoś, kto wskaże prostszą drogę.
  • REKLAMA
  • #8 9650742
    tmf
    VIP Zasłużony dla elektroda
    Widzisz kolego, tak to jest jak się pisze o czymś czego się nie rozumie. To co powyżej opisałeś to wprowadzenie entropii, tyle, że nie pochodzącej z szumu ADC, ale z szumu czasowego. Jaka jest różnica? Żadna, po prostu na około chcesz zrobić coś co można zrobić wprost. Jasno jednak widać, że żaden magiczny rejestr nie pomoże, musi być losowe ziarno, lub w inny sposó wprowadzona entropia do układu.
  • #10 9654812
    ktrot
    Poziom 20  
    Fajny pomysł z tym ADC - nie dość, że generuje losowe liczby to jeszcze spowoduje losowe zachowanie procesora w zaszumionym środowisku.
    Tak na poważnie, odradzam zostawianie wysokich impedancji na wejściu - wszystkie nieużywane piny jako wyjście i do masy (albo vcc).

    Ziarno dla generatora pseudolosowego nie musi być losowe - wystarczy brać różne za każdym włączeniem. Przkładowe rozwiązanie:
    Na początku, po włączeniu (lub resecie) procesora wykonujemy:

    1. Odczytaj ziarno z eeprom.
    2. Ustaw srand(ziarno).
    3. ziarno++;
    4. Zapisz ziarno do eeprom.

    Krok 3 można skomplikować ale do wielu zastosowań wystarczy tak prosto bo sekwencje liczb generowanych po srand(n) i srand(n+1) nie są w widoczny sposób skorelowane.
    Po 65tys. włączeń sekwencja generowanych liczb się powtórzy ale przy np średnio 20 resetów/dzień powtórzy się po 10 latach. EEprom wytrzyma dłużej.
  • #12 9655226
    tmf
    VIP Zasłużony dla elektroda
    ktrot napisał:
    Fajny pomysł z tym ADC - nie dość, że generuje losowe liczby to jeszcze spowoduje losowe zachowanie procesora w zaszumionym środowisku.
    Tak na poważnie, odradzam zostawianie wysokich impedancji na wejściu - wszystkie nieużywane piny jako wyjście i do masy (albo vcc).

    Chuba raczej jako wejście, jeśli łączysz je do masy lub Vcc. Inaczej będziesz miał zwarcie. Z tego też powodu ustawienie pinu jako wyjście jest ryzykowne. Kosztem nieznacznego wzrostu poboru energii lepiej piny nieużywane zostawić jako wejścia z włączonym rezystorem podciągającym.

    ktrot napisał:
    Ziarno dla generatora pseudolosowego nie musi być losowe - wystarczy brać różne za każdym włączeniem. Przkładowe rozwiązanie:
    Na początku, po włączeniu (lub resecie) procesora wykonujemy:

    1. Odczytaj ziarno z eeprom.
    2. Ustaw srand(ziarno).
    3. ziarno++;
    4. Zapisz ziarno do eeprom.

    Krok 3 można skomplikować ale do wielu zastosowań wystarczy tak prosto bo sekwencje liczb generowanych po srand(n) i srand(n+1) nie są w widoczny sposób skorelowane.
    Po 65tys. włączeń sekwencja generowanych liczb się powtórzy ale przy np średnio 20 resetów/dzień powtórzy się po 10 latach. EEprom wytrzyma dłużej.


    Bo ja wiem, zauważ, że zasadniczo po każdym losowaniu musiałbyś zapisywać ziarno, w przeciwnym przypadku, po kolejnym włączeniu, sekwencja losowanych liczb od ostatniego zapisu ziarna by się powtórzyła. W efekcie trzeaby wprowadzić dodatkowe źródła entropii. Z kolei częsty zapis do EEPROM jest niepraktyczny, bo raz, że ta pamięć ma ograniczoną trwałość, a dwa, że zapis jest wolny. Oczywiście dużo zależy od zastosowania, i w pewnych uproszczenie jakie podałeś będzie ok.
    Należy też pamiętać, że szczególnie w AVR-libc wbudowany generator jest prosty i powtarzalny, tak naprawdę do niczego poważniejszego się nie nadaje i należałoby napisać własną funkcję rand().
  • #13 9655393
    ktrot
    Poziom 20  
    Cytat:
    Chuba raczej jako wejście, jeśli łączysz je do masy lub Vcc. Inaczej będziesz miał zwarcie


    Fakt, źle się wyraziłem - do masy lub vcc wewnętrznie - czyli pisząc po ludzku ustawiamy jako wyjście i 0 (do masy) lub 1 (czyli do vcc). Absolutmie nie zamierzałem polecać zewnętrzne podłączanie do masy. To czy jako wejście z podciąganiem to kwestia ilośći zewnętrznych zakłóceń: jeżeli impedancja ok 20k wystarczy to wejście z podciąganiem, jeżeli nie to wyjście (impedancja ok 40ohm).



    Cytat:
    po kolejnym włączeniu, sekwencja losowanych liczb od ostatniego zapisu ziarna by się powtórzyła

    Dlaczego ma się powtórzyć? Z każdym włączeniem jest inne ziarno (choćby i kolejne)
    Ustawienie srand(2) generuje liczby pseudolosowe a1,a2,a3,a4...
    ale srand(3) nie generuje liczb a2,a3,a4...tylko własny ciąg b1,b2,b3...
    Tak samo postępujesz jak potrzebujesz dłuższy ciąg liczb pseudolosowych - normalnie dla jednego ziarna masz ich chyba 65tys. (nie jestem tego pewien) więc jak potrzebujesz więcej to zmieniasz ziarno przed kolejnym losowaniem. Sekwencja powtórzy się oczywiście po obróceniu ziarna.
REKLAMA