Pseudo-Codeword Analysis and Design of Quasi-Cyclic and Convolutional Codes

提案：DMS - 0708033PI: Smarandache， roxaninstitution: San Diego State university标题：本项目侧重于现代数字通信系统的数学方面，特别是有限域上某些向量空间的分析和设计，称为低密度奇偶校验（LDPC）码，具有一组“稀疏”向量生成对偶空间，其中包括准循环和卷积LDPC码。结合基于沿与代码自然相关的图的边缘传递概率估计的迭代解码算法，这些代码对当前和未来的通信系统显示出很大的希望。分析包括对相关代码图、基本锥体（在线性规划解码和迭代解码中具有含义）、伪码字集（阻止迭代解码收敛的罪魁祸首）和伪权（迭代解码下的性能度量）的分析。目标是：发展有限长度LDPC码的理论，并提供具有相关代数结构的不同码之间的比较；统一近码字、伪码字、周长、最小距离、最小伪权值等相关概念，研究它们之间的相互作用；基于这些参数及其影响，推导出LDPC块码和卷积码性能的下界和上界；并最终为设计在迭代解码下具有可预测的良好性能的有限长度LDPC码提供指导。将LDPC分组码纳入新兴标准，如数字视频广播、以太网和第三代（3G）移动电话网络，这将使3G手机的无线接入速度比老式拨号快十倍以上，最近激发了人们对LDPC卷积码的兴趣。对LDPC卷积码的初步研究使PI相信，与LDPC分组码相比，这些码具有几个潜在的实用优势。该项目的目标是分析这些代码并构建具有可预测的良好性能的新代码。这项研究将自然地将抽象理论与现实应用相结合，为交叉研究提供了令人兴奋的机会。PI与来自学术界和工业界的领先工程专家的持续合作，使该项目的理论研究成果能够转化为实用的通信系统。预计该项目将对未来的信息基础设施产生影响，并有助于实现普遍可及性。这种影响将扩展到数据压缩、通信协议和安全领域，因为它们的基础理论与编码理论密切相关。

Proposal: DMS - 0708033PI: Smarandache, RoxanaInstitution: San Diego State UniversityTitle: Pseudo-Codeword Analysis and Design of Quasi-Cyclic and Convolutional CodesAbstractThis project focuses on the mathematical aspects of modern digital communication systems --- in particular on the analysis and design of certain vector spaces over finite fields, called low-density parity-check (LDPC) codes, that have a set of "sparse'' vectors generating the dual space, and among these, on quasi-cyclic and convolutional LDPC codes. In conjunction with an iterative decoding algorithm based on passing probability estimates along the edges of a graph naturally associated to the code, these codes show great promise for current and future communication systems. The analysis consists of an analysis of the associated code graphs, fundamental cones (with implications in linear programming decoding and iterative decoding), pseudo-codeword sets (the culprits that prevent the convergence of iterative decoding) and pseudo-weights (a measure of performance under iterative decoding). The goals are: to develop a theory of finite-length LDPC codes and provide a comparison between different codes having related algebraic structures; to unify relevant notions like near-codewords, pseudo-codewords, girth, minimum distance, minimum pseudo-weight by studying the effect that each has on the others; to derive lower and upper bounds on the performance of LDPC block and convolutional codes based on these parameters and their influences; and to ultimately provide guidelines for designing finite-length LDPC codes that have predictably good performance under iterative decoding.The inclusion of LDPC block codes in emerging standards such as digital video broadcasting, Ethernet and third-generation (3G) mobile-telephone networks, which will allow wireless access from 3G phones to be over ten times faster than from an old-fashioned dial-up, has recently spurred interest in LDPC convolutional codes. Initial research on LDPC convolutional codes leads the PI to the belief that these codes have several potential practical advantages compared to LDPC block codes. The goal of this project is to analyze these codes and construct new ones with predictably good performance. This research will naturally integrate abstract theory and real-world applications, providing exciting opportunities for cross-cutting research. The PI's continuing collaboration with leading engineering experts from academia and industry enables a transition from the theoretical research findings in this project to practical communication systems. It is anticipated that the project will have an impact on the future information infrastructure and contribute to universal accessibility. This impact will extend to the areas of data compression and communication protocols and security, since their underlying theories are closely related to coding theory.