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

Eine Restoperation seriell durchzuführen ist eigentlich ganz einfach. Die Hauptannahme ist, dass die Daten in MSB-first kommen, wenn sie seriell sind. Sie benötigen nur N Zustände, um einen Rest modulo N zu berechnen. Beginnen Sie im Zustand "0", und wenn Sie nach dem letzten Bit im Zustand "0" landen (es spielt keine Rolle, wie viele Bits vorhanden sind), ist der Rest Null.

^{Simulieren Sie diese Schaltung – Mit CircuitLab erstellter Schaltplan}

Denken Sie darüber nach, wie Sie eine lange Division 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 unter Umkehrung geschlossen sind (siehe z. B. 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 der Antwort von Dave Tweed . 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: Designing a DFA and the reverse of it beschrieben .
   Sie können das (nicht minimierte) Ergebnis dieses Schritts in der alten Überarbeitung dieser Antwort sehen.

3. Minimieren Sie den resultierenden DFA. Leider ist diese Funktion in der neuesten JFLAP-Version ein wenig fehlerhaft, daher habe ich mich damit abgefunden, sie von Hand zu minimieren.
   Auch hier gibt es viele Algorithmen und Quellen dafür, ich habe den unter „DFA-Minimierung“ auf tutorialspoint.com beschriebenen verwendet .
   
   (Tatsächlich, wenn Ihre Augen gut genug darin trainiert sind, DFAs zu betrachten, könnten Sie das direkt sehen$q_0$und$q_1$sind äquivalente Zustände im DFA wie in Punkt 2 erhalten. Meine sind es nicht, danke, dass Sie es bemerkt haben, gehen Sie zu Supercats Kommentar!)

Tatsächlich gibt der resultierende Automat die richtigen Antworten:

Anhang: Aus Gründen der Barrierefreiheit akzeptiert der DFA Binärzahlen, die durch 5 mit LSB-first teilbar sind$A_{rev5} = (Q, \Sigma, \delta, q_0, F)$mit$Q = \{q_0, q_1, q_2, q_3, q_4\}$,$\Sigma = \{0,1\}$,$F = \{q_0\}$und$\delta$folgendermaßen:

$\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 erstellen, ist wie folgt:

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

2. Es kommt ein neues Bit herein 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 leicht 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.

Hoffentlich ging es bei der Interviewfrage eher darum, wie Sie das Problem lösen würden, als um die Vor- und Nachteile von VHDL oder Verilog. Die Sprachdetails sind einfach, sobald Sie einen Algorithmus haben.

Wenn die Zahl bitweise mit MSB zuerst übergeben wird, dann kann der Wert der Zahl modulo 5 durch Initialisieren des Zustands berechnet werden$S=0$und dann den Wert mit akkumulieren$S \leftarrow (2 S + d) \text{ mod } 5$. Am Ende ist die Zahl durch 5 iff teilbar $S$ist Null. Seit$S,d$begrenzt sind, kann die Aktualisierungsgleichung als einfache Zustandsmaschine mit Zuständen geschrieben werden$S=0,\cdots, 4$.

Wenn die Zahl zuerst mit LSB nach und nach übergeben wird, müssen wir etwas mehr Arbeit leisten. Auf Anhieb können wir versuchen, den Zustand zu initialisieren$S=0, k= 0$und dann den Wert mit akkumulieren$S \leftarrow (S + 2^k d) \text{ mod } 5 , k \leftarrow k+1$. Das Problem dabei ist, dass$k$ist jedoch potenziell unbegrenzt, da$2^4 = 1 \text{ mod } 5$, können wir das Obige vereinfachen zu$S \leftarrow (S + 2^k d) \text{ mod } 5 , k \leftarrow (k+1) \text{ mod } 4$. Wieder seit$S,k,d$begrenzt sind, kann die Aktualisierungsgleichung als einfache Zustandsmaschine mit Zuständen geschrieben werden$(S,k)$wo$S=0,\cdots, 4$,$k=0,\cdots, 3$.

Je nachdem, wofür die VHDL geschrieben wird, möchten Sie möglicherweise einen Ansatz wählen, der sie als direkte, kombinatorische Berechnung beschreibt. Der Empfang einer Zahl kann bedeuten, dass sich die gesamte Zahl für einen Taktzyklus in einem Register befindet.

Sie könnten zum Beispiel den Mod 5 des Werts notieren, den jedes der Bits darstellt, diese zusammenzählen und dann den Vorgang wiederholen, bis Sie etwas weniger als 5 übrig haben. Entweder implementieren Sie dies kombiniert für alle Reduktionsschritte, oder die Logik für eine kleine Anzahl von Zyklen wiederverwenden.

Aber wenn Sie den VHDL-Rem-Operator verwenden, ist das vielleicht genau die richtige Antwort. Angenommen, das Unternehmen verfügt über anständige Synthesewerkzeuge, die Ihnen eine ziemlich effiziente Implementierung ermöglichen würden - vielleicht etwas mehr Fläche als State-Machine-Lösungen, aber voller Durchsatz und daher wahrscheinlich gute Energie pro Berechnung. Es ist die Option, die am wenigsten Zeit in der Umsetzung und damit wahrscheinlich am wenigsten Geld für den Arbeitgeber kosten würde!

Um fair zu sein, ist es wahrscheinlich nicht die Antwort, die sie auf eine solche Frage suchen - aber es ist auch eine Gelegenheit, echte Designerfahrung zu zeigen.

Wenn die Zahl in Blöcken präsentiert wird, die größer als ein Bit sind, kann es hilfreich sein, einige parallele Berechnungen zu verwenden, um das Residuum mod 15 zu berechnen, mit der Maßgabe, dass die Berechnung genau 15 ergeben kann, wenn das Residuum null ist. Eine einfache Methode zur Berechnung des mod-15-Residuums besteht darin, zu beobachten, dass für jeden Wert von N > = 1 das Hinzufügen der 4 N Bits ganz links zum Teil einer Zahl darüber hinaus einen Wert ergibt, der mit dem ursprünglichen mod 15 kongruent ist. Dies ermöglicht es, das Problem je nach den verfügbaren Ressourcen auf viele verschiedene Arten zu unterteilen.

Wenn man beispielsweise mit einem 32-Bit-Wert beginnt, kann das 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. Das Addieren der oberen drei Bits dieses 7-Bit-Werts zu den unteren 4 Bits ergibt einen 5-Bit-Wert, der höchstens 21 ist. Man kann also bestimmen, ob der ursprüngliche Wert ein Vielfaches von 5 ist, indem man beobachtet, ob der Endwert es ist eine von 0, 5, 10, 15 oder 20.

Ich kann mich nicht an mein VHDL erinnern, aber hier ist eine Skizze der Idee, die mir zuerst in den Sinn kam:

Die letzten Ziffern (in Basis 10) der ersten Zweierpotenzen sind 1, 2, 4, 8, 6, 2, ... und der Zyklus wiederholt sich. Daher sind die Reste mod 5 von Zweierpotenzen 1, 2, 4, 3, ....

Damit könnten wir Bits vom LSB verschieben und die Reste mod 5 akkumulieren, die der Position entsprechen, wann immer ein 1Bit gesehen wird. Machen Sie auch die Akkumulation Mod 5, und es reicht 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 durch 5 teilbar ist, wenn die alternierende Ziffernsumme ist. Wir deshalb

1. gruppiere die Ziffern 2 mal 2,
2. summiere die ungeraden und subtrahiere die geraden 2-Bit-Blöcke.
3. Wenn das Ergebnis im Zweier-Komplement-Bereich von einigen Bits liegt, zum Beispiel [-4,3] (einfach zu überprüfen, vorausgesetzt, wir verwenden zwei Komplemente), dann sind wir fertig und können die ursprüngliche Zahl nur dann durch 5 teilen, wenn das Ergebnis von Die Summe ist 0, was ein sehr einfacher logischer Ausdruck ist, der überprüft werden muss (im Grunde nur ein großes Nor auf allen resultierenden Bits, oder?)
4. andernfalls iterieren wir mit der neuen (viel kürzeren Zahl).

Versuchen wir es mit der Zahl 166 = (10)(10)(01)(10): 2,2,1,2

2-2+1-2 = -1

was <= 3 im absoluten Wert und nicht 0 ist, 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 Geschwindigkeit / Anzahl der Tore billiger / besser ist als Iteration. Man kann natürlich das schlechteste (größtmögliche Ergebnis angesichts der zulässigen Eingaben) vorausberechnen 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 ... es hat nur ein paar Stunden gedauert. Es stellt sich heraus, dass es dem von @ComFreek gezeigten entspricht, nur anders kommentiert.

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

Wir beginnen mit dem Fall, in dem "SUMME" 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

Denn beide Zustände repräsentieren das:
SUM = 1 und NEXT = 4 OR
SUM = 2 and NEXT = 3 OR
SUM = 3 and NEXT = 2 OR
SUM = 4 and NEXT = 1.

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

Immer wenn Sie in einen neuen Zustand übergehen, wird jede Zahl in "NEXT" verdoppelt und dann modulo'd 5. Für die "SUMME" folgen Sie diesen Regeln:

• Wenn Sie entlang einer 0 übergegangen sind, behält die oberste Reihe ihre Werte.
• Wenn Sie entlang einer 1 übergegangen sind, ist jede Spalte die "SUMME" + "NEXT" Modulo 5 des alten Zustands.

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

In Ordnung, jetzt füllen wir die Nullen aus. Es wird nur ein Zustand hinzugefügt, also füllen wir auch seine Übergänge aus.

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

All dies scheint so kompliziert! Es gibt eine einfache mathematische Methode, um festzustellen, ob eine binäre ganze Zahl durch fünf teilbar ist. Erinnern Sie sich zunächst daran, wie man in der gewöhnlichen Dezimalarithmetik "Neunen auswirft"? Der Modulo-9-Rest einer dezimalen ganzen Zahl ist derselbe wie der Modulo-9-Rest der Summe ihrer Ziffern. Das funktioniert, weil 9 um eins kleiner ist als die Zahlenbasis.

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

Wenn wir also „Fünen verwerfen“ wollen, könnten wir unsere ganze Zahl in der Zahlenbasis vier darstellen. Dann beginnen wir mit dem niedrigsten Zahlenpaar als Anfangssumme und subtrahieren es vom nächsten Zahlenpaar, um die nächste Summe zu erhalten. Nachdem wir unsere Kandidaten-Ganzzahl auf diese Weise durchgegangen sind, 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, NOT durch 5 teilbar

Beachten Sie, dass Sie zusätzliche Bits für das Vorzeichen der akkumulierten Differenz und für Fälle tragen müssen, in denen es zu einer Übertragung kommt.

Eine andere Möglichkeit besteht darin, einfach die Hexadezimalziffern zu addieren, um den Rest 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 konstruieren, obwohl in der Computerlogik die für Potenzen von 2 +/- 1 am einfachsten zu implementieren sind.

Einer meiner Favoriten in der Dezimalarithmetik ist mein Test für Residuum mod 7. Beachten Sie, dass 100 zwei größer als ein Vielfaches von 7 ist, also gruppieren Sie die Ziffern in Paaren (arbeiten Sie mit der Zahlenbasis 100) und addieren Sie die Hunderter ZWEIMAL von den Einheiten. Hier arbeiten wir von links nach rechts...

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

Im Binärformat nehmen Sie natürlich einfach die Summe der Oktalziffern (Gruppen von 3 Bits).

Tut mir leid, ich wünschte, ich wäre ein Verilog-Guru, aber Arithmetik ist alles, was ich in diesem Lebensabschnitt bieten kann. Siehe Ron Doerflers "Dead Reckoning" für viele Tricks wie diesen.

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

Ich hatte Gelegenheit, einen ghdl llvm-Backend-Bug mit einer Implementierung von Dave Tweeds Zustandsübergangstabelle zu finden, wo der Autor von ghdl 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, was ein einfacheres Debuggen ermöglicht, und verwendet Zustandsnamen, die mit VHDL kompatibel sind, wobei der Aufzählungstyp erhalten bleibt:

(erstellt mit Dia)

Die Idee dabei ist, dass die Funktion (oder sogar ein VHDL-Beispielprogramm mit 27 Zeilen) kurz genug ist, um während eines Interviews eine VHDL-Antwort zu schreiben. Sie müssen sich keine Sorgen machen, eine Interviewfrage zu verderben, die den Nachweis von Wissen und Können erfordert. Von einem Interviewpartner wird erwartet, dass er eine Implementierung verteidigt, wenn er befragt wird.

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

Eines der bemerkenswerten Dinge ist, dass die Zustandsübergangstabelle uns auch sagt, wo ein Quotientenbit eine '1' wäre, was durch einen Übergang zu einem Zustand mit einem niedrigeren Restwert (oder beide Übergänge für r4) angezeigt wird, wenn 5 vom Dividenden subtrahiert wird. Dies kann in einer separaten Tabelle (oder einer Tabelle eines Datensatztyps, der umständlich erscheint) codiert werden. Wir tun dies historisch in Grafikhardware, die sich mit horizontalen Bildschirmauflösungen befasst, die ein Vielfaches von 5 Pixeln sind.

Dadurch erhalten wir ein div/mod5, das einen Quotienten und einen Rest erzeugt:

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;

Hier implementiert mit einer Generate-Anweisung, einer inneren Generate-Anweisung, die Quotientenbits erzeugt. Das Array restr stellt eine Zustandsübergangsverfolgung bereit:

Alles ohne Rechenoperation.

Es ist auch möglich, in einer Prozedur zu implementieren, ohne dass alle Register Parameter mit Mode Out nutzen. Das würde einer minimalen Anzahl von Zeilen für ein Interview nahe kommen.

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

Je nach Dividendenhöhe gibt es einen Kompromiss zwischen Zeit und Komplexität, den Sie wahrscheinlich auch in einem Interview verteidigen müssten.