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 ρ_κ(H) denote the number of vectors in F_b^m that can be obtained by a linear combination of κ or less columns of H. If ρ_k−1(H) < b^m, a vector x ∈ F_b^m 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(b^m, s + 1,F_b, k).

Now the original Varšamov bound follows from

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^m_i, s_i,F_b, k) and generator matrices H_i as follows: One starts with an existing OA A₀ and estimates

ρ_κ(H₀) ≤ N₀(κ) := minb^m, V_b^s(κ)

for κ = 0,…, k−1. Note that ρ₀(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^m_i, a vector x ∈ F_b^m_i exists such that H_i+1 := (H_i|x) is the generator matrix of an OA(b^m_i, s_i +1,F_b, k) which we use as A_i+1. Furthermore we have

  ρ_κ(H_i+1) ≤ N_i+1(κ) := min{b^m_i+1, N_i(κ) + (b – 1)N_i(κ – 1)}

  for 1,…, k−1.

• If N_i(k – 1) = b^m_i, 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)^jN_i(k – 1 – j) < b^m_i+r,

  which can be shown to be equivalent to determining the smallest r such that N_i(k – 1 – r) < b^m_i. Now a vector x ∈ F_b^m_i+r can be found such that H_i+1 := (H_iʹ|x) is the generator matrix of an OA(b^m_i+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(κ) := minb^m_i+1, (b – 1)^jN_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: 2024-09-05. http://mint.sbg.ac.at/desc_CVarshamovEdel.html