On Divisible Codes over Finite Fields

bounds;divisible codes;error-correcting codes;Ward

Liu, Xiaoyu ; Wilson, Richard M.

University:California Institute of Technology

Department:Physics, Mathematics and Astronomy

关键词: bounds;    divisible codes;    error-correcting codes;    Ward;   

Others  :  https://thesis.library.caltech.edu/2055/1/thesis.pdf

美国|英语

来源: Caltech THESIS

【 摘 要 】

We study a certain kind of linear codes, namely divisible codes, over finite fields. These codes, introduced by Harold N. Ward, have the property that all codeword weights share a common divisor larger than 1. These are interesting error-correcting codes because many optimal codes and/or classical codes exhibit nontrivial divisibility.

We first introduce an upper bound on dimensions of divisible codes in terms of their weight spectrums, as well as a divisibility criteria for linear codes over arbitrary finite fields. Both the bound and the criteria are given by Ward, and these are the primary results that initiate this work.

Our first result proves an equivalent condition of Ward's bound, which involves only some property of the weight distribution, but not any other properties (including the linearity) of the code. This equivalent condition consequently provides an alternative (and more elementary) proof of Ward's bound, and from the equivalence we extend Ward's bound to certain nonlinear codes.

Another perspective of the equivalence gives rise to our second result, which studies weights modulo a prime power in divisible codes. This is generalized from weights modulo a prime power in linear codes, and yields much better results than the linear code version does. With a similar method we propound a new bound that is proved to be better than Ward's bound.

Our third result concerns binary divisible codes of maximum dimension with given lengths. We start with level one and level two codes, which are well described from this point of view. For higher level codes we prove an induction theorem by using the binary version of the divisibility criteria, as well as Ward's bound and the new generated bound. Moreover, this induction theorem allows us to determine the exact bound and the codes that attain the bound for level three codes of relatively small length.