The MacWilliams Identities for Nonlinear Codes

In recent years a number of nonlinear codes have been discovered which have better error-correcting capabilities t h a n any known linear codes (e.g., Refs. 1 and 2). However, very little is known about the properties of such codes. In this paper we study the most basic property, the Hamming weight enumerator (defined in Section II), which gives fundamental information about the error probability when the code is used in various error-correction schemes (Ref. 3, Ch. 16). In 1963 one of us showed t h a t the Hamming and the complete weight enumerators of a linear code are related in a simple way to those of the dual code (Ref. 4; Theorems 1 and 3 below). The requirement t h a t the code be linear is unsatisfactory for two reasons: (?) Several pairs of nonlinear 803 804 T H E BELL SYSTEM TECHNICAL JOURNAL, APRIL 1972 codes d, (B are known whose weight enumerators satisfy Theorem 3. One example of such a pair is given by the Preparata 2 and Kerdock 1 codes, another by the code shown in Fig. 1. («) The important theorem of S. P. Lloyd (giving a necessary condition for the existence of a prefect code) may be deduced for linear codes as a corollary to Theorem 3 (Ref. 4, Lemma 2.15), but may be proved directly without assuming linearity (Ref. 5; Ref. 6, p. 111). It is the purpose of the present paper, therefore, to define the "weight enumerators of the dual code" so as to make Theorems 1 and 3 (and the corresponding theorem for the Lee weight enumerator, Theorem 2) valid even for nonlinear codes.