Zadanie 1: Dzielnik

Data ogłoszenia: 27.10.2020

Termin oddania: 24.11.2020

Szablon rozwiązania i testy: divider_template.py

Napisać moduł dzielący dwie liczby bez znaku przez siebie.

Moduł powinien mieć:

  • parametr width określający szerokość wejść i wyjść w bitach

  • wejście a, width-bitowe bez znaku: dzielna

  • wejście b, width-bitowe bez znaku: dzielnik

  • wejście start, 1-bitowe: sygnał startu. Gdy to wejście będzie równe 1, dzielnik powinien rozpocząć dzielenie.

  • wyjście busy, 1-bitowe: powinno być ustawione na 1 gdy dzielnik jest zajęty, zaczynając od cyklu po ustawieniu start, a kończąc gdy wynik jest gotowy.

  • wyjście q, width-bitowe: wynik dzielenia (a / b)

  • wyjście r, width-bitowe: reszta z dzielenia (a % b)

  • wyjście err, 1-bitowe: ustawione jeśli wystąpił błąd dzielenia (b jest równe 0); q i r mogą mieć w takim wypadku dowolną wartość

Protokół użycia dzielnika jest następujący:

  1. Po resecie, dzielnik nic nie robi (busy jest równe 0).

  2. Dopóki start jest równe 0, dzielnik nic nie robi (nie zmienia stanu wyjść, itp).

  3. Gdy busy jest równe 0, użytkownikowi wolno rozpocząć operację dzielenia przez ustawienie wejść a i b oraz ustawienie start na 1. Dzielnik rozpocznie dzielenie w następnym cyklu zegara. Od następnego cyklu dzielnik ustawi też busy na 1 (chyba, że będzie w stanie dać wynik w jednym cyklu zegara).

  4. Dopóki dzielnik liczy, busy jest ustawione na 1, a użytkownikowi nie wolno ustawić start na 1. Stan wyjść może się dowolnie zmieniać w tym czasie.

  5. Gdy dzielnik policzy wynik, ustawia busy na 0. W tym samym cyklu ustawia również err, q i r na wyliczony wynik (nie musi ustawiać q i r jeśli nastąpił błąd).

Dzielenie jest skomplikowaną operacją — nie należy próbować zrobić dzielnika działającego w jednym cyklu (z wyjątkiem szczególnych przypadków, jak np. wykrywanie błędów), gdyż spowoduje to po prostu zbyt długą ścieżkę krytyczną w realizacji sprzętowej i będzie bardzo ograniczało maksymalną częstotliwość zegara.

Istnieje wiele ciekawych algorytmów dzielenia do realizacji sprzętowej. Na potrzeby tego zadania wystarczy użyć prostego algorytmu liczącego jeden bit wyniku na cykl:

r = a;
q = 0;
for (pos = width-1; pos >= 0; pos--) {
    bool bit = (r >= (b << pos));
    if (bit)
        r -= b << pos;
    q = q << 1 | bit;
}