Difference-Set Cyclic Codes

The Bose-Chaudhur^-Hocquenghem"' (BCH) cyclic codes are, as a class, the best of the known, constructive, random-error-correcting codes. Fortunately a decoding algorithm, which can be implemented with a reasonable amount of equipment, has been found for these codes.3,4,5 In this paper, a new class of random-error-correcting cyclic codes is presented. These codes can be implemented much more simply than the BCH codes and are approximately as powerful. Unfortunately, the class is a small one. I I . D I F F E R E N C E - S E T CYCLIC CODES A simple perfect difference set of order I and modulus n = I (I -- 1) + 1 is defined as a collection of I integers chosen from the set {0, 1, · · · , 1(1 -- 1)} such that no two of the 1(1 -- 1) ordered differences modulo n are identical. That is, each occurs once. Singer6 has shown 1045 1046 THE B E L L SYSTEM T E C H N I C A L J O U R N A L , SEPTEMBER 19GG how to construct such sets when I = p* -j- 1, p prime, s a positive integer, while Evans and Mann 7 have shown that a perfect difference set cannot be constructed for any other value of I ^ 1G00. Since adding a fixed integer to every element of a perfect difference set clearly results in another such set, no loss of generality is suffered by considering only sets containing the element 0. In what follows, all perfect difference sets will be of this type. Denote the elements of a perfect difference set of order ps -f- 1 by di = 0, d.2, · · · , dp*+ and let 6(x) = + xd* + · · · + xdpS+1 be a polynomial in the algebra of polynomials modulo xn -- 1.