Solutions for leading one detector

[FvM]

Re: leading one detector

I see the same logic cell amountof 2*nbit - 1 for both methods. And nbit logic cells using low level primitives as reported.

 

[ali_umair21]

Re: leading one detector

I see the same logic cell amountof 2*nbit - 1 for both methods. And nbit logic cells using low level primitives as reported.

I want to ask, what are low level primitives and using them can save some resource?

 

[FvM]

Re: leading one detector

It's the way to access logic cells respectively LUTs directly. The libraries are vendor dependant, you have to refer to the respective documentation.

As I mentioned in my post #11, the leading one detector (priority mask) can be coded as a simple combinational expression. If a FPGA family is able to put the carry part into the logic cell carry chain, than it can be implemented with one logic cell per bit. If the design compiler can't recognize the behavioral description, low level primitives are way to make it implement the option anyway.

In the present case, the adder solution is quite good, speed-wise, so you won't have to dig for low-level alternatives, normally. I only did, because I was disappointed by Quartus not finding the obvious solution.

 

[twb8t5]

Re: leading one detector

As I mentioned in my post #11, the leading one detector (priority mask) can be coded as a simple combinational expression. If a FPGA family is able to put the carry part into the logic cell carry chain, than it can be implemented with one logic cell per bit. If the design compiler can't recognize the behavioral description, low level primitives are way to make it implement the option anyway.
In the present case, the adder solution is quite good, speed-wise, so you won't have to dig for low-level alternatives, normally. I only did, because I was disappointed by Quartus not finding the obvious solution.

What FvM means is that you could use basic gates instead of processes.
I had the same idea as FvM (#11 11-02-11) and wrote this code (that has not been checked in any way) for a single byte:

ENTITY leadingone IS
PORT(ein : IN bit_vector(7 downto 0); aus : OUT bit_vector(2 downto 0));
END ENTITY leadingone;

entity numberone is
port(ein, carry : IN bit; aus : out bit);
end entity numberone;

architecture name of numberone is
begin
aus <= ein and not carry;
end name;

ARCHITECTURE name OF leadingone IS
component numberone
port(ein, carry : IN bit; aus : out bit);
end component numberone;
signal intercon : bit_vector(7 downto 0);
BEGIN
for i in 0 to 6 generate
numberone port map
(ein(i), intercon(i+1), intercon(i));
end generate numberone;
intercon(7) <= ein(7);

-- These 3 lines need to be done differently:
aus(0) <= intercon(7) or intercon(5) or intercon(3) or intercon(1);-- every other bit, uneven
aus(1) <= intercon(7) or intercon(6) or intercon(3) or intercon(2);-- every other pair
aus(2) <= intercon(7) or intercon(6) or intercon(5) or intercon(4);-- every other quad
END name;

I have not found a good way to decode the position though. I generated the code manually for one byte. Plz someone give me an idea for how to do it for an arbitrary length. Shifting and adding is out of the question. All that is needed is a "one-out-of-many-decoder".

 

[twb8t5]

Re: leading one detector

The second question about "tells the position of first 1" (priority encoder) is still pending. There are basically two methods
- based on the output of the leading bit detector, which is already "one hot" encoded.
- based on the input directly
The first solution ends up in a wide or expression for each position bit and one additional for the all zero case, like below:

FOR J IN 0 TO NBITA-1 LOOP
   FOR I IN 0 TO NBIT-1 LOOP
      tmp_mask(I) := to_unsigned(i,NBITA)(J);
   END LOOP;
   q(J) <= OR_REDUCE(tmp_mask AND dataout);
END LOOP;
zero <= NOT OR_REDUCE(dataout);

A consideration about priority encoder designs can be found in the Arbitration chapter of the Altera Advanced Synthesis Cookbook. It also mentions a priority masking method using an adder similar to Permute's suggestion.
https://www.altera.com/literature/manual/stx_cookbook.pdf

The named Altera source contains an example "onehot_to_bin". It works by using the period of the n-th bit in a counter to generate the OR pattern for the n-th result bit. This is done using two loops in a nested fashion. (See FvM's post #13)
I just don't know how I can do it without a process, I prefer a structural description using generate.

 

[FvM]

I just don't know how I can do it without a process, I prefer a structural description using generate.

It's possible with nested generate statements, but less straightforward in my view. You need to declare signals for the or-ed bits, e.g. as a 2D-bit array. Or generate constant bitmasks, similar to the sequential description.

All-in-all, it's just good as an exercise problem. Generating structured constants isn't covered by most VHDL text books, but you'll find the syntax described in the IEEE spec. There's something about a begin statement inside the generate construct.

The synthesis tool needs to cascade logic cells to form the wide or terms if the input has more than 8 or 12 bits. At the same time, it will try to re-use part of the logic terms for other output bits. We usually leave this job to the tool.