Can I counter how many 0s and 1s in a fixed size boolen array in one FPGA tick?

[jiangliang]

Hello there: I want to make a protocol decoding program, as there is no additional clock wire provided, I need to match the frame head, to provide max robust, I decided to let fpga build a shifting array, and push every bit from the beginning of the array, then I will compare the array to my gold pattern every tick, I hope by doing so it can make my decoding program ignore some transmission errors. Now there comes the question, can I actually make this happen at FPGA level? I would say it kinda like correlation, and I only need to find when the correlation output is at its' max, then I can be sure I have a synced clock there. The clock would be around 5Mhz.

[nathand]

What's the size of the Boolean array? One way to do it is with a lookup table on each byte. Convert 8 bits of the array to a number (this is free on the FPGA), use that as an index into a lookup table. The lookup table output is the number of 1s in that byte. Sum the results from each byte of the array. You should be able to do each byte in parallel, quite possibly within a single clock cycle.

I hope that helps; your question isn't totally clear so I'm just answering what you asked in the subject line.

[Dragis]

You can fit quite a bit of boolean logic in a 5 MHz clock tick, but without knowing more specifics I would recommend just trying it out and seeing if it works. And, like others mentioned previously, there are a number of ways to do this trading off clock rate for resource utilization.

[ZX81]

I suspect counting bits isn't really what you're looking for.  You mentioned the gold pattern...  You can probably XOR the input with your gold pattern, and OR the results:

As long as there aren't a lot of bits, it should be single-cycle (I never found the cell-size limits of the FPGAs).  

It sounds like this is a serial application, so counting as the bits come in may be tempting, but it's hard to reset the counters correctly.  In a few cases, you may get away with an unsigned fixed-point number that doesn't wrap on overflow.

[jiangliang]

Thank you for your time, you're right about my application, I want to approximate-matching a bit pattern from a digital input, say that sometimes there might be errors introduced while transmission, I want to let my system ignore certain amounts of error. So the diagram you posted would work if every thing runs perfectly, but we all know it not always happen.

[jiangliang]

the array contains about 500 boolen elements.

[Dragis]

Is the boolean signal stream coming from a digital I/O? If so, you should definitely be able to clock your digital input into a shift register and then compare the latest 500 elements to a golden header packet to perform the correlation.

[ZX81]

I'm relatively certain for 500 elements, the answer is:  No.

I have some good experience with GPS (with CDMA), and this sounds fairly similar to that, so I'll answer you from that perspective.  So, it sounds like what you'd like is something more like:

In GPS, at least in about 1994, that wasn't feasible.  What we did instead, was guess at the clocking, and start multiplying (XOR) the input against what we thought was the right pattern, sum the result, and see if the sum constantly increased, or averaged close to 0.  If it increased, we were likely correct.  If it decreased, we had the polarity opposite (easy in GPS), but otherwise likely correct.  We constantly shifted the guess at clocking, until we got a match.  This algorithm (correlation) was done many times at once, looking for different clocking, to find the match more quickly.

It would be awefully tedious, but you may be able to get some success by breaking up the 500 bit gold pattern into groups of about 8 bits, and test the input against each one separately, then see if the match against [0-7] 492 clicks ago, plus the match against [8-15] 484 clicks ago.......[492..499] right now, all add up to the acceptable level (or highest level).  I said '8 bits' thinking the idea posted before by nathand, about using a memory-look-up to count 'on' bits would be very helpful.

[ZX81]

Here's another approach, but it requires a huge FPGA:

Use 500 counters.  Each counter compares the input to a different clocking of the signal.  You may need to read the counters and clear them periodically.

[Dragis]

One thing to remember is that even though the clock being synchronized is running at 5 MHz, the FPGA clock can be much faster. If you clock the logic at 100 MHz, that gets you 20 cycles to compute the correlation which should be more than enough time to pipeline scanning 500 elements. And if you only need to slowly stear the 5 MHz clock every once in a while you may have 100s of 100 MHz clock cycles to work with. Again, this all depends on exactly what the needs for this particular system are.