# how to implement the "how many" logic function?

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

1. ### nospamGuest

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

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 RoeGuest

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,

3. ### Tony RoeGuest

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,

4. ### Tim ShoppaGuest

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 BloggsGuest

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. ### Arie de MuynckGuest

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

"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. ### nospamGuest

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. ### Arie de MuynckGuest

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 BloggsGuest

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

11. ### Jim ThompsonGuest

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 BloggsGuest

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 ThompsonGuest

[snip]

Did you miss my post yesterday around noon Arizona time:

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 RoeGuest

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

15. ### Tony RoeGuest

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

16. ### Sir Charles W. Shults IIIGuest

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