Re: Dynamic scaling question

On Thu, 28 Jul 2005 14:07:38 +1000, "Paul Solomon"
<psolomon@xxxxxxxxxx> wrote:

>I am trying to work out a piece of code that will allow me to obtain the
>number of leading zero's in a number.

"mk" has given you good answers on how to make your exhaustive
approach work in Verilog, but in fact there's a much better way.
For the sake of example, let's do it on an 8-bit word 8'b00100110.

We build a device with three stages (because 8 == 2**3).

The first stage examines the top 4 bits. If they are all zero, it
shifts the word 4 bits to the left and sets the MSB of a 3-bit
result word. If they are not all zero, as in our example,
it does no shift, and clears the MSB of the result word.
So, in our example, the outputs of this stage are the original
8-bit word without shift, and a single zero:
8'b00100110 3'b0xx
The resulting, possibly shifted, word is then passed to the second
stage. It examines the top 2 bits. They are indeed zero, so it
shifts the word 2 places to the left and sets the next bit of result:
8'b10011000 3'b01x
The final stage examines only the top bit. If zero, it shifts one
place to the left; if not, there's no shift. In our example, the
top bit is 1 so there's no shift and the LSB of result is cleared.
8'b10011000 3'b010

In only 3 steps we get the leading-zero count, and also a
normalised version of the input word. In many applications,
if you need to count the leading zeros of a word, then it's
quite likely you need a normalised version of it as well -
for example, floating-point arithmetic. So the "normalised
value" output is a useful bonus.

There's one exceptional case: if the input word was exactly
zero, then we will get a shift count of 7 which is of course
wrong - the leading-zero count is 8, not 7. However, it's
very easy to handle that special case. If the MSB of the
normalised (shifted) result is zero, then we know we have
encountered the special case and we correct for it by jamming
the leading-zero count result to 8 instead of 7. This is
cheaper, and probably faster, than trying to detect the
all-zero case with a very wide NOR gate.

Each stage synthesises to a zero-detector (NOR gate) and an array
of 2-input multiplexers. This is very cheap and fast. Only N
stages are required to zero-count and normalise a 2**N bit word.
If you are truly desperate for speed, the design could easily
be pipelined. Parameterising the design for arbitrary bit
widths is a little tricky in Verilog, but it's possible if
you use Verilog-2001 constructs. Writing the design for a
known bit width is easy, albeit a little clumsy:

module normalise_and_clz(a, y, clz);

input [7:0] a; // input vector
output [7:0] y; // normalised version
output [3:0] clz; // leading zero count in range 0..8

reg [3:0] clz;
reg [7:0] y;

// intermediate stages
reg [7:0] a1, a2;
// provisional leading-zero count
reg [2:0] zc;

// first stage
always @(a)
if (a[7:4] == 4'b0) begin
zc[2] = 1'b1;
a1 = {a[3:0], 4'b0};
end else begin
zc[2] = 1'b0;
a1 = a;
end

// second stage
always @(a1)
if (a1[7:6] == 2'b0) begin
zc[1] = 1'b1;
a2 = {a1[5:0], 2'b0};
end else begin
zc[1] = 1'b0;
a2 = a1;
end

// third stage
always @(a2)
if (a2[7] == 1'b0) begin
zc[0] = 1'b1;
y = {a2[6:0], 1'b0};
end else begin
zc[0] = 1'b0;
y = a2;
end

// final correction for all-zeros special case
always @(y or zc)
if (y[7] == 1'b0)
clz = {4'b1000}; // special case, all zero
else
clz = {1'b0, zc};

endmodule

Other solutions, based on for-loops or generate-for, are possible
and may be more elegant than the above brute-force version;
they will also make it possible to parameterise the design for
different bit widths. Experienced Verilog coders will also
see many opportunities for making the code more concise, but
my objective here is clarity rather than brevity.

HTH
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL, Verilog, SystemC, Perl, Tcl/Tk, Verification, Project Services

Doulos Ltd. Church Hatch, 22 Market Place, Ringwood, BH24 1AW, UK
Tel: +44 (0)1425 471223 mail:jonathan.bromley@xxxxxxxxxx
Fax: +44 (0)1425 471573 Web: http://www.doulos.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.
.

Relevant Pages

  • Re: Erich Hartmanns F-86 Sabre
    ... that shot has a rather lower Pk and smaller "no-escape zone" ... than a shot from the hot noisy fast guy: ... This is back to the Zero vs. F6F fight: the Zero can turn tighter at low ... Going forward, the B-1A, a hot design, was cancelled, but improved ...
    (rec.aviation.military)
  • Re: Optimal amplifier output impedance for headphones
    ... Zero is always best for driving anything that's properly designed to ... is a good design starting-point for both frequency response and ... meaning a resistor driven by a low impedance output. ... Probably a single ended triode amp would work fine for headphone ...
    (rec.audio.tubes)
  • Re: Parametric models of two and three mirror reflecting telescopes
    ... >distance and primary mirror focal length. ... designed from these with ray tracing using your favorite design ... requirement that the third order Petzval Sum be zero. ...
    (sci.optics)
  • Re: Shifting unsigned long long values by 64 bits
    ... be zero, and compiles with a constant zero as the parameter. ... Note, too, the compiler warning for this line. ... shift at the machine-code level, and places "64" in a register, ... I ran into recently on code which worked just fine on a platform ...
    (comp.lang.c)
  • Re: P&S Revenue predicted to fall by 24%, D-SLR revenue predicted to fall by 12%
    ... that it increases from zero in the middle to a maximum at the edges? ... It is lens designer's job to minimize ... If before the shift it is zero across the field, ... You stupid fuckin' troll. ...
    (rec.photo.digital)
Loading