Generic Priority Encoder

[Altera_Forum]

Is there a better way to generate a generic priority encoder without IF/ELSEIF? I need the parameterize my encoder (before synthesis), without recoding manually every time. I have manually coded up a fixed priority encoder, and clearly IF/ELSEIF is less optimal than using CASE statement. But I haven't been able to keep it generic without using IF/ELSEIF. It needs to be minimal logic layers.

[Altera_Forum]

What is priority encoder? I have never heard of it as a concept but I know some of us use this word for if/else/... and I am not sure if case statement is priority as it implies parallel logic. So it will help to know what is your priority encoder inputs/outputs and what is'it meant to do?

[Altera_Forum]

TO_BE_DONE

[Altera_Forum]

using if/elsif: 

 Proc_priority_encoder2 : process(s_CLOCK, s_RESET) --worse performance over CASE statement begin  if (s_RESET = '1') then    s_DEC_IN_Q1 <= (others=>'0');  s_DEC_OUT_Q1 <= (others=>'0');    elsif (s_CLOCK'event and s_CLOCK='1') then    s_DEC_IN_Q1 <= s_DEC_IN;    if (s_DEC_IN_Q1 = "000000000000000001") then  s_DEC_OUT_Q1 <= "00000001";  elsif (s_DEC_IN_Q1 = "000000000000000010") then  s_DEC_OUT_Q1 <= "00000010";  elsif (s_DEC_IN_Q1 = "000000000000000011") then  s_DEC_OUT_Q1 <= "00000011";  elsif (s_DEC_IN_Q1 = "000000000000000100") then  s_DEC_OUT_Q1 <= "00000100";  elsif (s_DEC_IN_Q1 = "000000000000001000") then  s_DEC_OUT_Q1 <= "00000101";  elsif (s_DEC_IN_Q1 = "000000000000010000") then  s_DEC_OUT_Q1 <= "00000110";  elsif (s_DEC_IN_Q1 = "000000000000100000") then  s_DEC_OUT_Q1 <= "00000111";  elsif (s_DEC_IN_Q1 = "000000000001000000") then  s_DEC_OUT_Q1 <= "00001000";  elsif (s_DEC_IN_Q1 = "000000000010000000") then  s_DEC_OUT_Q1 <= "00001001";  elsif (s_DEC_IN_Q1 = "000000000100000000") then  s_DEC_OUT_Q1 <= "00001010";  elsif (s_DEC_IN_Q1 = "000000001000000000") then  s_DEC_OUT_Q1 <= "00001011";  elsif (s_DEC_IN_Q1 = "000000010000000000") then  s_DEC_OUT_Q1 <= "00001100";  elsif (s_DEC_IN_Q1 = "000000100000000000") then  s_DEC_OUT_Q1 <= "00001101";  elsif (s_DEC_IN_Q1 = "000001000000000000") thenp  s_DEC_OUT_Q1 <= "00001110";  elsif (s_DEC_IN_Q1 = "000000000010000000") then  s_DEC_OUT_Q1 <= "00001111";  elsif (s_DEC_IN_Q1 = "000000000010000000") then  s_DEC_OUT_Q1 <= "00010000";  elsif (s_DEC_IN_Q1 = "000000000010000000") then  s_DEC_OUT_Q1 <= "00010001";  elsif (s_DEC_IN_Q1 = "000000000010000000") then  s_DEC_OUT_Q1 <= "00010011";  else  s_DEC_OUT_Q1 <= "00000000";  end if;    end if; end process;

[Altera_Forum]

Read about priority encoders here: http://www.electronics-tutorials.ws/combination/comb_4.html 

 The problem with IF/ELSEIF is too many mux layers, and for a 64-bit priority encoder, obviously that is too many layers.  BTW, priority encoders are very common. I just need a really big one, and it has to be generic.

[Altera_Forum]

Thanks for the link. After a quick glance it looks like(unless proved otherwise) this not really fpga area but rather combinatorial circuits meant for some ICs. FPGAs do not have this problem to merit this type of design. But it is interesting to know that.

[Altera_Forum]

mbmckeon, 

if I'm reading it correctly, the two pieces of code you have written do not have the same behavior. The first is a typical priority encoder, while the second will output "00000000" if two inputs are active at the same time. That may explain the   Beyond that, unless the tool has limitations (which it often does), if you express the SAME behavior, then it doesn't matter if you're using CASE or IF/ELSE.

[Altera_Forum]

--- Quote Start ---  clearly IF/ELSEIF is less optimal than using CASE statement  --- Quote End ---   Why, particularly?  There's a discussion about priority encoder coding methods in the advanced synthesis cookbook. http://www.altera.com/literature/manual/stx_cookbook.pdf  In terms of synthesis efficiency, there seems to be a problem of the Quartus synthesis tool (and probably others too) to utilize the carry chain for non-arithmetical problems. The synthesis cookbook overcomes it by utilizing an adder for the first step of a priority encoder, the priority masking.  Without this problems, we would expect that functional equivalent descriptions of the priority encoder synthesize to the same logic (e.g. case or if elseif), but unfortunately it's not the case. A straightforward behavioral description of the priority encoder can be written as a for loop.   You should also check the results of the altpriority_encoder MegaFunction for comparison.

[Altera_Forum]

As rbugalho pointed out, the case and if-elsif-else example don't implement the same logic, and there is apparently a typo in the first lines of the if-elsif code. So I#m not totally sure about the intended function.  

 I assume that lsb_priority with 1-based index is intended. See below two parameterizable variants. altpriority_encoder is faster and needing fewer logic elements than the behavioral description. I used two pipeline levels according to the original example.  If you want to enforce a faster implementation in arithmetic mode (using carry chain), there are other options. The code won't be that straightforward, however.  To decide about the implementation, we need to know the intended fmax and maximum number of bits.  t2: IF typ = 2 generate process(s_CLOCK, s_RESET) begin if (s_RESET = '1') then s_DEC_IN_Q1 <= (others=>'0'); s_DEC_OUT_Q1 <= (others=>'0'); elsif (s_CLOCK'event and s_CLOCK='1') then s_DEC_IN_Q1 <= s_DEC_IN; for I in 0 to NBIT-1 loop if s_DEC_IN_Q1(i) = '1' then s_DEC_OUT_Q1 <= std_logic_vector(to_unsigned(i,nbita)+1); exit; end if; s_DEC_OUT_Q1 <= (others => '0'); end loop; end if; end process; end generate; t3: IF typ = 3 generate pe: altpriority_encoder generic map ( lsb_priority => "YES", pipeline => 1, width => nbit, widthad => nbita) port map ( aclr => S_RESET, clock => S_CLOCK, data=> s_DEC_IN, q => s_DEC_OUT ); process(s_CLOCK, s_RESET) begin if (s_RESET = '1') then s_DEC_OUT_Q1 <= (others=>'0'); elsif (s_CLOCK'event and s_CLOCK='1') then s_DEC_OUT_Q1 <= std_logic_vector(unsigned(s_DEC_OUT)+1); end if; end process; end generate;

[Altera_Forum]

The behavior I want is in example 1. I didn't verify example 2, and looking back there is probably a mistake anyway (zeros to right should be don't care, after ones). In either case, what I meant about being optimal is speed wise, I don't care if it uses more or less resources. My design ideally would be able to run in excess of 333 MHz which might not be realistic, but the closer I can get to that number or beyond the better, and I want to minimize logic layers. FvM I did find the code for example t2 in another book, and is nice and compact code, but I don't know what performance I can achieve yet. The input width's could be anywhere between 12-64. I was not able to find any information on altpriority_encoder, I can't find it in the MegaWizard. Where exactly is it located?

[Altera_Forum]

I also searched for the altpriority_encoder to no avail! 

But I did find this little gem in QII 9.1SP2 megafunctions directory: C:\altera\91sp2\quartus\libraries\megafunctions => a_priority_encoder.tdf. It is in (good old) AHDL. One day I might (will) try the same in VHDL. I have a related recursive function in VHDL to filter out the highest bit set in a std_logic_vector, but this returns a one-hot vector instead of a number.

[Altera_Forum]

I couldn't find it in my altera_mf_components.vhd file, but I instantiated it anyway and it seems to work. Maybe it's been moved to another file? 

 I did find a website here, but again couldn't find it in my own file: http://subversion.assembla.com/svn/cpu-lab3/altera_mf_components.vhd  Just search for, altpriority_encoder

[Altera_Forum]

--- Quote Start ---  I couldn't find it in my altera_mf_components.vhd file, but I instantiated it anyway and it seems to work. Maybe it's been moved to another file?  --- Quote End ---   The VHDL component definition is in quartus\libraries\vhdl\altera_mf\altera_mf_components.vhd, for all Quartus versions since V7 at least.  Altera is using it in many arithmetic MegaFunctions internally, for some reason, they didn't document the function.  component altpriority_encoder generic ( lsb_priority : string := "NO"; pipeline : natural := 0; width : natural; widthad : natural; lpm_hint : string := "UNUSED"; lpm_type : string := "altpriority_encoder" ); port( aclr : in std_logic := '0'; clk_en : in std_logic := '1'; clock : in std_logic := '0'; data : in std_logic_vector(width-1 downto 0); q : out std_logic_vector(widthad-1 downto 0); zero : out std_logic ); end component;    --- Quote Start ---  My design ideally would be able to run in excess of 333 MHz which might not be realistic.  --- Quote End ---   With how many pipeline (register) levels? Which FPGA family? You have already 2 register levels (in- and output registers) in your example code.

[Altera_Forum]

I've been looking in another directory \quartus\eda\sim_lib 

 That is because according to this link, http://www.altera.com/support/examples/modelsim/simulation-manual-howto.html  that is where it tells you where to compile from in modelsim project. I'm in Quartus 11.0SP1 and if you search in that directory it's missing, but I do see it in the other directory.  Anyway, I'm currently in a Stratix V GS - D8.

[Altera_Forum]

Is this function not supported in ModelSim?? When I compile the altera_mf, I don't see it in the library. Any thoughts?

[Altera_Forum]

--- Quote Start ---  Is this function not supported in ModelSim?? When I compile the altera_mf, I don't see it in the library. Any thoughts?  --- Quote End ---    I found it here: \altera\quartus\libraries\vhdl\altera_mf

[Altera_Forum]

--- Quote Start ---  Is this function not supported in ModelSim?? When I compile the altera_mf, I don't see it in the library. Any thoughts?  --- Quote End ---   There is probably no functional simulation model. altpriority_encoder is used internally in the synthesis of several arithmetic MegaFunctions, but apperently not in the respective simulation models.  But what's the point of simulating altpriority_encoder? For the functional simulation you can replace it by a simple behavioral model as suggested previously in this thread. If you are interested in timing behaviour, you'll refer to gate level simulation.

[Altera_Forum]

Any MegaFunction should have an associated model. The priority encoder is simple enough to generate my own behavioral model, but I shouldn't have to if it's an Altera IP. I'm also not simulating just the encoder by itself, it's of course a part of a much larger system model, and it will be used many times all with different input parameters. I don't really want to get involved in the gate level stuff until I get a functional model working, it just slows down the work flow. Thanks.