Software - 徐 宗本 - 教师个人主页.pdf 
Software - 徐 宗本 - 教师个人主页.pdf
3778 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 54, NO. 8, AUGUST 2008 systematic code to q -ary systematic code. One simply needs to change B = (C T Ik ) into B = (0C T Ik ) and generalize Definition 4.1 to the following Definition 4.2, and then Theorems 4.1, 4.2, and 4.3 are also hold. Definition 4.2: If the stabilizer and normalizer matrices of Q = = (I(n0k) C j (I(n0k) C )S ) and [[n; k; d]]q are N( )= In 0k2n S B On The Classification of Binary Optimal Self-Orthogonal Codes Ruihu Li, Zongben Xu, and Xuejun Zhao Abstract—The classification of binary [n; k; d] codes with d s2 and without zero coordinates is reduced to the classification of binary [(2 1)c(k; s; t) + t; k; d] code for n = (2 1)s + t, s 1 and 1 t 2, where c(k; s; t) min s; t is a function of k; s; and t. Binary 2 [15s + t; 4] optimal self-orthogonal codes are characterized by systems of linear equations. Based on these two results, the complete classification of 1; 2; 6; 7; 8; 9; 13; 14 [15s + t; 4] optimal self-orthogonal codes for t and s 1 is obtained, and the generator matrices and weight polynomials of these 4-dimensional optimal self-orthogonal codes are also given. 0 respectively, where S is symmetric and B = (0C T Ik ), then Q is called a systematic quantum code, and its stabilizer matrix and normalizer matrix N ( ) are called in standard form. Remark 4.2: In [10], Tonchev proved that the subspaces generated by matrices of the form (In j S ) are maximum totally isotropic subspaces, where S is the adjacency matrix of an undirected graph. He also pointed out that the number of trace self-dual additive codes with generator matrix (In j S ) is much smaller than the total number of trace self-dual additive codes. Our Theorem 4.3 shows that it suffices to study trace self-dual additive codes with generator matrix (In j S ) for dealing with trace self-dual additive codes. ACKNOWLEDGMENT The authors would like to thank the anonymous referees for their valuable comments and suggestions, which help to improve this manuscript significantly. R. Li would like to thank Prof. S. Zhang and J. Zhang for their help in revising this correspondence. REFERENCES [1] A. Ashikhmin and E. Knill, “Nonbinary quantum stablizer codes,” airXiv:quant-ph/0005008. [2] J. Bierbrauer and Y. Edel, “Quantum twisted codes,” J. Comb. Designs, vol. 8, pp. 174–188, 2000. [3] A. R. Calderbank, E. M. Rains, P. W. Shor, and N. J. A. Sloane, “Quantum error-correction via codes over GF(4),” IEEE Trans. Inf. Theory, vol. 44, no. 4, pp. 1369–1387, Jul. 1998. [4] D. Gottesman, “Stabilizer codes and quantum error correction,” Ph.D. dissertation, Phys. Dept., California Inst. Technol., Los Angeles, CA, 1997, quant-ph/9707027. [5] L. K. Hua and Z. Wan, Classical Group (In Chinese). Shanghai, China: Shanghai Sci. Technol. Press, 1963. [6] W. C. Huffman, “On the classification and enumeration of self-dual codes,” Finite Fields Appl., vol. 11, pp. 451–490, 2005. [7] R. J. McEliece, The Theory of Information and Coding, 2nd ed. Cambridge, U.K.: Cambridge Univ. Press, 2002. [8] J. H. van Lint, Introduction to Coding Theory. New York: SpringerVerlag, 1982. [9] E. M. Rains, “Nonbinary quantum codes,” IEEE Trans. Inf. Theory, vol. 45, no. 6, pp. 1827–1832, Sep. 1999. [10] V. Tonchev, “Error-correcting codes from graphs,” Discrete Math., vol. 257, pp. 549–557, 2002. [11] Z. Wan, Geometry of Classical Groups Over Finite Fields. Lund, Sweden: Student Literature, 1993. f g 0 0 2f g Index Terms—Binary linear code, self-orthogonal code, optimal code. I. INTRODUCTION Since the pioneer work of Pless in [6], people paid much attention on self-dual codes—a subclass of self-orthogonal codes (SO codes, for short), and a vast number of papers have been devoted to the study of self-dual codes, as shown in the excellent survey of [7] and [4] for an overview of these results and the references therein. But, very little has previously been known about the minimum distance and number of general [n; k] SO codes of rate less than 12 , except the binary [2k + 1; k] SO codes for k 9 in [6]. Recently, people begin to study general optimal [n; k] SO codes of rate less than 12 and use these optimal [n; k] SO codes to study self-dual codes, see [1]. In [2] Bouykliev et al. studied the classification of optimal SO codes of length 29 and dimension less than 7 over F3 and F4 . In [3] Bouykliev et al. studied the classification of binary optimal SO codes of length 40 and dimension less than 10, and gave complete classification of three-dimensional (3-D) optimal SO codes. However, their classification are based on two algorithms and no unified proofs for dimension greater than 4, and most of the generator matrices of their optimal SO codes of length 25 and dimension greater than 6 are not given. In this correspondence, we discuss the classification of k -dimensional binary optimal SO codes. This correspondence is arranged as follows. First, we give some notations and make some preparation in this section. In Section II, we give the proof of our main result. In Section III, we give the relations of binary SO codes and some systems of linear equations, and explain how to determine the [15s + t; 4] optimal SO codes. In Section IV, we give the classification of [15s + t; 4] optimal SO codes for t 2 f1; 2; 6; 7; 8; 9; 13; 14g and s 1. Manuscript received April 16, 2007; revised November 22, 2007. This work is supported by Natural Science Foundation of China under Grants 60573040, 60575045, and 70531030, the National Basic Research Program of China (973 Program) under Grant 2007CB311002, the Postdoctoral Science Foundation of China under Grant 20060391009, and the Science Research Foundation of College of Science at AFE University. R. Li is with the College of Science, Xi’an Jiaotong University, Shaanxi 710049, China, and the Department of Applied Mathematics and Physics, College of Science, Air Force Engineering University, Xi’an, Shaanxi 710051, China (e-mail: liruihu@yahoo.com.cn). Z. Xu is with the College of Science, Xi’an Jiaotong University, Shaanxi 710049, China (e-mail: zbxu@mail.xjtu.edu.cn). X. Zhao is with the Department of Applied Mathematics and Physics, College of Science, Air Force Engineering University, Xi’an, Shaanxi 710051, China (e-mail: zly419@163.com). Communicated by G. Seroussi, Associate Editor for Coding Theory. Digital Object Identifier 10.1109/TIT.2008.926367 0018-9448/$25.00 © 2008 IEEE IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 54, NO. 8, AUGUST 2008 Let F2n be the n-dimensional row vector space over the binary field F2 . A binary linear [n; k] code C is a k -dimensional subspace of F2n . The weight w(x) of x 2C is the number of its nonzero coordinates. A code C is called even if the weights of x 2C are even and odd otherwise. Two binary codes C and C 0 are equivalent if one can be obtained from the other by permuting the coordinates. If two matrices G1 and G2 generate equivalent codes, we denote them as G1 = G2 . The dual code C ? of C is defined as C ? = fx 2 F2n j x 1 y = xy T = 0for all y 2 Cg. A code C is self-orthogonal if C C ? , and self-dual if C = C ? . All SO codes are even, but an even code is not always self-orthogonal. 3779 Lemma 2.1: If k 3, then Dk is invertible over the rational field , and Dk01 = 0 2 1 ((01) 1 ))1i;j 2 01 . And each row (or column) of 2k01 Dk01 has 2k01 1’s and (2k01 0 1) 0 1’s. Proof: Let Ek =0 2 1 ((01) 1 ))1i;j 2 01 ; ai be the ith row of Dk and bm be the mth column of Ek . From the above discussion, it is easy to check that ai bm = 0 1k 2 Definition 1.1: An [n; k] SO code C is called optimal if it has the highest weight among all [n; k] SO codes. Let N (n; k) be the number of nonequivalent optimal [n; k] SO codes, and N0 (n; k) and N1 (n; k) be the number of nonequivalent optimal [n; k] SO codes with zero coordinates and without zero coordinates, respectively. Then N (n; k) =N0 (n; k) +N1 (n; k). If the minimum distance of an optimal [n; k] SO code equal the minimum distance of an optimal [n 0 1; k] SO code, then N0 (n; k) = N (n 0 1; k ), otherwise N0 (n; k ) = 0. Thus, in the following we usually focus on optimal SO codes without zero coordinates. We use Gk to denote the generator matrix of [2k 0 1; k] simplex code, and 1n =(1; 1; 1 1 1 ; 1)12n and 0n =(0; 0; . . . ; 0)12n to denote the all-ones vector and the zero vector of length n, respectively. And use iG = (G; G; 1 1 1 ; G) to denote the juxtaposition of i copies of G for given matrix G. Our main result of this correspondence is as follows. 1 0 2k [ = 0 21k [01 0 (01 + 2k i;m )] 0 1 ( 1) j 0 1( + 0 ( 1) j )] = i;m : Hence, the Lemma holds. Proof of Theorem 1.1: Let G = (l1 1 ; 1 1 1 ; l2 01 2 01 ) be a generator matrix of C . The nonzero weights y1 ; y2 ; . . . ; y2 01 of C are given by y1 y2 l1 l2 = Dk .. . Let zi = yi 0 s2k01 . Then z1 z2 = Dk .. . z2 01 = Dk : .. . l2 01 y2 01 l1 l2 0 Dk .. . s s .. . s l2 01 l1 0 s l2 0 s : .. . l2 01 0 s i.e. l1 0 s l2 0 s .. . II. PROOF OF THEOREM 1.1 In order to prove Theorem 1.1, we need some preparation. Let i be the k -dimensional binary column vector representation of i for 0 i 2k 0 1, i.e., 0 = (0; 0; . . . ; 0)T = 0T k; T T = (0 ; 0 ; . . . ; 1) = (1 ; 1 ; . . . ; 1) , 1 1 1 ; . Then G 1 k = 2 01 k ( 1 ; . . . ; 2 01 ) is a generator matrix of [2 0 1; k ] simplex code. Using the columns of Gk , we construct a (2k 0 1) 2 (2k 0 1) matrix Dk , where Dk = ( 21 (1 0 (01) 1 ))1i;j 2 01 . Let 1 i; j; m 2k 0 1. For each i , there are 2k01 0 1 m ’s such that i 1 m = 0 and 2k01 m ’s such that i 1 m = 1, and if i 6= j , there are 2k02 0 1 m ’s such that i 1 m = j 1 m = 0. Thus each row of Dk has weight 2k01 , and the distance of any two different rows of Dk is 2k01 . Hence, the rows of Dk are just the nonzero vectors of the [2k 0 1; k] simplex code generated by Gk . Suppose G is a generator matrix of an [n; k] code C . If the columns of G have li copies of i for 0 i 2k 0 1, we denote G as G = (l0 0 ; l1 1 ; . . . ; l2 01 2 01 ) for short, and call LGc = (l0 ; l1 ; . . . ; l2 01 ) the complete define vector of G and LG = (l1 ; l2 ; . . . ; l2 01 ) the define vector of G. If the code generated T, by G without zero coordinates, then LGc = LG . Let Y T = Dk LG where Y = (y1 ; y2 ; . . . ; y2 01 ). Then the nonzero weights of C are y1 ; y2 ; . . . ; y2 01 . j 0 (01) 1 ](01) 1 = Theorem 1.1: Suppose k 3; s 1; 1 t 2k 0 2 and n = (2k 0 1)s + t. Then, every [n; k; d] binary code C with d s2k01 and without zero coordinates is equivalent to a code with generator matrix G = ((s 0 c(k; s; t))Gk H ), where c(k; s; t) minfs; tg is a function of k; s and t, and H has (2k 0 1)c(k; s; t) + t columns. According to Theorem 1.1, the classification of [n; k] optimal SO codes can be reduced to the classification of [(2k 0 1)c(k; s; t) + t; k] optimal SO codes. [1 z1 z2 01 = Dk : .. . l2 01 0 s z2 01 Since zi 0, we have li 0 s 0 k101 (z1 + z2 + . . . + z2 01 ) 2 0 2k0 [(y + y + . . . + y 0 ) 0 s2k0 (2k 0 1)] 1 k0 ((2k 0 1)s + t) 0 s2k0 (2k 0 1)] = 0 k0 [2 2 = 0t: Let c(k; s; t) = 0 minfli 0 s j 1 i 2k 0 1g. Then c(k; s; t) minfs; tg, and the conclusion follows. = 1 1 1 2 1 2 1 1 1 1 Using Theorem 1.1, one can deduce the following corollary. Corollary 2.2: If k 3, every [(2k 0 1)s; k; s2k01 ] code is equivalent to the SO code with generator matrix sGk . III. BINARY SELF-ORTHOGONAL CODES AND SYSTEMS OF LINEAR EQUATIONS We will use systems of liner equations to characterize SO codes of given minimum distance, and explain how to determine the generator 3780 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 54, NO. 8, AUGUST 2008 matrices of all [n; 4] optimal SO codes, where n = 15s + t; s 1 and 1 t 14. And, we will give a method of determining c(4; s; t) at the end of this section. Let C = [n; k + 1; 2m] be a SO code. From the definition of equivalence of binary codes, we can assume that C has generator matrix G, where Once R (or Y ) satisfying (1) is given, from [3] and Lemma 3.1, we know that ri + li rj + lj (mod 2), and xi yi for 1 i 7. Thus, WX and L0 can be determined by the following system of linear equations (2): G= 12m 0n02m X Y : L = D01 W x 0(mod 2) x + y 2m; 1 i 7 y 0 x 0; 1 i 7 r + l r + l (mod 2); 1 i; j 7 l 0 = 2 m 0 (l 1 + 1 1 1 + l7 ): T T X i Lemma 3.1: Let C = [n; k + 1; 2m] be a SO code with generator matrix G as above, and let the codes generated by (X Y ); X and Y be C 0 ; C 1 and C 2 , respectively. Then C 0 is an [n; k] SO code, C 1 and C 2 are even codes. And the following holds. 1) If (u j v ) 2 C0 with u 2 C1 and v 2 C2 , then w(u) w(v ). e. 2) d(C1 ) d(C2 ) and d(C2 ) 2d m 2 3) C2 is an [n 0 2m; k] code. Proof: Since C is self-orthogonal, it is obviously that C 0 is an [n; k ] SO code, C 1 and C 2 are even codes. 1) Let (u j v ) 2 C0 with u 2 C1 and v 2 C2 , and w(u) = 2a and w(v) = 2b. Then w(u + 12m j v) = 2m 0 2a + 2b d(C ) = 2m, thus w (u) w (v ). 2) If v1 2 C2 with w(v1 ) = d(C2 ), then there is a u1 2 C1 such that (u1 j v1 ) 2 C0 , and d(C1 ) w (u1 ) w (v1 ) = d(C2 ). Since 2d(C1 ) w (u1 ) + w (v1 ) d(C ) and d(C2 ) is even, thus we e. have d(C2 ) 2d m 2 It is obviously that 3) also holds from the discussion of 1) and 2). Using Lemma 3.1 and the Griesmer bound, one can deduce the following corollary easily. Corollary 3.2: There are no [15s+5; 4; 8s+2] and [15s+12; 4; 8s+6] SO codes. Now, we focus our discussion on [n; 4] optimal SO codes without zero coordinates, where n = 15s + t and s; t 1, and let C = [n; 4; 2m] be such a code. Let G be a generator matrix of C , where G; X; Y as in Lemma 3.1. And, let X = (l0 0 ; l1 1 ; . . . ; l7 7 ) and Y = (r1 1 ; r2 2 ; . . . ; r7 7 ). Then, L0 = (l0 ; l1 ; 1 1 1 ; l7 ) is the complete define vectors of X; L = (l1 ; l2 ; 1 1 1 ; l7 ) and R = (r1 ; r2 ; 1 1 1 ; r7 ) are the define vectors of X and Y , respectively. Since G can be completed determined by (L0 ; R), we call (L0 ; R) the define vectors of G. Let WXT =D3 LT and WYT = D3 RT , where WX = (x1 ; x2 ; . . . ; x7 ) and WY = (y1 ; y2 ; . . . ; y7 ). Then, we change the problem of determine G into that of determine X and Y (or (L0 ; R)). Since GL(3; 2) acts double transitively on f 1 ; 1 1 1 ; 7 g, so, in the following, we can assume r1 r2 ri ; i = 3; 4; 1 1 1 ; 7, and r4 rj , j = 5; 6; 7 as in [3]. Since y1 + y2 + 1 1 1 + y7 = 4(n 0 2m), we have the following system of linear equations: i i i i i i j (2) j Then, X exists if and only if (2) has nonnegative integer solutions. Thus, one can easily determine all the possible X by the nonnegative integer solutions of (2), and determine all the possible generator matrix G of [n; 4; 2m] optimal SO codes at last. For given s 1 and 1 t 14. Denote the set of all the generator matrix G (determined above) of [15s + t; 4] optimal SO codes as G [15s + t; 4], and let D[15s + t; 4] = f(L0 ; R) j (L0 ; R) is the define vectors of G; G 2 G [15s + t; 4]g. Then c(4; s; t) = 0 min0i7;1j7fli 0 s; rj 0 s j (L0; R) 2 D[15s + t; 4]g. IV. CLASSIFICATION OF FOUR-DIMENSIONAL (4-D) OPTIMAL SO CODES In this section, we will study the classification of optimal [n; 4] SO codes for n = 15s + t; s 1 and t 2 f1; 2; 6; 7; 8; 9; 13; 14g. According to Corollary 2.2 and 3.2, and the relations among N (n; k); N0 (n; k); N1 (n; k) and N (n 0 1; k), we only need to give N1 (n; 4). To save space, we only explain our classification process for [15s + 1; 4] OSO codes, other case can be deduced similarly. And, we use OSO codes to represent optimal SO codes without zero coordinates in this section. Case 1: n = 15s + 1; s 1. A [15s + 1; 4] OSO code has minimum distance 8s. Using MATLAB [8] program, one can easily check that there are seven solutions satisfying (1) and (2), thus D [15s + 1; 4] has seven elements, denoted as (L0i ; Ri ) = (s18 ; s17 ) + (L00i ; Ri0 ), 0 0 1 i 7, where L01 = (01; 1; 1, 01; 1; 01; 01; 1) = 0L02 , 0 0 0 0 L03 = 08 , L04 = (1; 01; 01; 1; 0; 0; 0; 0) = 0L05 , L06 = 0 = (0; 0; 0; 0; 1; 01; 01; 1), Ri0 = (1; 1; 01; 1; 01; 01; 1) for 0L07 0 1 i 3, and Ri = (1; 1; 01; 0; 0; 0; 0) for 4 i 7. Thus c(4; s; 1) = 1. Accordingly, the generator matrices Gn(i) , 1 i 7, of these 7 OSO codes are determined. Let the define vectors of H16;j be (L0;j ; R) and Gn;j = ((s 0 1)G4 H16;j ); j = 1; 2,where L0;1 = (0; 2; 2; 0; 2; 0; 0; 2); L0;2 = (1; 1; . . . ; 1); R = (2; 2; 0; 2; 0; 0; 2). It is easy to check that Gn(i) = Gn;1 for 1 i 2, and Gn(i) = Gn;2 for 3 i 7. Thus, we have the following theorem. (1) Theorem 4.1: If n = 15s + 1; s 1, then N1 (n; k) = 2. The two nonequivalent [n; 4; 8s] OSO codes have generate matrices Gn;1 and Gn;2 , their weight polynomials are 1 + 14y8s + y8s+8 and 1 + 13y8s + 8s+4 , respectively. 2y For each given WY = (y1 ; y2 ; 1 1 1 ; y7 ) satisfying y1 + y2 + 1 1 1 + y7 = 4(n 0 d(C )), yi 0(mod 2) and yi d(C2 ) for 1 i 7, such Y exists if and only if (1) has nonnegative integer solutions. Thus, one can easily determine all the possible Y (or R) by the nonnegative integer solutions of (1). Let the define vectors of H17;i be (L0;i ; R1 ) and H32;i = ((s 1)G4 H17;i ) for i = 1; 2, where L0;1 and L0;2 as in Case 1, and R1 = (3; 1; . . . ; 1). j 9, Let the define vectors of H32;j be (L0;j ; Rj ) for 3 where L0;3 = (2; 2; . . . ; 2) = L0;7 ; L0;4 = (0; 3; 3; 2; 3; 2; 2; 1); L0;5 = (0; 4; 3; 1; 3; 1; 2; 2); L0;6 = (0; 3; 3; 2; 3; 2; 3); L0;8 = (3; 1; 1; 3; 1; 3; 3; 1); L0;9 = (0; 4; 4; 0; 4; 0; 0; 4); R3 = R = D301 W y 0(mod2); i = 1; 2; 1 1 1 ; 7 2d 2 e y n 0 2m y1 + y2 + 1 1 1 + y7 = 4(n 0 2m) r1 r 2 r ; i = 3 ; 4; 1 1 1 ; 7 r 4 r ; j = 5 ; 6; 7: T T Y i m i i j Case 2: n = 15s + 2; s 1. 0 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 54, NO. 8, AUGUST 2008 (4; 4; 0; 2; 2; 2; 2); R4 = (3; 3; 2; 3; 2; 2; 1); R5 = (4; 3; 1; 3; 1; 2; 2); R6 = (3; 3; 2; 3; 2; 3); R7 = (4; 4; 0; 4; 0; 0; 4) = R8 = R9 . If s 2, let Gn;l = ((s 2)G4 H32;l ) for 1 l 9. 0 Theorem 4.2: Let n = 15s + 2; s 1. 1) If s = 1, then N1 (17; 4) = 2. The two [17; 4; 8] OSO codes have generate matrices H17;1 and H17;2 , and have weight polynomials 8 12 8 10 1 + 11y + 4y and 1 + 7y + 8y , respectively. 2) If s 2, then N1 (n; 4) = 9. The nine nonequivalent [n; 4; 8s] OSO have generate matrices Gn;i ; 1 i 9, their weight polynomials are 1 + 11y 8s + 4y 8s+4 , 1 + 7y 8s + 8y 8s+2 , 1 + 11y 8s + 8s+4 , 1 + 11y 8s + 4y 8s+4 , 1 + 12y 8s + 2y 8s+4 + y 8s+12 , 4y 8s 8s+4 8s+12 1 + 12y + 2y +y , 1 + 13y 8s + 2y 8s+8 , 1 + 13y 8s + 8s+4 8s+12 y +y , 1 + 14y 8s + y 8s+16 , respectively. Case 3: n = 15s + 6; s 1. Let the define vectors of H21 be (L0;a ; Ra ) and H36;1 = (G4 H21 ), where L0;a = (1; 2; 2; 1; 2; 1; 1; 0), Ra = (2; 2; 1; 2; 1; 1; 2). Let the define vectors of H36;2 be (L0;b ; Rb ), where L0;b = (3; 2; 2; 3; 2; 3; 3; 0), Rb = (3; 3; 2; 3; 2; 2; 3). For s 2, let Gn;i = ((s 0 2)G4 H36;i ); 1 i 2. Theorem 4.3: Let n = 15s + 6; s 1. 1) If s = 1, then N1 (n; 4) = 1. The [21; 4; 10] OSO code has generate matrix H21 and weight polynomial 1+8y 10 +6y 12 +y 16 . 2) If s 2, then N1 (n; 4) = 2. The two nonequivalent [n; 4; 8s + 2] OSO codes have generate matrices Gn;1 and Gn;2 , and their weight polynomials are 1 + 8y 8s+2 + 6y 8s+4 + y 8s+8 and 1 + 8s+2 8s+4 8s+6 7y + 7y +y , respectively. Case 4: n = 15s + 7; s 1. Let the define vectors of H22;i be (L01;i ; Ri ) and H37;i = i 6, where L01;1 = (1; 2; 2; 1; 2; 1; 1; 0), (G4 H22;i ); 1 L01;2 = (0; 3; 3; 0; 3; 0; 0; 1), L01;3 = (1; 2; 2; 1; 1; 0; 0; 3), L01;4 = (2; 1; 1; 2; 2; 1; 1; 0), L01;5 = (2; 0; 2; 2; 2; 2; 0; 0),L01;6 = (1; 2; 1; 2; 1; 2; 1; 0), R1 = (3; 3; 0; 3; 0; 0; 3) = R2 , R3 = (3; 3; 0; 2; 1; 1; 2) = R4 , R5 = (2; 2; 2; 2; 2; 2; 0), R6 = (3; 2; 1; 2; 1; 2; 1). j 8, Let the define vectors of H37;j be (L02;j ; Rj ) for 7 where L02;7 = (3; 2; 2; 3; 2; 3; 3; 0), L02;8 = (2; 3; 3; 2; 2; 3; 3; 0), R7 = (4; 4; 1; 4; 1; 1; 4), R8 = (4; 4; 1; 3; 2; 2; 3). Let the define vectors of H52;l be (L03;l ; Rl ) for 9 l 12, where L03;9 = (5; 2; 2; 5; 2; 5; 5; 0), L03;10 = (4; 3; 3; 4; 2; 5; 5; 0), L03;11 = (3; 4; 3; 4; 3; 4; 5; 0), L03;12 = (2; 4; 4; 4; 4; 4; 4; 0), R9 = (5; 5; 2; 5; 2; 2; 5), R10 = (5; 5; 2; 4; 3; 3; 4), R11 = (5; 4; 3; 4; 3; 4; 3), R12 = (4; 4; 4; 4; 4; 4; 2). m 8, and Gn;p = ((s Let H52;m = (G4 H37;m ) for 1 3)G4 H52;p ) for s 3 and 1 p 12. j j = 15 + 7 1. 0 Theorem 4.4: Let n s ;s 1) If s = 1, then N1 (22; 4) = 6. The six nonequivalent [22; 4; 10] OSO codes have generate matrix H22;i , 1 i 6, and their weight polynomials W22;i are 1 + 7y 10 + 6y 12 + y 16 + y 18 , 10 12 22 10 12 14 18 1 + 7y + 7y + y , 1 + 6y + 7y +y +y , 1+ 10 12 14 16 10 12 14 20 + 6y + 2y + y , 1 + 6y + 6y + 2y + y , 6y 10 12 14 1 + 5y + 7y + 3y , respectively. 2) If s = 2, then N1 (37; 4) = 8. The eight nonequivalent [37; 4; 18] OSO codes have generate matrices H37;j ; 1 j 8, their weight polynomials W37;j are W37;i = 1 + y 8 (W22;i 0 1) for 1 i 6, and W37;7 = 1 + 7y 18 + 6y 20 + y 22 + y 28 , W37;8 = 1 + 7y 18 + 20 22 24 5y + y + 2y , respectively. 3) If s 3, then N1 (n; 4) = 12. The twelve nonequivalent [n; 4; 8s + 2] OSO codes have generate matrices Gn;l ; 1 l 12, their weight polynomials Wn;l are 3781 Wn;j = 1 + y 8s+4 8(s 02) (W37 0 1) for 1 j 8, and 1 + 8y8 +2 + ;j 8s+16 s 8s+2 8s+4 8s+8 8s+12 6y + y ; 1 + 8y + 5y + y + y , 8s+2 8s+4 8s+8 1 + 8y + 4y + 3y , 1 + 8y 8s+2 + 4y 8s+4 + 3y 8s+8 , respectively. Case 5: n = 15s + 8; s 1. Theorem 4.5: If n = 15s +8; s 1, then N (n; 4) =N1 (n; k) = 1. The only [n; 4; 8s + 4] OSO code is the juxtaposition of s-copies of simplex codes and the [8; 4; 4] self-dual code, and has weight polynomial 1 + 14y 8s+4 + y 8s+8 . Case 6: n = 15s + 9; s 1. Let the define vectors of H24;i be (L0i;c ; Ri;c ) and Gn;i = (G4 H24;i ), 1 i 4, where L01;c = (3; 0; 0; 3; 0; 3; 3; 0), L02;c = (2; 1; 1; 2; 1; 2; 2; 1), L03;c = (2; 1; 1; 2; 2; 1; 1; 2), L04;c = (0; 3; 3; 0; 3; 0; 0; 3), R1;c = R2;c = R4;c = (3; 3; 0; 3; 0; 0; 3), R3;c = (3; 3; 2; 1; 1; 2). Theorem 4.6: If n = 15s + 9 and s 1, then N1 (n; 4) = 4. The four nonequivalent [n; 4; 8s + 4] OSO codes have generator matrices 8s+4 Gn;i ; 1 i 4, and their weight polynomials are 1 + 14y + 8s+16 8s+4 8s+8 8s+12 8s+4 8s+8 y , 1 + 13y +y +y , 1 + 12y + 3y , and 8s+4 8s+8 1 + 12y + 3y , respectively. Case 7: n = 15s + 13; s 1. Let the define vectors of H28 be (L0;d ; Rd ) and Gn = ((s 0 1)G4 j for s 1, where L0;d = (0; 2; . . . ; 2); Rd = (2; . . . ; 2). H28 ) Theorem 4.7: If n = 15s + 13; s 1, then N1 (n; k) = 1. The only [n; 4; 8s + 6] SO code has generator matrix Gn , and has weight polynomial 1 + 8y 8s+6 + 7y 8s+8 . Case 8: n = 15s + 14; s 1. Let the define vectors of H29;i be (L01;e ; Ri;e ) and H44;i = (G4 H29;i ) for 1 i 3, where L01;e = (3; 1; 1; 3; 1; 3; 1; 1), L02;e = (2; 2; 2; 2; 3; 1; 1; 1), L03;e = (0; 2; 2; . . . ; 2), R1;e = R3;e = (3; 3; 1; 3; 1; 1; 3), R2;e = (3; 3; 1; 2; 2; 2; 2). Let the define vectors of H44;l be (L0l;e ; Rl;e ) for 4 l 5, where L04;e = (0; 4; 4; 2; 4; 2; 2; 4) = (0; R4;e ), L05;e = (0; 4; 4; 2; 3; 3; 3; 3) = (0; R5;e ). Let Gn;m = ((s 2)G4 H44;m ) for s 2 and 1 m 5. 0 Theorem 4.8: Let n = 15s + 14; s 1 as follows. 1) If s = 1, then N1 (n; 4) = 3, the three nonequivalent [29; 4; 14] OSO codes have generate matrix H29;1 ; H29;2 and H29;3 , and their weight polynomials are 1 + 7y 14 + 7y 16 + y 22 , 1 + 6y 14 + 16 18 14 16 18 20 7y + 2y , 1 + 7y + 6y + y + y , respectively. 2) If s 2, then N1 (n; 4) = 5. The five nonequivalent [n; 4; 8s +6] OSO codes have generator matrices Gn;i , 1 i 5, and their weight polynomials are 1 + 7y 8s+6 + 7y 8s+8 + y 8s+14 , 1 + 8s+6 8s+8 8s+10 6y + 7y + 2y , 1 + 7y 8s+6 + 6y 8s+8 + y 8s+10 + 8s+12 8s+6 8s+8 8s+16 , 1 + 8y + 6y y +y , 1 + 8y 8s+6 + 5y 8s+8 + 8s+12 2y , respectively. V. CONCLUSION We have given the complete classification of [15s + t; 4] optimal SO codes for s 1 and t 2 f1; 2; 6; 7; 8; 9; 13; 14g. Our classification results of optimal [n; 4] SO codes for n 40 in Section IV are concordant with the results of [3]. For t 2 f3; 4; 5; 10; 11; 12g and s 1, the classification of [15s + t; 4] optimal SO codes can also be given as in Section IV, but a little complex and lengthy, we will discuss in another paper. The method we used in Section III can be generalized to [n; k] optimal SO codes for k 4. 3782 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 54, NO. 8, AUGUST 2008 ACKNOWLEDGMENT The authors are very grateful to an anonymous referee for the proofs of Lemma 2.1 and Theorem 1.1 which simplifies the original proofs. REFERENCES [1] S. Bouyuklieva, “Some optimal self-orthogonal codes and self-dual codes,” Discr. Math., vol. 287, pp. 1–10, 2004. [2] I. Bouyukliev and P. Ostergard, “Classification of self-orthogonal codes over F and F ,” SIAM J. Discr. Math., vol. 19, no. 2, pp. 363–370, 2005. [3] I. Bouyukliev, S. Bouyuklieva, T. A. Gulliver, and P. Ostergard, Classification of Optimal Binary Self-Orthogonal Codes. [Online]. Available: http://users.tkk.fi/pat/patric-pub-html [4] W. C. Huffman, “On the classification and enumeration of self-dual codes,” Finite Fields Appl., vol. 11, pp. 451–490, 2005. [5] W. C. Huffman and V. Pless, Fundmentals of Error-Correcting Codes. Cambridge, U.K.: Cambridge University Press, 2003. [6] V. Pless, “A classification of self-orthogonal codes over GF (2),” Discr. Math., vol. 3, pp. 209–246, 1972. [7] E. M. Rains and N. J. A. Sloane, “Self-Dual Codes,” in Handbook of Coding Theory, W. C. Huffman and V. S. Pless, Eds. Amsterdam, The Netherlands: Elsevier, 1998, pp. 177–294. [8] The MathWorks, MATLAB R2006a, Natick, MA, 2006. The Icosian Code and the Lattice: A New Space–Time Code With Nonvanishing Determinant Jiaping Liu and A. Robert Calderbank, Fellow, IEEE Abstract—This paper introduces a new rate-2, full-diversity space–time code for four transmit antennas and one receive antenna. The 4 4 codeword matrix consists of four 2 2 Alamouti blocks with entries from Q(i; 5), and these blocks can be viewed as quaternions which in turn represent rotations in R . The Alamouti blocks that appear in a codeword are drawn from the icosian ring consisting of all linear combinations of 120 basic rotations corresponding to symmetries of the icosahedron. This algebraic structure is different from the Golden code, but the complex entries are taken from a common underlying field. The minimum determinant is bounded below by a constant that is independent of the signal constellation, and the new code admits a simple decoding scheme that makes use of a geometric correspondence between the icosian ring and the E lattice. p 2 2 Index Terms—Space–time codes, icosian ring, Gosset lattice E , reduced complexity decoding algorithms. I. INTRODUCTION Space–time codes improve the reliability of communication systems over fading channels by correlating signals across different transmit antennas. Tarokh et al. [1] developed the following two design criteria for the high SNR regime. • Rank Criterion: Maximize the minimum rank r of the difference Xi 0 Xj over all distinct pairs of space–time codewords Xi ; Xj ; the space–time code achieves a diversity gain of r . Manuscript received September 2, 2006; revised February 5, 2008. This work was supported in part by the National Science Foundation under Contract 1096066. The material in this correspondence was presented in part at the IEEE International Symposium on Information Theory, Seattle, WA, July 2006. The authors are with the Department of Electrical Engineering, Princeton University, Princeton, NJ 08544 (e-mail: jiapingl@princeton.edu; calderbk@ princeton.edu). Communicated by G. Seroussi, Associate Editor for Coding Theory. Color versions of Figures 1–3 in this correspondence are available online at http://ieeexplore.ieee.org. Digital Object Identifier 10.1109/TIT.2008.926352 • Determinant Criterion: For a given diversity r , maximize the minimum product of the nonzero singular values of the difference Xi 0 Xj over all distinct pairs of space–time codewords Xi ; Xj ; the product determines the coding gain of the spacetime code. The construction of space–time block codes that achieve particular rate–diversity tradeoffs is an area of intense research activity (see [2]–[9]), and many authors have used algebraic techniques to guarantee full diversity (see the monograph by Viterbo and Oggier [10] connecting algebraic number theory to code design for Rayleigh-fading channels). We will follow this approach to get full diversity, and in addition, we will use the algebraic techniques to introduce a geometric structure that simplifies decoding. Conway and Sloane [12] connected the geometry of finite-dimensional lattices with signal constellation design for the additive white Gaussian noise channel. The lattice/coset framework provides solutions to the problem of addressing the signal constellation at the encoder and the problem of decoding the received vector to the closest lattice point at the decoder. We are able to simplify decoding of the new space–time block code by associating constituent Alamouti blocks with vectors in the Gosset lattice E8 and then applying the E8 decoding algorithms developed by Conway and Sloane. The new code is described by a 4 2 4 matrix for four transmit antennas and one receive antenna for the implementation of its low-complexity decoding algorithm. It contains four 2 2 2 Alamouti blocks, each of which is the quaternionic form of an icosian. The algebraic structure of the code is similar to the Golden code p [2] ofpBelfiore et al. in that algebraic conjugation interchanging p5 and 0 5 appears as the isomorphism of the Galois extension Q(i; 5)=Q(i) used in the construction of the Golden code. The codeword matrix takes the form X= A B B 1 K A where information symbols A and B are icosians in Alamouti blocks B are the algebraic conjugates of A; B . Moreover, a “magic and A; K ” which is also an Alamouti block of an icosian will be chosen to guarantee full diversity. A similar approach to increasing diversity by rotation is given by Jafarkhani for his quasi-orthogonal code design [5]. The correspondence is organized as follows. Section II introduces the icosian ring and derives some important properties. Section III gives the construction of the new 4 2 4 Space–Time Block Code (STBC) based on the icosian ring and establishes full diversity. Section IV develops a coherent decoding scheme with reduced complexity, using the correspondence of the icosian ring with the E8 lattice. Simulation results are presented in Section V and conclusions are given in Section VI. II. THE ICOSIAN RING AND THE LATTICE E8 We assume a basic familiarity with quaternion algebra, including the classical two-to-one correspondence between unit quaternions and rotations in SO3 , and we refer readers interested in more details to Conway and Sloane [12, pp. 52–55]. Definition 1: The double cover 2I of the icosahedral group is a multiplicative group of order 120 consisting of the quaternions 1 1 (61; 0; 0; 0)E ; (61; 61; 61; 61)E ; (0; 61; 6; 6 )E 2 2 p p where ( ; ; ; ) means + i + j + k; = 102 5 ; = 1+2 5 , and the superscript E means that all even permutations of the coordinates are permitted. 0018-9448/$25.00 © 2008 IEEE