A systematic optimized comparison algorithm for fast LDPC decoding

Abstract

This paper proposes a novel systematic optimization algorithm for comparison operations required by a check node unit (CNU) in LDPC decoding, given any input number N-in. The algorithm can automatically synthesize an optimized fast comparison operations that guarantees a shortest comparison delay time of [log(2) (N-in - 1)] T-cmp and a minimized total number of two-input comparators, where T-cmp is the delay time of a comparator. High speed is achieved by adopting parallel divide-and-conquer comparison operations, while the required comparators are minimized by developing a novel set construction algorithm that maximizes shareable comparison operations. The designed CNU is favourable to the existing CNU designs which are non-systematically designed with either longer critical path delays or higher comparator counts than the proposed designs. The proposed design is particularly good for long code length cases, when it is impractical to do customized optimized designs by hand, due to high design complexity.