Count "1" bit in bit stream

Hi, all.
I'm using Xilinx FPGA with VHDL language.

Now I try to build a system, and that system
needs a counter which counts "1" bit in bit stream.
like "11101001" => 5

I've tried several methods like adding all bits to one
integer signal,
(That is, result <= bit(0)+bit(1)+bit(2) ...;)
or by using Xilinx bit correlator with all "1" reference
bit stream.

Is there any noble method for this problem?
Thanx for any help.

hetfield wrote:
> Hi, all.
> I'm using Xilinx FPGA with VHDL language.
> 
> Now I try to build a system, and that system
> needs a counter which counts "1" bit in bit stream.
> like "11101001" => 5
> 
> I've tried several methods like adding all bits to one
> integer signal,
> (That is, result <= bit(0)+bit(1)+bit(2) ...;)
> or by using Xilinx bit correlator with all "1" reference
> bit stream.
> 
> Is there any noble method for this problem?
> Thanx for any help.
> 

If you want to count the ones in an incoming bit stream, can you not 
just use the incoming data as an enable signal for a counter clocked 
with the same clock?

Thanks for your answer, but I want to count the "1" bits during only
one or two clock cycles.
I use 10 MHz clock in my system for synchronization.
And the input bit stream is about 150 bits long.
Moreover, input bit stream changes on every clock rising edges.
That why I cannot apply simple counter on this problem.

hetfield wrote:
> Thanks for your answer, but I want to count the "1" bits during only
> one or two clock cycles.
> I use 10 MHz clock in my system for synchronization.
> And the input bit stream is about 150 bits long.

Seems like a semantics issue.  Normally the term "bitstream"
implies data coming one bit at a time, serially.  So you're
saying every 100 nS you get 150 bits all at once?  Normally
we would say in this case the data is 150 bits "wide".

> Moreover, input bit stream changes on every clock rising edges.
> That why I cannot apply simple counter on this problem.

100 nS is a long time for modern FPGA's so you should be able to
use many levels of logic, however serializing the data to
1500 MHz, 1 bit wide would not be an option (for the counter
approach).  So normally you'd use LUT's to group as many bits
as possible into a sum in the first stage, possibly using
block RAMs as LUTs if your architecture permits.  Then use
a tree of adders to finish the addition.

Sorry for my mistake.
150 bits wide - That's exactly what I just meant.
Thank you very much for your help.
I'll try LUT methods for my design.

hetfield wrote:

> Thanks for your answer, but I want to count the "1" bits during only
> one or two clock cycles.
> I use 10 MHz clock in my system for synchronization.
> And the input bit stream is about 150 bits long.
> Moreover, input bit stream changes on every clock rising edges.
> That why I cannot apply simple counter on this problem.

So 1) how fast is the clock for your input bit stream and 2) why wait 
100 ns before starting to count?

In article <1127305201.546845.85310@g43g2000cwa.googlegroups.com>,
hetfield <magnacum@gmail.com> wrote:
>Thanks for your answer, but I want to count the "1" bits during only
>one or two clock cycles.
>I use 10 MHz clock in my system for synchronization.

I expect that a straightforward adder tree

b[1:0] = a[0] + a[1] + a[2]
b[3:2] = a[3] + a[4] + a[5]
b[5:4] = a[6] + a[7] + a[8]
...
c[2:0] = b[1:0] + a[3:2]
c[5:3] = b[5:4] + b[7:6]
...

[write perl to write the source code!]

would happily add 150 bits together in the hundred nanoseconds you've
got, using a total of about 150 adders of various widths (mostly
small).  If timing is critical, play around with the widths at the
bottom; 3 LUTs will do a count-bits on a 4-bit word in one propagation
delay.

Tom

It seems like you want to "count" the 1s in a 150-bit wide word, coming
in every 100 ns = 10 MHz.

Here is how I would do it:
Use 6 or 7 dual-ported BlockRAMs as LUTs.
Each BlockRAM is used as a ROM, organized 4k x 4,i.e. with 12 address
bits and 4 output bits.
The ROM stores the value of the number of ones on the address inputs.
One ROM takes care of 12 inputs, but since it is dual-ported, each
BlockRAM takes care of 24 inputs, generating two independent 4-bit
outputs.
Six BlockRAMs thus cover 144 inputs, and generate 12 independent 4-bit
binary numbers in less than 4 ns. The remaining 96 ns can be used in
simpler adder structures, or in a 12-step sequential accumulator
running at, say, 200 MHz.
Peter Alfke, Xilinx Applications

> It seems like you want to "count" the 1s in a 150-bit wide word, coming
> in every 100 ns = 10 MHz.
>
> Here is how I would do it:
> Use 6 or 7 dual-ported BlockRAMs as LUTs.
> Each BlockRAM is used as a ROM, organized 4k x 4,i.e. with 12 address
> bits and 4 output bits.
> The ROM stores the value of the number of ones on the address inputs.
> One ROM takes care of 12 inputs, but since it is dual-ported, each
> BlockRAM takes care of 24 inputs, generating two independent 4-bit
> outputs.
> Six BlockRAMs thus cover 144 inputs, and generate 12 independent 4-bit
> binary numbers in less than 4 ns. The remaining 96 ns can be used in
> simpler adder structures, or in a 12-step sequential accumulator
> running at, say, 200 MHz.
> Peter Alfke, Xilinx Applications

That's great guide for me.
Thanks a lot!

hetfield wrote:
> Hi, all.
> I'm using Xilinx FPGA with VHDL language.
> 
> Now I try to build a system, and that system
> needs a counter which counts "1" bit in bit stream.
> like "11101001" => 5
> 
> I've tried several methods like adding all bits to one
> integer signal,
> (That is, result <= bit(0)+bit(1)+bit(2) ...;)
> or by using Xilinx bit correlator with all "1" reference
> bit stream.
> 
> Is there any noble method for this problem?
> Thanx for any help.
> 

"in" is a standard_logic_vector( a downto 0)
"result" is an integer.

process(in)
variable i:integer;
variable sum:integer;
begin
	sum := 0;
	for i in 0 to in'left loop
		sum := sum + in(i);
	end loop;
	result <= sum;
end process;

Hope there are not to much errors, I have no syntax check on hand right now.

This is not executed sequentially. It only tells the compiler 
sequentially how to create the logic.

You may need arithmetic libs to add bits to integer.