IEEE Transactions on Information Theory · 2020 · 60 citations · 16 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsTopologyCoding TheoryComputational ComplexityError-correcting CodesBounds On CodesCode OptimalityLinear CodesMinimum DistanceMinimum Distance BoundsSimplicial ComplexesSimplicial Sets
A linear code is optimal if it has the highest minimum distance of any linear code with a given length and dimension. We construct infinite families of optimal binary linear codes C <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Δc</sub> constructed from simplicial complexes in F <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> , where Δ is a simplicial complex in F <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> and Δ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">c</sup> the complement of Δ. We first find an explicit computable criterion for C <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Δc</sub> to be optimal; this criterion is given in terms of the 2-adic valuation of Σ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">s</sup> <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">j=1</sub> 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">|Ai|-1</sup> , where the At's are maximal elements of Δ. Furthermore, we obtain much simpler criteria under various specific conditions on the maximal elements of Δ. In particular, we find that C <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Δc</sub> is a Griesmer code if and only if the maximal elements of Δ are pairwise disjoint and their sizes are all distinct. Specially, when f has exactly two maximal elements, we explicitly determine the weight distribution of C <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Δc</sub> .We present many optimal linear codes constructed by our method, and we emphasize that we obtain at least 32 new optimal linear codes.
16
Adi Shamir · Communications of the ACM · 1979 · 13.5K citations · Full text
Minimal vectors in linear codes
Alexei Ashikhmin, Alexander Barg · IEEE Transactions on Information Theory · 1998 · 355 citations