Counting ones

Hi,

Can anybody tell me a practical way (in VHDL) to count the number of 
ones in a bit pattern? Counting should be done with combinatorial logic, 
which means that a for-to loop cannot be used here (but being quite new 
to FPGA and VHDL, I'm not even sure). The number of bits to be counted 
is about 30, so a single look-up table is not the solution, using only a 
Spartan II.

Any suggestions? Purpose is amongst others pattern matching, where I 
count how many bits differ from the expected result.

Thanks,

Aart

Aart van Beuzekom wrote:

> Hi,
> 
> Can anybody tell me a practical way (in VHDL) to count the number of 
> ones in a bit pattern? Counting should be done with combinatorial logic, 
> which means that a for-to loop cannot be used here (but being quite new 
> to FPGA and VHDL, I'm not even sure). The number of bits to be counted 
> is about 30, so a single look-up table is not the solution, using only a 
> Spartan II.
> 
> Any suggestions? Purpose is amongst others pattern matching, where I 
> count how many bits differ from the expected result.
> 
> Thanks,
> 
> Aart
> 
I forgot to mention that the for-to loop cannot be used because I do not 
want the system to use any clock cycles - the result just has to be there.

Aart van Beuzekom <aart@westcontrol.dontspamme.com> wrote:
: Hi,

: Can anybody tell me a practical way (in VHDL) to count the number of 
: ones in a bit pattern? Counting should be done with combinatorial logic, 
: which means that a for-to loop cannot be used here (but being quite new 
: to FPGA and VHDL, I'm not even sure). The number of bits to be counted 
: is about 30, so a single look-up table is not the solution, using only a 
: Spartan II.

: Any suggestions? Purpose is amongst others pattern matching, where I 
: count how many bits differ from the expected result.

It has been discussed before. Try www.deja.com to search this group for old
answers.

Bye
-- 
Uwe Bonnes                bon@elektron.ikp.physik.tu-darmstadt.de

Institut fuer Kernphysik  Schlossgartenstrasse 9  64289 Darmstadt
--------- Tel. 06151 162516 -------- Fax. 06151 164321 ----------

Aart van Beuzekom schrieb:
> Hi,
> 
> Can anybody tell me a practical way (in VHDL) to count the number of 
> ones in a bit pattern? Counting should be done with combinatorial logic, 
> which means that a for-to loop cannot be used here (but being quite new 
> to FPGA and VHDL, I'm not even sure). The number of bits to be counted 
> is about 30, so a single look-up table is not the solution, using only a 
> Spartan II.
> 
Its not VHDL, but:
if you have bits numberd x0, x1, x2, x3 ... x30 than you can simply add
them: Y = x0 + x1 + x2 + ... x30 for counting ONE's

greetings, Bertram

-- 

Bertram Geiger,  Graz - AUSTRIA
Private Mail: remove the letters "b a d" from my reply address

Uwe Bonnes wrote:

> Aart van Beuzekom <aart@westcontrol.dontspamme.com> wrote:
> : Hi,
> 
> : Can anybody tell me a practical way (in VHDL) to count the number of 
> : ones in a bit pattern? Counting should be done with combinatorial logic, 
> : which means that a for-to loop cannot be used here (but being quite new 
> : to FPGA and VHDL, I'm not even sure). The number of bits to be counted 
> : is about 30, so a single look-up table is not the solution, using only a 
> : Spartan II.
> 
> : Any suggestions? Purpose is amongst others pattern matching, where I 
> : count how many bits differ from the expected result.
> 
> It has been discussed before. Try www.deja.com to search this group for old
> answers.
> 
> Bye

Hi Uwe,

Thanks for four response. Fortunately, I checked this newsgroup's 
archive before posting. The problem is that it isn't exactly pattern 
matching I want, but counting the number of errors (at the other end of 
a poor communication link) in a bitstream, compared to an expected 
pattern. Something that for example can be used to find a kind of 
preamble signal.
Any more suggestions?

Aart

"Bertram Geiger" <badnews_geiger@aon.at> wrote in message
news:3F784164.2000108@aon.at...
> Aart van Beuzekom schrieb:
> > Hi,
> >
> > Can anybody tell me a practical way (in VHDL) to count the number of
> > ones in a bit pattern? Counting should be done with combinatorial logic,
> > which means that a for-to loop cannot be used here (but being quite new
> > to FPGA and VHDL, I'm not even sure). The number of bits to be counted
> > is about 30, so a single look-up table is not the solution, using only a
> > Spartan II.
> >
> Its not VHDL, but:
> if you have bits numberd x0, x1, x2, x3 ... x30 than you can simply add
> them: Y = x0 + x1 + x2 + ... x30 for counting ONE's

I don't remember it being discussed so recently.  It might be too far back
to find, or maybe another newsgroup.  comp.arch might be a good choice.

Anyway, adding with carry save adders is the best combinatorial algorithm I
know of.  I don't know how well it works in an FPGA, though.

-- glen

Aart van Beuzekom <aart@westcontrol.dontspamme.com> wrote:
: Uwe Bonnes wrote:

:> Aart van Beuzekom <aart@westcontrol.dontspamme.com> wrote:
...
:> It has been discussed before. Try www.deja.com to search this group for old
:> answers.
:> 
:> Bye

: Hi Uwe,

: Thanks for four response. Fortunately, I checked this newsgroup's 
: archive before posting. The problem is that it isn't exactly pattern 
: matching I want, but counting the number of errors (at the other end of 
: a poor communication link) in a bitstream, compared to an expected 
: pattern. Something that for example can be used to find a kind of 

The second hit on deja in a search for "fpga counting ones" gives:

>Re: Counting the number of ones present ...
> comp.lang.verilog - 8 Jul 2002 by John_H - View Thread (10 articles)

http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&oe=UTF-8&threadm=3D29BF6F.C2CA3906%40mail.com&rnum=2&prev=/groups%3Fq%3Dfpga%2Bcounting%2Bones%26hl%3Den%26lr%3D%26ie%3DUTF-8%26oe%3DUTF-8%26start%3D0%26sa%3DN

The 6th hit is
Re: Count 1's algorithm...
... To count 16 ones you would need 5 CLBs and have one ... you have to do it and how many
bits you are counting. ... with a fanin and fanout of 2. The FPGA LUTs generally ...
comp.arch.fpga - 4 Feb 2000 by Dragon - View Thread (11 articles)

Hope this helps

-- 
Uwe Bonnes                bon@elektron.ikp.physik.tu-darmstadt.de

Institut fuer Kernphysik  Schlossgartenstrasse 9  64289 Darmstadt
--------- Tel. 06151 162516 -------- Fax. 06151 164321 ----------

Hi Aart

There is an excellent example of a combinational ones counter in the course
notes on our Comprehensive VHDL course ;-) Check out my employers website
for more details...

Our example does use a for loop - I'm not sure why you feel a for-loop
cannot be used for combinational logic, unless you are putting wait
statements inside the for loop, and in that case it probably won't
synthesise (unless you have a behavoral compiler). To work out what a loop
will do, simply replicate the contents of the loop once for each iteration
of the loop, replacing the loop parameter with a constant. eg

process(b , c)
begin
  for i in 0 to 3 loop
    a(i) = b(i) and c(3-i);
  end loop
end process;

is equivalent to

process(b , c)
begin
  a(0) = b(0) and c(3);
  a(1) = b(1) and c(2);
  a(2) = b(2) and c(1);
  a(3) = b(3) and c(0);
end process;


Try a for-loop looping the entire 'range of your error vector. Inside the
for loop, sum all the bits. So long as you get the types right and don't put
any timing in the loop, it will synthesise to combinational logic.

HTH

Ian Poole
--
Ian Poole, Consultant and Trainer

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * Perl * Tcl/Tk * Verification * Project Services

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.


"Aart van Beuzekom" <aart@westcontrol.dontspamme.com> wrote in message
news:bl8u9v$1v5$1@news.netpower.no...
> Hi,
>
> Can anybody tell me a practical way (in VHDL) to count the number of
> ones in a bit pattern? Counting should be done with combinatorial logic,
> which means that a for-to loop cannot be used here (but being quite new
> to FPGA and VHDL, I'm not even sure). The number of bits to be counted
> is about 30, so a single look-up table is not the solution, using only a
> Spartan II.
>
> Any suggestions? Purpose is amongst others pattern matching, where I
> count how many bits differ from the expected result.
>
> Thanks,
>
> Aart
>

"Uwe Bonnes" <bon@elektron.ikp.physik.tu-darmstadt.de> wrote in message
news:bl9cg6$7uq$1@news.tu-darmstadt.de...
> Aart van Beuzekom <aart@westcontrol.dontspamme.com> wrote:
> : Hi,
>
> : Can anybody tell me a practical way (in VHDL) to count the number of
> : ones in a bit pattern?

<snip>

In either the Xilinx or Altera architecture, it's probably most efficient to
pre-add in groups of 4 bits then add thse results in an adder tree.  For 32
bits (for instance) you can get 8 values with counts of 0-4 with simple
LUTs.  The next stages give 4 values of 0-8 by adding the previous values in
pairs, the next level is 2 values of 0-16 and the last stage is a single
adder with a result from 0 to 32.  This can be extended to whatever quantity
of bit errors you want to count per-cycle.

If you just try to add all 32 bits in one line - which is entirely valid -
some synthesizers will give you poor results.  The structured coding tesnds
to give structured results.  If you need higher speed, you can pipeline the
adder tree to get extreme clock rates.

- John_H

Aart van Beuzekom wrote:
> Hi,
> 
> Can anybody tell me a practical way (in VHDL) to count the number of 
> ones in a bit pattern?

Related thread:

http://groups.google.com/groups?q=pattern_recognizer


  -- Mike Treseler