Infinite Families of Optimal Linear Codes Constructed From Simplicial Complexes

• Published in: IEEE transactions on information theory 2020-11, Vol.66 (11), p.6762-6773
• Main Authors: Hyun, Jong Yoon, Lee, Jungyun, Lee, Yoonjin
• Format: Article
• Language: English
• Subjects: 3G mobile communication; 94A60; Binary codes; Binary system; Codes; Cost accounting; Criteria; Cryptography; Generators; Griesmer code; Linear codes; Mathematics; Optimal linear code; simplicial complex; weight distribution 2010 AMS Subject Classification 94B05
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.2020.2993179

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_{\Delta ^{c}} constructed from simplicial complexes in \mathbb {F}^{n}_{2} , where \Delta is a simplicial complex in \mathbb {F}^{n}_{2} and \Delta ^{c} the complement of \Delta . We first find an explicit computable criterion for C_{\Delta ^{c}} to be optimal; this criterion is given in terms of the 2-adic valuation of \sum _{i=1}^{s} 2^{|A_{i}|-1} , where the A_{i} 's are maximal elements of \Delta . Furthermore, we obtain much simpler criteria under various specific conditions on the maximal elements of \Delta . In particular, we find that C_{\Delta ^{c}} is a Griesmer code if and only if the maximal elements of \Delta are pairwise disjoint and their sizes are all distinct. Specially, when \mathcal {F} has exactly two maximal elements, we explicitly determine the weight distribution of C_{\Delta ^{c}} . We present many optimal linear codes constructed by our method, and we emphasize that we obtain at least 32 new optimal linear codes.