A Caltech Library Service

Subspace subcodes of Reed-Solomon codes


Hattori, Masayuki (1995) Subspace subcodes of Reed-Solomon codes. Dissertation (Ph.D.), California Institute of Technology.


NOTE: Text or symbols not renderable in plain ASCII are indicated by [...]. Abstract is included in .pdf document.

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([...]).

Starting from a (n, k0, d0) RS code over GF([...]), with any positive integer 0 [...] v [...] m, there is an SSRS code of length n and designed minimum distance d0 over the symbol alphabet S, the vector space of binary v-tuples. SSRS codes are constructed using properties of the Galois field GF([...]). SSRS codes are not linear over GF([...]) 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([...]) 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([...]) is a subfield of GF([...]), 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.

Item Type:Thesis (Dissertation (Ph.D.))
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Electrical Engineering
Thesis Availability:Restricted to Caltech community only
Research Advisor(s):
  • McEliece, Robert J.
Thesis Committee:
  • McEliece, Robert J. (chair)
  • Franklin, Joel N.
  • Abu-Mostafa, Yaser S.
Defense Date:30 May 1995
Record Number:CaltechETD:etd-07172007-105811
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:2912
Deposited By: Imported from ETD-db
Deposited On:17 Jul 2007
Last Modified:26 Dec 2012 02:55

Thesis Files

[img] PDF (Hattori_M_1995.pdf) - Final Version
Restricted to Caltech community only
See Usage Policy.


Repository Staff Only: item control page