zbMATH — the first resource for mathematics

On graph constructions for LDPC codes by quasi-cyclic extension. (English) Zbl 1073.94523
Blaum, Mario (ed.) et al., Information, coding and mathematics. Proceedings of workshop honoring Professor Bob McEliece on his 60th birthday, Pasadena, CA, USA, May 24–25, 2002. Boston, MA: Kluwer Academic Publishers (ISBN 1-4020-7079-9/hbk). The Kluwer International Series in Engineering and Computer Science 687, 209-220 (2002).
Summary: Quasi-cyclic (QC) extension is a recursive graph construction that preserves key design parameters of a “seed” graph, such as the distribution of the degrees of the nodes, while increasing graph size and girth. Algebraic QC extension graphs are described in which automorphisms of the seed graph are purposefully preserved in the extension. The girth of the extension graph will be as least as great as for the seed while the “design rate” of the code is the same. A two-stage QC extension is given for a \((3,4)\) low-density parity-check (LDPC) code to illustrate.
For the entire collection see [Zbl 1054.94001].
94B15 Cyclic codes
05C90 Applications of graph theory
20B25 Finite automorphism groups of algebraic, geometric, or combinatorial structures