Algebraic analysis of parity check codes and iterative decoding

主要研究者：马修斯，格雷琴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.