Author Topic: Counting Number of Set Bits / TMDS / DVI on FPGA  (Read 16663 times)

0 Members and 1 Guest are viewing this topic.

Offline gamozoTopic starter

  • Regular Contributor
  • *
  • Posts: 86
  • Country: us
    • Personal Website
Counting Number of Set Bits / TMDS / DVI on FPGA
« on: April 11, 2012, 05:10:56 am »
I wanted to figure out how many bits were set in an 8 bit number. If you haven't guessed, this is for a TMDS encoder for DVI/HDMI.

Just looking for tips/advice to see if I'm doing this all right. In the boxes is the logic itself (each stage determines a bit value for the number of 'set' bits), below is TMDS specific logic for deciding whether or not to use XOR or XNOR.

This is meant for an FPGA by the way.

-Brandon
« Last Edit: April 11, 2012, 11:04:53 pm by gamozo »
Brandon Falk, Systems Software Engineer
http://gamozo.org/ - http://gamozolabs.com/
 Catalog your components - http://eesdb.org/
 

Offline joelby

  • Frequent Contributor
  • **
  • Posts: 634
Re: Counting Number of Set Bits
« Reply #1 on: April 11, 2012, 05:52:18 am »
For 8-bit values, you may be better off just using block RAM as a look up table. I would test both approaches and see which achieves timing, though BRAM would probably be simpler to implement and faster than combinatorial logic.
 

Offline graynomad

  • Regular Contributor
  • *
  • Posts: 54
  • Country: au
Re: Counting Number of Set Bits
« Reply #2 on: April 11, 2012, 06:37:07 am »
Quote
This is meant for an FPGA by the way.
Thank goodness for that.

If you have some RAM why not just to a lookup table?

EDIT: Oops, joelby beat me to it, that'll teach me to have dinner after loading the post and before responding :)

______
Rob
« Last Edit: April 11, 2012, 06:40:17 am by graynomad »
Graynomad, AKA Rob Gray www.robgray.com
 

Offline cybergibbons

  • Frequent Contributor
  • **
  • Posts: 400
Re: Counting Number of Set Bits
« Reply #3 on: April 11, 2012, 06:54:24 am »
I'd also say use RAM. It's such a small amount of RAM that distributed RAM would do the trick. With combinatorial logic, it's easy to make mistakes and miss timing requirements.
 

Offline slateraptor

  • Frequent Contributor
  • **
  • Posts: 833
  • Country: us
Re: Counting Number of Set Bits
« Reply #4 on: April 11, 2012, 04:07:50 pm »
If the guaranteed 1-cycle penalty incurred by using an instantiated ROM LUT isn't a big deal, I'd go that route, as everyone else has suggested.

What FPGA do you intend to use btw?
 

Offline gamozoTopic starter

  • Regular Contributor
  • *
  • Posts: 86
  • Country: us
    • Personal Website
Re: Counting Number of Set Bits
« Reply #5 on: April 11, 2012, 04:35:09 pm »
I'm using a Cyclone IV. I haven't looked into working with the built in block RAM yet, but I probably will end up using it. However I think it would be tough for it to address memory, and then clock it out, faster than my circuit would react. But I really have no clue. It sounds like something fun to do benchmarking on.

-Brandon
Brandon Falk, Systems Software Engineer
http://gamozo.org/ - http://gamozolabs.com/
 Catalog your components - http://eesdb.org/
 

Offline olsenn

  • Frequent Contributor
  • **
  • Posts: 993
Re: Counting Number of Set Bits
« Reply #6 on: April 11, 2012, 04:40:46 pm »
My Verilog is rusty, so forgive me if this makes no sense, but what about:

module countBits(number[7:0])
       reg count;
       initial
           begin
               count < 0;
               if(number[0] == 1) count <= count + 1;
               if(number[1] == 1) count <= count + 1;
               if(number[2] == 1) count <= count + 1;
               if(number[3] == 1) count <= count + 1;
               if(number[4] == 1) count <= count + 1;
               if(number[5] == 1) count <= count + 1;
               if(number[6] == 1) count <= count + 1;
               if(number[7] == 1) count <= count + 1;
           end
endmodule
 

Offline olsenn

  • Frequent Contributor
  • **
  • Posts: 993
Re: Counting Number of Set Bits
« Reply #7 on: April 11, 2012, 04:42:15 pm »
...and of course you'd have to output the count register to whichever module needs it
 

Offline gamozoTopic starter

  • Regular Contributor
  • *
  • Posts: 86
  • Country: us
    • Personal Website
Re: Counting Number of Set Bits
« Reply #8 on: April 11, 2012, 04:51:24 pm »
Can't check your Verilog... as I've barely played with HDLs yet.

However, wouldn't adding each of the 8 bits to a counter take eight 4-bit full adders? 0-8 takes 4-bits to represent, and 8 add operations are done (unless you have a clock and run in O(n)... but I want O(1) [do those terms even apply here?]). And 8 4-bit full adders would take up a lot more space on the chip. However, at least we would know that your code will work properly (if syntax is in order). I haven't tested mine... it will be a pain to debug if it doesn't work, but I think it *should* just fine (famous last words).

-Brandon
Brandon Falk, Systems Software Engineer
http://gamozo.org/ - http://gamozolabs.com/
 Catalog your components - http://eesdb.org/
 

Offline free_electron

  • Super Contributor
  • ***
  • Posts: 8515
  • Country: us
    • SiliconValleyGarage
Re: Counting Number of Set Bits
« Reply #9 on: April 11, 2012, 04:52:05 pm »
If time is not an issue i use this trick :
n-bit shift register. output of shift register drives enable pin on a counter.
step1 : reset counter and load shift register.
step 2 : apply n clockpulses. the latched data shifts out and controls the ENABLE pin of the counter. if the bit is 1 the counter is allowed to increment. if the bit is zero the counter does not increment.
step 3: at 'n'th clockpulse : copy the counter in an output register.

This thing is scalable. and requires very little resources. ( especially as the number of bits increases. for every extra bit you need only one extra flipflop in the input latch. and for every additional power of 2 you need an additional flipflop in your output counter and step counter. So , 32 bit system requires only 32 input flipflops and three time 5 flipflops (2^5 = 32).  (5 for the step counter , 5 for the bitcounter and 5 for the output latch )
Professional Electron Wrangler.
Any comments, or points of view expressed, are my own and not endorsed , induced or compensated by my employer(s).
 

Offline free_electron

  • Super Contributor
  • ***
  • Posts: 8515
  • Country: us
    • SiliconValleyGarage
Re: Counting Number of Set Bits
« Reply #10 on: April 11, 2012, 04:54:17 pm »
My Verilog is rusty, so forgive me if this makes no sense, but what about:

module countBits(number[7:0])
       reg count;
       initial
           begin
               count < 0;
               if(number[0] == 1) count <= count + 1;
               if(number[1] == 1) count <= count + 1;
               if(number[2] == 1) count <= count + 1;
               if(number[3] == 1) count <= count + 1;
               if(number[4] == 1) count <= count + 1;
               if(number[5] == 1) count <= count + 1;
               if(number[6] == 1) count <= count + 1;
               if(number[7] == 1) count <= count + 1;
           end
endmodule
Verilog is not a programming language... This doesn't work at all as all the expressions are evaluated in parallel. What you made is an or gate...
when one of the inputs is high 'count' will be 1...
Professional Electron Wrangler.
Any comments, or points of view expressed, are my own and not endorsed , induced or compensated by my employer(s).
 

Offline gamozoTopic starter

  • Regular Contributor
  • *
  • Posts: 86
  • Country: us
    • Personal Website
Re: Counting Number of Set Bits
« Reply #11 on: April 11, 2012, 04:57:52 pm »
This thing is scalable. and requires very little resources. ( especially as the number of bits increases. for every extra bit you need only one extra flipflop in the input latch. and for every additional power of 2 you need an additional flipflop in your output counter and step counter. So , 32 bit system requires only 32 input flipflops and three time 5 flipflops (2^5 = 32).  (5 for the step counter , 5 for the bitcounter and 5 for the output latch )

This was my original thought, but I don't think I will be able to afford 5 clock pulses to do this. This will be for a TMDS implementation. If you're not familiar: http://www.oocities.org/yehcheang/Images/TMDS_Encoding_Algorithm.jpg . I'm only on the first 'decision'... not even the first stage :P

I was wondering about that Verilog as well.. I didn't know if there was any sort of atomic protection.

I think I'll have to go with my circuit (at this point I'm proud of it so it's going to be hard to convince me to not use it) or use a lookup table.

It's actually really interesting that I'm working on this project again. During my Google interview 'how to count bits' was one of the questions. Sadly it was for computers, and obviously a lookup table was the option there.

-Brandon
Brandon Falk, Systems Software Engineer
http://gamozo.org/ - http://gamozolabs.com/
 Catalog your components - http://eesdb.org/
 

Offline jahonen

  • Super Contributor
  • ***
  • Posts: 1052
  • Country: fi
Re: Counting Number of Set Bits
« Reply #12 on: April 11, 2012, 06:31:04 pm »
I don't obviously know implementation details but I somehow guess that small latency does not harm, so you can use as many clock cycles between DVI output and your pixel input as you like as long as you maintain the required throughput. So you can create a pipelined structure where each stage processes different pixel in various stages. That fits on a FPGA perfectly. In fact pipelined structures are preferred instead of complex combinatorial logic.

I agree that using block RAM is the simplest way, and is resource efficient on Cyclone IV. It takes only one memory block. You can easily add the ROM using megawizard plugin manager in Quartus,  it creates block symbol file etc. for you, when you enter some basic parameters, like data width and number of words. You can then punch an address into your ROM memory block in each clock cycle, and you get your result out after latency for each clock. Very simple.

Regards,
Janne

 

Offline free_electron

  • Super Contributor
  • ***
  • Posts: 8515
  • Country: us
    • SiliconValleyGarage
Re: Counting Number of Set Bits
« Reply #13 on: April 11, 2012, 06:48:45 pm »
You can use your own clock. Given that internal clocks in FPGa's can be pumped up to 400 MHz ... even if you need 10 clockticks to calculate...

ANyway , what you need can be resolved in a different way. you are not interested in the absolute bitcount... you only need to know if there are more 1's than zeros... so you can use a modified exor tree.

look at two adjacent bits. if they are 01 or 10 -> eliminate them they balanced each other out

you need to build a block that has 2 outputs. 1 output tells you 'BALANCED', the other tell's you if its 0 heavy or 1 heavy...

you need 4 of these blocks. this reduces your outputs to 4.
now build a block that looks at two adjacent outputs. if both are balanced set an output 'balanced'. if they are not balanced look of one is 0 heavy and the other '1 heave and strike them out to 'balance ( exor gate ). if the result is again imbalanced it will be '0' heavy or '1 heavy'

this output essentially tells you the output for 4 input bits. ( no need to look at all 8 )
the outputs tells you : the block is either internally balanced , or it is leaning to 1 , or leaning to 0

at the top level you only need to compare 2 blocks. if both yield 'balanced', or one is leaning 1 and the other leaning 0 you decide based on D0. in other instances you  take the 'leaning' result.

i'd have to work it out but i think all you need is about 6 xor gates and some AND and or gates.
You can reduce the logic becasue you do not need an absolute bit count as a numerical value. you are only interested if the 1 and 0's are balance , leaning towards 1 or leaning towards 0.

Now, here is another thing. This is for digital video. the bits are transmitted serially... so you can do away with the shifter altogether. all you need is a counter. drive the enable with the incoming bitstream , syncronize with the bitclock and by the time the last bit is received you have your answer.

Sync a state machine to D7 , and at the moment D0 is in you know the answer. ( plus some propagation time, but well before the next clocktick ).
Now, that being said. How are you going to capture this stream ? You will need a bloody fast FPGA to handle the bitstream ... TMDS uses a 165 MHz i/o clock.. guess what... it won't be a plcc44 on a double sided board ... FPGA's that can handle that are BGA , need 6 to 12 layer boards, matched impedance and tuned line lengths. And they need differential transceiver cells.... And you are trying to design this as a schematic... ( you don't know an HDL apparently .. ) Pardon my french but : FAIL !

Second problem. Silicon Image holds the rights on TMDS ... if you build a decoder and publish it you will have to fork over some serious dough to them ...
« Last Edit: April 11, 2012, 06:57:34 pm by free_electron »
Professional Electron Wrangler.
Any comments, or points of view expressed, are my own and not endorsed , induced or compensated by my employer(s).
 

Offline Rufus

  • Super Contributor
  • ***
  • Posts: 2095
Re: Counting Number of Set Bits
« Reply #14 on: April 11, 2012, 06:51:15 pm »
I wanted to figure out how many bits were set in an 8 bit number. If you haven't guessed, this is for a TMDS encoder for DVI/HDMI.

http://read.pudn.com/downloads183/sourcecode/embed/857895/xapp460/dvi_demo/rtl/tx/encode.v__.htm

Supposed to manage 700Mb/s in a Spartan3A
 

Offline gamozoTopic starter

  • Regular Contributor
  • *
  • Posts: 86
  • Country: us
    • Personal Website
Re: Counting Number of Set Bits
« Reply #15 on: April 11, 2012, 07:37:25 pm »
Interesting that they add them all up instead of using a lookup table... I guess the 'decision' process really doesn't need to be fast though, it only has to run at the pixel rate. My fastest PLL runs at about 450MHz, so I'm going to be stuck with that.

At 450MHz I could run 1080p @ 20Hz... but would a monitor complain if I don't give it 60Hz refresh rate?

-Brandon
Brandon Falk, Systems Software Engineer
http://gamozo.org/ - http://gamozolabs.com/
 Catalog your components - http://eesdb.org/
 

Offline slateraptor

  • Frequent Contributor
  • **
  • Posts: 833
  • Country: us
Re: Counting Number of Set Bits
« Reply #16 on: April 11, 2012, 07:43:52 pm »
My fastest PLL runs at about 450MHz, so I'm going to be stuck with that.

If you get your architecture to f'n properly at 450MHz, I'd be impressed.
 

Offline gamozoTopic starter

  • Regular Contributor
  • *
  • Posts: 86
  • Country: us
    • Personal Website
Re: Counting Number of Set Bits
« Reply #17 on: April 11, 2012, 07:53:30 pm »
My fastest PLL runs at about 450MHz, so I'm going to be stuck with that.

If you get your architecture to f'n properly at 450MHz, I'd be impressed.

The output will have to throw the bits out at 450MHz. My calculations will only have to be done at 45MHz (I can calculate on the pixel rate, data goes out at 10x pixel rate). I don't think 45MHz is very impractical... and I'm sure I can PISO bits out at 450MHz. I don't have much of a clue though.
Brandon Falk, Systems Software Engineer
http://gamozo.org/ - http://gamozolabs.com/
 Catalog your components - http://eesdb.org/
 

Offline cybergibbons

  • Frequent Contributor
  • **
  • Posts: 400
Re: Counting Number of Set Bits
« Reply #18 on: April 11, 2012, 07:55:21 pm »
Looking at the image of the algorithm, isn't the idea that this can be processed serially, bit by bit? There doesn't seem to be any need to change this into bytes before performing the operation.
 

Offline joelby

  • Frequent Contributor
  • **
  • Posts: 634
Counting Number of Set Bits
« Reply #19 on: April 11, 2012, 10:20:23 pm »
Some FPGAs have built-in SERDES blocks, which make high speed serial data I/O much simpler, because you can send them 4, 5, or 8-bit words (or whatever) at a fraction of the line rate. This makes it quite easy to achieve sensible fabric timing on inexpensive FPGAs such as the Xilinx Spartan-6. I'm not sure which Altera series incorporate SERDES, but it's well worth seeing if yours does.
 

Offline 0xdeadbeef

  • Super Contributor
  • ***
  • Posts: 1570
  • Country: de
Re: Counting Number of Set Bits
« Reply #20 on: April 11, 2012, 10:47:11 pm »
Trying is the first step towards failure - Homer J. Simpson
 

Offline gamozoTopic starter

  • Regular Contributor
  • *
  • Posts: 86
  • Country: us
    • Personal Website
Re: Counting Number of Set Bits
« Reply #21 on: April 11, 2012, 11:03:23 pm »
Some FPGAs have built-in SERDES blocks, which make high speed serial data I/O much simpler, because you can send them 4, 5, or 8-bit words (or whatever) at a fraction of the line rate. This makes it quite easy to achieve sensible fabric timing on inexpensive FPGAs such as the Xilinx Spartan-6. I'm not sure which Altera series incorporate SERDES, but it's well worth seeing if yours does.

I only saw things about SERDES and LVDS... however the LVDS output on my chip can run a 10-bit line with a serial output at 840MHz! That probably can get me to 720p. I'll wait till I get home to see what megafunctions I can throw in there. Perhaps LVDS is optional.

(http://www.altera.com/literature/hb/cyclone-iv/cyiv-53001.pdf - Section 1-31)

-Brandon
Brandon Falk, Systems Software Engineer
http://gamozo.org/ - http://gamozolabs.com/
 Catalog your components - http://eesdb.org/
 

Offline Rufus

  • Super Contributor
  • ***
  • Posts: 2095
Re: Counting Number of Set Bits
« Reply #22 on: April 11, 2012, 11:33:39 pm »
Interesting that they add them all up instead of using a lookup table...

But does it? If the synthesiser is any good a combinatorial logic expression will be minimised and fitted to the hardware regardless of how it was expressed in HDL. If you coded a large case statement which looks like a lookup table the end result should be the same.
 

Offline free_electron

  • Super Contributor
  • ***
  • Posts: 8515
  • Country: us
    • SiliconValleyGarage
Re: Counting Number of Set Bits / TMDS / DVI on FPGA
« Reply #23 on: April 12, 2012, 12:57:31 am »
the key to the TMDs system is that you do not need to count bits ! you only need to know if the word is 'balanced' and to which side it leans.
For every zero you need a one.
Here's how its done in the real silicon: 4 bit counter loaded with combination 1000  for every incoming bit that is 1 they increment. for every incoming bit that is zero they decrement.
if at the end the counter is still at '1' they use te last received bit as parity. For other combinations you only need to look at the LSB of the 4 bit counter.
Don't know if this is portable to FPGA.... the i/o structures may not have fast enough flipflops..
Professional Electron Wrangler.
Any comments, or points of view expressed, are my own and not endorsed , induced or compensated by my employer(s).
 

Offline gamozoTopic starter

  • Regular Contributor
  • *
  • Posts: 86
  • Country: us
    • Personal Website
Re: Counting Number of Set Bits / TMDS / DVI on FPGA
« Reply #24 on: April 12, 2012, 01:08:12 am »
I essentially just add the bits, and ignore the extra complications of decrementing. Then I compare if it's >4, =4 or <4. You can see the comparison logic at the bottom of the schematic, below the boxes. Pretty simple.
Brandon Falk, Systems Software Engineer
http://gamozo.org/ - http://gamozolabs.com/
 Catalog your components - http://eesdb.org/
 


Share me

Digg  Facebook  SlashDot  Delicious  Technorati  Twitter  Google  Yahoo
Smf