Subspace Subcodes of Reed-Solomon Codes

Citation

Hattori, Masayuki (1995) Subspace Subcodes of Reed-Solomon Codes. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/m50j-xx64. https://resolver.caltech.edu/CaltechETD:etd-07172007-105811

Abstract

In this paper we introduce a new class of non-linear cyclic error-correcting codes, which we call subspace subcodes of Reed-Solomon (SSRS) codes. An SSRS code is a subset of a parent Reed-Solomon (RS) code consisting of codewords whose components all lie in a fixed v-dimensional vector subspace S of GF(2ᵐ).

Starting from a (n, k₀, d₀) RS code over GF(2ᵐ), with any positive integer 0 ≤ v ≤ m, there is an SSRS code of length n and designed minimum distance d₀ over the symbol alphabet S, the vector space of binary v-tuples. SSRS codes are constructed using properties of the Galois field GF(2ᵐ). SSRS codes are not linear over GF(2ᵛ) but are Abelian group codes over S. However, they are linear over GF(2), and the symbol-wise cyclic shift of any codeword is also a codeword.

Our first main result is an explicit formula for the dimension of an SSRS code. It is followed by a corollary which gives a simple lower bound, which gives the true value for "most" subspaces. We also prove several important duality properties.

Next, we give a classification of the v-dimensional subspaces of GF(2ᵐ) into categories, such that two subspaces in the same category always produce isometric SSRS codes. Then, we give an efficient means to find the "exceptional" subspaces among the huge number of subspaces. We also present a reasonably simple encoding algorithm that works for systematic shortened linear codes in general.

Finally, we present some numerical examples, which show, among other things, that (1) SSRS codes can have a higher dimension than comparable GBCH codes, so that even if GF(2ᵛ) is a subfield of GF(2ᵐ), it may not be the "best" v-dimensional subspace for constructing SSRS codes; and (2) many high-rate SSRS codes have larger dimension than any previously known code with the same values of n, d and q, including algebraic-geometry codes. These examples suggest that high-rate SSRS codes are likely candidates to replace Reed-Solomon codes in high-performance transmission and storage systems.

Thesis Files