| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | February 6, 2007 |
| Latest Amendment Date: | February 6, 2007 |
| Award Number: | 0635391 |
| Award Instrument: | Standard Grant |
| Program Manager: |
William H Tranter
CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | February 15, 2007 |
| End Date: | January 31, 2011 (Estimated) |
| Total Intended Award Amount: | $255,235.00 |
| Total Awarded Amount to Date: | $255,235.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
3227 CHEADLE HALL SANTA BARBARA CA US 93106-0001 (805)893-4188 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
3227 CHEADLE HALL SANTA BARBARA CA US 93106-0001 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | SIGNAL PROCESSING SYS PROGRAM |
| Primary Program Source: |
|
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
In the last decade, decoding of codes from low-density matrices (LDPC codes) using the sum-product algorithm was shown to yield dramatic improvement over classical coding schemes. Unfortunately, the decoding algorithm is not understood well enough to indicate how optimal LDPC codes should be constructed. Code performance can only be verified by computationally intensive simulation. The goal of our work, which will use a combination of theoretical analysis and structured, carefully targeted computer simulation, is
The proposed research comprises three complementary innovations, which will lead to a better understanding of the sum-product algorithm and of code design. First, we have developed an algebraic model for the algorithm in which we can study the fixed locus, and the dynamics after several iterations. We have used this model to establish exact results about convergence of the algorithm for small codes and successfully applied heuristics from small examples to understand codes of larger practical sizes. Second, we have improved on a widely used method for constructing LDPC codes in which the parity-check matrix is a block matrix with circulant submatrices. Our method works for very general block matrix structures and provides control over the existence of small cycles in the bipartite graph of the check-matrix. We will pursue a systematic comparison of a variety of codes constructed with this method, as well as comparisons with other methods. Third, we have developed a grid-based software infrastructure for studying the decoding properties of different codes at high signal-to-noise ratios. Using this infrastructure, we will be able to gather statistical
data about decoding failure at high signal-to-noise ratio. We can examine properties of input vectors that lead to decoding failure and test the relationship between decoding failure and the graphical model of the code.
Broader Impact: Successful completion of our research will have a significant impact on error-correction technology, which is playing an increasingly important role in data communication and storage. Commercial applications in the area of cellular and wireless technologies will benefit immediately. Our work will also influence emerging research disciplines in the area of low-power and unreliable communications systems such as sensor networks.
The research project will aid the Department of Mathematics and Statistics at San Diego State University in its goal of developing focused areas of applied mathematics research and collaborations with scientists and engineers in a variety of disciplines. Through the project's collaboration, we believe it will also encourage students to pursue doctoral research that combines rigorous mathematics with advanced computer systems techniques.
Intellectual Merit: The intellectual merit in this proposal is embodied in three of its features. First, it develops and applies a new approach that focuses on the foundations of belief propagation and the mathematical definition of high-quality LDPC codes. Second, it uses novel nationally distributed large-scale computing capabilities to guide and aid analysis rather than simply to offer empirical evidence of code quality. Finally, it blends expertise in mathematics and high-performance computer systems in a way that will both generate significant results and will motivate students to pursue similar interdisciplinary approaches to research.
Please report errors in award information by writing to: awardsearch@nsf.gov.
