Microsoft Word - MATH080424-f edited_checked.doc 53-59 SQU Journal For Science, 14 (2009) © 2009 Sultan Qaboos University 53 Transform Domain Characterization of Dual Group Codes of Cyclic Group Codes over Elementary Abelian Groups Adnan Abdulla Zain Department of Electronics and Communications Engineering, Faculty of Engineering, University of Aden, Yemen. Email: adnan_zain2003@yahoo.com. )آبل(الوصف في المجال المتحول للشفرات المزدوجة للشفرات الدورية على الزمر من نوع عدنان عبداهللا زين في تعريف االزدواجية بين المجموعات الجزئية للمجموعة ، ) آبل( من نوع استخدمت مجموعة رموز الزمر :خالصة في هذا البحث تم تطوير الوصف في المجال المتحول . رمزوالتي تم تعميمها لتعريف االزدواجية بين الشفرات على ال =−1 (للشفرات الدورية ذات طول mpn (على هذه الزمر واستنتاج الوصف لشفراتها المزدوجة . ABSTRACT: The group of characters of an elementary Abelian group mpZ has been used to define duality between its subgroups, which in turn is extended to duality between group codes. The transform domain description of the dual codes of cyclic group codes of length 1−= mpn over mpZ has been developed in this paper. Several example codes and their duals have been presented also. KEYWORDS: group codes, cyclic codes, dual codes, Abelian groups. 1. Introduction he transform domain description of cyclic linear codes over )( mpGF using discrete Fourier transform (DFT) defined over an extension field rmpGF )( is well known (Blahut, 1997). The transform domain description of cyclic group codes over an elementary Abelian group ....mp p p pZ Z Z Z= ⊕ ⊕ ⊕ (m-times), using discrete Fourier transform (DFT) defined over an extension group ( )m r m m mp p p pZ Z Z Z= ⊕ ⊕ ⊕… (r-times) has been developed by Zain and Rajan (1997) ; this class of codes are subgroups of the Cartesian product group ( ) ....m n m m mp p p pZ Z Z Z= ⊕ ⊕ ⊕ (n- times), which amounts to relaxing the condition of linearity, T ADNAN ABDULLA ZAIN 54 hence yielding a larger class of codes that contains the class of linear codes. The important class of Reed- Solomon codes over )( mpGF where the length of the code n is equal to 1−mp has been generalized to Reed-Solomon group codes over the elementary Abelian group mpZ , which is the additive group of )( mpGF (Zain and Rajan, 1995). The dual codes of systematic group codes over finite Abelian groups have been characterized (Zain and Rajan, 1997) in terms of the endomorphism of the Abelian group that defines the group code. In this paper, using the structural properties of the dual codes of cyclic group codes of length 1−= mpn over mpZ , their characterization in the transform domain is presented. Several example codes and their duals are presented also. The paper is organized as follows. Section 2 presents the mathematical preliminaries that are relevant to the development of the main results. In section 3 the main theorem that characterizes the codes and their duals in the transform domain is proved. Illustration of the applicability of the main theorem with examples codes and their duals is presented in section 4. Conclusions and suggestions for further work are given in section 5. 2. Mathematical preliminaries The minimum mathematical background that is necessary for the development of the main result of the paper is presented in the following two subsections. 2.1 Group characters, inner product and dual subgroups A character of a group G is a homomorphism of G into the group of units of the field of complex numbers *C or group of units of any appropriate field in which there exist an thm − root of unity, where m is the exponent of G. Let ^ G be the set of characters of G. Result (1)( Hungerford, 1989): GG ≅ ^ (1) Under the above isomorphism, the elements of ^ G can be indexed with the elements of G as follows: GxGx GG x ∈∀∈→ → , : ^ ^ η η (2) Let H be a subgroup of G . Definition (1) ( Hungerford, 1989): The subgroup dH of G is said to be the dual of the subgroup H if eH dH =)(η (3) where e is the identity element in the group of units. Definition (2) ( Hungerford, 1989): A subgroup H of G is said to be self dual if HH d = . (4) TRANSFORM DOMAIN CHARACTERIZATION OF DUAL GRUP CODES 55 An inner product on G is defined next. The indexing of the characters of G with the elements of G can be done such that the mapping: *CGG →× given by , ( ), ,xx y y x y Gη< >= ∈ (5) is symmetric in both arguments. This mapping will be called an inner product on G ( Delsarte 1972). Result (2)( Hungerford, 1989): GHH d = . (6) where | . | stands for the cardinality of the set. 2.2 Elementary Abelian Discrete Fourier Transform (EADFT) Let mpZ denote the elementary Abelian group, )( m pZAut the group of automophrisms of m pZ , and n denote the length of the code where n and p are relatively prime. Definition (3) (Zain and Rajan, 1995): The transform vector of ,1,,1,0 , ),,,,( 110 −=∈= − → niZaaaaa mpin …… denoted by ,1,,1,0 , ),,,,( 110 −=∈= − → njZAAAAA mpjn …… is defined by )( 1 0 i ij n i j aA α − = ⊕= (7) where )( iaα denotes the image of ia under the action of the automorphism )( m pZAut∈α whose order is n . The EADFT transform defined above is invertible (Zain and Rajan, 1995), and its inverse is given below: 1,,1,0,)( 1 0 1 −=⎟ ⎠ ⎞ ⎜ ⎝ ⎛ ⊕Λ= − − = − niAa j ij n j ni …α (8) where 1−Λn is the inverse of an automorphism of m pZ defined by: m pn Zxxxx ∈∀⊕⊕=Λ n times)()( (9) The following definition is important to the characterization of the class of codes that are cyclic. Definition (4) (Zain and Rajan, 1997): (Invariant Subgroups): Let G be a group and H be a subgroup of )(GAut . A subgroup of G which is invariant under the action of H on G is called a H -invariant subgroup of G . Definition (5)(Zain and Rajan, 1997):(Conjugacy Classes): The mp -conjugacy class containing 10 , −≤≤ mpjj is the set })(,,)(,,{)( 12, −≡ jemmmnp pjpjjpjjC … where )( ulomod )( mem pjpj j = , and je is the exponent. ADNAN ABDULLA ZAIN 56 2.3 Transform Domain Characterization of Cyclic Group Codes The transform domain characterization of the class of codes that are group codes ( not necessarily linear codes), cyclic and of length 1−= mpn over the elementary Abelian group mpZ presented in (Zain and Rajan 1995), identifies two cases as shown below: • Case 1, In this class of cyclic group codes, all the transform components are free. • Case 2, In this class of cyclic group codes, the transform components that are in the same conjugacy class are related. In this paper, we consider case 1 which is the class of codes of length n that is equal to 1−mp , in which the transform components that lie in the same conjugacy class are all either free or zeros. 3. Main theorem The following theorem gives the transform domain characterization of the dual codes of the cyclic codes, whose transform components that lie in one conjugacy class are all either free or assigned zeros, (those codes covered by case 1). Theorem (1): If C is a cyclic group code of length 1−= mpn over mpZ whose transform vectors are all free and take values from the following jS -invariant subgroups of m pZ , jnjj SSS ,,, 21 … for the components njjj ,,, 21 … , respectively, then the transform vectors of the dual code dC take values from the following jS -invariant subgroups, djn d j d j SSS ,,, 21 … respectively for the components )(,),(),( 21 njnjnjn −−− … . Proof: Let ),,,( 110 − → = nAAAA … be the transform vector of the code vector Caaaa n ∈= − → ),,,( 110 … . By definition of the EADFT and its inverse, we have 1,,1,0,)( 1 0 1 −=⎟ ⎠ ⎞ ⎜ ⎝ ⎛ ⊕Λ= − − = − niAa j ij n j ni …α Given that the transform vectors take values from jnjj SSS ,,, 21 … invariant subgroups for the components njjj ,,, 21 … respectively, we have 1,,1,0 ,21 −=⊕⊕⊕= niSSSa jnjji …… . (10) Now, let dn Cbbbb ∈= − → ),,,( 110 … and ),,,( 110 − → = nBBBB … be its transform vector, so we have 1,,1,0,)( 1 0 1 −=⎟ ⎠ ⎞ ⎜ ⎝ ⎛ ⊕Λ= − − = − niBb j ij n j ni …α (11) Since the components of the transform vector )(,),(),( 21 njnjnjn −−− … take values from the d jn d j d j SSS ,,, 21 … invariant subgroups, we have 1,,1,0 ,21 −=⊕⊕⊕= niSSSb d jn d j d ji …… . (12) Next we compute the inner product >< →→ ba, : TRANSFORM DOMAIN CHARACTERIZATION OF DUAL GRUP CODES 57 eeSSSbba n i d jnS d jS d jS n iia n i jnjji =Π=∗∗∗Π=Π>=< − = − = − = →→ 1 021 1 0 1 0 )}()()({)(, 21 ηηηη … where ∗ stands for the operation in the group of units. Now, we want to show that nd GCC = . since jnjj SSSC …21= , and djn d j d j d SSSC …21= , we have nd jnjn d jj d GGGSSSSCC === ……11 This completes the proof. 4. Illustrations of the theorem The usefulness of the main theorem is best demonstrated with the following two numerical examples, where a length 3 cyclic group code over the elementary Abelian group with four elements is characterized in the transform domain, then by using the theorem, its dual is also characterized and obtained. Example (1): Let }11,01,10,00{22 ><><><><=⊕≅ ZZG . Then we define },,,{ 11011000 ^ ><><><><= ηηηηG according to the following inner product mapping *CGG →× given by Gyxyyx x ∈>=< , ),(, η where }1,0{2 * =≅ ZC since 2 is the exponent of G . The detailed mapping is given in Table 1: Table 1. Characters mappings <00> <10> <01> <11> ><00η 0 0 0 0 ><10η 0 1 0 1 ><01η 0 0 1 1 ><11η 0 1 1 0 Table 2 gives all possible dual subgroups of 22 ZZG ⊕≅ . Table 2. Subgroups and their Duals. Subgroup ( H ) Dual subgroup ( dH ) {<00>} {<00>, <10>, <01>, <11>} {<00>, <10>} {<00>, <01>} {<00>, <01>} {<00>, <10>} {<00>, <11>} {<00>, <11>} {<00>, <10>, <01>, <11>} {<00>} ADNAN ABDULLA ZAIN 58 Note that the subgroup {<00>, <11>} is self-dual. Example (2): Length 3 code over 22 ZZG ⊕≅ and its dual. The transform vectors for the code are listed in the first column where the characterization for the conjugacy classes is as follows: }11,01,10,00{ },00{ },10,00{ 210 ><><><><=><=><><= AAA . According to the theorem the dual code should have the following characterization for the conjugacy classes: }01,00{0 ><><=B , which is the dual subgroup of }10,00{ ><>< }11,10,10,00{1 ><><><><=B , which is the dual subgroup of }00{ >< }00{2 ><=B , which is the dual subgroup of }11,10,10,00{ ><><><>< The detailed listing of the code vectors and the transform vectors of the code and its dual is presented in Table 3. Table 3. Code vectors and their transforms. Transform Vector Code Vector Transform Vector Dual Code Vector 210 AAA 210 aaa 210 BBB 210 bbb <00> <00> <00> <00> <00> <00> <00> <00> <00> <00> <00> <00> <00> <00> <10> <00> <11> <01> <00> <10> <00> <00> <11> <10> <00> <00> <01> <01> <00> <11> <00> <01> <00> <01> <01> <01> <00> <00> <11> <01> <11> <10> <00> <11> <00> <01> <10> <11> <10> <00> <00> <10> <01> <11> <01> <00> <00> <10> <00> <11> <10> <00> <10> <10> <10> <10> <01> <10> <00> <10> <11> <01> <10> <00> <01> <11> <01> <00> <01> <01> <00> <11> <01> <10> <10> <00> <11> <11> <10> <01> <01> <11> <00> <11> <10> <00> 5. Conclusions The structural properties of the dual codes of cyclic group codes of length 1−= mpn over the elementary Abelian group mpZ have been used to present and prove a theorem that gives the characterization, in the transform domain, of the dual codes in terms of the dual subgroups of the group mpZ . As an example a length 3 cyclic group codes over 22Z is characterized in the transform domain, then its dual code is obtained. Further work can be done to generalize the main result to other classes of cyclic group codes whose transform characterization contains components that are related (Zain and Rajan, 1997), and to quasi-cyclic codes (Dey and Rajan, 2003). 5. References BLAHUT, R.E. 1997. Theory and Practice of Error Control Codes, Addison-Wesely. DELSARTE, P. 1972. Bounds for unrestricted codes by linear programming. Philips Research Dev. J., 27: 272- 289. DEY, B.K. Rajan B. S. 2003. DFT Domain Characterization of Quasi-Cyclic Codes", Applicable Algebra in Engineering, Communication and Computing, Springer-Verlag, 13(1): 453-474. TRANSFORM DOMAIN CHARACTERIZATION OF DUAL GRUP CODES 59 HUNGERFORD, T.W. 1989. Algebra, Springer-Verlag. ZAIN, A.A. and RAJAN, B.S. 1997. M-PSK BCM Using Cyclic Codes over Elementary Abelian Groups. Proceedings of ISIT, Ulm, Germany, June 29-July 4 1997, p.410. ZAIN, A.A. and RAJAN, B.S. 1995. Reed-Solomon Group Codes. Proceedings of ISIT, British Columbia, Canada, 17-22 September 1995, p.495. ZAIN, A.A. and RAJAN, B.S. 1997. Dual Codes of Systematic Group Codes over Abelian Groups. Applicable Algebra in Engineering, Communication and Computing, Springer-Verlag, 8(1): 71-83. Received 24 April 2008 Accepted 24 May 2009