Some Results on Incorrigible Sets of Binary Linear Codes

Hedong HOU  Haiyang LIU  Lianrong MA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E104-A    No.2    pp.582-586
Publication Date: 2021/02/01
Publicized: 2020/08/06
Online ISSN: 1745-1337
DOI: 10.1587/transfun.2020EAL2021
Type of Manuscript: LETTER
Category: Coding Theory
binary linear code,  incorrigible set,  matroid,  Tutte polynomial,  

Full Text: PDF>>
Buy this Article

In this letter, we consider the incorrigible sets of binary linear codes. First, we show that the incorrigible set enumerator of a binary linear code is tantamount to the Tutte polynomial of the vector matroid induced by the parity-check matrix of the code. A direct consequence is that determining the incorrigible set enumerator of binary linear codes is #P-hard. Then for a cycle code, we express its incorrigible set enumerator via the Tutte polynomial of the graph describing the code. Furthermore, we provide the explicit formula of incorrigible set enumerators of cycle codes constructed from complete graphs.