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

Reply to
davidc
Loading thread data ...

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

Reply to
Jon Beniston

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.

Reply to
Sylvain Munaut

Perhaps you might find this useful:

formatting link

Cheers,

Andy

Reply to
Andy Ray

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.

Reply to
Ray Andraka

If it

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.

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

formatting link

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

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

Reply to
davidc

it

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

Reply to
Ray Andraka

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?

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

Reply to
davidc

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.

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.

Reply to
Ray Andraka

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
Reply to
Nico Coesel

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.