We investigate iterative low-resolution message-passing algorithms for quasi-cyclic LDPC codes with horizontal and vertical layered schedules. Coarse quantization and layered scheduling are highly relevant for hardware implementations to reduce the bit width of messages and the number of decoding iterations. As a novelty, this paper compares the two scheduling variants in combination with mutual information maximizing compression operations in variable and check nodes. We evaluate the complexity and error rate performance for various configurations. Dedicated hardware architectures for regular quasi-cyclic LDPC decoders are derived on a conceptual level. The hardware-resource estimates confirm that most of the complexity lies within the routing network operations. Our simulations reveal similar error rate performance for both layered schedules but a slightly lower average iteration count for the horizontal decoder.
We investigate iterative low-resolution message-passing algorithms for quasi-cyclic LDPC codes with horizontal and vertical layered schedules. Coarse quantization and layered scheduling are highly relevant for hardware implementations to reduce the bit width of messages and the number of decoding iterations. As a novelty, this paper compares the two scheduling variants in combination with mutual information maximizing compression operations in variable and check nodes. We evaluate the complexity and error rate performance for various configurations. Dedicated hardware architectures for regular quasi-cyclic LDPC decoders are derived on a conceptual level. The hardware-resource estimates confirm that most of the complexity lies within the routing network operations. Our simulations reveal similar error rate performance for both layered schedules but a slightly lower average iteration count for the horizontal decoder.
We investigate iterative low-resolution message-passing algorithms for quasi-cyclic LDPC codes with horizontal and vertical layered schedules. Coarse quantization and layered scheduling are highly relevant for hardware implementations to reduce the bit width of messages and the number of decoding iterations. As a novelty, this paper compares the two scheduling variants in combination with mutual information maximizing compression operations in variable and check nodes. We evaluate the complexity and error rate performance for various configurations. Dedicated hardware architectures for regular quasi-cyclic LDPC decoders are derived on a conceptual level. The hardware-resource estimates confirm that most of the complexity lies within the routing network operations. Our simulations reveal similar error rate performance for both layered schedules but a slightly lower average iteration count for the horizontal decoder.
In recent years coarsely quantized LDPC decoding using a flooding schedule has been extensively studied. However, there exist few works addressing coarse quantization for a layered schedule, which enables improved convergence speed of the message passing algorithm. The layered schedule can especially be beneficial for high throughput applications like fiber optical systems. This paper presents innovative layered decoding approaches, where the information bottleneck method is used for the design of different coarsely quantized decoder architectures. The varieties of investigated node implementations include lookup tables, computational domain techniques as well as reduced complexity approximations. All structures are designed offline using a layered discrete density evolution method. The performance of multiple node architectures is investigated in terms of evolution of mutual information in the design phase and in terms of error rates. We focus in this paper on regular quasi-cyclic codes. Our simulations running on GPUs also allow insights into the error floor behavior.
Recently, low-resolution LDPC decoders have been introduced that perform mutual information maximizing signal processing. However, the optimal quantization in variable and check nodes requires expensive non-uniform operations. Instead, we propose to use uniform quantization with a simple hardware structure, which reduces the complexity of individual node operations approximately by half and shortens the decoding delay significantly. Our analysis shows that the loss of preserved mutual information resulting from restriction to uniform quantization is very small. Furthermore, the error rate simulations with regular LDPC codes confirm that the uniform quantization causes only minor performance degradation within 0.01 dB compared to the non-uniform alternative. Due to the complexity reduction, especially the proposed 3-bit decoder is a promising candidate to replace 4-bit conventional decoders.
In this paper, we propose a framework of the mutual information-maximizing (MIM) quantized decoding for low-density parity-check (LDPC) codes by using simple mappings and fixed-point additions. Our decoding method is generic in the sense that it can be applied to LDPC codes with arbitrary degree distributions, and can be implemented based on either the belief propagation (BP) algorithm or the min-sum (MS) algorithm. In particular, we propose the MIM density evolution (MIM-DE) to construct the lookup tables (LUTs) for the node updates. The computational complexity and memory requirements are discussed and compared to the LUT decoder variants. For applications with low-latency requirement, we consider the layered schedule to accelerate the convergence speed of decoding quasi-cyclic LDPC codes. In particular, we develop the layered MIM-DE to design the LUTs based on the MS algorithm, leading to the MIM layered quantized MS (MIM-LQMS) decoder. An optimization method is further introduced to reduce the memory requirement for storing the LUTs. Simulation results show that the MIM quantized decoders outperform the state-of-the-art LUT decoders in the waterfall region with both 3-bit and 4-bit precision over the additive white Gaussian noise channels. For small decoding iterations, the MIM quantized decoders also achieve a faster convergence speed compared to the benchmarks. Moreover, the 4-bit MIM-LQMS decoder can approach the error performance of the floating-point layered BP decoder within 0.3 dB in the moderate-to-high SNR regions, over both the AWGN channels and the fast fading channels.
The implementation complexity of the decoder for low-density parity-check codes (LDPC) is dictated by memory and interconnect requirements. We propose new LDPC decoder architectures that reduce the need of message passing memory by 80% (for standard message passing)-55%(for layered decoding) and the router requirements by more than 50%. These novel architectures are based on scheduling of computation that results in "on the fly computation" of variable node and check node reliability messages. These architectures are targeted for quasi- cyclic LDPC codes such as array LDPC codes (regular QC-LDPC) and block LDPC codes (irregular QC-LDPC). FPGA and ASIC implementation results show substantial gains when compared to the existing work in the literature.
This thesis explores hardware implementation of low error floor and high speed low-density parity-check (LDPC) decoders.At first, a novel partially-parallel implementation of a protograph-based quasi-cyclic (QC) LDPC decoder, using a new column-layered message-passing schedule is presented.A new design for serial-input check nodes and switch networks, results in lower hardware complexity while having a higher throughput and comparable latency in comparison with all existing partiallyparallel architectures.Thereafter, we introduce a multi-step scheme for the input quantization of message-passing decoders for LDPC codes.The scheme is based on successive requantization and re-decoding of the input blocks that cause the decoder to be trapped in a trapping set, until the decoding is successful or a maximum number of requantization/re-decodings is reached.The proposed scheme, which is applicable to both regular and irregular codes, lowers the error floor significantly at the cost of small increase in complexity, memory and latency.Furthermore, to facilitate the process of code design and performance evaluation in the error floor region, we design a fast and accurate technique to estimate the error floor of variable-regular LDPC codes under quantized iterative decoding algorithms.This technique, which is based on enumerating the dominant elementary trapping sets of the code, provides significant improvement over existing methods in terms of speed and accuracy.Finally, we examine the harmfulness of trapping sets of variable-regular LDPC codes for soft-decision iterative decoding algorithms.We show that, other than the size of a trapping set, the number of unsatisfied check nodes and the trapping set's topological properties, the position of its subgraph in the Tanner graph of the code can also have an effect on its harmfulness.We also examine dominant trapping sets iii of the quantized min-sum (MS) decoding algorithm and two of its variants (offset-MS and MS with successive relaxation (SR)), for both regular and irregular LDPC codes.We show that the distribution of dominant trapping sets of these algorithms is similar for regular codes and different for irregular codes.Based on these results, we evaluate the error floor performance of a decoder, consisting of MS, offset-MS and SR-MS decoding algorithms working in parallel.First, I would like to thank my supervisor, Professor Amir H. Banihashemi for leading and encouraging me during my research.When I started as his M.A.Sc.student nine years ago, my dream was to acquire a set of skills.Amir helped me to achieve them with invaluable advice and excellent guidance.I would also like to thank M. Samy Hosny, the CEO of SiloconPro Inc. for supporting my research and providing me with his professional experience.I can not express my appreciation to my wonderful wife