www.mikrocontroller.net

Forum: FPGA, VHDL & Co. Bitlänge ungleich Null bestimmen "length?"


Autor: Student FH Köln (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: spartanne (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wie lang sind die Vektoren?

Autor: Daniel -------- (root)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Daniel -------- (root)
Datum:

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

Autor: Christoph (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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!

Autor: Martin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Lothar Miller (lkmiller) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: christian (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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!

Autor: Duke Scarring (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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

Autor: christian (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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?

Autor: Martin Kohler (mkohler)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Lothar Miller (lkmiller) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [vhdl]VHDL-Code[/vhdl]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.