Searching \ for '[EE] Digital circuit that counts 'ones'.' in subject line. ()
Help us get a faster server
FAQ page: massmind.org/techref/timers.htm?key=count
Search entire site for: 'Digital circuit that counts 'ones'.'.

Exact match. Not showing close matches.
'[EE] Digital circuit that counts 'ones'.'
2007\01\29@203016 by

This one is making me go crazy. I know there is a well-known solution
for detecting the number of 'ones' in a byte using logic gates (just as
you might use XOR's for parity check) but I just can't simply remember!

Do any of you guys do remember it?

Regards,

*Carlos Marcano*
-Guri, Venezuela-
From
my.opera.com/allbits/blog/show.dml/114980
which has a whole slew of interesting operations.

It's a start.

----------
13. Population Count (Ones Count)

The population count of a binary integer value x is the number of one
bits in the value. Although many machines have single instructions for
this, the single instructions are usually microcoded loops that test a
bit per cycle; a log-time algorithm coded in C is often faster. The
following code uses a variable-precision SWAR algorithm to perform a
tree reduction adding the bits in a 32-bit value:

unsigned int
ones32(register unsigned int x)
{
/* 32-bit recursive reduction using SWAR...
but first step is mapping 2-bit values
into sum of 2 1-bit values in sneaky way
*/
x -= ((x >> 1) & 0x55555555);
x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
x = (((x >> 4) + x) & 0x0f0f0f0f);
x += (x >> 8);
x += (x >> 16);
return(x & 0x0000003f);
}

----------

On 1/29/07, Carlos A. Marcano V. <c.marcanogmail.com> wrote:
> This one is making me go crazy. I know there is a well-known solution
> for detecting the number of 'ones' in a byte using logic gates (just as
> you might use XOR's for parity check) but I just can't simply remember!
>
> Do any of you guys do remember it?
>
> Regards,
>
> *Carlos Marcano*
> -Guri, Venezuela-
> -
All I seem to have is at:

http://www.piclist.com/techref/microchip/math/bit/countbits.htm

But that is programmatic rather than discrete logic.

I seem to remember such a thing but I also can't find it with a short
dogpile (.com) so I will be watching to see if anyone comes up with it.

---
James.

> {Original Message removed}
Carlos A. Marcano V. wrote:
> This one is making me go crazy. I know there is a well-known solution
> for detecting the number of 'ones' in a byte using logic gates (just as
> you might use XOR's for parity check) but I just can't simply remember!
>
> Do any of you guys do remember it?

What do you mean by "detect"? In other words, what should the output look
like?

Vitaliy

Never mind, I found it. In binary, a standard 2 bit (+ carry) full adder is
also counting the number of ones. To expand that, one must simply add the
results from more than one full adder.

http://www.circuitcellar.com/library/eq/144/5.htm

A full adder is shown here:
http://et.nmsu.edu/~etti/spring98/electronics/tapper/img00052.gif and
explained in dizzying detail here:
http://et.nmsu.edu/~etti/spring98/electronics/tapper/bcdpaper.html

Basically, for inputs A B and C, the outputs S0 and S1 are:

S0 = (A XOR B) XOR C

S1 = ( C AND (A XOR B) ) OR (A AND B)

---
James.

> {Original Message removed}
If you are using logic gates, you still have to
iterate each bit and use something like a counter to
add up the 1 bits. But the problem is an interesting
on. How to synthesis it purely on logic gates. A
counter IC is a collection of logic gates but you want
a simple version of counting one bits rite?

John

--- "M. Adam Davis" <stienmangmail.com> wrote:

{Quote hidden}

Vitaliy wrote:

> What do you mean by "detect"? In other words, what should the output look
> like?

I mean that from any byte the circuit would count how many bits are in
logic state 1. The output could be any representation of the result
(i.e, BCD).

Regards,

*Carlos Marcano*
-Guri, Venezuela-

I was looking for something less code-like and more hardware-like (TTL
gates and similar) but it is a very interesting reading.

Regards,

*Carlos Marcano*
-Guri, Venezuela-

{Quote hidden}

John Chung wrote:
> If you are using logic gates, you still have to
> iterate each bit and use something like a counter to
> add up the 1 bits. But the problem is an interesting
> on. How to synthesis it purely on logic gates. A
> counter IC is a collection of logic gates but you want
> a simple version of counting one bits rite?

Yes, the simpler, the better.

Regards,

*Carlos Marcano*
-Guri, Venezuela-

2007\01\29@222805 by
James Newton, Host wrote:
> Never mind, I found it. In binary, a standard 2 bit (+ carry) full adder is
> also counting the number of ones. To expand that, one must simply add the
> results from more than one full adder.
>
> www.circuitcellar.com/library/eq/144/5.htm
>
> A full adder is shown here:
> http://et.nmsu.edu/~etti/spring98/electronics/tapper/img00052.gif and
> explained in dizzying detail here:
> et.nmsu.edu/~etti/spring98/electronics/tapper/bcdpaper.html
>
> Basically, for inputs A B and C, the outputs S0 and S1 are:
>
> S0 = (A XOR B) XOR C
>
> S1 = ( C AND (A XOR B) ) OR (A AND B)

Awesome! Exactly what I was looking for.

Thanks a lot James!

Regards,

*Carlos Marcano*
-Guri, Venezuela-

It seems to me that that is a parity check.

Jim

{Quote hidden}

> --
hmmm...8 bit shift register and a BCD counter....still discrete logic but not a ton of gates.

Makes me wonder why anyone would do it in gates....8 pin PIC, serial data in, BCD out?

"Carlos A. Marcano V." <c.marcanogmail.com> wrote:

I was looking for something less code-like and more hardware-like (TTL
gates and similar) but it is a very interesting reading.

Regards,

*Carlos Marcano*
-Guri, Venezuela-

{Quote hidden}

Put the bits in the address lines of an eeprom
Program it with the right pattern to create the count at the outputs

Peter van Hoof

On 1/30/07, Peter van Hoof <pvhoofyahoo.com> wrote:
>
> Put the bits in the address lines of an eeprom
> Program it with the right pattern to create the count at the outputs

Or an LUT in software, you can make it a lot smaller if you do it by
nybbles.
On Tue, 2007-01-30 at 06:59 -0800, alan smith wrote:
> hmmm...8 bit shift register and a BCD counter....still discrete logic but not a ton of gates.
>
>   Makes me wonder why anyone would do it in gates....8 pin PIC, serial data in, BCD out?

Usually the answer to why anybody does anything in gates is very simple:
speed.

That's always a trade off with digital logic. Take pretty much any sort
of complex function and there are always two extremes in how to design
it: small and slow, or big and fast. Obviously there is alot of room in
between.

A similar situation often appears in the progamming world. Consider a
sine function. You can actually calculate the sine value, using the
formulas. Generally small in code size, but also takes alot of cycles to
complete. Consider the other extreme: a LUT. VERY fast (one cycle), but
also very big (depending on the resolution you're after).

TTYL

More... (looser matching)
- Last day of these posts
- In 2007 , 2008 only
- Today
- New search...