How to count zeros in registers?

And the answer is (the following is pseudo code in Verilog ) :

function [3:0] CountLeadingZeros ;
input [7:0] source ;
begin
// synopsys_full_case or something like that
casex ( source )
8'b1xxxxxx : CountLeadingZeros = 4'd0 ;
8'b01xxxxx : CountLeadingZeros = 4'd1 ;
8'b001xxxx : CountLeadingZeros = 4'd2 ;
... ( you can fill in the rest here )
8'b0000000 : CountLeadingZeros = 4'd8 ;
default : CountLeadingZeros = 4'dx ; // I always put in
defaults for simulation sake
endcasex
endfunction

This should do the trick. I have no clue what the other 21 people on
this thread are talking about, or why this wasn't the first answer. but
Here it is.

-Art
 
Frank Bemelman wrote:
"Spehro Pefhany" <speffSNIP@interlogDOTyou.knowwhat> schreef in bericht
news:b08po11ms5v7s0lne6ek248lpsj69vnv2s@4ax.com...
On Tue, 29 Nov 2005 18:31:41 +0100, the renowned "Frank Bemelman"
f.bemelmanq@xs4all.invalid.nl> wrote:

"Spehro Pefhany" <speffSNIP@interlogDOTyou.knowwhat> schreef in bericht
news:jnuoo11clvm7t4dntf4noh36q05bsks7ja@4ax.com...
On 29 Nov 2005 06:12:56 -0800, the renowned "Davy"
zhushenli@gmail.com> wrote:

Hi all,

reg[7:0] register;
The register contains data like
[0 0 0 1 0 1 0 1]
And I want to know the number of the zeros before the first 1
(in this example is 3 zeros).

How to do this in a combinational logic?

Best regards,
Davy

Pretty easy (a few minutes) if you can use a behavioral description.

A few minutes indeed.

It synthesized to 9 4-in LUTs on an FPGA, or 5 slices, with 6 levels
of logic.

Here's another nice puzzle I stumbled on
yesterday:

http://cgi.ebay.com/Magic-Switchboard_W0QQitemZ6581621863

Took me about 3 minutes to figure out half a solution. The problem
I have is the requirement:
"With this improved version, when the board is initially turned on
you are able to light the bulbs in any order.".

Spending another 30 minutes didn't bring me any luck ;)

Heh. Nonvolatile memory? ;-)

I don't know. If you mount the bulbs and caps in random
order, you could "program" the board by flipping the switches
in the same sequence as the lamps are mounted. So, if the
bulbs are mounted as B-Y-G-R, flip the switches in B-Y-G-R
sequence, thus telling the board which switch belongs to
which bulb. Not many would notice that turning on the
switches in that sequence, is actually a learning cycle for
the controller. Only needed once after power-on reset, and
then the game can continue.

But then there is the claim that you can turn on the lamps
in any order, no matter in what sequence they are mounted.

Perhaps there is enough difference in resistance between the
colored bulbs to indentify them reliably. The controller
could then measure the cold resistance to find out which
bulb is in which socket.

Sounds like a fun project, bit of shame I don't need a
fun project at this moment ;)
Click to expand...
You are thinking too much like an engineer and not enough as a
magician. It's magic, so trickery is normal. The way it's usually done
is that under each bulb there are four magnetic reed relays. Notice the
white cylinders? Each has a small magnet underneath. The trick is the
color is actually encoded by the position of the white cylinder, not
the bulb. You just need to remember to rotate the cylinder to the
correct position while screwing in the bulb.

A simple schematic for a single bulb (in ASCII of course, use
propotional font):


red
|
\
|
|
green__/ ____bulb____M____blue
|
|
\
|
yellow


M = Small magnet for closing the contact
of the reed relay. Rotate this magnet
to select which switch turns on this
bulb.
 
On Tue, 29 Nov 2005 15:44:19 -0800, Art Stamness wrote:

And the answer is (the following is pseudo code in Verilog ) :

function [3:0] CountLeadingZeros ;
input [7:0] source ;
begin
// synopsys_full_case or something like that
casex ( source )
8'b1xxxxxx : CountLeadingZeros = 4'd0 ;
8'b01xxxxx : CountLeadingZeros = 4'd1 ;
8'b001xxxx : CountLeadingZeros = 4'd2 ;
... ( you can fill in the rest here )
8'b0000000 : CountLeadingZeros = 4'd8 ;
default : CountLeadingZeros = 4'dx ; // I always put in
defaults for simulation sake
endcasex
endfunction

This should do the trick. I have no clue what the other 21 people on
this thread are talking about, or why this wasn't the first answer. but
Here it is.

-Art
Click to expand...
I think your answer is about the best, given that the OP seems to want
verilog (although he didn't explicitly SAY that). But the original post
also is visible here in sci.electronics.design (as well as a few other
groups), where many of the other answers are more-or-less on-topic.

Probably the OP should have posted to comp.lang.verilog only.

I can't imagine that it is ever a good idea to post to comp.lang.verilog
and comp.lang.vhdl. ;-)

--Mac
 
"slebetman@yahoo.com" <slebetman@gmail.com> schreef in bericht
news:1133307891.046401.110620@z14g2000cwz.googlegroups.com...
Frank Bemelman wrote:

But then there is the claim that you can turn on the lamps
in any order, no matter in what sequence they are mounted.

Perhaps there is enough difference in resistance between the
colored bulbs to indentify them reliably. The controller
could then measure the cold resistance to find out which
bulb is in which socket.

Sounds like a fun project, bit of shame I don't need a
fun project at this moment ;)


You are thinking too much like an engineer and not enough as a
magician. It's magic, so trickery is normal. The way it's usually done
is that under each bulb there are four magnetic reed relays. Notice the
white cylinders? Each has a small magnet underneath. The trick is the
color is actually encoded by the position of the white cylinder, not
the bulb. You just need to remember to rotate the cylinder to the
correct position while screwing in the bulb.

A simple schematic for a single bulb (in ASCII of course, use
propotional font):


red
|
\
|
|
green__/ ____bulb____M____blue
|
|
\
|
yellow


M = Small magnet for closing the contact
of the reed relay. Rotate this magnet
to select which switch turns on this
bulb.
Click to expand...
Hmm, yes, looks a bit complicated to me. It would require
a lot of fiddling with the cylinders, with the added risk
that people will notice that.

A mini version can be seen here:
http://www.wellingtonent.com/document/switchb.html

Here we see no cylinders, only sockets screwed on a wood
base. The caps on the tumbler switches don't allow for
much trickery either. Although there are some large black
mountings around it, which perhaps can be rotated. That
could be part of another deception, make people believe
these can be rotated. And when they try that, it turns out
to make no difference at all. Something like that ;)

--
Thanks, Frank.
(remove 'q' and '.invalid' when replying by email)
 
soxmax wrote:
Davy wrote:
And I want to know the number of the zeros before the first 1
Click to expand...

Also - never begin a sentence with a
preposition.
Click to expand...
I'm not native speaker, but I don't agree :
http://grammar.uoregon.edu/prepositions/prepositions.html

Anyway, I wouldn't start a sentence with "and"...

-Derek
Click to expand...
 
"Stephane" <stephane@nospam.fr> wrote in message
news:dmjq9c$l98$1@ellebore.extra.cea.fr...
soxmax wrote:
Davy wrote:
And I want to know the number of the zeros before the first 1
Click to expand...
The book "Hacker's Delight" from Henry S. Warren, ISBN 0201914654, available
at Amazon lists several algorithms to do this. Some use loops and others
only logical test. Very interesting reading.

Meindert
 
Art Stamness wrote:
And the answer is (the following is pseudo code in Verilog ) :

function [3:0] CountLeadingZeros ;
input [7:0] source ;
begin
// synopsys_full_case or something like that
casex ( source )
8'b1xxxxxx : CountLeadingZeros = 4'd0 ;
8'b01xxxxx : CountLeadingZeros = 4'd1 ;
8'b001xxxx : CountLeadingZeros = 4'd2 ;
... ( you can fill in the rest here )
8'b0000000 : CountLeadingZeros = 4'd8 ;
default : CountLeadingZeros = 4'dx ; // I always put in
defaults for simulation sake
endcasex
endfunction

This should do the trick. I have no clue what the other 21 people on
this thread are talking about, or why this wasn't the first answer. but
Here it is.
Click to expand...
I agree about the others, but this wouldn't be my first answer.
To me the obvious solution is a for-loop over the word
that returns the loop counter as soon a '1' is found.

The reason why this "obvious" solution apparently isn't that
obvious to many people may be that this is one more occasion
in which Verilog doesn't really help. Many languages have
a 'return' or 'break' statement to break out of a loop early
and cleanly. But in Verilog, one has to use that awkward
'disable' statement to emulate this behavior.

Jan

--
Jan Decaluwe - Resources bvba - http://www.jandecaluwe.com
Losbergenlaan 16, B-3010 Leuven, Belgium
From Python to silicon:
http://myhdl.jandecaluwe.com
 
Jan Decaluwe skrev:

Art Stamness wrote:
And the answer is (the following is pseudo code in Verilog ) :

function [3:0] CountLeadingZeros ;
input [7:0] source ;
begin
// synopsys_full_case or something like that
casex ( source )
8'b1xxxxxx : CountLeadingZeros = 4'd0 ;
8'b01xxxxx : CountLeadingZeros = 4'd1 ;
8'b001xxxx : CountLeadingZeros = 4'd2 ;
... ( you can fill in the rest here )
8'b0000000 : CountLeadingZeros = 4'd8 ;
default : CountLeadingZeros = 4'dx ; // I always put in
defaults for simulation sake
endcasex
endfunction

This should do the trick. I have no clue what the other 21 people on
this thread are talking about, or why this wasn't the first answer. but
Here it is.

I agree about the others, but this wouldn't be my first answer.
To me the obvious solution is a for-loop over the word
that returns the loop counter as soon a '1' is found.
Click to expand...
yep loop is better, I've always been told that casex is evil :)

The reason why this "obvious" solution apparently isn't that
obvious to many people may be that this is one more occasion
in which Verilog doesn't really help. Many languages have
a 'return' or 'break' statement to break out of a loop early
and cleanly. But in Verilog, one has to use that awkward
'disable' statement to emulate this behavior.

Jan
Click to expand...
you could just run the loop backwards i.e. starting from the lsb

-Lasse
 
Jim Thompson wrote:
On 29 Nov 2005 06:12:56 -0800, "Davy" <zhushenli@gmail.com> wrote:

Hi all,

reg[7:0] register;
The register contains data like
[0 0 0 1 0 1 0 1]
And I want to know the number of the zeros before the first 1
(in this example is 3 zeros).

How to do this in a combinational logic?

Best regards,
Davy

See...

http://www.analog-innovations.com/SED/HowManyOnes.pdf

You'll need to modify it for "zeroes" and to stop at the first
occurrence of a "one"
Click to expand...
Holy Mole, that seems like a contest winner how to do the job
with the most gates possible (altho a modern compiler will
optimize it down some)

Just draw the K-map and loop the functions.

The problem tells us there are 8 bits, people

One thing, the problem doesn't specify: what is wanted when
the register contains 0 0 0 0 0 0 0 0

Wood
 
On 30 Nov 2005 15:58:57 -0800, "Woody Brison" <woody_brison@yahoo.com>
wrote:

Jim Thompson wrote:
On 29 Nov 2005 06:12:56 -0800, "Davy" <zhushenli@gmail.com> wrote:

Hi all,

reg[7:0] register;
The register contains data like
[0 0 0 1 0 1 0 1]
And I want to know the number of the zeros before the first 1
(in this example is 3 zeros).

How to do this in a combinational logic?

Best regards,
Davy

See...

http://www.analog-innovations.com/SED/HowManyOnes.pdf

You'll need to modify it for "zeroes" and to stop at the first
occurrence of a "one"

Holy Mole, that seems like a contest winner how to do the job
with the most gates possible (altho a modern compiler will
optimize it down some)
Click to expand...
Just half-adders.

Just draw the K-map and loop the functions.
Click to expand...
If you have that luxury.

The problem tells us there are 8 bits, people

One thing, the problem doesn't specify: what is wanted when
the register contains 0 0 0 0 0 0 0 0

Wood
Click to expand...

...Jim Thompson
--
| James E.Thompson, P.E. | mens |
| Analog Innovations, Inc. | et |
| Analog/Mixed-Signal ASIC's and Discrete Systems | manus |
| Phoenix, Arizona Voice:(480)460-2350 | |
| E-mail Address at Website Fax:(480)460-2142 | Brass Rat |
| http://www.analog-innovations.com | 1962 |

I love to cook with wine. Sometimes I even put it in the food.
 
On 30 Nov 2005 15:58:57 -0800, "Woody Brison" <woody_brison@yahoo.com>
wrote:

Jim Thompson wrote:
On 29 Nov 2005 06:12:56 -0800, "Davy" <zhushenli@gmail.com> wrote:

Hi all,

reg[7:0] register;
The register contains data like
[0 0 0 1 0 1 0 1]
And I want to know the number of the zeros before the first 1
(in this example is 3 zeros).

How to do this in a combinational logic?

Best regards,
Davy

See...

http://www.analog-innovations.com/SED/HowManyOnes.pdf

You'll need to modify it for "zeroes" and to stop at the first
occurrence of a "one"

Holy Mole, that seems like a contest winner how to do the job
with the most gates possible (altho a modern compiler will
optimize it down some)

[snip]
Click to expand...

The OP (for HowManyOnes) wanted to count ALL 1's, not just leading.

...Jim Thompson
--
| James E.Thompson, P.E. | mens |
| Analog Innovations, Inc. | et |
| Analog/Mixed-Signal ASIC's and Discrete Systems | manus |
| Phoenix, Arizona Voice:(480)460-2350 | |
| E-mail Address at Website Fax:(480)460-2142 | Brass Rat |
| http://www.analog-innovations.com | 1962 |

I love to cook with wine. Sometimes I even put it in the food.
 
On Wed, 30 Nov 2005 17:35:47 -0700, Jim Thompson wrote:

On 30 Nov 2005 15:58:57 -0800, "Woody Brison" <woody_brison@yahoo.com
wrote:

Jim Thompson wrote:
On 29 Nov 2005 06:12:56 -0800, "Davy" <zhushenli@gmail.com> wrote:

Hi all,

reg[7:0] register;
The register contains data like
[0 0 0 1 0 1 0 1]
And I want to know the number of the zeros before the first 1
(in this example is 3 zeros).

How to do this in a combinational logic?

Best regards,
Davy

See...

http://www.analog-innovations.com/SED/HowManyOnes.pdf

You'll need to modify it for "zeroes" and to stop at the first
occurrence of a "one"

Holy Mole, that seems like a contest winner how to do the job
with the most gates possible (altho a modern compiler will
optimize it down some)

[snip]

The OP (for HowManyOnes) wanted to count ALL 1's, not just leading.
Click to expand...
I thought "before the first 1" meant "leading". ;-)

Here's the part:
http://pdf.alldatasheet.co.kr/datasheet-pdf/view/53747/FAIRCHILD/74HC148.html

Might have to invert the bits - this chip actually counts '1's.
Or you could do it in Xilinx schematic mode. ;-)

Cheers!
Rich
 
["Followup-To:" header set to sci.electronics.basics.]
On 2005-11-29, Davy <zhushenli@gmail.com> wrote:
Hi all,

reg[7:0] register;
The register contains data like
[0 0 0 1 0 1 0 1]
And I want to know the number of the zeros before the first 1
(in this example is 3 zeros).

How to do this in a combinational logic?
Click to expand...
what output do you want?




--

Bye.
Jasen
 
Jim Thompson wrote:
On 30 Nov 2005 15:58:57 -0800, "Woody Brison" <woody_brison@yahoo.com
wrote:

Just draw the K-map and loop the functions.

If you have that luxury.
Click to expand...
Yes... and I think the original poster has that luxury, I concur
that this looks a lot like homework. So what he's needing to
do is draw a K-map. I just wanted to steer him in the right
direction without doing it for him

By the way, code to draw K-maps is not too hard to write.
Collecting minterms isn't too far beyond that.
Reducing 'em isn't too far beyond that.
Having tools like that cuts the time down, bringing such luxuries
into reach of even the humble compiler user

Wood
 
On 1 Dec 2005 13:48:52 -0800, "Woody Brison" <woody_brison@yahoo.com>
wrote:

Jim Thompson wrote:
On 30 Nov 2005 15:58:57 -0800, "Woody Brison" <woody_brison@yahoo.com
wrote:

Just draw the K-map and loop the functions.

If you have that luxury.

Yes... and I think the original poster has that luxury, I concur
that this looks a lot like homework. So what he's needing to
do is draw a K-map. I just wanted to steer him in the right
direction without doing it for him

By the way, code to draw K-maps is not too hard to write.
Collecting minterms isn't too far beyond that.
Reducing 'em isn't too far beyond that.
Having tools like that cuts the time down, bringing such luxuries
into reach of even the humble compiler user

Wood
Click to expand...
I can still do 'em by hand but, now-a-days, I use KarnaughMap v4.4.5,
by Russell Sasamori... http://www.puz.com/sw/karnaugh/index.htm

...Jim Thompson
--
| James E.Thompson, P.E. | mens |
| Analog Innovations, Inc. | et |
| Analog/Mixed-Signal ASIC's and Discrete Systems | manus |
| Phoenix, Arizona Voice:(480)460-2350 | |
| E-mail Address at Website Fax:(480)460-2142 | Brass Rat |
| http://www.analog-innovations.com | 1962 |

I love to cook with wine. Sometimes I even put it in the food.
 
clz[2] = "1" when (D[3 downto 0] = "0000") else "0";
if(clz[2] == "1") then
D1 <= D[7 downto 4];
else
D1 <= D[3 downto 0];
end if;
clz[1] = "1" when (D1[1 downto 0] = "00" else "0";
if(clz[1] == "1") then
D2 <= D1[3 downto 2];
else
D2 <= D1[1 downto 0];
end if;
clz[0] <= "1" when (D2[0] == "0") else "0";

will return the position of the first set bit or 0b111 if no bit is set.
Idea stolen from a girl...

--
Best Regards,
Ulf Samuelsson
This is intended to be my personal opinion which may,
or may bot be shared by my employer Atmel Nordic AB
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top