## Varšamov–Edel Lengthening

In [1, Theorem 1.23] an improvement on the Varšamov bound is given.

Let * H* be the generator matrix of a linear orthogonal array OA(

*b*

^{m},

*s*,

**F**

_{b},

*k*). Let

*ρ*

_{κ}(

*) denote the number of vectors in*

**H****F**

_{b}

^{m}that can be obtained by a linear combination of

*κ*or less columns of

*. If*

**H***ρ*

_{k−1}(

*) <*

**H***b*

^{m}, a vector

*∈*

**x****F**

_{b}

^{m}can be found that is linearly independent of any

*k*−1 columns in

*. Thus (*

**H***|*

**H***) is the generator matrix of a linear OA(*

**x***b*

^{m},

*s*+ 1,

**F**

_{b},

*k*).

Now the original Varšamov bound follows from

*ρ*

_{k−1}(

*) ≤*

**H***V*

_{b}

^{s}(

*k*−1),

where *V*_{b}^{s}(*r*) denotes the volume of a ball with radius *r* in the Hamming space **F**_{b}^{s}.

Better OAs can be obtained by constructing a sequence of OAs (A_{i})_{i ≥ 0} with parameters OA(*b*^{mi}, *s*_{i},**F**_{b}, *k*) and generator matrices **H**_{i} as follows: One starts with an existing OA A_{0} and estimates

*ρ*

_{κ}(

**H**_{0}) ≤

*N*

_{0}(

*κ*) := min

*b*

^{m},

*V*

_{b}

^{s}(

*κ*)

for *κ* = 0,…, *k*−1. Note that *ρ*_{0}(**H**_{i}) = *N*_{i}(0) = 1 for all *i*. Then one constructs A_{i+1} from A_{i} using one of the following two methods:

If

*N*_{i}(*k*– 1) <*b*^{mi}, a vector∈**x****F**_{b}^{mi}exists such that**H**_{i+1}:= (**H**_{i}|) is the generator matrix of an OA(**x***b*^{mi},*s*_{i}+1,**F**_{b},*k*) which we use as A_{i+1}. Furthermore we have*ρ*_{κ}(**H**_{i+1}) ≤*N*_{i+1}(*κ*) := min{*b*^{mi+1},*N*_{i}(*κ*) + (*b*– 1)*N*_{i}(*κ*– 1)}for 1,…,

*k*−1.

If

*N*_{i}(*k*– 1) =*b*^{mi}, we construct an OA A_{i}ʹ with generator matrix**H**_{i}ʹ := ,where

*r*≥ 1 is chosen as small as possible such that*ρ*_{k−1}(**H**_{i}ʹ) ≤*N*_{i}ʹ(*k*– 1) := (*b*– 1)^{j}*N*_{i}(*k*– 1 –*j*) <*b*^{mi+r},which can be shown to be equivalent to determining the smallest

*r*such that*N*_{i}(*k*– 1 –*r*) <*b*^{mi}. Now a vector∈**x****F**_{b}^{mi+r}can be found such that**H**_{i+1}:= (**H**_{i}ʹ|) is the generator matrix of an OA(**x***b*^{mi+r},*s*_{i}+*r*+ 1,**F**_{b},*k*) used for A_{i+1}. The*N*_{i+1}can be calculated based on*N*_{i}using the formula*ρ*_{κ}(**H**_{i+1}) ≤*N*_{i+1}(*κ*) := min*b*^{mi+1}, (*b*– 1)^{j}*N*_{i}(*κ*−*j*).

### See Also

Since the new code contains the original code as a subcode, construction X can be applied to this pair.

### References

[1] | Yves Edel.Eine Verallgemeinerung von BCH-Codes.PhD thesis, Ruprecht-Karls-Universität, Heidelberg, 1996. |

### Copyright

Copyright © 2004, 2005, 2006, 2007, 2008, 2009, 2010 by Rudolf Schürer and Wolfgang Ch. Schmid.

Cite this as: Rudolf Schürer and Wolfgang Ch. Schmid. “Varšamov–Edel Lengthening.”
From MinT—the database of optimal net, code, OA, and OOA parameters.
Version: 2008-04-04.
http://mint.sbg.ac.at/desc_CVarshamovEdel.html