Algebraic analysis of parity check codes and iterative decoding

主要研究人员：Matthews，Gretchen L.建议编号：DMS-0901693机构：克莱姆森大学标题：奇偶校验码和迭代译码的代数分析这项资助得到了EPSCoR计划的部分支持。研究人员研究代数结构在编码理论中的应用。本项目主要研究由奇偶校验矩阵定义的码的迭代译码算法，特别是由稀疏矩阵定义的低密度奇偶校验码。虽然这样的码与用于解码的迭代消息传递算法配对可以获得接近容量的性能，但这些观察主要基于模拟和随机化。对这种性能的代数理解将绕过随机化的需要，随机化是一种可能导致差错纠正能力并阻碍编码过程的过程。该项目旨在解释并开发基于稀疏矩阵的代码的性能能力。特别是，研究人员的目标是识别导致解码失败的代数结构，并描述最有可能失败的代数结构。这一问题的理想结果是如何最好地表示线性码，以及如何为给定码和译码算法选择奇偶校验矩阵。尽管目前奇偶校验码的实际实现只对那些由稀疏矩阵定义的码是合理的，但理论研究适用于任何线性码，并且可以提供超越低密度奇偶校验码的见解。纠错码确保了信息的可靠传输和存储。随着PC和数据存储介质的广泛应用，从无线通信和深空通信到高清晰度电视和智能手机，具有可靠纠错能力的高效纠错码在日常生活中变得越来越重要。使用稀疏矩阵定义的码，称为低密度奇偶校验码，由于低复杂度的译码算法而吸引着这样的应用。此外，基于随机生成的稀疏矩阵的代码在模拟中往往表现良好。然而，这种出色的表现缺乏理论依据，因此，总体上并不能得到保证。在这项建议中，研究者从代数的角度研究与迭代译码算法配对的奇偶校验码，具体目的是描述译码失败的特征。

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.