[8085] 16 bitowy generator przebiegów losowych

[gaweł]

16 bitowy generator
przebiegów losowych

Potrzebuję 16-bitowego generatora przebiegów losowych. Jego głównych przeznaczeniem jest diagnostyka elektronicznych układów w czasie pracy w warunkach losowych i niepewnych. Wymyśliłem sobie, że zbuduję odpowiednią aparaturę pozwalającą na generowanie owych przebiegów. Ujmując to w skrócie, jest procek, który będzie generował na porcie równoległym przebieg losowy. Pogrzebałem w swojej szufladzie i padło na 8085. Zagadnienie nie jest aż tak złożone jakby mogło się wydawać a jego moc obliczeniowa w zupełności wystarczy. A z drugiej strony, to będzie miał okazję się wykazać zamiast oddawać się nieróbstwu w szufladzie.
Zanim przejdę do etapu budowy, to zrobiłem sobie badania symulacyjne. Można zaproponować wiele algorytmów dających różne rozkłady generowanych liczb. Mnie interesuje rozkład równomierny, czyli ma zostać wygenerowanych 65536 liczb i żadna nie może się powtórzyć (czyli ma wystąpić każda możliwa kombinacja). Na taką okoliczność ludzkość dopracowała się wzoru:
X_new = M * X_old + Aczyli każda nowa liczba jest otrzymywana z poprzedniej poprzez pomnożenie jest przez stałą (stała multiplikatywna) i dodaniu innej stałej (stała addytywna). Oczywiście wystąpi problem pierwszej liczby losowej, ale to daje się rozwiązać w miarę prosty sposób. Przykładowo w przerwaniach od czasu inkrementowana jest zmienna w pamięci i jak użytkownik wciśnie przycisk „Start”, to stanowi ona wystarczająco dobrą startową zmienną losową.
By wiedzieć co w trawie piszczy i dokąd to zmierza, napisałem sobie w C program na PC do podstawowych badań. Z eksperymentów wyłonił się istotny wniosek: nie każda wartość stałych M i A daje oczekiwany rozkład generowanych liczb. Programik jest następujący:

Kod: Zaznacz cały

/*
       Test 16-bitowego generatora liczb losowych
       napisał: gaweł
       Białystok, 04.2023
       Licencja: CC BY 3.0
*/

#include <stdio.h>
#include <stdlib.h>

#define TabSize 0x10000

#define MultConst 65
#define AddConst 17

FILE * OutFile ; 
unsigned short Status [ TabSize ] ;

int main(int argc, char *argv[])
{
  unsigned long Loop ;
  unsigned short RandomV ;
  /*----------------------------------------------------------------*/
  OutFile = fopen ( "random.txt" , "w" ) ;
  for ( Loop = 0 ; Loop < TabSize ; Loop ++ )
    Status [ Loop ] = 0 ;
  RandomV = 1234 ;
  fprintf ( OutFile , "Badania losowosci: stala multiplikatywna=%d, stala addytywna=%d\n" , MultConst , AddConst ) ;
  for ( Loop = 0 ; Loop < TabSize ; Loop ++ )
  {
    RandomV = ( ( MultConst * RandomV ) + AddConst ) ;
    fprintf ( OutFile , "Liczba losowa numer %d=%d\n" , Loop , RandomV ) ;
    Status [ RandomV ] ++ ;
  } /* for */ ;
  for ( Loop = 0 ; Loop < TabSize ; Loop ++ )
  {
    fprintf ( OutFile , "Krotnosc liczby %d=%d\n" , Loop , Status [ Loop ] ) ;
  } /* for */ ;
  fprintf ( OutFile , "Tropienie statystyki\n" ) ;
  for ( Loop = 0 ; Loop < TabSize ; Loop ++ )
  {
    if ( Status [ Loop ] == 0 )
      fprintf ( OutFile , "blad liczba %d nie wygenerowala\n" , Loop ) ;
    if ( Status [ Loop ] > 1 )
      fprintf ( OutFile , "blad dla liczby %d wygenerowala się %d razy\n" , Loop , Status [ Loop ] ) ;
  } /* for */ ;
  fprintf ( OutFile , "Koniec statystyki\n" ) ;
  fclose ( OutFile ) ;
  return 0;
}

Z badań wynika, że najlepiej jest jak obie stałe są liczbami nieparzystymi. Przykładowo dla M=128 i A=9 program wpadł w pętlę i nie mógł się z niej wyrwać. Generował w kółko liczbę 17545 (17545 * 128 + 9 = 2245769, co po obcięciu do 16 bitów daje 17545). Zmiana stałej na M=129, A=9 daje już bardzo dobre rezultaty (żadna liczba się nie powtórzyła, zatem wystąpiło 65536 różnych liczb).
Również dobrze wypadły następujące pary: M=1025 A=7, M=1025 A=9, M=129 A=9, M=257 A=31, M=257 A=33, M=65 A=17, M=65 A=7. Dobór stałej M ma fundamentalne znaczenie. Starłem się dobrać stała multiplikatywną jako 2 do potęgi 0 plus 2 do potęgi jakiejś. To daje bardzo prostą realizację operacji mnożenia w prockach, które nie mają wymaganych instrukcji. By wyliczyć przykładowo nową liczbę dla parametrów M=257 i A=33 [X_new=257 * X_old + 33 = (256 +1 ) * X_old + 33 = X_old * 256 + X_old + 33], mamy tylko sumowanie i operacje przesunięcia (nadaje się nawet dla 8085, który nie wiem, czy nawet wyciąga jednego MIPS’a).

Jeżeli ktoś jest zainteresowany wynikami badań, to zapraszam do lektury:

random.7z

[piotrek]

Sposób, który zaimplementowałeś znany jest pod nazwą LGC (linear congruential generator).
Podobny pod względem matematycznym jest LFSR (Linear-feedback shift register), który można zaimplementować sprzętowo za pomocą rejestrów przesuwnych i bramek xor (tak jest robione w FPGA), a także software'owo z użyciem operatorów przesunięcia bitowego (szybszych niż mnożenie czy modulo).

Jeżeli ten ciąg permutacji puszczony w losowej kolejności ma być za każdym razem inny, to myślę, że ten sam efekt można uzyskać po prostu losując za każdym razem jedną liczbę z podanego przedziału.

[gaweł]

można zaimplementować sprzętowo za pomocą rejestrów przesuwnych i bramek xor (tak jest robione w FPGA), a także software'owo z użyciem operatorów przesunięcia bitowego (szybszych niż mnożenie czy modulo).

Zgadza się, ale FPGA zrobiło się koszmarnie drogie, więc jest to redukcja kosztów oraz jest tu przewidzianych kilka funkcji, o których nie napisałem.

[gaweł]

Tak zagłębiając się filozoficznie w temat generacji liczb losowych nasuwa się pytanie: na ile jest losowe to zdarzenie? Niby tworzące się ciągi bitowe są w jakimś stopniu przypadkowe, ale z drugiej strony w rzeczywistości wszystko jest ściśle zdeterminowane, gdyż nowe elementy wynikają z określonego algorytmu. Poznanie tej formuły pozwala określić jaki będzie następny element, więc pozostaje do rozkminy problem o determinizmie zdarzeń.
Jednak wracając do budowy generatora, konstrukcja wygląda następująco: jest procek z podstawowymi elementami niezbędnymi do jego działania, pamięć RAM oraz pamięć EPROM, zespół portów przewidziany do współpracy z otoczeniem. Z grubsza to wygląda tak:

rnd0.png

Zespół procka przedstawia się następująco:

rnd1.png

Sam procek 8085, który jak wiadomo, ma wbudowany generator taktu zegarowego, więc w prostym rozwiązaniu wystarczy podłączyć rezonator kwarcowy. Użyty 8085 może poginać z częstotliwością 3MHz (są szybsze, ale mój jest taki), jednak zastosowałem rezonator z w miarę okrągłą częstotliwością (4MHz). Sam procek wewnętrznie dzieli ją przez dwa. Okrągłość częstotliwości wynika z w miarę prostych rachunków dla timera by regulować tempo generowania ciągów bitowych. Z tego powodu w układzie znalazł się układ 8253, który będzie generował przerwania dla proca. By nie tworzyć zbyt rozbudowanego rozwiązania, wykorzystane jest wejście przerwania RST7.5 (jest to wejście z reakcją na zbocze sygnału przerywającego). Pozostałe reagują na poziom, więc konieczne byłoby dorobienie rozwiązania by stworzyć wariant reakcji na zbocze. A ponieważ jest tylko jeden sygnał przerywający, to pozostałe są niewykorzystane.
Procek 8085 ma tą przypadłość, że ma multipleksowaną szynę danych (współdzieloną z młodszą częścią adresowej). Z tego powodu występuje rejestr (dokładnie zatrzask) do uzyskania młodszej części adresu.
Do obsługi pamięci i portów są użyte dwa układy do generowania sygnałów wyboru. W przypadku pamięci to na zakresie adresowym 0000H .. 7FFFH odzywa się EPROM oraz na zakresie 8000H..FFFFH pukamy do pamięci RAM. Podobne rozwiązanie występuje przy obsłudze portów. Mamy trzy porty: 8253 i dwie sztuki 8255. By wygenerować chipselekty do wszystkich układów, sam dekoder adresowy również musi zostać odpowiednio „odpalony”. Procek do tego generuje kilka sygnałów: IO/M oraz S0 i S1. To pozwala na szczegółowe rozróżnienie cykli wykonywanych przez procka, ale z drugiej strony konieczna jest dodatkowa logika bramkowa. W moim wariancie wystarczy informacja, że procek pisze lub czyta do pamięci względnie portów (nie zależy mi na informacji, że jest w fazie fetch [M1 w wariancie ziloga] i temu podobnych).

rnd2.png

Pamiątki, to trywialna sprawa. Występuje drobne urozmaicenie: można zastosować układ 27128 lub 27256. Sprowadza się to do tego, że na pin 27 należy podać kolejny bit adresu lub podłączyć go do +5V.

rnd3.png

Porty do wyjścia liczb losowych: koncepcja wręcz trywialna: zapis do portu 8255. Jednak moim wymaganiem jest by na wyjściu wszystko pojawiło się jednocześnie. Wiadomo, że 8-bitowy procek nie jest w stanie tego zrobić, więc są zastosowane dwa rejestry, które jednym (wspólnym) sygnałem przepiszą wynik z 8255 do rejestrów wyjściowych. Akcja staje się jednoczesna i niepodzielna. Trzeci port z układu 8255 steruje różnymi jednobitowymi sygnałami (jak przykładowo przepisanie danych do rejestrów wyjściowych). By „świat zewnętrzny” wiedział o nadchodzących zmianach, wychodzi sygnał strobu (przepuszczony przez bramkę, by ochronić samego 8255 przez nieszczęściem czyhającym na zewnątrz). Strob na zewnątrz jest generowany niezależnie od strobu przepisania danych i może być programowo określony, że nowe dane nas zewnątrz sygnalizowane są narastającym lub opadającym zboczem tego sygnału. Pozostałe sygnały z portu C sterują diodami LED.

rnd4.png

Drugi port 8255 jest przewidziany do poganiania modułem alfanumerycznym LCD oraz małą klawiaturka matrycową.

rnd5.png

Całość danych wychodzi na display LED’owy oraz na złącze na zewnątrz.

[Zegar]

Wyszło całkiem rozległe urządzenie... W dodatku 100% retro. Ale LCD można sterować bezpośrednio z magistrali i znacznie uprościć, a więc również przyspieszyć, jego obsługę. Z Z80 działa, więc tutaj też powinno. Nie ma M1, ale to nie wada lecz zaleta. Bramka jest potrzebna tylko do negacji CS.

LCD-direct.png

[gaweł]

Wyszło całkiem rozległe urządzenie... W dodatku 100% retro.

No bo to miało być retro. Z wiekiem człowiek dziecinnieje i wraca do minionych czasów. Wtedy właśnie takimi prockami się zajmowałem . Poza tym, jak nie zużyję tych układów, to będę musiał je wyrzucić. Serce mnie zaboli jak będę musiał to zrobić więc łączę przyjemne z pożytecznym.

Ale LCD można sterować bezpośrednio z magistrali i znacznie uprościć, a więc również przyspieszyć, jego obsługę. Z Z80 działa, więc tutaj też powinno. Nie ma M1, ale to nie wada lecz zaleta. Bramka jest potrzebna tylko do negacji CS.

Coś podobnego robiłem z AVR (na ATM8515, bo on ma możliwość dopięcia zewnętrznej RAM) i moduł był właśnie komórką pamięci (tak jak w Ciebie). Trzeba było dać mniejszą częstotliwość taktującą, bo taki moduł udaje dosyć powolna pamięć RAM. W 8085 powinno się udać, bo 2MHz taktu daje czas dostępu większy niż 500ns.
No LCD jest trochę słabo pasujący do retro, ale potrzebuję wyświetlić trochę informacji alfanumerycznych. Chociaż ... natchnąłeś mnie pewną koncepcją rozwiązania retro. Sprawa jest jeszcze otwarta i można wnieść jeszcze korekty. Wszystko jeszcze przed nami.

[Zegar]

Coś podobnego robiłem z AVR (na ATM8515, bo on ma możliwość dopięcia zewnętrznej RAM) i moduł był właśnie komórką pamięci (tak jak w Ciebie). Trzeba było dać mniejszą częstotliwość taktującą, bo taki moduł udaje dosyć powolna pamięć RAM. W 8085 powinno się udać, bo 2MHz taktu daje czas dostępu większy niż 500ns.

CS mam z IORQ, więc to normalne peryferium. Sprawdziłem na 4 MHz i 8 MHz i daje radę. Może nowe HD44780 są szybsze?

Wszystko jeszcze przed nami.

Coraz trudniej kupić "ładne" stare kości, więc na pewno ktoś by je chętnie przytulił.

[mokrowski]

Tu masz parametry dla LFSR od Xilinxa: https://docs.xilinx.com/v/u/en-US/xapp052 Nadają się oczywiście także do implementacji programowej (kiedyś jakiejś używałem w projektach dla klienta)
Trochę podstawowe, ale użyteczne jako punkt startu dla LCG: https://en.wikipedia.org/wiki/Linear_co ... _generator
Bardzo przystępny wykład odnośnie rand_gen: https://www.youtube.com/watch?v=45Oet5qjlms&t=2s
Cała strona dobra, ale to podsumowanie: https://www.pcg-random.org/index.html

Co do zasiewu lub entropii, z braku dedykowanego układu źródła szumów, można zastosować antenę na pływającym wejściu ADC. Czasem także konkretne MCU mają braki determinizmu np. na etapie operacji z EEPROM lub innych peryferiów. Ogólnie wszystko co szumi warto wstrzyknąć do procedury generacji....

[gaweł]

Próbowałem pokynarzyć swój projekt, no idzie to opornie.

kyn.jpg

Wygenerowała się taka liczba problemów i pomyłek, że kur...ica mnie wzięła. Postanowiłem przejść na lepszy level i zamiast walczyć z drucikami, zrobiłem PCB.

random-bcu.png

random-fcu.png

random-fsil.png

[gaweł]

No i nadeszła ta historyczna chwila...
Przyszła płytka PCB

rndf01.jpg

którą cierpliwie polutowałem i zbudowałem generator przebiegów losowych. Wszystko jest zgodnie z zasadami jakie obowiązywały w dawnych czasach.

rndf02.jpg

Teraz zostało trochę powalczyć z softem.

[gaweł]

Pomógł przypadek

No i nadeszła ta chwila, by dokończyć to co zostało rozpoczęte. Układ polutowany i gotowy do kontynuacji prac (no trochę mu się przeleżało). Pierwszy odpał nie obył się bez problemów. Na początek zauważyłem jakieś dziwności w obwodzie resetowania:

rnd3-01.png

Napięcie na kondensatorze od resetu nie miało ochoty podskoczyć powyżej 3,5V, nawet jak wyjąłem procka. Znaczy się, że kondek ma dużą upływność? Wyrwałem chwasta i dałem nowy. Teraz jest tak być powinno.

rnd3-02.png

W tego typu konstrukcjach, by nie walczyć z wiatrakami, to należy mieć pewność, że procek ma zabezpieczone właściwe warunki do pracy → znaczy, że dostaje dobry sygnał zegarowy. Włączam procka do prądu (na razie nic się nie grzeje, to dobry znak na przyszłość) oscylek pokazuje, że procek nawiązał jakąś tam kooperację z rezonatorem kwarcowym… ale moją uwagę przykuł wynik pokazany przez oscylka. Przy 4MHz kwarca powinno na pinie 37 (rysunek schematu wyżej) wychodzić 2 MHz, a tu jest

rnd3-03.png

jakieś niecałe 25 kHz. Trochę rozkminy, może kwarc jakiś nie teges (jak kondek z resetu). I tak całkiem przypadkiem, macając płytkę (macanie zawsze ma duży potencjał) zauważyłem, że procek nagle wypuścił 2 MHz’y na swoim wyjściu.

rnd3-04.png

Tak przyszło mi do głowy, że mu brakuje czegoś. Przypomniałem sobie, że czasami równolegle z kwarcem stosowany jest duży rezystor, no to wlutowałem równolegle do kwarca 100 kΩ, choć intelowe materiały jakoś nie pisały o tym.

rnd3-05.png

No i pomogło skutecznie. Każdorazowy odpał zasilania prowadził do wygenerowania właściwego sygnału zegarowego. Ot i taka to zagadka.

[gaweł]

Kolejny krok do celu

rnd4-00.png

Mój procek umie już „mówić”, troszkę podgoniłem softa i nawet ruszył bez większych problemów. Znaczy wcześniej sprawdziłem na oscylku, czy łączy się z portami, takie zapętlone input z portu (każdego, jaki występuje w konstrukcji), no i oscylek mówi, że jest OK (są chipselekty). Skoro tak, to podłączyłem moduł LCD.

rnd4-01.png

Jak się później okazało, zabanglał z pierwszego kopa, ale wcześniej trochę musiałem się nakręcić potencjometrem od kontrastu: za pierwszym razem pojechałem nie w tą stronę i doszło do bandy. Z lekką obawą pokręciłem w drugą stronę i już myślałem, że będą problemy, gdy układ mnie zaskoczył i pojawił się napis. Prawdę mówiąc, to przełożyłem na intelowego asma istniejące procedury z avr’owego C, gdzie obsługa była sprawna. No jak się okazało, nawet się nie pomyliłem przy przekładzie.

rnd4-02.png

Do pracy wykorzystałem swój stary emulator eprom, który, jak widać nie doczekał się jeszcze obudowy. No kiedyś to nastąpi, będzie musiało.

rnd4-03.png

No teraz czeka mnie potyczka z układem 8253 i przerywadło od czasu.