# On Maximum Lee Distance Codes

Authors: Tim L. Alderson; Svenja Huntemann
Journal: Journal of Discrete Mathematics
 (2013)

---

## Abstract

Singleton-type upper bounds on the minimum Lee distance of general (not necessarily linear) Lee codes overℤq are discussed. Two bounds known for linear codes are shown to also hold in the general case, and several new bounds are established. Codes meeting these bounds are
investigated and in some cases characterised.


---

## Body

## 1. Introduction

The Lee metric was introduced by Lee [1] in 1958 as an alternative to the Hamming metric for certain noisy channels. It found application and in particular was later developed for certain noisy channels (primarily those using phase-shift keying modulation [2]). The past decade has witnessed a burst of new and varied applications for codes defined in the Lee metric (Lee codes) including constrained and partial-response channels [3], interleaving schemes [4], orthogonal frequency-division multiplexing [5], multidimensional burst-error correction [6], and error correction for flash memories [7]. These recent applications give increased interest in questions surrounding optimal Lee codes.Similar to the case of the Hamming metric, it is desirable to investigate upper bounds on the minimum Lee distance of a code given the code size, code length, and alphabet size. Codes meeting these bounds are of special interest as they are optimal in the sense that their minimum distance is largest. Under the Hamming metric, such codes are referred to as maximum distance separable (MDS) codes. Under the Lee metric, such codes may be referred to asMaximum Lee Distance Separable (MLDS) codes. Here, we will present several upper bounds similar to the Singleton bound and investigate the existence question of MLDS codes. In certain cases, we are able to completely characterize MLDS codes.


## 2. Preliminaries

An(n,k,d)q block code C is a collection of qkn-tuples (codewords) over an alphabet of size q such that the minimum (Hamming) distance between any two codewords is d (hence, no two codewords have as many as n-d+1 common coordinates). Here, k=logq|C| is the dimension of C, which need not be an integer. Where context demands, we may also denote the Hamming distance by dH. The Singleton bound states that
(1)d≤n-⌈k⌉+1
and holds for all block codes. Codes meeting this bound with equality are called maximum distance separable (MDS) codes. Research on both linear and nonlinear MDS codes has been extensive (e.g., see [8–10] and references therein).


### 2.1. Lee Codes

Letℤq={0,1,…,q-1} be the set of representatives of the integer equivalence classes modulo q. The Lee weight of any element a∈ℤq is given by wL(a)=min{a,q-a}. Given an element c=(c1,c2,…,cn)∈ℤqn, the Lee weight of c, denoted wL(c), is given by
(2)wL(c)=∑i=1n‍min{a,q-a}.
For c,e∈ℤqn, the Lee distancedL(c,e) between c and e is defined to be the Lee weight of their difference,
(3)dL(c,e)=wL(c-e)=∑i=1n‍min{ci-ei(modq),ei-ci(modq)}.A Lee codeC will be specified by (n,k,dL)q, where n, k, and q are as aforementioned, and dL is the minimum Lee distance of C; that is, dL=min{dL(c,e)∣c,e∈C,c≠e}.Observe that in the case thatq=2 or 3 (binary or ternary codes), the Hamming and Lee metrics are identical. Thus a code C with q=2 or q=3 is MLDS if and only if C is MDS. As much literature discusses MDS codes, we shall focus attention on the cases q>3.A codeC over the alphabet  ℤq is considered linear if C forms a submodule of ℤqn. Unless otherwise stated, we do not assume linearity.


### 2.2. Code Equivalence

We shall say a permutationσ of ℤq is a Lee permutation if it preserves Lee distance. That is, dL(a,b)=dL(σ(a),σ(b)), for all a,b∈ℤq. For example, any translation σ(x)=x+t(modq) is a Lee permutation.Given an(n,k,dL)q Lee code C, we may define the following operations on codewords. A positional permutation is a permutation (on n letters) of the coordinate positions, applied to each word of C. A Lee symbol permutation is a Lee permutation applied to a fixed coordinate position throughout C. Two codes are equivalent if one may be obtained from the other by applying a sequence of Lee symbol or positional permutations.Example 1.
The code(4)C=(0,0)(1,2)(2,4)(3,1)(4,3)
is a (2,1,3)5 Lee code. The equivalent codes may be produced by applying the Lee permutation (0)(14)(23) to one or more of the coordinate entries of C. For example, the code
(5)C′=(0,0)(1,3)(2,1)(3,4)(4,2)
is equivalent to C.It follows  that  any given Lee Code is equivalent to a Lee Code containing the  zero codeword. This observation shall prove quite useful in the sequel.


## 2.1. Lee Codes

Letℤq={0,1,…,q-1} be the set of representatives of the integer equivalence classes modulo q. The Lee weight of any element a∈ℤq is given by wL(a)=min{a,q-a}. Given an element c=(c1,c2,…,cn)∈ℤqn, the Lee weight of c, denoted wL(c), is given by
(2)wL(c)=∑i=1n‍min{a,q-a}.
For c,e∈ℤqn, the Lee distancedL(c,e) between c and e is defined to be the Lee weight of their difference,
(3)dL(c,e)=wL(c-e)=∑i=1n‍min{ci-ei(modq),ei-ci(modq)}.A Lee codeC will be specified by (n,k,dL)q, where n, k, and q are as aforementioned, and dL is the minimum Lee distance of C; that is, dL=min{dL(c,e)∣c,e∈C,c≠e}.Observe that in the case thatq=2 or 3 (binary or ternary codes), the Hamming and Lee metrics are identical. Thus a code C with q=2 or q=3 is MLDS if and only if C is MDS. As much literature discusses MDS codes, we shall focus attention on the cases q>3.A codeC over the alphabet  ℤq is considered linear if C forms a submodule of ℤqn. Unless otherwise stated, we do not assume linearity.


## 2.2. Code Equivalence

We shall say a permutationσ of ℤq is a Lee permutation if it preserves Lee distance. That is, dL(a,b)=dL(σ(a),σ(b)), for all a,b∈ℤq. For example, any translation σ(x)=x+t(modq) is a Lee permutation.Given an(n,k,dL)q Lee code C, we may define the following operations on codewords. A positional permutation is a permutation (on n letters) of the coordinate positions, applied to each word of C. A Lee symbol permutation is a Lee permutation applied to a fixed coordinate position throughout C. Two codes are equivalent if one may be obtained from the other by applying a sequence of Lee symbol or positional permutations.Example 1.
The code(4)C=(0,0)(1,2)(2,4)(3,1)(4,3)
is a (2,1,3)5 Lee code. The equivalent codes may be produced by applying the Lee permutation (0)(14)(23) to one or more of the coordinate entries of C. For example, the code
(5)C′=(0,0)(1,3)(2,1)(3,4)(4,2)
is equivalent to C.It follows  that  any given Lee Code is equivalent to a Lee Code containing the  zero codeword. This observation shall prove quite useful in the sequel.


## 3. Singleton-Type Bounds

In 2000 Shiromoto, [11] proved the following upper bound for linear codes over ℤq.Proposition 2 (see [11]).
IfC is a linear (n,k,dL)q Lee code over ℤq, then
(6)⌊dL-1⌊q/2⌋⌋≤n-k.We shall show that bound (6) holds for general (not necessarily linear) Lee codes. Indeed, observe that for a given code, any two codewords differ in at most dH coordinate positions, from which it follows that dL≤⌊q/2⌋dH. Combining this observation with the Singleton bound (1) gives the following.Proposition 3.
For any(n,k,dL)q Lee code C, the following holds:
(7)dL≤⌊q2⌋(n-⌈k⌉+1).Remark 4.
Observe that(8)dL≤⌊q2⌋(n-⌈k⌉+1)⇒⌊dL-1⌊q/2⌋⌋≤⌊n-⌈k⌉+⌊q/2⌋-1⌊q/2⌋⌋=n-⌈k⌉.
Consequently, Proposition 3 subsumes the bound of Shiromoto (6).Remark 5.
Suppose thatC is an (n,k,dL)q Lee code with ⌈k⌉=1 meeting bound (7), so that dL=⌊q/2⌋n. Assume that C contains the zero codeword. It follows that C contains precisely two codewords. Moreover, the nonzero codeword has (Lee) weight dL. Hence, if q is even, then the nonzero codeword has all entries q/2. If q is odd, then the nonzero codeword has each entry being either (q+1)/2 or (q-1)/2.We shall make improvements to  bound (7) under various settings. Observe that codes for which n<k necessarily contain repeated codewords; whence, dL=0. Also, codes with n=k necessarily comprise the entire space ℤqn, and consequently dL=1. Hence, in the sequel, we shall focus on codes with n>k.


### 3.1. Bounds on Codes over Even-Sized Alphabets

By restricting to codes over even-sized alphabets, we obtain the following bound.Theorem 6.
For any Lee metric code with alphabet sizeq even, of length n and minimum Lee distance dL, the following holds:
(9)dL≤q2n-⌈log2|C|⌉+1.Proof.
Ifq is even, we can create a distance preserving map (Gray code) ϕ (similar to that used in [12, 13]) from the metric space (ℤq,dL) to the metric space (ℤ2q/2,dH) defined by
(10)ϕ(a)={000︷q/2-a⋯111︷aif0≤a≤q2-1,111︷q-a⋯000︷a-q/2ifq2≤a≤q-1.
For c∈C, we extend the map coordinatewise; thus, ϕ(c)=(ϕ(c1)⋯ϕ(cn)), and let C′=ϕ(C)={ϕ(c)∣c∈C}. It follows that C′ is a binary code of length n(q/2) with |C|=|C′|, and dL(C)=dH(C′). The result follows from the Singleton bound (1).


#### 3.1.1. Special Cases: Characterizing and Improving

If restrictions are made on the size ofC, we are able to characterize cases of equality in bound (9). The following well known property of binary MDS codes shall be of use. See, for example, [14].Lemma 7.
IfC is a binary (n,k,d)2 MDS code of integral dimension k≥1, then either (1)
k=1, and C is the repetition code {(0,0,…,0),(1,1,…,1)},(2)
k≥2, n=k+1, and C is the binary parity check code consisting of all binary n-tuples of even (Hamming) weight, or(3)
k≥2, n=k, and C is the entire space ℤ2n.Lemma 8.
LetC be an (n,k,dL)q Lee code with n>k≥1, q>2 even, and log2|C|∈ℤ. If dL=(q/2)n-log2|C|+1, then either (1)
k=1, and C is the repetition code {(00⋯0)((q/2)(q/2)⋯q/2)}, or(2)
k=n-(1/2), and q=4.Proof.
Assume thatdL=(q/2)n-log2|C|+1. Let ϕ be as defined in the proof of Theorem 6. Then, C′=ϕ(C) is a binary (n′,k′,d′) MDS code, n′=(q/2)n, and k′=log2|C|. Note that since n≥2 and q≥4, we have n′≥4. According to Lemma 7, we have three cases to consider.
Case 1 (k′=1). In this case, C′ is the binary repetition code; hence, C is the code
(11)(00⋯0)(q2q2⋯q2).
Case  2  (k′>1,n′=k′+1). In this case, C′ is the binary parity check code of length n′. As such, the vector (101000⋯0) is in C′. From the definition of ϕ, it follows that q/2≤2; so, q=4.
Note that sinceq=4, we have n′=2n=k′+1=2k+1.
Case  3 (k′>1,n′=k′). In this case, C′=ℤ2k′. Again, the vector (101000⋯0) is in C′, giving q=4. But then, n′=2n=k′=2k, contradicting n>k.Remark 9.
An example of a code satisfying item(2) in Lemma 8 is the (2,3/2,2)4 Lee code:
(12)C={(00),(02),(20),(22),(13),(31),(11),(33)}.With Lemma8, we see that the bound in Theorem 6 may be improved in certain cases.Theorem 10.
LetC be an (n,k,dL)q Lee code with q>4 even, n>k≥1, and log2|C|∈ℤ. Then,
(13)dL≤q2n-log2|C|.


### 3.2. Bounds on General Alphabets

In this section, we shall make improvements to the bound in Proposition3. First, some intermediary lemmata are introduced.Lemma 11.
IfC is an (n,k,dL)q Lee code with dL≥⌊q/2⌋(n-⌊k⌋)+1, then the following hold:(1)
k is an integer;(2)
Fixk coordinate positions i1<i2<⋯<ik, and k (not necessarily distinct) elements α1,…,αk∈ℤq. Then, there exists precisely one codeword c having cij=αj, j=1,2,…,k.Proof.
For the first part, observe that if two codewords agree in⌊k⌋ coordinates, then their distance is at most ⌊q/2⌋(n-⌊k⌋), violating the minimum Lee distance condition. Consequently, |C|≤q⌊k⌋, giving k=⌊k⌋.
For the second part, fixk coordinate positions {i1,…,ik}. The result then follows by observing that no two codewords agree in all of these positions, and there are qk codewords in total.Lemma 12.
IfC is a (k+1,k,3)5 Lee code, k∈ℤ, then k=1.Proof.
First, note that from Example1, a (2,1,3)5 Lee code does in fact exist.
Now, letk≥2, and assume without loss of generality that the zero codeword is in C. Consider (Lemma 11) the three codewords w1, w2, and w3, having first k coordinates 100⋯0, 0100⋯0, and 400⋯0, respectively. In order to maintain minimum Lee distance 3 from the zero codeword, the (k+1)-st coordinate of each wi must be from {2,3}. Thus, at least two of {w1,w2,w3} agree in the final coordinate, violating the minimum distance property.Lemma 13.
IfC is an (n,k,dL)q code with q>3, and integral dimension k>1, then dL≤⌊q/2⌋(n-k).Proof.
Suppose thatC is an (n,k,dL)q code, q>3, 1<k∈ℤ, with dL≥⌊q/2⌋(n-k)+1. From Lemma 11, there exist codewords a, b, and c having first k-1 coordinates 0 and kth coordinate 0, 1, and q-1, respectively. Consequently, we have dL=⌊q/2⌋(n-k)+1.
Ifq is even, then dL(a,b)=(q/2)(n-k)+1 gives bi=ai+(q/2)(modq), for i=k+1,k+2,…,n. Similarly, ci=ai+(q/2)(modq), for i=k+1,k+2,…,n. But then, dL(b,c)=2, contradicting the condition dL=(q/2)(n-k)+1.
Ifq is odd, then a similar argument shows that for each of the final (n-k) coordinate, dL(bi,ci)≤1. Consequently, dL(b,c)≤n-k+2. Therefore, we have n-k+2≥⌊q/2⌋(n-k)+1 from which it follows that q=5, n=k+1, and d=3. From Lemma 12, it then follows that k=1, a contradiction.From Lemmas11 and 13, we have the following result.Theorem 14.
IfC is an (n,k,dL)q Lee code q>3, n>k>1 then
(14)dL≤⌊q2⌋(n-⌊k⌋).


### 3.3. Bound Based on Plotkin’s Average Distance Bound

Based on the fact that the minimum distance between pairs of codewords cannot exceed the average distance between all pairs of distinct codewords, Wyner and Graham [15] obtained the following bound.Proposition 15.
IfC is an (n,k,dL)q Lee code, then
(15)dL≤nD-1-(1/|C|),
where D- is the average Lee weight of ℤq, given by
(16)D-={q2-14qifqisodd,q4ifqiseven.Using the previous result, we may establish a further Singleton-type bound for Lee codes.Theorem 16.
LetC be an (n,k,dL)q code. Let α be the maximal number of codewords mutually agreeing in ⌈k⌉-1 common coordinates. Then,
(17)dL≤⌊(n-⌈k⌉+1)·a⌋,
where
(18)a={q2-14q·αα-1ifqodd,q4·αα-1ifqeven.Proof.
LetC be an (n,k,dL)q code, and let α be as defined earlier. Consider a collection C1 of α codewords mutually agreeing in ⌈k⌉-1 coordinates, assumed to be the first ⌈k⌉-1 coordinates. Let C′ be the corresponding punctured code obtained by deleting the first ⌈k⌉-1 coordinates of each word in C1.
It follows thatC′ is an (n-⌈k⌉+1,1,d′L)q code with d′L≥dL. Applying Proposition 15 to C′, we obtain
(19)dL≤d′L≤(n-⌈k⌉+1)D-1-(1/α).
Finally, applying (16), we get the result.Suppose thatC is an (n,k,dL)q Lee code, and α is as defined ealier. Observe that since |C|>q⌈k⌉-1, it follows that α≥2. So, if q is even, the bound in Theorem 16 always meets or exceeds bound (7). Moreover, if k∈ℤ, simple counting shows that α≥q. This gives the following corollary, much improving bound (7).Corollary 17.
IfC is an (n,k,dL)q Lee code with k∈ℤ, then
(20)dL≤(n-k+1)·a,
where
(21)a={q24(q-1)ifqeven,q+14ifqodd.Remark 18.
Chiang and Wolf [16] established the bound in Corollary 17 for linear codes.Codes meeting the bounds in Theorem16 do exist [16]. Two examples follow: (1)
forp as prime, the linear one-dimensional (equidistant) (p-1,1,((p-1)/2)·3)p code generated by (1,2,…,p-1);(2)
the linear(4,2,4)5 Lee code with generator matrix
(22)G=[34100341].


## 3.1. Bounds on Codes over Even-Sized Alphabets

By restricting to codes over even-sized alphabets, we obtain the following bound.Theorem 6.
For any Lee metric code with alphabet sizeq even, of length n and minimum Lee distance dL, the following holds:
(9)dL≤q2n-⌈log2|C|⌉+1.Proof.
Ifq is even, we can create a distance preserving map (Gray code) ϕ (similar to that used in [12, 13]) from the metric space (ℤq,dL) to the metric space (ℤ2q/2,dH) defined by
(10)ϕ(a)={000︷q/2-a⋯111︷aif0≤a≤q2-1,111︷q-a⋯000︷a-q/2ifq2≤a≤q-1.
For c∈C, we extend the map coordinatewise; thus, ϕ(c)=(ϕ(c1)⋯ϕ(cn)), and let C′=ϕ(C)={ϕ(c)∣c∈C}. It follows that C′ is a binary code of length n(q/2) with |C|=|C′|, and dL(C)=dH(C′). The result follows from the Singleton bound (1).


### 3.1.1. Special Cases: Characterizing and Improving

If restrictions are made on the size ofC, we are able to characterize cases of equality in bound (9). The following well known property of binary MDS codes shall be of use. See, for example, [14].Lemma 7.
IfC is a binary (n,k,d)2 MDS code of integral dimension k≥1, then either (1)
k=1, and C is the repetition code {(0,0,…,0),(1,1,…,1)},(2)
k≥2, n=k+1, and C is the binary parity check code consisting of all binary n-tuples of even (Hamming) weight, or(3)
k≥2, n=k, and C is the entire space ℤ2n.Lemma 8.
LetC be an (n,k,dL)q Lee code with n>k≥1, q>2 even, and log2|C|∈ℤ. If dL=(q/2)n-log2|C|+1, then either (1)
k=1, and C is the repetition code {(00⋯0)((q/2)(q/2)⋯q/2)}, or(2)
k=n-(1/2), and q=4.Proof.
Assume thatdL=(q/2)n-log2|C|+1. Let ϕ be as defined in the proof of Theorem 6. Then, C′=ϕ(C) is a binary (n′,k′,d′) MDS code, n′=(q/2)n, and k′=log2|C|. Note that since n≥2 and q≥4, we have n′≥4. According to Lemma 7, we have three cases to consider.
Case 1 (k′=1). In this case, C′ is the binary repetition code; hence, C is the code
(11)(00⋯0)(q2q2⋯q2).
Case  2  (k′>1,n′=k′+1). In this case, C′ is the binary parity check code of length n′. As such, the vector (101000⋯0) is in C′. From the definition of ϕ, it follows that q/2≤2; so, q=4.
Note that sinceq=4, we have n′=2n=k′+1=2k+1.
Case  3 (k′>1,n′=k′). In this case, C′=ℤ2k′. Again, the vector (101000⋯0) is in C′, giving q=4. But then, n′=2n=k′=2k, contradicting n>k.Remark 9.
An example of a code satisfying item(2) in Lemma 8 is the (2,3/2,2)4 Lee code:
(12)C={(00),(02),(20),(22),(13),(31),(11),(33)}.With Lemma8, we see that the bound in Theorem 6 may be improved in certain cases.Theorem 10.
LetC be an (n,k,dL)q Lee code with q>4 even, n>k≥1, and log2|C|∈ℤ. Then,
(13)dL≤q2n-log2|C|.


## 3.1.1. Special Cases: Characterizing and Improving

If restrictions are made on the size ofC, we are able to characterize cases of equality in bound (9). The following well known property of binary MDS codes shall be of use. See, for example, [14].Lemma 7.
IfC is a binary (n,k,d)2 MDS code of integral dimension k≥1, then either (1)
k=1, and C is the repetition code {(0,0,…,0),(1,1,…,1)},(2)
k≥2, n=k+1, and C is the binary parity check code consisting of all binary n-tuples of even (Hamming) weight, or(3)
k≥2, n=k, and C is the entire space ℤ2n.Lemma 8.
LetC be an (n,k,dL)q Lee code with n>k≥1, q>2 even, and log2|C|∈ℤ. If dL=(q/2)n-log2|C|+1, then either (1)
k=1, and C is the repetition code {(00⋯0)((q/2)(q/2)⋯q/2)}, or(2)
k=n-(1/2), and q=4.Proof.
Assume thatdL=(q/2)n-log2|C|+1. Let ϕ be as defined in the proof of Theorem 6. Then, C′=ϕ(C) is a binary (n′,k′,d′) MDS code, n′=(q/2)n, and k′=log2|C|. Note that since n≥2 and q≥4, we have n′≥4. According to Lemma 7, we have three cases to consider.
Case 1 (k′=1). In this case, C′ is the binary repetition code; hence, C is the code
(11)(00⋯0)(q2q2⋯q2).
Case  2  (k′>1,n′=k′+1). In this case, C′ is the binary parity check code of length n′. As such, the vector (101000⋯0) is in C′. From the definition of ϕ, it follows that q/2≤2; so, q=4.
Note that sinceq=4, we have n′=2n=k′+1=2k+1.
Case  3 (k′>1,n′=k′). In this case, C′=ℤ2k′. Again, the vector (101000⋯0) is in C′, giving q=4. But then, n′=2n=k′=2k, contradicting n>k.Remark 9.
An example of a code satisfying item(2) in Lemma 8 is the (2,3/2,2)4 Lee code:
(12)C={(00),(02),(20),(22),(13),(31),(11),(33)}.With Lemma8, we see that the bound in Theorem 6 may be improved in certain cases.Theorem 10.
LetC be an (n,k,dL)q Lee code with q>4 even, n>k≥1, and log2|C|∈ℤ. Then,
(13)dL≤q2n-log2|C|.


## 3.2. Bounds on General Alphabets

In this section, we shall make improvements to the bound in Proposition3. First, some intermediary lemmata are introduced.Lemma 11.
IfC is an (n,k,dL)q Lee code with dL≥⌊q/2⌋(n-⌊k⌋)+1, then the following hold:(1)
k is an integer;(2)
Fixk coordinate positions i1<i2<⋯<ik, and k (not necessarily distinct) elements α1,…,αk∈ℤq. Then, there exists precisely one codeword c having cij=αj, j=1,2,…,k.Proof.
For the first part, observe that if two codewords agree in⌊k⌋ coordinates, then their distance is at most ⌊q/2⌋(n-⌊k⌋), violating the minimum Lee distance condition. Consequently, |C|≤q⌊k⌋, giving k=⌊k⌋.
For the second part, fixk coordinate positions {i1,…,ik}. The result then follows by observing that no two codewords agree in all of these positions, and there are qk codewords in total.Lemma 12.
IfC is a (k+1,k,3)5 Lee code, k∈ℤ, then k=1.Proof.
First, note that from Example1, a (2,1,3)5 Lee code does in fact exist.
Now, letk≥2, and assume without loss of generality that the zero codeword is in C. Consider (Lemma 11) the three codewords w1, w2, and w3, having first k coordinates 100⋯0, 0100⋯0, and 400⋯0, respectively. In order to maintain minimum Lee distance 3 from the zero codeword, the (k+1)-st coordinate of each wi must be from {2,3}. Thus, at least two of {w1,w2,w3} agree in the final coordinate, violating the minimum distance property.Lemma 13.
IfC is an (n,k,dL)q code with q>3, and integral dimension k>1, then dL≤⌊q/2⌋(n-k).Proof.
Suppose thatC is an (n,k,dL)q code, q>3, 1<k∈ℤ, with dL≥⌊q/2⌋(n-k)+1. From Lemma 11, there exist codewords a, b, and c having first k-1 coordinates 0 and kth coordinate 0, 1, and q-1, respectively. Consequently, we have dL=⌊q/2⌋(n-k)+1.
Ifq is even, then dL(a,b)=(q/2)(n-k)+1 gives bi=ai+(q/2)(modq), for i=k+1,k+2,…,n. Similarly, ci=ai+(q/2)(modq), for i=k+1,k+2,…,n. But then, dL(b,c)=2, contradicting the condition dL=(q/2)(n-k)+1.
Ifq is odd, then a similar argument shows that for each of the final (n-k) coordinate, dL(bi,ci)≤1. Consequently, dL(b,c)≤n-k+2. Therefore, we have n-k+2≥⌊q/2⌋(n-k)+1 from which it follows that q=5, n=k+1, and d=3. From Lemma 12, it then follows that k=1, a contradiction.From Lemmas11 and 13, we have the following result.Theorem 14.
IfC is an (n,k,dL)q Lee code q>3, n>k>1 then
(14)dL≤⌊q2⌋(n-⌊k⌋).


## 3.3. Bound Based on Plotkin’s Average Distance Bound

Based on the fact that the minimum distance between pairs of codewords cannot exceed the average distance between all pairs of distinct codewords, Wyner and Graham [15] obtained the following bound.Proposition 15.
IfC is an (n,k,dL)q Lee code, then
(15)dL≤nD-1-(1/|C|),
where D- is the average Lee weight of ℤq, given by
(16)D-={q2-14qifqisodd,q4ifqiseven.Using the previous result, we may establish a further Singleton-type bound for Lee codes.Theorem 16.
LetC be an (n,k,dL)q code. Let α be the maximal number of codewords mutually agreeing in ⌈k⌉-1 common coordinates. Then,
(17)dL≤⌊(n-⌈k⌉+1)·a⌋,
where
(18)a={q2-14q·αα-1ifqodd,q4·αα-1ifqeven.Proof.
LetC be an (n,k,dL)q code, and let α be as defined earlier. Consider a collection C1 of α codewords mutually agreeing in ⌈k⌉-1 coordinates, assumed to be the first ⌈k⌉-1 coordinates. Let C′ be the corresponding punctured code obtained by deleting the first ⌈k⌉-1 coordinates of each word in C1.
It follows thatC′ is an (n-⌈k⌉+1,1,d′L)q code with d′L≥dL. Applying Proposition 15 to C′, we obtain
(19)dL≤d′L≤(n-⌈k⌉+1)D-1-(1/α).
Finally, applying (16), we get the result.Suppose thatC is an (n,k,dL)q Lee code, and α is as defined ealier. Observe that since |C|>q⌈k⌉-1, it follows that α≥2. So, if q is even, the bound in Theorem 16 always meets or exceeds bound (7). Moreover, if k∈ℤ, simple counting shows that α≥q. This gives the following corollary, much improving bound (7).Corollary 17.
IfC is an (n,k,dL)q Lee code with k∈ℤ, then
(20)dL≤(n-k+1)·a,
where
(21)a={q24(q-1)ifqeven,q+14ifqodd.Remark 18.
Chiang and Wolf [16] established the bound in Corollary 17 for linear codes.Codes meeting the bounds in Theorem16 do exist [16]. Two examples follow: (1)
forp as prime, the linear one-dimensional (equidistant) (p-1,1,((p-1)/2)·3)p code generated by (1,2,…,p-1);(2)
the linear(4,2,4)5 Lee code with generator matrix
(22)G=[34100341].


## 4. Conclusion

Several upper bounds on the minimum Lee distance of a block code similar to the Singleton bound were established. Codes actually meeting some of these bounds were presented. Two bounds known for linear codes were shown (see Proposition2 and Corollary 17) to hold for nonlinear codes.  Several new bounds were also established.



---

*Source: 625912-2013-02-07.xml*