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(bm, s,Fb, k). Let ρκ(H) denote the number of vectors in Fbm that can be obtained by a linear combination of κ or less columns of H. If ρk−1(H) < bm, a vector xFbm can be found that is linearly independent of any k−1 columns in H. Thus (H|x) is the generator matrix of a linear OA(bm, s + 1,Fb, k).

Now the original Varšamov bound follows from

ρk−1(H) ≤ Vbs(k−1),

where Vbs(r) denotes the volume of a ball with radius r in the Hamming space Fbs.

Better OAs can be obtained by constructing a sequence of OAs (Ai)i ≥ 0 with parameters OA(bmi, si,Fb, k) and generator matrices Hi as follows: One starts with an existing OA A0 and estimates

ρκ(H0) ≤ N0(κ) := min$\displaystyle \left\{\vphantom{ b^{m},\, V_{b}^{s}(\kappa)}\right.$bmVbs(κ)$\displaystyle \left.\vphantom{ b^{m},\, V_{b}^{s}(\kappa)}\right\}$

for κ = 0,…, k−1. Note that ρ0(Hi) = Ni(0) = 1 for all i. Then one constructs Ai+1 from Ai using one of the following two methods:

See Also


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


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: 2015-09-03.

Show usage of this method