MinT - Varšamov–Edel Lengthening

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

ρ_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^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₀(κ) := min $\displaystyle \left\{\vphantom{ b^{m},\, V_{b}^{s}(\kappa)}\right.$ b^m, V_b^s(κ) $\displaystyle \left.\vphantom{ b^{m},\, V_{b}^{s}(\kappa)}\right\}$

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ʹ := $\displaystyle \left(\vphantom{\begin{array}{cc} \vec{H}_{i} & \vec{0}\\ \vec{0} & \vec{I}_{r}\end{array}}\right.$ $\displaystyle \begin{array}{cc} \vec{H}_{i} & \vec{0}\\ \vec{0} & \vec{I}_{r}\end{array}$ $\displaystyle \left.\vphantom{\begin{array}{cc} \vec{H}_{i} & \vec{0}\\ \vec{0} & \vec{I}_{r}\end{array}}\right)$ ,
where r ≥ 1 is chosen as small as possible such that
ρ_k−1(H_iʹ) ≤ N_iʹ(k – 1) := $\displaystyle \sum_{{j=0}}^{{r}}$ $\displaystyle \binom{r}{j}$ (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(κ) := min $\displaystyle \left\{\vphantom{ b^{m_{i+1}},\,\sum_{j=0}^{\min\{\kappa,r+1\}}\binom{r+1}{j}(b−1)^{j}N_{i}(\kappa-j)}\right.$ b^m_i+1, $\displaystyle \sum_{{j=0}}^{{\min\{\kappa,r+1\}}}$ $\displaystyle \binom{r+1}{j}$ (b – 1)^jN_i(κ−j) $\displaystyle \left.\vphantom{ b^{m_{i+1}},\,\sum_{j=0}^{\min\{\kappa,r+1\}}\binom{r+1}{j}(b−1)^{j}N_{i}(\kappa-j)}\right\}$ .

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: 2015-09-03. http://mint.sbg.ac.at/desc_CVarshamovEdel.html

Show usage of this method

Varšamov–Edel Lengthening

See Also

References

Copyright