Forum Discussion
Altera_Forum
Honored Contributor
Honored ContributorCounting the position of ones in a binary vector
I want to design a combinatorial circuit for an fpga which will count the position of ones in a 16 bit vector.
eg1 if vector is 16'b0000_0000_0011_0101 then output should be 64'h0000_0000_0000_5420 eg2 if vector is 16'b0000_1010_0000_1010 then output should be 64'h0000_0000_0000_b931. Please help. Thanks in advance....22 Replies
Altera_Forum--- Quote Start --- no bugs, no hassle of spaghetti --- Quote End --- This solution is of course consuming much less logic resources, but not corresponding to the original specification - whatever may be it's purpose.- Altera_Forum
no bugs, no hassle of spaghetti
additionally you can add clock or change indexinglibrary ieee; use ieee.std_logic_1164.all; use ieee.numeric_std.all; entity test is port( din : in std_logic_vector(0 to 15); dout: out std_logic_vector(0 to 63) ); end entity; architecture a of test is begin process(din) begin for i in 0 to 15 loop if din(i) = '0' then dout(i*4 to i*4+3) <= "0000"; else dout(i*4 to i*4+3) <= std_logic_vector(to_unsigned(i,4)); end if; end loop; end process; end a; - Altera_Forum--- Quote Start --- This is a "bug" thats been around a while, and have mentioned on our internal wiki. --- Quote End --- Thanks for clarifying. According to josyb, it has been already fixed in V9.1SP2. I accepted the limitation when working with previous Quartus versions and didn't yet figure out, if a variable slice range is required by the VHDL standard. Do you know the exact paragraph in IEEE 1076?
- Altera_Forum--- Quote Start --- I didn't yet proceed to Quartus 10. I compiled under V9.0 with VHDL 1993 settings and got the below error with your recent code. I was under the assumption, that constant slice ranges are required, no idea which other setting may be different. But the point isn't very important. --- Quote End --- This is a "bug" thats been around a while, and have mentioned on our internal wiki. Apparently only Quartus has had a problem with it, no concerns with ISE or Modelsim. Maybe they finally fixed it with Q10!
- Altera_Forum
It looks like Altera 'progresses' on VHDL support on each subsequent release. E.g. 9.1SP2 supports VHDL 2008 but only a subset, 10.1 supports a bit more, but not yet everything (not that we need everything ...). Maybe this also the case with VHDL-1993 support.
- Altera_Forum--- Quote Start --- I used the VHDL 1993 setting in QII 9.1SP2 that I use for waveform simulation. Actually 9.1SP2 produces a faster circuit then 10.1SP1. --- Quote End --- I didn't yet proceed to Quartus 10. I compiled under V9.0 with VHDL 1993 settings and got the below error with your recent code. I was under the assumption, that constant slice ranges are required, no idea which other setting may be different. But the point isn't very important. --- Quote Start --- Error (10394): VHDL error at bitpos.vhd(29): left bound of range must be a constant --- Quote End ---
- Altera_Forum
Wow, a lot of activity while I was away ...
I only added the input and output registers to measure the speed (in TimeQuest you don't get tPD reports unless you set constraints and I was doing this test in QII 10.1SP1) and second to give the compiler a fair chance to get a high speed. Double registering the outputs may even help a bit more. While driving home from the office last night I mused that I could have written it as a function giving a better view:
At the same time I added the generic to find out when we cross the 266 MHz border, at width 8 we get about 200 MHz, at width 4 500MHz+ or maximum speed. A fully pipelined design will need about 1280 registers, and run at maximum speed. Using a Cyclone IV E in stead of a Cyclone II ups the speed form 110 to 121 MHz for a 16 bit input vector (with a tCK setting of 8.0 ns) Compiling it for a width of 8 it gets up to 237 MHz. to FvM: --- Quote Start --- The assignment to the slice lq(j*4+3 downto j*4) isn't accepted at least by my VHDL version, I think a slice must generally needs a constant range. I used a bitwise copy instead. --- Quote End --- I used the VHDL 1993 setting in QII 9.1SP2 that I use for waveform simulation. Actually 9.1SP2 produces a faster circuit then 10.1SP1.library ieee; use ieee.std_logic_1164.all; use IEEE.numeric_std.all; entity bitpos is generic ( WIDTH_D : positive := 16 ) ; port ( Clk : in std_logic ; data_in : in std_logic_vector(WIDTH_D - 1 downto 0) ; data_out : out std_logic_vector(WIDTH_D * 4 - 1 downto 0) ); end bitpos ; architecture a of bitpos is function reportbitpos( v : std_logic_vector) return std_logic_vector is variable j : natural ; variable r : std_logic_vector(v'length * 4 - 1 downto 0) ; begin j := 0 ; r := (others => '0') ; for i in 0 to v'high loop if v(i) = '1' then r(j*4+3 downto j*4) := std_logic_vector(to_unsigned(i,4)); j := j + 1 ; end if; end loop; return r ; end function ; signal ld : std_logic_vector(WIDTH_D - 1 downto 0) ; begin process(clk) begin if rising_edge(Clk ) then ld <= data_in ; data_out <= reportbitpos( ld ) ; end if ; end process; end a ; - Altera_Forum
I found, that the pure combinational solution (without the registers implemented by josyb) results in a tpd of about 17 ns with Cyclone III. So 266 MHz would surely need pipelining.
I didn't try, if the synthesis tool will "pull-in" registers to the synthesis of the behavioral description. As previously reported in the Forum, it does e.g. in the case of a parallel divider. But most likely, you have to break the data path manually to achieve the speed requirement. - Altera_Forum--- Quote Start --- That code will give me the solution but i cannot buy that because i dont know what circuit it will boil down to and so i cannot guaranty that it will work at 266 MHz. Can you tell me what circuit it will amke out of that for loop ?? Thats why i want a gate level circuit.. --- Quote End --- How can you expect to work at 266MHz with a purely combinatorial circuit? plus, for loops do show the circuit if you understand how it works. Plus you could use the RTL viewer to look at the circuit. A for loops makes the source code manageable.
- Altera_Forum
It is sad that in many fora across the web simple solutions get drowned in garbage.
The for loop unfolds to comb logic as follows: if input(0) = '1' then .... end if; if input(1) = '1' then .... end if; if input(2) = '1' then .... end if; etc. until input(15) The compiler unrolls it at compile time. It is just for convenience of writing multiple statements.
