Count "1" bit in bit stream

Sep 21, 2005 9 Replies

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


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.

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

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.

So 1) how fast is the clock for your input bit stream and 2) why wait

100 ns before starting to count?

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

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

"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

Join the Discussion

Have something to add? Share your thoughts — no account required.

Didn't find your answer?

Ask the community — no account required