In VHDL ..... wie führende Nullen des Vektors zählen?

Question

Ich arbeite in einem VHDL-Projekt und ich habe ein Problem, um die Länge des Vektors zu berechnen. Ich weiß, dass es ein Längenattribut eines Vektors gibt, aber das ist nicht die Länge, nach der ich suche. Zum Beispiel habe ich std_logic_vector

E : std_logic_vector(7 downto 0); 

dann

E <= "00011010"; 

so, len = E'length = 8 aber ich bin nicht dafür suchen. Ich möchte len nach dem Verwerfen der linken Nullen, so len = 5;

Ich weiß, dass ich für die Schleife verwenden kann, indem Sie "0" s Bits von links nach rechts und stoppen, wenn "1" Bit auftreten. Aber das ist nicht effizient, weil ich 1024 oder mehr Bits habe und das wird meine Schaltung verlangsamen. Gibt es also eine Methode oder einen Algorithmus, um die Länge effizient zu berechnen? So wie die Verwendung kombinatorischer Gatter mit log (n) -Pegel von Gattern (wobei n = Anzahl von Bits).

Answer 1

Was Sie mit Ihrer "Bit-Zählung" tun, sehr ähnlich dem Logarithmus (Basis 2).

Dies wird häufig in VHDL verwendet, um herauszufinden, wie viele Bits erforderlich sind, um ein Signal darzustellen. Wenn Sie beispielsweise bis zu N Elemente im RAM speichern möchten, ist die Anzahl der Bits, die für die Adressierung dieses RAM erforderlich sind, ceil (log2 (N)). Dazu verwende ich:

function log2ceil(m:natural) return natural is 
begin -- note: for log(0) we return 0 
    for n in 0 to integer'high loop 
     if 2**n >= m then 
      return n; 
     end if; 
    end loop; 
end function log2ceil; 

Normalerweise möchten Sie dies zur Synthesedauer mit Konstanten tun, und Geschwindigkeit ist kein Problem. Sie können aber auch FPGA-Logik generieren, wenn Sie das wirklich wollen. Wie bereits erwähnt, wird eine "for" -Schleife in VHDL nur verwendet, um eine Nachschlagetabelle zu erzeugen, die aufgrund langer Signalwege langsam ist, aber immer nur einen einzigen Takt benötigt.

Was passieren kann ist, dass Ihre maximale Taktfrequenz sinkt. Normalerweise ist dies nur ein Problem, wenn Sie mit Vektoren arbeiten, die größer als 64 Bit sind (Sie haben 1024 Bit erwähnt), und schneller als 100 MHz getaktet. Vielleicht hat dir der Synthesizer schon gesagt, dass das dein Problem ist, ansonsten schlage ich vor, dass du es zuerst versuchst.

Dann müssen Sie den Vorgang über mehrere Uhren aufteilen und einige Zwischenergebnisse in ein FF speichern. (Ich würde im Voraus vergessen, den Synthesizer auszutricksen, indem ich den Code neu anordne. Eine Nachschlagetabelle ist eine Tabelle. Warum sollte es wichtig sein, wie Sie die Werte in dieser Tabelle erzeugen? Aber stellen Sie sicher, dass Sie dem Synthesizer sagen: "Egal "Werte, wenn Sie sie haben." Wenn Sie Geschwindigkeit haben, verwenden Sie die erste Uhr, um alle 16-Bit-Blöcke parallel (unabhängig voneinander) zu überprüfen, und verwenden Sie dann einen zweiten Taktzyklus, um die Ergebnisse aller 16-Bit zu kombinieren Blöcke in ein einzelnes Ergebnis.Wenn es um die FPGA-Logik geht, implementieren Sie eine Zustandsmaschine, die bei jedem Taktzyklus einen einzelnen 16-Bit-Block prüft.

Aber seien Sie vorsichtig, dass Sie dabei die CPU nicht neu erfinden.

Answer 2

Nun, VHDL ist keine SW, es braucht keine Zeit, um eine Operation wie diese durchzuführen, es braucht nur Ressourcen von Ihrem FPGA.

Sie können Ihre 1024-Bit-Daten in einen 32-Bit-Abschnitt unterteilen und zwischen allen Bits ein ODER durchführen. Auf diese Weise können Sie jeweils 32 Bits überprüfen. Es ist nicht wirklich notwendig, da die for-Schleife perfekt funktionieren würde für das, was Sie tun wollen, schreiben Sie einfach den Code, suchen Sie nach der ersten 1 im Array und stoppen Sie die Schleife und verwenden Sie die Indexnummer als Zeiger auf den ersten 1 in Ihrem Array. Ich habe diesen Code nicht kompilieren, aber so etwas wie dies sollte für Sie arbeitet:

FirstOne <= 1023; 
for i in E'reverse_range loop 
    if (E(i) == '1') then 
    FirstOne <= i; 
    exit; 
    end if; 
end loop; 

Es wird nicht so ein großen Blöcke innerhalb eines FPGA, nachdem alle.

Answer 3

Das Problem bei der Verwendung einer Schleife ist, dass Sie bei der Synthese möglicherweise eine sehr lange Logikkette erhalten.

Eine andere Möglichkeit, Ihr Problem zu untersuchen, besteht darin, den Index des höchstwertigen gesetzten Bits zu finden. Dazu können Sie einen Prioritäts-Encoder verwenden. Das Schöne daran ist, dass Sie einen Codierer mit großer Priorität erstellen können, indem Sie Codierer mit kleinerer Priorität in einer Baumstruktur verwenden, also ist die Verzögerung O (log N) anstelle von O (N). Hier

ist ein 4-Bit-Prioritätscodierer: http://en.wikibooks.org/wiki/VHDL_for_FPGA_Design/Priority_Encoder Sie können eine 16-Bit-Prioritätscodierer machen mit 5 dieser Blöcke, dann ein 256-Bit-Encoder von fünf 16-Bit-Encoder, usw.

Aber da Sie haben so viele Bits wird es ziemlich groß sein.

Answer 4

Die meisten Synthesizer unterstützen heutzutage rekursive Funktionen. Und in der Tat wird diese geben Sie log(N) vergleichbare Komplexität, wobei N die Anzahl der Bits ist:

• Schneiden Sie Ihre Vektor in zwei Hälften
• Wenn die obere Hälfte sind alle Nullen
  • Das führende Bit Ihrer Antwort '1', niedrige Bits hängen von der unteren Hälfte Vektor
• Ansonsten
  • das führende Bit Ihrer Antwort ist '0', niedrige Bits d epend auf der oberen Hälfte Vektor
• Recurse auf dem halben Vektor von Interesse oben
gewählt