Electromagnetic Modeling of the Propagation Characteristics of Satellite Communications Through Composite Precipitation Layers Science and Technology, 8 (2003) 145-151 © 2003 Sultan Qaboos University On Group Codes Over Elementary Abelian Groups Adnan A. Zain Department of Electronics and Communications Engineering, Faculty of Engineering, University of Aden, P.O.Box 7409, Almansoora City, Aden Governorate, Republic of Yemen, Email: aazain@gmx.de. بتدائية اال (Abel)حول أنظمة التشفير المزمرة بواسطة زمر عدنان عبداهللا زین تقدم الورقة تعريفا لكل من مصفوفة التوليد و مصفوفة فحص التكافؤ ألنظمة التشفير المزمرة بواسطة الزمر االبتدائية من : خالصة تطوير النظرية , في هذا البحث, باستخدام ذلك تم. للزمرةةوهذه المصفوفات عناصرها تنتمي إلى الحلقات المتبلور, ) Abel(نوع التي تعطي العالقة بين مصفوفة التوليد و مصفوفة فحص التكافؤ ألنظمة التشفير الخطية بواسطة الحقول المتناهية إلى نظرية جديدة أعلى : جديدة تمتلك خواص جيدة مثليعرض البحث شفرات ). Abel(ألنظمة التشفير المزمرة بواسطة الزمر االبتدائية من نوع . والخاصية الحلقية, ذاتية االزدواجية, وقابلية االنفصال ) Hamming(قيمة للمسافة ABSTRACT: For group codes over elementary Abelian groups we present definitions of the generator and the parity check matrices, which are matrices over the ring of endomorphism of the group. We also lift the theorem that relates the parity check and the generator matrices of linear codes over finite fields to group codes over elementary Abelian groups. Some new codes that are MDS, self-dual, and cyclic over the Abelian group with four elements are given. KEYWORDS: Codes Over Groups, Elementary Abelian Groups, Endomorphism Rings. 1. Introduction A group code of length n over an Abelian group C A is a subgroup of , the n-fold direct product of . The rate is defined by nA A )C(k CC A)( =k , where log X stands for cardinality. A group code C of length with rate and minimum Hamming distance d is called a [ code. A linear code C over a field is also a group code over the additive group of . It has been shown by Forney and Trott (1993) that many of the important structural properties of codes over are associated with the additive and not the multiplicative group properties of . For an information set supporting group codes (Forney, 1992) i.e. for group codes that are equivalent to systematic group codes over Abelian groups, the notion of generator and check matrices was introduced in Biglieri and Elia (1993). In this paper, following Biglieri and Elia (1993), we present the formal definitions of a generator and parity check matrices over the endomorphism ring of the elementary Abelian groups. Based on this we generalize the well known theorem that relates the generator and parity check matrices of linear codes over fields to group codes over elementary Abelian groups. Some new codes, MDS, Self-Dual, and Cyclic over the Abelian group with four elements, which cannot be obtained as linear codes over fields, are presented. n k H ],, Hdkn F F F F The paper is organized as follows. Section 2 contains the mathematical preliminaries. In section 3 the main theorem of the paper is proved. Table 2 contains the generator matrices and the listing of the code words of the new codes. 145 ADNAN A. ZAIN 2. Preliminaries An elementary abelian group, denoted by , of order , where mpA mpq = p is a prime, is isomorphic to the direct sum of cyclic groups, , of order m pC p , written as . Let be a generator for the i cyclic group. An arbitrary element can be written as times)( −⊕⊕≡ mCCA ppp m K mp Ax ∈β ig th .,,2,1 , , ,, 1 miZxgxx pihh m h K=∈⊕= = βββ (1) Let mm pp AA →:ψ be an endomorphism of the group defined by the following mpA .,,2,1 , , )( ,, 1 miZgg pjijji m j i K=∈⊕= = ααψ (2) Then ψ can be specified by the following m m× matrix over )( pGFZ p ≡               = mmmm m m ,2,1, ,22,21,2 ,12,11,1 ][ ααα ααα ααα ψ K MMM K K (3) The action of ψ on any element , is given by the following expression mpAx ∈β h m i hii m h mm gpxgxgxx ]} mod {[)()()( 1 ,, 1 ,11, ∑ = = ⊕=⊕⊕= αψψψ ββββ K (4) The endomorphism ring of denoted by is isomorphic to the matrix ring consisting of matrices over a finite field with mp A )( mpAEnd )( pm ZM m m× p elements denoted by (McDonald, 1974). )( pGF Example 1: Consider the group 2222 CCA ⊕≡ . )()( 2222 ZMAEnd ≡ . 2 2 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 0 0 1 1 1 1 0 1 1 0 ( ) , , , , , , , , , , , , , , 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 1 0 0 1 1 1 1 0 0 1 1 1 1 1 M Z                               =                                                            1 1 , 1 1           2 2 10 01 11 01 10 11 ( ) , , , , , 01 10 10 11 11 01 GL Z              =                           2 2 2 00 10 01 11 , , , (2 00 01 11 10 F G          = ≡                  )F The set , the set of endomorphisms, contains as a proper subset the set GL , the set of automorphisms, which contains a proper subset of the set that is isomorphic to the finite field with four elements, . The action of every endomorphism on the group elements is shown in Table 1, where the first column contains the elements of the group against which are the images under the action of the underlying endomorphism. )( 22 ZM )( 22 Z 22 F )4(GF 146 GROUP CODES OVER ELEMENTARY ABELIAN GROUPS Table 1. List of and Their actions on the group elements. )()( 2222 ZMAEnd ≡ 00 00       10 00       01 00       00 10       00 01       11 00       10 10       10 01       01 10       01 01       00 11       01 11       10 11       11 01       11 10       11 11       00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 10 00 10 01 00 00 11 10 10 01 01 00 01 10 11 11 11 01 00 00 00 10 01 00 10 01 10 01 11 11 11 01 10 11 11 00 10 01 10 01 11 00 11 11 00 11 10 01 10 01 00 3. ( Group Codes ), kn A block of k message symbols kuuuu K21= , where u A , 1, 2, , ,mi p i k∈ = K , , , 2211 kxuxux = will be encoded into a codeword where , and these code words form a code. The first part of the codeword consists of the message itself: ,mpA∈ , 21 jn xxxx= Kx kn ≥ ,ku== K followed by check symbols kn − . , ,1 nk xx K+ Following the definition of systematic group codes presented by Biglieri and Elia (1993), the check symbols can be obtained as ).(,,2,1 ),( 1 knlxx iil k i lk −=⊕= = + Kψ (5) In matrix notation the above can be written as Ψ= ux (6) where is the generator matrix of the code given by Ψ             =Ψ ksI sI sI ψψψψψψ ψψψψψψ ψψψψψψ KK MMMMMM KK KK | | | | k2k100 2222100 1121100 (7) and Iψ is the identity endomorphism that maps every element in the group onto itself while 0ψ is the zero endomorphism that maps every element on to the identity element of the group .e The parity check matrix Η for the code can be obtained as follows )( nkn ×− 1 2 tr n x e x e x ex            Η = Η =            MM (8)             =Η invksss invk invk ψψψψψψ ψψψψψψ ψψψψψψ KK MKMMMKMM KK KK | | | 0021 0022212 0012111 (9) where invψ is the endomorphism that maps every element on to its inverse. (This parity check matrix is different from the parity check matrix in Biglieri and Elia (1993)). 147 ADNAN A. ZAIN Now we are in a position to generalize the well-known result that relates the generator matrix and the parity check matrix for a linear code over finite fields. ),( kn Theorem 1: For codes over an elementary Abelian group the generator matrix Ψ and the parity check matrix are related by ),( kn Η mp A [ ]sktrtr OHH ×=Ψ=Ψ oo , where [ ]skO × is the matrix with all entries equal to 0ψ i.e. the zero endomorphism, and o denotes a composition of endomorphisms. Proof: From equation (8) that defines H, we have [ ] 12 1 × =             =Η=             Η s tr n e e e e x x x x MM Use equation (6) to substitute for in the above to obtain trx [ ] 1×=Ψ strtr euH o Using (7) and (9) in the above matrix equation, we obtain             =                                         −−−−−−             e e e u u u k ks k k I I I invksss invk invk MM K MKMM K K K MKMM K K o KK MKMMMKMM KK KK | | | 2 1 2s1s 22212 12111 00 00 00 0021 0022212 0012111 ψψψ ψψψ ψψψ ψψψ ψψψ ψψψ ψψψψψψ ψψψψψψ ψψψψψψ 1 2 11 21 1 0 0 12 22 2 0 0 11 2 0 0 1 1 ( ) ( ) | ( ) | ( ) | ( ) I I k inv k inv I k k i is s ks inv i k is i i u u u u u ψ ψ ψ ψ ψ ψ ψ ψ ψ ψ ψ ψ ψ ψ ψ ψψ ψ ψ ψ ψ ψ ψ = =               ⊕     ⊕ K K M K K o M M K M M M K M K K M e e e             =             M 148 GROUP CODES OVER ELEMENTARY ABELIAN GROUPS             =               ⊕⊕⊕ ⊕⊕⊕ == == e e e uu uu iis k i invlls k l ii k i invll k l M M ))}(({)}({ ))}(({)}({ 11 1 1 1 1 ψψψ ψψψ           =           ⊕ ⊕ e e vv vv sinvs inv MM )( )( 11 ψ ψ which yields           =                             −−−−−−             00 00 2s1s 22212 12111 00 00 00 0021 0022212 0012111 | | | ψψ ψψ ψψψ ψψψ ψψψ ψψψ ψψψ ψψψ ψψψψψψ ψψψψψψ ψψψψψψ K MKM K K MKMM K K K MKMM K K o KK MKMMMKMM KK KK ks k k I I I invksss invk invk That is . [ ]sktr OH ×=Ψo In a similar way it can be proved that [ ]sktr OH ×=Ψ o , hence the result. The class of codes over obtained using mpA Ψ contains as a proper subclass the linear codes over GF . This can be illustrated using the following example. )( mp Example 2: codes over and codes over GF . ),( kn 22A ),( kn )4( The matrix Ψ with entries )()( 2222 ZMAEndij ≡∈ψ generates codes over denoted by the set Ρ . ),( kn 22A The matrix Ψ with entries )()( 2222 AEndZGLij ⊂∈ψ generates codes over denoted by the set Ρ . ),( kn 22A ' The matrix with entries Ψ )()( 22 2222 AEndZGLFij ⊂⊂∈ψ generates codes over denoted by the set Ρ . This set coincides with codes over GF . ),( kn 22A '' ),( kn )4( Clearly the following inclusion property holds, ''' Ρ⊃Ρ⊃Ρ : Based on example 2 we present, in Table 2, three new (4,2,3) group codes and their binary images, where the codes belong to the set , and they do not belong to the set 'Ρ ''Ρ ; that means that they cannot be obtained as linear codes over GF . We also observe that these codes are self-dual, MDS and two of them are also cyclic. )4( 149 ADNAN A. ZAIN Table 2: New (4,2,3) group codes over }3,2,1,0{}11,01,10,00{2222 ≡≡⊕≡ CCA Remarks Binary Image Code Generator Matrix MDS SELF-DUAL 00 00 00 00 00 10 01 11 00 01 11 01 00 11 10 10 10 00 10 11 10 10 11 00 10 01 01 10 10 11 00 01 01 00 11 10 01 10 10 01 01 01 00 11 01 11 01 00 11 00 01 01 11 10 00 10 11 01 10 00 11 11 11 11 0000 0123 0232 0311 1013 1130 1221 1302 2031 2112 2203 2320 3022 3101 3210 3333                                                               11 10 10 11 01 10 00 00 11 01 01 11 00 00 01 10 MDS SELF-DUAL CYCLIC 00 00 00 00 00 10 10 11 00 01 11 10 00 11 01 01 10 00 01 11 10 10 11 00 10 01 10 01 10 11 00 10 01 00 11 01 01 10 01 10 01 01 00 11 01 11 10 00 11 00 10 10 11 10 00 01 11 01 01 00 11 11 11 11 0000 0113 0231 0322 1023 1130 1212 1301 2032 2121 2203 2310 3011 3102 3220 3333                                                               10 11 11 10 01 10 00 00 01 11 11 01 00 00 01 10 MDS SELF-DUAL CYCLIC 00 00 00 00 00 10 11 01 00 01 01 11 00 11 10 10 10 00 11 10 10 10 00 11 10 01 10 01 10 11 01 00 01 00 10 11 01 10 01 10 01 01 11 00 01 11 00 01 11 00 01 01 11 10 10 00 11 01 00 10 11 11 11 11 0000 0132 0223 0311 1031 1103 1212 1320 2013 2121 2230 2302 3022 3110 3201 3333                                                               11 01 01 11 01 10 00 00 11 10 10 11 00 00 01 10 150 GROUP CODES OVER ELEMENTARY ABELIAN GROUPS 4. Conclusion In this paper, the formal definitions of a generator and parity check matrices over the endomorphism ring of the elementary Abelian groups have been presented. The well-known theorem that relates the generator and parity check matrices of linear codes over fields were generalized to group codes over elementary Abelian groups. New codes, MDS, Self-Dual, and Cyclic over the Abelian group with four elements, which cannot be obtained as linear codes over fields, were also given. The algebraic framework motivates us to a further study of the class of group codes that are cyclic over elementary Abelian groups especially over to cover the recently developed codes in Ran and Snyders (2000). 22 A References BIGLIERI, E. and ELIA, M. 1993 Construction of linear block codes over groups. IEEE International Symposium on Information Theory, San Antonio, Texas. FORNEY, G.D. 1992 On the Hamming distance properties of group codes. IEEE Trans. Inform. Theory, IT-38: 1797-1801. FORNEY, G.D. JR. and TROTT, M.D.1993 The dynamics of group codes: state space, trellis diagram, and the canonical encoders. IEEE Trans. Inform. Theory, IT-39: 1491-1513. McDONALD, B.R. 1974. Finite rings with identity. Marcel Dekker, New York, 1974. RAN, M. and SNYDERS, J. 2000. On cyclic reversible self-dual additive codes with odd length over . IEEE Trans. Inform. Theory, IT-46: 1056-1059. 22Z Received 5 February 2002 Accepted 3 September 2003 151 On Group Codes Over Elementary Abelian Groups Adnan A. Zain Department of Electronics and Communications Engineering, Faculty of Engineering, University of Aden, P.O.Box 7409, Almansoora City, Aden Governorate, Republic of Yemen, Email: aazain@gmx.de. ABSTRACT: For group codes over elementary Abelian groups we present definitions of the generator and the parity check matrices, which are matrices over the ring of endomorphism of the group. We also lift the theorem that relates the parity check and the KEYWORDS: Codes Over Groups, Elementary Abelian Groups, Endomorphism Rings. References