Ich hätte gerne eine synthetisierbare und optimierte Lösung für den Modulo-Operator in Verilog (%) für die Nichtpotenz von zwei ganzen Zahlen.
cnt_mod <= cnt % 3;
Für Potenzen von zwei Ganzzahlen (n_arg) könnte dies als ein Linksverschiebungsprozess angesehen werden, gefolgt von einem Abschneiden auf n_arg Bits.
Wie kann es für die Nichtpotenz zweier ganzer Zahlen implementiert werden?
Danke
Es ist tatsächlich möglich, den Modulus durch eine Konstante nur mit Addition und einer kleinen Nachschlagetabelle zu implementieren.
Angenommen, Sie haben eine 8-Bit-Binärzahl. Betrachten Sie alle Zweierpotenzen, die in 8 Bit darstellbar sind, nämlich die folgenden:
00000001 = 1
00000010 = 2
00000100 = 4
00001000 = 8
00010000 = 16
00100000 = 32
01000000 = 64
10000000 = 128
Wenden Sie nun den Modulo-Operator (in unserem Fall % 3) auf diese Zweierpotenzen an:
00000001 -> 1
00000010 -> 2
00000100 -> 1
00001000 -> 2
00010000 -> 1
00100000 -> 2
01000000 -> 1
10000000 -> 2
Dies gibt uns den Wert jedes Bits in der Zahl mod 3. Unter Verwendung der Tatsache, dass (a + b)%x = (a%x + b%x)%x, können wir eine kleinere Zahl ableiten, die denselben Wert mod hat 3 als ursprüngliche Zahl:
n2 = cnt[0] + 2*cnt[1] + cnt[2] + 2*cnt[3] + cnt[4] + 2*cnt[5] + cnt[6] + 2*cnt[7];
Dieser Ausdruck ist maximal, wenn alle Bits in cnt gesetzt sind. Durch einfache Addition erhalten wir, dass n2 höchstens 12 ist. Daher ist n2 eine 4-Bit-Zahl.
Wir haben jetzt unsere ursprüngliche 8-Bit-Zahl in eine 4-Bit-Zahl "komprimiert", die denselben Wert mod 3 hat. Das heißt, cnt%3 = n2%3.
Um den tatsächlichen Modulus zu erhalten, müssen wir jetzt nur diese kleine 4-Bit-Zahl mod 3 nehmen, die die Synthese einer Nachschlagetabelle zuordnen wird:
always @(*) begin
if (n2 < 3) cnt_mod3 = n2;
else if (n2 < 6) cnt_mod3 = n2 - 3;
else if (n2 < 9) cnt_mod3 = n2 - 6;
else if (n2 < 12) cnt_mod3 = n2 - 9;
else cnt_mod3 = n2 - 12;
end
Alles, was wir also am Ende brauchten, um den mod3-Ausdruck zu berechnen, war ein Addierer und eine Nachschlagetabelle mit 4 Eingängen.
Dieses Verfahren ist auf beliebig breite Zahlen und beliebige Module anwendbar, solange der Modul konstant ist. Das einzige, was sich ändern wird, ist die Liste der Konstanten, mit denen jedes Bit multipliziert werden muss. Wenn "n2" immer noch zu breit ist (dh 6 Bits oder mehr), nachdem die erste Runde der bitweisen "Komprimierung" angewendet wurde, wenden Sie einfach eine weitere Runde davon an, bis es klein genug ist.
Ich nehme an, cnt ist ein Zähler.
Wenn ja, und wenn es bei 0 (oder einer festen Zahl N) beginnt, warum sollte man dann nicht eine zweite Variable cnt_mod_3 beibehalten, die im selben Moment wie cnt inkrementiert und beim Erreichen von 3 auf 0 zurückgesetzt wird?
Auf diese Weise müssen Sie keine Modulo-/Divisionsberechnungen durchführen und Sie haben keine zusätzliche Verzögerung.
Falls cnt kein Zähler ist (oder zur Laufzeit mit Zahlen initialisiert wird, für die Sie keinen Modulus 3 haben), können Sie sich den folgenden Trick ansehen: N=0b a(n) a(n-1) . .. a(1) a(0). a(0) % 3 = +a(0) % 3 a(1) 0 % 3 = -a(1) % 3 a(2) 0 0 % 3 = +a(2) % 3 ... a( 2 i) 0...0 = +a(2 i) % 3 a(2 i+1) 0...0 = -(a i+1) % 3 ...
Also N%3 = sum( a(i)*(-1)^i) %3
Sie können also N in die Summe ( a (i) * (-1) ^ i) reduzieren, um den Modulus 3 (der eine viel größere Zahl ist) zu überprüfen. Reduzieren Sie um 1 oder mehrere solcher Schritte, entweder bis Sie garantieren können, dass das Ergebnis zwischen 0 und 2 liegt, oder bis es klein genug ist, um eine Nachschlagetabelle zum Abschluss zu verwenden.
NB: Wenn Sie lieber Zahlen ohne Vorzeichen verwendet haben, können Sie 2 a(2 i+1) anstelle von -a(2*i+1) verwenden.