Transactions of Beijing Institute of Technology

Constructing of LDPC Code with High Speed Parallel Decoding Structure

AN Jian-ping

Published Jan 1, 2010• 0 citations

Abstract

A method for constructing low-density parity-check (LDPC)code that can be implemented with high speed parallel decoding structure is proposed.Firstly,aparity-check matrix is generated with algebraic method.The short circles in the matrix can be eliminated by selecting proper parameters,so that the generated code has good performance.Then rearrange the rows of the generated parity-check matrix with specific rules to make the rearranged matrix has block structure.With the block structure,the partial parallel decoding of LDPC code can be realized in engineering,and a lot of resources can be saved.The simulation results show that the performance of constructed LDPC code is also very good and is equal to the random code.

Related papers

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 parallelized-decoding LDPC codes

Tsung-Che Wu, Chang‐Ming Lee, Cheng-Kuei Wang

In the parallelization for high-throughput applications, the number of independent memory access usually dominates the coding throughput. Moreover, a class of large-girth low-density parity check (LDPC) codes usually has difficulties to realize the parallelization in the decoder. To cope with these obstacles, we propose an efficient code construction to take the number of required parallel decoding unit and the large-girth constraint into considerations at once. First, the parity check matrix would be split into the block-wise structure to fit the parallelization in the decoder. Second, the conversion of the cycle-checking inequalities can transform the girth issue into a linear system. Finally, based on the decomposition of the polyhedral set, the Smith normal form can efficiently solve inequalities of the proposed system. Simulation results show that the proposed code construction can satisfy the requirements of parallelization and high-performance coding with girth g = 12.

IEEE International Symposium on Circuits and Systems proceedingsMay 1, 20161 citation

A Novel Quasi-Cyclic LDPC Codes Construction Method for High-Speed Parallel Decoding

Ming Ke Dong, Wang Da, Ya Dan Zheng +2 more

The decoding parallelism of quasi-cyclic low density parity check (QC-LDPC) codes, an important realization factor of LDPC codes, is limited by the block size. Joint row-column (JRC) decoding algorithm, an efficient decoding technique having low computation cost and small iteration number, also suffers from the decoding parallelism limitation in QC-LDPC application. In this paper, a novel LDPC-code construction method is presented and validated. This method constructs the row sets to eliminate the data access conflicts, and it clearly enhances the decoding parallelism while avoids any degradation of bit error rate (BER) performance.

Applied Mechanics and MaterialsAug 1, 20130 citations

Recursive construction of LDPC codes

Shunliang Mei

To reduce the cycles in the Tanner graph which may affect the code performance,a recursive method to construct low-density parity-check(LDPC) codes was proposed.The method used a parity-check matrix of a short LDPC code as its mother matrix upon which a long code was constructed with circulant permutation matrices.By choosing the circulant permutation matrix parameters properly,the number of cycles having a given length in the Tanner graph of the constructed long codes were equal to or less than that of the short code.Either regular or irregular LDPC codes were constructed.Simulation results show that the LDPC codes constructed by this method have very low error-floor and almost no performance degradation due to their special structure as compared with random LDPC codes.

Journal of Tsinghua University(Science and Technology)Jan 1, 20070 citations

Efficient Design of Structured LDPC Codes

Biwoong Chung, Joon-Sung Kim, Song Hong-Yeop

The high encoding complexity of LDPC codes can be solved by designing structured parity-check matrix. If the parity-check matrix of LDPC codes is composed of same type of blocks, decoder implementation can be simple, this structure allow structured decoding and required memory for storing the parity-check matrix can be reduced largely. In this paper, we propose a construction algorithm for short block length structured LDPC codes based on girth condition, PEG algorithm and variable node connectivity. The code designed by this algorithm shows similar performance to other codes without structured constraint in low SNR and better performance in high SNR than those by simulation

한국통신학회논문지Jan 1, 20062 citations

Regular LDPC Code Construction and Partly Parallel Decoder Design

Xizheng Zhang

Recently,LDPC(Low Density Parity Check) codes have attracted a lot of attention.However,because of the lack of efficient decoder hardware design approaches,the real-world applications of LDPC codes are limited.In this paper,it presents a joint code and decoder design approach to construct a class of(j,k) regular LDPC codes that not only have good error-correcting performance but also have high-speed partly parallel decoder.

Journal of Hunan Institute of EngineeringJan 1, 20070 citations