Pytanie do wywiadu VHDL - wykrywanie, czy liczbę można podzielić przez 5 bez reszty

Widziałem ładne pytanie do wywiadu dla VHDL - zbuduj system, który odbiera liczbę i wykrywa, czy można ją podzielić przez 5 bez reszty. Próbowałem rozwiązać to za pomocą automatu stanów (przypuszczam, że nie chcą, abyś używał modów lub remów ) i chociaż odniosłem początkowy sukces (liczby takie jak 5, 10, 15 i liczby takie jak 20, 40, 80 działały ), inne liczby, takie jak 130, 75 itd., zawiodły dla mnie.

Chciałbym pokazać moją maszynę stanów, ale to kompletny bałagan (to nie kod, to rysunek) i, jak powiedziałem, nawet nie działa.

Zasadniczo starałem się zapisać liczby binarne, które można podzielić przez 5, i zbudować maszynę stanu, która będzie dla nich działać.

Byłbym szczęśliwy, gdybyś mógł pokazać mi, jak rozwiązać ten problem i jak myśleć, gdy staje się coś takiego.

Dziękuję Ci!

Wykonanie pozostałej operacji seryjnie jest w rzeczywistości dość łatwe. Kluczowym założeniem jest to, że dane przychodzą najpierw do MSB, jeśli są szeregowe. Potrzebujesz tylko stanów N, aby obliczyć resztę modulo N. Zacznij od stanu „0”, a jeśli skończysz w stanie „0” po ostatnim bicie (nie ma znaczenia, ile jest bitów), reszta to zero.

^{symulacja tego obwodu - Schemat utworzony za pomocą CircuitLab}

Pomyśl o tym, jak zrobiłbyś długi podział, gdyby jedyną rzeczą, którą musisz śledzić, była reszta:

process (clk)
begin
  if rising_edge(clk) then
    if reset = 1 then
      state <= 0;
    else
      if (state & din) >= N then
        state <= (state & din) - N;
      else
        state <= state & din;
      end if;
    end if;
  end if;
end process;

Możesz także zaprojektować maszynę stanową, jeśli dane pochodzą najpierw od LSB:

Istnienie takiego deterministycznego automatu skończonego (DFA) wynika bezpośrednio z innej odpowiedzi , która opisuje DFA dla MSB-first. Ponieważ języki akceptowane przez DFA są zwykłe, a znane języki są zamknięte w trakcie cofania (np. Patrz tutaj ), musi istnieć DFA, który akceptuje następujący język:

.$L = \{w\in \{0,1\}^* |\ \text{reverse}(w)_{10}\ \text{is divisible by }5\}$

Budowa

1. Skopiuj pierwszy MSB DFA z odpowiedzi Dave'a Tweeda . Użyłem narzędzia automatycznego JFLAP .

2. Zastosuj jawny algorytm transformacji dla zamian DFA, np. Jak opisano w CS.SE: Projektowanie DFA i jego odwrotność .
   Możesz zobaczyć (niezminimalizowany) wynik tego kroku w starej wersji tej odpowiedzi.

3. Zminimalizuj wynikowy DFA. Niestety, ta funkcja jest trochę wadliwa w najnowszej wersji JFLAP, więc zrezygnowałem z jej ręcznego minimalizowania.
   Znów istnieje wiele algorytmów i źródeł dla nich. Użyłem tego opisanego w „Minimalizacji DFA” na tutorialspoint.com .
   
   (W rzeczywistości, jeśli twoje oczy są wystarczająco dobrze wyszkolone w patrzeniu na DFA, możesz bezpośrednio zobaczyć, że i q $q_0$$q_1$ są równoważnymi stanami w DFA, jak uzyskano w punkcie 2. Moje nie są, dziękuję, że zauważyłeś, że to idzie do komentarza superkata !)

Rzeczywiście, wynikowy automat daje prawidłowe odpowiedzi:

$A_{rev5} = (Q, \Sigma, \delta, q_0, F)$$Q = \{q_0, q_1, q_2, q_3, q_4\}$$\Sigma = \{0,1\}$$F = \{q_0\}$$\delta$

$\delta(q_0, 0) = q_0,\quad\delta(q_0, 1) = q_1\\ \delta(q_1, 0) = q_4,\quad\delta(q_1, 1) = q_3\\ \delta(q_2, 0) = q_1,\quad\delta(q_2, 1) = q_2\\ \delta(q_3, 0) = q_2,\quad\delta(q_3, 1) = q_4\\ \delta(q_4, 0) = q_3,\quad\delta(q_4, 1) = q_0$

Jednym ze sposobów wymyślenia automatu stanowego (MSB first) jest:

1. Dotychczas otrzymano numer N. Załóż, że znasz resztę M = N mod 5.

2. Nadchodzi nowy bit i nowa wartość jest teraz N' = N*2 + b.

3. Nowa reszta jest wtedy M' = (N*2 + b) mod 5 = (M*2 + b) mod 5.

Łatwo jest to zestawić ręcznie:

    M b | M
------------------
    0 0 | 0
    1 0 | 2)
    2 0 | 4
    3 0 | 1
    4 0 | 3)
    0 1 | 1
    1 1 | 3)
    2 1 | 0
    3 1 | 2)
    4 1 | 4

Który pasuje do automatu stanowego w odpowiedzi Dave'a Tweeda.

Mam nadzieję, że pytanie w wywiadzie dotyczyło sposobu rozwiązania problemu, a nie tajników VHDL lub Verilog. Szczegóły języka są proste, gdy masz już algorytm.

$S=0$$S \leftarrow (2 S + d) \text{ mod } 5$ $S$$S,d$$S=0,\cdots, 4$

$S=0, k= 0$$S \leftarrow (S + 2^k d) \text{ mod } 5 , k \leftarrow k+1$$k$$2^4 = 1 \text{ mod } 5$$S \leftarrow (S + 2^k d) \text{ mod } 5 , k \leftarrow (k+1) \text{ mod } 4$$S,k,d$$(S,k)$$S=0,\cdots, 4$$k=0,\cdots, 3$

W zależności od tego, dla czego jest napisany VHDL, możesz zastosować podejście, które opisuje go jako bezpośrednie obliczenie kombinacyjne. Otrzymanie numeru może oznaczać, że cały numer będzie w rejestrze dla jednego cyklu zegara.

Możesz na przykład zanotować mod 5 wartości, którą reprezentują każdy z bitów, dodać je razem, a następnie powtarzać proces, aż pozostanie coś mniejszego niż 5. Albo zaimplementuj to łącznie dla wszystkich etapów redukcji, lub ponownie użyć logiki dla niewielkiej liczby cykli.

Ale jeśli używasz operatora rem VHDL, może to być właściwa odpowiedź. Zakładając, że firma ma przyzwoite narzędzia do syntezy, dałoby to dość wydajną implementację - być może nieco większy obszar niż rozwiązania typu maszyna-maszyna, ale pełna przepustowość, a zatem prawdopodobnie dobra energia na obliczenia. Jest to opcja, która wdrożyłaby najmniej czasu, a zatem prawdopodobnie najmniej pieniędzy dla pracodawcy!

Szczerze mówiąc, prawdopodobnie nie jest to odpowiedź, której szukają z takim pytaniem - ale jest to również okazja, aby pochwalić się prawdziwym doświadczeniem projektowym.

Jeśli liczba jest prezentowana w kawałkach większych niż jeden bit, pomocne może być zastosowanie równoległych obliczeń do obliczenia reszty mod 15, z zastrzeżeniem, że obliczenia mogą dać 15 dokładnie wtedy, gdy reszta jest równa zero. Prostym sposobem obliczenia reszty mod-15 jest zaobserwowanie, że dla dowolnej wartości N> = 1, dodanie skrajnie lewych 4N bitów do części liczby poza nią da wartość zgodną z oryginalnym modem 15. To pozwala podzielić problem na wiele różnych sposobów, w zależności od dostępnych zasobów.

Na przykład, jeśli zaczyna się od wartości 32-bitowej, można to traktować jako osiem wartości 4-bitowych. Można je sumować parami, aby uzyskać cztery wartości 5-bitowe, które z kolei można połączyć w dwie wartości 6-bitowe lub jedną wartość 7-bitową. Dodanie trzech górnych bitów tej 7-bitowej wartości do dolnych 4-bitowych da 5-bitową wartość, która wynosi najwyżej 21. Można w ten sposób ustalić, czy oryginalna wartość jest wielokrotnością 5, obserwując, czy ostateczna wartość jest jeden z 0, 5, 10, 15 lub 20.

Nie pamiętam mojego VHDL, ale oto szkic idei, która pojawiła się po raz pierwszy:

Ostatnie cyfry (w podstawie 10) pierwszych potęg dwóch to 1, 2, 4, 8, 6, 2, ... i cykl się powtarza. Stąd reszta mod 5 potęg dwóch to 1, 2, 4, 3, ....

Korzystając z tego, moglibyśmy przesunąć bity z LSB i gromadzić resztki mod 5 odpowiadające pozycji, ilekroć 1bit jest widoczny. Wykonaj także mod akumulacji 5 i wystarczy sprawdzić, czy suma na końcu wynosi zero.

Możemy skorzystać z pomysłu z odpowiedzi tutaj , że w podstawie 4 możemy wywnioskować, że liczba jest podzielna przez 5 tylko wtedy, gdy suma cyfr naprzemiennych jest. My zatem

1. zgrupuj cyfry 2 po 2,
2. zsumuj nieparzyste i odejmij parzyste 2-bitowe bloki.
3. Jeśli wynik znajduje się w dwóch dopełniających obszarach kilku bitów, na przykład [-4,3] (łatwe do sprawdzenia, zakładając, że używamy dwóch uzupełnień), to jesteśmy skończeni i możemy podzielić pierwotną liczbę przez 5, tylko jeśli wynik sumowanie wynosi 0, co jest bardzo prostym logicznym wyrażeniem do sprawdzenia (w zasadzie tylko duży ani nie wszystkie uzyskane bity, nie?)
4. w przeciwnym razie iterujemy nowy (znacznie krótszy numer).

Spróbujmy na liczbie 166 = (10) (10) (01) (10): 2,2,1,2

2-2 + 1-2 = -1

która wynosi <= 3 w wartości bezwzględnej, a nie 0, dlaczego możemy stwierdzić w jednej iteracji, że 166 nie jest podzielone równomiernie przez 5.

Może być tak, że mała pamięć może być tańsza / lepsza pod względem prędkości / liczby bramek niż iteracja. Można oczywiście wstępnie obliczyć najgorszy (największy możliwy wynik przy dozwolonych danych wejściowych) i odpowiednio zaplanować projekt.

Podejście MSB jest zdecydowanie łatwiejsze, ale udało mi się wykonać diagram stanu LSB bez potrzeby generowania rozwiązania MSB ... zajęło mi to tylko kilka godzin. Okazuje się, że jest to odpowiednik tego pokazanego przez @ComFreek, po prostu inaczej opisany.

Będziemy śledzić dwie liczby. Najpierw będziemy śledzić bieżącą sumę, modulo 5 („SUM”). Po drugie, będziemy śledzić wartość następnej mocy 2, która ma zostać przesunięta, modulo 5 („NASTĘPNY”). Przedstawię każdy stan możliwymi wartościami „SUM” u góry i odpowiadającymi im wartościami „NASTĘPNY” poniżej.

Zaczniemy od przypadku, w którym „SUM” modulo 5 wynosi 0:

Zauważ, że stan wygląda następująco:
3,2,4,1
1,4,3,2

odpowiada:
1,3,4,2
2,1,3,4

Ponieważ oba stany reprezentują, że:
SUMA = 1 i NASTĘPNA = 4 LUB
SUMA = 2 i NASTĘPNA = 3 LUB
SUMA = 3 i NASTĘPNA = 2 LUB
SUMA = 4 i NASTĘPNA = 1.

Ok, więc teraz musimy opracować dodatkowe stany, ponieważ większość ankieterów nie będzie pod wrażeniem diagramu stanu z tylko jednym stanem. Skończymy, gdy każdy stan ma dwa przejścia.

Ilekroć przejdziesz do nowego stanu, każda liczba w „NASTĘPNYM” jest podwojona, a następnie modulo'd 5. W przypadku „SUMY” przestrzegaj następujących zasad:

• Jeśli przeszedłeś wzdłuż 0, górny wiersz zachowa swoje wartości.
• Jeśli przeszedłeś wzdłuż 1, każda kolumna jest modułem „SUM” + „NEXT” starego stanu 5.

Zacznijmy więc od wypełnienia przejść, gdy bit przychodzący ma wartość 1.

W porządku, teraz wypełniamy zera. Dodano tylko jeden stan, więc przejdziemy dalej i uzupełnimy jego przejścia.

I voila! Mamy maszynę stanów, która najpierw akceptuje LSB, bez konieczności generowania rozwiązania MSB.

Wszystko to wydaje się takie skomplikowane! Istnieje prosty matematyczny sposób na wykrycie, czy binarna liczba całkowita jest podzielna przez pięć. Na początek, czy pamiętasz, jak „wyrzucić dziewiątki” w zwykłej arytmetyki dziesiętnej? Moduł resztowy 9 liczby dziesiętnej jest taki sam, jak moduł resztowy 9 sumy jego cyfr. Działa to, ponieważ 9 jest o jeden mniej niż podstawa liczbowa.

Istnieje podobny proces, „wyrzucanie jedenastu”, w którym znaki alternatywnych cyfr są ustawione na ujemne. Działa to, ponieważ jedenastka jest o jeden większa od podstawy liczbowej.

Więc jeśli chcemy „wyrzucić piątki”, możemy reprezentować naszą liczbę całkowitą w bazie czwartej. Następnie zaczynamy od najniższej pary cyfr jako sumy początkowej i odejmujemy ją od następnej pary cyfr, aby otrzymać następną sumę. Po przejściu przez naszą liczbę całkowitą kandydata w ten sposób końcowa suma będzie równa zero lub podzielna przez 5, jeśli nasza pierwotna liczba całkowita będzie podzielna przez 5.

Przykład 70: 01 00 01 10 -> 01 00 -1 -> 01 01 -> 00, podzielny przez 5 Przykład 49: 11 00 01 -> 11 -1 -> 1 00 -> 1, NIE podzielny przez 5

Pamiętaj, że musisz nosić dodatkowe bity dla znaku skumulowanej różnicy i dla przypadków, gdy występuje.

Innym sposobem jest dodanie cyfr szesnastkowych, aby uzyskać resztkowy modulo 15. Oczywiście potrzebujesz ostatniego kroku logicznego, aby zidentyfikować trzy akceptowalne wyniki zero, pięć i dziesięć.

Przykład 70: 4 6 -> A, więc 70 można podzielić przez 5 (ale nie przez 15) Przykład 49: 3 1 -> 4, więc 70 NIE można podzielić przez 5.

Zauważ, że możesz użyć różnych baz liczbowych do zbudowania wielu testów podzielności, chociaż w logice komputerowej te dla potęg 2 +/- 1 są najłatwiejsze do wdrożenia.

W przypadku arytmetyki dziesiętnej jednym z moich ulubionych jest mój test na pozostałość mod 7. Zauważ, że 100 jest dwa większe od wielokrotności 7, więc zgrupuj cyfry w pary (pracuj w bazie liczb 100) i dodaj setki DWUKROTNIE z jednostek. Tutaj pracujemy od lewej do prawej ...

Przykład: 98 76 -> 2 72 -> 76, więc 9876 nie można podzielić przez 7. Jest to 6 mod 7. Przykład: 03 45 67 -> 51 67 -> 1 69 -> 71 więc jest 1 mod 7.

Oczywiście w systemie binarnym wystarczy wziąć sumę cyfr ósemkowych (grupy 3 bitów).

Przepraszam, chciałbym być guru Verilog, ale arytmetyka jest wszystkim, co mogę zaoferować na tym etapie życia. Zobacz „Dead Reckoning” Rona Doerflera, aby uzyskać wiele takich sztuczek.

Pytanie do wywiadu VHDL powinno spowodować powstanie kodu VHDL.

Miałem okazję znaleźć błąd zaplecza ghdl llvm z implementacją tabeli przejścia stanu Dave'a Tweeda, w której autor ghdl destylował implementację w funkcji do 17 wierszy:

type remains is (r0, r1, r2, r3, r4); -- remainder values

    function mod5 (dividend: bit_vector) return boolean is
        type remain_array is array (NBITS downto 0) of remains;
        type branch is array (remains, bit) of remains;
        constant br_table:  branch := ( r0 => ('0' => r0, '1' => r1),
                                        r1 => ('0' => r2, '1' => r3),
                                        r2 => ('0' => r4, '1' => r0),
                                        r3 => ('0' => r1, '1' => r2),
                                        r4 => ('0' => r3, '1' => r4)
                                      );
        variable  remaind:    remains := r0;
        variable tbit:        bit_vector (NBITS - 1 downto 0) := dividend;
    begin
        for i in dividend'length - 1 downto 0 loop
            remaind := br_table(remaind,tbit(i));
        end loop;
        return remaind = r0;
end function;

Powiązany przypadek testowy jest dość mały, co pozwala na łatwiejsze debugowanie i używa nazw stanów zgodnych z VHDL w wyliczonym typie pozostaje:

(stworzony przy pomocy Dia)

Chodzi o to, że funkcja (lub nawet przykładowy program 27 linii VHDL) jest wystarczająco krótki, aby napisać odpowiedź VHDL podczas wywiadu. Nie musisz się martwić, że zepsujesz pytanie podczas rozmowy kwalifikacyjnej wymagające wykazania się zarówno wiedzą, jak i umiejętnościami, od osoby, z którą rozmawiamy, będzie się bronić implementacji, gdy zostanie zapytany.

(Błąd llvm został naprawiony dzisiaj w commit 1f5df6e ).

Jedną z ważniejszych rzeczy jest to, że tabela przejścia stanu mówi nam również, gdzie bit ilorazu byłby „1” pokazany przez przejście do stanu o niższej wartości resztkowej (lub obu przejść dla r4) przy odejmowaniu 5 od dywidendy. Można to zakodować w osobnej tabeli (lub tabeli typu rekordu, która wydaje się niewygodna). Robimy to historycznie w sprzęcie graficznym obsługującym poziome rozdzielczości ekranu wielokrotności 5 pikseli.

W ten sposób otrzymujemy div / mod5, który tworzy iloraz, a resztę:

library ieee;
use ieee.std_logic_1164.all;

entity divmod5 is
    generic (
        NBITS:  natural := 13 
    );
    port (
        clk:        in  std_logic;
        dividend:   in  std_logic_vector (NBITS - 1 downto 0);
        load:       in  std_logic;
        quotient:   out std_logic_vector (NBITS - 3 downto 0);
        remainder:  out std_logic_vector (2 downto 0);
        remzero:    out std_logic
    );
end entity;

architecture foo of divmod5 is
    type remains is (r0, r1, r2, r3, r4); -- remainder values
    type remain_array is array (NBITS downto 0) of remains;
    signal remaindr:    remain_array := (others => r0);
    signal dividendreg: std_logic_vector (NBITS - 1 downto 0);
    signal quot:        std_logic_vector (NBITS - 3 downto 0);
begin

parallel:
    for i in NBITS - 1 downto 0 generate
        type branch is array (remains, bit) of remains;
        -- Dave Tweeds state transition table:
        constant br_table:  branch := ( r0 => ('0' => r0, '1' => r1),
                                        r1 => ('0' => r2, '1' => r3),
                                        r2 => ('0' => r4, '1' => r0),
                                        r3 => ('0' => r1, '1' => r2),
                                        r4 => ('0' => r3, '1' => r4)
                                      );

        type qt is array (remains, bit) of std_ulogic;
    -- Generate quotient bits from Dave Tweeds state machine using q_table.
    -- A '1' when a remainder goes to a lower remainder or for both branches
    -- of r4. A '0' for all other branches.

        constant q_table:   qt :=     ( r0 => (others => '0'),
                                        r1 => (others => '0'),
                                        r2 => ('0' => '0', '1' => '1'),
                                        r3 => (others => '1'),
                                        r4 => (others => '1')
                                      );
        signal tbit:    bit;
    begin
        tbit <= to_bit(dividendreg(i));
        remaindr(i) <= br_table(remaindr(i + 1),tbit);
do_quotient:
        if i < quot'length generate   
            quot(i) <= q_table(remaindr(i + 1),tbit);
        end generate;
    end generate;

dividend_reg:
    process (clk)
    begin
        if rising_edge(clk) then
            if load = '1' then
                dividendreg <= dividend;
            end if;
        end if;
    end process;

quotient_reg:
    process (clk)
    begin
        if rising_edge (clk) then
            quotient <=  quot;
        end if;
    end process;

remainders:
    process (clk)
    begin
        if rising_edge(clk) then 
            remzero <= '0';
            case remaindr(0) is
                when r0 =>
                    remainder <= "000";
                    remzero <= '1';
                when r1 =>
                    remainder <= "001";
                when r2 =>
                    remainder <= "010";
                when r3 =>
                    remainder <= "011";
                when r4 =>
                    remainder <= "100";
            end case;
        end if;
    end process;

end architecture;

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity divmod5_tb is
end entity;

architecture foo of divmod5_tb is
    constant NBITS:    integer range 0 to 13 := 8;
    signal clk:        std_logic := '0';
    signal dividend:   std_logic_vector (NBITS - 1 downto 0);
    signal load:       std_logic := '0';

    signal quotient:   std_logic_vector (NBITS - 3 downto 0);
    signal remainder:  std_logic_vector (2 downto 0);
    signal remzero:    std_logic;
    signal psample:    std_ulogic;
    signal sample:     std_ulogic;
    signal done:       boolean;
begin
DUT:
    entity work.divmod5
        generic map  (NBITS)
        port map (
            clk => clk,
            dividend => dividend,
            load => load,
            quotient => quotient,
            remainder => remainder,
            remzero => remzero
        );
CLOCK:
    process
    begin
        wait for 5 ns;
        clk <= not clk;
        if done'delayed(30 ns) then
            wait;
        end if;
    end process;
STIMULI:
    process
    begin
        for i in 0 to 2 ** NBITS - 1 loop
            wait for 10 ns;
            dividend <= std_logic_vector(to_unsigned(i,NBITS));
            wait for 10 ns;
            load <= '1';
            wait for 10 ns;
            load <= '0';
        end loop;
        wait for 15 ns;
        done <= true;
        wait;
    end process;

SAMPLER:
    process (clk)
    begin
        if rising_edge(clk) then
            psample <= load;
            sample <= psample after 4 ns;
        end if;
    end process;

MONITOR:
    process (sample)
        variable i:     integer;
        variable div5:  integer;
        variable rem5:  integer;
    begin
        if rising_edge (sample) then
            i := to_integer(unsigned(dividend));
            div5 := i / 5;
            assert div5 = unsigned(quotient)
                report LF & HT &
                    "i = " & integer'image(i) &
                    " div 5 expected " & integer'image(div5) & 
                    " got " & integer'image(to_integer(unsigned(quotient)))
                SEVERITY ERROR;
            rem5 := i mod 5;
            assert rem5 = unsigned(remainder)
                report LF & HT &
                    "i = " & integer'image(i) &
                    " rem 5 expected " & integer'image(rem5) & 
                    " got " & integer'image(to_integer(unsigned(remainder)))
                SEVERITY ERROR;
        end if;
    end process;

end architecture;

Zaimplementowane tutaj z instrukcją generowania, wewnętrzną instrukcją generowania produkującą bity ilorazowe. Pozostała tablica zapewnia śledzenie przejścia stanu:

Wszystko bez operacji arytmetycznej.

Możliwe jest również wdrożenie w procedurze bez wykorzystywania przez wszystkie rejestry parametrów bez trybu. To zbliży się do minimalnej liczby linii na rozmowę kwalifikacyjną.

Taktowana sekwencyjna implementacja wymagałaby nieco licznika i kontroli przepływu (przerzutnik JK i kilka bramek).

Kompromis czas / złożoność zależy od wielkości dywidendy, której prawdopodobnie będziesz musiał bronić podczas wywiadu.