How to count zeros in registers?

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

  1. Davy

    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, Nov 29, 2005
    #1
    1. Advertising

  2. Davy

    John Penton Guest

    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
    #2
    1. Advertising

  3. Davy

    Stephane Guest

    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!

    (and cross-posting is baaaaad ;-)
     
    Stephane, Nov 29, 2005
    #3
  4. Davy

    Fred Bloggs Guest

    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
    #4
  5. Davy

    Jim Thompson Guest

    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 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.
     
    Jim Thompson, Nov 29, 2005
    #5
  6. Davy

    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
    #6
  7. Davy

    John Penton Guest

    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
    #7
  8. Davy

    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>

    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
     
    , Nov 29, 2005
    #8
  9. "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:

    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.
     
    Richard Henry, Nov 29, 2005
    #9
  10. Davy

    soxmax Guest

    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
    #10
  11. 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
    Embedded software/hardware/analog Info for designers: http://www.speff.com
     
    Spehro Pefhany, Nov 29, 2005
    #11
  12. "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
    #12
  13. Davy

    Rick Jackson Guest

    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
    #13
  14. "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
    #14
  15. 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
    Embedded software/hardware/analog Info for designers: http://www.speff.com
     
    Spehro Pefhany, Nov 29, 2005
    #15
  16. 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
    Embedded software/hardware/analog Info for designers: http://www.speff.com
     
    Spehro Pefhany, Nov 29, 2005
    #16
  17. "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
    #17
  18. 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
    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 ;)


    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
    Embedded software/hardware/analog Info for designers: http://www.speff.com
     
    Spehro Pefhany, Nov 29, 2005
    #18
  19. Davy

    Tam/WB2TT Guest

    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
    #19
  20. "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
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. MM
    Replies:
    3
    Views:
    630
    Ralf Hildebrandt
    Jul 28, 2004
  2. martin f. krafft

    confusion when resetting registers

    martin f. krafft, Aug 18, 2004, in forum: VHDL
    Replies:
    2
    Views:
    474
    Paul Sereno
    Aug 19, 2004
  3. lucahtc
    Replies:
    0
    Views:
    1,410
    lucahtc
    Jul 8, 2010
  4. lucahtc

    count leading zeros

    lucahtc, Jul 13, 2010, in forum: VHDL
    Replies:
    0
    Views:
    932
    lucahtc
    Jul 13, 2010
  5. efelnavarro09
    Replies:
    2
    Views:
    957
    efelnavarro09
    Jan 26, 2011
Loading...

Share This Page