2008/05/05 by Yingquan Wu, Wu, Yingquan
Computer Science · Mathematics · #Algorithm #Block code #Cellular Automata and Applications #Code word #Coding theory and cryptography #Combinatorics #Computational Complexity (cs.CC) #Concatenated error correction code #Cooperative Communication and Network Coding #Decoding methods #Discrete mathematics #Expander code #FOS: Computer and information sciences #FOS: Mathematics #Generator matrix #Information Theory (cs.IT) #Linear code #Mathematics #Parity-check matrix #Reed–Solomon error correction #Rings and Algebras (math.RA) #Upper and lower bounds #cs.CC #cs.IT #math.IT #math.RA
paper · pdf · doi:10.48550/arxiv.0805.0615
published in arXiv (Cornell University) (Cornell University) · 23 pages. Submitted for publication in IEEE Trans. Inform. Theory
openalex publication_date 2008/05/05 · arxiv created 2008/07/08 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
The paper has a threefold purpose. The first purpose is to present an explicit description of expanded cyclic codes defined in \GF(qm). The proposed explicit construction of expanded generator matrix and expanded parity check matrix maintains the symbol-wise algebraic structure and thus keeps many important original characteristics. The second purpose of this paper is to identify a class of constant-weight cyclic codes. Specifically, we show that a well-known class of q-ary BCH codes excluding the all-zero codeword are constant-weight cyclic codes. Moreover, we show this class of codes achieve the Plotkin bound. The last purpose of the paper is to characterize expanded cyclic codes utilizing the proposed expanded generator matrix and parity check matrix. We characterize the properties of component codewords of a codeword and particularly identify the precise conditions under which a codeword can be represented by a subbasis. Our developments reveal an alternative while more general view on the subspace subcodes of Reed-Solomon codes. With the new insights, we present an improved lower bound on the minimum distance of an expanded cyclic code by exploiting the generalized concatenated structure. We also show that the fixed-rate binary expanded Reed-Solomon codes are asymptotically "bad", in the sense that the ratio of minimum distance over code length diminishes with code length going to infinity. It overturns the prevalent conjecture that they are "good" codes and deviates from the ensemble of generalized Reed-Solomon codes which asymptotically achieves the Gilbert-Varshamov bound.