right_shift und "/" liefern unterschiedliche Ergbnisse

[dito (Gast)]

Hallo,

warum kommen denn bei folgendem VHDL-Code in der Simulation mit Modelsim 
unterschiedliche Ergebnisse raus?

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

entity test is
  port(
    result0 : out signed(5 downto 0);
    result1 : out signed(5 downto 0)
    );
end test;

architecture beh of test is
  signal a: signed(5 downto 0) := to_signed(-27, 6); -- b"100101"
begin
  result0 <= shift_right(a, 2); -- -7   b"111001"
  result1 <= a/4;               -- -6   b"101001"
end beh;

"-7" hätte ich auch für result1 erwartet, da ich davon ausgegangen bin, 
dass eine Divsion durch eine Potenz von 2 immer auf einen Shift 
zurückgeführt wird.

Bitte um Aufklärung!
Danke
dito

[Jan M. (mueschel)]

Bei einer Integerdivision werden per Definition immer die 
Nachkommastellen abgeschnitten (27/4=6.75 -> 6).
Beim Schieben wird hier anscheinend (wo kommt diese Funktion eigentlich 
her, ist die in numeric_std?) das höchstwertige Bit dupliziert, das 
entspricht bei negativen Zahlen einem aufrunden auf die nächste ganze 
Zahl (-27/4=-6.75 -> -7).

Die beiden Operationen sind also nicht äquivalent.

[dito (Gast)]

Ja, right_shift ist in numeric_std enthalten.

Was du schreibst ist zwar richtig, aber dann müsste ja -6 rauskommen 
(beachte, dass wir uns im Zweierkomplement befinden und bei negativen 
Zahlen wird dann aufgerundet). Mit ist unklar, wie das Bitmuster für -6 
zustande kommt.

[dito (Gast)]

Sorry meinte, natürlich "aber dann müsste ja -7 rauskommen".

[Georg A. (Gast)]

> -6   b"101001"

Ich sehe zwischen den beiden Werten keine Entsprechung, das binäre ist 
doch -23... Fipptehler?

[dito (Gast)]

Ja sorry. -6 entspricht natürllich b"111010"

Erklären kann ich mir das aber trotzdem nicht. Wenn die Division in 
Hardware durch "Abschneiden" und "Auffüllen" - also durch Schieben - 
umgesetzt wird, bedeutet dies, dass zwischen Simulation und Synthese ein 
Unterschied besteht?

[dito (Gast)]

Hmm, wie es aussieht hat hier niemand eine plausible Erklärng für mich 
parat.
Ich habe selbst noch ein wenig recherchiert und das hier gefunden:

"It is frequently stated that arithmetic right shifts are equivalent to 
division by a (positive, integral) power of the radix (e.g. a division 
by a power of 2 for binary numbers), and hence that division by a power 
of the radix can be optimized by implementing it as an arithmetic right 
shift. (A shifter is simpler than a divider. On some processors, shift 
instructions will execute more quickly than division instructions.) 
Steele quotes a large number of 1960s and 1970s programming handbooks, 
manuals, and other specifications from companies and institutions such 
as DEC, IBM, Data General, and ANSI that make such statements. However, 
as Steele points out, they are all wrong.

Arithmetic right shifts are only equivalent to division by a power of 
the radix on an "N-1's-complement" machine (for radix "N"). Arithmetic 
shifts of binary numbers are only equivalent to division by a power of 2 
when the one's complement representation of signed numbers is being 
used, for example."

Quelle: http://en.wikipedia.org/wiki/Arithmetic_shift

Das Dividieren mir einer Potenz von 2 ist im Allgemeinen also nicht 
äquivalent mit dem Rechtsshift bei Zweikomplementzahlen. Interessant.

Mit dem "/"-Operator habe ich auch einen höheren Ressourcenverbrauch, da 
vermutlich erst ein Vergleich auf kleiner 0 durchgeführt wird und dann 
ggf. eine Addition mit "-1" durchgeführt wird.

[Hagen R. (hagen)]

Naja, das kommt auf die Sichtweise an. Eine Division mit einer Potenz 
von 2 ist bei 2'er Complement mit einem arithmetischen Rechtsshift sehr 
wohl identisch. Aber eben nicht mit einem binär logischen Rechtsshift.

Sogesehen ist / 2 eben nicht das Gleiche wie shr 1 sondern hängt von der 
Zahlendarstellung ab. Nicht umsonst kennen viele Prozessoren zwei 
Varianten von Link/Rechtsshifts. Zb. shr und asr.

Deine Deklaration mit signed() impliziert einen vorzeichen behafteten 
Wert und demzufolge macht zb. / 4 einen arithmetischen Rechtsshift von 
2.
Du benutzt aber mit right_shift() sicherlich einen binär logischen 
Rechtsshift ohne Beachtung des Vorzeichens. Wenn der Inhalt im Signal a 
also positiv ist (oberstes Bit nicht gesetzt) werden beide Operationen 
das gleiche Resulat liefern. Ist a aber negativ dann nicht mehr.

Gruß Hagen

[Matthias F. (flint)]

Ich denke das ganze ich nicht so esoterisch sondern liegt einfach daran, 
wie numeric_std die Division implementiert. Keine Ahnung ob das jetzt 
stellvertretend für alle Implementierungen stehen kann aber in der von 
diesem Link

http://www.csee.umbc.edu/help/VHDL/packages/numeric_std.vhd

passiert genau das: Division von signed durch integer wird auf Division 
von signed durch signed zurückgeführt. In dieser wird dann überprüft, ob 
einer der beiden Werte negativ ist (in diesem Beispiel -27), wenn ja 
wird das Inverse bzgl der Addition genommen (also 27), dann die Division 
mit positiven Zahlen durchgeführt (27/4 ergibt wie zu erwarten 6) und 
dann wird das Ergebnis von 0 abgezogen (also -6). Passt doch alles 
zusammen und ist ein wunderbares Beispiel dafür, dass man diese 
Funktionen für die Synthese wohl einfach gar nicht brauchen kann.

lg
flint

[dito (Gast)]

@ Hagen Re:
> Du benutzt aber mit right_shift() sicherlich einen binär logischen
> Rechtsshift ohne Beachtung des Vorzeichens.

Nein, shift_right() gilt auch für signed-Werte.

@  Matthias F.
> Passt doch alles zusammen und ist ein wunderbares Beispiel dafür,
> dass man diese Funktionen für die Synthese wohl einfach gar nicht
> brauchen kann.

Also sollte man für synthesefähige Designs auf den "/"-Operator 
verzichten und lieber manuell shiften (zumindest im signed-Fall)?

[Läubi .. (laeubi)]

dito schrieb:
> @ Hagen Re:
>> Du benutzt aber mit right_shift() sicherlich einen binär logischen
>> Rechtsshift ohne Beachtung des Vorzeichens.
>
> Nein, shift_right() gilt auch für signed-Werte.
Aber bei signed werte unterscheidet man normalerweise zwischen einem 
(logischen) shift nach rechts (lsr) und einem Arithmetischem shift nach 
rechts (asr), beim Linksschift gibt es dieses unterscheidung i.A. nicht.

Bei sowas

result1 <= a/4;

Müßte man gff. auch mal schauen wie da die Regeln sind was die Synthese 
fabriziert wenn signed durch unsigned gerechnet wird.

Dann könnte es nämlich sein das erstmal a um ein Bit erweitert wird, 
geteilt/geschoben wird und dann wieder auf die ursprüngliche Breite 
gebracht wird.

-27 = 100101

Fall 1:
 2x (Arithmetisch) nach rechts geschoben => 111001

Fall 2:
 Beide Operanden um das Vorzeichenbit erweitern
 (s)1100101 / (u)0000100         | umwandeln in unsigned/unsigned
 (u)011001 / (u)0000100 = 000110 | erste Stelle streichen
 = 00110                         | Vorzeichenbit setzen
 => 10110

Und schon hast du dein "falsches" Ergebnis...

@  Matthias F.
> Passt doch alles zusammen und ist ein wunderbares Beispiel dafür,
> dass man diese Funktionen für die Synthese wohl einfach gar nicht
> brauchen kann.
Versteh ich nicht so ganz... Das Verhalten scheint mir hier so 
vermutlich durch den VHDL Standard festgelegt es gibt für VHDL bestimmt 
auch ne Übersicht wie bei Unterschiedlicher "signedness" zu verfahren 
ist...
Man müßte mal probieren was rauskommt wenn man die 4 explizit als signed 
Zahl deklariert.

[D. I. (Gast)]

Läubi .. schrieb:

> Aber bei signed werte unterscheidet man normalerweise zwischen einem
> (logischen) shift nach rechts (lsr) und einem Arithmetischem shift nach
> rechts (asr), beim Linksschift gibt es dieses unterscheidung i.A. nicht.

Das halte ich für ein Gerücht.
Selbst GNU (und andere) Assembler kennen shl und sal

[Jörg W. (dl8dtl) (Moderator)]

Christopher D. schrieb:

> Selbst GNU (und andere) Assembler kennen shl und sal

Nein, Assembler kennen das, was die zu Grunde liegende CPU
implementiert.  Beim i386 und seinen Verwandten gibt es in der
Tat beide Befehlsnamen, aber beide bezeichnen die gleiche
Operation.  Sind gewissermaßen nur aus Symmetriegründen mit
beiden Namen aufgenommen worden.  Ähnliche Praktiken gibt es
auch bei anderen CPUs, bspw. kennt ein AVR einen Opcode "CLR Rn",
der weiter nichts ist als ein "XOR Rn, Rn".

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

> Selbst GNU (und andere) Assembler kennen shl und sal
Ja, aber das wird dann so ein Pseudo-Befehl sein, wie z.B.
clr R0
beim AVR das ja einfach durch ein
xor R0,R0
implementiert ist.

Pech, wieder mal Zweiter ;-)

[Duke Scarring (Gast)]

Hier mal was für die Synthesetools:

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

entity shift_or_division is
    port ( slv       : in  std_logic_vector (7 downto 0);

           uns_shift : out std_logic_vector (7 downto 0);
           uns_div   : out std_logic_vector (7 downto 0);
           sig_shift : out std_logic_vector (7 downto 0);
           sig_div   : out std_logic_vector (7 downto 0)
       );
end shift_or_division;

architecture bhv of shift_or_division is

begin
    
    uns_div   <= std_logic_vector( unsigned(slv) / 8);
    uns_shift <= std_logic_vector( shift_right( unsigned(slv), 3));

    sig_div   <= std_logic_vector(   signed(slv) / 8);
    sig_shift <= std_logic_vector( shift_right(   signed(slv), 3));

end architecture bhv;

Bei XST (9.2.04i) kommt das angehängte Bild raus.

Es sieht ganz dannach aus, das Shift und Division und bei signed 
verschiedene Ergebnisse liefern. Bei unsigned werden wie erwartet nur 
Leitungen gelegt.

Duke

[Duke Scarring (Gast)]

@Läubi:
> Müßte man gff. auch mal schauen wie da die Regeln sind was die Synthese
> fabriziert wenn signed durch unsigned gerechnet wird.

Laut ieee.numeric_std und der Tabelle (Arithmetic Operators) unter
http://www.eda.org/comp.lang.vhdl/FAQ1.html#4.8.1
ist signed durch unsigned nicht definiert. Nur signed/integer und 
unsigned/natural.

Duke

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

Eigenartig: der Alias rechts oben gibt mir zu denken...  :-/

BTW:
Wo ist denn da der unsigned div abgeblieben?

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

So, die Simulation zeigt, dass der Thread richtig benannt ist:
>>>>> right_shift und "/" liefern unterschiedliche Ergbnisse  <<<<<
Der Code ist der obige von Duke Scarring, ich gebe ein paar Vektoren vor 
(slv) und erhalte die Werte im Screenshot.
Die ersten 5 Zeilen werden in Vektordarstellung angezeigt. Dann kommen 3 
Zeilen, die unsigned angezeigt werden. Danach noch drei Zeilen, die 
signed angezeigt werden.

Und in diesen letzten drei Zeilen sieht man, dass die Werte -1 bis -7 
unterschiedliche Ergebnisse liefern. QED.

[Duke Scarring (Gast)]

Hier noch eine passende Testbench:

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

entity shift_or_division_tb_vhd is
end shift_or_division_tb_vhd;

architecture bhv of shift_or_division_tb_vhd is 

  -- component declaration for the unit under test (uut)
  component shift_or_division
  port(
    slv : in std_logic_vector(7 downto 0);          
    uns_shift : out std_logic_vector(7 downto 0);
    uns_div : out std_logic_vector(7 downto 0);
    sig_shift : out std_logic_vector(7 downto 0);
    sig_div : out std_logic_vector(7 downto 0)
    );
  end component;

  --inputs
  signal slv :  std_logic_vector(7 downto 0) := (others=>'0');

  --outputs
  signal uns_shift :  std_logic_vector(7 downto 0);
  signal uns_div   :  std_logic_vector(7 downto 0);
  signal sig_shift :  std_logic_vector(7 downto 0);
  signal sig_div   :  std_logic_vector(7 downto 0);

begin

  -- instantiate the unit under test (uut)
  uut: shift_or_division port map(
    slv       => slv,
    uns_shift => uns_shift,
    uns_div   => uns_div,
    sig_shift => sig_shift,
    sig_div   => sig_div
  );

  tb : process
  variable l : line;
  begin

    for i in -15 to 15 loop
    
      slv <= std_logic_vector( to_signed(i, 8));
      wait for 6 ns; -- approx. the real time, for synthesis report
      
      write(l, "i: "         & integer'image( i) & ht);
      write(l, "uns_shift: " & integer'image( to_integer( unsigned(uns_shift))) & ht);
      write(l, "uns_div: "   & integer'image( to_integer( unsigned(uns_div)))   & ht);
      write(l, "sig_shift: " & integer'image( to_integer( signed(sig_shift)))   & ht);
      write(l, "sig_div: "   & integer'image( to_integer( signed(sig_div)))     & ht);
      writeline(output, l);
    
    end loop;

    wait; -- will wait forever
  end process;

end;

Ich bevorzuge die Ausgabe in Textform :-)

Duke

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

> Ich bevorzuge die Ausgabe in Textform :-)
Aber ich war schneller  ;-)

[Duke Scarring (Gast)]

@Lothar:

> Eigenartig: der Alias rechts oben gibt mir zu denken...  :-/
Das soll wohl den shift_right enthalten.

Das RTL-Schematic von ISE 11.1 war komplett unbrauchbar :-(

> BTW:
> Wo ist denn da der unsigned div abgeblieben?
Das entspricht ja dem uns_shift. Aber gesehen hätte ich es auch gern.

Vielleicht kann ja der geneigte Leser mal gucken, was ISE 11.2 oder 
Quartus draus macht.

Duke

[Duke Scarring (Gast)]

Nachtrag:
XST kann auch durch andere Zahlen als nur durch Zweierpotenzen 
dividieren (und offenbar auch synthetisieren). Im RTL-Viewer kann man 
dann sehen, was da draus wird. Früher hätte man dazu TTL-Grab gesagt ;-)

Duke

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

>> Ich bevorzuge die Ausgabe in Textform :-)
> Aber ich war schneller  ;-)
Es ist viel schlimmer als vermutet...
ich habe durch mein Schlüsselloch nicht alles gesehen  :-(

# i: -128  uns_shift: 16  uns_div: 16  sig_shift: -16  sig_div: -16  
# i: -127  uns_shift: 16  uns_div: 16  sig_shift: -16  sig_div: -15  
# i: -126  uns_shift: 16  uns_div: 16  sig_shift: -16  sig_div: -15  
# i: -125  uns_shift: 16  uns_div: 16  sig_shift: -16  sig_div: -15  
# i: -124  uns_shift: 16  uns_div: 16  sig_shift: -16  sig_div: -15  
# i: -123  uns_shift: 16  uns_div: 16  sig_shift: -16  sig_div: -15  
# i: -122  uns_shift: 16  uns_div: 16  sig_shift: -16  sig_div: -15  
# i: -121  uns_shift: 16  uns_div: 16  sig_shift: -16  sig_div: -15  
# i: -120  uns_shift: 17  uns_div: 17  sig_shift: -15  sig_div: -15  
# i: -119  uns_shift: 17  uns_div: 17  sig_shift: -15  sig_div: -14  
# i: -118  uns_shift: 17  uns_div: 17  sig_shift: -15  sig_div: -14  
# i: -117  uns_shift: 17  uns_div: 17  sig_shift: -15  sig_div: -14  
# i: -116  uns_shift: 17  uns_div: 17  sig_shift: -15  sig_div: -14  
# i: -115  uns_shift: 17  uns_div: 17  sig_shift: -15  sig_div: -14  
# i: -114  uns_shift: 17  uns_div: 17  sig_shift: -15  sig_div: -14  
# i: -113  uns_shift: 17  uns_div: 17  sig_shift: -15  sig_div: -14  
:
:
# i: -21  uns_shift: 29  uns_div: 29  sig_shift: -3  sig_div: -2  
# i: -20  uns_shift: 29  uns_div: 29  sig_shift: -3  sig_div: -2  
# i: -19  uns_shift: 29  uns_div: 29  sig_shift: -3  sig_div: -2  
# i: -18  uns_shift: 29  uns_div: 29  sig_shift: -3  sig_div: -2  
# i: -17  uns_shift: 29  uns_div: 29  sig_shift: -3  sig_div: -2  
# i: -16  uns_shift: 30  uns_div: 30  sig_shift: -2  sig_div: -2  
# i: -15  uns_shift: 30  uns_div: 30  sig_shift: -2  sig_div: -1  
# i: -14  uns_shift: 30  uns_div: 30  sig_shift: -2  sig_div: -1  
# i: -13  uns_shift: 30  uns_div: 30  sig_shift: -2  sig_div: -1  
# i: -12  uns_shift: 30  uns_div: 30  sig_shift: -2  sig_div: -1  
# i: -11  uns_shift: 30  uns_div: 30  sig_shift: -2  sig_div: -1  
# i: -10  uns_shift: 30  uns_div: 30  sig_shift: -2  sig_div: -1  
# i: -9  uns_shift: 30  uns_div: 30  sig_shift: -2  sig_div: -1  
# i: -8  uns_shift: 31  uns_div: 31  sig_shift: -1  sig_div: -1  
# i: -7  uns_shift: 31  uns_div: 31  sig_shift: -1  sig_div: 0  
# i: -6  uns_shift: 31  uns_div: 31  sig_shift: -1  sig_div: 0  
# i: -5  uns_shift: 31  uns_div: 31  sig_shift: -1  sig_div: 0  
# i: -4  uns_shift: 31  uns_div: 31  sig_shift: -1  sig_div: 0  
# i: -3  uns_shift: 31  uns_div: 31  sig_shift: -1  sig_div: 0  
# i: -2  uns_shift: 31  uns_div: 31  sig_shift: -1  sig_div: 0  
# i: -1  uns_shift: 31  uns_div: 31  sig_shift: -1  sig_div: 0  
# i: 0  uns_shift: 0  uns_div: 0  sig_shift: 0  sig_div: 0  
# i: 1  uns_shift: 0  uns_div: 0  sig_shift: 0  sig_div: 0  
# i: 2  uns_shift: 0  uns_div: 0  sig_shift: 0  sig_div: 0  
# i: 3  uns_shift: 0  uns_div: 0  sig_shift: 0  sig_div: 0  
# i: 4  uns_shift: 0  uns_div: 0  sig_shift: 0  sig_div: 0  
# i: 5  uns_shift: 0  uns_div: 0  sig_shift: 0  sig_div: 0  
# i: 6  uns_shift: 0  uns_div: 0  sig_shift: 0  sig_div: 0  
# i: 7  uns_shift: 0  uns_div: 0  sig_shift: 0  sig_div: 0  
# i: 8  uns_shift: 1  uns_div: 1  sig_shift: 1  sig_div: 1  
# i: 9  uns_shift: 1  uns_div: 1  sig_shift: 1  sig_div: 1  
# i: 10  uns_shift: 1  uns_div: 1  sig_shift: 1  sig_div: 1  
# i: 11  uns_shift: 1  uns_div: 1  sig_shift: 1  sig_div: 1  
# i: 12  uns_shift: 1  uns_div: 1  sig_shift: 1  sig_div: 1  
# i: 13  uns_shift: 1  uns_div: 1  sig_shift: 1  sig_div: 1  
# i: 14  uns_shift: 1  uns_div: 1  sig_shift: 1  sig_div: 1  
# i: 15  uns_shift: 1  uns_div: 1  sig_shift: 1  sig_div: 1  
# i: 16  uns_shift: 2  uns_div: 2  sig_shift: 2  sig_div: 2  
# i: 17  uns_shift: 2  uns_div: 2  sig_shift: 2  sig_div: 2  
# i: 18  uns_shift: 2  uns_div: 2  sig_shift: 2  sig_div: 2  
# i: 19  uns_shift: 2  uns_div: 2  sig_shift: 2  sig_div: 2  
# i: 20  uns_shift: 2  uns_div: 2  sig_shift: 2  sig_div: 2  
# i: 21  uns_shift: 2  uns_div: 2  sig_shift: 2  sig_div: 2  
# i: 22  uns_shift: 2  uns_div: 2  sig_shift: 2  sig_div: 2  
# i: 23  uns_shift: 2  uns_div: 2  sig_shift: 2  sig_div: 2  
# i: 24  uns_shift: 3  uns_div: 3  sig_shift: 3  sig_div: 3  
# i: 25  uns_shift: 3  uns_div: 3  sig_shift: 3  sig_div: 3  
# i: 26  uns_shift: 3  uns_div: 3  sig_shift: 3  sig_div: 3  
# i: 27  uns_shift: 3  uns_div: 3  sig_shift: 3  sig_div: 3  
# i: 28  uns_shift: 3  uns_div: 3  sig_shift: 3  sig_div: 3  
:
:

[dito (Gast)]

Dem Schematic nach ballert XST ja noch ganz schön was an Logik rein. Da 
wird eine einfache Division durch 2, 4, 8 etc. aber ganz schön teuer... 
:-(

[Matthias F. (flint)]

Man sollte, außer in Testbenches, wohl einfach die Finger vom "*" und 
vom "/" Operator lassen, sondern diese gleich entweder mit 
Multiplizierer-Primitiven implementieren bzw bei Zweierpotenzen einfach 
abschneiden, wenn nötig noch mit dem normalen Rundungsalgorithmus. Wenn 
ein Syntesetool den Code umsetzt, auf den ich da oben verlinkt habe, 
dann kann jedenfalls nichts schönes dabei rauskommen.