The use of rate-compatible error correcting codes offers several advantages as compared to the use of fixed-rate codes: a smooth adaptation to the channel conditions, the possibility of incremental Hybrid ARQ schemes, as well as sharing of the encoder and decoder implementations between the codes of different rates. In this paper, the implementation of a decoder for rate-compatible quasi-cyclic LDPC codes is considered. Assuming the use of a code ensemble obtained through puncturing of a low-rate mother code, the decoder achieves significantly reduced convergence rates by merging the check node neighbours of the punctured variable nodes. The architecture uses the minsum algorithm with serial node processing elements to efficiently handle the wide spread of node degrees that results from the merging of the check nodes.
The use of rate-compatible error correcting codes offers several advantages as compared to the use of fixed-rate codes: a smooth adaptation to the channel conditions, the possibility of incremental Hybrid ARQ schemes, as well as sharing of the encoder and decoder implementations between the codes of different rates. In this paper, the implementation of a decoder for rate-compatible quasi-cyclic LDPC codes is considered. Assuming the use of a code ensemble obtained through puncturing of a low-rate mother code, the decoder achieves significantly reduced convergence rates by merging the check node neighbours of the punctured variable nodes. The architecture uses the minsum algorithm with serial node processing elements to efficiently handle the wide spread of node degrees that results from the merging of the check nodes.
The use of rate-compatible error correcting codes offers several advantages as compared to the use of fixed-rate codes: a smooth adaptation to the channel conditions, the possibility of incremental Hybrid ARQ schemes, as well as simplified code representations in the encoder and decoder. In this paper, the implementation of a decoder for rate-compatible quasi-cyclic LDPC codes is considered. The decoder uses check node merging to increase the convergence speed of the algorithm. Check node merging allows the decoder to achieve the same performance with a significantly lower number of iterations, thereby increasing the throughput. The feasibility of a check node merging decoder is investigated for codes from IEEE 802.16e and IEEE 802.11n. The faster convergence rate of the check node merging algorithm allows the decoder to be implemented using lower parallelization factors, thereby reducing the logic complexity. The designs have been synthesized to an Altera Cyclone II FPGA, and results show significant increases in throughput at high SNR.
In this paper, we present a rate-compatible LDPC decoder architecture which supports code rates between the rate of the mother code and 1. The rate-1/2 2304-bit Quasi-Cyclic (QC) LDPC codes with dual-diagonal parity check structure is selected from WiMax standard as the mother code and is punctured using specific puncturing patterns to obtain arbitrary rates. Parallel layered decoding architecture (PLDA) is employed to reduce chip area and improve the throughput. Simulation results show that the proposed punctured codes have comparable error correcting performances with the performances of dedicated codes from WiMax standard. The decoder is implemented on the platform of Xilinx XC2V8000. Compared with previous WiMax LDPC decoders synthesized by the same device, our low-complexity decoder consumes less FPGA resources: reduction of slices by 63%, flip-flops by 73%, look-up tables (LUTs) by 60% and RAMs by 30%.
We construct a protograph-based rate-compatible family of low-density parity-check (LDPC) codes that cover a very wide range of rates from 1/2 to 16/17, perform within about 0.5 dB of their capacity limits for all rates, and can be decoded conveniently and efficiently with a common hardware implementation. In contrast to alternative methods that create codes of different rates by puncturing, shortening, or expurgation, our method uses a combination of expurgation and lengthening (equivalent to an unusual extension) to produce lower-rate codes. Advantages compared to the alternative methods include roughly uniform utilization of common family decoder hardware for different rates, implementation with uniformly low maximum check node degrees despite high maximum rate, and a large fixed portion of the protograph that can be labeled with a fixed set of edge permutations for all rates. We apply this method to create a rate-compatible code family anchored by a particular code of (nominal) rate 7/8 and length n = 8176 designed by Kou, Lin and Fossorier [1] whose edge permutations are determined by Euclidean geometries (EG). All members of our family retain all of the EG-designed edges and circulant permutations of this anchor code, and this helps to avoid weak spots in the code graph that usually arise when edge permutations are assigned by greedy algorithms. There are also varying numbers of auxiliary and ancillary checks, variables, and edges, allowing realization of different rates, with fixed (nominal) dimension k = 8176 for all rates. Simulations show that all members of this family achieve steeply falling error rate curves without detectable error floors, at least to codeword error rates of about 10-6
In this paper, families of rate-compatible protograph-based LDPC codes that are suitable for incrementalredundancy hybrid ARQ applications are constructed. A systematic technique to construct low-rate base codes from a higher rate code is presented. The base codes are designed to be robust against erasures while having a good performance on error channels. A progressive node puncturing algorithm is devised to construct a family of higher rate codes from the base code. The performance of this puncturing algorithm is compared to other puncturing schemes. Using the techniques in this paper, one can construct a rate-compatible family of codes with rates ranging from 0.1 to 0.9 that are within 1 dB from the channel capacity and have good error floors.
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.
While rate-compatible punctured low-density parity-check (RCP-LDPC) codes offer high flexibility in terms of code rate at a relatively low cost in implementation complexity, they are reported to require more decoding iterations than unpunctured LDPC codes. In this paper1we consider layered belief propagation decoding and propose efficient check node layering that significantly accelerates the decoding convergence of RCP-LDPC codes. We show that the proposed layering outperforms both random layering and conventional BP decoding. The performance improvements become more distinctive at high rates and they come at no additional implementation cost.