| Author |
Message |
Frank Bemelman
Guest
|
 Posted:
Wed Nov 30, 2005 1:02 am Post subject:
Re: How to count zeros in registers? |
|
|
"Spehro Pefhany" <speffSNIP@interlogDOTyou.knowwhat> schreef in bericht
news:b08po11ms5v7s0lne6ek248lpsj69vnv2s@4ax.com...
| Quote: | 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 ;)
--
Thanks, Frank.
(remove 'q' and '.invalid' when replying by email)
|
|
| Back to top |
|
 |
Joel Kolstad
Guest
|
| Posted:
Wed Nov 30, 2005 1:35 am Post subject:
Re: How to count zeros in registers? |
|
|
"petrus bitbyter" <pieterkraltlaatditweg@enditookhccnet.nl> wrote in message
news:438cccb2$0$6508$e4fe514c@dreader11.news.xs4all.nl...
| Quote: | 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 . |
|
| Back to top |
|
|
Rich Grise
Guest
|
| Posted:
Wed Nov 30, 2005 1:35 am Post subject:
Re: How to count zeros in registers? |
|
|
On Tue, 29 Nov 2005 06:12:56 -0800, Davy wrote:
| Quote: | 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
|
|
| Back to top |
|
|
slebetman@yahoo.com
Guest
|
| Posted:
Wed Nov 30, 2005 1:35 am Post subject:
Re: How to count zeros in registers? |
|
|
Frank Bemelman wrote:
| Quote: | "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 ;)
|
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. |
|
| Back to top |
|
|
Art Stamness
Guest
|
| Posted:
Wed Nov 30, 2005 1:35 am Post subject:
Re: 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 |
|
| Back to top |
|
|
petrus bitbyter
Guest
|
| Posted:
Wed Nov 30, 2005 1:35 am Post subject:
Re: How to count zeros in registers? |
|
|
"Davy" <zhushenli@gmail.com> schreef in bericht
news:1133273576.137921.272350@f14g2000cwb.googlegroups.com...
| Quote: | 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 |
|
| Back to top |
|
|
Tam/WB2TT
Guest
|
| Posted:
Wed Nov 30, 2005 1:35 am Post subject:
Re: How to count zeros in registers? |
|
|
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...
| Quote: | 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
|
|
|
| Back to top |
|
|
Spehro Pefhany
Guest
|
| Posted:
Wed Nov 30, 2005 1:35 am Post subject:
Re: How to count zeros in registers? |
|
|
On Tue, 29 Nov 2005 20:02:21 +0100, the renowned "Frank Bemelman"
<f.bemelmanq@xs4all.invalid.nl> wrote:
| Quote: | "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.
|
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.
| Quote: | 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
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. ;-)
| Quote: | 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"
speff@interlog.com Info for manufacturers: http://www.trexon.com
Embedded software/hardware/analog Info for designers: http://www.speff.com |
|
| Back to top |
|
|
Mac
Guest
|
| Posted:
Wed Nov 30, 2005 9:35 am Post subject:
Re: How to count zeros in registers? |
|
|
On Tue, 29 Nov 2005 15:44:19 -0800, Art Stamness wrote:
| Quote: | 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 |
|
| Back to top |
|
|
Frank Bemelman
Guest
|
| Posted:
Wed Nov 30, 2005 9:35 am Post subject:
Re: How to count zeros in registers? |
|
|
"slebetman@yahoo.com" <slebetman@gmail.com> schreef in bericht
news:1133307891.046401.110620@z14g2000cwz.googlegroups.com...
| Quote: | 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.
|
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) |
|
| Back to top |
|
|
Stephane
Guest
|
| Posted:
Wed Nov 30, 2005 3:04 pm Post subject:
[OT] Re: How to count zeros in registers? |
|
|
soxmax wrote:
| Quote: | Davy wrote:
And I want to know the number of the zeros before the first 1
|
| Quote: | 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"...
|
|
| Back to top |
|
|
Meindert Sprang
Guest
|
| Posted:
Wed Nov 30, 2005 4:59 pm Post subject:
Re: [OT] Re: How to count zeros in registers? |
|
|
"Stephane" <stephane@nospam.fr> wrote in message
news:dmjq9c$l98$1@ellebore.extra.cea.fr...
| Quote: | soxmax wrote:
Davy wrote:
And I want to know the number of the zeros before the first 1
|
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 |
|
| Back to top |
|
|
Jan Decaluwe
Guest
|
| Posted:
Wed Nov 30, 2005 5:35 pm Post subject:
Re: How to count zeros in registers? |
|
|
Art Stamness wrote:
| Quote: | 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
--
Jan Decaluwe - Resources bvba - http://www.jandecaluwe.com
Losbergenlaan 16, B-3010 Leuven, Belgium
From Python to silicon:
http://myhdl.jandecaluwe.com |
|
| Back to top |
|
|
Arie de Muynck
Guest
|
| Posted:
Thu Dec 01, 2005 1:35 am Post subject:
Re: How to count zeros in registers? |
|
|
I found on the web some discussions, with this as the best observation:
| Quote: | 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.
--
Regards,
Arie de Muynck |
|
| Back to top |
|
|
Guest
|
| Posted:
Thu Dec 01, 2005 1:35 am Post subject:
Re: How to count zeros in registers? |
|
|
Jan Decaluwe skrev:
| Quote: | 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.
|
yep loop is better, I've always been told that casex is evil :)
| Quote: | 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 |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in