Algorithms of Finding the First Two Minimum Values and Their Hardware Implementation

Abstract

Given a set of numbers X, finding the minimum value of X, min_1st, is a very easy task. However, efficiently finding its second minimum value, min_2nd, requires the derivations of min_1st and finding the minimum value from the set of the remaining numbers. Efficient algorithms and cost-effective hardware of finding the two smallest of X are greatly needed for the low-density parity-check (LDPC) decoder design. The following two architectures are developed in this paper: (1) sorting-based (XS) approach and (2) tree structure (TS) approach. Experimental results show that the XS approach provides less number of comparisons, while the TS approach achieves higher speed performance at lower hardware cost. Since the hardware unit is repeatedly used in the LDPC decoder design, the proposed high-speed low-cost TS approach is strongly recommended.