Counting Number of Set Bits / TMDS / DVI on FPGA

[amspire]

The trouble with complex combinatorial logic is you can end up with a fair bit of gate delay, and you need to allow for worse case settling time. It is hard to judge if this is a problem without knowing the device you are using.

If instead you set up a synchronous pipeline, then you can use counters or whatever you want, and you can still output at the full clock speed. If it takes 8 clock cycles for a counter to count the bits, and a couple more to then encode the data, just have a 10 stage synchronous pipeline, and every clock cycle, all the data just moves one step down the pipeline to the next set of registers. You get maximum speed without any critical gate delay problems.

Richard.

[joelby]

Unless you really want to re-invent the wheel, Xilinx have a reference design that implements a TMDS encoder and decoder. I've just had a look and it simply does this:

Code: [Select]

  reg [3:0] n1d; //number of 1s in din
  reg [7:0] din_q;

  always @ (posedge clkin) begin
    n1d <=#1 din[0] + din[1] + din[2] + din[3] + din[4] + din[5] + din[6] + din[7];

    din_q <=#1 din;
  end

The actual encoder should be portable to any FPGA. I've no idea if Altera have a similar app note and reference design, but I'd be surprised if they didn't.

XAPP495 is available from here and the design files here (latter requires a free Xilinx account).

[gamozo]

Thanks for all the help guys!

I'm going to go ahead and reinvent the wheel for my first prototype (I love working with gates), and then I'll make a 'proper' implementation.

Tonight I made a simple tester for stage 1 of the TMDS encoding and outputs to LEDs. Stage 2 will be tricky because it relies on the past data's parity.

What I get to see:



-Brandon

[joelby]

Cool! The schematic looks like a nightmare Have you considered using HDL?

[gamozo]

Cool! The schematic looks like a nightmare Have you considered using HDL?

I've been doodling gate-based circuitry in my notebook since I was 11. Now that I have an FPGA I can make all my dreams come true (without 100 hours of breadboarding)... it looks like art to me

But once I get bored of drawing gates (I've got a lot in my system to get out), I will use an HDL.

-Brandon

[amspire]

I've been doodling gate-based circuitry in my notebook since I was 11. Now that I have an FPGA I can make all my dreams come true (without 100 hours of breadboarding)... it looks like art to me

I like designing with gates as well, as long as I can see some kind of structure, so it is possible to make sense of it.

When it looks like randomly connected gates, I hate it.

Here is my take on a solution to your problem using gates. I have only done the first four bits, but there is a pattern that can be repeated for as many bits as you want. The output (I hope) is an ordered list of bits starting at the bottom and growing up. If only one bit is set on the input, the bottom bit only will be set on the output. If 3 bits are set on the input, then bottom 3 will be set on the output.



Each stage handles one more bit then the previous stage. Each stage consists of an AND gate at the top and an OR gate at the bottom. The intermediate bits use one AND gate and one OR gate each. Obviously each time you add a bit, the delay increased by two gate delays.

The rough logic is that if a output bit is set in the preceding stage, it stays set. If it was not set, then it gets set if the next lower bit is set, and the topmost bit of the stage is set. You only have to look at the topmost bit in stage to see if a new bit needs to turn on, since all the lower ones have been processed in the previous stages.

To check for =4 bits set then takes an XOR gate to the 4th and 5th outputs. To check for <4, you just invert the 4th output. To check for >4, you take the 5th output directly.

Probably not the most efficient solution, but it can be comprehended at least.

Richard.

[gamozo]

I wanted to share also my explanation about how my little design works.

https://www.eevblog.com/forum/beginners/counting-number-of-set-bits/?action=dlattach;attach=23082;image

Each stage (in the boxes) is essentially the same, but they process 1 less bit.

The XOR gates cascade all of the way through, to determine if the number of ones is even or odd. In the first stage, this determines if there are an even number of ones (sbits[0] == 0) or if there are an odd number (sbits[0] == 1).

The AND gates keep track of how many sets of two there are (thus, the second bit (2^1)). Even though there are 7 AND gates, it's impossible to have more than four set due to the design. Now the outputs of all the AND gates represents floor(red[7..0] / 2) [not in binary, but by the number of ones present... for example 0110100 is 3].

The second stage repeats this process, but now it determines if there's an even number of twos, and also it now uses the AND gates to create the representation of floor(red[7..0] / 4).

Finally the 3rd stage gets the third bit, and the fourth stage determines the final bit. (Note that the AND gates from the third stage are never used, but are just shown to show the pattern and are optimized out at compile-time)

Below all of these boxes is the logic to determine if it's =4, <4 or >4... and then determines which operation to use based on these.

Here's an example:

Code: [Select]

0 & = 0 -> stg1[0]
1 ^ = 1 -------------\
                     | & = 0 -> stg1[4]
1 & = 1 -> stg1[1]   | ^ = 1 -----------\
1 ^ = 0 -------------/                   \
                                          \
0 & = 0 -> stg1[2]                        | & = 1 -> stg1[6]
1 ^ = 1 -------------\                    / ^ = 0 -> sbits[0]
                     | & = 0 -> stg1[5]  /
0 & = 0 -> stg1[3]   | ^ = 1 -----------/
0 ^ = 0 -------------/

stg1[6..0] = 1000010
sbits[0]   = 0

Actual number of bits in the original string:

4 (0b100)

You can see how if you count the number of set bits in stg1, you get 2.
Multiply this 2 by 2 and you get 4... coincidence? No.
TL;DR: Come to think about it... what I'm doing is just base conversion using modulus.

-Brandon

[A-sic Enginerd]

This is probably a bit 'after the fact' in looking at the dates on replies, but here's my $0.02.
I actually had need of this very thing (counting ones in a reg) some time back, only for an actual ASIC. You hate to use a LUT as that takes real estate. Shift reg is the most obvious answer (small logic, easy to implement).....until you're counting 32 or 64 bit regs. Then it gets very expensive. Can't afford the latency. So that set me on a hunt. I think I ran across the very same link someone else pointed out earlier about how many algorithms there are to count 1's. I played around with a couple variants and synthesized each to see what they really looked like. (yes, I'm working in an HDL...Verilog to be specific).

The one that gave me the best solution, trading off area and doing it in a single clock cycle and still meeting timing was a simple for loop. (yes, for loops are a synthesize construct.....if used properly)

Code: [Select]

// sorry, I'll probably wind up mixing in some SystemVerilog syntax, but you'll get the gist
always_comb
begin
   count = 6'b0; // counter is this big because I'm counting a 32 bit reg
   for (integer i=0; i<32; i=i+1)
      count = count + my_reg[i];
end
This is actually, basically the same code as someone else wrote out from a Xilinx example it's just this one stays neater and tighter from a syntax perspective when the number of bits you're counting grows.

Soooo, what does that give me. Well, it actually winds up looking very similar to what you built by hand.
I can't be certain of the exact logic constructed, but it was similar enough I'd say you're spot on. (lots of XOR blocks staged serially). The difference here is coding it in HDL lessens the strain on the grey matter. And when you're block is a few hundred thousand gates, you can't afford to be drawing stuff out by hand.

Few other tidbits to take note of: if you haven't experienced it already, the actual clock speed you can get the FPGA to run at is dependent on how much utilization you have and the congestion / routing issues (as others have mentioned).
Yes, you can very likely get the IO / serdes / whatever to run at speed, but the internal logic can sometimes be a challenge to get to speed. I worked on a project that we stuffed into a very large, very expensive FPGA that had the serdes running at 1.5Gbps, but it was a stretch to get the internal logic to run at anything faster than 35MHz.

EDIT: DOH! hit post and realized the html conflicts with the Verilog syntax I was trying to type.