Algebraic analysis of parity check codes and iterative decoding

点击翻译按钮获取中文摘要

ABSTRACTPrincipal Investigator: Matthews, Gretchen L. Proposal Number: DMS - 0901693Institution: Clemson UniversityTitle: Algebraic analysis of parity check codes and iterative decodingThis grant was supported in part by the EPSCoR program.The investigator studies applications of algebraic structures to coding theory. This project focuses on iterative decoding algorithms for codes defined by parity check matrices, especially low-density parity check codes which are defined by sparse matrices. While such codes paired with iterative message-passing algorithms for decoding may achieve near-capacity performance, these observations are based primarily on simulations and randomization. An algebraic understanding of this performance would circumvent the need for randomization, a process which invites the possibility of poor error-correcting capability and impedes the encoding process. This project aims to explain and then exploit the performance capabilities of codes based on sparse matrices. In particular, the investigator aims to identify algebraic structures that lead to decoding failure and characterize those most likely to do so. Desirable outgrowths of this line of inquiry are how to best represent a linear code and how to select a parity check matrix for a given code and decoding algorithm. Even though the (current) practical implementation of parity check codes is reasonable only for those codes defined by sparse matrices, the theoretical study applies to any linear code and may provide insight beyond low-density parity check codes.Error-correcting codes ensure reliable transfer and storage of information. With a wide range of application, from PC's and data storage media to wireless communication and deep-space telecommunication to high-definition television and smart phones, efficient error-correcting codes with reliable error-correcting capability are increasingly important in daily life. Codes defined using sparse matrices, known as low-density parity check codes, are appealing to such applications due to low-complexity decoding algorithms. Moreover, codes based on randomly-generated sparse matrices tend to perform well in simulations. However, this remarkable performance lacks theoretical underpinning and, hence, is not guaranteed in general. In this proposal, the investigator examines parity check codes paired with iterative decoding algorithms from an algebraic standpoint with the specific goal of characterizing decoder failure.