How to count zeros in registers?

[Joel Kolstad]

The question is clear enough but I miss the background. I cannot believe
this to be a serious design problem. Anyone who has some basic knowledge of
digital design should be able to answer immediately. A practical solution
depends on the background I'm missing. You can use a bunch of logic gates,
an EPROM or a PLD to name a few.

He's probably looking for a 'clever,' in this case meaning 'low gate count' or
'fast' solution. There are plenty of digital design problems out there that
are entirely straightforward to just 'code up' a solution to in, e.g., VHDL or
TTL logic, but can be an order of magnitude slower or larger than more clever
solutions.

Counting the number of consecutive zero bits is one of these problems.

This sort of problem comes up somewhat more frequently in software, where
people stuck with, e.g., 1MHz CPUs really do need every last CPU cycle they
can spare... solutions are found all over, e.g.,
http://graphics.stanford.edu/~seander/bithacks.html .

 

[Rich Grise]

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?

Google '"priority encoder" logic' - include the double-quote (")
and don't include the single-quote (').

There used to be a chip, the 74148, that would give you the answer
in one cycle.

Good Luck!
Rich

 

[Art Stamness]

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

 

[slebetman]

"Spehro Pefhany" <[email protected]> schreef in bericht
On 29 Nov 2005 06:12:56 -0800, the renowned "Davy"

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

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.

 

[Mac]

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

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

 

[Frank Bemelman]

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.

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

 

[Stephane]

Also - never begin a sentence with a
preposition.

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"...

 

[Meindert Sprang]

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

 

[Jan Decaluwe]

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.

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

 

[Arie de Muynck]

I found on the web some discussions, with this as the best observation:

I'm very sure that there is some sort of electronic circuit in there

somewhere (yet another "thick base"). If you notice, the trick is
performed, so that every time the switches are thrown, the lights light up
in the order they are in the sockets, from right to left. (This is using
the Carson performance as reference).
So, I'd assume that it's some sort of circuit so that no matter what
switch is thrown, the first goes on, then the second switch thrown turns
on the second one, as so forth.


Which sounds like some very simple sequential logic.

Also, suggestions were made that tracking the order in which lamps were
removed, then replaced, allows the unit to "memorize" the positions. But
that in itself would not explain the final part of the trick with the
exchanging of the switch caps, in that part the operation (sequencing) of
the switches must be special.

 

[langwadt]

Jan Decaluwe skrev:

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.

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

you could just run the loop backwards i.e. starting from the lsb

-Lasse

 

[Woody Brison]

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)

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

 

[Jim Thompson]

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)

Just half-adders.

Just draw the K-map and loop the functions.

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

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

I love to cook with wine. Sometimes I even put it in the food.

 

[Jim Thompson]

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.

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

I love to cook with wine. Sometimes I even put it in the food.

 

[Rich Grise]

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.

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

 

[Jasen Betts]

["Followup-To:" header set to sci.electronics.basics.]

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?

what output do you want?

 

[Weng Tianxiang]

Hi,
This is a search list about how to count leading zero for ASIC.

Using the patent number, you can download full content of a patent from
US Patent Office website:
http://patft.uspto.gov/netahtml/search-bool.html.

Those listed must be the most advanced algorithm. Others may be at
amateur level.

Weng


Results of Search in 1976 to present db for:
TTL/"leading zero": 13 patents.
Hits 1 through 13 out of 13
PAT. NO. Title
1 6,779,008 Method and apparatus for binary leading zero counting with
constant-biased result
2 6,654,776 Method and apparatus for computing parallel leading zero
count with offset
3 6,594,679 Leading-zero anticipator having an independent sign bit
determination module
4 6,477,552 Device and method for performing a leading zero
determination on an operand
5 6,205,461 Floating point arithmetic logic unit leading zero count
using fast approximate rounding
6 5,993,051 Combined leading one and leading zero anticipator
7 5,974,432 On-the-fly one-hot encoding of leading zero count
8 5,875,123 Carry-select adder with pre-counting of leading zero
digits
9 5,844,826 Leading zero count circuit
10 5,241,490 Fully decoded multistage leading zero detector and
normalization apparatus
11 5,204,825 Method and apparatus for exact leading zero prediction
for a floating-point adder
12 5,111,415 Asynchronous leading zero counter employing iterative
cellular array
13 4,247,891 Leading zero count formation

 

[Woody Brison]

On 30 Nov 2005 15:58:57 -0800, "Woody Brison" <[email protected]>
wrote:

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

 

[Jim Thompson]

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

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 Voice480)460-2350 | |
| E-mail Address at Website Fax480)460-2142 | Brass Rat |
| http://www.analog-innovations.com | 1962 |

I love to cook with wine. Sometimes I even put it in the food.

 

[Ulf Samuelsson]

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...