On ZRM codes Borges, J.(a) * ; Fern´andez, C.(a) ;Phelps, K.T. (b) (a) Department
of Information and Communications Engineering Universitat Aut`onoma de Barcelona. 08193-Bellaterra, Spain
[email protected],
[email protected] (b) Department
of Mathematics & Statistics Auburn University. Auburn, Alabama.
[email protected]
Abstract. Quaternary Z RM (r, m) codes were defined to study the Z 4 -linearity of ReedMuller codes. In the literature two different definitions of such codes can be found, denoted Z RM (r, m) and Z RM ∗ (r, m). We will show that both definitions are equivalent exactly for those values of r such that their binary images are Reed-Muller codes. We will compute the rank and the kernel of their binary image. Keywords. Reed-Muller codes, quaternary codes, rank, kernel
1. Introduction There are different families of quaternary codes related to the Reed-Muller codes. The first family of codes are the QRM(r, m) codes defined in [2]. In [1], the class QRM (r, m) is defined as a generalization of QRM(r, m) codes. In that paper, various properties of codes in QRM (r, m) are established including the rank and the dimension of the kernel. The second family, Z RM (r, m) codes, were defined to prove that Reed-Muller codes RM(r, m) were Z4 -linear codes for some values of the parameter r. In the literature there are different definitions of these codes. Comparing the definitions of such codes in [2] and [5], we found that, in fact, they coincide when the related Reed-Muller code is Z4 -linear but they differ in the other cases. Section 2 reviews constructions and some of the properties of Reed-Muller codes. Section 3, presents the definitions and constructions of Z RM codes in [2] and [5] and establishes the difference between both definitions. We will prove the * This work has been partially supported by Spanish CICYT grant TIC2003-08604-C04-01 and Catalan DURSI grant SGR2005-00319.
163
164
Borges, J. et al.
linearity of codes in the first definition and we will give the rank and dimension of the kernel of codes in the second one. In the remainder of this section we introduce the basic definitions and prior results which will be needed. 1.1. Definitions and Notation Let Zn2 be the n-dimensional binary vector space. We denote by 0 the all-zero vector and by 1 the all-one vector. As usual, the (Hamming) distance between two vectors x, y ∈ Zn2 is the number of coordinates in which they differ and it is denoted by d(x, y). The weight of a vector x ∈ Zn2 is the number of its nonzero entries. For u = (u1 , · · · , un ), v = (v1 , · · · , vn ) ∈ Zn2 , we use uv to denote the componentwise product of u and v. Let R be a ring and A, B ⊆ R. A + x ⊆ R is defined as {a + x | a ∈ A}, for x ∈ R, and A + B as the subset {a + b | a ∈ A, b ∈ B}. Let A be a subset of Zn2 then, < A > denotes the linear subspace spanned by A. The rank of a binary code, C, denoted by rank(C) is the dimension of the linear subspace < C >. The kernel of C is defined as ker(C) = {x ∈ C | C = C + x}, dim(ker(C)) denotes the dimension of the kernel. A quaternary code, or Z4 -code, C of length n is a linear block code over Zn4 ; i.e. an additive subgroup of Zn4 . Any Z4 -code C is permutation-equivalent to a code C 0 with generator matrix of the form
Idk1 0
A 2Idk2
B 2C
,
where A and C are matrices over Z2 and B is a matrix over Z4 . |C | = 22k1 +k2 and we say that C is of type 4k1 2k2 (see [2]). Let α : Zn4 → Zn2 defined by α (x) = x (mod 2) and let φ : Z4 → Z22 be the usual Gray map given by φ (0) = 00, φ (1) = 01, φ (2) = 11 and φ (3) = 10. The extended Gray map, from Zn4 to Z2n 2 , applies φ coordinate-wise, i.e. φ (x) = (φ (x1 ), . . . , φ (xn )). A binary code C is Z4 -linear if it is equivalent under coordinate permutation to the extended Gray map image φ (C ) of some quaternary code C ⊆ Z n4 . Some authorities refer to the composition of the extended Gray map and a permutation as a general Gray map. In effect, a general Gray map associates each Z4 coordinate i with a pair of binary coordinates {i1 , i2 } inducing a partition. The definitions and arguments that follow are valid for any such partition and thus φ can be any general Gray map unless it is said otherwise. In such case, the particular coordinate permutation will be given. However, as a matter of notational convenience and ease of argument we will often represent φ as the extended Gray map.
On ZRM codes
165
The dimension of the kernel and the rank of C are the dimension of the kernel and the rank of its binary image (dim(ker(φ (C ))), rank(φ (C ))). If A is a subset of Zn4 , then < A >4 denotes the subgroup spanned by A. Let C ⊆ Zn2 be a binary linear code. Note that C can also be considered as a subset of Zn4 and it can be spanned in the space Zn4 ; C 4 . As C is a linear code, given two . vectors x, y ∈ C, their binary sum belongs to C and, therefore, it belongs to C 4
Moreover, as x, y ∈ C 4 , their quaternary sum also belongs to C 4 . In many cases we are interested in both, the binary and the quaternary sum of codewords. In order to avoid confusion, any binary sum of codewords x, y ∈ Z n2 will be denoted x +b y and any quaternary sum of x, y ∈ Zn4 is denoted simply by x + y.
2. Reed-Muller codes Consider a m × 2m binary matrix where the columns consist of all binary mm tuples. Let v1 , v2 , . . . vm be the row vectors of this matrix in Z22 . For convenience, we can assume the columns of the matrix are in canonical order so that the j-th coordinate of vi is 1 if and only if 2i−1 occurs in the binary expansion of j − 1. For example, v1 has 1 in all odd coordinates, v2 has 1 in coordinate j if and only if j ≡ 2, 3 (mod 4), etc. In this way, one stablishes a one to one correspondence between 2m vectors in Zm 2 and coordinates in Z2 . It is well-known that the automorphisms of the codes RM(r, m) correspond to the affine transformations of the space Z m 2 [4]. Let RM(r, m) be the r-th order Reed-Muller code of length 2m . RM(r, m) consists of all linear combinations of the vectors corresponding to the products 1, v1 , . . . , vm , v1 v2 , v1 v3 , . . . , vm−1 vm , . . . (up to degree r), which therefore form a basis for the code. Let PI (v1 , . . . , vm ) = ∏i∈I vi , I ⊆ {1, . . . , m}, where PI = 1 if |I| = 0, denote the basis vector corresponding to this product of variables. Therefore,
RM(r, m) = {PI (v1 , . . . , vm )}|I|≤r .
(1)
Lemma 1. Let I1 , I2 ⊆ {1, 2, . . . , m}. Then,
PI1 (v1 , . . . , vm )PI2 (v1 , . . . , vm ) = P(I1 ∪I2 ) (v1 , . . . , vm ). Theorem 1 ([4]). Let r, m be integers such that 0 ≤ r ≤ m. The Reed-Muller code RM(0, m) is the repetition code {0, 1} and RM(r + 1, m + 1) = {(u, u + v)|u ∈ RM(r + 1, m), v ∈ RM(r, m)}.
(2)
166
Borges, J. et al.
If G(r, m) is the generator matrix of the Reed-Muller code RM(r, m) then, G(0, m) = (1) and G(r + 1, m) G(r + 1, m) (3) G(r + 1, m + 1) = 0 G(r, m) The following theorem was partially proved in [2] and the equivalent of both statements was given lately in [3]. Theorem 2. The r-th order binary Reed-Muller code RM(r, m) of length n = 2 m , m ≥ 1, is Z4 -linear if and only if r = 0, 1, 2, m − 1 and m.
3. ZRM codes There are two different definitions of ZRM codes. Even though they are not equivalent definitions, in both cases they are used to prove the Z4 -linearity of RM(r, m) (whenever it is a Z4 -linear code). The first definition was given in [2] in 1994 and these codes will be denoted Z RM (r, m). The second one can be found in [5] (1997) and codes in such case are denoted Z RM ∗ (r, m). 3.1. Definitions of Z RM (r, m) and Z RM ∗ (r, m) codes Let m, r be integers such that 0 ≤ r ≤ m + 1. Let RM(r, m) be a r-th order binary Reed-Muller code, G(r, m) its generator matrix and PI (v1 . . . , vm ) its generator vectors for |I| ≤ r (Theorem 1), where RM(−1, m) = RM(m + 1, m) = {0} and G(−1, m) = G(m + 1, m) = (0). Let Z RM (r, m) be the quaternary code of length 2m generated by RM(r − 1, m) and 2RM(r, m);
(4) Z RM (r, m) = RM(r − 1, m), 2RM(r, m) 4 . Denote by ZRM(r, m) = φ (Z RM (r, m)) the Z4 -linear code of length 2m+1 . Let Z RM ∗ (r, m) be the Z4 -code of length 2m generated by the matrix G(r − 1, m) . 2G(r, m)
Note that Z RM ∗ (r, m) can be defined as Z RM ∗ (r, m) =
= {PI (v1 , . . . , vm ) | |I| ≤ r − 1} 4 + {2PI (v1 , . . . , vm ) | |I| ≤ r} 4 .
(5)
Denote by ZRM ∗ (r, m) = φ (Z RM ∗ (r, m)) the Z4 -linear code of length 2m+1 . In [2] and [5] the proof of the following Proposition can be found.
On ZRM codes
167
Proposition 1. Let r = 0, 1, 2, m − 1 and m. (i) ZRM(r, m − 1) = RM(r, m), (ii) ZRM ∗ (r, m − 1) = RM(r, m). As a corollary, for the values of r, m such that RM(r, m) is a Z4 -linear code, both definitions, Z RM (r, m − 1) and Z RM ∗ (r, m − 1), coincide and the binary image of such codes under the Gray map is, exactly, RM(r, m). So we have seen that for some values of r, m, Z RM (r, m) and Z RM ∗ (r, m) codes coincide. What is the difference between such codes? Let u1 , u2 be codewords in RM(r − 1, m). Since u1 and u2 belong to both codes, so does their quaternary sum. Now consider their binary sum u3 . By definition, u3 belongs to RM(r − 1, m) ⊆ Z RM (r, m) but it may not belong to Z RM ∗ (r, m). Thus, some of the codewords in Z RM (r, m) (obtained from the binary sum of codewords) may not be generated in Z4 by the generator vectors of Z RM ∗ (r, m) (equation (5)). We will give a set of generator vectors of Z RM (r, m) and will see that these codes are equivalent only for the values of r, m of the Proposition 1. Proposition 2. Let r, m be integers such that 2 ≤ r ≤ m + 1. Then,
Z RM (r, m) = RM(r, m) 4 =
= {PI (v1 , . . . , vm ) | |I| ≤ r − 1} 4 + {2PI (v1 , . . . , vm ) | r ≤ |I| ≤ t} 4 , where t = min{2r − 2, m}. Moreover,
Z RM (0, m) = {2} 4 ,
Z RM (1, m) = {1} 4 + {2PI (v1 , . . . , vm ) | |I| ≤ 1} 4 .
Proposition 3. Z RM (r, m) = Z RM ∗ (r, m) if and only if r = 0, 1, 2, m and m + 1. 3.2. Rank and kernel of Z RM (r, m) and Z RM ∗ (r, m) codes Proposition 4. Z RM (r, m) and Z RM ∗ (r, m) are quaternary codes of length ∗ ∗ 2m and type 4k1 2k2 and 4k1 2k2 respectively, where t r−1 m m m ∗ ∗ . , t = min{2r − 2, m}, and k2 = , k2 = ∑ k1 = k 1 = ∑ r i i=r i i=0 Proposition 5. Let r, m be integers such that 0 ≤ r ≤ m + 1. Therefore,
ZRM ∗ (r, m) = ZRM(r, m)
168
Borges, J. et al. As a corollary, we obtain that ZRM(r, m) are linear codes.
Proposition 6. ZRM(r, m) are linear codes and dim(ZRM(r, m)) =
r−1
∑
i=0
t m m , where t = min{2r − 2, m}. +∑ i i=0 i
By Proposition 1 for r = 0, 1, 2, m, m + 1, ZRM ∗ (r, m) is a linear code and, m+1 r ∗ ∗ therefore, rank(ZRM (r, m)) = dim(ker(ZRM (r, m)) = ∑i=0 i . We will establish the value of the rank and the dimension of the kernel for the rest of the values of r. Recall that ZRM ∗ (r, m) is the image of Z RM ∗ (r, m) under a general Gray map, that is, a composition of the extended Gray map and a coordinate permutation. Note that if C is a binary code, then rank(C) = rank(π (C)) and dim(ker(C)) = dim(ker(π (C))) for any coordinate permutation π . That way, in order to obtain the rank and the dimension of the kernel of ZRM ∗ (r, m) codes, we can apply a specific coordinate permutation to the extended Gray map. In all this section, we refer to the Gray map φ as the composition of the extended Gray map and a coordinate permutation π such that
φ (v1 , . . . , vn ) = (x1 , . . . , xn , y1 , . . . , yn ),
(6)
where xi , yi are the two binary coordinates related to the quaternary coordinate vi by the usual Gray map. Next theorems will give the value of the rank and the dimension of the kernel of ZRM ∗ (r, m) codes for the others values of r. Theorem 3. Let r, m be integers such that 3 ≤ r ≤ m − 1. ∗
rank(ZRM (r, m)) =
r−1
∑
i=0
t m m , +∑ i i=0 i
where t = min{m, 2r − 2}. Theorem 4. Let r, m be integers such that 3 ≤ r ≤ m − 1. m + m + 1. dim(ker(ZRM (r, m))) = ∑ i=0 i ∗
r
On ZRM codes
169
3.3. Z RM (r, m), Z RM ∗ (r, m) and RM(r, m) codes As we have seen in Proposition 1, φ (Z RM (r, m − 1)) = RM(r, m) for the values of r such that RM(r, m) is a Z4 -linear code. In this section we will prove that Z RM (r, m − 1) is, in fact, the minimum quaternary code C such that φ (C ) contains RM(r, m), where φ is the extended Gray map defined in (6). Thus, in all this section, φ will be such specific extended Gray map. Lemma 2. Let r, m be integers such that 0 ≤ r ≤ m. RM(r + 1, m + 1) = φ (RM(r, m)) + φ (2RM(r + 1, m)). Proposition 7. Let r, m be integers such that 0 ≤ r ≤ m + 1. Then, Z RM (r, m − 1) is the minimum quaternary code such that φ (Z RM (r, m − 1)) contains the code RM(r, m), where φ is the Gray map defined in (6). Note that last proposition does not give a minimum Z4 -linear code containing RM(r, m). There may exist a quaternary code C with cardinality less than Z RM (r, m − 1) and a coordinate permutation π such that π ◦ φ (C ) contains RM(r, m) (or, equivalently, a different extended Gray map φ 0 = π ◦ φ ). Nevertheless, with the last proposition we can assure the following statement. Corollary 1. Let C be a minimum Z4 -linear code containing RM(r, m). Then, t r−1 m−1 m−1 dim(C) ≤ ∑ +∑ , i i i=0 i=0 where t = min{m − 1, 2r − 2}.
4. Conclusion In this paper we have continued the classification of the different quaternary codes related to the binary Reed-Muller codes that appear in the literature. We have established that the families Z RM (r, m) and Z RM ∗ (r, m) only coincide when r = 0, 1, 2, m and m + 1, i.e., when RM(r, m + 1) is both linear and Z4 -linear. ∗ Otherwise
we∗ have that the binary images of Z RM (r, m) and Z RM (r, m) satisfy ZRM (r, m) = ZRM(r, m) and that ZRM(r, m) is linear. We have also established the rank and dimension of the kernel of these families of codes.
References [1] J. Borges, C. Fern´andez and K. Phelps, Quaternary Reed-Muller codes, IEEE Transactions on Information Theory 51, n.7, July 2005.
170
Borges, J. et al.
[2] A. Hammons, P. V. Kumar, A. R. Calderbank, N. J. A. Sloane and P. Sol´e, The Z4 -linearity of Kerdock, Preparata, Goethals and Related Codes, IEEE Transactions on Information Theory 40, pp. 301-319, 1994. [3] X.-D. Hou, J. T. Lahtonen and S. Koponen, The Reed-Muller Code R(r, m) is not Z4 -linear for 3 ≤ r ≤ m − 2, IEEE Transactions on Information Theory 44, pp. 798-799, 1998. [4] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland Publishing Company, 1977. [5] Z.-X. Wan, Quaternary Codes, World Scientific, 1997.
