Research On Low-Density Erasure Codes And Trellis Complexity

Cascaded low-density erasure codes are based on sparse random bipartite graphs. Very efficient linear time encoding and erasure recover algorithms with the arbitrarily near erasure channel capacity performance of the codes with respect to the algorithms have made them one of the most optimal coding techniques up to now. It is pointed out that the design of sequences of degree distribution in bipartite graphs is one of the most important problems in constructing low-density erasure codes. In this dissertation, emphasis is put on making a detailed study of theoretical problems on design methods, thresholds and analytical properties of sequences of degree distribution for low-density erasure codes. Some positive results on the above problems are obtained and summarized as follow:1. The decoding ideas of low-density parity-check codes on graphs are systematically summarized. Erasure codes which belong to standard classes of RS codes and their erasure correcting principles are introduced with emphasis on cascaded low-density erasure codes with linear time encoding and erasure recover algorithms. The encoding and decoding complexities of these codes are analyzed.2. Two results are presented on the maximum tolerable loss fraction, i.e. threshold, for regular low-density erasure codes. Thresholds of regular degree distributions are analyzed. It is shown that low-density erasure codes based on (d,2d) -regular sequences of degree distribution are not close to optimal (d > 3).3. Improved right regular sequences of low-density erasure codes are presented, and it is testified that the sequences are asymptotically quasi-optimal. In the meantime, simulations of cascaded low-density erasure codes based on a few types of special sequences of degree distribution available are given, together with performance analyses on these codes.4. Based on the known principle of fixed points in mathematical analysis, a sufficient convergence condition of the erasure recover algorithm for low-density erasure codes is shown.5. Heavy-Tail/Poisson and right-regular sequences are analyzed in detail and a new method for designing the two classes of sequences above is presented. By introducing a basis of monotonically decreasing and continuous function, a new theory of general design of degree distribution is proposed, and its corresponding design method is given.6. Sequences of degree distribution for low-density erasure codes are investigated.Some analytical properties of the Heavy-Tail/Poisson sequences, right-regular sequences and general capacity-achieving sequences for low-density erasure codes are shown.7. Absolute minimal trellis complexities of extended codes and their dual codes of two types of linear block codes whose code length is odd are given. From these conclusions some results are obtained on absolute minimal trellis complexities of extended primitive BCH codes and their dual codes of primitive BCH codes.