CaltechAUTHORS
  A Caltech Library Service

Subspace subcodes of Reed-Solomon codes

Hattori, Masayuki and McEliece, Robert J. and Solomon, Gustave (1998) Subspace subcodes of Reed-Solomon codes. IEEE Transactions on Information Theory, 44 (5). pp. 1861-1880. ISSN 0018-9448. http://resolver.caltech.edu/CaltechAUTHORS:HATieeetit98

[img]
Preview
PDF
See Usage Policy.

1003Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:HATieeetit98

Abstract

We introduce a class of nonlinear 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 the RS codewords whose components all lie in a fixed ν-dimensional vector subspace S of GF (2m). SSRS codes are constructed using properties of the Galois field GF(2m). They are not linear over the field GF(2ν), which does not come into play, but rather 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 main result is an explicit but complicated formula for the dimension of an SSRS code. It implies a simple lower bound, which gives the true value of the dimension for most, though not all, subspaces. We also prove several important duality properties. We present some numerical examples, which show, among other things, that (1) SSRS codes can have a higher dimension than comparable subfield subcodes of RS codes, so that even if GF(2ν) is a subfield of GF(2m), it may not be the best ν-dimensional subspace for constructing SSRS codes; and (2) many high-rate SSRS codes have a 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 promising candidates to replace Reed-Solomon codes in high-performance transmission and storage systems.


Item Type:Article
Additional Information:© Copyright 1998 IEEE. Reprinted with permission. Manuscript received November 11, 1996; revised March 2, 1998. The work of M. Hattori was supported by the Sony Corporation and the California Institute of Technology. A portion of the work of R. McEliece was performed at the Jet Propulsion Laboratory, California Institute of Technology, under Contract to the National Aeronautics and Space Administration. This work was also supported by NSF under Grant NCR-9505975, and in part by the Sony Corporation. The work of G. Solomon was carried out in part at the Jet Propulsion Laboratory, California Institute of Technology, under Contract to the National Aeronautics and Space Administration. G. Solomon died on January 31, 1996, after the research in this paper had been completed. The material in this paper was presented in part at the IEEE International Symposium on Information Theory, Trondheim, Norway, 1994.
Subject Keywords:Error-correcting codes, nonbinary codes, Reed–Solomon codes
Record Number:CaltechAUTHORS:HATieeetit98
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:HATieeetit98
Alternative URL:http://dx.doi.org/10.1109/18.705564
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:6792
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:21 Dec 2006
Last Modified:26 Dec 2012 09:25

Repository Staff Only: item control page