1
\$\begingroup\$

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?

\$\endgroup\$
4
  • 2
    \$\begingroup\$ I don't know VHDL, but in Verilog a loop doesn't use more cycles, it just generates more hardware \$\endgroup\$
    – The Photon
    Jan 16, 2021 at 4:07
  • \$\begingroup\$ I think I understand what you mean and how that is the case for a loop construct in general. Maybe loop wasn't the right word, by loop I meant going through the vector bit by bit. I should've mentioned that I am looking at single-port block RAM, and my understanding is that I can only read one address per clock cycle. I am trying to see if, given the example vector above and its location of 1s, there is some way to read from addresses 0, 2, and 4 (3 clock cycles) instead of checking all 16 bits (16 clock cycles) and reading only from addresses 0, 2, and 4 during their respective clock cycles. \$\endgroup\$
    – austin
    Jan 16, 2021 at 5:07
  • \$\begingroup\$ Is there a limit to the number of bits that will be set in your address vector? Consider that an 8x16 is small enough that in a modern FPGA you could easily just store it in registers, and do the whole look-up operation in a single cycle. Assuming you don't need to replicate this 1000 times in your design. \$\endgroup\$
    – The Photon
    Jan 16, 2021 at 5:45
  • \$\begingroup\$ Ah yes that's true, this 8x16 example was just to keep my brainstorming simple. Ultimately, this address vector corresponds to a row in a parity check matrix of size 1022x8176 and row weight 32. So I am looking at an address vector that is 8176 bits long with 32 bits that are set and would be doing this operation 1022 times. \$\endgroup\$
    – austin
    Jan 16, 2021 at 6:01

2 Answers 2

Reset to default
1
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ Thanks for your answer Dave, using a priority encoder in the manner that you have described sounds like it'll do the trick. Just a couple of questions, for LUT utilization, how did you arrive at those numbers from the input size? Also, if I am interested in processing multiple vectors in parallel to read from memory, would my only option be to have multiple blocks of RAM with identical contents and read from those blocks separately? \$\endgroup\$
    – austin
    Jan 16, 2021 at 19:55
  • \$\begingroup\$ @Austin If the number of set bits is small, then you could have multiple units scanning for set bits and they could share the blockram. Actually if you have many vectors to process, then a simpler approach with shifting by one would minimize the logic for computing the addresses. You would just need a small fifo for the output of each address unit to save the addresses that you need to look up. If the FIFOs are big enough to accumulate all the addresses then you could just wait until they are all ready and have a mux read from each FIFO sequentially. \$\endgroup\$
    – IanJ
    Jan 16, 2021 at 20:56
  • \$\begingroup\$ The LUT counts are based on building a 4-input priority encoder (3 LUTs) and then using them, along with 4:1 muxes (3 LUTs per bit) to build a tree structure for larger encoders. \$\endgroup\$
    – Dave Tweed
    Jan 17, 2021 at 2:59
  • \$\begingroup\$ To answer your second question. the block RAM in FPGAs is usually dual-port, so you can do two reads simultaneously from a single BRAM. If you want to do more than that, then yes, you will need multiple copies of your data in separate BRAMs. \$\endgroup\$
    – Dave Tweed
    Jan 17, 2021 at 3:00
0
\$\begingroup\$

You can accelerate this as much as you want with more hardware. One way would be to create a circuit to count the number of zeros on the left, and use this as input to a barrel shifter to left shift the bit vector. You would accumulate the total number of shifts as the address that you want to look up. Barrel shifters can be implemented efficiently in Xilinx FPGAs with their multiplier DSP blocks. The amount of zeros that you look for would limit the speed up. If you look for up to 32 bits then you could run up to 32x faster.

As a design approach I would implement the simple solution first and use that to validate the design before optimizing.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks for you answer Ian. Priority encoders as Dave suggested are something that I have come across before, but this is also an interesting approach that I'll have to look into as well. As a beginner I do appreciate the advice, I might be getting ahead of myself here and will look to validate the design first. \$\endgroup\$
    – austin
    Jan 16, 2021 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.