Leading Zero Detection by Sub-Division
To find the number of leading zeros in N-Bit word, following sub-division method can be used.
Divide the N bit vector (N should be power of 2) into two equal groups each with N/2 size. Now call them as LHalf and RHalf.
The signal AllZerosInLHalf indicates all are zeros in left half.
The addition in the above equation is not require an adder. It's just concatenating AllZerosInLHalf to the result at (N-1). The leading-zero detection hardware is in a tree structure with a building block. The figure shows the building block, which can be used in leading zero detection hierarchy.
Now we can build a primitive (Ex: 4 bit) leading-zero detection hardware and put multiple of them in the first stage depending on the size of the input word. And we can put the building block shown in the figure to find out the leading zeros. An example structure for finding leading zeros in a 16 bit word is shown in below figure.
The signal AllZerosInRHalf indicates all are zeros in right half.
The signal LeadZerosInLHalf indicates leading zeros in left half.
The signal LeadZerosInRHalf indicates leading zeros in right half.
Leading Zeros In N Bit Vector = 2pow(N-1)* AllZerosInLHalf + {
AllZerosInLHalf ?
LeadZerosInRHalf :
LeadZerosInLHalf
}
The addition in the above equation is not require an adder. It's just concatenating AllZerosInLHalf to the result at (N-1). The leading-zero detection hardware is in a tree structure with a building block. The figure shows the building block, which can be used in leading zero detection hierarchy.
Now we can build a primitive (Ex: 4 bit) leading-zero detection hardware and put multiple of them in the first stage depending on the size of the input word. And we can put the building block shown in the figure to find out the leading zeros. An example structure for finding leading zeros in a 16 bit word is shown in below figure.
Comments
Post a Comment