Coding Theory

Our research explores the relations among coding theory, information theory, and related areas of computer science and mathematics. In error control coding, our team is concerned with the design, performance analysis and decoding of efficient modern error control systems such as wavelet codes, rateless codes, low density parity check codes (LDPC) and other types of iterative coding schemes. We are particularly interested in coding techniques for erasure channels, unequal error protecting codes, rate compatible codes, nonuniform codes, and two-dimensional codes for digital communication/storage systems and wireless ad hoc networks.

 

 

Improve decoding algorithms for LDPC codes The performance of LDPC codes using the message passing algorithm over the binary erasure channel BEC has been extensively studied. Over BEC, it is well known that the iterative message passing algorithm stops if the set of erasures in the received codeword contains a stopping set although it may be the case that ML decoding may succeed in recovering the information bits completely. We note that even though the message passing algorithm is inferior to the ML decoding, it is practical and is a linear time algorithm. Interestingly, it can be noted that one can attribute to the set of parity check equations that a linear block code satisfies, an "abstract" vector space structure over the same field as that of the code. Therefore, if a received codeword is ML-decodable but not decodable by iterative message passing algorithm; thus, after the iterative decoder halts, there exists a set of parity check equations using which we can recover all the bits in the stopping set. Although we have not proved this yet, the structure of the stopping set is such that the knowledge of few unknown bits is enough to always complete the decoding if a received codeword is ML-decodable. Therefore, it may be possible to improve the performance if we can improve the standard message passing algorithm. This is particulary important for the short-length LDPC codes for which a good optimization methodology is lacking. We consider the improved decoding for both BEC and other memoryless binary input output symmetric channels (MBIOS). The intention is to analyze graph theoretic classification of stopping sets to evaluate the gain in performance with these algorithms. This characterization will eliminate the usage of simulations in the previously improved algorithms, making these viable for algorithmic implementation. We propose to prove that these algorithms are fast and have the same order of complexity as that of the standard message-passing