# How to count zeros in registers?

Discussion in 'VHDL' started by Davy, Nov 29, 2005.

1. ### DavyGuest

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, Nov 29, 2005

2. ### John PentonGuest

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?

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.

John Penton, Nov 29, 2005

3. ### StephaneGuest

John Penton 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?

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

This would waste a lot of resources if the reg is large... I would have
done it sequentially with a counter!

Stephane, Nov 29, 2005
4. ### Fred BloggsGuest

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

Fred Bloggs, Nov 29, 2005
5. ### Jim ThompsonGuest

On 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?
>
>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"

...Jim Thompson
--
| James E.Thompson, P.E. | mens |
| 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, Nov 29, 2005
6. ### Guest

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

, Nov 29, 2005
7. ### John PentonGuest

Jim Thompson wrote:
> On 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?
>>
>> 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"

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.

John Penton, Nov 29, 2005
8. ### Guest

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.

<snipped Fred being conversational>

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

, Nov 29, 2005
9. ### Richard HenryGuest

"Davy" <> wrote in message
news:...
> 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?

Use the register bits as address inputs to a ROM in which the data is coded
for the results.

Register --> ROM --> Output

Examples:

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.

Richard Henry, Nov 29, 2005
10. ### soxmaxGuest

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

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

soxmax, Nov 29, 2005
11. ### Spehro PefhanyGuest

On 29 Nov 2005 06:12:56 -0800, the renowned "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

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"
Info for manufacturers: http://www.trexon.com

Spehro Pefhany, Nov 29, 2005
12. ### Frank BemelmanGuest

"Davy" <> schreef in bericht
news:...
> 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).

Use a chain of 2-input or-gates, output to input.

Tie the other input of each gate to your register.

The outputs of each or-gate goes to an inverter.

The outputs of the inverters go to a 8-3 binary encoder.

--
Thanks, Frank.
(remove 'q' and '.invalid' when replying by email)

Frank Bemelman, Nov 29, 2005
13. ### Rick JacksonGuest

On Tue, 29 Nov 2005 15:02:42 GMT, 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.

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

Rick Jackson, Nov 29, 2005
14. ### Frank BemelmanGuest

"Spehro Pefhany" <> schreef in bericht
news:...
> On 29 Nov 2005 06:12:56 -0800, the renowned "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

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

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)

Frank Bemelman, Nov 29, 2005
15. ### Spehro PefhanyGuest

On 29 Nov 2005 08:31:46 -0800, the renowned
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

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"
Info for manufacturers: http://www.trexon.com

Spehro Pefhany, Nov 29, 2005
16. ### Spehro PefhanyGuest

On Tue, 29 Nov 2005 18:31:41 +0100, the renowned "Frank Bemelman"
<> wrote:

>"Spehro Pefhany" <> schreef in bericht
>news:...
>> On 29 Nov 2005 06:12:56 -0800, the renowned "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

>>
>> 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? ;-)

Best regards,
Spehro Pefhany
--
"it's the network..." "The Journey is the reward"
Info for manufacturers: http://www.trexon.com

Spehro Pefhany, Nov 29, 2005
17. ### Frank BemelmanGuest

"Spehro Pefhany" <> schreef in bericht
news:...
> On Tue, 29 Nov 2005 18:31:41 +0100, the renowned "Frank Bemelman"
> <> wrote:
>
> >"Spehro Pefhany" <> schreef in bericht
> >news:...
> >> On 29 Nov 2005 06:12:56 -0800, the renowned "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
> >>
> >> 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

--
Thanks, Frank.
(remove 'q' and '.invalid' when replying by email)

Frank Bemelman, Nov 29, 2005
18. ### Spehro PefhanyGuest

On Tue, 29 Nov 2005 20:02:21 +0100, the renowned "Frank Bemelman"
<> wrote:

>"Spehro Pefhany" <> schreef in bericht
>news:...
>> On Tue, 29 Nov 2005 18:31:41 +0100, the renowned "Frank Bemelman"
>> <> wrote:
>>
>> >"Spehro Pefhany" <> schreef in bericht
>> >news:...
>> >> On 29 Nov 2005 06:12:56 -0800, the renowned "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
>> >>
>> >> 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.

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.

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

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"
Info for manufacturers: http://www.trexon.com

Spehro Pefhany, Nov 29, 2005
19. ### Tam/WB2TTGuest

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" <> wrote in message
news:...
> 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
>

Tam/WB2TT, Nov 29, 2005
20. ### petrus bitbyterGuest

"Davy" <> schreef in bericht
news:...
> 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
>

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, Nov 29, 2005