Information sets in quadratic-residue codes

AbstractIn a linear (n, k) code, a set of k coordinates is said to be an information set for the code if the projection map onto those k coordinates is a vector space isomorphism. Extended (cyclic) quadratic-residue codes are linear (p+1,12(p+1)) codes, defined whenever p is prime. The automorphism group of this code contains PSL(2, p) (the Gleason-Prange theorem). This group includes elements with order 12(p+1) and it is conceivable that one or both orbits of such an element will serve as an information set for the code. When this happens, simplified decoding procedures are possible.These codes can be defined over a ring of algebraic integers in such a way that the QR code with entries in a finite field is just the image of this global code under a residue-class map. It is shown that the global code includes a codeword of the form (z(p) 0 0 … 0) on a given orbit, where z(p) is a rational integer. A series of theorems show that knowing this codeword is enough to answer the question (for either orbit) for QR codes over fields of any characteristic. (Briefly an orbit can fail to be an information set for the characteristic q case if and only if q devides z(p). A method for finding this codeword is given which is based on a connection between z(p) and the determinant of a certain 0, 1-matrix. The results of this technique are given which answer the question for 5 ⩽ p ⩽ 83