In VHDL ..... come contare gli zeri iniziali del vettore?

Question

Sto lavorando a un progetto VHDL e sto affrontando un problema per calcolare la lunghezza del vettore. So che c'è un attributo di lunghezza di un vettore ma questa non è la lunghezza che sto cercando. Ad esempio, ho std_logic_vector

E : std_logic_vector(7 downto 0); 

poi

E <= "00011010"; 

così, len = E'length = 8 ma io non sono alla ricerca di questo. Voglio calcolare len dopo aver scartato gli zeri più a sinistra, quindi len = 5;

So che posso usare per il ciclo controllando i bit "0" da sinistra a destra e fermarsi se si verifica il bit "1". Ma non è efficiente, perché ho 1024 o più bit e questo rallenterà il mio circuito. Quindi c'è qualche metodo o algoritmo per calcolare la lunghezza in modo efficiente? Come usare le porte combinatorie del livello log (n) delle porte, (dove n = numero di bit).

Answer 1

Cosa si fa con il "conteggio dei bit" molto simile al logaritmo (base 2).

Questo è comunemente usato in VHDL per capire quanti bit sono necessari per rappresentare un segnale. Ad esempio, se si desidera memorizzare fino a N elementi nella RAM, il numero di bit richiesti per indirizzare quella RAM è ceil (log2 (N)). Per questo io uso:

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; 

In genere, si desidera eseguire questa operazione in fase di sintesi con costanti e la velocità non è un problema. Ma puoi anche generare logica FPGA, se è davvero quello che vuoi.

Come altri hanno già detto, un ciclo "for" in VHDL è appena usato per generare una tabella di ricerca, che può essere lenta a causa di lunghi percorsi di segnale, ma richiede solo un solo orologio. Ciò che può accadere è che la frequenza massima del clock si abbassi. Solitamente questo è solo un problema se operate su vettori maggiori di 64 bit (avete menzionato 1024 bit) e orologi più veloci di 100MHz. Forse il sintetizzatore ti ha già detto che questo è il tuo problema, altrimenti ti suggerisco di provare prima.

Quindi è necessario dividere l'operazione su più clock e memorizzare un risultato intermedio in un FF. (Mi dimenticherei in anticipo di provare a battere in astuzia il sintetizzatore riordinando il codice.Una tabella di ricerca è un tavolo.Perché dovrebbe importare come si generano i valori in questa tabella? Ma assicurati di dire al sintetizzatore di "non preoccuparti "valori se li avete.)

Se la velocità è la vostra preoccupazione, utilizzare il primo orologio per controllare tutti i blocchi a 16 bit in parallelo (indipendenti l'uno dall'altro), e quindi utilizzare un secondo ciclo di clock per combinare i risultati di tutti i 16 bit blocca in un unico risultato.Se la quantità di logica FPGA è di tuo interesse, implementa una macchina a stati che controlla un singolo blocco a 16 bit ad ogni ciclo di clock.

Ma attenzione a non reinventare la CPU mentre lo fai.

Answer 2

Bene, VHDL non è SW, non ci vuole tempo per eseguire un'operazione come questa, prende solo risorse dal tuo FPGA.

È possibile dividere i dati a 1024 bit in una sezione a 32 bit ed eseguire un OR tra tutti i bit, in questo modo si controllano 32 bit alla volta. Non è realmente necessario dal momento che il ciclo for funzionerebbe perfettamente bene per quello che vuoi fare, basta scrivere il codice, cercare il primo 1 nell'array e fermare il ciclo e usare il numero indice del loop come puntatore al primo 1 nel tuo array. Non ho fatto compilare questo codice, ma qualcosa di simile dovrebbe funzionare per voi:

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

non sarà un tale grandi blocchi all'interno di un FPGA, dopo tutto.

Answer 3

Il problema con l'utilizzo di un ciclo è che quando si sintetizza si potrebbe ottenere una catena logica molto lunga.

Un altro modo per esaminare il problema è trovare l'indice del bit impostato più significativo. Per fare ciò è possibile utilizzare un encoder di priorità. Il bello di questo è che puoi creare un codificatore con priorità elevata usando codificatori con priorità più piccola in una struttura ad albero, quindi il ritardo è O (log N) invece di O (N).

Ecco un codificatore a 4 bit di priorità: http://en.wikibooks.org/wiki/VHDL_for_FPGA_Design/Priority_Encoder si può fare un codificatore di priorità a 16 bit con 5 di questi blocchi, poi un encoder a 256 bit da cinque a 16 bit encoder, ecc

Ma dal momento che hai così tanti bit sarà abbastanza grande.

Answer 4

La maggior parte dei sintetizzatori in questi giorni supporta le funzioni ricorsive. E in effetti questo vi darà la complessità paragonabile a log(N) dove N è il numero di bit:

• tagliare il vettore in due metà
• Se la metà superiore sono tutti zeri
  • Il bit principale della vostra risposta è '1', bassi bit dipendono dalla metà inferiore vettore
• Altrimenti
  • il bit iniziale della risposta è '0', i bit bassi d epend sulla metà superiore vettore
• Recurse sulla metà vettore di interesse scelto sopra