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. doi:10.7907/m50j-xx64.


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.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:Elecrical Engineering
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Electrical Engineering
Thesis Availability:Public (worldwide access)
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:07 May 2020 18:59

Thesis Files

PDF (Hattori_M_1995.pdf) - Final Version
See Usage Policy.


Repository Staff Only: item control page