MacWilliams Identity for the Rank Metric Maximilien Gadouleau and Zhiyuan Yan Department of Electrical and Computer Engineering Lehigh University, PA 18015, USA E-mails: {magc, yan}@lehigh.edu Abstract—Thispaperinvestigatestherelationshipbetweenthe The rest of the paper is organized as follows. Section II rankweightdistributionofalinearcodeandthatofitsdualcode. reviewsnecessarybackgroundsinanefforttomakethispaper Themainresultofthispaperisthat,similartotheMacWilliams self-contained. Section III-A introduces the concepts of q- 7 identityfortheHammingmetric,therankweightdistributionof 0 any linear code can be expressed as an analytical expression product and q-derivative for homogeneous polynomials, and 0 of that of its dual code. Remarkably, our new identity has investigates their properties. Using these tools, Sections III-B 2 a similar form to the MacWilliams identity for the Hamming and III-Cprovethe MacWilliams identity for the rank metric, n metric. Our new identity provides a significant analytical tool and Section III-D derives the relationship between the mo- a to the rank weight distribution analysis of linear codes. We mentsofthe rankdistributionof alinearcodeandthoseofits J use a linear space based approach in the proof for our new dualcode.Wealsoprovideanalternativederivationoftherank identity,andadaptthisapproachtoprovideanalternativeproof 6 of the MacWilliams identity for the Hamming metric. Finally, distribution of MRD codes in Section III-E. Some examples 1 we determine the relationship between moments of the rank are provided in Section III-F to illustrate our results. Finally, distribution of a linear code and those of its dual code, and Section IV adapts the approach in Sections III-B and III-C to ] T provideanalternative derivation of therankweight distribution provide an alternative proof of the MacWilliams identity for of maximum rank distance codes. I the Hammingmetric.All the proofshave beenomitted dueto . s limited space, and they will be presented at the conference. c I. INTRODUCTION [ The rank metric has attracted some attention due to its II. PRELIMINARIES 1 relevance to wireless communications [1], [2], public-key v A. Rank metric cryptosystems [3], and storage equipments (see, for example, 7 9 [4]).Duetotheseapplications,thereisasteadystreamofwork Consider an n-dimensional vector x = 0 that focuson generalpropertiesof codeswith the rank metric (x0,x1,...,xn−1)∈GF(qm)n. Assume {α0,α1,...,αm−1} 1 [4]–[14]. Despite these works, many open problems remain is a basis set of GF(qm) over GF(q), then for 70 for rank metric codes. For example, it is unknown how to j =0,1,...,n−1, xj can be written as xj = mi=−01xi,jαi, 0 derive the rank weight distribution for any given linear code where xi,j ∈ GF(q) for i = 0,1,...,mP− 1. Hence, / except when the code is a maximum rank distance (MRD) xj can be expanded to an m-dimensional column vector cs code[5].Besidestheminimumrankdistance,therankweight (x0,j,x1,j,...,xm−1,j)T with respect to the basis set : distribution is an importantproperty of any rank metric code, {α0,α1,...,αm−1}. Let X be the m×n matrix obtained by v and determines its error performance in applications. expanding all the coordinates of x. That is, i X In this paper, we investigate the rank weight properties of r linear codes. The main result of this paper is that, similar to x0,0 x0,1 ... x0,n−1 a  x1,0 x1,1 ... x1,n−1  twheeigMhtacdWisitlrliibaumtisonideonftiatynyfolrintehaer Hcoadmemcianng bmeeterxicp,rethsseedranaks X= ... ... ... ... ,   an analytical expression of that of its dual code. Our new  xm−1,0 xm−1,1 ... xm−1,n−1    identity is a significant analytical tool for both rank weight distribution and hence error performance analysis of linear where xj = mi=−01xi,jαi. The rank norm of the vector codes. To our best knowledge, no similar result exists in the x (over GF(q)P), denoted as rk(x|GF(q)), is defined to be def literature. It is also remarkable that our new MacWilliams the rank of the matrix X over GF(q), i.e., rk(x|GF(q)) = identity for the rank metric has a similar form to that for rank(X) [5]. In this paper, all the ranks are over the base the Hamming metric. Despite the similarity, our new identity field GF(q) unless otherwise specified. To simplify notations, is proved using a different approach based on linear spaces. we denote the rank norm of x as rk(x) henceforth. Using the same approach, we give an alternative proof of the The rank norm of x is also the number of coordinates in MacWilliams identity for the Hamming metric. Based on our x that are linearly independent over GF(q) [5]. The field newidentity,wealsoderiveanexpressionthatrelatesmoments GF(qm) may be viewed as an m-dimensional vector space of the rank distribution of a linear code to those of its dual overGF(q). Thecoordinatesof x thusspana linearsubspace code,andprovideanalternativederivationfortherankweight of GF(qm), denoted as S(x), and the rank of x is the distribution of MRD codes. dimension of S(x). Forallx,y∈GF(qm)n,itiseasilyverifiedthatd (x,y)d=ef Gaussian binomial [16], defined as n = α(n,u)/α(u,u). R u rk(x−y) is a metric over GF(qm)n, referred to as the rank Notethat n isthenumberofu-dime(cid:2)ns(cid:3)ionallinearsubspaces u metric henceforth [5]. The minimum rank distance of a code, of GF(q)(cid:2)n.(cid:3)We also define β(m,0) d=ef 1 and β(m,u) d=ef dpeonssoitbeldeapsaidrsR,oifsdsiismtipnlcyt cthoedemwionridmsu.m rank distance over all ui=−01 m1−i foru>0,whichareusedinSectionIII-A.These Qtermsa(cid:2)recl(cid:3)oselyrelatedtotheGaussianbinomial:β(m,u)= m β(u,u) and β(m+u,m+u)= m+u β(m,m)β(u,u). B. The Singleton bound and MRD codes u u (cid:2) (cid:3) (cid:2) (cid:3) The minimum rank distance of a code can be specifically III. MACWILLIAMS IDENTITYFOR THERANK METRIC bounded. First, the minimum rank distance d of a code R of length n over GF(qm) is obviously bounded above by A. q-product and q-derivative of homogeneous polynomials min{m,n}.CodesthatsatisfydR =marestudiedin[8].Also, Definition 4 (q-product): Let a(x,y;m) = it can be shown that dR ≤ dH [5], where dH is the minimum ri=0ai(m)yixr−i and b(x,y;m) = sj=0bj(m)yjxs−j be Hamming distance of the same code. Due to the Singleton Ptwo homogeneouspolynomialsin x anPd y of degrees r and s bound on the minimum Hamming distance of block codes respectively with coefficients a (m) and b (m) respectively. i j [15], the minimum rank distance of a block code of length n a (m) and b (m) for i,j ≥ 0 in turn are real functions of i j (n≤m) and cardinality M over GF(qm) thus satisfies m, and are assumed to be zero unless otherwise specified. The q-product of a(x,y;m) and b(x,y;m) is defined to be d ≤n−log M +1. (1) R qm def the homogeneous polynomial of degree (r+s) c(x,y;m) = Asin[5],werefertocodesthatachievetheequalityinEq.(1) a(x,y;m)∗b(x,y;m)= r+s c (m)yuxr+s−u, with u=0 u as MRD codes. It is also shown that the dual of any MRD P code is also an MRD code [5]. Clearly MRD codes are the u counterparts of maximum distance separable (MDS) codes. cu(m)= qisai(m)bu−i(m−i). Xi=0 C. Weight enumerator and Hadamard transform For n≥0 the n-th q-power of a(x,y;m) is defined recur- We restrict our attention to the Hamming metric and the sively:a(x,y;m)[0] =1anda(x,y;m)[n] =a(x,y;m)[n−1]∗ rank metric only henceforth in this paper. a(x,y;m) for n≥1. Definition 1 (Weight function): Let d be a metric over Toillustratetheq-product,weprovidesomeexamplesofthe GF(qm)n, and define w(v) = d(0,v) as a weight over q-product.Wehavex∗y =yx,y∗x=qyx,yx∗x=qyx2,and GF(qm)n. Suppose v ∈ GF(qm)n has weight r, then the yx∗(qm−1)y =(qm−q)y2x.Notethatx∗y 6=y∗x.Itiseasy weight function of v is defined as f (v)=yrxn−r. w to verify that the q-product is in general non-commutative. We shall henceforth denote the Hamming weight function However, it is commutative for some special cases. and the rank weight function as f and f respectively. Note H R Lemma 1: Suppose a(x,y;m) = a is a constant indepen- that n is the maximum weight for both f and f . H R dent from m, then a(x,y;m) ∗ b(x,y;m) = b(x,y;m) ∗ Definition 2: Let C be a code of length n over GF(qm). a(x,y;m) = ab(x,y;m). Also, if deg[c(x,y;m)] = Suppose there are A codewords in C with weight i, then the i deg[a(x,y;m)], then [a(x,y;m)+c(x,y;m)]∗b(x,y;m) = weight enumerator of C, denoted as WC(x,y), is defined as a(x,y;m)∗b(x,y;m)+c(x,y;m)∗b(x,y;m),andb(x,y;m)∗ n [a(x,y;m)+c(x,y;m)]=b(x,y;m)∗a(x,y;m)+b(x,y;m)∗ WCw(x,y)d=ef fw(v)= Aiyixn−i. c(x,y;m). Definition 3 (HadamavXr∈dCtransformXi[=105]): Let C be the The homogeneous polynomials al(x,y;m) d=ef [x+(qm − field of complex numbers. Let a ∈ GF(qm) and let 1)y][l] and bl(x,y;m)d=ef(x−y)[l] turn out to be very impor- {1,α1,...,αm−1} be a basis set of GF(qm). We thus have tant to our derivations below. The following lemma provides a = a0 +a1α1 +...+am−1αm−1. Finally, let ζ ∈ C be the analytical expressions of al(x,y;m) and bl(x,y;m). a primitive q-th root of unity. We define χ(a) d=ef ζa0. For Lemma 2: For i ≥ 0, σi d=ef i(i−21). For l ≥ 0, we have a mapping f from F to C, the Hadamard transform of f, y[l] =qσlyl and x[l] =xl. Furthermore, denoted as fˆ, is given by l l fˆ(v)d=ef χ(u·v)f(u). (2) al(x,y;m)= (cid:20)u(cid:21)α(m,u)yuxl−u, (3) uX∈F uX=0 l l D. Notations bl(x,y;m)= (−1)uqσuyuxl−u. (4) (cid:20)u(cid:21) In orderto simplify notations,we shall occasionallydenote uX=0 the vector space GF(qm)n as F. We denote the number of Note that al(x,y;m) is the rank weight enumerator of vectors of rank u (0 ≤ u ≤ min{m,n}) in GF(qm)n as GF(qm)l. N (qm,n). It can be shown that N (qm,n) = n α(m,u), Definition 5 (q-transform): We define the q-transform of whuere α(m,u) is defined as follouws: α(m,0)(cid:2)u=(cid:3) 1 and a(x,y;m) = ri=0ai(m)yixr−i as the homogeneous poly- α(m,u) = ui=−01(qm −qi) for u ≥ 1. The nu term is the nomial a¯(x,y;Pm)= ri=0ai(m)y[i]∗x[r−i]. Q (cid:2) (cid:3) P Definition 6 (q-derivative [17]): For q ≥ 2, the q- MRD codes has been derived in [5]. However, we will use derivative for x6=0 of a real-valued function f(x) is defined ourresults to give an alternativederivationof the rankweight as distributionofMRD codeslater,andthuswe shallnotusethe f(qx)−f(x) f(1)(x)d=ef . result in [5] here. (q−1)x Lemma 7: For r ≥ 1, suppose vr = (v0,...,vr−1) ∈ Theq-derivativeoperatorislinear. Forν ≥0,we shalldenote GF(qm)r has rank r ≤ m. Then the number of vectors in ⊥ the partial ν-th q-derivative of f(x,y) (with respect to x) as Lr =hvri with rank r, denoted as Ar,r, depends on only r f(ν)(x,y). The 0-th q-derivative of f(x,y) is defined to be andsatisfiesAr,r =α(m,r−1)−qr−1Ar−1,r−1.Furthermore, f(x,y) itself. the rank weight enumerator of Lr is given by Lemma 3: For ν ≤n, the ν-th q-derivative of the function WR (x,y)=q−m [x+(qm−1)y][r]+(qm−1)(x−y)[r] . xn is given by β(n,ν)xn−ν. Also, the ν-th q-derivative Lr n o of f(x,y) = r f yixr−i is given by f(ν)(x,y) = Thefollowinglemmarelatestherankweightenumeratorof ri=νfiβ(i,ν)xiP−νi.=0 i a cLoedmemtoat8h:atLoeftaCny⊆ofGitFs(sq-mth)rorbdeeraelleinmeeanrtcaorydeexwteitnhsiroannsk. PLemma 4 (Leibniz rule): For two homogeneouspolynomi- 0 als f(x,y) = ri=0fiyixr−i and g(x,y) = sj=0gjyjxs−j wbeeitghhetreannukmweeriagthotreWnuCRm0(exr,ayto)r, oafnditsfosr-ths o≥rd0er, Blet-eWlemCRse(nxt,ayry) withdegreesrPandsrespectively,theν-th(ν ≥P1)q-derivative extension C . Then WR (x,y) does not depend on B and is of their q-product is given by s C s given by ν ν (f(x,y)∗g(x,y))(ν) = q(ν−l)(r−l)··· WR (x,y)=WR (x,y)∗[x+(qm−1)y][s]. (8) (cid:20)l(cid:21) Cs C0 Xl=0 Combining Corollary 1, Lemma 7, and Lemma 8, the rank ··· f(l)(x,y)∗g(ν−l)(x,y). (5) weight enumerator of hvi⊥ can be determined at last. Next, we derive the q-derivatives of a (x,y;m) = [x + Proposition 1: For v ∈ GF(qm)n with rank r ≥ 0, the l (qm−1)y][l] and b (x,y;m)=(x−y)[l]. rank weight enumerator of L=hvi⊥ dependson only r, and l Lemma 5: For ν ≤l we have is given by al(ν)(x,y;m) = β(l,ν)al−ν(x,y;m) (6) WLR(x,y) = q−m [x+(qm−1)y][n]+(qm−1)··· bl(ν)(x,y;m) = β(l,ν)bl−ν(x,y;m). (7) ··· (x−ny)[r]∗[x+(qm−1)y][n−r] . (9) o B. The dual of a vector C. MacWilliams identity As an important step toward our main result, we derive the rank weight enumerator of hvi⊥, where v ∈ GF(qm)n UsingtheresultsshowninSectionIII-B,wenowderivethe MacWilliams identity for rank metric codes. is an arbitrary vector and hvi d=ef {av:a∈GF(qm)}. It is Lemma 9: Suppose that for all λ ∈ GF(qm)∗ and all ⊥ remarkable that the rank weight enumerator of hvi depends u ∈ F, we have w(λu) = w(u). For v ∈ GF(qm)n, let on only the rank of v. ⊥ us denote hvi as L. Then the Hadamard transform of the Definition 7: For s ≥ 1 the s-th order B-elementary weight function f , denoted as fˆ , satisfies w w extension of an (n,k) linear code C is the (n + s,k + 0 s) linear code defined as Cs d=ef {(c0,...,cn+s−1) ∈ WLw(x,y)=q−m WFw(x,y)+(qm−1)fˆw(v) . (10) GF(qm)n+s|(c0,...,cn−1) − (cn,...,cn+s−1)B ∈ C0}, Lemma 10: Supposhe v ∈ GF(qm)n has rank r.iThen the where B is an s × n matrix over GF(q). The 0-th order Hadamard transform of the rank weight function is given by elementary extension of C is defined to be C itself. Lemma 6: Let C0 be a0n (n,k) linear code0 over GF(qm) fˆR(v)=(x−y)[r]∗[x+(qm−1)y][n−r]. (11) with generator matrix G and parity-check matrix H . The Let C be an (n,k) linear code over GF(qm), and let ss)-thlinoerdaerrcBod-eeleCmsenotvareyr0eGxFte(nqsmio)n wofithC0aisgtehneer(anto+r 0ms,aktri+x WanCdR(xW,CyR⊥)(=x,yP) ni==0Ainjy=i0xBn−jyijbxen−itjs braentkhewreaingkhtweeniugmhtereantuo-r G 0 merator of its dualPcode C⊥. Gs = (cid:18) B0 Is (cid:19) and a parity-check matrix Hs = Theorem 1: For any linear code C and its dual code C⊥, H −H BT . 0 0 1 (cid:0) Corollary 1: Su(cid:1)ppose v=(v0,...,vn−1)∈GF(qm)n has WCR⊥(x,y)= |C|W¯CR(x+(qm−1)y,x−y), (12) ⊥ rank r ≥ 1. Then L = hvi is equivalent to the (n−r)-th order elementary extension of an (r,r−1) linear code with where W¯CR is the q-transform of WCR. Equivalently, d =2. n n R It is easy to verify that the (r,r −1) code with d = 2 is B yjxn−j =qm(k−n) A (x−y)[i]∗[x+(qm−1)y][n−i]. R j i actually an MRD code as defined in Section II-B. Xj=0 Xi=0 We hence derive the rank weight enumerator of an (r,r− (13) 1,2) MRD code. Note that the rank weight distribution of Also, Bj’s can be explicitly expressed in terms of Ai’s. Corollary 2: We have We remark that the above rank distribution is consistent with n that derived by Gabidulin in [5]. 1 B = A P (i;m,n), (14) j i j |C|Xi=0 F. Examples where In this section, we illustrate Theorem 1 and Proposition 2 j using some examples. For m ≥ 2, consider the (3,2) linear i n−i Pj(i;m,n)d=ef (cid:20)l(cid:21)(cid:20)j−l(cid:21)(−1)lqσlql(n−i)α(m−l,j−l). code C1 over GF(qm) with generator matrix Xl=0 (15) 1 α 1 G = , 1 (cid:18) 1 α 0 (cid:19) D. Moments of the rank distribution Next, we investigate the relationship between moments of where α is a primitive element of GF(qm). It can be verified the rank distribution of a linear code and those of its dual thattherankweightenumeratorofC isgivenbyWR (x,y)= 1 C1 code. Our results parallel those in [15, p. 131]. x3+(qm−1)yx2+q2(qm−1)y2x+(qm−q2)(qm−1)y3. First, applying Theorem 1 to C⊥, we obtain Applying Theorem 1, we obtain WR (x,y) = x3 +(qm − C⊥ 1 n n 1)y2x. We can verify by hand that WR (x,y) is indeed the Aiyixn−i =qm(k−n) Bjbj(x,y;m)∗an−j(x,y;m). rank weight enumerator of C⊥, which hC1⊥as a generator matrix Xi=0 Xj=0 H =( −α 1 0 ). ForC1, bothsides of (17) are givenby (16) 1 1 q2m,qm 3 ,(qm−1+ 3 ),and1forν =0,1,2,3respectively. By q-differentiating Eq. (16) ν times with respect to x and 1 1 using the Leibniz rule in Lemma 4 as well as the results in Note tha(cid:2)t t(cid:3)he results h(cid:2)o(cid:3)ld when m=2<n=3. Lemma 5, we obtain For m ≥ 4, let us now consider the (4,2) code C2 over Proposition 2: For 0≤ν ≤n, GF(qm) with the following generator matrix n−ν n−i ν n−j 1 α α2 α3 (cid:20) ν (cid:21)Ai =qm(k−ν) (cid:20)n−ν(cid:21)Bj. (17) G2 =(cid:18) 1 αq α2q α3q (cid:19). Xi=0 Xj=0 As in [15], we refer to the left hand side of Eq. (17) as C is actually a (4,2) MRD code with d = 3. Hence, its 2 R moments of the rank distribution of C. We remark that the dual code C⊥ is also a (4,2) MRD code with d = 3. 2 R cases where ν =0 and ν =n are trivial. Also, Proposition 2 The rank weight enumerators of both C and C⊥ can be 2 2 can be simplified if ν is less than the minimum distance of readily obtained using Proposition 3, and they are given the dual code. by WR (x,y) = WR (x,y) = x4 + 4 (qm − 1)y3x1 + If Cνo<rodll′a,rtyhe3n: Let d′R be the minimum rank distance of C⊥. q2m−C21− 41 (qm−C2⊥1) y4.Itcanbeve(cid:2)r1ifi(cid:3)edthatWCR2(x,y) R (cid:8)and WCR⊥(x,(cid:2)y)(cid:3) satisfy T(cid:9)heorem 1. For C2, it can also be n−ν n−i A =qm(k−ν) n . (18) verified2that both sides of (17) are q2m, 41 qm, 42 , 41 , and (cid:20) ν (cid:21) i (cid:20)ν(cid:21) 1 for ν =0,1,··· ,4 respectively. (cid:2) (cid:3) (cid:2) (cid:3) (cid:2) (cid:3) Xi=0 Finally, consider the (7,4) code C over GF(24) with the E. Rank distribution of MRD codes 3 following generator matrix The rank distribution of MRD codes was first given in [5]. BasedonourresultsinSectionIII-D,weprovideanalternative 1 0 0 0 β3 β6 β12 derivation of the rank distribution of MRD codes. In this  0 1 0 0 β6 β12 0  G = , subsection, we assume n≤m. 3 0 0 1 0 β12 0 β3   First, we obtain the following results necessary for our  0 0 0 1 0 β3 β6    alternative derivation of the rank distribution. whereβ isaprimitiveelementofGF(24).Itsrankweightenu- Lemma 11: Let {a }l and {b }l be two sequences j j=0 i i=0 meratoris givenbyWR (x,y)=x7+105y2x5+7350y3x4+ of real numbers. Suppose that for 0 ≤ j ≤ l we have C3 a = j l−i b . Then for 0 ≤ i ≤ l we have b = 58080y4x3, Theorem 1 indicates that the rank weight enu- j i=0 l−j i i merator of its dual code is given by WR (x,y) = x7 + ij=0(−P1)i−j(cid:2)qσi−(cid:3)j ll−−ji aj. 465y3x4+3630y4x3, which can be verifieCd3⊥using exhaustive PBased on Corolla(cid:2)ry 3(cid:3)and using Lemma 11, we can derive search. It can also be verified that both sides of (17) for C the rank distribution of MRD codes when n≤m: 3 are 216,520192,682752,196416,22416,2772,127, and 1 for Proposition 3 (Rank distribution of MRD codes): Let C be an (n,k,d ) MRD code over GF(qm) (n ≤ m), and let ν =0,1,··· ,7 respectively. R WR(x,y) = n A yixn−i be its rank weight enumerator. C i=0 i IV. MACWILLIAMS IDENTITYFORTHEHAMMING METRIC We then havePA0 =1 and for 0≤i≤n−dR, In this section, we adapt the approach used in our proof of i n d +i A = (−1)i−jqσi−j R qm(j+1)−1 . Theorem1toprovideanalternativeproofoftheMacWilliams dR+i (cid:20)dR+i(cid:21)Xj=0 (cid:20)dR+j(cid:21)(cid:16) (cid:17) identityfortheHammingm⊥etric.WefirstderivetheHamming (19) weight enumerator of hvi , where v is an arbitrary vector. Then, using this result and properties of the Hadamard trans- We remark that the MacWilliams identities for the Hamming form, we obtain the MacWilliams identity for the Hamming and the rank metrics given in Theorems 2 and 1 respectively metric. have exactly the same form except for the q-transform in Definition 8: Fors≥1,thes-thordercoordinateextension Eq. (12). Note that Theorem 2 is precisely the MacWilliams ofan(n,k)linearcodeC isdefinedasthe(n+s,k+s)code identity for the Hamming metric given by Theorem 13 in 0 Cs d=ef{(c0,...,cn+s−1)∈GF(qm)n+s|(c0,...,cn−1)∈C0}. [15, Chap. 5], although our proof is different from that in The 0-th order coordinate extension of C is defined as C [15, Chap. 5]. Finally, we remark that Theorem 13 in [15, 0 0 itself. Chap. 5] is a special case of the MacWilliams Theorem Weremarkthatthes-thordercoordinateextensionisaspecial for complete weight enumerators (see Theorem 10 in [15, case of the s-th order B-elementary extension with B=0. Chap. 5]). For the rank metric, it is not clear how we can Lemma 12: Let C be an (n,k) linear code over GF(qm), adapt the concept of complete weight enumerator to give a 0 with a generator matrix G and a parity-check matrix proof of the MacWilliams identity. 0 H . Then C over GF(qm) has a generator matrix G = 0 s s REFERENCES G 0 0 and a parity-check matrix H = H 0 . (cid:18) 0 Is (cid:19) s 0 [1] V. Tarokh, N. Seshadri, and A. R. Calderbank, “Space-time codes for Corollary 4: Suppose v∈GF(qm)n has Ham(cid:0)ming weig(cid:1)ht highdataratewirelesscommunication: Performancecriterion andcode construction,” IEEE Trans. Info. Theory, vol. 44, pp. 774–765, March ⊥ r ≥ 1. Then L = hvi is equivalent to the (n−r)-th order 1998. coordinate extension of an (r,r−1,2) MDS code. [2] P.Lusina,E.M.Gabidulin,andM.Bossert,“MaximumRankDistance codesasspace-timecodes,”IEEETrans.Info.Theory,vol.49,pp.2757– We hence derive the Hamming weight distribution of an 2760,Oct.2003. (r,r −1,2) MDS code. Note that [15] gives the Hamming [3] E.M.Gabidulin, A.V.Paramonov,andO.V.Tretjakov,“Ideals overa weight distribution of all MDS codes. However, that proof non-commutative ring and their application in cryptology,” LNCS, vol. 573,pp.482–489,1991. relies on the MacWilliams identity, and thus may not be used [4] R. M. Roth, “Maximum-rank array codes and their application to here. crisscross error correction,” IEEE Trans. Info. Theory, vol. 37, no. 2, Lemma 13: Suppose vr = (v0,...,vr−1) ∈ GF(qm)r has pp.328–336, March1991. ⊥ [5] E. M. Gabidulin, “Theory of codes with maximum rank distance,” Hammingweightr. ThenL =hv i isan(r,r−1,2)MDS r r Problems on Information Transmission, vol. 21, no. 1, pp. 1–12, Jan. code whose weight enumeratordoes not depend on vr and is 1985. given by [6] N. Suresh Babu, “Studies on rank distance codes,” Ph.D Dissertation, IITMadras,Feb.1995. WH (x,y)=q−m{[x+(qm−1)y]r+(qm−1)(x−y)r}. [7] W.B.Vasantha andN.SureshBabu,“Onthecovering radius ofrank- Lr distance codes,”GanitaSandesh,vol.13,pp.43–48,1999. The followinglemma relates the Hammingweightenumer- [8] K. N. Manoj and B. Sundar Rajan, “Full Rank Distance codes,” ator of a code to that of its s-th order coordinate extension. Technical Report,IIScBangalore,Oct.2002. Lemma 14: Let C ⊆ GF(qm)r be a linear code with [9] W.B.VasanthaandR.J.Selvaraj, “Multi-covering radiiofcodes with 0 rankmetric,” Proc.InformationTheoryWorkshop,p.215,Oct.2002. Hamming weight enumerator WH (x,y), and for s ≥ 0 C0 [10] W.B. Vasantha and R. S.Raja Durai, “Maximum rank distance codes let WH (x,y) be the weight enumerator of its s-th order with complementary duals: an application to F-adder channel,” Dec. C coordinsate extension C . Then 2002. s [11] U.SripatiandB.SundarRajan,“Ontherankdistanceofcycliccodes,” WH (x,y)=WH (x,y)·[x+(qm−1)y]s. (20) Proc.IEEEInt.Symp.onInformation Theory,p.72,July2003. Cs C0 [12] A. Kshevetskiy and E. M. Gabidulin, “The new construction of rank Combining Corollary 4, Lemma 13, and Lemma 14, the codes,” Proc. IEEEInt. Symp. onInformation Theory, pp.2105–2108, Hamming weight distribution of L can eventually be deter- Sept.2005. mined. [13] E. M. Gabidulin and P. Loidreau, “On subcodes of codes in the rank metric,” Proc. IEEE Int. Symp. on Information Theory, pp. 121–123, Proposition 4: For v ∈ GF(qm)n with wH(v) = r, the Sept.2005. ⊥ Hamming weight enumerator of L = hvi depends on only [14] P.Loidreau, “Properties ofcodesinrankmetric,” preprint. [15] F.MacWilliamsandN.Sloane,TheTheoryofError-CorrectingCodes. w (v), and is given by H Amsterdam:North-Holland, 1977. [16] G.E.Andrews, The Theory ofPartitions, ser. Encyclopedia ofMathe- WLH(x,y) = q−m [x+(qm−1)y]n+(qm−1)··· matics andits Applications, G.-C.Rota, Ed. Reading, MA:Addison- n Wesley,1976,vol.2. ··· (x−y)r[x+(qm−1)y]n−r . (21) [17] G. Gasper and M. Rahman, Basic Hypergeometric Series, 2nd ed., Lemma 15: Suppose v ∈ GF(qm)n has Hamoming weight ser. Encyclopedia of Mathematics and its Applications. Cambridge University Press,2004,vol.96. r. Then the Hadamard transform of the Hamming weight function is given by fˆ(v)=(x−y)r[x+(qm−1)y]n−r. (22) H Using Lemma 15, we finally establish the MacWilliams identity for the Hamming metric. Theorem 2: For any linear code C, we have 1 WH (x,y)= WH(x+(qm−1)y,x−y). (23) C⊥ |C| C