Paper Menu >>
Journal Menu >>
 Open Journal of Applied Sciences, 2013, 3, 27-31 doi:10.4236/ojapps.2013.31B1006 Published Online April 2013 (http://www.scirp.org/journal/ojapps) Images of Linear Block Codes over qqq q F uF vFuvF Jane D. Palacio, Virgilio P. Sison Institute of Mathematical Sciences and Physics, University of the Philippines Los Baños, College, Laguna, Philippines Email: [email protected], [email protected] Received 2013 ABSTRACT In this paper, we considered linear block codes over 22 ,0, qqq qq RFuFvFuvFuv uvvu where , m qp m . First we looked at the structure of the ring. It was shown that is neither a finite chain ring nor a principal ideal ring but is a local ring. We then established a generator matrix for the linear block codes and equipped it with a homogeneous weight function. Field codes were then constructed as images of these codes by using a basis of over q R q R q F . Bounds on the minimum Hamming distance of the image codes were then derived. A code meeting such bounds is given as an example. Keywords: -ary Images; Distance Bounds q 1. Introduction Let be a prime number, p,m and q m qp F de- note the Galois field with elements. During the late 1990s, C. Bachoc used linear block codes over , q p p F uF 2 u0 for constructing modular lattices. Its success motivated the study of linear block codes over the finite chain ring p p F uF. And many of the results from these studies have been extended over finite chain rings of the form 21 ..., 0, rr qq qq FuFuFuFu r . Such rings can be seen as natural extensions of qq F uF . Another ring extension of qq F uF is qqq q RFuFvFuvFq where Unlike 22 0, .uv uvvu, qq F uF is neither q R a finite chain ring nor a principal ideal ring. B. Yildiz and S. Karadeniz introduced linear block codes over the ring 222 2 F uF vF uvF in [6]. Self-dual codes, cyclic codes and constacyclic codes over this ring were also studied by these authors in [3,7,8]. In 2011, X. Xu and X. Liu studied the structure of cyclic codes over in [5]. q R In this work, we will analyze linear block codes over q R. The structure of the ring will be discussed in Section 2. The generator matrix of linear block codes over and weight functions defined on will be tackled in q R q R Section 3. The -ary images of these linear block codes and bounds on its minimum Hamming distance will be presented in Sections 4 and 5, respectively. Lastly, a code meeting these bounds is given in Section 6. 2. Preliminaries and Definitions q Structure of the Ring qqq F uF vF q uvF Let q R denote the ring qqqq F uF vF uvF abu w ents can be uniquely written as hose elem cvduv where ,,,q abcd F . An element of q R is a unit if and only if 0a . The ring has 5q ideals namely 0, , ,, q uvvR u jv wq jF. q R is not ,,u vhere a principal ideal ring since the maxiemal idal ,uv is generated by u and v. The cardinality of the iare deals ,uv q 2,vujq 3 ,,uv q and 4. q Rq v Its lattice of ideals is shown in Figur 1. As can be in the lattice of ideals,is not a finite chain ring. But eseen q R it is a local, Noetherian and Artinian ring. All zero divi- sors are the elements of ,\0uv and its units are the elements of \, q Ruv. Figure 1. Lattice of ideals of q qqq FuFvFuvF . Copyright © 2013 SciRes. OJAppS  J. D. PALACIO, V. P. SISON 28 Clearly, the ring is isomorphic to 22 [, ],, q F x yxyxyyx ring of all 44 ma . It is also isomorphic to the trices of the form Moreover, is Frobenius with generating character 00 . 00 000 abcd ac ab a q R 2 :, itrd p qTabucvduv trace map on R e wher r denotes the e t q F and T is the multiplicative group of unlex num Further, is a vector it compbers. q R space over q F with dimension 4. A basis over q of Rq F is given by the is set which the polynomial Another sideren this work 3. lo Any linear block code over a fi has a generator matrix which can be pu l (1 where 1,, ,uvuv basis of q R. we will refer to as conbasis d i 1,1,1,1uv uvv uvu uvuv. Linear Bck Codes over qqq q FuFvFuvF nite commutative ring R t in the following form 1 11,2k aI A 2 1,3 1,1 1 ,1 l ll AA 22 2,32 2, l kl lk aI aA aA G aI aA ) ,ij A are binary matrices for and are trices over for. A code of this form has 1ima q R 1i 1 i lk i i aR elements, where the ' i as define th e nonzero equiva- lence classes 12 ,,, l aa a under the equivalen relation on R defined by ce if for a unit in ababuuR for some ii aRxxarrR ; and the blanks in G are zeros. B of length n over is an -submodule of. B has a generator mwhich be put in shown in Figure 2e to be filled with A linear block code q R wher q R can n q R the form atrix ,ij A are ij kk matrover , ices q R,ij D are ij kk matri- ces over 2 F and the blank parts of GB 4k are to be k filled with zeros. Moreover, B has 3 1q qqq 2t dewords where 2 2 q i i k t co . A linear block code over q R i if and only if 0 i k r all 3iq. Now, w equip B with two weight funs namely the usual Hamming metric and a homogeneous wei function. s freefo e ght Honold ring with generating character 2, , nctio Lemma 2.1. (T. , [2]) Let R be a Frobenius , then every homoge- ne an be in terms of ous weight whom on R c expressed as follows hom 1 yR wxy R 1 (1) where R is the group of units of R. Theorem 2.1. A homogeneous weight whom on Rq is given by hom 1 wx ifx q \ quv \0 if xR quv (2) Proof: Let 0otherwise q x abucvduvR ma, every homogeneous wei . Now, using the previous lemght on Rq can be expressed as hom 3 1 11yR wx qq y Case 1. Let q x R . There are 2 1qq units having the same d, for any q dF 1m p . But there are ele- ments of Fqr an that has trace j, foy p jF. He rq Figure 2. Generator Matrix of Linear Block Codes over q nce, 4 GB 3 ()uv I u 2, 4q uD 1 3 1, 21,31, 41, 51, 4 2,4 3,43,53,4 4,54, 4 ,1,4 3,4 () r q k q k q k q krr kqq IA AAAA vI vDvDvDvD uD vD uvD ujvI ujvDujvD uvI uvD 22,3 2,5k uI uD qqq F uF vF uvF . Copyright © 2013 SciRes. OJAppS  J. D. PALACIO, V. P. SISON 29 2 21 1. p q i j mp jF yR xyqq pe But 2 0 p ij p jF e . So, Case 2. Let. For every hom w. \0xuvq aF cv duv , there are 3 q units of the form yabu e trace value j, f . Now, of these have the samor any 1 m p p jF while there are 11 m p of them with trace zero. Hence, 2ij 31 31 1. qq mm p yR jF xyqpeq p But 2 1 q ij p jF e . So, hom 1 q wq . Case 3. Let ,\ x uv uv. There are 1q ele- moe ents of ,\uv ve the same cent for uv that ha ,\ ffici uv. For each element x uv appears copies e multiset uv q in th ,,\ q x yyR xuvuv . Moreover, there are 1m p elements of q F that has trace j, for any p jF. Hence 2 1 1. q q ij mp jF yR xyqq pe xtend this to turally: if We en q R na 12 ,,, n x xx x then . The homogeneous (resp. hom hom 1 n i wx wx distance be i Hamming)tween any distinct vectors ,, n q x yR denoted by hom ,dxy (resp. y), is defined as hom wxy (resp. weote the mini- mum homogeneong) distance , H dx We will d resp. Ham H us xy) distance . n ( mi by a linear block code over by (resp. q R hom d H d). 4. The q-ary Images of Linear Block Codes over qqqq F uF vFuvF Let ents of an ordered basis of y element ofcan be written in the form 1 bb q R. Then an 4 234 ,,,bb be distinct elem q R 1 , ii iq i ab aF . Define the mapping 4 12 4 1 : ,,, qq ii i RF aba aaa 3 We then extend tn q R dinate-w: o cooriseif 12 ,,, n x xx x and , 1 ii jj 4 j x ab then 1,1 ,, , ,,,, ,, 1,42,12,4,1,4nn x aaa aa a. It is easy to show that isn q a F -module isomor- phism The B is a linear block c . orem 4.1. Ifode over of length n, then q R Bxx Bis a linear block code over q F with Proof: First we show that for every length 4n. ,q 4n x Bx F. 12 ,, n x xx x B , Since 4 iq x F for any Let 1, 2,,,ni then 4. n q x F Net we show that x B q is a subspace of 4n F . Let q s F and let 1 , y yB . Then there exist 1 , x xB such that y x and 11 y x . But 11 s yy s xx since is a mod- ule homomorphism. Since 1 s xx B, 1 s yy B . Thus, B is a subspacef 4n q o F . Theorem 4.2. Let GB be the ge gi nerator matrix of B ven in Figure 2. Thn GB has a generator m- trix that is permutae matrix given in Figure 3. e on-equi a ti hvalent to t 1 1 1 1 2 2 1,21,31, 4 1,2 1,34 1,2 1,34 1,21,31, 4 2,4 2,3 ,1 ,1 k q k k q k q k q k l l k IAAA vI vAvA uI uAuA vI ujvD uvI 3 ,1 ,1 3,4 l q ll ll kqq uvD uvD uvI uvD 1, 1, q vA uA uvA vD uvI uvAuvA 2,3 vD ll Figure 3. Generator Matrix of 2, 4q uvD ujvD l k uvI uvD ujvI B . Copyright © 2013 SciRes. OJAppS  J. D. PALACIO, V. P. SISON 30 Proof: Let B have a generator matrix given in Figure 2. Then for every c can be expressed as yG where , that is, z where cB, k q yR, 4 1 i i kk 1 k ii i cs iq s R and the are the k rows of ' i zs GB. Using sis of Rq, cfurther be written Now, Hence, any ba can 4444 ,, ,,, 111111 11 kkkk ijl iijiijiiji ijijij ij azb uzcvzduvz 44 ,, 11 11 44 ,, 11 11 . kk ij iiji ij ij kk ij iiji ij ij cazbuz cvz duvz ,,, iii Szuzvzuv er whenever or for some 1,2,, i zi k spans B . But 0 i vz whenev112 1,, k k or ik 3q1,, k; ikk 0uz i12 3 31, , q ikk k ; 0 whenever ; and 12 1, ,ik kkkk i uvz 1 ik ii uz jvzq jF i r some l whenever k fo Define the set 1ll i 11 1, , ii ik . sted a m as the resulting set once the unde- sirable cases libove are deducted from the set S. Notice that the eleents of are the rows of the ma- trix given in Fi we will denote by M. Now, define as the matrix that consists of the rows l k of M so that M can be for all i. Consider a ropressed as a linear com any , t gure 3 l 1 1 42 1,, l kk B 1 22 42 ii ii k written in the form 2 1 B B . 3q ewish to show that te B W hrows of M are linearly inde- pendent. Without loss of generality, let i k w of i B. Clearly, it cannot bination of rows from 1 be ex of the ' j Bs ji. We know t ha 1,, ,uvuv are line- arly independent and so any nonzero linear combination of these vectors is not the zero vector. Thus, any row of i B cannot be written as a linear combination of rows of any of the ' j Bs, ji. Hence, the rows of M are line- y independent. arl The succeeding theorems aof Theorem 4.2. Corollary 4.3. If B is free with rank k, then re direct consequences B is free with rank 4k. Corollary 4.4. Let B be a free rate-kn linear block code overwith generator matrix 2 R I A B , then the generator mtrix of the q-ary image of with respect to the basis a 1,1 ,1uvuv vuvuv,1uuv uivalent to is permutation-e where q 0 000 00 0 000 0 kkk kk kk kk IIIEFHDEDFDH IIDE DE IIDF DF IID D A DEuFvHuv . 5. Distance Bounds of the Images of Linear Block Codes over qqqq F uF vF uvF um distance ofle indica- tion of the goodness of a code. A field code can correct at The minim a code gives a simp most 1 2 errors where is its minimum Hamming distance. Hence, we are interested with upper bounds of the minimum Hamming distance of the images of the linear block codes over q R. For the succeeding discus- sions, we let B be a rate-kn linear block over q R. Also, we denote by code the minimum Hamming distance of B . eorem 5.1. (Singl B be free. Then Th eton-type Bound) Let 41.nk (3) The above theorem is a direct consequence of Corol- lary 4.3 and the Sinton Bound for codes over fields wh gle f ile the next theorem is a direct consequence of the Plotkin Bound for codes over fields. Theorem 5.2. (Plotkin-type Bound) Let B beree. Then 41 414 . 1 k k qqn q (4) The next bound is in terms of the average homogene- ous weight on q F andis- tance of B. the minimum Hamming d Theorem 5.3. (Rains-type bound) For a code B, 4. H H dd (4 Proof: Note that ) is bounded above by 4n. If for every , H H x Bw Bd then 4 H d . Now, is bounded below by H d ng wei si of the Hammig nce nimumro value ht on 1 is the mi nonze q F . Thus, inequality (4) pt of subcodes of B generated holds. Now, we use the conce by x as defined by V. Sison and P. Sole in [4]. The sub- code of B generated by x B , denoted by x B, is the set Copyright © 2013 SciRes. OJAppS  J. D. PALACIO, V. P. SISON 31 ax aR. A generalization of the Rabizzoni bound was din [4]. Here wprove a parallel bound for linear odes over q Rhe proof presented here is erived e block cT. based on the proof in [4]. Lemma 5.4. Let ,0xBx. x B is free if and only if 4 x Bq. Proof: Let x B be then the equation 0axfree s only the trivial solution. In particular, 0abx aabplies ax bx. Thus, ha imb, that is, 4 x Bq . Let 4 x Bq. Then for any nonzero a and b, ab axbx . That is, 0abxab . But x generates x B by definition. So, x B t conse is free. quence of the car-The next statement is a di direc nality of the ideals of q R Corollary 5.5. Let x B. Then \0 nn xuv if and only if m x Bp; \ nn x ujv uv or \ nn x vuv if and only if 2m x Bp; ,\ n x uv S if and only if 3m x Bp where q jF ujvv . Theorem 5.5. (Rbizzoni-type Bound) Let x be a minimum H nn S a amming weight codeword. Then 14. 1 x xH d (5) x Bq More Bq over, if x B is free, then 3 41 . 1 xH qqd q (6) 4 Proof: Let x be a minimum Hamming weight code- word in B then consider subcode x B. Let x denote the minimum Hamming distance of x B . The minimum Hamming distance of x B is still H d since x B is a subcode of B. Also x B is a subcode of B with x . The effective length of x B is 4 H d coming from the H d nonze in. Direct application of the Rabizzoni bou inuality (5) holds. By Le i ro posi resu t nd l ion ts t 4, nlit Conse free ra s o x eq mma 5.equay (6) follows. 6. Example ider thte-14 self-orthogonal code B over 2 11G uv . If GIA then 1,11,0 k ID E R F generated by HB is 4nary image of B was ned with 1. Comparison of bounds for 1 1vuvu 11 1 ht 0,4 or 8. The minim , um 110 and 001H. A codeword in B either has homogeneous weig amming distance of . The bi obtai respect to the basis 1,1,1,1u v uvvu uvu uv v . Table . Singleton-type 813 Plotkin-type 88 8.53 4816 Rains-type Rabizzoni-type 16 x B 88 4 x B 8 10.6 2 x B 816 Using Corollary 4.4, i equivalent to as a m dista 8 and le 1, w se REFERENCES . K. Gupta and [2] T. Honold, “A Characterization of Finite Frobenius Rings,” Ar Mathematik, V GB s permutation- 0111100100001110 1010100000111011 . 1100001111 0110 1001111 00000111 The image code hinimum Hammingnce of is self-orthogonal. In Tab e cane that B meets the upper bound of the Plotkin-type and Rabiz- zoni-type bound. 00 0 [1] S. T. Dougherty, M K. Shiromoto, “On Generalized Weights for Codes over Finite Rings,” pre- print, 2002. rchiv deol. 40, No. 6, 2001, pp. 406-415. doi：10.1007/PL00000451 [3] S. Karadeniz and B. Yildiz, “ 1v-Constacyclic Codes over 222 2 F uF vFuvF,” Jour stitute, Vol. 347, 2011, pp. 2652- nal 2632. of the Franklin In- [4] V. Sison and P. Solè, “Bounds on the Minimum Homo- geneo r Block Codes s Ri us Distance of the r p-ary Image of Linea over the Galoing , r GR pm ,” , Vol. IEEE transac- tions on53, No. 6, 2007, pp. 2270-2 .1109/TIT.2007.896891 Information Theory 273. doi：10 [5] X. Xu aOn the Structure of clic Codes over nd X. Liu, “Cy 222 FuFvFuvF 2 Natura l. ,” Wuhan University Journal of 16, No. 5, 2011, pp. 457-460. doi:10.1007/s11859-011-0780-5 l Sciences, Vo [6] B. Yildizand S. Karadeniz, “Linear Codes over 2222 F uF vFF Vol. 54, No. 1, 20, p uv ,” Designs Codes Cryptography, p. 61-81. doi:10.1007/s10623-009-9309-8 01 ] B. Yildiz and S. Karadeniz, “Self-dual Codes over [7 222 2 FuFvFuvF ,” Joe Franklin Institute, Vol. 347, doi:10.1016 urnal of th No. 10, pp. 1888-1894. /j.jfranklin.2010.10.007 2010, [8] B. Yildiz and S. Karadeniz, “Cyclic Codes over 2222 FuFvFuvF Vol. 58, No. 3, 2011, pp ,” Designs Codes Cryptography, . 221-234. doi:10.1007/s10623-010-9399-3 Copyright © 2013 SciRes. OJAppS |