# Weight Distribution of Periodic Errors and Optimal/Anti-Optimal Linear Codes

Authors: Pankaj Kumar Das
Journal: Journal of Mathematics
 (2014)

---

## Abstract

The paper discusses weight distribution of periodic errors and then the optimal case on bounds of parity check digits for (n=n1+n2, k) linear codes over GF(q) that corrects all periodic errors of order r in the first block of length n1 and all periodic errors of order s in the second block of length n2 and no others. Further, we extend the study to the case when the errors are in the form of periodic errors of order r (and s) or more in the two subblocks.


---

## Body

## 1. Introduction

In coding theory, many types of error patterns have been considered, and codes accordingly are constructed to combat such error patterns. Periodic errors are one type of error patterns that are found in channels like astrophotography [1], gyroscope and computed tomography [2]. Such error occurs due to happening of disturbances periodically. So, there is a need to study such errors and to develop codes dealing with such errors. It was in this spirit that codes detecting/correcting such errors were studied by Das and Tyagi [3, 4]. A periodic error of order s is defined as follows.Definition 1.
A periodic error of orders is a vector whose nonzero components are located at s shifting positions in a code vector where s=1,2,3,…,(n-1) and the number of its starting positions is among the first s+1 components.Fors=1, the periodic errors of order 1 are the vectors where error may occur in 1st, 3rd, 5th, …, positions or 2nd, 4th, 6th, …, positions. For example, in a vector of length 8, periodic errors of order 1 are of the type 10101000, 00101000, 0010101, 10101010, 10001010, 01010101, 01000101, 00000101, 00000001, and so forth.Fors=2, the periodic errors of order 2 may look like 10010010, 10000010, 00010010, 01001001, 01000001, 01000000, 00001001, and so forth in a vector of length 8.Perfect codes are the best codes among the linear codes since the parameters satisfy the Sphere-Packing (or Hamming) bound [5, 6]. It was a big challenge for mathematician to search for such codes for several years in the past. It was finally established that there are no perfect codes other than the single error correcting Hamming [5] codes, double and triple error correcting Golay codes [7], and the Repetitive codes (refer to Tietavainen [8], Tietavainen and Perko [9], and van Lint [10]).By perfect codes we mean the linear codes that are capable of correcting allt or fewer errors and no others.Thereafter several attempts were given to find codes that are not perfect in the usual sense but that correct certain type of error pattern and no more. Such codes are calledoptimal codes. Sharma and Dass [11] were the first who attempted to find such codes. In paper [12], Dass and Tyagi explored a new type of binary (1,2) optimal codes. Similar kind of perfect codes is also studied in [13].Further, mathematicians also started to find codes that are opposite in nature to perfect codes. Those codes are called anti-perfect codes. In this direction, an attempt is given in paper [14] by Sharma et al. These codes correct all t errors and more and no others.In view of these studies, this paper presents(n=n1+n2,k) linear optimal codes over GF(q) that correct all periodic errors of order r in the first block of length n1 and all periodic errors of order s in the second block of length n2 and no others. Then the study has been extended to the case when the errors in the first block of length n1 are in the form of order r or more and the errors in the second block of length n2 are in the form of order s or more and no others. They are called anti-optimal codes.This paper also presents the weight structure of periodic errors in the space ofn-tuples over GF(q). The study of weight structure for different types of error patterns is of considerable interest to many researchers. Various results are obtained in this direction (e.g., [15, 16]).The paper is organized as follows. Section1 is the introduction. In Section 2, we present minimum weight and weight structure of periodic errors in the space of n-tuples. In Section 3, we study optimal codes that correct all periodic errors of order r in the first block of length n1 and all periodic errors of order s in the second block of length n2 and no others. Section 4 presents the study of anti-optimal codes mentioned above.


## 2. Weights of Periodic Errors

In coding theory, an important criterion is to look for minimum weight and structure of weight in a group of vectors. Our following theorems (which are equivalent to Plotkin bound [17], also Theorem  4.1, Peterson and Weldon [6]) are results in that direction. The weight of a vector is considered in Hamming’s sense.Lemma 2.
LetWs denote the total weight of all periodic errors of order s in the space of all n-tuples over GF(q). Then,
(1)Ws=∑w=1k0‍w(k0w)(q-1)w+∑w=1k1‍w(k1w)(q-1)w+⋯+∑w=1ks‍w(ksw)(q-1)w,
where ki=⌈(n-i)/(s+1)⌉ (i=0,1,2,…s).Proof.
We first count the total number of periodic errors of orders with weight w in the space of all n-tuples.
Consider a periodic error of orders. The number of positions in which periodic error of order s can occur is k0,k1,…,ks where ki=⌈(n-i)/(s+1)⌉  (i=0,1,2,…,s) and w≤ks (refer to Tyagi and Das [4]). So, the total number of periodic errors of order s with weight w is given by
(2){(k0w)+(k1w)+⋯+(ksw)}(q-1)w.
Then,
(3)Ws=∑w=1k0‍w(k0w)(q-1)w+∑w=1k1‍w(k1w)(q-1)w+⋯+∑w=1ks‍w(ksw)(q-1)w.Theorem 3.
The minimum weight of a periodic error of orders in the space of n-tuples is at most
(4)(∑w=1k0‍w(k0w)(q-1)w+∑w=1k1‍w(k1w)(q-1)wss+⋯+∑w=1ks‍w(ksw)(q-1)w)×(∑i=0s‍(qki-1))-1,
where ki=⌈(n-i)/(s+1)⌉, i=0,1,2,…s.Proof.
The number of periodic errors of orders in the space of n-tuples over GF(q) is given by
(5)∑i=0s‍(qki-1),whereki=⌈n-is+1⌉(i=0,1,2,…,s).
By using Lemma 2, the total weight of all periodic errors of order s is given by
(6)∑w=1k0‍w(k0w)(q-1)w+∑w=1k1‍w(k1w)(q-1)w+⋯+∑w=1ks‍w(ksw)(q-1)w.
Since the minimum weight element can have at most the average weight, an upper bound on the minimum weight of periodic errors of order s is given by
(7)(∑w=1k0‍w(k0w)(q-1)w+∑w=1k1‍w(k1w)(q-1)wss+⋯+∑w=1ks‍w(ksw)(q-1)w)×(∑i=0s‍(qki-1))-1.During the process of transmission, periodic disturbances cause occurrence of periodic errors. But it is quite possible that all the periodic components in such periodic errors may not be affected; that is, some digits are received correctly while others get corrupted. In view of this, we have the following results for periodic errors with weightw or less (without proof).Lemma 4.
LetWs,w denote the total weight of all periodic errors of order s which are of weight w or less (w≤ks) in the space of all n-tuples. Then,
(8)Ws,w=∑m=1w‍m(k0m)(q-1)m+∑m=1w‍m(k1m)(q-1)m+⋯+∑m=1w‍m(ksm)(q-1)m,
where ki=⌈(n-i)/(s+1)⌉, i=0,1,2,…s.Theorem 5.
The minimum weight of a periodic error of orders which is of weight w or less (w≤ks) in the space of n-tuples is at most
(9)(∑m=1w‍m(k0m)(q-1)m+∑m=1w‍m(k1m)(q-1)mss+⋯+∑m=1w‍m(ksm)(q-1)m)×(∑i=0s‍(qki-1))-1,
where ki=⌈(n-i)/(s+1)⌉, i=0,1,2,…s.


## 3. Optimal Codes

Das [18] has studied the (n=n1+n2,k) linear code over GF(q) that corrects all periodic errors of order r in the first block of length n1 and all periodic errors of order s in the second block of length n2 as follows.Theorem 6.
The number of parity check digits for an(n=n1+n2,k) linear code over GF(q) that corrects all periodic errors of order r in the first block of length n1 and all periodic errors of order s in the second block of length n2 always satisfies
(10)qn-k≥1+∑i=0r‍(qkir-1)+∑j=0s‍(qkjs-1),
where kir=⌈(n1-i)/(r+1)⌉(i=0,1,2,…r) and kjs=⌈(n2-j)/(s+1)⌉ (j=0,1,2,…s).Considering the equality of inequality (10) gives us the optimal case; that is,
(11)qn-k=1+∑i=0r‍(qkir-1)+∑j=0s‍(qkjs-1),
where kir=⌈(n1-i)/(r+1)⌉, kjs=⌈(n2-j)/(s+1)⌉, (i=0,1,2,…r), (j=0,1,2,…s).We now give an example of a linear code overGF(2) that corrects all periodic errors of order 2 in the first block of length 6 and all periodic errors of order 1 in the second block of length 4 and no other errors.Example 7.
By puttingr=2, s=1, n1=6, and n2=4 over GF(2), equality (11) gives rise to (6+4,6) linear code. Consider the following matrix:
(12)H=[1110000001010111010101101011000000110011].
The code obtained from the above matrix H as a parity check matrix is a (6+4,6) linear code. This code can correct all periodic errors of order 2 in the first block of length 6 and all periodic errors of order 1 in the second block of length 4 and no others. We list in Table 1 all the error vectors and their corresponding syndromes which can be seen to be all distinct and exhaustive.Table 1
Error pattern syndromes.
Error patterns
Syndromes
Error patterns
Syndromes
100100 0000
1100
000001 0000
0101
010010 0000
1001
000000 1010
0011
001001 0000
1111
000000 0101
1011
100000 0000
1000
000000 1000
0010
010000 0000
1110
000000 0100
0110
001000 0000
1010
000000 0010
0001
000100 0000
0100
000000 0001
1101
000010 0000
0111


## 4. Anti-Optimal Codes

In this section, we will obtain bound on(n=n1+n2,k) linear code over GF(q) that corrects all periodic errors of order r or more in the first block of length n1 (r≥(n1-3)/2) and all periodic errors of order s or more in the second block of length n2 (s≥(n2-3)/2) and no other errors. Taking the bound tight, we obtainanti-optimal codes. The codes are anti-optimal codes in the sense that they correct all periodic errors of order r or more in the first block of length n1 and all periodic errors of order s or more in the second block of length n2 and no others. First we prove the following lemma.Lemma 8.
IfB(n,s) (where  n≤2s+3) denotes the number of periodic errors of order s or more over the space of all n-tuples over GF(q), then
(13)B(n,s)={∑i=sn-1‍E(i)-(n-s-1)n(q-1),forn≤2s+1,∑i=s2s‍E(i)-sn(q-1),forn=2s+3orn=2s+2,
where E(i)=∑j=0i‍(qkji-1) and kji=⌈(n-j)/(i+1)⌉.Proof.
Forn≤2s+1, there will be no common errors among the periodic errors of order s or more except the single errors. Let E(s) be the number of periodic errors of order s. Then,
(14)E(s)=∑j=0s‍(qkjs-1),wherekjs=⌈n-js+1⌉
(refer to Tyagi and Das [4]).
Therefore(15)B(n,s)=E(s)+E(s+1)+⋯+E(n-2)+E(n-1)-(n-s-1)n(q-1)=∑i=sn-1‍E(i)-(n-s-1)n(q-1),
where
(16)E(i)=∑j=0i‍(qkji-1),kji=⌈n-ji+1⌉.
Letn=2s+2. Since any periodic error of order 2s+1 is a periodic error of order s, therefore we have
(17)B(n,s)=E(s)+E(s+1)+⋯+E(2s)-sn(q-1)=∑i=s2s‍E(i)-sn(q-1).
Let n=2s+3. Since E(n-1) represents the single errors and all single errors present in periodic errors of any order, so by counting the number of periodic errors of order s or more, we take the value of s up to n-2. Also, any periodic error of order 2s+1 is a periodic error of order s. Hence
(18)B(n,s)=E(s)+E(s+1)+⋯+E(2s)-sn(q-1)=∑i=s2s‍E(i)-sn(q-1).Theorem 9.
The number of parity check digits for an(n=n1+n2,k) linear code over GF(q) that corrects all periodic errors of order r or more in the first block of length n1 (r≥(n1-3)/2) and all periodic errors of order s or more in the second block of length n2 (s≥(n2-3)/2) and no other error patterns is at least
(19)log⁡q⁡[1+B(n1,r)+B(n2,s)],
where B(n1,r) and B(n2,s) are given in Lemma 8.Proof.
This proof is based on counting the number of errors above specific type and comparing with the available cosets in the(n=n1+n2,k) linear code over GF(q).
By Lemma8, we have the following.(a)
The number of periodic errors of orderr or more in the first block of length n1 is B(n1,r).(b)
The number of periodic errors of orders or more in the second block of length n2 is B(n2,s).
Therefore, the total number of errors including the zero vector is(20)1+B(n1,r)+B(n2,s).
Thus
(21)qn-k≥1+B(n1,r)+B(n2,s).
Hence the proof of Theorem 9 is complete.Now the equality of inequality (21) gives us the optimal case. By considering the equality in (21), we get
(22)qn-k=1+B(n1,r)+B(n2,s).
For r=n1-1 and q=2, (22) becomes
(23)2n-k=1+n1+B(n2,s).Example 10.
Forn1=3, n2=6, and s=2, (23) gives rise to binary (3+6,5) linear code. The code whose parity check matrix is given below is a periodic error correcting anti-optimal code that corrects all periodic errors of order 2 or more in the first block of length 3 and all periodic errors of order 2 or more in the second block of length 6 and no others. Consider
(24)H=[111101000101000101111011000010000011].
It can be verified from the error pattern syndromes shown in Table 2.Table 2
Error pattern syndromes.
Error patterns
Syndromes
Error patterns
Syndromes
100 000000
1110
000 001001
1111
010 000000
1011
000 100010
1001
001 000000
1110
000 010001
0111
000 100000
1000
000 100001
1101
000 100100
1100
000 000100
0100
000 010000
0010
000 000010
0001
000 010010
0011
000 000001
0101
000 001000
1010Example 11.
Forn1=6, n2=9, and s=3, (23) gives rise to binary (6+9,10) linear code. The code whose parity check matrix is given below is a periodic error correcting anti-optimal codes in two blocks that correct all single errors in the first block of length 6 and all periodic errors of order 3 or more in the second block of length 9 and no more. It can also be verified by the error pattern syndrome table. Consider
(25)H=[011000101100000000110001110110010100000101011111110010100110101001001001110].



---

*Source: 971410-2014-08-31.xml*