überprüfen Sie, ob eine Zahl von 3 in Logikdesign

Question

teilbar ist i einen Beitrag auf der Website darüber gesehen und ich verstand nicht die Antwort, ich kann Erklärung erhält Sie unter:

Frage:

Schreibe Code, um festzustellen, ob eine Zahl durch 3 teilbar ist. Die Eingabe für die Funktion ist ein einzelnes Bit, 0 oder 1, und die Ausgabe sollte 1 sein, wenn die bisher empfangene Zahl die Binärdarstellung einer durch 3 teilbaren Zahl ist Null.

Beispiele:

input "0": (0) output 1 inputs "1,0,0": (4) output 0 inputs "1,1,0,0": (6) output 1

Dieses auf einem Interview Frage basiert. Ich frage nach einer Zeichnung von Logikgattern, aber da dies Stackoverflow ist, werde ich jede Programmiersprache akzeptieren. Bonuspunkte für eine Hardware-Implementierung (Verilog etc).

Teil a (einfach): Erste Eingabe ist das MSB. Teil b (etwas härter): Erste Eingabe ist das LSB. Teil c (schwierig): Welche ist schneller und kleiner, (a) oder (b)? (Nicht theoretisch im Big-O Sinn, aber praktisch schneller/kleiner.) Nimm nun den langsameren/größeren und mache ihn so schnell/klein wie der schnellere/kleinere.

Antwort:

Zustandstabelle für LSB:

S I S' O 0 0 0 1 0 1 1 0 1 0 2 0 1 1 0 1 2 0 1 0 2 1 2 0

Erläuterung: 0 ist durch drei teilbar. 1 + 0 = 0. Repeat unter Verwendung von S = (S < < 1 + I)% 3 und o = 1, wenn S == 0.

Zustandstabelle für MSB:

S I S' O 0 0 0 1 0 1 2 0 1 0 1 0 1 1 0 1 2 0 2 0 2 1 1 0

Erläuterung: 0 ist durch drei teilbar. 0 >> 1 + 0 = 0. Wiederholen Sie mit S = (S >> 1 + I)% 3 und O = 1 wenn S == 0.

S 'unterscheidet sich von oben, aber O funktioniert das gleiche, da S '0 ist für die gleichen Fälle (00 und 11). Da O in beiden Fällen gleich ist, O_LSB = O_MSB, um MSB so kurz wie LSB oder umgekehrt zu machen, verwende einfach die kürzeste von beiden.

danke für die Antworten in fortgeschrittenen.

Answer 1

Nun, ich nehme an, die Frage ist nicht völlig off-topic, da Sie nach Logik-Design gefragt haben, aber Sie müssen die Codierung selbst tun.

Sie haben 3 Zustände in der S-Spalte. Diese verfolgen den Wert der aktuellen vollen Eingabe mod 3. S0 bedeutet also, dass der aktuelle Eingang mod 3 0 ist und somit durch 0 teilbar ist (bedenke auch, dass 0 durch 3 teilbar ist). S1 bedeutet, der Rest ist 1, S2 bedeutet, dass der Rest 2 ist.

Die Spalte I gibt den aktuellen Eingang (0 oder 1) und S 'gibt den nächsten Zustand (mit anderen Worten, die neue Nummer Mod 3) .

Für 'LSB' ist die neue Nummer die alte Nummer < < 1, plus entweder 0 oder 1. Schreiben Sie die Tabelle aus. Für den Fall, dass der alte Modulo 0 war, dann ist der neue Modulo 0, wenn das Eingangsbit 0 war, und 1, wenn der neue Eingang 1 war. Dies gibt Ihnen die ersten 2 Zeilen in der ersten Tabelle. Der Rest wird als Übung für dich ausgefüllt.

Beachten Sie, dass die O-Spalte nur 1 ist, wenn der nächste Status wie erwartet 0 ist.