On the Construction of Linear q-ary Lexicodes

Abstract Let V be a list of all vectors of GF(q)n, lexicographically ordered with respect to some basis. Algorithms which search list V from top to bottom, any time selecting a codeword which satisfies some criterion, are called greedy algorithms and the resulting set of codewords is called a lexicode. In many cases such a lexicode turns out to be linear. In this paper we present a greedy algorithm for the construction of a large class of linear q-ary lexicodes which generalizes the algorithms of several other papers and puts these into a wider framework. By applying this new method, one can produce linear lexicodes which cannot be constructed by previous algorithms, because the characteristics or the underlying field of the codes do not meet the conditions of those algorithms.