Hierarchical Quasi-cyclic Codes from Reed-Solomon and Polynomial Evaluation Codes

Emily McMillon 1, Kathryn Haymaker 2 · 2025

Read Hierarchical Quasi-cyclic Codes from Reed-Solomon and Polynomial Evaluation Codes by Emily McMillon 1, Kathryn Haymaker 2 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-23872.txt.

Introduction

Emily McMillon and Kathryn Haymaker construct the first algebraic examples of hierarchical quasi-cyclic codes, error-correcting codes with layered structure. Their raw material is the classic Reed-Solomon code family, combined through a superimposed code construction published by Kautz and Singleton in 1964. Hierarchy lets different parts of a message enjoy different levels of protection, and quasi-cyclic structure keeps encoding hardware simple.

Both the number of hierarchy levels and the index of their codes turn out to be fixed by the underlying field size. The same holds for wider classes of polynomial evaluation codes. The authors give explicit parameters plus bounds on rank and distance; starting from two-dimensional Reed-Solomon codes yields Tanner graphs of girth six. Some small examples match the best known minimum distance for binary codes while adding the hierarchical structure. Unlike the simulation-heavy literature on related codes, their bounds are proved algebraically.

Catalog record

CREATOREmily McMillon 1, Kathryn Haymaker 2
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE80 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-23872

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Hierarchical Quasi-cyclic Codes from Reed-Solomon and Polynomial Evaluation Codes Thanks: The first author was supported by the National Science Foundation grant DMS-2303380. Emily McMillon 1, Kathryn Haymaker 2 Abstract . We introduce the first example of algebraically constructed hierarchical quasi-cyclic codes. These codes are built from Reed-Solomon codes using a 1964 construction of superimposed codes by Kautz and Singleton. We show both the number of levels in the hierarchy and the index of these Reed-Solomon derived codes are determined by the field size. We show that this property also holds for certain additional classes of polynomial evaluation codes. We provide explicit code parameters and properties as well as some additional bounds on parameters such as rank and distance. In particular, starting with Reed-Solomon codes of dimension k = 2 k=2 yields hierarchical quasi-cyclic codes with Tanner graphs of girth 6 6 . We present a table of small code parameters and note that some of these codes meet the best known minimum distance for binary codes, with the additional hierarchical quasi-cyclic structure. We draw connections to similar constructions in the literature, but importantly, while existing literature on related codes is largely simulation-based, we present a novel algebraic approach to determining new bounds on parameters of these codes. 2010 Mathematics Subject Classification 94B05, 94B25, 94B27 1. Introduction Parity-check codes are linear codes specified by a parity-check matrix, which plays a central role in determining code parameters and often forms the basis for a decoding strategy. Notable families include low-density parity-check (LDPC) codes, moderate-density parity-check (MDPC) codes, and codes defined via sparse Tanner graph representations. LDPC codes and their iterative decoding algorithm were introduced by Gallager [ 1 ] . Modern research in MDPC codes is inspired by their role in post-quantum cryptography schemes based on the McEliece cryptosystem [ 2 ] . Here, we explore an algebraic construction of parity-check codes motivated by a study of moderate-density and low-density parity-check codes from disjunct matrices [ 3 ] . This construction is inspired by Kautz and Singleton’s classical work on superimposed codes [ 4 ] . The Kautz and Singleton approach has seen renewed interest recently (e.g. [ 5 , 6 ] ), including a flurry of new work related to group testing for COVID-19 [ 7 , 8 , 9 , 10 ] . Kautz and Singleton used q -ary codes to create binary superimposed codes, and since there are many ways to derive binary codes from nonbinary, we will delineate the differences between our main construction and other methods. One notable related construction is for LDPC codes from 2-dimensional MDS codes [ 11 ] , a special case of which was adopted as the standard for 10 Gigabit Ethernet over copper (10GBASE-T) [ 12 ] . Related LDPC codes from 2-dimensional MDS codes are presented in [ 13 , 14 ] . A variation called mirror-paradigm Reed-Solomon based quasi-cyclic LDPC codes was proposed for nonvolatile memory channels in [ 12 ] . More recently, a correspondence that sends rank-metric codes to Hamming codes via a similar length q unit-vector mapping was studied in [ 15 ] . There are different methods of mapping non-binary Reed-Solomon (or other) codes into binary. The binary image of a code over \mathbb{F}_{2^{m}} replaces each \mathbb{F}_{2^{m}} symbol with a binary m -tuple (see [ 16 ] ). For example, the binary expanded Reed-Solomon codes studied in [ 17 ] replace each field element from \mathbb{F}_{2^{m}} with a binary m -tuple. In contrast, the mapping in this paper sends symbols from an arbitrary field \mathbb{F}_{q} to binary q -tuples of weight one. The resulting codes are quasi-cyclic, with index equal to the characteristic of the underlying field, and have further hierarchical quasi-cyclic properties that we prove. Quasi-cyclic parity-check codes are among the most widely studied classes of structured linear codes due to their simple and practical implementations (e.g. [ 18 , 19 , 20 , 21 ] ). A code is quasi-cyclic if it is invariant under shifts by some integer t , called the index. Quasi-cyclic LDPC and MDPC codes have proven to be successful and produce codes with predictable rank behavior and favorable Tanner graph properties while maintaining efficient implementations [ 22 ] . These advantages have led to the use of quasi-cyclic LDPC codes in a variety of modern communication and storage standards. The rank of QC-LDPC codes has been studied in [ 23 , 24 ] and references therein. Hierarchical quasi-cyclic (HQC) codes were introduced in [ 19 ] as a generalization of quasi-cyclic codes. In these codes, the matrix structure is globally quasi-cyclic, and the smaller pieces of the code are also quasi-cyclic, potentially with multiple such levels. This also generalizes the idea of taking the pre-lifted protograph approach, as in e.g. [ 25 , 26 ] , to an arbitrary number of quasi-cyclic graph lifts. From a practical perspective, HQC codes present a way to compactly represent more complicated, but still structured, matrices. From a theoretical perspective, the presence of multiple quasi-cyclic layers introduces parameters—such as the number of levels and associated indices—that can be leveraged to influence code parameters. In [ 3 ] , it was shown that by taking a Reed-Solomon code of length n and dimension 2 , the parity-check codes obtained via the construction considered in this paper are free of 4 -cycles, which is advantageous for iterative decoding. However, specific parameters such as exact dimension and minimum distance were left as open questions. In this work, we show that hierarchical quasi-cyclic structure can arise naturally from an algebraic construction based on Reed–Solomon codes and other classes of polynomial evaluation codes via the Kautz–Singleton superimposed code construction. To our knowledge, this is the first explicit algebraic construction yielding hierarchical quasi-cyclic codes. This means that the code parameters are not imposed externally, but are intrinsic to the algebraic construction, and enables analysis of their parameters using algebraic tools. A few of the results were first presented in [ 27 ] , some without proofs. This version has significantly more background and motivation and also contains new results on the hierarchical quasi-cyclic structure of parity-check codes from Reed-Solomon and certain polynomial evaluation codes, using the main construction. The paper is structured as follows: Section 2 introduces standard coding theory definitions as well as needed background on hierarchical quasi-cyclic codes and the key constructions. The parameters and an algebraic analysis of our main construction are given in Section 3 as well as a characterization of these codes within the hierarchical quasi-cyclic framework. Results on the relationship between the main construction and existing codes, as well as the impact of permutation and monomial equivalence in the starting q -ary codes on the resulting binary codes, are proven in Section 4 . Section 5 gives a table of code parameters for small field sizes. Section 6 concludes the paper. 2. Preliminaries We begin with some general notation. Throughout, [N] denotes the set \{1,2,\dotsc,N\} . The finite field with q elements is denoted \mathbb{F}_{q} ( q is always a power of a prime). Vectors are denoted in boldface, i.e. \mathbf{x} . The support of a binary string \mathbf{x} is the set of indices i where x_{i}=1 . Finally, define [\mathbf{e}_{i}]_{n} to be

Read the complete text