On Expanded Cyclic and Reed–Solomon Codes
Yingquan Wu · IEEE Transactions on Information Theory · 2011
This paper offers new insights into expanded cyclic and Reed-Solomon codes. First, we present a new description of general expanded codes defined over GF(qm). The proposed explicit description of the expanded generator matrix and the expanded parity check matrix reserves the symbol-wise algebraic structure. We reveal that the dual of an expanded code is the symbol-wise dual code expanded by the dual basis. Second, we characterize expanded cyclic codes utilizing the proposed expanded generator matrix (a similar analysis may be carried out over the proposed expanded parity check matrix). We focus on exploring the properties of component words of a codeword as well as their reciprocal relations. We reveal that the existence of subspace subcodes is dictated by conjugate roots of its dual generator polynomial, but not by its nonconjugate roots. We further show that each generator (parity check) matrix can be divided into block-bidiagonal submatrices associated with conjugate roots of the dual generator (generator) polynomial. Third, we shed light on binary expanded Reed-Solomon codes, which are of particular mathematical and practical interest. We first show an explicit way of constructing superior subspace subcodes utilizing the product basis which exhibit a higher dimension than the counterpart subfield subcodes. We next demonstrate that the effective dimension of the expanded parity check (generator) matrix, which governs the complexity of maximum-likelihood soft-decision decoding, can be noticeably reduced by employing block-bidiagonal structures of submatrices associated with conjugate roots of the generator (dual generator) polynomial. We finally conclude that the fixed-rate binary expanded Reed-Solomon codes are asymptotically “bad,” regardless of basis realization, in the sense that the ratio of minimum distance over code length diminishes with code length going to infinity. We assert “badness” in three scenarios, namely, (1) (conventional) fixed starting spectral null for all rates; (2) centered spectral null for rates above1/3; and (3) dynamic spectral null for rates above11/21. Our conclusions overturn the prevailing conjecture that binary expanded Reed-Solomon codes, particularly high-rate ones, are asymptotically “good” codes, while deviating from the ensemble of generalized Reed-Solomon codes which asymptotically achieve the Gilbert-Varshamov bound.