I am currently trying to learn how to program in VHDL with the goal of implementing an LDPC decoder in hardware. My understanding is that log-likelihood ratios (LLRs) serve as inputs to the decoder.
Is there an efficient way of reading from RAM if, for example, I have 1) 8-bit LLRs stored in a block of RAM that is 16 addresses deep, and 2) a 16-bit vector where a 1 in position X denotes that I want to read from address X.
As an example, given the 16-bit vector "1010100000000000", I would like to read from addresses 0, 2, and 4 (assuming that the LSB is on the left). My first thought is to use a loop through the entire vector, which seems inefficient in terms of clock cycles. Is there a way to quickly read from those three addresses, either in quick succession or in parallel?
Best Answer
A circuit that can identify a particular set bit in a vector in a fixed amount of time is called a "priority encoder". The general concept is that you use the priority encoder to find the first set bit in your vector, use its number to address your memory, and then you clear that bit in the vector so that the priority encoder can find the next set bit in the next cycle.
An 8176-input priority encoder would be a large circuit,1 but since you're expecting to find 32 set bits in your vector anyway, you could break the problem up so that you scan only part of the vector at a time. For example, you could build a 64-input priority encoder2 and scan your vector in blocks of 64 bits at a time, using 128 clock cycles. If you ever find more than one bit set in a given block, you'll need extra clock cycles to process them, but even in the worst case, you'll need no more than 159 clocks to complete the job.
1 Roughly 13,640 4-input LUTs.
2 If your FPGA has 4-input LUTs, such an encoder would require just 99 of them.