Moderate-density parity-check codes from projective bundles.

• DOI: 10.5167/uzh-219471
• Publication Date: 2022-05-24
• Authors: Bariffi, Jessica; Mattheus, Sam; Neri, Alessandro; Rosenthal, Joachim
• Keywords: Projective plane; FOS: Computer and information sciences; Projective bundle; Computer Science - Information Theory; bit-flipping decoding algorithm.; 02 engineering and technology; 0102 computer and information sciences; 01 natural sciences; Article; 510 Mathematics; 2604 Applied Mathematics; Bit-flipping decoding algorithm; 1706 Computer Science Applications; 0202 electrical engineering, electronic engineering, information engineering; FOS: Mathematics; Mathematics - Combinatorics; 11T71, 51E05; 2614 Theoretical Computer Science; flipping decoding algorithm; Applied Mathematics; Information Theory (cs.IT); Computer Science Applications; 10123 Institute of Mathematics; 2607 Discrete Mathematics and Combinatorics; Bit-flipping decoding algorithm; MDPC codes; Projective bundle; Projective plane; MDPC codes; Combinatorics (math.CO); MDPC codes · Projective bundle · Projective plane · Bit

AbstractNew constructions for moderate-density parity-check (MDPC) codes using finite geometry are proposed. We design a parity-check matrix for the main family of binary codes as the concatenation of two matrices: the incidence matrix between points and lines of the Desarguesian projective plane and the incidence matrix between points and ovals of a projective bundle. A projective bundle is a special collection of ovals which pairwise meet in a unique point. We determine the minimum distance and the dimension of these codes, and we show that they have a natural quasi-cyclic structure. We consider alternative constructions based on an incidence matrix of a Desarguesian projective plane and compare their error-correction performance with regards to a modification of Gallager’s bit-flipping decoding algorithm. In this setting, our codes have the best possible error-correction performance after one round of bit-flipping decoding given the parameters of the code’s parity-check matrix.