IEEE International Symposium on Circuits and Systems proceedings

Symmetric split-row LDPC decoders

Mohammad Shahrad, Mahdi Shabany

Published May 1, 2017• 1 citation

Abstract

LDPC codes are deployed in many modern wired and wireless communication systems. While fully-parallel LDPC decoders are very efficient, they typically suffer from routing complexity. The Split-Row method effectively reduces this complexity with a minor performance loss. This paper shows the importance of symmetry in Split-Row architectures and proves that the implementation of Split-Row decoders based on new proposed smart column-permuted versions of parity check matrices leads to a better error performance as well as a more efficient hardware. Moreover, in order to achieve optimized column-permuted parity check matrices, a heuristic approach is proposed. This method is then generalized to support QC-LDPC codes. Applied to IEEE 802.3an (10GBASE-T Ethernet) and IEEE 802.11n (Wi-Fi) LDPC decoders, the new technique improves the error performance, while leading to almost 3× speed-up in the synthesis compile time and about 10% reduction in the critical path.

DOI: 10.1109/iscas.2017.8050909

Related papers

Efficient column-layered decoders for single block-row quasi-cyclic LDPC codes

Chuan Zhang, Xiaohu You, Zhongfeng Wang

The recently proposed single block-row quasi-cyclic low-density parity-check (QC-LDPC) codes are favorable for high-speed applications. However, conventional decoder design methods are not suitable for this kind of codes. To tackle this issue, this paper aims at designing efficient column-layered single block-row QC-LDPC decoder architecture without affecting the decoding performance. Moreover, the simplified version which only requires single minimum value is also proposed for further hardware reduction. Results show that, for the rate-0.9006 (1640, 1477) single block-row QC-LDPC code, the proposed two designs achieves significant advantages in both hardware and latency over their row-layered counterpart.

IEEE International Symposium on Circuits and Systems proceedingsJun 1, 20142 citations

Implementation of a Flexible LDPC Decoder

Guido Masera, Federico Quaglio, F. Vacca

Low-density parity-check codes (LDPC) are among the most powerful error correcting tools today available. For this reason they became very popular in several applications such as the digital satellite broadcasting system (DVB-S2), wireless local area network (IEEE 802.11n) and metropolitan area network (802.16e). Whereas several code-specific decoders have been proposed in the literature, the implementation of a high performance yet flexible LDPC decoder still is a challenging topic. This work presents a novel formulation of the decoding algorithm that strongly simplifies internal communication requirements and enables the development of decoders supporting generally defined LDPC codes. The resulting architecture is tailored to decode both IEEE 802.11n and IEEE 802.16e LDPC codes, as well as any other code of comparable complexity. The implementation cost deriving from the full flexibility offered by the proposed approach is also evaluated.

IEEE Transactions on Circuits and Systems II Analog and Digital Signal ProcessingJun 1, 2007124 citations

Scheduling Algorithm for Partially Parallel Architecture of LDPC Decoder by Matrix Permutation

In‐Cheol Park, Se-Hyeon Kang

The fully parallel LDPC decoding architecture can achieve high decoding throughput, but it suffers from large hardware complexity caused by a large set of processing units (PUs) and complex interconnections. A practical solution of area-efficient decoders is to use the partially parallel architecture in which a PU is shared for several rows or columns. It is important in the partially parallel architecture to determine the rows or columns to be processed in a PU and their processing order. The dependencies between rows and columns should be considered to minimize the overall processing time by overlapping the decoding operations. This paper proposes an efficient scheduling algorithm that can be applied to general LDPC codes, which is based on the concept of matrix permutation. Experimental results show that the proposed scheduling achieves a higher decoding rate, leading to a reduction of 25% processing time on average. A 1024-bit rate-1/2 LDPC decoder, employing the proposed scheduling algorithm, provides almost 1 Gbps decoding throughput and occupies one-fifth the area compared to the fully parallel decoder.

IEEE International Symposium on Circuits and Systems proceedingsJul 27, 200527 citations

Reduced Complexity of Decoding Algorithm for Irregular LDPC Codes Using a Split Row Method

Rachid El Alami, Mostafa Mrabti, Cheikh Bamba Gueye

In this paper, we have proposed a novel method of decoding algorithm of irregular LDPC codes. A reduced complexity LDPC decoding method for regular LDPC code is extended to irregular LDPC codes. We present in this paper a full description of this method and its benefits for various row weight and length code word. The Split-Row method makes column processing parallelism easier to exploit and significantly simplifies row processors. Recently, irregular LDPC codes have received a lot of attention by many advanced standard, such as WiFi, WiMAX Mobile and digital video broadcasting (DVB-S2). Hence the idea to develop the “Split-Row Method” for irregular LDPC codes. In this context, we have performed an implementation on MATLAB of an irregular LDPC codes with different code word and code rate; simulation results over an additive white Gaussian channel show that the error performance of high row-weight codes with Split-Row decoding is within 0.3–0.5 dB of the Min-Sum algorithm. The study result shows that the “Split Row Method” is better for irregular code than regular LDPC codes.

Journal of Wireless Networking and CommunicationsAug 31, 20125 citations

Low-Density Parity-Check Codes: Construction and Implementation

Gabofetswe Malema

Low-density parity-check (LDPC) codes have been shown to have good error correcting performance approaching Shannon’s limit. Good error correcting performance enables efficient and reliable communication. However, a LDPC code decoding algorithm needs to be executed efficiently to meet cost, time, power and bandwidth requirements of target applications. The constructed codes should also meet error rate performance requirements of those applications. Since their rediscovery, there has been much research work on LDPC code construction and implementation. LDPC codes can be designed over a wide space with parameters such as girth, rate and length. There is no unique method of constructing LDPC codes. Existing construction methods are limited in some way in producing good error correcting performing and easily implementable codes for a given rate and length. There is a need to develop methods of constructing codes over a wide range of rates and lengths with good performance and ease of hardware implementability. LDPC code hardware design and implementation depend on the structure of target LDPC code and is also as varied as LDPC matrix designs and constructions. There are several factors to be considered including decoding algorithm computations,processing nodes interconnection network, number of processing nodes, amount of memory, number of quantization bits and decoding delay. All of these issues can be handled in several different ways. \nThis thesis is about construction of LDPC codes and their hardware implementation. LDPC code construction and implementation issues mentioned above are too many to be addressed in one thesis. The main contribution of this thesis is the development of LDPC code construction methods for some classes of structured LDPC codes and techniques for reducing decoding time. We introduce two main methods for constructing structured codes. In the first method, column-weight two LDPC codes are derived from distance graphs. A wide range of girths, rates and lengths are obtained compared to existing methods. The performance and implementation complexity of obtained codes depends on the structure of their corresponding distance graphs. In the second method, a search algorithm based on bit-filing and progressive-edge growth algorithms is introduced for constructing quasi-cyclic LDPC codes. The algorithm can be used to form a distance or Tanner graph of a code. This method could also obtain codes over a wide range of parameters. Cycles of length four are avoided by observing the row-column constraint. \nRow-column connections observing this condition are searched sequentially or randomly. Although the girth conditions are not sufficient beyond six, larger girths codes were easily obtained especially at low rates. The advantage of this algorithm compared to other methods is its flexibility. It could be used to construct codes for a given rate and length with girths of at least six for any sub-matrix configuration or rearrangement. The code size is also easily varied by increasing or decreasing sub-matrix size. Codes obtained using a sequential search criteria show poor performance at low girths (6 and 8) while random searches result in good performing codes. \nQuasi-cyclic codes could be implemented in a variety of decoder architectures. One of the many options is the choice of processing nodes interconnect. We show how quasi-cyclic codes processing could be scheduled through a multistage network. Although these net-works have more delay than other modes of communication, they offer more flexibility at a reasonable cost. Banyan and Benes networks are suggested as the most suitable networks. \nDecoding delay is also one of several issues considered in decoder design and implementation. In this thesis, we overlap check and variable node computations to reduce decoding time. Three techniques are discussed, two of which are introduced in this thesis. The techniques are code matrix permutation, matrix space restriction and sub-matrix row-column scheduling. Matrix permutation rearranges the parity-check matrix such that rows and columns that do not have connections in common are separated. This techniques can be applied to any matrix. Its effectiveness largely depends on the structure of the code. We show that its success also depends on the size of row and column weights. Matrix space restriction is another technique that can be applied to any code and has fixed reduction in time or amount of overlap. Its success depends on the amount of restriction and may be traded with performance loss. The third technique already suggested in literature relies on the internal cyclic structure of sub-matrices to achieve overlapping. The technique is limited to LDPC code matrices in which the number of sub-matrices is equal to row and column weights. We show that it can be applied to other codes with a lager number of sub-matrices than code weights. However, in this case maximum overlap is not guaranteed. We calculate the lower bound on the amount of overlapping. Overlapping could be applied to any sub-matrix configuration of quasi-cyclic codes by arbitrarily choosing \nthe starting rows for processing. Overlapping decoding time depends on inter-iteration waiting times. We show that there are upper bounds on waiting times which depend on the code weights. Waiting times could be further reduced by restricting shifts in identity sub-matrices or using smaller sub-matrices. This overlapping technique can reduce the decoding time by up to 50% compared to conventional message and computation scheduling. \nTechniques of matrix permutation and space restriction results in decoder architectures that are flexible in LDPC code design in terms of code weights and size. This is due to the fact that with these techniques, rows and columns are processed in sequential order to achieve overlapping. However, in the existing technique, all sub-matrices have to be processed in parallel to achieve overlapping. Parallel processing of all code sub-matrices requires the architecture to have the number of processing units at least equal to the number sub-matrices. Processing units and memory space should therefore be distributed among the sub-matrices according to the sub-matrices arrangement. This leads to high complexity or inflexibility in the decoder architecture. We propose a simple, programmable and high throughput decoder architecture based on matrix permutation and space restriction techniques.

Jan 1, 200724 citations

Reduced complexity of decoding algorithm for irregular LDPC codes using Split Row method

Rachid El Alami, Cheikh Bamba Gueye, Mostafa Mrabti +2 more

A reduced complexity LDPC decoding method for regular LDPC code is extended to irregular LDPC codes; we present in this paper a full description of this method and its benefits for various row weight and length code word. The Split-Row method makes column processing parallelism easier to exploit and significantly simplifies row processors. Simulation results over an additive white Gaussian channel show that the error performance of high row-weight codes with Split-Row decoding is within 0.3-0.5 dB of the Min-Sum algorithm.

Apr 1, 20118 citations