Modulofunktion

[Steven H. (mme365)]

Guten Abend Community

Ich suche für ein kleiners Projekt, einen fertigen Modulo-Algorithmus ( 
x mod 7) für unsigned Variablen mit max. 8 bit.

vielleicht hat ja jemand sowas schon mal geschrieben und würde es mit 
mir Teilen?

Gruß Steven

[Cakaes (Gast)]

Welche Sprache/Controller?

m = x % 7;

[Steven H. (mme365)]

VHDL (ISE)

[Burkhard K. (buks)]

Steven H. schrieb:
> VHDL (ISE)

Siehe z.B. https://www.csee.umbc.edu/portal/help/VHDL/operator.html. 
Unsigned nach Integer casten, Modulo berechnen und dann mit 
to_unsigned() zurückwandeln.

[Steven H. (mme365)]

Ganz so einfach, das man einfach den Typ wechselt, ist es leider nicht.
Das Maximum für die Mod-Berechnung in VHDL (ISE) liegt leider bei 2 
sprich ( x mod 2)
Sprich man braucht einen Divisionsalgorithmus + die Ausgabe des Restes

[Yalu X. (yalu) (Moderator)]

Gesucht ist:

  y₂y₁y₀ =  x₇x₆x₅x₄x₃x₂x₁x₀ mod 7

Das kann nach folgendem Schema ohne Division berechnet werden:

a₃a₂a₁a₀ = x₅x₄x₃ + x₂x₁x₀

  b₂b₁b₀ =   x₇x₆ +     a₃

c₃c₂c₁c₀ = a₂a₁a₀ + b₂b₁b₀

  d₂d₁d₀ =     c₃ + c₂c₁c₀

           ⎧ 0 0 0   falls d₂=d₁=d₀=1
  y₂y₁y₀ = ⎨
           ⎩ d₂d₁d₀  sonst

Da ich kein VHDL kann, darfst du den Rest selber erledigen :)

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

Steven H. schrieb:
> Ganz so einfach, das man einfach den Typ wechselt, ist es leider nicht.
> Das Maximum für die Mod-Berechnung in VHDL (ISE) liegt leider bei 2
> sprich ( x mod 2)
Mitnichten. Wenn man %7 hinschreibt und alles in 1 Takt erledigt haben 
will, dann macht der Synthesizer einen kombinatorischen Divider.
Siehe z.B. den Beitrag "Re: Rechnen mit unsigned vs. signed und einer division"

> Sprich man braucht einen Divisionsalgorithmus + die Ausgabe des Restes
Man kann auch "hinreichend genau" auf eine Multiplikation mit 
anschließendem "Abschneiden" (aka Division duch Zweierpotenz) 
ausweichen:
mod7 <= x-7*((x*9362)/65536);

Der Trick dabei 9362/65536 = 1/7,000213

[Burkhard K. (buks)]

Steven H. schrieb:
> Das Maximum für die Mod-Berechnung in VHDL (ISE) liegt leider bei 2
> sprich ( x mod 2)

Etwas mehr geht schon, tatsächlich kann der XST für Series 7 u.a.:
  rem - Supported if the right operand is a constant power of 2
  mod - Supported if the right operand is a constant power of 2

https://www.xilinx.com/support/documentation/sw_manuals/xilinx14_7/xst_v6s6.pdf:

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

Burkhard K. schrieb:
> Etwas mehr geht schon, tatsächlich kann der XST für Series 7 u.a.:
>   rem - Supported if the right operand is a constant power of 2
>   mod - Supported if the right operand is a constant power of 2
Das geht schon immer. Es ist ja nur ein "Weglassen" der unteren Bits.
Im Prinzip funktioniert das aber nur bei Unsigned Vektoren korrekt...

[VHDL hotline (Gast)]

Für 8 bit, sprich 256 Werte, kann man die vorberechneten Werte einfach 
in einem Speicher hinterlegen, den man mit dem Wert selbst addressiert.

[Hagen R. (hagen)]

@Yalu: geht dein beschriebener Trick so zu generalisieren?

y = x mod (2^k-1)

wiederhole 
  x = (x / 2^k) + (x and (2^k-1))
solange bis x <= (2^k-1)

wenn x = (2^k-1) dann y = 0 ansonsten y = x.

Wobei natürlich die Division von x / 2^k ein simpler rechts Shift ist.

Kennst du noch andere solche Tricks, zb. modulo (x^y +- z)

Gruß hagen

[Yalu X. (yalu) (Moderator)]

Hagen R. schrieb:
> @Yalu: geht dein beschriebener Trick so zu generalisieren?
> y = x mod (2^k-1)
>
> wiederhole
>   x = (x / 2^k) + (x and (2^k-1))
> solange bis x <= (2^k-1)
>
> wenn x = (2^k-1) dann y = 0 ansonsten y = x.

Ja, genau.

Genauso wie der Neunerrest im Dezimalsystem über die Quersumme berechnet
werden kann (https://de.wikipedia.org/wiki/Neunerrest), ist dies für den
Siebenerrest im Oktalsystem oder allgemein für den Rest modulo n-1 im
Stellenwertsystem zur Basis n möglich. Man macht sich dabei zunutze,
dass

  n^i mod (n-1) = 1  für alle i ∈ ℕ

Ist n eine Zweierpotenz (n=2^k), dann wird die Zerlegung einer im
Binärsystem gegebenen Zahl in Ziffern besonders einfach, da dann jede
Ziffer einer Gruppe von k Bits entspricht. Man kann damit leicht die
Reste modulo 3, 7, 15 usw. berechnen.

Den Algorithmus für das Ganze hast du ja oben in sehr eleganter Form
hingeschrieben.

> Wobei natürlich die Division von x / 2^k ein simpler rechts Shift ist.

Auf dem FPGA muss nicht einmal unbedingt geshiftet werden. Da die Anzahl
der benötigten Additionen bei gegebener Bitbreite der zu bearbeitenden
Zahl nach oben beschränkt ist, kann die Berechnung rein kombinatorisch
(also ohne Flipflops) erfolgen.

> Kennst du noch andere solche Tricks, zb. modulo (x^y +- z)

Modulo n+1 in der Basis n geht auch relativ leicht, nämlich über die
alternierende Quersumme. Damit können mit einem ähnlichen Verfahren die
Reste modulo 2^k+1 (5, 9, 17 usw.) berechnet werden. Hier macht man sich
zunutze, dass

  n^i mod (n+1) = (-1)^i  für alle i ∈ ℕ

Möglicherweise wird die Umsetzung für ein FPGA wegen der negativen
Zwischenergebnisse etwas kniffliger.

[Hagen R. (hagen)]

Danke Yalu

[J. S. (engineer)]

Yalu X. schrieb:

> Möglicherweise wird die Umsetzung für ein FPGA wegen der negativen
> Zwischenergebnisse etwas kniffliger.
Nicht unbedingt, man müsste sie nach meinem Verständnis als unsigned 
halten können, um bei den Berechnungen nicht schief zu laufen, weil sie 
"restklassenmäßig" dann stimmen müssten.

[Markus F. (mfro)]

Lothar M. schrieb:
> Man kann auch "hinreichend genau" auf eine Multiplikation mit
> anschließendem "Abschneiden" (aka Division duch Zweierpotenz)
> ausweichen:
> mod7 <= x-7*((x*9362)/65536);
>
> Der Trick dabei 9362/65536 = 1/7,000213

Auch das lässt sich generalisieren: 
https://homepage.divms.uiowa.edu/~jones/bcd/divide.html (oder, wenn man 
lieber Bücher liest, "Hacker's Delight, 2nd Edition"): Multiplikationen 
mit dem binären Kehrwert, die man anschliessend in Shifts und Additionen 
zerlegt:

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

entity tb2 is
end tb2;

architecture rtl of tb2 is
begin
    p_initial : process
        variable n      : unsigned(7 downto 0);
        variable u_div  : unsigned(7 downto 0);
        variable u_mod  : unsigned(7 downto 0);
    begin
        for i in 0 to 255 loop
            n := to_unsigned(i, 8);
            u_div := shift_right(n, 1) + shift_right(n, 4);    
            u_div := shift_right(u_div + shift_right(u_div, 6), 2);
            u_mod := n - (shift_left(u_div, 3) - u_div);
            u_div := u_div + shift_right(u_mod + 1, 3);
            if u_mod > 6 then
                u_mod := u_mod - 7;
            end if;
            report "i = " & integer'image(i) & " div 7 = " & integer'image(to_integer(u_div)) & "," &
                                               " mod 7 = " & integer'image(to_integer(u_mod)) severity note;
        end loop;
        wait;
    end process p_initial;
end architecture rtl;

u_div ist der Quotient und u_mod der Rest. Der bei der angenäherten 
Division entstehende Fehler lässt sich leicht korrigieren.

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

Markus F. schrieb:
> Multiplikationen mit dem binären Kehrwert, die man anschliessend in
> Shifts und Additionen zerlegt
Es stimmt natürlich, dass man Multiplikationen durch Additionen und 
Subtraktionen von Zweierpotenzen ersetzen kann. Aber wenn noch ein 
Multipizierer übrig ist (und das ist er typischerweise bei denen, die 
solche Fragen stellen... ;-) dann muss man die Multiplikation nicht 
weiter optimieren.