Linear Programming Bound with Additional Constraints on the Weights

The linear programming bound for codes can be strengthened by taking into account that some weights cannot appear in a code with certain parameters. This observations yields to additional bounds of the form Ai = 0 for all iI, where I is a subset of {d + 1,…, s}.

Over the Binary Field

The nonexistence of the following codes is established by Daskalov and Kapralov:

Non-existent CodeReference
[43, 17, 14][1, Theorem 2]
[56, 18, 20][1, Theorem 2]
[61, 19, 22][1, Theorem 2]
[56, 29, 14][1, Theorem 2]
[47, 17, 16][1, Theorem 3]

Over the Ternary Field

In [2] Daskalov and Metodieva use this method for showing that neither a [105, 6, 68]-code nor a [230, 6, 152]-code over 3 can exist.

Over the Quaternary Field

Greenough and Hill show the nonexistence of a [32, 4, 23]-code over F4 in [3, Theorem 3.9], the non-existence of a [58, 4, 43]-code in [3, Theorem 3.12].

In [4] Daskalov and Metodieva use this method for showing that codes with the following parameters over F4 cannot exist: [29, 5, 20], [58, 5, 42], [62, 5, 45], [87, 5, 64], [108, 5, 80], [188, 5, 140], [192, 5, 143], [225, 5, 168], [241, 5, 180], [245, 5, 183], and [250, 5, 187]. The nonexistence of a [240, 5, 179]-code over F4 is shown in [5, Theorem 13] by Boukliev, Daskalov and Kapralov.

Over 5

The nonexistence of the following codes is established by Daskalov and Gulliver:

Non-existent CodeIReference
[75, 8, 55] {56, 61, 62, 66}[6, Theorem 5]
[80, 8, 59] {61, 66, 67, 71}[6, Theorem 5]

References

[1]Rumen N. Daskalov and Stoyan N. Kapralov.
New minimum distance bounds for certain binary linear codes.
IEEE Transactions on Information Theory, 38(6):1795–1796, November 1992.
doi:10.1109/18.165453
[2]Rumen N. Daskalov and Elena Metodieva.
The nonexistence of ternary [105, 6, 68] and [230, 6, 152] codes.
Discrete Mathematics, 286(3):225–232, September 2004.
doi:10.1016/j.disc.2004.06.002
[3]P. P. Greenough and Raymond Hill.
Optimal linear codes over GF(4).
Discrete Mathematics, 125(1–3):187–199, February 1994.
doi:10.1016/0012-365X(94)90160-0
[4]Rumen N. Daskalov and Elena Metodieva.
The nonexistence of some five-dimensional quaternary linear codes.
IEEE Transactions on Information Theory, 41(2):581–583, March 1995.
doi:10.1109/18.370155
[5]Iliya G. Boukliev, Rumen N. Daskalov, and Stoyan N. Kapralov.
Optimal quaternary linear codes of dimension five.
IEEE Transactions on Information Theory, 42(4):1228–1235, July 1996.
doi:10.1109/18.508846 MR1445641 (98b:94017)
[6]Rumen N. Daskalov and T. Aaron Gulliver.
New minimum distance bounds for linear codes over small fields.
Problems of Information Transmission, 37(3):206–215, July 2001.
doi:10.1023/A:1013873906597

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. “Linear Programming Bound with Additional Constraints on the Weights.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2008-04-04. http://mint.sbg.ac.at/desc_CBoundLPConstraints.html

Show usage of this method