On the dimension and exceptional subspaces of SSRS codes

Abstract

A class of nonlinear cyclic error-correcting codes, known as Subspace Subcodes of Reed-Solomon (SSRS) codes, is studied in this thesis. An SSRS code is a subcode of a Reed-Solomon (RS) code consisting of RS codewords whose components all lie in a fixed v-dimensional vector subspace V of F??. The RS code is called the parent code of the SSRS code. SSRS codes are closed under addition but not necessarily closed under multiplication with elements of F??. In general, they are nonlinear over F??. SSRS codes are cyclic in the sense that a cyclic shift of any codeword is again a codeword, and they are linear over F?. Thus, SSRS codes constitute a proper subclass of F?-linear cyclic (F?LC) codes over F??. Since an SSRS code is a subcode of the parent RS code, the minimum Hamming distance of the SSRS code is at least that of the parent code. So, estimating the dimension over F?, or equivalently finding the number of codewords in the SSRS code, is an important problem. When the parent code is of length 2? ? 1, in terms of a trace dual basis of V, an explicit but complicated formula for the binary dimension (HMS dimension formula) and a simple lower bound (HMS lower bound) of an SSRS code has recently been reported. In this thesis, we report a relatively simple formula for calculating the cardinality of an SSRS code by making use of the fact that K is an [m, v] linear code over F?, and hence is describable by a H (parity-check) matrix over F?. Our formula is in terms of the description of SSRS codes in the Discrete Fourier Transform (DFT) domain, H-matrix description of the given subspace, and counting endomorphisms of F?? satisfying certain conditions. A subspace V is called exceptional if there is an RS code for which the SSRS code over V has dimension more than the HMS lower bound. And subspaces that are not exceptional are called ordinary. A small class of subspaces is identified which is shown to be exceptional.