Einsen im Vektor zählen

Manchmal wäre es doch interessant, die Anzahl der gesetzen Bits in einem Vektor zu kennen. Die erste Schritt wäre, einen Stall Addierer zu nehmen, und die alle hintereinanderzuhängen. Das macht ein Design natürlich nicht unbedingt schneller, denn wenn da ein Carry langsam durchtrudeln muss.

Fangen wir einfach mal vorn an und zählen die Bits einfach in einer Schleife:

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;

entity CountOnes is
    Port ( i : in  STD_LOGIC_VECTOR (15 downto 0);
           o : out  STD_LOGIC_VECTOR (4 downto 0));
end CountOnes;

architecture Behavioral of CountOnes is

begin
  -- Spartan 3
  -- Number of Slices       42
  -- Number of 4 input LUTs 73
  process (i) 
  variable cnt : integer range 0 to 16 := 0;
  begin
     cnt := 0;
     for c in 0 to 15 loop
       if i(c)='1' then 
         cnt:=cnt+1; 
       end if;
     end loop;
     o <= std_logic_vector(to_unsigned(cnt,5));
  end process;

  -- Spartan 3
  -- Number of Slices       16
  -- Number of 4 input LUTs 28
  process (i) 
  variable cnt : unsigned (4 downto 0);
  begin
     cnt := "00000";
     for c in 0 to 15 loop
       cnt:=cnt+unsigned'("0000"&i(c)); 
     end loop;
     o <= std_logic_vector(cnt);
  end process;

end Behavioral;

Die erste Variante gibt einen recht aufwendigen Multiplexer und braucht 27ns, die zweite Variante die gewünschten Addierer mit 19ns Durchlaufzeit (incl. IO-Pads Treiber!).

Aber es geht noch schneller (16ns), wenn nämlich nicht eine Addiererkette gebildet wird, sondern erst ein paar kleine Teilsummen gebildet und die dann aufsummiert werden:

  process (i) 
  variable c0  : unsigned (2 downto 0);
  variable c1  : unsigned (2 downto 0);
  variable c2  : unsigned (2 downto 0);
  variable c3  : unsigned (2 downto 0);
  variable cnt : unsigned (4 downto 0);
  begin
     cnt := "00000";
     c0  := "000";
     c1  := "000";
     c2  := "000";
     c3  := "000";
     for c in 0 to 3 loop
       c0 := c0+unsigned'("00"&i(c)); 
       c1 := c1+unsigned'("00"&i(c+4)); 
       c2 := c2+unsigned'("00"&i(c+8)); 
       c3 := c3+unsigned'("00"&i(c+12)); 
     end loop;
     cnt:= unsigned'("00"&c0)+unsigned'("00"&c1)+unsigned'("00"&c2)+unsigned'("00"&c3);
     o <= std_logic_vector(cnt);
  end process;

Auf dem uC.net findet sich der entsprechende Thread: Bits in Wort zählen