Data Loading...
Square Designs on New Binary 23 Codes - HIKARI Flipbook PDF
Square designs on new binary codes 187 deleting the same row of Pn, the matrix Cn of order 3 n−1 2 × n−1 2 is obtained.
120 Views
17 Downloads
FLIP PDF 85.79KB
International Mathematical Forum, Vol. 6, 2011, no. 4, 185 - 191
Square Designs on New Binary ( 3 2−1 , 3 2−1 , 2.3n−2) Codes n
n
Manjusri Basu Department of Mathematics University of Kalyani Kalyani, W.B, India, Pin-741235 manjusri− [email protected] Satya Bagchi Department of Mathematics National Institute of Technology, Durgapur Burdwan, W.B, India, Pin-713209 [email protected] Debabrata Kumar Ghosh Department of Mathematics University of Kalyani Kalyani, W.B, India, Pin-741235 [email protected] Abstract C is an (n, M, d)q code over Fq of length n with M codewords and minimum distance d. The code C can be either linear or nonlinear. A t − (v, k, λ) design D is a set X of v points together with a collection of k−subsets of X (called block) such that every t−subset of X is contained in exactly λ blocks. In this paper a new binary code n n ( 3 2−1 , 3 2−1 , 2.3n−2 ), n ≥ 3 is developed. Some properties of this code n are stated. It is also shown that this code holds 2 − ( 3 2−1 , 3n−1 , 2.3n−2 ) design.
Keywords: Linear code, constant weight code, support, complement code, t-design
1
Introduction
Let Fqn denote the linear space of all n-tuples over the finite field Fq = GF (q). An (n, M) code C over Fq is a subset of Fqn of size M. If C is a k-dimensional
186
M. Basu, S. Bagchi and D. K. Ghosh
subspace of Fqn , C is called an [n, k] linear code over Fq . The field F2 is very special in coding theory, and codes over F2 are called binary codes. Codes over F3 are called ternary codes, and codes over F4 are called quaternary codes and so on. Thus codes over Fq are called q−ary codes. It is natural to expect that for some integers n and d there exists an (n, M, d)q nonlinear q-ary code of length n with minimum distance d whose number of codewords M is greater than the number of codewords of any linear q-ary code of length n and minimum distance d. In ternary q = 3, C is an (n, M, d)3 nonlinear code [6]. Due to the rapid growth of applications of design theory in modern science, various type of new codes holding with designs are coming up in the literature [1,2,4,5,7,10]. In this paper, a systematic new binary code n n ( 3 2−1 , 3 2−1 , 2.3n−2 ), n ≥ 3 is defined. The different properties of this code are n stated and proved. It is also shown that this code holds 2 − ( 3 2−1 , 3n−1 , 2.3n−2 ) design.
2
Definitions
Definition 2.1 Complement of a Binary code[3]: The complement of a binary code C is the binary code C + 1, where 1 is the all one codeword; so the complement of C is the code obtained from C by replacing 1 by 0 and 0 by 1. Definition 2.2 Support[8]: Let c be a binary codeword of length n. The set of positions in which c has nonzero entries is called support of c. Definition 2.3 Design[9]: Let C be a binary code of length n. Let Sk be the set of codewords in C of weight k. We say that Sk holds a t−(n, k, λ) design if the supports of codewords in Sk form the blocks of a t − (n, k, λ) design, if for any t-set T ⊂ {1, 2, · · · , n} there are exactly λ codewords of weight k in C with 1’s in the positions given by T. A t−(v, k, 1) design is defined as a Steiner System and denoted by S(t, k, v).
3
The new code Cn(n ≥ 3)
Let An (n ≥ 3) be a matrix of order n × (3n − 1) in F3 . The columns of An are all ternary codewords of length n except all zero codeword 0. n The matrix Gn of order n× 3 2−1 in F3 is obtained after deleting the linearly dependent columns of An . n Now the matrix Pn of order (3n − 1) × 3 2−1 is generated by Gn in F3 except 0 codeword. In Pn , 1 is taken in place of 2. So Pn has each row twice. After
187
Square designs on new binary codes
deleting the same row of Pn , the matrix Cn of order Hence the new code Cn is constructed. For example: When n = 3,
3n −1 2
×
3n −1 2
⎛
is obtained.
⎞
1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 ⎜ ⎟ A3 = ⎝ 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2 ⎠ . 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 After deleting the linearly dependent columns of A3 , ⎛
⎞
1 0 1 2 0 1 2 0 1 2 0 1 2 ⎜ ⎟ G3 = ⎝ 0 1 1 1 0 0 0 1 1 1 2 2 2 ⎠ . 0 0 0 0 1 1 1 1 1 1 1 1 1 After deleting 0 codeword from the code generated by G3 , ⎛
P3 =
⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝
1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2
0 1 0 0 1 1 2 2 2 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2
1 1 0 0 1 1 2 2 2 1 1 2 2 2 0 0 0 2 2 2 0 0 0 1 1 1
2 1 0 0 1 1 2 2 2 2 2 0 0 0 1 1 1 1 1 1 2 2 2 0 0 0
0 0 1 2 1 2 0 1 2 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2
1 0 1 2 1 2 0 1 2 2 0 1 2 0 1 2 0 2 0 1 2 0 1 2 0 1
2 0 1 2 1 2 0 1 2 0 1 2 0 1 2 0 1 1 2 0 1 2 0 1 2 0
0 1 1 2 2 0 2 0 1 1 2 1 2 0 2 0 1 0 1 2 1 2 0 2 0 1
1 1 1 2 2 0 2 0 1 2 0 2 0 1 0 1 2 2 0 1 0 1 2 1 2 0
2 1 1 2 2 0 2 0 1 0 1 0 1 2 1 2 0 1 2 0 2 0 1 0 1 2
0 2 1 2 0 1 1 2 0 1 2 2 0 1 1 2 0 0 1 2 2 0 1 1 2 0
1 2 1 2 0 1 1 2 0 2 0 0 1 2 2 0 1 2 0 1 1 2 0 0 1 2
2 2 1 2 0 1 1 2 0 0 1 1 2 0 0 1 2 1 2 0 0 1 2 2 0 1
⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟. ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠
Replacing 2 by 1 and deleting the same rows of P3 , the new code
188
M. Basu, S. Bagchi and D. K. Ghosh
⎛
C3 =
⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝
1 1 1 1 1 1 1 1 1 0 0 0 0
1 1 1 1 1 1 0 0 0 1 1 1 0
1 1 1 0 0 0 1 1 1 1 1 1 0
0 0 0 1 1 1 1 1 1 1 1 1 0
1 1 0 1 1 0 1 1 0 1 1 0 1
1 0 1 1 0 1 1 0 1 1 1 0 1
0 1 1 0 1 1 0 1 1 1 1 0 1
1 0 1 0 1 1 1 1 0 1 0 1 1
0 1 1 1 1 0 1 0 1 1 0 1 1
1 1 0 1 0 1 0 1 1 1 0 1 1
0 1 1 1 0 1 1 1 0 0 1 1 1
1 1 0 0 1 1 1 0 1 0 1 1 1
1 0 1 1 1 0 0 1 1 0 1 1 1
0 1 0 0 1 0 0 1 0 0 0 1 0
1 0 0 1 0 0 1 0 0 0 0 1 0
0 1 0 1 0 0 0 0 1 0 1 0 0
1 0 0 0 0 1 0 1 0 0 1 0 0
0 0 1 0 1 0 1 0 0 0 1 0 0
1 0 0 0 1 0 0 0 1 1 0 0 0
0 0 1 1 0 0 0 1 0 1 0 0 0
0 1 0 0 0 1 1 0 0 1 0 0 0
⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟. ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠
The complement code C3c of C3 is ⎛
C3c =
⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝
0 0 0 0 0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 1 1 1 0 0 0 1
0 0 0 1 1 1 0 0 0 0 0 0 1
1 1 1 0 0 0 0 0 0 0 0 0 1
0 0 1 0 0 1 0 0 1 0 0 1 0
⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟. ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠
Similarly Cn and Cnc can be constructed for all values of n.
4
Properties Property 4.1 The code Cn is a nonlinear code.
Property 4.2 The code Cn = Cn , where Cn is the square matrix of order obtained by re-arranging the columns of Cnt , the transpose of Cn . 2
3n −1
Property 4.3 Distance of any two different codewords of Cn is 2.3n−2 . Proof: Any two columns of the matrix Pn are linearly independent. In the matrix Pn , only 3n−2 − 1 rows of any two columns have consecutive 0’s, 4.3n−2 rows of any two columns have consecutive nonzero and the rest 4.3n−2 =
189
Square designs on new binary codes
(3n − 1) − (3n−2 − 1) − 4.3n−2 rows of any two columns have one zero and one nonzero. n Now after replacing 2 by 1 and deleting 3 2−1 identical rows of Pn , Cn is n−2 obtained. Thus in Cn , any two columns have consecutive 0’s in 3 2 −1 rows, n−2 consecutive 1’s in 2.3n−2 (= 4.32 ) rows and one 0 and one 1 in 2.3n−2 rows. Hence by property 2, distance of any two different codewords of Cn is 2.3n−2 . Property 4.4 Weight of each codeword of the code Cn is 3n−1 . Proof: Pn including 0 codeword is a linear code. So in each column of Pn , the numbers of 0’s, 1’s and 2’s are 3n−1 − 1, 3n−1 and 3n−1 respectively. After replacing 2 by 1, the numbers of 0’s and 1’s are 3n−1 − 1 and 2.3n−1 respectively in each column of Pn . After deleting the same row of Pn , the n−1 numbers of 0’s and 1’s are reduced to 3 2 −1 and 3n−1 respectively. Hence by property 2, the weight of each codeword of Cn is 3n−1 . Property 5 and property 6 follow from property 4: Property 4.5 Weight of the every codeword c + 1 (c ∈ Cn ) of the complen−1 ment codeword Cnc of Cn is 3 2 −1 . Property 4.6 The code Cn is a 3n−2 -error correcting code. n −1
Hence the new code Cn ( 3
5
2
n −1
,3
2
, 2.3n−2 ) is defined for n ≥ 3.
Main Results n
n
n
Theorem 5.1 The code Cn ( 3 2−1 , 3 2−1 , 2.3n−2 ) holds 2−( 3 2−1 , 3n−1 , 2.3n−2 ) design, n ≥ 3. n Proof: The length and weight of each codeword of Cn are 3 2−1 and 3n−1 respectively. Also by property 3, in any two columns of Cn there are 2.3n−2 consecutive 1’s. n n n Hence the code Cn ( 3 2−1 , 3 2−1 , 2.3n−2 ) holds 2−( 3 2−1 , 3n−1 , 2.3n−2 ) design, n ≥ 3. n −1
Theorem 5.2 The code Cn ( 3 3.
2
n −1
,3
2
, 2.3n−2 ) does not hold 3-design, n ≥
Proof: Considering 1st , 2nd and 3rd columns of C3 , there are three consecutive 1’s. But considering 1st , 2nd and 5th columns of C3 , there are four consecutive 1’s. So the code C3 does not hold 3−design. Hence the code Cn does not hold 3−design.
190
M. Basu, S. Bagchi and D. K. Ghosh n
n
n
n−1 −1
Theorem 5.3 The complement code Cnc ( 3 2−1 , 3 2−1 , 2.3n−2 ) hold 2−( 3 2−1 , 3 3n−2 −1 ) design, n ≥ 3. 2 n Proof: The length and weight of the complement code Cnc of Cn are 3 2−1 n−1 and 3 2 −1 respectively. By property 3 any two columns of the matrix Cnc have 3n−2 −1 consecutive 1’s. 2 Hence the theorem. For n = 3, C3c holds Steiner System, e.i. C3c holds S(2, 4, 13). n
n
Theorem 5.4 The complement code Cnc ( 3 2−1 , 3 2−1 , 2.3n−2 ) does not 3-design, n ≥ 3. Proof: Considering 10th , 11th and 12th columns of C3c , there is no secutive 1’s. But considering 11th, 12th and 13th columns of C3c , there consecutive 1’s. So the code C3c n ≥ 3 does not hold 3−design. Hence the Cnc does not hold 3−design.
6
hold conis a code
Conclusion
There are close relations between design theory and coding theory. In recent years, design theory has grown up tremendously with computer science. Also it has become necessary for interdisciplinary research with pure and applied mathematics groups, industrial groups etc.
References [1] M. Basu, Md. M. Rahaman and S. Bagchi, On a new code, [2n , n, 2n−1 ], Discrete Applied Mathematics, 175 (2009), 402-405. [2] I. Bouyukliev, V. Fack, and J. Winne, 2-(31,15,7), 2-(35,17,8) and 2(36,15,6) designs with automorphisms of odd prime order, and their related Hadamard matrices and codes, Design, Codes and Cryptography, 51 (2009), 105-122. [3] W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes, Cambridge, 2004. [4] D. R. Hughes and F. C. Piper, Design Theory, Cambridge University Press, Cambridge, 1985. [5] Y. J. Ionin and H. Kharaghani, A Recursive Construction for New Symmetric Designs, Designs, Codes and Cryptography, 35 (2005), 303-310.
2
,
Square designs on new binary codes
191
[6] S. Ling and C. Xing, A first course of coding theory, National University of Singapore, 2004. [7] P. R. J. Ostergard, A 2-(22, 8, 4) Design Cannot Have a 2-(10, 4, 4) Subdesign, Designs, Codes and Cryptography, 27 (2002), 257-260. [8] V. S. Pless and W.C. Huffman, Handbook of coding theory Vol. II, North Holland, 1998. [9] S. Roman, Coding and Information Theory, Springer, 1991. [10] D. J. Shin, P. V. Kumar and T. Helleseth, 3-Designs from the Z4 -Goethals Codes via a New Kloosterman Sum Identity, Designs, Codes and Cryptography, 28 (2003), 247-263. Received: July, 2010