arXiv:2210.03537 · FITCE Congress

Punctured Binary Simplex Codes as LDPC codes

Massimo Battaglioni, Giovanni Cancellieri

Published Sep 29, 2022• 7 citations

Abstract

Digital data transfer can be protected by means of suitable error correcting codes. Among the families of state-of-the-art codes, LDPC (Low Density Parity-Check) codes have received a great deal of attention recently, because of their performance and flexibility of operation, in wireless and mobile radio channels, as well as in cable transmission systems. In this paper, we present a class of rate-adaptive LDPC codes, obtained as properly punctured simplex codes. These codes allow for the use of an efficient soft-decision decoding algorithm, provided that a condition called row-column constraint is satisfied. This condition is tested on small-length codes, and then extended to medium-length codes. The puncturing operations we apply do not influence the satisfaction of the row-column constraint, assuring that a wide range of code rates can be obtained. We can reach code rates remarkably higher than those obtainable by the original simplex code, and the price in terms of minimum distance turns out to be relatively small, leading to interesting trade-offs in the resulting asymptotic coding gain.

DOI: 10.23919/fitce56290.2022.9934548

Related papers

Rate-Adaptive LDPC Codes Obtained from Simplex Codes

Massimo Battaglioni, Marco Baldi, Franco Chiaraluce +1 more

In this paper we show that, when a binary primitive polynomial can be associated to a sparse Golomb ruler, the simplex code obtained by taking it as the code parity-check polynomial exhibits good distance properties and performance. We define some conditions under which the obtained codes are also Low-Density Parity-Check (LDPC) codes, and can hence be decoded through efficient iterative algorithms. We perform code puncturing, leading to a family of rate-adaptive codes, and we predict some of their structural properties in terms of minimum distance and weight distribution. We show that, in addition to having some useful properties, these codes achieve good performance in terms of error rate under LDPC decoding.

International Conference on CommunicationsMay 28, 20236 citations

Design and Analysis of a Family of Complexity-Constrained LDPC Codes

Massimo Battaglioni, Matteo Amagliani, Marco Baldi +2 more

In this paper we study a special family of Low-Density Parity-Check (LDPC) codes, called Primitive Rate-Compatible (PRC) LDPC codes, obtained by applying puncturing to some properly chosen simplex codes. We investigate their minimum distance properties and give insights on the design of PRC-LDPC codes for use in scenarios where constraints on hardware and software resources require maintaining a low level of complexity. We numerically assess the error rate performance of these codes in such a setting, showing that they also demonstrate good performance under belief propagation decoding, in addition to low decoding complexity.

IEEE International Symposium on Information Theory (ISIT)Jul 7, 20242 citations

Rate-Compatible LDPC Codes Based on Primitive Polynomials and Golomb Rulers

Massimo Battaglioni, Marco Baldi, Franco Chiaraluce +1 more

We introduce and study a family of rate-compatible Low-Density Parity-Check (LDPC) codes. The design of these codes starts from simplex codes, defined by parity-check matrices having a simple form stemming from the coefficients of a primitive polynomial. For this reason, we call the new codes Primitive Rate-Compatible LDPC (PRC-LDPC) codes. By applying puncturing to these codes, we obtain a bit-level granularity of the code rate. We show that, in order to achieve good LDPC codes, the underlying polynomials, besides being primitive, must meet some more stringent conditions with respect to those of classical punctured simplex codes. We leverage non-modular Golomb rulers to take these new requirements into account. We characterize the minimum distance properties of PRC-LDPC codes, and study and discuss their encoding and decoding complexity. Finally, we assess the error rate performance of high rate PRC-LDPC codes under iterative decoding.

arXiv:2309.14917IEEE Transactions on CommunicationsJun 17, 20249 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

Construction of Optimal Puncturing of Low-Density Parity-Check Codes

S. Suresh Kumar, Manju Rajaram

Low-density parity-check with Length-compatible and low error floors (LDPC-LCLEF) on the binary symmetric channel is presented in this paper. These codes can support a wide range of lengths for a given rate and also the Tanner graphs are free of small trapping sets. This can be obtained by applying the schemes of shortening and puncturing to good LDPC codes and the trapping sets are selected using the trapping set ontology based on their relative harmfulness for the given decoding algorithm. The conventional approach does not guarantee to have a good performance as the degree distributions may be wildly varied. In this paper, a modified algorithm is presented to generate LDPC codes of a given rate with almost their degree distributions are same as the mother code degree distribution. Also the relative harmfulness for different trapping sets are evaluated and decoding failures of one trapping set in presence or absence of other trapping sets are analyzed. To facilitate this discussion, a new description of structured LDPC codes with arrays of permutation matrices as parity-check matrices is given. Numerical results show that the LDPC code constructed by this approach performed much better than the conventional approach.

CiiT international journal of fuzzy systemsJan 1, 20140 citations

Results on Punctured Low-Density Parity-Check Codes and Improved Iterative Decoding Techniques

Hossein Pishro-Nik, Faramarz Fekri

This paper first introduces an improved decoding algorithm for low-density parity-check (LDPC) codes over binary-input-output-symmetric memoryless channels. Then some fundamental properties of punctured LDPC codes are presented. It is proved that for any ensemble of LDPC codes, there exists a puncturing threshold. It is then proved that for any rates R1and R2satisfying 0121to R2resulting in asymptotically good codes for all rates R1lesRlesR2. Specifically, this implies that rates arbitrarily close to one are achievable via puncturing. Bounds on the performance of punctured LDPC codes are also presented. It is also shown that punctured LDPC codes are as good as ordinary LDPC codes. For BEC and arbitrary positive numbers R121lesRlesR2is shown. Based on the above observations, a method is proposed to design good punctured LDPC codes over a broad range of rates. Finally, it is shown that the results of this paper may be used for the proof of the existence of the capacity-achieving LDPC codes over binary-input-output-symmetric memoryless channels

IEEE Transactions on Information TheoryJan 23, 2007100 citations