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 --- Case statements would only inflate the code. josyb has shown an exact solution of your original problem, taking advantage of the VHDL iteration constructs. If you want a pure combinational solution for some reason, you can simply remove the if rising_edge(clk) condition. 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. The suggested solution gives the results specified in your original post. --- Quote End --- 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..- Altera_Forum--- Quote Start --- Actually it can be done in a combinatorial way but you dont take a case statement approach... i think there is a way... --- Quote End --- Case statements would only inflate the code. josyb has shown an exact solution of your original problem, taking advantage of the VHDL iteration constructs. If you want a pure combinational solution for some reason, you can simply remove the if rising_edge(clk) condition. 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 Start --- i dont know how to remove those extra zeros. --- Quote End --- The suggested solution gives the results specified in your original post.
- Altera_Forum
Thanks for your replies..people.
- Altera_Forum--- Quote Start --- only as guide, not tested
--- Quote End --- No for loops because i dont know what circuit will the synthesizer make out of that...process(data_in) begin for i in 0 to 15 loop if data_in(i) = '0' then data_out(i*4:i*4+3) <= "0000"; else data_out(i*4:i*4+3) <= std_logic_vector(to_unsigned(i,4)); end if; end loop; end process; - Altera_Forum--- Quote Start --- This will not be straightforward to realise in a combinatorial circuit because what you describe is a rather sequential process: traverse the input vector from right to left, if you encounter a bit set to '1' add its position index into the next available output slot. This doesn't mean it can't be done combinatorially, but the result will be huge as it has to cater for all combinations (all 65356 of them ...). --- Quote End --- Actually it can be done in a combinatorial way but you dont take a case statement approach... i think there is a way... Actually i have managed to get a partial output. eg if input is 16'b0000_0000_0001_0101 then i have managed to get the output 64'h0000_0000_0004_0200... i dont know how to remove those extra zeros. In this case the expected output is 64'h0000_0000_0000_0420.
- Altera_Forum--- Quote Start --- e.g. for bit 3, i == 3 and you will fill in nibble 3, but if this was the first bit (set to '1') encountered nibble 0 should get value 3. I don't think your code is doing that. Anyway I compiled my proposition, and it is actually not too bad, The compiler generated 477 LCs for a Cyclone II device. I still (would/will) have to simulate it. --- Quote End --- if bit index == 3 then it equals 3, how then it equals something else? it is physically decided at input declaration.
- Altera_Forum
And simulated. 466 LC, 80 registers, 105 MHz in a Cyclone II EP2C5F256C6.
It uses a lot less resources than I initially guessed. Just showing how awesome powerful VHDL is. (Verilog very, very probably too)library ieee; use ieee.std_logic_1164.all; use IEEE.numeric_std.all; entity bitpos is port ( Clk : in std_logic ; data_in : in std_logic_vector(15 downto 0) ; data_out : out std_logic_vector(63 downto 0) ); end bitpos ; architecture a of bitpos is signal ld : std_logic_vector(15 downto 0) ; begin process(clk) variable j : natural ; variable lq : std_logic_vector(63 downto 0) ; begin if rising_edge(Clk ) then ld <= data_in ; j := 0 ; lq := (others => '0') ; for i in 0 to 15 loop if ld(i) = '1' then lq(j*4+3 downto j*4) := std_logic_vector(to_unsigned(i,4)); j := j + 1 ; end if; end loop; data_out <= lq ; end if ; end process; end a ; - Altera_Forum--- Quote Start --- the loop index is going up anyway. for bit index 3 then output nibble = 3 if it is '1' else nibble = 0 --- Quote End --- e.g. for bit 3, i == 3 and you will fill in nibble 3, but if this was the first bit (set to '1') encountered nibble 0 should get value 3. I don't think your code is doing that. Anyway I compiled my proposition, and it is actually not too bad, The compiler generated 477 LCs for a Cyclone II device. I still (would/will) have to simulate it.
- Altera_Forum
the loop index is going up anyway. for bit index 3 then output nibble = 3 if it is '1' else nibble = 0
- Altera_Forum--- Quote Start --- only as guide, not tested
--- Quote End --- That doesn't do what ganeshmirajkar put forward, as e.g. bitposition 3 will always fill something into output nibble 3. So we need at least a variable. Steeling your code snippet:process(data_in) begin for i in 0 to 15 loop if data_in(i) = '0' then data_out(i*4:i*4+3) <= "0000"; else data_out(i*4:i*4+3) <= std_logic_vector(to_unsigned(i,4)); end if; end loop; end process;
I wonder how this compiles.process(data_in) variable j : natural ; begin j := 0 ; data_out <= (others => '0') ; for i in 0 to 15 loop if data_in(i) = '1' then data_out(j*4:j*4+3) <= std_logic_vector(to_unsigned(i,4)); j := j + 1 ; end if; end loop; end process;
