Connect with us

how to implement the "how many" logic function?

Discussion in 'Electronic Design' started by Tony Roe, Aug 28, 2003.

Scroll to continue with content
  1. nospam

    nospam Guest


    As you noted later you can't represent from 0 to 8 bits set in a 3 bit
    output. Verilog for a 7 input version is :-

    module add1s(sum, ones);

    output [2:0] sum;
    input [6:0] ones;

    assign sum = ones[6] + ones[5] + ones[4] + ones[3]
    + ones[2] + ones[1] + ones[0];
    endmodule

    Synthesised with a rather old version of Altera MaxPlusII this occupies
    21% of an EPM7032-7 device with maximum delay of 17.5ns.


    Others have gone into deeper analysis but the reality is it is a 7 input 3
    output logic expression. You can make your definition of the expression as
    complicated as you like but after logic minimisation and fitting the end
    result will be more or less the same.
     
  2. Tony Roe

    Tony Roe Guest

    OK I understand each operation you have described, but I'm not getting something
    fundamental here - how come a 1-of-16 decoder has 5 outputs, not 16?

    Regards,
    Tony (remove "_" from email address to reply)
     
  3. Tony Roe

    Tony Roe Guest

    I assume the function "ones[]" is defined somewhere else (no previous Verilog
    experience)? Is there an Alterra or other apnote that might help me to
    understand this?
    Regards,
    Tony (remove "_" from email address to reply)
     
  4. Tim Shoppa

    Tim Shoppa Guest

    One way is to use 1 1-bit adder with carry out, 3 2-bit adders (the
    last with carry out), and 4 3-bit adders (the last with carry out)
    to simply form the arithmetic sum of the 8 input bits. Delay
    from input to output depends on how you make an adder in your CUPL,
    but it's probably 24 or 32 individual gate delays.

    You can also use a shift register and a counter.
    It takes you eight clock cycles + however long it takes the ripple carry
    to the last bit of the counter. You need a clock and a "go" input
    too.

    To do this with "flash" logic you basically make a lookup table.
    Not very elegant or conserving of gates, but it simply works.

    Another option is an analog adder to sum the input bits followed by a
    A/D converter to get the count.

    In the far distant past, when logic was done with relays, there was a
    branch of design called "iterative networks". These worked very neatly
    for this class of problem because with relay contacts inputs and outputs
    are reversible. Not so for modern logic, although maybe something
    clever could be done with bilateral switches. Are bilateral switches
    available in CUPL's? I've never seen such a thing...

    Tim.
     
  5. Fred Bloggs

    Fred Bloggs Guest

    This is not quite true, it can still be an 8->3 bit logic function with
    255 and 0->0. A 7-bit input acts on only 128 inputs and the 8-bit gives
    valid outputs for 255 inputs, a simple overflow indicator would be the
    AND of all input bits. I can see that you have incurred quite a bit of
    parallel product term expansion delay with the Verilog algorithm on the
    max7000- so you seem to be stuck at 40% full speed operation.
     
  6. "ones[6]" is not a function, it is the sixth bit in the bit array "ones[]",
    the 7 inputs to this encoder.

    What this sum = ... does is just add each input bit as a value '1' if the
    bit is active.
    If they are all set then 1+1+1+1+1+1+1 = 7

    Regards,
    Arie de Muynck
     
  7. Fred Bloggs

    Fred Bloggs Guest

    "sum=" is not a function- "[2:0] sum" is the module output vector, "="
    is the assignment statement, and the +'s operate on the components of
    "[6:0] ones" to produce the result.
     
  8. nospam

    nospam Guest

    An 8->3 function with overflow is an 8->4 function :).
    Using a lot of parallel expanders produced the fastest and smallest (as
    reported) fit. It is a complex equation. It fitted with 2 levels of logic
    (15ns) and some expander delay. I don't see it going any faster in that
    part,
     

  9. First, I never said "sum = ..." is a function. I just described what
    happens.
    Second, I gave an answer to someone without any Verlilog or VHDL reading
    experience. See his post.

    I wonder, what answer is better understood by such a person, yours or mine?

    Regards,
    Arie de Muynck
     
  10. Fred Bloggs

    Fred Bloggs Guest

    He is using CUPL so he will have no problem understanding assignments,
    data fields, and operators.
     
  11. Jim Thompson

    Jim Thompson Guest

    I hesitated to say anything further about adders until I had time this
    weekend to review digital "stuff" I used to teach nearly 40 years ago.

    Please see "HowManyOnes.pdf" on the S.E.D/Schematics page of my
    website, where I implement the function with "Half-Adders", for
    *seven* inputs.

    ...Jim Thompson
     
  12. Fred Bloggs

    Fred Bloggs Guest

    This might not be right-the bottom 2nd tier adder is adding 2's weighted
    sum from first tier ( each bit here represents two bits set on the
    input) so that the "recoder" truth table would be :

    Please view in a fixed-width font such as Courier.




    Original:

    +----------------------+-------+-------+--------+-----+-----+-----+
    | B is a "recoder"... | | | | | | |
    +----------------------+-------+-------+--------+-----+-----+-----+
    | A(2) | B(1) | C(1) | A+B+C | S4 | S2 | S1 |
    | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
    | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
    | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
    | 0 | 1 | 1 | 2 | 0 | 1 | 0 |
    | 1 | 0 | 0 | 2 | 0 | 1 | 0 |
    | 1 | 0 | 1 | 3 | 0 | 1 | 1 |
    | 1 | 1 | 0 | 3 | 0 | 1 | 1 |
    | 1 | 1 | 1 | 4 | 1 | 0 | 0 |
    +----------------------+-------+-------+--------+-----+-----+-----+


    Corrected?

    +----------------------+-------+-------+--------+-----+-----+-----+
    | B is a "recoder"... | | | | | | |
    +----------------------+-------+-------+--------+-----+-----+-----+
    | A(2) | B(1) | C(1) | A+B+C | S4 | S2 | S1 |
    | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
    | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
    | 0 | 1 | 0 | 2 | 0 | 1 | 0 |
    | 0 | 1 | 1 | 3 | 0 | 1 | 1 |
    | 1 | 0 | 0 | 2 | 0 | 1 | 0 |
    | 1 | 0 | 1 | 3 | 0 | 1 | 1 |
    | 1 | 1 | 0 | 4 | 1 | 0 | 0 |
    | 1 | 1 | 1 | 5 | 1 | 0 | 1 |
    +----------------------+-------+-------+--------+-----+-----+-----+


    Similarly, you have the 4's weighting. So a complete "recoder" table
    would have an additional column A(4).
     
  13. Jim Thompson

    Jim Thompson Guest

    [snip]

    Did you miss my post yesterday around noon Arizona time:

    I hesitated to say anything further about adders until I had time this
    weekend to review digital "stuff" I used to teach nearly 40 years ago.

    Please see "HowManyOnes.pdf" on the S.E.D/Schematics page of my
    website, where I implement the function with "Half-Adders", for
    *seven* inputs.

    ...Jim Thompson
     
  14. Tony Roe

    Tony Roe Guest

    <indents etc omitted as they disrupted the tabs etc, and adders now numbered>
    +---+
    1--¦ +-2-------+
    1--¦ A1¦ ¦
    1--¦ +-1-----+ ¦ +---+
    +---+ ¦ +-¦ +-4---+
    +---¦---¦ A4¦ ¦
    +---+ ¦ +-¦---¦ +-2-+ ¦ +---+
    1--¦ +-2-+ ¦ ¦ +---+ ¦ +-¦ +-8--
    1--¦ A2¦ ¦ ¦ +---¦ B +-4--
    1--¦ +-1-+ ¦ ¦ +---+ +-¦ +-2--
    +---+ ¦ ¦ +---¦ +-2---+ +---+
    +-|-----¦ A5¦
    +---+ ¦ +---¦ +-1-----------1--
    1--¦ +-2---+ ¦ +---+
    1--¦ A3¦ ¦
    1--¦ +-1-----+
    +---+
    A is the adder defined above.

    B is a "recoder"...
    A(2) B(1) C(1) A+B+C S4 S2 S1
    0 0 0 0 0 0 0
    0 0 1 1 0 0 1
    0 1 0 1 0 0 1
    0 1 1 2 0 1 0
    1 0 0 2 0 1 0
    1 0 1 3 0 1 1
    1 1 0 3 0 1 1
    1 1 1 4 1 0 0

    Therefore for the recoder, S4,S2,S1 may be defined as (one cell each)...
    S4 = A.B.C
    S2 = !A.B.C + A.!B.!C + A.!B.C + A.B.!C
    S1 = !A.!B.C + !A.B.!C + A.!B.C + A.B.!C

    This might not be right-the bottom 2nd tier adder is adding 2's weighted
    sum from first tier ( each bit here represents two bits set on the
    input)...

    Tony Roe> Referring the (now) numbered adders, the bottom 2nd tier adder is A5,
    which adds the three "1" outputs from the 1st tier, so A5's outputs are still
    weighted "1" and "2". The top 2nd tier A4 adds the "2" weighted outputs from the
    1st tier, so its outputs are weighted "2" and "4". In case it's not clear, the
    bottom output from each adder is the sum (usually "1"), and top is the carry
    (usually "2").


    so that the "recoder" truth table would be :

    Please view in a fixed-width font such as Courier.

    Original:

    +----------------------+-------+-------+--------+-----+-----+-----+
    | B is a "recoder"... | | | | | | |
    +----------------------+-------+-------+--------+-----+-----+-----+
    | A(2) | B(1) | C(1) | A+B+C | S4 | S2 | S1 |
    | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
    | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
    | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
    | 0 | 1 | 1 | 2 | 0 | 1 | 0 |
    | 1 | 0 | 0 | 2 | 0 | 1 | 0 |
    | 1 | 0 | 1 | 3 | 0 | 1 | 1 |
    | 1 | 1 | 0 | 3 | 0 | 1 | 1 |
    | 1 | 1 | 1 | 4 | 1 | 0 | 0 |
    +----------------------+-------+-------+--------+-----+-----+-----+

    Corrected?

    +----------------------+-------+-------+--------+-----+-----+-----+
    | B is a "recoder"... | | | | | | |
    +----------------------+-------+-------+--------+-----+-----+-----+
    | A(2) | B(1) | C(1) | A+B+C | S4 | S2 | S1 |
    | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
    | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
    | 0 | 1 | 0 | 2 | 0 | 1 | 0 |
    | 0 | 1 | 1 | 3 | 0 | 1 | 1 |
    | 1 | 0 | 0 | 2 | 0 | 1 | 0 |
    | 1 | 0 | 1 | 3 | 0 | 1 | 1 |
    | 1 | 1 | 0 | 4 | 1 | 0 | 0 |
    | 1 | 1 | 1 | 5 | 1 | 0 | 1 |
    +----------------------+-------+-------+--------+-----+-----+-----+

    Tony Roe> This isn't what I intended. It seems you are assigning weights of
    2,2,1 instead of 2,1,1 (actually scaled to 4,2,2 in the diagram). The recoder is
    essentially similar to the other adders except that one input (only) has higher
    weighting, hence needing a 3rd output as well.


    Similarly, you have the 4's weighting. So a complete "recoder" table
    would have an additional column A(4).

    Tony Roe> I'm not sure what you mean. I can't find the problem yet, although I
    have subsequently found that replacing the "recoder" with 2 more "bog standard"
    adders gives me an extra "2" input and a "4" input - all together, that means 8
    x 1bit inputs plus a 3bit carry input (4/2/1 weighted), which gets me to the
    next step of my project.

    Maybe my terminology is off?

    On a closely related subject, I've given up on VHDL for the moment, and found
    instead that ABEL looks like it might be able to do the job (for CPLDs) with a
    minimum of effort. Does that seem reasonable?

    Regards,
    Tony (remove "_" from email address to reply)
     
  15. Tony Roe

    Tony Roe Guest

    Jim,

    Sorry for not replying - I DID check out your website - thanks.

    When I get into a new field (as I am now), I find it satisfying to explore all
    the tradeoffs (ie, this discussion, all the data sheets and apnotes etc) to get
    an idea what the limitations are. So I was glad to see your half-adder circuit,
    as well as a number of other interesting (even if less useful to me) ideas. Who
    knows what will end up in the logic? In spite of my direct request for a
    CPLD-implentable solution, it's not the actual solutions that have benefited me
    most, it's the "getting there" ("teach a man to fish...")

    Regards,
    Tony (remove "_" from email address to reply)
     
  16. We could take a completely different tack- how about making eight inputs
    connect to a resistor bank with all identical values and feed the output input a
    bar graph chip hooked to a priority encoder?
    Now you get a non-uniform analog value from one to eight based on the output
    voltage, but that goes into a log scaled (or whatever) bar graph chip, which
    outputs 0 through 8 in "dot" mode. Any single bar will represent a number of
    ones- and the priority encoder would convert it to digital format.

    Cheers!

    Chip Shults
    My robotics, space and CGI web page - http://home.cfl.rr.com/aichip
     
Ask a Question
Want to reply to this thread or ask your own question?
You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.
Electronics Point Logo
Continue to site
Quote of the day

-