Improved Johnson Bound

In [1] the original Johnson bound is improved based on ideas already stated in Theorem 4 and the appendix of [2]. A concise formulation of this bound can also be found in [3].

Assuming that C is a binary (s, N, 2u)-even-weight-code with 0 ∈ C (every (s, N, 2u)- and (s−1, N, 2u−1)-code over ℤ2 is equivalent to such a code due to code truncation and adding a parity check bit), the improved Johnson bound states that

N max$\displaystyle \left\{\vphantom{ \sum_{i=0}^{u−1}K_{2i},\sum_{i=0}^{u−1}K_{2i+1}}\right.$$\displaystyle \sum_{{i=0}}^{{u−1}}$K2i,$\displaystyle \sum_{{i=0}}^{{u−1}}$K2i+1$\displaystyle \left.\vphantom{ \sum_{i=0}^{u−1}K_{2i},\sum_{i=0}^{u−1}K_{2i+1}}\right\}$ ≤ 2s−1.

In this formula Kr = $ \binom{s}{r}$ for r ≤ u and

Kr ≥ max$\displaystyle \left\{\vphantom{ \frac{C_{r}}{R_{r}},\frac{2m_{r}C_{r}-D_{r}}{m_{r}(1+m_{r})}}\right.$$\displaystyle {\frac{{C_{r}}}{{R_{r}}}}$,$\displaystyle {\frac{{2m_{r}C_{r}-D_{r}}}{{m_{r}(1+m_{r})}}}$$\displaystyle \left.\vphantom{ \frac{C_{r}}{R_{r}},\frac{2m_{r}C_{r}-D_{r}}{m_{r}(1+m_{r})}}\right\}$

for r > u. Furthermore, the integer Cr is the number of vectors in ℤ2s with weight r and distance r from C, which can be bounded from below by

Cr ≥ max$\displaystyle \left\{\vphantom{ 0,\binom{s}{r}-\sum_{v=u}^{r−1}A_{2}(s,d,2v)\sum_{z=0}^{r-v−1}\binom{2v}{2v-r+z}\binom{s−2v}{z}}\right.$0,$\displaystyle \binom{s}{r}$ – $\displaystyle \sum_{{v=u}}^{{r−1}}$A2(s, d, 2v)$\displaystyle \sum_{{z=0}}^{{r-v−1}}$$\displaystyle \binom{2v}{2v-r+z}$$\displaystyle \binom{s−2v}{z}$$\displaystyle \left.\vphantom{ 0,\binom{s}{r}-\sum_{v=u}^{r−1}A_{2}(s,d,2v)\sum_{z=0}^{r-v−1}\binom{2v}{2v-r+z}\binom{s−2v}{z}}\right\}$.

The integer Dr is the sum of the number of code words in C ∖ { 0} with distance r from each of these vectors, which can be bounded from above by

Dr ≤ $\displaystyle \sum_{{v=0}}^{{r-u}}$$\displaystyle \binom{2r−2v}{r-v}$$\displaystyle \binom{s−2r+2v}{v}$A2(s, d, 2r−2v).

The integer mr is defined as

mr := 1 + ⌊Dr/Cr⌋.

Finally, A2(s, d, w) denotes the maximum number of code words of a constant-weight code.

MinT includes all improved Johnson bounds up to s = 100000.

See Also

References

[1]Selmer M. Johnson.
On upper bounds for unrestricted binary error-correcting codes.
IEEE Transactions on Information Theory, 17(4):466–478, July 1971.
[2]Selmer M. Johnson.
A new upper bound for error-correcting codes.
IEEE Transactions on Information Theory, 8(3):203–207, April 1962.
[3]Selmer M. Johnson.
Upper bounds for constant weight error correcting codes.
Discrete Mathematics, 3:109–124, 1972.
doi:10.1016/0012-365X(72)90027-1

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. “Improved Johnson Bound.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2015-09-03. http://mint.sbg.ac.at/desc_CBoundImprovedJohnson.html

Show usage of this method