How to count zeros in registers?

D

Davy

Guest
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
 
Davy 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...
With a priority tree:

if (reg[7:0] == 8'b00000000)
clz = 3'h8;
else if (reg[7:1] == 7'b0000000)
clz = 3'h7;
else if ...

You can play some tricks to make it faster - particularly useful if your
register is bigger than 8 bits. It will always be quite large.

John

--
John Penton, posting as an individual unless specifically indicated
otherwise.
 
Davy 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
Click to expand...
Hey why don't tell us a little about the application, because this
sounds like something totally divorced from reality. Is the real
application about cheating on a homework assignment? I could understand
if applied an iota of effort, but there's no evidence of that. Aren't
you the lazy punk-assed juvenile sh_t with the loud mouth about plonking
people and shooting your f____ing mouth off about how clever you are?
Well how damned clever are you when it comes to doing something
constructive, punk-ass?
 
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
Click to expand...
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"

...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.
 
Fred Bloggs wrote:
Davy 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


Hey why don't tell us a little about the application, because this
sounds like something totally divorced from reality.
Click to expand...
Some processors have Count Leading Zeros/Ones instructions to quickly
determine how many bits to left shift data. I had to write HDL code
for a custom ASIC processor with a clz instruction. Neat little
combinational logic problem...

Pete
 
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...
I don't think this is what the OP wanted. Perhaps he could comment.

John

--
John Penton, posting as an individual unless specifically indicated
otherwise.
 
Fred Bloggs wrote:
Davy 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


Hey why don't tell us a little about the application, because this
sounds like something totally divorced from reality.
Click to expand...
<snipped Fred being conversational>

The only time I had to do this, I had it easier, because I'd been asked
to produced a floating point output on a multiplexed multi-character
display, which was being driven from a shift register, back in the days
before PICs.

I don't think the system ever worked (and in fact I just found the
hardware out in the attic) but it should have worked, A colleague was
building his own photon counter, and wanted to display a wide range of
photon counts without paying for a large number of seven-segment
displays. He dumped the half-finished system on me when he went off to
concentrate on being an acadmeic chemist.

-----------
Bill Sloman, Nijmegen
 
"Davy" <zhushenli@gmail.com> wrote in message
news:1133273576.137921.272350@f14g2000cwb.googlegroups.com...
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...
Use the register bits as address inputs to a ROM in which the data is coded
for the results.

Register --> ROM --> Output

Examples:

ADDR DATA
00 8
01 7
02 6
03 6
04 5
05 5
06 5
07 5
08 4
....
0f 4
10 3
....
1f 3
20 2

etc.

Or you can write a mathematical expression involving logs to the base 2.
 
Davy 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
Click to expand...
In order to get combinational logic, your best bet is to use a Karnaugh
Map for each individual case. Also - never begin a sentence with a
preposition.

-Derek
 
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
Click to expand...
Pretty easy (a few minutes) if you can use a behavioral description.

What have you done to try and solve this (homework?) problem yourself?


Best regards,
Spehro Pefhany
--
"it's the network..." "The Journey is the reward"
speff@interlog.com Info for manufacturers: http://www.trexon.com
Embedded software/hardware/analog Info for designers: http://www.speff.com
 
On Tue, 29 Nov 2005 15:02:42 GMT, Fred Bloggs <nospam@nospam.com>
wrote:

Davy 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


Hey why don't tell us a little about the application, because this
sounds like something totally divorced from reality.
Click to expand...
It's pretty fundamental, actually; there's at least one TTL priority
encoder (the '278). A couple of obvious applications are normalisation
and interrupt prioritisation.

Rick
 
"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.
Click to expand...
A few minutes indeed. 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 ;)

--
Thanks, Frank.
(remove 'q' and '.invalid' when replying by email)
 
On 29 Nov 2005 08:31:46 -0800, the renowned Petrov_101@hotmail.com
wrote:

Fred Bloggs wrote:
Davy 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


Hey why don't tell us a little about the application, because this
sounds like something totally divorced from reality.

Some processors have Count Leading Zeros/Ones instructions to quickly
determine how many bits to left shift data. I had to write HDL code
for a custom ASIC processor with a clz instruction. Neat little
combinational logic problem...

Pete
Click to expand...
Sure, suppose you want to normalize a floating-point mantissa using a
barrel shifter.



Best regards,
Spehro Pefhany
--
"it's the network..." "The Journey is the reward"
speff@interlog.com Info for manufacturers: http://www.trexon.com
Embedded software/hardware/analog Info for designers: http://www.speff.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.
Click to expand...
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 ;)
Click to expand...
Heh. Nonvolatile memory? ;-)


Best regards,
Spehro Pefhany
--
"it's the network..." "The Journey is the reward"
speff@interlog.com Info for manufacturers: http://www.trexon.com
Embedded software/hardware/analog Info for designers: http://www.speff.com
 
"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? ;-)
Click to expand...
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 ;)

--
Thanks, Frank.
(remove 'q' and '.invalid' when replying by email)
 
On Tue, 29 Nov 2005 20:02:21 +0100, the renowned "Frank Bemelman"
<f.bemelmanq@xs4all.invalid.nl> 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.
Click to expand...
It depends on the meaning of "initially"-- remember it's to their
advantage to obfuscate a bit. Note the distinctions in the description
between what *you* must do and what the "spectators" can be allowed to
do (they can flip the switches, but presumably not decide *which*
switches to initially flip).

If it's previously been programmed, then you can turn it on
"initially" and it will remember the previous programming (and the
lights can be turned on in any order-- but not re-ordered with the
power off). Their early model might not have done that.

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.
Click to expand...
I don't think there's anything fancy-schmancy like that going on. Just
switches and probably detection of bulbs removed. You're thinking way
too hard about the electronics and not hard enough about the
obfuscation. It's a kind of magic trick.

Reminds me of the flashing devil horns that I bought for a couple of
dollars on the street one Halloween:

http://server2.hostingplex.com/~zstoretr/horns.JPG

Ran off of AA cells in the black cylinders on the sides, with a light
in each horn. I postulated some kind of COB ASIC with a bipolar
transistor driving each lamp. Felt pretty silly when I found one
fractional-cent thermal flasher Xmas mini-light in each horn and no
active circuitry at all. ;-)

Sounds like a fun project, bit of shame I don't need a
fun project at this moment ;)
Click to expand...
Might be a fun project for a student. In VHDL, Verilog, with a
microcontroller or whatever.


Best regards,
Spehro Pefhany
--
"it's the network..." "The Journey is the reward"
speff@interlog.com Info for manufacturers: http://www.trexon.com
Embedded software/hardware/analog Info for designers: http://www.speff.com
 
Don't reinvent the wheel. Invert the SR outputs, and run them into a 74x148.
If you look at the data sheet,the circuit is obvious. You want INPUT7 to be
the *least* significant bit. If you have more than an 8 bit SR, you have to
do some cascading. There is also a 10 bit version.

Tam

"Davy" <zhushenli@gmail.com> wrote in message
news:1133273576.137921.272350@f14g2000cwb.googlegroups.com...
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
Click to expand...
 
"Davy" <zhushenli@gmail.com> schreef in bericht
news:1133273576.137921.272350@f14g2000cwb.googlegroups.com...
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
Click to expand...
Well, Davy,

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.

petrus bitbyter
 
"petrus bitbyter" <pieterkraltlaatditweg@enditookhccnet.nl> wrote in message
news:438cccb2$0$6508$e4fe514c@dreader11.news.xs4all.nl...
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.
Click to expand...
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 .
 
On Tue, 29 Nov 2005 06:12:56 -0800, Davy 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...
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
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top