VHDL-Interviewfrage - Ermitteln, ob eine Zahl ohne Rest durch 5 geteilt werden kann

Ich habe eine nette Interviewfrage für VHDL gesehen - baue ein System, das eine Nummer erhält und erkennt, ob es ohne Rest durch 5 geteilt werden kann. Ich habe versucht, das mit einer Zustandsmaschine zu lösen (ich nehme an, sie möchten nicht, dass Sie Mod oder Rem verwenden ), und während ich anfänglich Erfolg hatte (Zahlen wie 5, 10, 15 und Zahlen wie 20, 40, 80 haben funktioniert) ), andere Nummern wie 130, 75 usw. sind für mich gescheitert.

Ich würde meine Zustandsmaschine zeigen, aber es ist ein komplettes Durcheinander (es ist kein Code, es ist eine Zeichnung), und wie gesagt, es funktioniert nicht einmal.

Grundsätzlich habe ich versucht, in Binärzahlen zu schreiben, die durch 5 teilbar sind, und eine Zustandsmaschine zu erstellen, die für sie funktioniert.

Ich würde mich freuen, wenn Sie mir zeigen könnten, wie man dieses Problem löst und wie man denkt, wenn man so etwas sieht.

Vielen Dank!

Es ist eigentlich recht einfach, einen Restvorgang seriell durchzuführen. Die Hauptannahme ist, dass die Daten zuerst in MSB eingehen, wenn sie seriell sind. Sie benötigen nur N Zustände, um ein Restmodulo N zu berechnen. Beginnen Sie im Zustand "0" und wenn Sie nach dem letzten Bit im Zustand "0" enden (es spielt keine Rolle, wie viele Bits es gibt), ist der Rest Null.

^{simulieren Sie diese Schaltung - Schaltplan erstellt mit CircuitLab}

Überlegen Sie, wie Sie eine lange Teilung durchführen würden, wenn Sie nur den Rest im Auge behalten müssten:

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;

Sie können auch eine Zustandsmaschine entwerfen, wenn die Daten LSB-first sind:

Die Existenz eines solchen deterministischen endlichen Automaten (DFA) folgt direkt aus der anderen Antwort , die den DFA für MSB-first beschreibt. Da von DFAs akzeptierte Sprachen regulär sind und reguläre Sprachen bekanntermaßen wegen Umkehrung geschlossen werden (siehe hier ), muss es einen DFA geben, der die folgende Sprache akzeptiert:

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

Konstruktion

1. Kopieren Sie den MSB-first-DFA aus Dave Tweeds Antwort . Ich habe dafür das Automatentool JFLAP verwendet .

2. Wenden Sie den expliziten Transformationsalgorithmus für DFA-Umkehrungen an, z. B. wie in CS.SE: Entwerfen eines DFA und umgekehrt beschrieben .
   Sie können das (nicht minimierte) Ergebnis dieses Schritts in der alten Revision dieser Antwort sehen.

3. 
   
   
   $q_0$$q_1$

In der Tat gibt der resultierende Automat die richtigen Antworten:

$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$

Eine Möglichkeit, die Zustandsmaschine (MSB first) zu entwickeln, ist folgende:

1. Die bisher erhaltene Nummer ist N. Angenommen, Sie kennen den Rest M = N mod 5.

2. Es kommt ein neues Bit und der neue Wert ist jetzt N' = N*2 + b.

3. Neuer Rest ist dann M' = (N*2 + b) mod 5 = (M*2 + b) mod 5.

Dies ist einfach genug, um von Hand zu tabellieren:

    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

Was mit der Zustandsmaschine in Dave Tweeds Antwort übereinstimmt.

Man hofft, dass sich die Interviewfrage eher mit der Frage befasst, wie Sie das Problem lösen würden, als mit den Vor- und Nachteilen von VHDL oder Verilog. Sobald Sie einen Algorithmus haben, sind die Sprachdetails unkompliziert.

$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$

Abhängig davon, wofür die VHDL geschrieben wird, können Sie einen Ansatz wählen, der sie als direkte kombinatorische Berechnung beschreibt. Das Empfangen einer Nummer kann bedeuten, dass sich die gesamte Nummer für einen Taktzyklus in einem Register befindet.

Sie können beispielsweise die Modifikation 5 des Werts notieren, den jedes der Bits darstellt, diese addieren und den Vorgang dann wiederholen, bis Sie weniger als 5 übrig haben. Implementieren Sie dies entweder kombinatorisch für alle Reduktionsschritte. oder verwenden Sie die Logik für eine kleine Anzahl von Zyklen erneut.

Wenn Sie jedoch den VHDL-Rem-Operator verwenden, ist dies möglicherweise die richtige Antwort. Vorausgesetzt, das Unternehmen verfügt über vernünftige Synthesewerkzeuge, die eine ziemlich effiziente Implementierung ermöglichen - ein bisschen mehr Fläche als State-Machine-Lösungen, aber voller Durchsatz und daher wahrscheinlich gute Energie pro Berechnung. Dies ist die Option, deren Implementierung am wenigsten Zeit und damit wahrscheinlich am wenigsten Geld für den Arbeitgeber kostet!

Um fair zu sein, es ist wahrscheinlich nicht die Antwort, die sie mit einer solchen Frage suchen - aber es ist auch eine Gelegenheit, ein echtes Designerlebnis zu präsentieren.

Wenn die Zahl in Blöcken dargestellt wird, die größer als ein Bit sind, kann es hilfreich sein, einige parallele Berechnungen zur Berechnung des Residuums mod 15 zu verwenden, mit der Maßgabe, dass die Berechnung genau 15 ergeben kann, wenn das Residuum Null ist. Ein einfacher Weg, um den Mod-15-Rest zu berechnen, besteht darin, zu beobachten, dass für jeden Wert von N> = 1 das Addieren der ganz linken 4N-Bits zu dem Teil einer Zahl darüber hinaus einen Wert ergibt, der mit dem ursprünglichen Mod 15 kongruent ist Dadurch kann das Problem in Abhängigkeit von den verfügbaren Ressourcen auf viele verschiedene Arten unterteilt werden.

Wenn man beispielsweise mit einem 32-Bit-Wert beginnt, kann dies als acht 4-Bit-Werte behandelt werden. Diese können paarweise zu vier 5-Bit-Werten addiert werden, die wiederum zu zwei 6-Bit-Werten oder einem 7-Bit-Wert kombiniert werden können. Addiert man die oberen drei Bits dieses 7-Bit-Werts zu den unteren 4-Bit-Werten, so erhält man einen 5-Bit-Wert von höchstens 21. Man kann also feststellen, ob der ursprüngliche Wert ein Vielfaches von 5 ist, indem man beobachtet, ob der Endwert ein Vielfaches von 5 ist eine von 0, 5, 10, 15 oder 20.

Ich kann mich nicht an meine VHDL erinnern, aber hier ist eine Skizze der Idee, die mir als erstes einfiel:

Die letzten Ziffern (in Basis 10) der ersten Zweierpotenzen sind 1, 2, 4, 8, 6, 2, ... und der Zyklus wird wiederholt. Daher sind die verbleibenden Modi 5 der Zweierpotenzen 1, 2, 4, 3, ....

Auf diese Weise könnten wir Bits aus dem LSB verschieben und die Restmodifikation 5 akkumulieren, die der Position entspricht, wann immer ein 1Bit gesehen wird. Mache auch den Akkumulations-Mod 5 und es ist genug zu prüfen, ob die Summe am Ende Null ist.

Wir können die Idee aus der Antwort hier verwenden , dass wir in Basis 4 ableiten können, dass eine Zahl nur dann durch 5 teilbar ist, wenn die alternierende Ziffernsumme ist. Wir deshalb

1. gruppieren sie die ziffern 2 durch 2,
2. summiere die ungeraden und subtrahiere die geraden 2-Bit-Blöcke.
3. Liegt das Ergebnis beispielsweise im Zweikomplementbereich einiger Bits [-4,3] (leicht zu überprüfen, vorausgesetzt, wir verwenden zwei Komplemente), sind wir fertig und können die ursprüngliche Zahl nur dann durch 5 dividieren, wenn das Ergebnis des Die Summe ist 0, was ein sehr einfach zu überprüfender logischer Ausdruck ist.
4. ansonsten iterieren wir auf der neuen (viel kürzeren Zahl).

Versuchen wir die Zahl 166 = (10) (10) (01) (10): 2,2,1,2

2-2 + 1-2 = -1

Das ist <= 3 im absoluten Wert und nicht 0, weshalb wir in nur einer Iteration schließen können, dass 166 nicht gleichmäßig durch 5 geteilt wird.

Könnte sein, dass ein kleiner Speicher in Bezug auf die Geschwindigkeit / Anzahl der Gates billiger / besser ist als das Iterieren. Man kann natürlich das schlechteste vorberechnen (größtmögliches Ergebnis bei den erlaubten Eingaben) und das Design entsprechend planen.

Der MSB-Ansatz ist definitiv einfacher, aber ich habe es geschafft, das LSB-Zustandsdiagramm zu erstellen, ohne die MSB-Lösung generieren zu müssen. Ich habe nur ein paar Stunden gebraucht. Es stellt sich heraus, dass es dem von @ComFreek gezeigten entspricht, nur anders kommentiert.

Wir werden zwei Zahlen verfolgen. Zuerst werden wir die laufende Summe, Modulo 5 ("SUM") verfolgen. Zweitens verfolgen wir den Wert der nächsten Potenz von 2, die eingeschoben werden soll, Modulo 5 ("NEXT"). Ich werde jeden Zustand mit möglichen Werten für "SUM" oben und den entsprechenden "NEXT" -Werten darunter darstellen.

Wir beginnen mit dem Fall, in dem "SUM" modulo 5 0 ist:

Beachten Sie, dass ein Zustand wie
folgt aussieht: 3,2,4,1
1,4,3,2

entspricht:
1,3,4,2
2,1,3,4

Weil beide Zustände dies darstellen:
SUM = 1 und NEXT = 4 ODER
SUM = 2 und NEXT = 3 ODER
SUM = 3 und NEXT = 2 ODER
SUM = 4 und NEXT = 1.

Okay, jetzt müssen wir zusätzliche Zustände entwickeln, da die meisten Interviewer nicht von einem Zustandsdiagramm mit nur einem Zustand beeindruckt sein werden. Wir sind fertig, wenn jeder Zustand zwei Übergänge hat.

Immer wenn Sie in einen neuen Zustand wechseln, wird jede Zahl in "NEXT" verdoppelt und dann mit 5 moduliert. Für die "SUM" gelten folgende Regeln:

• Wenn Sie entlang einer 0 gewechselt haben, behält die oberste Zeile ihre Werte bei.
• Wenn Sie mit einer 1 gewechselt haben, entspricht jede Spalte dem Modulo 5 "SUM" + "NEXT" des alten Zustands.

Beginnen wir also damit, die Übergänge auszufüllen, wenn das eingehende Bit 1 ist.

Okay, jetzt füllen wir die Nullen aus. Es wird nur ein Bundesstaat hinzugefügt, daher werden wir auch die Übergänge ausfüllen.

Und voila! Wir haben eine Zustandsmaschine, die das LSB zuerst akzeptiert, ohne die MSB-Lösung generieren zu müssen.

All das scheint so kompliziert! Es gibt eine einfache mathematische Methode, um festzustellen, ob eine binäre Ganzzahl durch fünf teilbar ist. Erinnern Sie sich zu Beginn, wie man in gewöhnlicher Dezimalarithmetik "Neunen austreibt"? Das Residuum Modulo 9 einer Dezimalzahl ist dasselbe wie das Residuum Modulo 9 der Summe seiner Ziffern. Dies funktioniert, weil 9 eins weniger als die Zahlenbasis ist.

Es gibt einen ähnlichen Vorgang, das "Auswerfen von Erhöhungen", bei dem die Zeichen alternierender Ziffern negativ gesetzt werden. Das funktioniert, weil elf eins größer als die Zahlenbasis ist.

Wenn wir also "Fünfer austreiben" wollen, könnten wir unsere ganze Zahl auf der Basis vier darstellen. Dann beginnen wir mit dem niedrigsten Ziffernpaar als Anfangssumme und subtrahieren es vom nächsten Ziffernpaar, um die nächste Summe zu erhalten. Nachdem Sie unsere Kandidatenzahl auf diese Weise durchlaufen haben, ist die Endsumme null oder durch 5 teilbar, wenn unsere ursprüngliche Ganzzahl durch 5 teilbar ist.

Beispiel 70: 01 00 01 10 -> 01 00 -1 -> 01 01 -> 00, teilbar durch 5 Beispiel 49: 11 00 01 -> 11 -1 -> 1 00 -> 1, NICHT teilbar durch 5

Beachten Sie, dass Sie zusätzliche Bits für das Vorzeichen der akkumulierten Differenz und für Fälle mitführen müssen, in denen eine Übertragung stattfindet.

Ein anderer Weg ist, einfach die Hexadezimalziffern zu addieren, um das Residuum Modulo 15 zu erhalten. Natürlich benötigen Sie einen letzten logischen Schritt, um die drei akzeptablen Ergebnisse von Null, Fünf und Zehn zu identifizieren.

Beispiel 70: 4 6 -> A, also ist 70 durch 5 teilbar (aber nicht durch 15) Beispiel 49: 3 1 -> 4, also ist 70 NICHT durch 5 teilbar.

Beachten Sie, dass Sie verschiedene Zahlenbasen verwenden können, um viele Teilbarkeitstests zu erstellen. In der Computerlogik sind jedoch diejenigen für Potenzen von 2 +/- 1 am einfachsten zu implementieren.

In der Dezimalarithmetik ist einer meiner Favoriten mein Test für Residuum Mod 7. Beachten Sie, dass 100 zwei größer als ein Vielfaches von 7 ist. Gruppieren Sie die Ziffern also in Paare (arbeiten Sie mit der Zahlenbasis 100) und addieren Sie die Hunderte ZWEIMAL aus den Einheiten. Hier arbeiten wir von links nach rechts ...

Beispiel: 98 76 -> 2 72 -> 76, daher ist 9876 nicht teilbar durch 7. Es ist 6 mod 7. Beispiel: 03 45 67 -> 51 67 -> 1 69 -> 71, so ist es 1 mod 7.

Natürlich nimm in Binärform einfach die Summe der Oktalziffern (3-Bit-Gruppen).

Entschuldigung, ich wünschte, ich wäre ein Verilog-Guru, aber das Rechnen ist alles, was ich in dieser Lebensphase anbieten kann. In Ron Doerflers "Dead Reckoning" finden Sie eine Menge solcher Tricks.

Eine VHDL-Interviewfrage sollte zu einem VHDL-Code führen.

Ich hatte Gelegenheit, einen ghdl llvm-Backend-Fehler mit einer Implementierung von Dave Tweeds Zustandsübergangstabelle zu finden, in der ghdls Autor die Implementierung in einer Funktion auf 17 Zeilen destillierte:

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;

Der zugehörige Testfall ist recht klein, um das Debuggen zu vereinfachen, und verwendet Statusnamen, die mit VHDL kompatibel sind. Der Aufzählungstyp bleibt erhalten:

(erstellt mit Dia)

Die Idee dabei ist, dass die Funktion (oder sogar ein Beispiel für ein VHDL-Programm mit 27 Zeilen) kurz genug ist, um während eines Interviews eine VHDL-Antwort zu schreiben. Kein Grund zur Sorge, eine Interviewfrage zu verderben, die den Nachweis von Wissen und Können erfordert. Es wird von einem Interviewten erwartet, dass er eine Implementierung verteidigt, wenn er befragt wird.

(Der Fehler im llvm-Backend wurde heute in Commit 1f5df6e behoben .)

Zu beachten ist, dass die Zustandsübergangstabelle auch angibt, wo ein Quotientenbit eine '1' ist, die durch einen Übergang in einen Zustand mit einem niedrigeren Restwert (oder beiden Übergängen für r4) angezeigt wird, wenn 5 von der Dividende subtrahiert wird. Dies kann in einer separaten Tabelle (oder einer Tabelle eines Datensatztyps, der umständlich zu sein scheint) codiert werden. Wir machen dies historisch in Grafikhardware, die mit horizontalen Bildschirmauflösungen um ein Vielfaches von 5 Pixeln arbeitet.

Auf diese Weise erhalten wir ein div / mod5, das einen Quotienten und einen Rest ergibt:

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;

Implementiert hier mit einer Erzeugungsanweisung, einer inneren Erzeugungsanweisung, die Quotientenbits erzeugt. Das Array remaindr stellt eine Ablaufverfolgung für den Statusübergang bereit:

Alles ohne Rechenoperation.

Es ist auch möglich, eine Prozedur zu implementieren, ohne dass alle Register die Parameter mit Modus ausnutzen. Das würde sich einer Mindestanzahl von Zeilen für ein Interview nähern.

Eine getaktete sequentielle Implementierung würde einen Bitzähler und eine Flusssteuerung erfordern (ein JK-Flipflop und ein paar Gatter).

Es gibt einen Kompromiss zwischen Zeit und Komplexität, der von der Dividendengröße abhängt, die Sie wahrscheinlich auch in einem Interview verteidigen müssen.