RTL Hardware design issue: Count Leading Zeros CLZ

Hi,

I'm trying to create a Count Leading Zero (CLZ) in VHDL for a project
but i'm having difficulty in finding any information what so ever apart
from an explanation as to what it does, can anyone help?

Can anyone explain what logic would be required to create a CLZ, i've
only found one point of reference on the web which uses a number of
nested multiplexers with the output of one being fed back into the
select line of the next. Any information regarding the hardware/ schema
would be greatly appreciated.

Thanks, Dave

davidc@ad-holdings.co.uk wrote:
> Hi,
>
> I'm trying to create a Count Leading Zero (CLZ) in VHDL for a project
> but i'm having difficulty in finding any information what so ever apart
> from an explanation as to what it does, can anyone help?
>
> Can anyone explain what logic would be required to create a CLZ, i've
> only found one point of reference on the web which uses a number of
> nested multiplexers with the output of one being fed back into the
> select line of the next. Any information regarding the hardware/ schema
> would be greatly appreciated.
>

In rough Verilog:

casez(number)
4'1????: res = 0;
4'b01??: res = 1;
4'b001?: res = 2;
4'b0001: res = 3;
4'b0000: res = 4;
endcase

Cheers,
Jon

> I'm trying to create a Count Leading Zero (CLZ) in VHDL for a project
> but i'm having difficulty in finding any information what so ever apart
> from an explanation as to what it does, can anyone help?
>
> Can anyone explain what logic would be required to create a CLZ, i've
> only found one point of reference on the web which uses a number of
> nested multiplexers with the output of one being fed back into the
> select line of the next. Any information regarding the hardware/ schema
> would be greatly appreciated.

I'd say there is two case :
 - If you have relatively short vector (like 4-8 bits)
 - Longer vectors.

For the first one, just make a case statement, most likely your
compiler will find a good implementation.
For the second case, I guess you can use a priority encoder followed by
a 1hot -> binary encoder.
That will be 3 layer of luts. (2 for the prio encoder, one for the 1hot
to binary converter).
If N is you number of bit :
 Size of the encoder : N + N/4 (IIRC)
 Size of the 1hot to binary converter log2(N) * ceil(N/8)

If you're interested, I'll try to be more precise when I get home and
have more time.

davidc@ad-holdings.co.uk wrote:
> Hi,
> 
> I'm trying to create a Count Leading Zero (CLZ) in VHDL for a project
> but i'm having difficulty in finding any information what so ever apart
> from an explanation as to what it does, can anyone help?
> 
> Can anyone explain what logic would be required to create a CLZ, i've
> only found one point of reference on the web which uses a number of
> nested multiplexers with the output of one being fed back into the
> select line of the next. Any information regarding the hardware/ schema
> would be greatly appreciated.
> 
> Thanks, Dave
> 


Perhaps you might find this useful:

http://tima-cmp.imag.fr/~guyot/Cours/Oparithm/english/Flottan.htm

Cheers,

Andy

davidc@ad-holdings.co.uk wrote:

> Hi,
> 
> I'm trying to create a Count Leading Zero (CLZ) in VHDL for a project
> but i'm having difficulty in finding any information what so ever apart
> from an explanation as to what it does, can anyone help?
> 
> Can anyone explain what logic would be required to create a CLZ, i've
> only found one point of reference on the web which uses a number of
> nested multiplexers with the output of one being fed back into the
> select line of the next. Any information regarding the hardware/ schema
> would be greatly appreciated.
> 
> Thanks, Dave
> 

The best way depends on what you intend to do with the count.  If it 
will be used to left-justify the data, then the best approach is to use 
a series of 2:1 muxes with each layer controlled by the previous layer's 
output.  The control function is easiest if you use sign-magnitude 
notation rather than two's complement, since that makes it strictly 
leading zeros rather than redundant sign.  The mux on the last layer 
shifts by 1 bit or passes unchanged, the previous layer by 2 bits or 
unchanged, the one before that 4 bits or unchanged and so on.  The 
select decision for each layer forms 1 bit of the leading zero count, 
which is the same as the number of positions the data was shifted left.

If, on the other hand, you are not also shifting the data, then you need 
some form of priority encoder to encode the position of the first 1. 
The Xilinx 4000 series was nice for this because the carry chain could 
go up or down the chip, so you could set it up to propagate down and use 
it as a first '1' detect (a one-hot signal), which is very easy to 
encode into a leading zero count without having to propagate a 'carry' 
in the encoder.

Thanks for the info guys it's starting to make sense.

On Dec 7, 6:49 pm, Ray Andraka <r...@andraka.com> wrote:
> dav...@ad-holdings.co.uk wrote:
> > Hi,
>
> > I'm trying to create a Count Leading Zero (CLZ) in VHDL for a project
> > but i'm having difficulty in finding any information what so ever apart
> > from an explanation as to what it does, can anyone help?
>
> > Can anyone explain what logic would be required to create a CLZ, i've
> > only found one point of reference on the web which uses a number of
> > nested multiplexers with the output of one being fed back into the
> > select line of the next. Any information regarding the hardware/ schema
> > would be greatly appreciated.
>
> > Thanks, DaveThe best way depends on what you intend to do with the count.  If it
> will be used to left-justify the data,

There is no practicle intention, it's more of an exercise to understand
how it works, so i'm mearly try to count the number of leading zeros
starting at the most significant bit.

> then the best approach is to use
> a series of 2:1 muxes with each layer controlled by the previous layer's
> output.

Similar to the CLZ diagram in the link provided by Andy above:

http://tima-cmp.imag.fr/~guyot/Cours/Oparithm/english/Flottan.htm

The diagram in the following link uses muxes, but they have multiple
outputs why is this? or are they adders in the diagram?

> The control function is easiest if you use sign-magnitude
> notation rather than two's complement, since that makes it strictly
> leading zeros rather than redundant sign.  The mux on the last layer
> shifts by 1 bit or passes unchanged, the previous layer by 2 bits or
> unchanged, the one before that 4 bits or unchanged and so on.  The
> select decision for each layer forms 1 bit of the leading zero count,
> which is the same as the number of positions the data was shifted left.
>

OK, so the output of each mux is fed into the "next layer's" input mux
and in addition to this the select line SEL forms the total output of
the circuit.

So if I had an 8 bit input, the output would be 4 bits. so on the first
layer which is uses 2 bit muxes on the input, for an 8 bit CLZ the
first layer would have 4 SEL lines, are these just connect together to
form the first bit of the output?

something like:

 0   1              2   3          4   5             6   7
 |    |                |    |          |    |              |    |
--------   S        --------  S    --------   S       --------  S
|       |----|        |      |----|    |       |----|       |
|----|            2's
--------             --------         --------           --------
    |                  |
    |_____    ___|
             |    |
            --------
            |       |
            4's
            --------

I this instance for output bit 0 all the "S" would be connected
together, is this coreect?

Is there any additional digital circuity required or is it all done
using muxes and "not" gates for the inputs.

Is there any way of doing this using Karnaugh maps, i've had experience
before with them, but where would I start on something like this?

Thanks,
Dave

> If, on the other hand, you are not also shifting the data, then you need
> some form of priority encoder to encode the position of the first 1.
> The Xilinx 4000 series was nice for this because the carry chain could
> go up or down the chip, so you could set it up to propagate down and use
> it as a first '1' detect (a one-hot signal), which is very easy to
> encode into a leading zero count without having to propagate a 'carry'
> in the encoder.

davidc@ad-holdings.co.uk wrote:
> Thanks for the info guys it's starting to make sense.
> 
> On Dec 7, 6:49 pm, Ray Andraka <r...@andraka.com> wrote:
> 
>>dav...@ad-holdings.co.uk wrote:
>>
>>>Hi,
>>
>>>I'm trying to create a Count Leading Zero (CLZ) in VHDL for a project
>>>but i'm having difficulty in finding any information what so ever apart
>>>from an explanation as to what it does, can anyone help?
>>
>>>Can anyone explain what logic would be required to create a CLZ, i've
>>>only found one point of reference on the web which uses a number of
>>>nested multiplexers with the output of one being fed back into the
>>>select line of the next. Any information regarding the hardware/ schema
>>>would be greatly appreciated.
>>
>>>Thanks, DaveThe best way depends on what you intend to do with the count.  If it
>>
>>will be used to left-justify the data,
> 
> 
> There is no practicle intention, it's more of an exercise to understand
> how it works, so i'm mearly try to count the number of leading zeros
> starting at the most significant bit.
> 
> 
>>then the best approach is to use
>>a series of 2:1 muxes with each layer controlled by the previous layer's
>>output.
> 
> 
> Similar to the CLZ diagram in the link provided by Andy above:
> 
> http://tima-cmp.imag.fr/~guyot/Cours/Oparithm/english/Flottan.htm
> 
> The diagram in the following link uses muxes, but they have multiple
> outputs why is this? or are they adders in the diagram?
> 
> 
>>The control function is easiest if you use sign-magnitude
>>notation rather than two's complement, since that makes it strictly
>>leading zeros rather than redundant sign.  The mux on the last layer
>>shifts by 1 bit or passes unchanged, the previous layer by 2 bits or
>>unchanged, the one before that 4 bits or unchanged and so on.  The
>>select decision for each layer forms 1 bit of the leading zero count,
>>which is the same as the number of positions the data was shifted left.
>>
> 
> 
> OK, so the output of each mux is fed into the "next layer's" input mux
> and in addition to this the select line SEL forms the total output of
> the circuit.
> 
> So if I had an 8 bit input, the output would be 4 bits. so on the first
> layer which is uses 2 bit muxes on the input, for an 8 bit CLZ the
> first layer would have 4 SEL lines, are these just connect together to
> form the first bit of the output?
> 
> something like:
> 
>  0   1              2   3          4   5             6   7
>  |    |                |    |          |    |              |    |
> --------   S        --------  S    --------   S       --------  S
> |       |----|        |      |----|    |       |----|       |
> |----|            2's
> --------             --------         --------           --------
>     |                  |
>     |_____    ___|
>              |    |
>             --------
>             |       |
>             4's
>             --------
> 
> I this instance for output bit 0 all the "S" would be connected
> together, is this coreect?
> 
> Is there any additional digital circuity required or is it all done
> using muxes and "not" gates for the inputs.
> 
> Is there any way of doing this using Karnaugh maps, i've had experience
> before with them, but where would I start on something like this?
> 
> Thanks,
> Dave
> 
> 
>>If, on the other hand, you are not also shifting the data, then you need
>>some form of priority encoder to encode the position of the first 1.
>>The Xilinx 4000 series was nice for this because the carry chain could
>>go up or down the chip, so you could set it up to propagate down and use
>>it as a first '1' detect (a one-hot signal), which is very easy to
>>encode into a leading zero count without having to propagate a 'carry'
>>in the encoder.
> 
> 

David, close but not quite.

Let's consider a 16 bit input.  You can have from 0 to 16 leading 0's 
(16 leading zeros is a special case, it is 15 where the data is also 0). 
  In this case we shift left 0 to 15 places, left shifting if all the 
leading bits for that shift are '0'.  This is done with 4 layers of 2:1 
muxes shifting by 8,4,2 and then 1 bits.  Each layer's shift select is 
the logical OR of the left N bits (N=8,4,2 and 1) so that a shift only 
occurs if all those left bits are 0.

lyr8 <= din(7 downto 0) & X"00" when din(15 downto 8)=X"00" else din;
sout(3) <= '1' when din(15 downto 8)=X"00" else '0';
lyr4 <= lyr8(11 downto 0) & X"0" when lyr8(15 downto 12)=X"0" else lyr8;
sout(2) <= '1' when lyr8(15 downto 12)=X"0" else '0';
lyr2 <= lyr4(13 downto 0) &"00" when lyr4(15 downto 14)="00" else lyr4;
sout(1) <= '1' when lyr4(15 downto 14)="00" else '0';
dout <= lyr2(14 downto 0) & '0' when lyr2(15)='0' else lyr2;
sout(0) <= '1' when lyr2(15)='0' else '0';

This works if din is unsigned because you only have leading '0's.  If 
din is 2's complement data, then you have leading sign bits instead of
leading '0', so the detection at each stage is made more difficult; in 
that case it has to see if all the bits that will get shifted out match 
the leftmost retained bit instead of just being zero so the detect 
function has an additional term:  when din(15 downto 7)="000000000" or 
din(15 downto 7)="111111111";  This precludes some shortcuts like using 
the carry chain to perform the detect.  It is often easier to convert 
from 2's complement notation to sign-magnitude notation, which is an 
unsigned magnitude plus an independent sign bit.  The conversion is done 
by performing the 2's complement if the 2's complement input is negative 
to get an unsigned magnitude, and then retaining the sign bit.  (this 
description is to answer a question posed by email).

>
> Let's consider a 16 bit input.  You can have from 0 to 16 leading 0's
> (16 leading zeros is a special case, it is 15 where the data is also 0).
>   In this case we shift left 0 to 15 places, left shifting if all the
> leading bits for that shift are '0'.  This is done with 4 layers of 2:1
> muxes shifting by 8,4,2 and then 1 bits.  Each layer's shift select is
> the logical OR of the left N bits (N=8,4,2 and 1) so that a shift only
> occurs if all those left bits are 0.



OK, so the "top" layer has 8 x 2-1 muxes for a 16 bit input (A0-A15),
the select line for each are connected together
by a logical OR function, the inputs of which are the left N bits - so
in this case would the inputs to the OR gate be A15-A8 or is it
"A1, A3, A5, A7, A9, A11, A13, and A15" which are all OR'd together and
the output goes to each select line SEL for
that particular layer?


>
> lyr8 <= din(7 downto 0) & X"00" when din(15 downto 8)=X"00" else din;
> sout(3) <= '1' when din(15 downto 8)=X"00" else '0';
> lyr4 <= lyr8(11 downto 0) & X"0" when lyr8(15 downto 12)=X"0" else lyr8;
> sout(2) <= '1' when lyr8(15 downto 12)=X"0" else '0';
> lyr2 <= lyr4(13 downto 0) &"00" when lyr4(15 downto 14)="00" else lyr4;
> sout(1) <= '1' when lyr4(15 downto 14)="00" else '0';
> dout <= lyr2(14 downto 0) & '0' when lyr2(15)='0' else lyr2;
> sout(0) <= '1' when lyr2(15)='0' else '0';
>
> This works if din is unsigned because you only have leading '0's.  If
> din is 2's complement data, then you have leading sign bits instead of
> leading '0', so the detection at each stage is made more difficult; in
> that case it has to see if all the bits that will get shifted out match
> the leftmost retained bit instead of just being zero so the detect
> function has an additional term:  when din(15 downto 7)="000000000" or
> din(15 downto 7)="111111111";  This precludes some shortcuts like using
> the carry chain to perform the detect.  It is often easier to convert
> from 2's complement notation to sign-magnitude notation, which is an
> unsigned magnitude plus an independent sign bit.  The conversion is done
> by performing the 2's complement if the 2's complement input is negative
> to get an unsigned magnitude, and then retaining the sign bit.  (this
> description is to answer a question posed by email).

I understand what you mean as negative numbers have a "1" at the most
significant bit which will give a 0 for the CLZ. I think i'll leave the
2's compliment for now ;D

Thanks

davidc@ad-holdings.co.uk wrote:

>>Let's consider a 16 bit input.  You can have from 0 to 16 leading 0's
>>(16 leading zeros is a special case, it is 15 where the data is also 0).
>>  In this case we shift left 0 to 15 places, left shifting if all the
>>leading bits for that shift are '0'.  This is done with 4 layers of 2:1
>>muxes shifting by 8,4,2 and then 1 bits.  Each layer's shift select is
>>the logical OR of the left N bits (N=8,4,2 and 1) so that a shift only
>>occurs if all those left bits are 0.
> 
> 
> 
> 
> OK, so the "top" layer has 8 x 2-1 muxes for a 16 bit input (A0-A15),
> the select line for each are connected together
> by a logical OR function, the inputs of which are the left N bits - so
> in this case would the inputs to the OR gate be A15-A8 or is it
> "A1, A3, A5, A7, A9, A11, A13, and A15" which are all OR'd together and
> the output goes to each select line SEL for
> that particular layer?
> 
> 
select for first layer (lyr8 below) is the logical or of bits 15:8 of 
the input.  If all those bits are zero, then it left shifts the input 8 
bit positions, shifting '0's into the 8 lsbs.

The next layer uses the output of the first layer.  If the 4 leftmost 
bits are zero then it shifts the previous (lyr8) result 4 bits to the 
left, filling the rightmost bits with zero.  and so on.

Basically, the decision at each layer is based on whether there are any 
significant (i.e. non-zero) bits in the field that will get shifted off 
the left end if a shift is performed.  If so, then the data is passed 
through unshifted, if not then it is left shifted by the amount for that 
layer.

> 
>>lyr8 <= din(7 downto 0) & X"00" when din(15 downto 8)=X"00" else din;
>>sout(3) <= '1' when din(15 downto 8)=X"00" else '0';
>>lyr4 <= lyr8(11 downto 0) & X"0" when lyr8(15 downto 12)=X"0" else lyr8;
>>sout(2) <= '1' when lyr8(15 downto 12)=X"0" else '0';
>>lyr2 <= lyr4(13 downto 0) &"00" when lyr4(15 downto 14)="00" else lyr4;
>>sout(1) <= '1' when lyr4(15 downto 14)="00" else '0';
>>dout <= lyr2(14 downto 0) & '0' when lyr2(15)='0' else lyr2;
>>sout(0) <= '1' when lyr2(15)='0' else '0';
>>
>>This works if din is unsigned because you only have leading '0's.  If
>>din is 2's complement data, then you have leading sign bits instead of
>>leading '0', so the detection at each stage is made more difficult; in
>>that case it has to see if all the bits that will get shifted out match
>>the leftmost retained bit instead of just being zero so the detect
>>function has an additional term:  when din(15 downto 7)="000000000" or
>>din(15 downto 7)="111111111";  This precludes some shortcuts like using
>>the carry chain to perform the detect.  It is often easier to convert
>>from 2's complement notation to sign-magnitude notation, which is an
>>unsigned magnitude plus an independent sign bit.  The conversion is done
>>by performing the 2's complement if the 2's complement input is negative
>>to get an unsigned magnitude, and then retaining the sign bit.  (this
>>description is to answer a question posed by email).
> 
> 
> I understand what you mean as negative numbers have a "1" at the most
> significant bit which will give a 0 for the CLZ. I think i'll leave the
> 2's compliment for now ;D

2's complement numbers repeat the sign until you get to the first 
significant bit.  For example consider -5 represented as a 2's 
complement 8 bit number:
-5 => 11111011.
for sign magnitude, we represent it instead as +5 with a sign bit:
-5 => 10000101  where the leftmost bit is the sign, and the remaining 
bits are the unsigned absolute value of the number to be represented. 
In that case we leave the sign bit out of the shifter and then shift the 
unsigned portion left to eliminate leading '0's.


> 
> Thanks
> 

davidc@ad-holdings.co.uk wrote:

>Hi,
>
>I'm trying to create a Count Leading Zero (CLZ) in VHDL for a project
>but i'm having difficulty in finding any information what so ever apart
>from an explanation as to what it does, can anyone help?

What you need is a priority encoder:

function priority8to3(inval : std_logic_vector(7 downto 0)) return
std_logic_vector is
variable ret : integer;
variable a: std_logic_vector(2 downto 0);
begin
	a := "000";

	--priority encoder. By looping from 7 downto 0, the priority
	--can be reversed.		
	prio_loop: for i in 0 to 7 loop
		if inval(i)='1' then
			ret := i;
			exit prio_loop;
		end if;
	end loop;

return a + ret;
end;


-- 
Reply to nico@nctdevpuntnl (punt=.)
Bedrijven en winkels vindt U op www.adresboekje.nl