A Low-Latency Algorithm and FPGA Design for the Min-Search of LDPC Decoders

The problem of finding efficiently the first k minimum or maximum values is generally met in many application fields, such as error control coding. More specifically, optimized solutions for the selection of the two or three smallest elements out of a given set of numbers are greatly needed for the design of high-speed Low-Density Parity-Check (LDPC) decoders, as this min-search can be the bottleneck. This paper aims to tackle current limitations by proposing a novel algorithm for solving this problem, where the searching is based on scanning from the most significant bit (MSB) to the least significant bit (LSB) of each input data. A design mapped to reconfigurable logic and a software tool for the automatic generation of synthesizable VHDL codes, implementing such low-latency components are presented as well. Experimental results show that compared to existing solutions, the proposed scheme achieves an up to 42% reduction in latency even at worst case. Since the hardware unit is repeatedly used in the LDPC decoder design, the described high-speed approach is strongly recommended.