Construction Y1 (Bound)
Shortening allows the construction of a linear [s−u, n−u, d]-code from a linear [s, n, d]-code for u = 1,…, n. However, in some situations it is possible to obtain a code-dimension of n−u + 1 instead of n−u.
Given a linear [s, n, d]-code C, then a new linear [s−u, n−u + 1, d]-code Cʹ over the same field exists, given that the dual distance d⊥ of C (the distance of C⊥, the dual code of C) is less or equal to u.
The new code is obtained by removing u columns from the parity check matrix of C such that all d⊥ non-zero coordinates of the minimum weight code word of C⊥ are removed.
Since MinT has no knowledge about the minimum distance of C⊥, it has to assume the worst and use the upper bound on the minimum distance of any [s, s−n]-code.
Parameters of the Involved Codes
This propagation rule is used by MinT in three different circumstances:
The straightforward way is to obtain Cʹ based on C. This method is listed as non-constructive because there is no efficient method for determining the minimum-weight codeword in C⊥. Cʹ is listed as parent of the construction.
This method can also be used for showing that the minimum distance of C⊥ is greater than u, provided that Cʹ does not exist. Applied in this way this rule is constructive, because the dual code can always be constructed efficiently. MinT lists C is listed as parent, the non-existence of Cʹ as the second parent of this construction.
When MinT uses this method for establishing bounds for codes, the non-existence is proven for the code C, whereas the first base code listed is the (non existent) resulting code Cʹ, and the second base code is the (non existent) dual C⊥ of C.
See Also
[1, Ch. 18, Section 9.1]
References
| [1] | F. Jessie MacWilliams and Neil J. A. Sloane. The Theory of Error-Correcting Codes. North-Holland, Amsterdam, 1977. |
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. “Construction Y1 (Bound).”
From MinT—the database of optimal net, code, OA, and OOA parameters.
Version: 2015-09-03.
http://mint.sbg.ac.at/desc_CConsB-bound.html