Bitlänge ungleich Null bestimmen "length?"

[Student FH Köln (Gast)]

Hallo zusammen,

ich arbeite momentan an meiner Diplomarbeit und habe folgendes Problem 
in VHDL.
Ich möchte die Länge eines Vektors überprüfen (Std_Logic_Vector oder 
Bit_Vector). Mit dem Befehl "length" kann man meines Wissens die gesamte 
Länge eines Vektors auslesen. Mich interessieren allerdings nicht die 
vorstehenden Nullen, sondern nur die Länge ab der ersten 1.

Beispiel:

 Vector X1 = ...00 0000 0111 --> als Ergebnis hätte ich gerne die Zahl 3
 Vector X2 = ...00 0011 0101 --> als Ergebnis hätte ich gerne die Zahl 6

Eine Lösung wäre, von links alle Bits abzufragen und sobald das Erste 
ungleich 0 ist könnte man über eine Zählschleife die Position ermitten. 
Da mein Programm aber sehr schnell arbeiten muss, habe ich maximal 4 
Takte für die Aufgabe zur verfügung und somit wäre eine Schleife zu 
langsam.

Kann mir vielleicht jemand einen Tipp geben, wie ich dieses Problem 
schneller lösen könnte?

MfG

Christoph

[spartanne (Gast)]

Wie lang sind die Vektoren?

[Daniel -. (root)]

vielleicht eine binäre Suche nach der Art

links[n:1],rechts[n:1] <= vec[2n:1]);

when ODER(links) = '1' =>
links[n/2:1],rechts[n/2:1] <= links[n:1]

when ODER(rechts) = '1' =>
links[n/2:1],rechts[n/2:1] <= rechts[n:1]

irgendwie in die Zustände einer State Machine abbilden.

16 bit vector = 2**4 => 4 Takte

[Daniel -. (root)]

du willst doch das synthetisieren oder?
für die simulation oder was am rechner läuft, braucht man
sicher nicht diese verrenkungen.

[Christoph (Gast)]

Die Vektoren sind 32 Bit lang und sie müssen synthetisieren werden. 
Deinen Vorschlag durchschaue ich zwar heute abend nicht mehr auf anhieb, 
werde das morgen aber ausprobieren!

[Martin (Gast)]

Wenns schnell gehen muss dann Bau halt soetwas wie einen Priority 
Encoder.

so in der Art

if (vector(0) = '1') then
  out <= "0001";
end if

if (vector(1) = '1') then
  out <= "0010";
end if

Das kostet zwar ein bisschen Logik geht aber auf jeden Fall in einem 
Takt.

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

Kürzer geschrieben ginge es etwa so:

entity MSB is
    Port ( data : in  STD_LOGIC_VECTOR (31 downto 0);
           msb1 : out  STD_LOGIC_VECTOR (4 downto 0));
end MSB;

architecture Behavioral of MSB is
signal msbint1 : integer range 0 to 31;
begin
  msbint1 <= 31 when data(31)='1' else
             30 when data(30)='1' else
             29 when data(29)='1' else
             28 when data(28)='1' else
                 :
              4 when data( 4)='1' else
              3 when data( 3)='1' else
              2 when data( 2)='1' else
              1 when data( 1)='1' else
              0;

   msb1 <= std_logic_vector(to_unsigned(msbint1,msb1'length));
end Behavioral;

Das ergibt dann eine recht aufwendige Kombinatorik:

Selected Device : 3s50pq208-5 
 Number of Slices:                      23  out of    768     2%  
 Number of 4 input LUTs:                40  out of   1536     2%  
:
 Maximum combinational path delay: 19.263ns

Kompakter liest sich eine For-Schleife:

   process (data) 
   variable foundbit : std_logic;
   begin
      foundbit := '0';
      msbint2 <= 0;
      for i in 31 downto 0 loop
         if (data(i)='1' and foundbit='0') then 
            msbint2  <= i;
            foundbit := '1';
         end if;
      end loop;
   end process;
  
   msb2 <= std_logic_vector(to_unsigned(msbint2,msb2'length));

Aber das Ergebnis ist suboptimal, weil die for-Schleife weiter 
durchlaufen wird, auch wenn eine '1' gefunden wurde:

Selected Device : 3s50pq208-5 
 Number of Slices:                      51  out of    768     6%  
 Number of 4 input LUTs:                87  out of   1536     5%  
  :
 Maximum combinational path delay: 24.339ns

Dritter Versuch: eine While-Schleife.

   process (data) 
   variable i : integer range 0 to 31;
   begin
      i := 31;
      while (data(i)='0') loop 
         i := i-1;
      end loop;
      msbint2 <= i;
   end process;
  
   msb2 <= std_logic_vector(to_unsigned(msbint2,msb2'length));

Damit lässt sich auch in der Laufzeit (auf Kosten einiger Slices) noch 
was holen:

Selected Device : 3s50pq208-5 
 Number of Slices:                      28  out of    768     3%  
 Number of 4 input LUTs:                47  out of   1536     3%  
  :
 Maximum combinational path delay: 18.821ns

Eine For-Schleife mit EXIT sieht so aus:

   process (data) 
   begin
      msbint2 <= 0;
      for i in 31 downto 0 loop
         if (data(i)='1') then 
            msbint2 <= i;
            exit;
         end if;
      end loop;
   end process;

   msb2 <= std_logic_vector(to_unsigned(msbint2,msb2'length));

Hier wird exakt die selbe Logik wie mit dem auscodierten Encoder 
erzeugt:

Selected Device : 3s50pq208-5 
 Number of Slices:                      23  out of    768     2%  
 Number of 4 input LUTs:                40  out of   1536     2%  
  :
 Maximum combinational path delay: 19.263ns

[christian (Gast)]

Bei den ganzen For- und While-Schleifen wird nur die Bedingung, das 
Ganze in vier Takten zu lösen, nicht eingehalten.
Ich würde das ganze parallel mit If aufbauen:

if data(31) = '1' then
msb1 = b"11111";
elsif data(30) = '1' then
msb1 = b"11110";
...

oder nach dem ersten Beispiel von Lothar Miller, was ich fast noch 
schöner finde.

Bei wem schreibst du denn die Diplomarbeit. Hab letztes Jahr an der 
FH-Köln meinen Abschluß gemacht.
Viel Erfolg!

[Duke Scarring (Gast)]

@christian:
> Bei den ganzen For- und While-Schleifen wird nur die Bedingung, das
> Ganze in vier Takten zu lösen, nicht eingehalten.
Du hast das Konzept der Schleifen in VHDL und paralleler Hardware noch 
nicht verstanden.

Die Beispiele von Lothar dauern genau einen Takt, wenn der im besten 
Fall nicht schneller als 18.821ns ist.

Duke

[christian (Gast)]

@Duke:
> Du hast das Konzept der Schleifen in VHDL und paralleler Hardware noch
> nicht verstanden.
Sieht so aus :-). Ich komm eigentlich aus der Programmierung. Ich dachte 
schleifen laufen auch in VHDL sequentiel ab, oder liegt das daran, daß 
der Prozess nicht geclockt ist?

[Martin K. (mkohler)]

christian wrote:
> Ich komm eigentlich aus der Programmierung.
Echt? Hätten wir nie gedacht ;-)

> Ich dachte schleifen laufen auch in VHDL sequentiel ab,
Ja, das ist ein typischer Anfängerfehler

> oder liegt das daran, daß > der Prozess nicht geclockt ist?
Nein, das liegt daran, dass mit VHDL Hardware (Gatter, Register, usw.) 
beschrieben wird und nicht ein Stück Ablaufsoftware.

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

> Bei den ganzen For- und While-Schleifen wird nur die Bedingung, das
> Ganze in vier Takten zu lösen, nicht eingehalten.
Wie Duke es schon gesagt hat, ist das Ganze absolut taktlos.
Entweder läuft das Design mit 50MHz, dann ist es nach 1 Takt fertig.
Oder das Design läuft mit 200MHz, dann braucht dieser "MSB-Sucher" 
meherer Zyklen (Multi-Cycle) und ist in 4 Takten fertig.