8_siap.dvi


EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS

Vol. 5, No. 3, 2012, 373-379
ISSN 1307-5543 – www.ejpam.com

Macwilliams Identity for M-Spotty Hamming Weight

Enumerator Over the Ring F2+ vF2

Vedat Şiap1,∗, Mehmet Özen 2

1 Department of Mathematical Engineering, Faculty of Chemical and Metallurgical Engineering,

Yildiz Technical University, Istanbul, Turkey
2 Department of Mathematics, Faculty of Arts and Sciences, Sakarya University, Sakarya, Turkey

Abstract. The m-spotty byte error control codes can correct or detect multiple spotty byte errors that
are distributed in multiple bytes. These codes are successfully applied to computer memory systems
that use RAM chips with b-bit Input/Output data when high-energy particles strike a particular RAM
chips. In this paper, we derive a MacWilliams type identity for m-spotty Hamming weight enumerator
over the ring F2 + vF2 with v2 = v.

2010 Mathematics Subject Classifications: 94B15

Key Words and Phrases: MacWilliams identity; Weight enumerator; M-spotty weight; M-spotty byte
error

1. Introduction

The theory of error correcting codes has been studied for over half a century. Also, error
control codes have been extensively applied to various digital systems, such as computer and
communication systems, as an essential technique to improve system reliability. In the appli-
cations of error correcting codes to computer systems, a new class of byte error control codes
called m-spotty byte error control codes are very effective for correcting/detecting errors in
semiconductor memory systems that employ high-density RAM chips with wide Input/Output
data. These RAM chips are strongly vulnerable to α− particles, neutrons, and so forth. Be-
cause of these facts, in order to be able to correct multiple errors a special type of byte errors
called spotty byte errors has been introduced in [6, 7].

Suzuki et al. [5] introduced the MacWilliams identity for the m-spotty weight enumera-
tor of m-spotty byte error control codes and clarified that the indicated identity also includes
the MacWilliams identity for the Hamming weight enumerator over the binary field F2 or the
extension fields of the binary field F2. Özen and Şiap [4] generalized this result to arbitrary

∗Corresponding author.

Email addresses: vedatsiap�gmail.
om (V. Şiap), ozen�sakarya.edu.tr (M. Özen)

http://www.ejpam.com 373 c© 2012 EJPAM All rights reserved.



V. Şiap, M. Özen / Eur. J. Pure Appl. Math, 5 (2012), 373-379 374

finite fields. Morever, Şiap [1] extended the definition of m-spotty weight originally intro-
duced in [6] from binary codes to codes over the ring F2 + uF2 with u2 = 0. In this paper,we
establish a MacWilliams type identity for the m-spotty Hamming weight enumerator over the
ring F2 + vF2 with v2 = v.

The organization of this paper is as follows: In Section 2, definition of m-spotty Hamming
weight and m-spotty Hamming distance are presented. In Section 3, the MacWilliams identity
for m-spotty Hamming weight enumerator over the ring F2 + vF2 with v2 = v is established.
In Section 4, we give an example of how the weight distribution of the m-spotty byte error
control code can be applied. Finally, the paper concludes in Section 5.

2. Preliminaries

Let R2 be the commutative ring F2 + vF2 = {0,1, v, 1+ v}, where v2 = v. Any element
of R2 can be expressed as c = a+ bv, where a, b ∈ F2. Let N positive integer. For a positive
divisor b of N , C is said to be a byte error control code of length N and byte length b over R2

if and only if C is an R2−submodule of RN
2 . The elements of C are called codewords.

Let v =
�

v11, v12, . . . , v1b, . . . , vn1, vn2, . . . , vnb

�
∈ Rbn

2 be a vector of length N = bn. The
first byte of v consists of the first b entries denoted by

�
v11, v12, . . . , v1b

�
. Hence, the i th byte

of v will be denoted by vi =
�

vi1, vi2, . . . , vi b

�
. Then for any two vectors u =

�
u1,u2, . . . ,uN

�

and v =
�

v1, v2, . . . , vN

�
∈ RN

2 , the inner product of u and v, denoted by 〈u, v〉, is defined as
follows:

〈u, v〉=
n∑

i=1



ui , vi

�
=

n∑

i=1




b∑

j=1

ui j vi j


.

Here,


ui , vi

�
=

b∑
j=1

ui j vi j denotes the inner product of the bytes ui and vi. Also, ui j and vi j

are the j th bits of ui and vi, respectively.
For a byte error control code of length bn over R having byte length b, the set

C⊥ =
¦

v ∈ Rbn
2 : 〈c, v〉 = 0 for all c ∈ C

©

is called the dual code of C .
First, we define the t/b−error as follows:

Definition 1. [7] An error is said to be a t/b−error or a spotty byte error if t or fewer bits

within a b−bit byte are in error, where 1¶ t ¶ b.

If there exist more than t−bit errors in a byte, the errors are called multiple t/b−errors
in a byte.

Definition 2. [6] An error is said to be an m-spotty byte error if at least one t/b−error is present

in a byte.

We now present the following definitions in order to define the m-spotty Hamming weight
enumerator of byte error control code.



V. Şiap, M. Özen / Eur. J. Pure Appl. Math, 5 (2012), 373-379 375

Definition 3. [6] Let e ∈ RN
2 be an error vector and ei ∈ Rb

2 be the i th byte of e, where 1¶ i ¶ n.

The number of t/b−errors in e, denoted by wM (e), is called the m-spotty Hamming weight and

is defined as

wM (e) =

n∑

i=1

¢
w
�

ei

�

t

¥
,

where w
�

ei

�
denotes the Hamming weight of ei over R2, which is equal to the number of non-zero

components of ei . Here, ⌈x⌉ denotes the ceiling value of x, i.e., the number ⌈x⌉ is equal to the

smallest integer not less than x.

If t = b, the m-spotty Hamming weight equals to the Hamming weight in Rb
2. In addition,

if t = 1, then wM (e) = w (e).

Definition 4. [6] Let c =
�
c1, c2, . . . , cn

�
and v =

�
v1, v2, . . . , vn

�
be codewords of an m-spotty

byte error control code C. Here, ci and vi are the i th bytes of c and v, respectively. Then, the

m-spotty Hamming distance between c and v, denoted by dM (c, v), is defined as follows:

dM (c, v) =

n∑

i=1

¢
d
�
ci , vi

�

t

¥
=

n∑

i=1

¢
w
�

ci − vi

�

t

¥
= wM (c − v) ,

where d
�
ci , vi

�
= w

�
ci − vi

�
denotes the Hamming distance between i th bytes ci and vi for each

i over R2.

The following theorem is originally proved for the binary field F2 given in the paper [6].

Theorem 1. The m-spotty Hamming distance is a metric over R2.

Definition 5. [5] Let z be an indeterminate element. The m-spotty Hamming weight enumerator

of a byte error control code C is defined as follows:

WC (z) =
∑

c∈C

zwM (c).

For a codeword c, let α j (c) be the number of bytes having the Hamming weight j,
0 ¶ j ¶ b. The Hamming weight distribution vector

�
α0 (c) ,α1 (c) , . . . ,αb (c)

�
is uniquely

determined for the codeword c. Then, the m-spotty Hamming weight of the codeword c is

defined as wM (c) =
∑b

j=0

�
j
�
t
�

.α j (c). Let A(α0,α1,...,αb) be the number of codewords with the

Hamming weight distribution vector
�
α0,α1, . . . ,αb

�
. For example, let

(1v1 000 0v1 00v 010) ∈ R15
2 be a codeword with byte length b = 3. Then, the Hamming

weight distribution vector of the codeword is
�
α0,α1,α2,α3

�
= (1,2,1,1). Therefore, A(1,2,1,1)

is the number of codewords with the Hamming weight distribution vector (1,2,1,1).
By using the parameter A(α0,α1,...,αb), the m-spotty Hamming weight enumerator can be

rewritten as follows:

WC (z) =
∑

α0+α1+...+αb=n

A(α0,α1,...,αb)

b∏

j=0

�
z⌈ j/t⌉

�α j

, (1)

where
∑

α0+α1+...+αb=n

denotes the summation over all
�
α0,α1, . . . ,αb

�
’s satisfying the condi-

tions α0,α1, . . . ,αb ¾ 0 and α0 +α1 + . . .+αb = n.



V. Şiap, M. Özen / Eur. J. Pure Appl. Math, 5 (2012), 373-379 376

3. The MacWilliams Identity

One of the most celebrated results in coding theory is the MacWilliams identity [2] that
describes how the weight enumerator of a linear code and the weight enumerator of the dual
code relate to each other. This identity has found widespread application in coding theory
[3]. In this section, we obtain the MacWilliams identity for the m-spotty Hamming weight
enumerator over the ring F2+ vF2 with v2 = v.

The ring R2 is a principal ring. As for the ideal structure we can easily find all the ideals
of R2 which are

〈0〉= {0} , 〈v〉= {0, v} , 〈1+ v〉= {0,1+ v} , R2.

As we see from the ideals, the ring F2 + vF2 is not a finite chain ring. Also, these ideals are
the additive subgroups of R2. In this paper, we define the character χ for this ring as follows:

Definition 6. For a+ v b ∈ R2, we refer to the character χ defined by

χ (a+ v b) = (−1)b (2)

Note that χ is a nontrivial character. It can be easily seen that the character χ is a group
homomorphism. We get the following result by using the definition of the character χ in (2).

Lemma 1. [3] Let I 6= {0} be an ideal of R2. Then,
∑

a∈I

χ (a) = 0.

The following lemma plays an important role in proving Theorem 2:

Lemma 2. [3] Let f be a function defined on Rnb
2 . We define

ef (c) =
∑

v∈Rnb
2

χ (〈c, v〉) f (v) , c ∈ Rnb
2 .

Then, the following relation holds between f (v) and ef (c):
∑

v∈C⊥

f (v) =
1

|C |

∑

c∈C

ef (c),

where |C | denotes the size of the set C.

The following theorem holds for the m-spotty weight enumerator WC (z) of the byte error
control code C and that of the dual code C⊥, denoted by WC⊥ (z).

Theorem 2. Let the code length in bits N be a multiple of byte length b, i.e., N = nb. Then, the

following relation holds:

WC⊥ (z) =
1

|C |

∑

α0+α1+...+αb=n

A(α0,α1,...,αb)

b∏

j=0

��
V
(t)

j
(z)
��α j

,



V. Şiap, M. Özen / Eur. J. Pure Appl. Math, 5 (2012), 373-379 377

where

V
(t)

j
(z) =

b∑

p=0

 
p∑

s=0

(−1)p−s3s

�
j

p− s

��
b− j

s

�!
z⌈p/t⌉.

Proof. In Lemma 2, we set f (v) =
∏n

i=1 z⌈w(vi)/t⌉, where vi denotes the i th byte of v. Let
χ be the character defined in (2). Then,

ef (c) =
∑

v∈Rnb
2

χ (〈c, v〉)
n∏

i=1

z⌈w(vi)/t⌉

=
∑

v∈Rnb
2

χ
�


c1, v1
�
+


c2, v2

�
+ ..


cn, vn

�� n∏

i=1

z⌈w(vi)/t⌉

=
∑

v1∈Rb
2

∑

v2∈Rb
2

...
∑

vn∈Rb
2

 
n∏

i=1

χ
�


ci , vi

��
z⌈w(vi)/t⌉

!

=

n∏

i=1



∑

vi∈Rb
2

χ
�


ci , vi

��
z⌈w(vi)/t⌉


.

Let ci be a fixed vector. Then,
∑

vi∈Rb
2

χ
�


ci , vi

��
z⌈w(vi)/t⌉ depends on w(ci). Assume that the

Hamming weight of the fixed vector ci is w(ci) = j. For all vectors vi having Hamming weight
p, we obtain the equality as follows:

∑

w(vi)=p

χ
�


ci , vi

��
z⌈w(vi)/t⌉ =

p∑

s=0

(−1)p−s3s

�
j

p− s

��
b− j

s

�
z⌈p/t⌉.

Since w(vi) = p, the number of non-zero components of vi is p. The inner product of ci and
vi shows the number of positions in which the components of neither ci nor vi are zero. The

number of p− s positions chosen from j positions is

�
j

p− s

�
. Morever, there are s non-zero

elements of vi left. These elements are in b− j positions. The number of s non-zero positions

chosen from b− j positions is 3s

�
b− j

s

�
. Hence,

∑

vi∈Rb
2

χ
�


ci , vi

��
z⌈w(vi)/t⌉ =

b∑

p=0

 
p∑

s=0

(−1)p−s3s

�
j

p− s

��
b− j

s

�!
z⌈p/t⌉.

Hence, the function ef (c) is expressed as

ef (c) =
b∏

j=0

�
V
(t)

j
(z)
�α j

. (3)



V. Şiap, M. Özen / Eur. J. Pure Appl. Math, 5 (2012), 373-379 378

Substituting Eq. (3) in Lemma 2 we obtain

∑

v∈C⊥

b∏

j=0

�
z⌈ j/t⌉

�α j

=
1

|C |

∑

c∈C

b∏

j=0

�
V
(t)

j
(z)
�α j

.

Hence the proof is completed.

4. An illustrative Example

Let

G =

�
1 0 v 1 0 v

0 1 1 1+ v 0 1

�

be the generator matrix of byte error control code (or a linear code) C over F2+ vF2 of length
6. The dual code of C is a byte error control code of length 6 and it has 256 codewords.

Let b = 3 and t = 2. The codewords of the byte control code C , the Hamming weight

distribution vectors of the codewords of C and the corresponding V
(2)
j

expressions are shown
in Table 1 for the necessary computations to be used in Theorem 2.

Table 1: Codewords and Their Corresponding Terms.

Codeword
�
α0,α1,α2,α3

�
V
(2)

0 V
(2)

1 V
(2)

2 V
(2)

3

(0,0,0,0,0,0) (2,0,0,0) V
(2)

0 V
(2)

0

(0,1,1,1+ v, 0,1) (0,0,2,0) V
(2)

2 V
(2)

2

(0, v, v, 0,0, v) (0,1,1,0) V
(2)

1 V
(2)

2

(0,1+ v, 1+ v, 1+ v, 0,1+ v) (0,0,2,0) V
(2)

2 V
(2)

2

(1,0, v, 1,0, v) (0,0,2,0) V
(2)

2 V
(2)

2

(1,1,1+ v, v, 0,1+ v) (0,0,1,1) V
(2)

2 V
(2)

3

(1, v, 0,1,0,0) (0,1,1,0) V
(2)

1 V
(2)

2

(1,1+ v, 1, v, 0,1) (0,0,1,1) V
(2)

2 V
(2)

3

(v, 0, v, v, 0, v) (0,0,2,0) V
(2)

2 V
(2)

2

(v, 1,1+ v, 1,0,1+ v) (0,0,1,1) V
(2)

2 V
(2)

3

(v, v, 0, v, 0,0) (0,1,1,0) V
(2)

1 V
(2)

2

(v, 1+ v, 1,1,0,1) (0,0,1,1) V
(2)

2 V
(2)

3

(1+ v, 0,0,1+ v, 0,0) (0,2,0,0) V
(2)

1 V
(2)

1

(1+ v, 1,1,0,0,1) (0,1,0,1) V
(2)

1 V
(2)

3

(1+ v, v, v, 1+ v, 0, v) (0,0,1,1) V
(2)

2 V
(2)

3

(1+ v, 1+ v, 1+ v, 0,0,1+ v) (0,1,0,1) V
(2)

1 V
(2)

3

By Eq. (1) and Table 1, we get the m-spotty Hamming weight enumerator of C as follows:

WC (z) = 1+ 8z2 + 7z3.



REFERENCES 379

By using both Theorem 2 and Table 1, we obtain

WC⊥ (z) =
�

V
(2)

0

�2
+ 4
�

V
(2)

2

�2
+ 3V

(2)
1 V

(2)
2 + 5V

(2)
2 V

(2)
3 + 2V

(2)
1 V

(2)
3 +

�
V
(2)

1

�2

= 1+ 4z+ 85z2 + 118z3+ 48z4.

Here V
(2)

0 = 1+ 36z + 27z2, V
(2)

1 = 1+ 8z − 9z2, V
(2)

2 = 1− 4z+ 3z2 and V
(2)

3 = 1− z2.

5. Conclusion

In this paper, we prove a MacWilliams type identity for m-spotty Hamming weight enu-
merators over the ring F2 + vF2 with v2 = v. We conclude the paper by giving an illustration
of Theorem 2. This provides the relation between the m-spotty Hamming enumerator of the
code and that of the dual code.

References

[1] I Şiap. An identity between the m-spotty weight enumerators of a linear code and its
dual. Turkish Journal of Mathematics, TBD, Accepted in 2011.

[2] F J MacWilliams. A Theorem on the distribution of weights in a systematic code. Bell

System Tech. J., 42:79–94, 1963.

[3] F J MacWilliams and N J Sloane. The Theory of Error-Correcting Codes. North-Holland
Publishing Co., 1977.

[4] M Özen and V Şiap. The Macwilliams identity for m-spotty weight enumerators of linear
codes over finite fields. Comput. Math. Appl., 61(4):1000–1004, 2011.

[5] K Suzuki and E Fujiwara. Macwilliams identity for m-spotty weight enumerator. IEICE

Transactions, E93-A(2):526–531, 2010.

[6] K Suzuki, T Kashiyama, and E Fujiwara. A general class of m-spotty byte error control
codes. IEICE Transactions, 90-A(7):1418–1427, 2007.

[7] G Umanesan and E Fujiwara. A class of random multiple bits in a byte error correcting
and single byte error detecting codes. IEEE Trans. Computers, 52(7):835–847, 2003.