Study of complex networks has been conducted across many fields of science, including computer networks, biological networks and social networks. Characteristics of different types of complex networks such as random networks, regular-coupled networks, small-world networks and scale-free networks have been discovered by researchers. Application of such network properties to solve engineering problems, however, is still at the infancy stage. In this study, we make one of the first attempts in applying complex network theories to communications engineering. In particular, inspired by the shortest-average-path-length property of scale-free networks, we design short-length low-density-parity-check (LDPC) codes with an aim to shortening the average distance between any two variable nodes. We will also compare the error performance, both theoretically and by simulations, of the proposed codes with those of other well-known LDPC codes.
Study of complex networks has been conducted across many fields of science, including computer networks, biological networks and social networks. Characteristics of different types of complex networks such as random networks, regular-coupled networks, small-world networks and scale-free networks have been discovered by researchers. Application of such network properties to solve engineering problems, however, is still at the infancy stage. In this study, we make one of the first attempts in applying complex network theories to communications engineering. In particular, inspired by the shortest-average-path-length property of scale-free networks, we design short-length low-density-parity-check (LDPC) codes with an aim to shortening the average distance between any two variable nodes. We will also compare the error performance, both theoretically and by simulations, of the proposed codes with those of other well-known LDPC codes.
Short-length codes may play a crucial role in delay-sensitive scenarios. Low-density parity-check (LDPC) codes, as a class of Shannon limit approaching codes, perform well with long code length. However, the design of short-length LDPC codes with good performance is still challenging. This paper investigates the construction of short-length LDPC codes based on the combinatorial design theory. Specifically, Kirkman triple systems (KTS), as a type of balanced incomplete block design (BIBD) techniques, are used to construct the parity-check matrices of LDPC codes, which are guaranteed to be 4-cycles free. Some other properties of such designed LDPC codes are also investigated. For instance, a lower bound on the girth, the code rate and minimum code distance. The simulation results show that the designed short-length LDPC codes based on KTS outperform that of randomly constructed ones.
Low-density parity-check (LDPC) codes can approach the Shannon limit performance closely, and are becoming one of the most promising channel codes in the Error Control Coding area.The performance of an LDPC code with given length is mainly affected by the sizes of some combinatorial characteristics of its corresponding bipartite graph and the distribution of variable degrees and check node degrees.With the help of the density evolution algorithm, randomly designed LDPC codes, with carefully chosen degree distribution pairs, have been shown to achieve better Shannon capacity performance than their regular counterparts when decoded using the iterative belief propagation (BP) decoding algorithm.However, regular LDPC codes outperform their irregular counterparts in term of their error floors.Therefore, construction of LDPC codes which have both attractive error rate performance and low error floor performance has become an attractive topic.Currently, optimization of variable node degree distribution and check node degree distribution for an LDPC code with given length, which could help the code to achieve good Shannon limit performance, has been extensively studied.In this dissertation, we demonstrate some approaches of improving the error floor performance for a given LDPC code with desired degree distribution pair.The contribution mainly includes three parts.In the first part, the relationship between cycles and unfavorable combinatorial
Abstract Recent breakthroughs in forward error correction, in the form of low-density parity-check(LDPC) and turbo codes, have seen the promise of near Shannon limit information trans-mission realised. The deterministic construction of good codes, for LDPC codes in par-ticular, is currently the subject of intense interest in the research and development com-munity. This thesis adds to this field, developing methods and supporting theory for thedesign of algebraic LDPC codes using incidence structures from combinatorial designs.The benefits of this approach are guaranteed code properties, parameter flexibility, easeof implementation and reduced encoding complexity.In the first part of this thesis Steiner 2-designs and partial geometries are used toprovide systematic constructions of regular LDPC codes with Tanner graphs free of 4-cyclesandwithdeterministiccodeproperties. Drawingextensivelyfromexistingincidencestructures we present new families of algebraic LDPC codes with benefits over traditionalrandomly constructed regular codes, particularly where small-to-medium length codes areconcerned. We focus in particular on exploring the effect of different design propertieson the code parameters by deriving the rate, minimum distance, girth, and stopping setdistribution of LDPC codes from designs.In the second part of this thesis resolvable designs are employed to create regularLDPC codes free of 4-cycles with the parameter flexibility and decoding performance ofrandomly constructed regular LDPC codes. Employing resolvability greatly extends theclass of LDPC codes that can be algebraically constructed. These codes can offer sig-nificant implementation advantages due to the deterministic structure of their resolutionclasses and in some cases their simple encoding.A shortcoming of LDPC codes is their potentially high encoding complexity, whichis generally quadratic in the code length. Finding computationally efficient encodersis therefore critical for LDPC codes to be considered as serious contenders for futuregenerations of forward error correction devices. As a result the purpose of the last part ofthis thesis is to design codes which have the graph-based properties necessary to performwell with sum-product decoding but which are also cyclic or quasi-cyclic and so can beencoded simply. The main focus is regular codes but we also extend our constructionof quasi-cyclic codes to produce irregular LDPC codes with simple linear-time encodingcircuits.
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.
Recent advances in coding theory have uncovered the previously forgotten power of Low-Density Parity-Check (LDPC) codes. Their popularity can be related to their relatively simple iterative decoders and their potential to achieve high performance close to shannon limit. These make them an attractive candidate for error correcting application in communication systems. In this thesis, we focus our research on the iterative decoding algorithms for Low-Density Parity-Check codes and present an improved decoding algorithm. First, the graph structure of LDPC codes is studied and a graph-based search algorithm to find the shortest closed walk and shortest cycle for each node of the graph is proposed. Then, the Deterministic schedule is applied on nodes of the graph with the objective of preserving the optimality of the algorithms. Finally, Hybrid Switch-Type technique is applied on the improved algorithms to provide a desirable complexity/performance trade-off. Hybrid Technique and Deterministic schedule are combined for decoding regular and irregular LDPC codes. The performance and complexity of the decoder is studied for Sum-Product and Gallager A algorithms. The result is a flexible decoder for any available LDPC code and any combination of decoding algorithms based on the communication systems need. In this technique, we benefit the high performance of soft-decision algorithms and low complexity of hard-decision algorithms by changing the decoding rule after a few iterations. Hence, a desirable performance can be obtained with less average number of soft iterations. Moreover, all the nodes do not update messages in each iteration. As a result, the total number of computations is reduced considerably
It is well known that extremely long low-density parity-check (LDPC) codes perform exceptionally well for error correction applications, short-length codes are preferable in practical applications. However, short-length LDPC codes suffer from performance degradation owing to graph-based impairments such as short cycles, trapping sets and stopping sets and so on in the bipartite graph of the LDPC matrix. In particular, performance degradation at moderate to high Eb/N0 is caused by the oscillations in bit node a posteriori probabilities induced by short cycles and trapping sets in bipartite graphs. In this study, a computationally efficient algorithm is proposed to improve the performance of short-length LDPC codes at moderate to high Eb/N0. This algorithm makes use of the information generated by the belief propagation (BP) algorithm in previous iterations before a decoding failure occurs. Using this information, a reliability-based estimation is performed on each bit node to supplement the BP algorithm. The proposed algorithm gives an appreciable coding gain as compared with BP decoding for LDPC codes of a code rate equal to or less than 1/2 rate coding. The coding gains are modest to significant in the case of optimised (for bipartite graph conditioning) regular LDPC codes, whereas the coding gains are huge in the case of unoptimised codes. Hence, this algorithm is useful for relaxing some stringent constraints on the graphical structure of the LDPC code and for developing hardware-friendly designs.