Dynamic scaling question

P

Paul Solomon

Guest
Hi guys,

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.
I have tried to do this with the following case statement but it does not
work.

I need this to work for positive and negative numbers, so the number of
leading 0's or the number of leading 1's

Can anyone give me pointers on how I can make this work??

Regards,


Paul Solomon

parameter WIDTH = 14;

input signed [WIDTH-1:0] x;
reg [3:0] scale_x;

// Prescaler
always @(posedge clk, posedge reset) begin
case (x)
{14'b00000000000001,{(WIDTH-14){1'bx}}} : scale_x <= 12;
{14'b11111111111111,{(WIDTH-14){1'bx}}} : scale_x <= 12;
{13'b0000000000001,{(WIDTH-13){1'bx}}} : scale_x <= 11;
{13'b1111111111111,{(WIDTH-13){1'bx}}} : scale_x <= 11;
{12'b000000000001,{(WIDTH-12){1'bx}}} : scale_x <= 10;
{12'b111111111111,{(WIDTH-12){1'bx}}} : scale_x <= 10;
{11'b00000000001,{(WIDTH-11){1'bx}}} : scale_x <= 9;
{11'b11111111111,{(WIDTH-11){1'bx}}} : scale_x <= 9;
{10'b0000000001,{(WIDTH-10){1'bx}}} : scale_x <= 8;
{10'b1111111111,{(WIDTH-10){1'bx}}} : scale_x <= 8;
{9'b000000001,{(WIDTH-9){1'bx}}} : scale_x <= 7;
{9'b111111111,{(WIDTH-9){1'bx}}} : scale_x <= 7;
{8'b00000001,{(WIDTH-8){1'bx}}} : scale_x <= 6;
{8'b11111111,{(WIDTH-8){1'bx}}} : scale_x <= 6;
{7'b0000001,{(WIDTH-7){1'bx}}} : scale_x <= 5;
{7'b1111111,{(WIDTH-7){1'bx}}} : scale_x <= 5;
{6'b000001,{(WIDTH-6){1'bx}}} : scale_x <= 4;
{6'b111111,{(WIDTH-6){1'bx}}} : scale_x <= 4;
{5'b00001,{(WIDTH-5){1'bx}}} : scale_x <= 3;
{5'b11111,{(WIDTH-5){1'bx}}} : scale_x <= 3;
{4'b0001,{(WIDTH-4){1'bx}}} : scale_x <= 2;
{4'b1111,{(WIDTH-4){1'bx}}} : scale_x <= 2;
{3'b001,{(WIDTH-3){1'bx}}} : scale_x <= 1;
{3'b111,{(WIDTH-3){1'bx}}} : scale_x <= 1;
default : scale_x <= 0;
endcase
end
 
On Thu, 28 Jul 2005 14:07:38 +1000, "Paul Solomon"
<psolomon@tpg.com.au> wrote:

Hi guys,

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.
Click to expand...
How about:
function nlz; // fill in the header ...

i = MSB;
if (x[MSB])
while (x) i = i -1;
else
while (!x) i = i - 1;
nlz = MSB - i;

Of course you have to stop at i==0 too and I am not sure how well this
might synthesize.
Another option is to use a casex statement:

casex(x)
000001???: nlz = 5;
00001????: nlz = 4;

etc.
You can do similarly for negative numbers 11110???, etc. or invert if
negative and use the positive number logic.

Hope this helps.

PS I sure hope there are some gals reading this newsgroup.
 
On Thu, 28 Jul 2005 14:07:38 +1000, "Paul Solomon"
<psolomon@tpg.com.au> 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.
Click to expand...
"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@doulos.com
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.
 
On Thu, 28 Jul 2005 09:18:47 +0100, Jonathan Bromley
<jonathan.bromley@doulos.com> wrote:

We build a device with three stages (because 8 == 2**3).
Click to expand...
[...]

Guess who didn't read quite carefully enough...
sorry, the original post was obviously talking about
a SIGNED-value normaliser. The technique I described
can easily be extended to handle signed values, but it's
just a little trickier - the "do we need to shift" condition
at each stage is no longer simply (upper_bits == all_0), but
((upper_bits == all_0) || (upper_bits == all_1)). And the
final special-case test is a little different too.

But the basic idea is OK.
--
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@doulos.com
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.
 
"Jonathan Bromley" <jonathan.bromley@doulos.com> wrote in message
news:016he1pa3jrbrgb8i6e2ahen4ej6vhrsee@4ax.com...
On Thu, 28 Jul 2005 09:18:47 +0100, Jonathan Bromley
jonathan.bromley@doulos.com> wrote:

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

[...]

Guess who didn't read quite carefully enough...
sorry, the original post was obviously talking about
a SIGNED-value normaliser. The technique I described
can easily be extended to handle signed values, but it's
just a little trickier - the "do we need to shift" condition
at each stage is no longer simply (upper_bits == all_0), but
((upper_bits == all_0) || (upper_bits == all_1)). And the
final special-case test is a little different too.

But the basic idea is OK.
--
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@doulos.com
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.
Click to expand...
Hi All,

Thanks for these replies.. they have helped me greatly and I have now
implemented this function.
 
The original piece of code doesn't work because you are trying to use x
as a don't care in the case items. To treat x as a don't care requires
the use of a casex statement rather than a case statement. Note that
casex is dangerous because it will also treat x bits in the selector
(which may be actual unknowns produced by your design) as don't cares,
causing false matches. For this reason, it is often recommended that
you use casez instead, since z is less likely to arise by mistake.
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top