Hello,
I need help decoding the header of some data, it’s quite tricky, I’ll try to explain.
The data come to my module serially, I read it out of a FIFO.
The data are a series of data-words, let’s say 32 bit, representing the energy in various cells of a particle detector. It doesn’t really matter, just assume they are numbers from 0 to 2^32-1.
The data words are preceded by a header made of N+1 words, that gives information on the data-words that are coming next.
The first N (let’s say 4) words represent a bit mask of the data word that exceed 2 sigma, i.e. each bit of the first 4 words concatenated represent one of the following data words, if the bit is 1 then the relative word exceeds 2 sigma, if it’s 0 it doesn’t.
Where the sigma is the RMS relative to the distribution of all the words, so I can know in advance which data words are going to be relevant and which not.
But now the interesting part comes, the (N+1)th header word is the 4-sigma mask, which represent which words in the 2-sigma mask, also exceed 4 sigma.
Now the meaning of the 4-sigma mask bit changes relatively to the one of the 2-sigma mask, i.e. if the 4-sigma mask is 0001 this means that the 4th one of the 2sigma mask also exceeds 4 sigma.
So how can I decode the 4-sigma mask in a way that tells me which words that are about to come exceed 4-sigma? Ideally, I’d like to do it in a combinational way that doesn’t use a lot of resources and let me know it in 1 clock cycle.
This is because the first word in the FIFO after the header is in fact the first data word, that might exceed 4-sigma!
Anyone has a brilliant idea?
If you can provide us with timing diagram or drawings of block diagram, we could help you more on this. Basically, correct me if I am wrong, you are asking to feed the 4-sigma mask into your state machine, which process the data words. If you decode the header words one-cycle before the data words, you should be able to decode the data words. Unless, you have one-cycle latency between state transition. The best is to add in some additional condition in your “DEC_HEADER” state, which can decode the first data word.
Basically I would like some combinational logic to receive something like this, e.g.:
First mask:
00111000 00100010 00001000 00010010
Second mask:
01000100
And work out from the second mask combined with the first the following ones in bold:
00111000 00100010 00001000 00010010
And so the combined mask is:
00010000 00000000 00001000 00000000
I hope this example is more clear
Perfect, thank you for this explanation.
Here is a solution:
- use one-hot to binary encoder to get the location of the second mask. This comb block should have 8 output ports range from a to h, each with a binary unsigned index of a bit and a valid signal. In your example 01000100, you get 2 in port b and 6 in port f. Such one-hot to binary encoder can be found everywhere.
- use carry chain to extract the one in the first mask. Scan from bit 0 to 31, with a counter, if the counter equal to the binary input, output of carry chain at this bit location 1, otherwise 0. Use 8 instances of this carry chain to cover all these situations. Enable the instance if the port’s valid signal is high. In your example, you get 0001 0000 000000 00000000 00000000 in instance b and 0000 0000 00000000 00001000 00000000 in instance f.
- use OR-logic to combine the output of carry chain instances.
NOTE: 32 depth carry chain is a bit stretchy in most FPGAs. You can break this down into smaller ones at the cost of parallel 4 byte carry chain.
Thank you this is a very interesting solution, and it’s partly combinational and a little bit sequential in the part with the counter.
I’ll think about this, but also to tell the truth I think that it is more than 32 bits, I’ll find out the exact number and I’ll post here.
However, do you think this problem could be solved in a purely combinational way?
So the first mask is 128 bit and the second is around 40, let’s say 48 for the time being
Although in your example, you have decoded the entire 4 Sigma mask, since you’re data is coming off a fifo, can it be said that you just need to be able to categorize the data one at a time as you read off the fifo?
In that case, put the mask in a shift register. You can already decode 2 Sigma. If it’s a valid 2 sigma just check the MSB of the 4 Sigma mask. If it’s 1 it’s also a 4 Sigma. Just do a left shift after every valid 2 Sigma.
1 Like
This is a very good idea!