The Nimber-Simplex Graph as a Model to Compare LDPC and Turbo Codes

Overview

Objectives/Goals The objective of this project was to expand on my previous projects, which defined and characterized the Nimber-Simplex graph. The first goal was to prove that all binary linear codes map to the graph. The second goal was to demonstrate the graph's practical applicability by comparing low density parity check (LDPC) codes and turbo codes. Methods/Materials To prove my first hypothesis, I formally defined the Nimber-Simplex graph, then proved that all binary linear codes map to the graph by mapping message digits to the vertices. I showed examples using Hamming codes, single parity check codes, and maximum length codes. Next, I formally defined binary linear sets as abelian groups with self-inverse and proved that they map to the graph. I showed examples using BCH codes and polynomials in binary fields. To prove my second hypothesis, I showed how Gaussian elimination can be used to derive standard generator and check matrices from an LDPC matrix. Using these standardized matrices, I mapped the LDPC (15, 7)-code to the graph and then showed a construction of standard parity check codes and turbo codes which are roughly equivalent to the original LDPC code. I briefly discussed measures of code performance and outlined a direct comparison between the two families, proving my hypothesis. Results This project proves its hypotheses and gives an outline for future study. The proof that all binary linear codes and sets map to the graph allows a direct comparison between two highly effective but dissimilar modern code families: LDPC codes and turbo codes. A proposal for implementation of this comparison is outlined. Conclusions/Discussion In this project, the Nimber-Simplex graph, which had been previously described as an abstract mathematical object, is shown to have applications to modern coding theory. The comparison between LDPC and turbo codes establishes a methodology to compare other code families. The Nimber-Simplex graph may be used to design new LDPC codes by reversing Gaussian elimination. The ability to map binary linear sets to the graph may also offer new ways of designing linear codes with a wide variety of properties.

Competition history

• CSEF 2006 Mathematics & Software · Entry J1218

Resources

• CSEF project summary ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.

Browse more like this

• All Computational Sciences projects
• CSEF Computational Sciences projects
• Every CSEF 2006 project